Onde posso aprender mais sobre otimização de “formigueiro”?

StackOverflow https://stackoverflow.com/questions/444671

Pergunta

Eu estive lendo coisas aqui e ali por um tempo agora sobre o uso de um modelo de "formigueiro" como uma abordagem heurística para otimizar vários tipos de algoritmos. No entanto, eu ainda tenho que encontrar um artigo ou livro que discute otimizações colônia de formigas de forma introdutória, ou mesmo em um monte de detalhes. Alguém pode apontar-me a alguns recursos onde posso aprender mais sobre essa idéia?

Foi útil?

Solução

Sobre a chance de que você sabe alemão (sim, desculpe ...), um amigo e eu ter escrito um introdução com código sobre este assunto que me encontro bastante aceitável. O texto e código usa o exemplo de TSP a introduzir o conceito.

Mesmo Se você não sabe alemão, dê uma olhada no código e as fórmulas do texto, isso pode ainda servir.

Outras dicas

ligação Wikipedia realmente me iniciou. Eu li o artigo e ficou de codificação. Eu estava resolvendo uma variação mau do problema caixeiro-viajante. É uma incrível meta-heurística. Basicamente, qualquer tipo de problema de busca que pode ser colocado em um gráfico (nós e bordas, simétricas ou não) pode ser resolvido com um ACO.

Procure a diferença entre trilhas globais e locais de feromônio. feromônios locais desencorajar uma geração de formigas de percorrer o mesmo caminho. Eles manter o modelo de convergência. feromônios globais são atratores e deve prender pelo menos uma formiga por geração. Eles encorajam os caminhos ideais ao longo de várias gerações.

A melhor sugestão que eu tenho, é simplesmente para jogar com o algoritmo. Configurar um básico TSP solver e alguns visualização colônia básico. Então divirta-se. Trabalhando com formigas, conceitualmente, é muito legal. Você programar seus comportamentos básicos e em seguida, defina-los soltos. I até mesmo crescer gostava deles. :)

ACOs são uma forma greedier de algoritmos genéticos. Brincar com eles. Alterar os seus comportamentos comunicativos e comportamento do bloco. Você vai rapidamente começar a ver programação de rede / gráfico de uma forma totalmente diferente. Essa é a sua maior vantagem, não a receita que a maioria das pessoas vê-lo como.

Você jogo só tem com ele para realmente entendê-la. Livros e artigos de investigação só dar uma compreensão geral muito alto. Como uma bicicleta, você só tem que começar a andar. :)

ACOs, de longe, é meu abstração favorito para problemas gráficos.

National Geographic escreveu um artigo interessante algum tempo atrás falando sobre algum das teorias.

O melhor recurso para esses tópicos é Google scholar . Ive vindo a trabalhar em algoritmos Ant Colony Optimization por um tempo, aqui estão algumas boas papéis:

Apenas procurar "Ant Colony" na Google scholar .

Além disso, procurar artigos publicados por Marco Dorigo .

Estou surpreso que ninguém tenha mencionado a bíblia do ACO:

Marco Dorigo & Thomas Stützle: Ant Colony Optimization

Este livro é escrito pelo autor da ACO e é altamente legível. Você pode levá-lo para a praia e se divertir lendo. Mas também é o recurso mais completo de todos, grande como uma referência ao implementar a coisa.

Você pode ler alguns href="http://books.google.co.uk/books/about/Ant_Colony_Optimization.html?id=_aefcpY8GiEC" rel="nofollow"> trechos

Outra grande fonte de sabedoria é a ACO Homepage

À primeira vista este parece estar estreitamente relacionado com (ou prehaps um caso especial de) o Metropolis algoritmo . Então, isso é outra possível orientação para a pesquisa.

Adição: Este arquivo PDF inclui uma referência ao papel Metropolis originais de 1953.

Bem, eu encontrei o Homepage de Eric Rollins e seus diferentes implementações (Haskell, Scala, Erlang, ...) de um prestativo ACO Algorithm. E também o livro de Enrique Alba, intitulado. "Parallel Metaheurísticas: uma nova classe de Algoritmos", onde você pode encontrar um capítulo inteiro de explicação sobre ACO Algoritmos e seus diferentes usos

Hth

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top