Pesquisa Informada e Algoritmos Genéticos

A abordagem best-first search designa-se por pesquisa informada que expande o nó mais promissor (não o caminho mais curto) em primeiro lugar. O algoritmo A* é um caso específico desta abordagem. A maior desvantagem (Algoritmo A*) é a grande necessidade de recursos de memória. O algoritmo A* resulta no algoritmo de Dijkstra quando a função Heurística h(n)=0 para cada nó existente.

Greedy Best-First Search

Completo? Não, nem sempre encontra uma solução. Complexidade: Tempo O(b^m) Memória O(b^m). Ótimo? Não, o caminho encontrado pode não ser o mais curto.

A* Search

Completo? Sim, a menos da existência de um número infinito de nós. Complexidade: Tempo = O(b^m) Memória O(b^m). Ótimo? Sim, assumindo uma heurística admissível. Eficácia Ótima? Sim, nenhum outro algoritmo com a mesma heurística consegue expandir menos nós.

Algoritmos Genéticos:

Caminhada Aleatória:

1. Amostrar soluções em todo o espaço de pesquisa usando uma função de distribuição uniforme.
2. Em cada interação: escolhe uma solução aleatoriamente, compara-a com a melhor e guarda a melhor.
3. Ou seja, a caminhada aleatória é uma formalização matemática de um trajeto que consiste em fazer exames sucessivos em etapas aleatórias.

Os algoritmos genéticos são uma classe de procedimentos, com distintas bem definidas. Utilizam uma codificação do conjunto de parâmetros (indivíduos) e não com o próprio parâmetro (estados).

Para que servem?

• Busca e otimização
• Amplamente utilizados, com sucesso, em problemas de difícil manipulação pelas técnicas tradicionais
• Eficiência vs Flexibilidade.

Funcionamento Fundamental:

A seleção escolhe soluções com base na sua “qualidade” relativa. Cruzamento decompõe duas soluções distintas e mistura de forma aleatória as suas partes para formar soluções novas. Mutação modifica aleatoriamente uma solução.

Função de Aptidão:

Fornece uma indicação da qualidade (aptidão) de uma Solução.

Seleção:

Orientar a população para regiões promissoras da área de Pesquisa. Escolher as melhores soluções. Existem vários métodos de seleção:

• Roleta: Colocam-se os indivíduos numa roleta, dando uma fatia proporcional à aptidão. No rolar, o indivíduo que parar a agulha passa à próxima e depois repete-se o processo.
• Torneio: Utiliza sucessivas disputas para realizar a seleção. O indivíduo com a melhor aptidão é selecionado.
• Amostragem Universal Estocástica (SUS): Semelhante à roleta, mas para k indivíduos, utilizar k agulhas igualmente espaçadas, girando-as em conjunto, mas só uma vez.