Heurísticas - ia
1465 palavras
6 páginas
UNIVERSIDADE NOVE DE JULHO – UNINOVEDAISY MONTE MACHADO
RENATO SANTANA BRITO
RICARDO RAMOS DOS SANTOS
META-HEURÍSTICAS
SÃO PAULO
2012
DAISY MONTE MACHADO
RENATO SANTANA BRITO
RICARDO RAMOS DOS SANTOS
META-HEURÍSTICAS
Atividade de IA II
Linha de pesquisa: Meta-heurísticas
Professor: Adilson Pereira Marques
SÃO PAULO
2012
INDICE
1 BUSCA TABU ...................................................................................................................................... 4
2 SIMULATED ANNEALING ................................................................................................................. 7
3 OTIMIZAÇÃO DE COLÔNIA DE FORMIGAS - OCF.......................................................................... 9
4 ALGORITMOS GENÉTICOS ............................................................................................................ 10
3 CONCLUSÃO .................................................................................................................................... 12
4
Busca Tabu
A meta heurística busca tabu, é utilizada quando o intuito é evitar percorrer o caminho já visitado, criando uma lista de estados já visitados.
O seu algoritmo evita retornar ao local já visitado previamente, com o intuito de atingir um resultado ótimo ou próximo ao ótimo global.
A busca tabu é capaz de armazenar em suas memórias flexíveis os espaços já percorridos. Para que o algoritmo seja capaz de encontrar “boas soluções”, são utilizadas técnicas de memória adaptativa. Uma “boa solução” está próximo do ótimo global. Assim como outras metas heurísticas, a busca tabu consome tempo de processamento e de experiências percorrendo diversos caminhos, porem é considerado um tempo de processamento aceitável.
A seguir é apresentado um exemplo:
Figura 1.1 – Solução inicial
5
Figura 1.2 – Ótimo local
Figura 1.3 – Elemento tabu
Figura 1.4 – Ótimo global
6
O ponto de partida se