miniatura|Certs comportaments de les formigues són l'origen d'algorismes d'optimització (aquí, el de les formigues legionàries del gènere Dorylus). Els algorismes de les colònies de formigues són algorismes inspirats en el comportament de les formigues i que constitueixen una família de metaheurístiques d'optimització. Va ser proposat per primera vegada per Marco Dorigo i altres en els anys 90.A. Colorni, M. Dorigo i V. Maniezzo. Distributed Optimization by Ant Colonies, actes de la primera conferència europea sobre la vida artificial, París, França, Elsevier Publishing, 134-142, 1991.M. Dorigo. Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Itàlia, 1992. Per a la investigació de camins òptims en un graf, el primer algorisme s'inspira en el comportament de les formigues que cerquen un camí entre la seva colònia i una font d'aliment. La idea original es diversifica després per resoldre una classe més àmplia de problemes, i apareixen diversos algorismes que s'inspiren en diversos aspectes del comportament de les formigues.
En anglès, el terme consagrat a la principal classe d'algorismes és «Ant Colony Optimization» (acrònim ACO). Els especialistes reserven aquest terme per un tipus particular d'algorisme. Existeixen tanmateix diversos grups de mètodes que s'inspiren en el comportament de les formigues. En francès, aquests diferents enfocaments s'agrupen sota els termes «algorithmes de colonies de fourmis» (algorismes de colònies de formigues), «optimisation par colonies de fourmis» (optimització per colònies de formigues), «fourmis artificielles» (formigues artificials) o diverses combinacions d'aquestes variants.
Origen miniatura|1) La primera formiga troba la font d'aliments (F), a través d'un camí qualsevol (a), i després torna al niu (N), deixant darrere d'ella una pista de feromones (b). 2) Les formigues emprenen indiferentment els quatre camins possibles, però el reforç de la pista fa més atractiu el camí més curt. 3) Les formigues prenen el camí més curt i les porcions llargues dels altres camins perden la seva pista de feromones. La idea original prové de l'observació de l'explotació dels recursos alimentaris per part de les formigues. En efecte, aquestes, encara que individualment tenen capacitats cognoscitives limitades, són capaces de trobar de manera col·lectiva el camí més curt entre una font d'aliments i el seu niu.
En una sèrie d'experiències dutes a terme a partir del 1989,S. Goss, S. Aron, J.-L. Deneubourg i J.-M. Pasteels. "The self-organized exploratory pattern of the Argentina ant", Naturwissenschaften, volum 76, pàg. 579-581, 1989J.-L. Deneubourg, S. Aron, S. Goss i J.-M. Pasteels. "The self-organizing exploratory pattern of the Argentina ant", Journal of Insect Behavior, volum 3, pàg. 159, 1990 alguns biòlegs han observat que una colònia de formigues en la que els individus han de triar entre dos camins, de longitud desigual, que porten a una font d'aliment determinada, tendeixen a fer servir el camí més curt. Un model que explica aquest comportament és el següent: Una formiga (anomenada «exploradora») recorre més o menys a l'atzar el medi al voltant de la colònia; Si aquesta descobreix una font d'aliments, entra al niu de manera més o menys directa, deixant sobre el seu camí una pista de feromones; Com que aquestes feromones són atractives, les formigues que passen prop tindran tendència a seguir, de manera més o menys directa, aquesta pista; En tornar al niu, aquestes mateixes formigues van reforçant la pista de feromones; Si hi ha dos camins possibles per arribar a la mateixa font d'aliments, el més curt serà recorregut per més formigues que el més llarg, considerant la mateixa durada; El camí curt tindrà, per tant, cada vegada un reforç més important i també serà cada cop més atractiu; La pista de feromones del camí llarg acabarà desapareixent, ja que les feromones són volàtils; Per tant, al final, el conjunt de les formigues determinen i «escullen» el camí més curt.
Les formigues fan servir l'entorn com a suport de comunicació: intercanvien indirectament informació dipositant feromones tot descrivint l'estat del seu «treball». La informació intercanviada té un abast local: només una formiga situada a l'indret on les feromones han estat dipositades hi té accés. Aquest sistema té el nom d'«estigmèrgia», i es pot trobar en altres insectes socials; per exemple, s'ha estudiat bé la construcció de monticles als nius dels tèrmits.
Un mecanisme que permeti resoldre un problema massa complex per a ser abordat només per formigues és un bon exemple d'un sistema autoorganitzat. Aquest sistema descansa sobre retroaccions positives (el dipòsit de feromona atreu altres formigues que la reforçaran) i negatives (la dissipació de la pista per evaporació impedeix el sistema d'embalar-se). Teòricament, si la quantitat de feromona en totes les rutes continués sent idèntica, no se n'escolliria cap. Ara bé, a conseqüència de les retroaccions, una feble variació sobre una ruta anirà sent ampliada i, llavors, permetrà la tria d'una ruta en concret. L'algorisme permetrà passar d'un estat inestable on cap ruta no té més senyals que una altra, cap a un estat estable on l'itinerari quedarà configurat per les «millors» rutes.
Exemple: el «sistema formiga» miniatura|L'algorisme «Ant System» que optimitza el problema del viatjant de comerç: 1) Una formiga escull un trajecte, i traça una pista de feromona. 2) El conjunt de les formigues recorre un cert nombre de trajectes, i cada formiga diposita una quantitat de feromona proporcional a la qualitat del recorregut (com més curt més gran). 3) Cada aresta del millor camí és més reforçada que les altres. 4) L'evaporació fa desaparèixer les males solucions. El primer algorisme de colònies de formigues proposat s'anomena Ant system (sistema formiga).M. Dorigo, V. Maniezzo, A. Colorni. "Ant system: optimization by a colony of cooperating agents", IEEE Transactions on Systems, Man, and Cybernetics. Part B, volum 26, núm. 1, pàg. 29-41, 1996. Apunta sobretot a resoldre el problema del viatjant de comerç, on l'objectiu és trobar el camí més curt que permeti enllaçar un conjunt de ciutats.
Descripció general L'algorisme general és relativament senzill, i descansa sobre un conjunt de formigues en el qual cadascuna recorre un trajecte entre tots els possibles. A cada etapa, la formiga escull passar d'una ciutat a una altra en funció d'algunes regles: No pot visitar més que una vegada cada ciutat; Com més lluny és una ciutat, menys probabilitat té de ser escollida (és la «visibilitat»); Com més gran és la intensitat de la pista de feromones dipositada sobre l'aresta del graf que uneix dues ciutats, més gran és la probabilitat d'escollir-la; Una vegada el recorregut el seu trajecte, la formiga diposita, sobre el conjunt de les arestes recorregudes, més feromones com més curt sigui el trajecte; Les pistes de feromones s'evaporen a cada iteració.
Descripció formal La regla de desplaçament s'anomena «regla aleatòria de transició proporcional», i s'escriu matemàticament de la forma següent:
A la fórmula, Jik és la llista dels desplaçaments possibles per una formiga k quan es troba sobre una ciutat i; ηij representa la visibilitat, que és igual a l'invers de la distància de dues ciutats i i j (1/dij); τij (t) és la intensitat de la pista en una iteració donada t. Els dos principals paràmetres que controlen l'algorisme són α i β, i ho fan controlant la importància relativa de la intensitat i la visibilitat d'una aresta.
Una vegada efectuada la volta per les ciutats, cada formiga k diposita una quantitat de feromones sobre cada aresta del seu recorregut:
Aquí, Tk (t) és la volta feta per la formiga k en la iteració t; Lk (t) és la longitud del trajecte i Q és un paràmetre d'ajust.
Al final de cada iteració de l'algorisme, les feromones dipositades a les iteracions precedents per les formigues s'evaporen en:
També, en finalitzar la iteració s'obté la suma de les feromones que no s'han evaporat i de les que s'acaben de dipositar. A la fórmula, m és el nombre de formigues utilitzades per a la iteració t, i ρ un paràmetre d'ajust:
Principals variants L'algorisme de la colònia de formigues s'ha fet servir, sobretot a l'inici, per produir solucions quasi-òptimes del problema del viatjant de comerç. Posteriorment, d'una forma més general, s'ha aplicat en determinats problemes d'optimització combinatòria. S'observa que, des dels seus començaments, el seu ús s'ha estès en diversos àmbits, des de l'optimització contínua fins a la classificació o també en el tractament digital d'imatges.
El marc «ACO» Una part dels algorismes (sobretot els dissenyats pel M. Dorigo i els seus col·legues) s'ha agrupat amb la denominació «Ant Colony Optimization» (ACO). Tanmateix, aquesta categoria es limita als algorismes que construeixen solucions sota la forma de paràmetres associats als components d'un graf amb l'ajuda d'un model estadístic esbiaixat. Un mètode de tipus ACO segueix l'algorisme seguint: Inicialització de les pistes de feromona. Acció mentre no es compleixi el criteri d'aturada. construcció de les solucions component per component; aplicació (ús facultatiu) d'una acció heurística; actualització de les pistes de feromones. Fi del bucle.
Una variant eficaç de lAnt System és el Max-Min Ant System (MMAS),T. Stützle i H.H. Hoos, "Màx. Min Ant System", Future Generation Computer Systems, volum 16, pàg. 889-914, 2000 on només les millors formigues tracen pistes i on el dipòsit de feromones queda limitat per un marge superior –que impedeix que una pista sigui massa reforçada–, i un marge inferior –que obre la possibilitat que sigui explorada des de qualsevol solució–. Aquest algorisme obté resultats millors que l'original, i evita sobretot una convergència prematura.
L'altra variant més coneguda és lAnt Colony System (ACS),M. Dorigo i l M. Gambardella. "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem", IEEE Transactions on Evolutionary Computation, volum 1, núm. 1, pàg. 53-66, 1997. on hi ha una nova regla de desplaçament anomenada «regla pseudoaleatòria proporcional», i s'hi afegeix un procés d'actualització «local» dels elements de les pistes de feromones. L'objectiu d'aquest mecanisme és augmentar la diversificació de la recerca.
És possible, per a certes versions, demostrar que l'algorisme és convergent, és a dir, que és capaç de trobar l'òptim global en un temps finit. La primera prova de convergència d'un algorisme de colònies de formigues va ser aportada l'any 2000 amb la proposta de l'algorisme graph-base ant system, i després pels algorismes ja comentats ACS i MMAS. Tot i així, per a la majoria de les metaheurístiques és molt difícil estimar teòricament la velocitat de convergència.
El 2004, Zlochin i els seus col·legues varen mostrarM. Zlochin, M. Birattari, N. Meuleau, i M. Dorigo. "Model-based search fur combinatorial optimization: A critical survey", Annals of Operations Research, volum 131, pàg. 373-395, 2004. que els algorismes de tipus ACO podien ser assimilats amb els mètodes de descens estocàstic de gradient, d'entropia creuada i els algorismes d'estimació de distribució. S'ha proposat d'agrupar aquests mètodes metaheurístics sota el terme de «recerca a base d'un model».
Una definició difícil miniatura|Amb un algorisme de colònies de formigues el camí més curt entre dos punts A i B es construeix a partir de la combinació de diversos camins. No és fàcil donar una definició precisa de què és o què no és un algorisme de colònies de formigues, ja que la definició pot variar segons els autors i els usos. D'una manera molt general, els algorismes de colònies de formigues són considerats com a metaheurístiques de la població, on cada solució es representa amb una formiga desplaçant-se sobre l'espai de cerca. Les formigues marquen les millors solucions i tenen en compte els marcatges precedents per optimitzar la seva cerca.