View
117
Download
6
Category
Preview:
Citation preview
Meta-Heurística Colônia de Formigas
Disciplina: ODSTProfessores: 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
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?
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
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
Caminho mais curto por colónias de formigas (biológicas)
Formigueiro
Formigas andando aleatoriamente
Comida
Caminho mais curto por colónias de formigas (biológicas)
Formigueiro
Achou a comida e vai voltar para o formigueiro
Comida
Caminho mais curto por colónias de formigas (biológicas)
Formigueiro
Achou a comida e vai voltar para o formigueiro
Comida
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
Caminho mais curto por colónias de formigas (biológicas)
FormigueiroComida
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)
Caminho mais curto por colónias de formigas (biológicas)
FormigueiroComida
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”
• 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
• 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
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
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
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
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
• 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()
Aplicações
• Principalmente para o TSP, mas também pode ser aplica do a:– Scheduling– Network synthesis– Vehicle routing
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)
Resultados obtidos
• 29 cidades: arquivo • 51 cidades: arquivo
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
Conclusões
• Algoritmo novo, ainda em desenvolvimento• Resultados muito bons para problemas
pequenos. Para problemas grandes temos que utilizar modificações do AS
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
Recommended