Algorisme de la colònia de formigues

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. 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

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, 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:

1. Una formiga (anomenada «exploradora») recorre més o menys a l'atzar el medi al voltant de la colònia;
2. 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;
3. 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;
4. En tornar al niu, aquestes mateixes formigues van reforçant la pista de feromones;
5. 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;
6. El camí curt tindrà, per tant, cada vegada un reforç més important i també serà cada cop més atractiu;
7. La pista de feromones del camí llarg acabarà desapareixent, ja que les feromones són volàtils;
8. 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»

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). 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:

1. No pot visitar més que una vegada cada ciutat;
2. Com més lluny és una ciutat, menys probabilitat té de ser escollida (és la «visibilitat»);
3. 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;
4. 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;
5. 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:

$p_{ij}^{k}\left(t\right)=\left\{{\begin{matrix}{\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 {si}}\,j\in J_{i}^{k}\\0&{\textrm {si}}\,j\notin J_{i}^{k}\end{matrix}}\right.$

A la fórmula, J_i^k é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/d_ij); τ_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 $\Delta \tau _{ij}^{k}$ de feromones sobre cada aresta del seu recorregut:

$\Delta \tau _{ij}^{k}(t)=\left\{{\begin{matrix}{\frac {Q}{L^{k}(t)}}&{\textrm {si}}\,(i,j)\in T^{k}(t)\\0&{\textrm {si}}\,(i,j)\notin T^{k}(t)\end{matrix}}\right.$

Aquí, T^k (t) és la volta feta per la formiga k en la iteració t; L^k (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: $\rho \tau _{ij}(t)\;$

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:

$\tau _{ij}(t+1)=(1-\rho )\tau _{ij}(t)+\sum _{k=1}^{m}\Delta \tau _{ij}^{k}(t)$

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 l'Ant System és el Max-Min Ant System (MMAS), 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 l'Ant Colony System (ACS), 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 mostrar 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

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.

Se'ls pot considerar com algorismes multiagents probabilístics, utilitzant una distribució de probabilitat implícita per efectuar la transició entre cada iteració. En les seves versions adaptades a problemes combinatoris fan servir una construcció iterativa de les solucions.

Segons certs autors, el que diferenciaria els algorismes de colònies de formigues d'altres metaheurístiques properes –com, per exemple, els algorismes a estimació de distribució o l'optimització per eixam particular– seria justament el seu aspecte constructiu. En efecte, en els problemes combinatoris, és possible que s'acabi trobant la millor solució fins i tot en el cas que cap formiga l'hagi realitzat amb èxit. Així, en l'exemple del problema del viatjant de comerç, no és necessari que una formiga recorri efectivament el camí més curt: aquest pot ser construït a partir dels segments més reforçats de les millors solucions. Tanmateix, aquesta definició pot plantejar problemes en el cas dels problemes amb variables reals, on no existeix cap estructura de veïnatge.

El comportament col·lectiu dels insectes socials continua sent una font d'inspiració per als investigadors. La gran diversitat d'algorismes –sigui o no per a l'optimització–, que apel·len a l'autoorganització en els sistemes biològics ha donat lloc al concepte d'«intel·ligència en eixam», que és un marc molt general en el qual s'inscriuen els algorismes de colònies de formigues.

Algorismes estigmèrgics

En la pràctica, s'observa que un gran nombre d'algorismes requereixen una inspiració basada en les «colònies de formigues» tot i que no sempre necessiten compartir el marc general de l'optimització de les colònies de formigues canònica (ACO). En la pràctica, la utilització d'un intercanvi d'informacions entre formigues per mitjà de l'entorn natural, un principi que s'anomena estigmèrgia, és suficient per a ser classificat dins la categoria dels algorismes de la colònia de formigues. Aquest principi ha impulsat certs autors a crear el terme «optimització estigmèrgica». D'aquesta manera, existeixen mètodes inspirats en comportaments que es basen en la cerca d'aliments, en la tria de larves, en la divisió del treball o en el transport cooperatiu.

Aplicacions

Problema de la motxilla. Un nombre limitat de formigues privilegien la gota de mel per davant de les que prefereixen l'aigua ensucrada, més abundant però menys nutritiva. Les gotes de mel es troben en menor quantitat però tenen més interès nutritiu.

Les variants combinatòries poden tenir un avantatge respecte a altres mètodes metaheurístics. En el cas del gràfic estudiat, pot arribar a canviar d'una manera dinàmica en el transcurs de l'execució i la colònia de formigues s'adaptarà de manera relativament flexible als canvis. Segons alguns investigadors d'aquest algorisme, la seva aplicació sembla que podria ser interessant per a l'encaminament de xarxes informàtiques.

Els algorismes de les colònies de formigues, com ja s'ha comentat, s'han aplicat a un gran nombre de problemes d'optimització combinatòria, que van des de l'assignació quadràtica fins als plecs d'una proteïna. Com molts sistemes metaheurístics, l'algorisme de base ha estat adaptat en problemes dinàmics, en variables reals, en problemes estocàstics, en multiobjectius o en implementacions paral·leles, per citar algunes aplicacions. Que el gràfic pugui canviar de forma dinàmica és un avantatge sobre l'algorisme anomenat simulated annealing (recuit simulat) i els enfocaments d'algorismes genètics aplicats a problemes similars.

L'algorisme de la colònia de formigues pot funcionar de manera contínua i adaptar-se als canvis en temps real. Això té interès en les rutes de les xarxes de comunicacions i altres sistemes del transport urbà. Com un molt bon exemple, els algorismes de les colònies de formigues (ACO) s'han utilitzat per trobar solucions òptimes per al problema del viatjant de comerç. El primer algorisme ACO va ser anomenat ant system (sistema formiga) i va ser destinat a resoldre el problema del viatjant ambulant, en el que l'objectiu és trobar el camí més curt d'anada i tornada per un element que pretengui connectar una sèrie de ciutats. L'algorisme general és relativament simple i es basa en un grup de formigues que poden decidir entre possibles opcions d'anada i tornada entre diversos punts o ciutats.

Història

Cronologia dels algorismes de colònies de formigues.

• 1959, Pierre-Paul Grassé inventa la teoria de l'estigmèrgia per explicar el comportament de construcció dels nius en els tèrmits.
• 1983, Deneubourg i els seus col·legues estudien el comportament col·lectiu de les formigues.
• 1988, Moyson i Manderick presenten un article sobre l'autoorganització en les formigues.
• 1989, treballs de Goss, Aron, Deneubourg i Pasteels, sobre els comportaments col·lectius de les formigues Argentines, que donaran la idea dels algorismes de les colònies de formigues.
• 1989, implementació d'un model de comportament de cerca d'aliments per Ebling i els seus col·legues.
• 1991, M. Dorigo proposa l'Ant System a la seva tesi doctoral (que no serà publicada fins al 1992). Presenta amb V. Maniezzo i A. Colorni un informe tècnic, que serà publicat cinc anys més tard.
• 1995, Bilchev i Parmee publiquen la primera temptativa d'adaptació als problemes continus.
• 1996, publicació de l'article sobre l'Ant System.
• 1996, Stützle i Hoos inventen el Max-Min Ant Sytem.
• 1997, Dorigo i Gambardella publiquen l'Ant Colony System.
• 1997, Schoonderwoerd i col·laboradors dissenyen la primera aplicació en xarxes de telecomunicacions.
• 1997, Martinoli i col·laboradors s'inspiren en els algorismes de colònies de formigues per al control de robots.
• 1998, Dorigo fa la primera conferència dedicada als algorismes de les colònies de formigues.
• 1998, Stützle proposa les primeres implementacions paral·leles.
• 1999, Bonabeau i col·laboradors presenten un llibre que tracta principalment sobre formigues artificials;
• 1999, primeres aplicacions en rutes de vehicles, en l'assignació quadràtica i en l'algorisme de la motxilla multidimensional.
• 2000, número especial d'una revista científica sobre els algorismes de les colònies de formigues;
• 2000, primeres aplicacions dins la programació d'operacions, la programació seqüencial i la satisfacció de restriccions.
• 2000, Gutjahr publica la primera demostració de convergència per a un algorisme de colònies de formigues.
• 2001, primera utilització dels algorismes de colònies de formigues per a empreses (Eurobios i AntOptima);
• 2001, Iredi i els seus col·legues publiquen el primer algorisme multiobjectiu.
• 2002, primeres aplicacions a la planificació de les xarxes bayesianes.
• 2002, Bianchi i els seus col·legues proposen el primer algorisme per a problemes estocàstics.
• 2004, Zlochin i Dorigo mostren que certs algorismes són equivalents al descens estocàstic de gradient, l'entropia creuada i els algorismes d'estimació de distribució.
• 2005, primeres aplicacions en el plegament proteic.

Bibliografia

• É. Bonabeau, M. Dorigo i G. Theraulaz. Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, 1999. ISBN 0195131592.
• J.L. Denebourg, J.M. Pasteels i J.C. Verhaeghe. "Probabilistic Behaviour in Ants: a Strategy of Errors?", Journal of Theoretical Biology, núm. 105, 1983.
• M. Dorigo, M. Birattari i T. Stützle. "Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique", IEEE Computational Intelligence Magazine, volum 1, num. 4, pàg. 28–39, 2006.
• M. Dorigo, V. Maniezzo, i 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.
• M. Dorigo i T. Stützle. Ant Colony Optimization, Cambridge, MA, MIT Press/Bradford Books, 2004. ISBN 0262042193.
• J. Dréo, A. Petrowski, É. Taillard i P. Siarry. Métaheuristiques pour l'optimisation difficile, Eyrolles, Paris, setembre 2003. ISBN 2-212-11368-4.
• W.J. Gutjahr. "A graph-based Ant System and its convergence", Future Generation Computer Systems, volum 16, pàg. 873-888, 2000.
• R. Schoonderwoerd, O. Holland, J. Bruten i L. Rothkrantz. "Ant-based load balancing in telecommunication networks", Adaptive Behaviour, volum 5, núm. 2, pàg. 169-207, 1997
• T. Stützle i H.H. Hoos. "Màx. Min Ant System", Future Generation Computer Systems, volum 16, pàg. 889-914, 2000
• M. 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.

Enllaços externs

• Ant Colony Optimization Home Page, lloc web mantingut per Marco Dorigo, bibliografia, codifiques fonts. (anglès)
• Una introducció als algorismes de colònies de formigues (versió arxivada per Internet Archive) (anglès)
• Una llista de referències bibliogràfiques sobre les formigues artificials Arxivat 2016-03-04 a Wayback Machine. (anglès)
• Ant Colony Algorithm Una simulació en Java de l'ACO, amb terreny modificable. Presentació, informe i codi font descarregables. (anglès)
• Aplicació d'un algorisme de colònia de formigues al problema del viatjant de comerç (francès)