Algoritmo di colonie di formiche

Naviga le tue risposte
13

Sono uno studente che lavora su un simulatore di colonie di formiche per un progetto di corso. L'algoritmo per esso è (ovviamente) un algoritmo di colonia di formiche. So che ci sono varie forme dell'algoritmo, ma tutte erano matematicamente dettagliate per noi, quindi abbiamo adottato un approccio in cui abbiamo:

  • Una formica nasce in una colonia e deve raccogliere cibo da una fonte per sostenere la colonia.
  • Tutte le formiche sono simili.
  • L'area in cui si muove la formica è una griglia 1000x1000, quindi ogni punto della griglia serve come punto valido per una formica da occupare. Ora, tutti gli algoritmi che ho incontrato coinvolgono il trattamento di vertici e spigoli separatamente, ma poiché limitiamo il movimento delle formiche a sole quattro direzioni (su, giù, sinistra, destra), immagino che non importa dove mettiamo il feromone.
  • I punti della griglia menzionati sopra memorizzano il feromone.
  • Una formica rilascia il feromone solo se trasporta cibo.
  • Per una formica in una posizione (i, j), decide dove muoversi nel passaggio successivo prendendo in considerazione le quantità di feromone sui suoi quattro nodi adiacenti in una semplice formula probabilistica, vale a dire. la probabilità di viaggiare verso un nodo è data da (quantità di feromoni in particolare nodo adiacente) / (somma delle quantità di feromone in 4 nodi adiacenti).
  • Una formica non può tornare alla posizione da cui è appena uscita. Può farlo solo se si trova in un sito che ha cibo o è nella sua colonia.

Ora la mia preoccupazione è (e cosa sta realmente accadendo nel nostro programma) che quando una formica PRIMA raggiunge una posizione che ha cibo e la raccoglie, allora dal nostro algoritmo funziona, può muoversi ovunque! Questo perché lascerà solo una traccia di feromone, una volta che avrà il cibo e non prima e siccome è la prima formica, non c'è traccia esistente.

Se la formica può muoversi ovunque, le formiche che raggiungono la fonte di cibo dopo di essa tenderanno anche a seguirla. ANCHE SE non si sta spostando di nuovo verso la colonia. Ciò sconfigge lo scopo dell'intero algoritmo.

Quindi le mie domande sono

  • La preoccupazione sopra riportata è valida? Se no, allora perché? Se sì, allora come affrontarlo?
  • Abbiamo bisogno di apportare alcune modifiche alla nostra comprensione di base dell'algoritmo per farlo funzionare davvero?
  • Quali sono alcune altre cose sottili ma importanti che i neofiti come me potrebbero perdere in questo caso?
posta transistor 13.04.2015 - 20:16
fonte

2 risposte

6

Questo non è il modo in cui funziona ACO. ACO rilascia solo feromoni dopo che le formiche si sono mosse attraverso tutti i punti della griglia. Quindi valuti qualcosa (forse il tempo di viaggio totale) e poi fai cadere i feromoni per le buone formiche e ripeti.

Non si spostano due volte sullo stesso vertice, generalmente, sebbene sia possibile personalizzarlo per specificità di implementazione.

I feromoni non vengono rilasciati ogni mossa, cadono dopo che si muovono ovunque e qualcosa viene valutato per determinare quali formiche sono migliori. Le formiche che sono meglio quindi rilasciano i phereomones (forse il migliore 25% che esegue formiche).

    
risposta data 13.04.2015 - 20:49
fonte
1

Le implementazioni che ho visto dagli altri, e quelle che ho scritto per me stesso, hanno sempre avuto le formiche rilasciare i feromoni lungo il percorso che hanno viaggiato per arrivare al cibo, una volta che hanno raggiunto il cibo. Cioè, le formiche marciano dalla loro colonia al cibo seguendo una passeggiata casuale; i percorsi seguiti dalle formiche dalla colonia al cibo vengono quindi marcati usando i feromoni solo dopo le formiche hanno avuto successo nel raggiungere il cibo. Il viaggio di ritorno non è simulato esplicitamente. In generale, le formiche multiple fanno il loro corso prima che i feromoni vengano depositati per l'iterazione corrente. I feromoni vengono quindi distribuiti per i percorsi riusciti e inizia un nuovo round.

Di solito, le probabilità della formica di entrare in un dato nodo sono ponderate in base alla quantità di feromoni volte a qualche misura di "bontà". Ad esempio, la misura della bontà potrebbe essere qualcosa di simile all'inverso della distanza tra la formica e il cibo - questo manterrà le formiche che cercano di muoversi verso il cibo, indipendentemente dai precedenti depositi di feromoni. La bontà potrebbe essere ulteriormente ponderata per tenere conto di altri fattori, ad es. alcuni nodi potrebbero essere più facili da percorrere rispetto ad altri. E come sottolinea enderland, in genere c'è una qualche forma di "selezione" del percorso quando tutte delle formiche hanno eseguito con successo i loro corsi, dove solo una parte dei percorsi "migliori" vengono scelti per il deposito di feromoni. Tuttavia, dovresti comunque ottenere percorsi ragionevoli anche senza selezione, purché la tua scelta di "bontà" abbia senso.

    
risposta data 13.04.2015 - 22:27
fonte

Leggi altre domande sui tag

Qual è il modo migliore per eseguire il failover offline di un client basato sul desktop che utilizza un servizio Web? Come possiamo migliorare l'istruzione e la formazione del programmatore in generale? [chiuso]