Meta-Heurística Colônia de Formigas

  • View
    30

  • Download
    0

Embed Size (px)

DESCRIPTION

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 - PowerPoint PPT Presentation

Text of Meta-Heurística Colônia de Formigas

Colnia de Formigas

Meta-Heurstica Colnia de FormigasDisciplina: ODSTProfessores: Jos Oliveira e Maria CarravillaAluno: Marcelo NogueiraFEUP FEVEREIRO 20081IntroduoAlgoritmos de formigas: propostos inicialmente por Dorigo para soluo de problemas de optimizao combinatria Inspirado na observao de colnias de formigas reaisFormiga: insecto social, ou seja, vive em colnias e tem comportamento direccionado para a sobrevivncia da colnia ao invs de um nico individuo da colnia2Colnias de formigas (ACO) Chamaram ateno dos cientistas devido ao seu alto grau de estruturao quando comparado com a simplicidade de um nico individuo da colniaFormigas, que so quase cegas, conseguem achar o caminho mais curto entre sua colnia a uma fonte de alimento. Como?

3Caminho mais curto por colnias de formigas (biolgicas)Formigas se comunicam atravs de marcas qumicas deixadas no cho chamadas feromnioAo passar por um local uma formiga deixa uma certa quantidade de feromnio no cho formando assim trilhasOutras formigas podem detectar tais trilhas com feromnio, e tendem a escolher seu caminho por trilhas com mais feromnio

4Caminho mais curto por colnias de formigas (biolgicas)Quando mais formigas passarem por uma trilha, mais feromnio esta ter, formando assim uma realimentao positivaEste comportamento simples de seguir trilhas faz emergir um comportamento mais complexo de encontrar trilhas mais curtas entre dois pontos5Caminho mais curto por colnias de formigas (biolgicas)

FormigueiroFormigas andando aleatoriamenteComida6Caminho mais curto por colnias de formigas (biolgicas)

FormigueiroAchou a comida e vai voltar para o formigueiroComida7Caminho mais curto por colnias de formigas (biolgicas)

FormigueiroAchou a comida e vai voltar para o formigueiroComida

8Caminho mais curto por colnias de formigas (biolgicas)

FormigueiroAchou a comida e vai voltar para o formigueiroComida

Achou a comida e vai voltar para o formigueiro

9Caminho mais curto por colnias de formigas (biolgicas)

FormigueiroComida

10Caminho mais curto por colnias de formigas (biolgicas)

FormigueiroComida

Tem maior probabilidade de ir por baixo (trilha onde passaram mais formigas - mais feromnio) 11Caminho mais curto por colnias de formigas (biolgicas)

FormigueiroComida

12Algoritmo AS (Ant System) para o TSPFormigas artificiais: passeiam pelo grafo realizando caminhosA partir da ciadade i a escolha da proxima cidade j depende da distancia entre i e j e da quantidade de feromnio no arco i-j

13Ao terminar um caminho com custo Lk, a formiga k deposita feromnio em todas as arestas visitadas neste caminho numa quantidade inversamente proporcional a Lk

Algoritmo AS (Ant System) para o TSP

114Ao final de todas as formigas terem realizado o passeio, a quantidade de feromnio em cada aresta actualizadaPara evitar estagnao (formigas percorrendo sempre o mesmo caminho mnimo local) , o feromnio das trilhas possui uma taxa de evaporao < 1

Algoritmo AS (Ant System) para o TSP

15Enquanto (criterio de parada)Para cada formiga kPercorrer_caminho()fim_para Atualizar_feromonio()Decorar_melhor_solucao_atual()Fim_enquantoAlgoritmo AS (Ant System) para o TSPs depois de todas a formigas terem feito seus caminhos16Percorrer_caminho()Iniciar aleatoriamente em uma cidade do grafoEnquanto(caminho incompleto)escolher prxima cidade ainda no visitada de acordo com a regra de probabilidadesincluir tal cidade na soluo parcialFim_enquantoCalcular custo do camihoPara a formiga k decorar caminho realizado e custoFim17Parmetros do ASExistem basicamente 3 parmetros a serem ajustados:Alpha: informa a importncia do feromnio na escolha da prxima cidadeBeta: informa a importncia da distancia entre cidades (visibilidade) na escolha da prxima cidadeRho: taxa de evaporao do feromnio18Variaes do ASActualizao do feromnio na medida que cada formiga termina seu caminhoEnquanto (criterio de parada)Para cada formiga kPercorrer_caminho()Atualizar_feromonio()fim_paraDecorar_melhor_solucao_atual()Fim_enquantoJ actualiza o feromnio das arestas19Actualizao do feromnio na medida que cada formiga faz seu caminho: ao passar por uma aresta, a formiga deposita uma certa quantidade Q de feromnioEnquanto (criterio de parada)Para cada formiga kPercorrer_caminho(){Atualizar_feromonio()}fim_paraDecorar_melhor_solucao_atual()Fim_enquantoActualiza dentro da funoPercorrer_caminho()20AplicaesPrincipalmente para o TSP, mas tambm pode ser aplica do a:SchedulingNetwork synthesisVehicle routing

21Vantagens e DesvantagensWalter Gutjahr provou que um algoritmo particular de ACO converge para a soluo optima. Mas tal algoritmo no foi implementando e bem difente de qualquer impletao j feiraAS fornece boms resultados para grafos pequenos (30 cidades), mas para grafos maiores os resultados pioram, e exigem variaes do ASPara problemas grandes, uma grande quantidade de memria usadaMtodo lento: muitos clculos de ponto flutuante (probabilidades)

22Resultados obtidos29 cidades: arquivo 51 cidades: arquivo

23Resultados obtidos1002 cidades - ptimo: 259045 1 5 0.9 e 50 iteraes com numero de formigas reduzido 50 formigas( 15 minutos)Custo= 3638331 7 0.9 e 50 iteraes Custo= 333268Insero mais barata: 30467224ConclusesAlgoritmo novo, ainda em desenvolvimentoResultados muito bons para problemas pequenos. Para problemas grandes temos que utilizar modificaes do AS25Bibliografiahttp://www.aco-metaheuristic.org visitada em 29/01/2008Ant Algorithms for Discrete Optimization, Marco Dorigo, Gianni Di Caro and Luca M. GambardellaThe Ant System: Optimization by a colony of cooperating agents, Marco Dorigo, Vittorio Maniezzo, and Alberto Colorniwww.wikipedia.org, visitada em 29/01/2008Ant colony optimization theory: A survey, Marco Dorigo and Christian BlumThe ant Colony Optimization Meta-Heuristic, Marco Dorigo and Gianni Di Caro26