Dove posso trovare ulteriori informazioni su & # 8220; ant colony & # 8221; ottimizzazioni?

Question

Sto leggendo cose qua e là da un po 'di tempo sull'uso di una "colonia di formiche" modello come approccio euristico per l'ottimizzazione di vari tipi di algoritmi. Tuttavia, devo ancora trovare un articolo o un libro che discute l'ottimizzazione delle colonie di formiche in modo introduttivo o anche in molti dettagli. Qualcuno può indicarmi alcune risorse in cui posso saperne di più su questa idea?

Answer 1

Se non conosci il tedesco (sì, scusa & # 8230;), un amico e io abbiamo scritto un introduzione con codice su questo argomento che trovo abbastanza accettabile. Il testo e il codice usano l'esempio di TSP per introdurre il concetto.

Anche se non conosci il tedesco, dai un'occhiata al codice e alle formule nel testo, questo potrebbe comunque essere utile.

Answer 2

link Wikipedia mi ha davvero dato il via. Ho letto l'articolo e ho iniziato a scrivere codice. Stavo risolvendo una variazione malvagia del problema del commesso viaggiatore. È un incredibile meta-euristico. Fondamentalmente, qualsiasi tipo di problema di ricerca che può essere inserito in un grafico (nodi e bordi, simmetrici o meno) può essere risolto con un ACO.

Cerca la differenza tra le tracce di feromoni globali e locali. I feromoni locali scoraggiano una generazione di formiche percorrendo lo stesso percorso. Impediscono al modello di convergere. I feromoni globali sono attrattori e dovrebbero afferrare almeno una formica per generazione. Incoraggiano percorsi ottimali per diverse generazioni.

Il miglior suggerimento che ho, è semplicemente giocare con l'algoritmo. Imposta un solutore TSP di base e alcune visualizzazioni di base delle colonie. Allora divertiti. Lavorare con le formiche, concettualmente, è fantastico. Programmate i loro comportamenti di base e poi li liberate. Mi affeziono persino a loro. :)

Gli ACO sono una forma più avida di algoritmi genetici. Gioca con loro. Modifica i loro comportamenti comunicativi e il comportamento dei pacchetti. Inizierai rapidamente a vedere la programmazione di reti / grafici in un modo completamente diverso. Questo è il loro più grande vantaggio, non la ricetta che la maggior parte delle persone vede.

Devi solo giocarci per capirlo davvero. Libri e libri; i documenti di ricerca forniscono solo una comprensione generale alle stelle. Come una bici, devi solo iniziare a guidare. :)

Gli ACO, di gran lunga, sono la mia astrazione preferita per i problemi con i grafici.

Answer 3

National Geographic ha scritto un articolo interessante qualche tempo fa parlando di alcuni delle teorie.

Answer 4

La migliore risorsa per questi argomenti è Google scholar . Ho lavorato sugli algoritmi di Ant Colony Optimization per un po ', qui ci sono alcuni buoni documenti:

• Ottimizzazione delle colonie di formiche - Un nuovo metaoreuristico
• Ottimizzazione delle colonie di formiche - Formiche artificiali come tecnica di intelligenza computazionale

Solo cercare " Ant Colony " su google scholar .

Cerca anche articoli pubblicati da Marco Dorigo .

Answer 5

Sono sorpreso che nessuno abbia menzionato la Bibbia di ACO:

Marco Dorigo & amp; Thomas St & # 252; tzle: ottimizzazione della colonia di formiche

Questo libro è stato scritto dall'autore di ACO ed è altamente leggibile. Puoi portarlo in spiaggia e divertirti a leggerlo. Ma è anche la risorsa più completa di tutte, ottima come riferimento quando si implementa la cosa.

Puoi leggere alcuni estratti su Google Libri

Un'altra grande fonte di saggezza è la Homepage ACO

Answer 6

Vedi ad esempio questo articolo su scholarpedia.

C'è anche una discussione qui nel Qual è il modo più efficiente di trovare un percorso attraverso un piccolo grafico mondiale? domanda.

Answer 7

A prima vista questo sembra essere strettamente correlato (o predice un caso speciale di) the Algoritmo Metropolis . Quindi questa è un'altra possibile direzione per la ricerca.

Aggiunta: Questo file PDF include un riferimento al documento originale Metropolis del 1953.

Answer 8

Bene, ho trovato la Homepage di Eric Rollins e le sue diverse implementazioni (Haskell, Scala, Erlang, ...) di un algoritmo ACO utile. E anche il libro di Enrique Alba, intitolato "Metaheuristics parallela: una nuova classe di algoritmi". dove puoi trovare un intero capitolo di spiegazioni sugli algoritmi ACO e sui loro diversi usi.

Hth