Algoritmo delle colonie di formiche: differenze tra le versioni

Versione delle 10:03, 24 mag 2021

Versione delle 10:23, 24 mag 2021

Riga 26:

Le formiche usano l'ambiente come mezzo di [[comunicazione]]: si scambiano informazioni indirettamente depositando feromone, in modo da descrivere lo stato del loro "lavoro". Le informazioni vengono scambiate in ambito locale, infatti una formica ha accesso al feromone solo se si trova nel luogo dove questo è stato depositato. Questo sistema è chiamato "[[stigmergia]]" e si verifica in vari animali sociali (in particolare è stato studiato nel caso della costruzione di pilastri nei nidi di [[Isoptera|termiti]]).

Il meccanismo che permette di risolvere un problema troppo complesso per essere affrontato da singole formiche è un buon esempio di sistema [[Auto-organizzazione|auto-organizzato]]. Questo sistema si basa su [[retroazione|retroazioni]] positive (la deposizione di feromone attira altre formiche che rafforzeranno il percorso) e negative (la dissipazione del percorso a causa dell'evaporazione impedisce al sistema di bloccarsi). In teoria, se la quantità di feromone rimane la stessa nel corso del tempo su tutti i percorsi, non ne verrà scelto alcuno. Tuttavia, a causa della retroazione, una piccola variazione su un percorso sarà amplificato e quindi consente la scelta di un percorso. L'algoritmo consente di passare da uno stato instabile dove nessun percorso è migliore di un altro, ada uno stato stabile in cui il percorso viene realizzato da tratti "migliori".

==Esempio: l<nowiki>'</nowiki>''Ant system''==

Riga 35:

L'algoritmo generale è relativamente semplice ed è basato su un insieme di formiche, ciascuna delle quali attraversa un percorso tra quelli possibili. In ogni fase, la formica sceglie di spostarsi da una città all'altra secondo alcune regole:

# più una città è distante, meno possibilità ha di essere scelta (la ''"visibilità"'');

# più l'intensità del percorso di feromone situato sul crinale tra due città è maggiore, più ha possibilità di essere scelto;

# una volta completato il suo percorso, la formica deposita, su tutti i bordi attraversati, più feromone se il percorso è breve;

Riga 41:

===Descrizione formale===

La regola di spostamento, chiamata ''"regola casuale di transizione proporzionale"'' è matematicamente scritta come segue:

:<math>p_{ij}^{k}\left(t\right)=\left\{ \begin{matrixcases}

<math>

\displaystyle\frac{\tau_{ij}\left(t\right)^{\alpha}\cdot\eta_{ij}^{\beta}}{{\scriptscriptstyle displaystyle\sum_{l\in J_{i}^{k}}}\tau_{il}\left(t\right)^{\alpha}\cdot\eta_{il}^{\beta}}, & \textrmtext{con }\, j\in J_{i}^{k}, \\

p_{ij}^{k}\left(t\right)=\left\{ \begin{matrix}

0, & \textrmtext{con }\, j\notin J_{i}^{k},\end{matrixcases}\right.</math>

\frac{\tau_{ij}\left(t\right)^{\alpha}\cdot\eta_{ij}^{\beta}}{{\scriptscriptstyle \sum_{l\in J_{i}^{k}}}\tau_{il}\left(t\right)^{\alpha}\cdot\eta_{il}^{\beta}} & \textrm{con}\, j\in J_{i}^{k}\\

0 & \textrm{con}\, j\notin J_{i}^{k}\end{matrix}\right.

</math>

dove ''J<submath>J_{i</sub><sup>}^{k}</supmath>'' è l'elenco dei possibili spostamenti di una formica ''<math>k''</math> quando si trova in una città ''<math>i'',</math> ''η<submath>\eta_{ij}</submath>'' la visibilità, che è uguale all'inverso della distanza <math>d_{ij}</math> tra due città ''<math>i''</math> e ''j'' (''1/d<submath>ijj</submath>'') e ''τ<submath>\tau_{ij}(t)</submath> (t)'' l'intensità della pista ad una data iterazione ''<math>t''.</math> I due parametri principali che controllano l'algoritmo sono ''α''<math>\alpha</math> e ''β''<math>\beta,</math> che controllano l'importanza relativa della intensità e la visibilità di un bordo.

Una volta fatto il giro delle città, una formica <math>k</math> deposita una quantità <math>\Delta\tau^k_{ij}</math> di feromone su ogni bordo del suo percorso:

:<math>\Delta\tau_{ij}^{k}(t)=\begin{cases}

<math>

\Deltadisplaystyle\tau_frac{ijQ}{L^{k}(t)=\left}, & \text{con }(i,j)\beginin T^{matrixk}(t), \\

\frac{Q}{L^{k}(t)}0, & \textrmtext{con }\,(i,j)\innotin T^{k}(t),\\end{cases}</math>

0 & \textrm{con}\,(i,j)\notin T^{k}(t)\end{matrix}\right.

</math>

dove ''T<supmath>T^{k}(t)</supmath> (t)'' è il giro fatto dalla formica ''<math>k''</math> all'iterazione ''<math>t'',</math> ''L<supmath>L^{k}(t)</supmath> (t)'' la lunghezza del percorso e ''<math>Q''</math> un parametro di regolazione.

Alla fine di ogni iterazione dell'algoritmo, il feromone depositato nelle precedenti iterazioni delle formiche evaporano:

:<math> \rho \tau_{ij}(t).</math>

E alla fine dell'iterazione, si ha la quantità di feromone che non è evaporato e di quello che verrà depositato:

:<math>\tau_{ij}(t+1)=(1-\rho) \tau_{ij}(t) + \sum_{k=1}^{m}\Delta\tau_{ij}^{k}(t),</math>

<math>

\tau_{ij}(t+1)=(1-\rho) \tau_{ij}(t) + \sum_{k=1}^{m}\Delta\tau_{ij}^{k}(t)

</math>

dove ''<math>m''</math> è il numero di formiche utilizzate per l'iterazione ''<math>t''</math> e ''ρ''<math>\rho</math> un parametro di regolazione.

==Varianti principali==

Riga 77 ⟶ 71:

=== Il contesto dell<nowiki>'</nowiki>''ACO''===

Parte degli algoritmi (compresi quelli progettati da M. Dorigo ede i suoi colleghi) sono ora raggruppati sotto il termine "Ant Colony Optimization" (ACO). Questo quadro si limita ad algoritmi che costruiscono delle soluzioni sotto forma di parametri associati ai componenti di un grafo, utilizzando un modello statistico di parte.

Un metodo di tipo ACO segue lo schema algoritmico seguente, impostato da: