b'\n_START_ARTICLE_\nAlgoritmo delle colonie di formiche\n_START_PARAGRAPH_\nGli algoritmi delle colonie di formiche sono degli algoritmi ispirati dal comportamento delle formiche, o da altre specie che formano un superorganismo, che sono una parte dell\'ottimizzazione metaeuristica._NEWLINE_Inizialmente proposto da Marco Dorigo et al., nel 1990, per la ricerca dei percorsi ottimali in un grafo, il primo algoritmo si basa sul comportamento delle formiche che cercano un percorso tra la loro colonia e una fonte di cibo. L\'idea originale da allora si \xc3\xa8 diversificata per risolvere una classe pi\xc3\xb9 ampia di problemi, facendo quindi emergere diversi algoritmi attingendo da vari aspetti del comportamento delle formiche._NEWLINE_In inglese, il termine dedicato all\'algoritmo principale \xc3\xa8 Ant Colony Optimisation (ACO). Gli specialisti riservano tale termine per un particolare tipo di algoritmo. Tuttavia, ci sono diverse famiglie di metodi basate sul comportamento delle formiche. In italiano, questi approcci sono raggruppati secondo i termini: algoritmi delle colonie di formiche, ottimizzazione delle colonie di formiche, formiche artificiali o diverse combinazioni di queste varianti.\n_START_SECTION_\nDescrizione formale\n_START_PARAGRAPH_\nLa regola di spostamento, chiamata "regola casuale di transizione proporzionale" \xc3\xa8 matematicamente scritta come segue:_NEWLINE_dove J\xe1\xb5\xa2\xe1\xb5\x8f \xc3\xa8 l\'elenco dei possibili spostamenti di una formica k quando si trova in una citt\xc3\xa0 i, \xce\xb7\xe1\xb5\xa2\xe2\xb1\xbc la visibilit\xc3\xa0, che \xc3\xa8 uguale all\'inverso della distanza tra due citt\xc3\xa0 i e j (1/d\xe1\xb5\xa2\xe2\xb1\xbc) e \xcf\x84\xe1\xb5\xa2\xe2\xb1\xbc (t) l\'intensit\xc3\xa0 della pista ad una data iterazione t. I due parametri principali che controllano l\'algoritmo sono \xce\xb1 e \xce\xb2, che controllano l\'importanza relativa della intensit\xc3\xa0 e la visibilit\xc3\xa0 di un bordo._NEWLINE_Una volta fatto il giro delle citt\xc3\xa0, una formica k deposita una quantit\xc3\xa0  di feromone su ogni bordo del suo percorso:_NEWLINE_dove T\xe1\xb5\x8f (t) \xc3\xa8 il giro fatto dalla formica k all\'iterazione t, L\xe1\xb5\x8f (t) la lunghezza del percorso e Q un parametro di regolazione._NEWLINE_Alla fine di ogni iterazione dell\'algoritmo, il feromone depositato nelle precedenti iterazioni delle formiche evaporano:_NEWLINE_E alla fine dell\'iterazione, si ha la quantit\xc3\xa0 di feromone che non \xc3\xa8 evaporato e di quello che verr\xc3\xa0 depositato:_NEWLINE_dove m \xc3\xa8 il numero di formiche utilizzate per l\'iterazione t e \xcf\x81 un parametro di regolazione.\n_START_SECTION_\nVarianti principali\n_START_PARAGRAPH_\nL\'algoritmo delle colonie di formiche \xc3\xa8 stato originariamente utilizzato principalmente per produrre soluzioni quasi ottimali per il problema del commesso viaggiatore e, pi\xc3\xb9 in generale, per i problemi di ottimizzazione combinatoria.\n_START_SECTION_\nUna definizione difficile\n_START_PARAGRAPH_\nNon \xc3\xa8 facile dare una definizione precisa di ci\xc3\xb2 che \xc3\xa8 o ci\xc3\xb2 che non \xc3\xa8 un algoritmo delle colonie di formiche, perch\xc3\xa9 la definizione pu\xc3\xb2 variare a seconda degli autori e degli usi._NEWLINE_In modo molto generale, gli algoritmi delle colonie di formiche sono considerati come delle metaeuristiche di popolazione, dove ogni soluzione \xc3\xa8 rappresentata da un movimento della formica sullo spazio di ricerca. Le formiche segnano le migliori soluzioni, e tengono conto delle marcature precedenti per ottimizzare la loro ricerca._NEWLINE_Essi possono essere considerati come algoritmi probabilistici multi-agente che utilizzano una distribuzione di probabilit\xc3\xa0 implicita per la transizione tra ogni iterazione. Nelle loro versioni per problemi combinatori, usano una costruzione iterativa di soluzioni._NEWLINE_Secondo alcuni autori, la differenza fra gli algoritmi delle colonie di formiche ed altri processi metaeuristici simili (come gli algoritmi di stima della distribuzione o di ottimizzazione degli sciami di particelle) \xc3\xa8 proprio il suo aspetto costruttivo. Infatti, nei problemi combinatori, \xc3\xa8 possibile che alla fine sar\xc3\xa0 trovata la soluzione migliore, anche se nessuna formica l\'avr\xc3\xa0 utilizzata in modo efficiente. Cos\xc3\xac, nell\'esempio del problema del commesso viaggiatore, non \xc3\xa8 necessario che una formica effettivamente faccia il percorso pi\xc3\xb9 breve: pu\xc3\xb2 essere costruito da segmenti rinforzati delle soluzioni migliori. Tuttavia, questa definizione pu\xc3\xb2 essere problematica nel caso di variabili reali a problemi in cui nessuna struttura esiste nella zona._NEWLINE_Il comportamento collettivo degli insetti sociali rimane una fonte di ispirazione per i ricercatori. L\'ampia variet\xc3\xa0 di algoritmi (per l\'ottimizzazione e non) che sostengono l\'auto-organizzazione nei sistemi biologici ha dato origine al concetto di "swarm intelligence", che \xc3\xa8 un quadro molto generale, al cui interno vi sono anche gli algoritmi delle colonie di formiche.\n_START_SECTION_\nApplicazioni\n_START_PARAGRAPH_\nLe varianti combinatorie possono avere un vantaggio rispetto ad altre metaeuristiche, nel caso in cui il grafico studiato pu\xc3\xb2 cambiare in modo dinamico durante l\'esecuzione: la colonia di formiche si adatter\xc3\xa0 in modo relativamente flessibile al cambiamento. Questo \xc3\xa8 interessante per l\'instradamento di reti._NEWLINE_Gli algoritmi delle colonie di formiche sono stati applicati a molti problemi di ottimizzazione combinatoria, dalla replicazione delle proteine allo smistamento dei veicoli. Come molte metaeuristiche, l\'algoritmo di base \xc3\xa8 stato adattato ai problemi dinamici in variabili reali, problemi stocastici, multi-obiettivi o ad implementazioni parallele, etc.'