Heurística (ciência da computação) - Heuristic (computer science)

Em otimização matemática e ciência da computação , heurística (do grego εὑρίσκω "Eu encontro, descubro") é uma técnica projetada para resolver um problema mais rapidamente quando os métodos clássicos são muito lentos, ou para encontrar uma solução aproximada quando os métodos clássicos falham em encontrar qualquer solução. Isso é obtido trocando-se otimização, integridade, exatidão ou precisão por velocidade. De certa forma, pode ser considerado um atalho.

Uma função heurística , também chamada simplesmente de heurística , é uma função que classifica alternativas em algoritmos de pesquisa em cada etapa de ramificação com base nas informações disponíveis para decidir qual ramificação seguir. Por exemplo, pode aproximar a solução exata.

Definição e motivação

O objetivo de uma heurística é produzir uma solução em um período de tempo razoável que seja bom o suficiente para resolver o problema em questão. Essa solução pode não ser a melhor de todas as soluções para esse problema ou pode simplesmente aproximar-se da solução exata. Mas ainda é valioso porque encontrá-lo não requer um tempo proibitivamente longo.

As heurísticas podem produzir resultados por si mesmas ou podem ser usadas em conjunto com algoritmos de otimização para melhorar sua eficiência (por exemplo, podem ser usadas para gerar bons valores iniciais).

Os resultados sobre a dureza NP na ciência da computação teórica tornam a heurística a única opção viável para uma variedade de problemas de otimização complexos que precisam ser resolvidos rotineiramente em aplicações do mundo real.

As heurísticas estão na base de todo o campo da Inteligência Artificial e da simulação computacional do pensamento, pois podem ser utilizadas em situações onde não existem algoritmos conhecidos .

Troca

Os critérios de compensação para decidir se deve usar uma heurística para resolver um determinado problema incluem o seguinte:

• Optimalidade: quando existem várias soluções para um determinado problema, a heurística garante que a melhor solução será encontrada? É realmente necessário encontrar a melhor solução?
• Completude: quando existem várias soluções para um determinado problema, a heurística pode encontrar todas elas? Precisamos realmente de todas as soluções? Muitas heurísticas destinam-se apenas a encontrar uma solução.
• Exatidão e precisão: a heurística pode fornecer um intervalo de confiança para a solução pretendida? A barra de erro da solução é excessivamente grande?
• Tempo de execução : esta é a heurística mais conhecida para resolver esse tipo de problema? Algumas heurísticas convergem mais rápido do que outras. Algumas heurísticas são apenas marginalmente mais rápidas do que os métodos clássicos, caso em que a 'sobrecarga' no cálculo da heurística pode ter um impacto negativo.

Em alguns casos, pode ser difícil decidir se a solução encontrada pela heurística é boa o suficiente, porque a teoria subjacente à heurística não é muito elaborada.

Exemplos

Problema mais simples

Uma forma de obter o ganho de desempenho computacional esperado de uma heurística consiste em resolver um problema mais simples cuja solução também seja uma solução para o problema inicial.

Problema do caixeiro viajante

Um exemplo de aproximação é descrito por Jon Bentley para resolver o problema do caixeiro viajante (TSP):

• "Dada uma lista de cidades e as distâncias entre cada par de cidades, qual é o trajeto mais curto possível que visita cada cidade e retorna à cidade de origem?"

para selecionar a ordem de desenho usando um plotter de caneta . O TSP é conhecido por ser NP-Hard, portanto, uma solução ideal, mesmo para um problema de tamanho moderado, é difícil de resolver. Em vez disso, o algoritmo guloso pode ser usado para fornecer uma solução boa, mas não ótima (é uma aproximação da resposta ótima) em um período de tempo razoavelmente curto. A heurística do algoritmo ganancioso diz para escolher o que for atualmente a melhor próxima etapa, independentemente de isso impedir (ou mesmo tornar impossível) boas etapas posteriores. É uma heurística em que a prática diz que é uma solução boa o suficiente, a teoria diz que existem soluções melhores (e até pode dizer quão melhor em alguns casos).

Procurar

Outro exemplo de heurística tornando um algoritmo mais rápido ocorre em certos problemas de pesquisa. Inicialmente, a heurística tenta todas as possibilidades em cada etapa, como o algoritmo de busca em espaço total. Mas pode interromper a busca a qualquer momento se a possibilidade atual já for pior do que a melhor solução já encontrada. Em tais problemas de pesquisa, uma heurística pode ser usada para tentar boas escolhas primeiro, de modo que caminhos ruins possam ser eliminados mais cedo (consulte poda alfa-beta ). No caso de algoritmos de melhor busca , como A * search , a heurística melhora a convergência do algoritmo enquanto mantém sua correção enquanto a heurística for admissível .

Newell e Simon: hipótese de pesquisa heurística

Em seu discurso de aceitação do Prêmio Turing , Allen Newell e Herbert A. Simon discutem a hipótese de pesquisa heurística: um sistema de símbolos físicos irá gerar e modificar repetidamente estruturas de símbolos conhecidas até que a estrutura criada corresponda à estrutura da solução. Cada etapa seguinte depende da etapa anterior, portanto, a pesquisa heurística aprende quais caminhos seguir e quais ignorar, medindo o quão perto a etapa atual está da solução. Portanto, algumas possibilidades nunca serão geradas, pois são medidas para serem menos prováveis ​​de completar a solução.

Um método heurístico pode realizar sua tarefa usando árvores de pesquisa. No entanto, em vez de gerar todos os ramos de solução possíveis, uma heurística seleciona ramos com maior probabilidade de produzir resultados do que outros ramos. É seletivo em cada ponto de decisão, escolhendo ramos com maior probabilidade de produzir soluções.

Software antivírus

O software antivírus geralmente usa regras heurísticas para detectar vírus e outras formas de malware. A varredura heurística procura códigos e / ou padrões de comportamento comuns a uma classe ou família de vírus, com diferentes conjuntos de regras para vírus diferentes. Se for descoberto que um arquivo ou processo de execução contém padrões de código correspondentes e / ou está executando aquele conjunto de atividades, o mecanismo de varredura infere que o arquivo está infectado. A parte mais avançada da varredura heurística baseada em comportamento é que ela pode funcionar contra vírus auto-modificadores / mutantes ( polimórficos ) altamente aleatórios que não podem ser facilmente detectados por métodos de varredura de strings mais simples. A varredura heurística tem o potencial de detectar vírus futuros sem exigir que o vírus seja primeiro detectado em outro lugar, enviado ao desenvolvedor do scanner de vírus, analisado e uma atualização de detecção para o scanner fornecida aos usuários do scanner.

Armadilhas

Algumas heurísticas têm uma forte teoria subjacente; eles são derivados da teoria de cima para baixo ou são obtidos com base em dados experimentais ou do mundo real. Outros são apenas regras básicas baseadas na observação ou experiência do mundo real, sem nem mesmo um vislumbre da teoria. Estes últimos estão expostos a um maior número de armadilhas.

Quando uma heurística é reutilizada em vários contextos porque foi vista "funcionar" em um contexto, sem ter sido matematicamente provado para atender a um determinado conjunto de requisitos, é possível que o conjunto de dados atual não represente necessariamente conjuntos de dados futuros ( veja: overfitting ) e que as supostas "soluções" acabam sendo semelhantes ao ruído.

A análise estatística pode ser realizada ao empregar heurísticas para estimar a probabilidade de resultados incorretos. Para usar uma heurística para resolver um problema de pesquisa ou um problema de mochila , é necessário verificar se a heurística é admissível . Dada uma função heurística destinada a aproximar a verdadeira distância ótima até o nó objetivo em um grafo direcionado contendo o total de nós ou vértices rotulados , "admissível" significa aproximadamente que a heurística subestima o custo para o objetivo ou formalmente para todos onde . ${\ displaystyle h (v_ {i}, v_ {g})}$${\ displaystyle d ^ {\ star} (v_ {i}, v_ {g})}$${\ displaystyle v_ {g}}$${\ displaystyle G}$${\ displaystyle n}$${\ displaystyle v_ {0}, v_ {1}, \ cdots, v_ {n}}$${\ displaystyle h (v_ {i}, v_ {g}) \ leq d ^ {\ star} (v_ {i}, v_ {g})}$ ${\ displaystyle (v_ {i}, v_ {g})}$${\ displaystyle {i, g} \ in [0,1, ..., n]}$

Se uma heurística não for admissível, ela pode nunca encontrar o objetivo, seja terminando em um beco sem saída do gráfico ou pulando para frente e para trás entre dois nós e onde . ${\ displaystyle G}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {j}}$${\ displaystyle {i, j} \ neq g}$

Etimologia

A palavra "heurística" começou a ser usada no início do século XIX. É formado irregularmente a partir da palavra grega heuriskein , que significa "encontrar".

Veja também

• Algoritmo
• Heurística construtiva
• Algoritmo genético
• Heurística
• Roteamento heurístico
• Avaliação heurística : Método para identificar problemas de usabilidade em interfaces de usuário.
• Metaheurística : Métodos para controlar e ajustar algoritmos heurísticos básicos, geralmente com uso de memória e aprendizado.
• Matheurística : Algoritmos de otimização feitos pela interoperação de metaheurísticas e técnicas de programação matemática (MP).
• Otimização de busca reativa: Métodos que usam princípios de aprendizado de máquina online para autoajuste de heurísticas.
• Recursão (ciência da computação)
• Macro (ciência da computação)

Referências