26
Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Embed Size (px)

Citation preview

Page 1: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Meta-Heurística Colônia de Formigas

Disciplina: ODSTProfessores: José Oliveira e Maria Carravilla

Aluno: Marcelo Nogueira

FEUP FEVEREIRO 2008

Page 2: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Introdução

• Algoritmos de formigas: propostos inicialmente por Dorigo para solução de problemas de optimização combinatória

• Inspirado na observação de colónias de formigas reais

• Formiga: insecto social, ou seja, vive em colónias e tem comportamento direccionado para a sobrevivência da colónia ao invés de um único individuo da colónia

Page 3: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Colónias de formigas (ACO)

• Chamaram atenção dos cientistas devido ao seu alto grau de estruturação quando comparado com a simplicidade de um único individuo da colónia

• Formigas, que são quase cegas, conseguem achar o caminho mais curto entre sua colónia a uma fonte de alimento. Como?

Page 4: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Caminho mais curto por colónias de formigas (biológicas)

• Formigas se comunicam através de marcas químicas deixadas no chão chamadas feromônio

• Ao passar por um local uma formiga deixa uma certa quantidade de feromônio no chão formando assim trilhas

• Outras formigas podem detectar tais trilhas com feromônio, e tendem a escolher seu caminho por trilhas com mais feromônio

Page 5: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Caminho mais curto por colónias de formigas (biológicas)

• Quando mais formigas passarem por uma trilha, mais feromônio esta terá, formando assim uma realimentação positiva

• Este comportamento simples de seguir trilhas faz emergir um comportamento mais complexo de encontrar trilhas mais curtas entre dois pontos

Page 6: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Caminho mais curto por colónias de formigas (biológicas)

Formigueiro

Formigas andando aleatoriamente

Comida

Page 7: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Caminho mais curto por colónias de formigas (biológicas)

Formigueiro

Achou a comida e vai voltar para o formigueiro

Comida

Page 8: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Caminho mais curto por colónias de formigas (biológicas)

Formigueiro

Achou a comida e vai voltar para o formigueiro

Comida

Page 9: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Caminho mais curto por colónias de formigas (biológicas)

Formigueiro

Achou a comida e vai voltar para o formigueiro

Comida

Achou a comida e vai voltar para o formigueiro

Page 10: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Caminho mais curto por colónias de formigas (biológicas)

FormigueiroComida

Page 11: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Caminho mais curto por colónias de formigas (biológicas)

FormigueiroComida

Tem maior probabilidade de ir por baixo (trilha onde passaram mais formigas - mais feromônio)

Page 12: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Caminho mais curto por colónias de formigas (biológicas)

FormigueiroComida

Page 13: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Algoritmo AS (Ant System) para o TSP

• Formigas artificiais: passeiam pelo grafo realizando caminhos

• A partir da ciadade “i” a escolha da proxima cidade “j” depende da distancia entre “i” e “j” e da quantidade de feromônio no arco “i-j”

Page 14: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

• Ao terminar um caminho com custo “Lk”, a formiga k deposita feromônio em todas as arestas visitadas neste caminho numa quantidade inversamente proporcional a “Lk”

Algoritmo AS (Ant System) para o TSP

1

Page 15: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

• Ao final de todas as formigas terem realizado o “passeio”, a quantidade de feromônio em cada aresta é actualizada

• Para evitar estagnação (formigas percorrendo sempre o mesmo caminho – mínimo local) , o feromônio das trilhas possui uma taxa de evaporação < 1

Algoritmo AS (Ant System) para o TSP

Page 16: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Enquanto (criterio de parada)Para cada formiga k

Percorrer_caminho()fim_para Atualizar_feromonio()Decorar_melhor_solucao_atual()

Fim_enquanto

Algoritmo AS (Ant System) para o TSP

só depois de todas a formigas terem feito seus caminhos

Page 17: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Percorrer_caminho()Iniciar aleatoriamente em uma cidade do grafoEnquanto(caminho incompleto)

escolher próxima cidade ainda não visitada de acordo com a regra de probabilidadesincluir tal cidade na solução parcial

Fim_enquantoCalcular custo do camihoPara a formiga k decorar caminho realizado e custo

Fim

Page 18: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Parâmetros do AS

• Existem basicamente 3 parâmetros a serem ajustados:– Alpha: informa a importância do feromônio na

escolha da próxima cidade– Beta: informa a importância da distancia entre

cidades (visibilidade) na escolha da próxima cidade

– Rho: taxa de evaporação do feromônio

Page 19: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Variações do AS

• Actualização do feromônio na medida que cada formiga termina seu caminho

Enquanto (criterio de parada)Para cada formiga k

Percorrer_caminho()Atualizar_feromonio()

fim_paraDecorar_melhor_solucao_atual()

Fim_enquanto

Já actualiza o feromônio das arestas

Page 20: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

• Actualização do feromônio na medida que cada formiga faz seu caminho: ao passar por uma aresta, a formiga deposita uma certa quantidade Q de feromônio

Enquanto (criterio de parada)Para cada formiga k

Percorrer_caminho(){…Atualizar_feromonio()

}fim_paraDecorar_melhor_solucao_atual()

Fim_enquanto

Actualiza dentro da funçãoPercorrer_caminho()

Page 21: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Aplicações

• Principalmente para o TSP, mas também pode ser aplica do a:– Scheduling– Network synthesis– Vehicle routing

Page 22: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Vantagens e Desvantagens

• Walter Gutjahr provou que um algoritmo particular de ACO converge para a solução optima. Mas tal algoritmo não foi implementando e é bem difente de qualquer impletação já feira

• AS fornece boms resultados para grafos pequenos (30 cidades), mas para grafos maiores os resultados pioram, e exigem variações do AS

• Para problemas grandes, uma grande quantidade de memória é usada

• Método lento: muitos cálculos de ponto flutuante (probabilidades)

Page 23: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Resultados obtidos

• 29 cidades: arquivo • 51 cidades: arquivo

Page 24: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Resultados obtidos

• 1002 cidades - óptimo: 259045 – 1 5 0.9 e 50 iterações com numero de formigas

reduzido – 50 formigas( 15 minutos)• Custo= 363833

– 1 7 0.9 e 50 iterações • Custo= 333268

• Inserção mais barata: 304672

Page 25: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Conclusões

• Algoritmo novo, ainda em desenvolvimento• Resultados muito bons para problemas

pequenos. Para problemas grandes temos que utilizar modificações do AS

Page 26: Meta-Heurística Colônia de Formigas Disciplina: ODST Professores: José Oliveira e Maria Carravilla Aluno: Marcelo Nogueira FEUP FEVEREIRO 2008

Bibliografia

• http://www.aco-metaheuristic.org visitada em 29/01/2008• Ant Algorithms for Discrete Optimization, Marco Dorigo,

Gianni Di Caro and Luca M. Gambardella• The Ant System: Optimization by a colony of cooperating

agents, Marco Dorigo, Vittorio Maniezzo, and Alberto Colorni• www.wikipedia.org, visitada em 29/01/2008• Ant colony optimization theory: A survey, Marco Dorigo and

Christian Blum• The ant Colony Optimization Meta-Heuristic, Marco Dorigo

and Gianni Di Caro