Algorisme de la colònia de formigues

De Viquipèdia
Dreceres ràpides: navegació, cerca
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.[1][2] 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[modifica | modifica el codi]

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 empren 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,[3][4] 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»[modifica | modifica el codi]

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).[5] 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[modifica | modifica el codi]

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[modifica | modifica el codi]

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, 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 \Delta\tau^k_{ij} 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í, 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: 
\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[modifica | modifica el codi]

L'algorisme de la colònia de formigues s'ha fet sevir, 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»[modifica | modifica el codi]

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),[6] 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),[7] 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[8] 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 aquestes mètodes metaheurístics sota el terme de «recerca a base d'un model».

Una definició difícil[modifica | modifica el codi]

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 del què és o el 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[modifica | modifica el codi]

En la pràctica, s'observa que un gran nombre d'algorismes requereixen d'una inspiració basada en les «colònies 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».[9] 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[modifica | modifica el codi]

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'enrutament de xarxes informàtiques.[10]

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 a 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 diverses punts o ciutats.[5]

Història[modifica | modifica el codi]

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.[11]
  • 1983, Deneubourg i els seus col·legues estudien el comportament col·lectiu de les formigues.[12]
  • 1988, Moyson i Manderick presenten un article sobre l'autoorganització en les formigues.[13]
  • 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.[3]
  • 1989, implementació d'un model de comportament de cerca d'aliments per Ebling i els seus col·legues.[14]
  • 1991, M. Dorigo proposa l'Ant System a la seva tesi doctoral (que no serà publicada fins el 1992[2]). Presenta amb V. Maniezzo i A. Colorni un informe tècnic,[15] que serà publicat cinc anys més tard.[5]
  • 1995, Bilchev i Parmee publiquen la primera temptativa d'adaptació als problemes continus.[16]
  • 1996, publicació de l'article sobre l'Ant System.[5]
  • 1996, Stützle i Hoos inventen el Max-Min Ant Sytem.[6]
  • 1997, Dorigo i Gambardella publiquen l'Ant Colony System.[7]
  • 1997, Schoonderwoerd i col·laboradors dissenyen la primera aplicació en xarxes de telecomunicacions.[17]
  • 1997, Martinoli i col·laboradors s'inspiren en els algorismes de colònies de formigues per al control de robots.[18]
  • 1998, Dorigo fa la primera conferència dedicada als algorismes de les colònies de formigues.[19]
  • 1998, Stützle proposa les primeres implementacions paral·leles.[20]
  • 1999, Bonabeau i col·laboradors presenten un llibre que tracta principalment sobre formigues artificials;[21]
  • 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;[22]
  • 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.[23]
  • 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.[24]
  • 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.[25]
  • 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ó.[8]
  • 2005, primeres aplicacions en el plegament proteic.

Notes i referències[modifica | modifica el codi]

  1. 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.
  2. 2,0 2,1 M. Dorigo. Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Itàlia, 1992.
  3. 3,0 3,1 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, 1989
  4. J.-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
  5. 5,0 5,1 5,2 5,3 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úmero 1, pàgines 29-41, 1996.
  6. 6,0 6,1 T. Stützle i H.H. Hoos, "Màx. Min Ant System", Future Generation Computer Systems, volum 16, pàg. 889-914, 2000
  7. 7,0 7,1 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.
  8. 8,0 8,1 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.
  9. A. Ajith; G. Crina; R. Vitorino (editors). Stigmergic Optimization, Studies in Computational Intelligence, volum 31, 299 pàgines, 2006. Isbn 978-3-540-34689-0
  10. K.M. Sim, W.H. Sun. "Ant colony optimization for routing and load-balancing: survey and new direccions", Ieee Transactions hom Systems, Man and Cybernetics, Part A, volum 33, núm. 5, pàg. 560-572, 2003
  11. P.-P. Grassé. "La reconstruction du nid et les coordinations inter-individuelles chez Belicositermes natalensis et Cubitermes sp. La théorie de la Stigmergie: Essai d’interprétation du comportement des termites constructeurs", Insectes Sociaux, núm. 6, pàg. 41-80, 1959.
  12. 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.
  13. F. Moyson, B. Manderick. "The col·lectiva behaviour of Ants: an Example of Self-Organization in Massive Parallelism", Actes d'Aaai Spring Symposium hom Parallel Models of Intel·ligència, Stanford, Californie, 1988.
  14. M. Ebling, M. Di Loreto, M. Presley, F. Wieland, i D. Jefferson. An Ant Foraging Model Implemented on the Time Warp Operating System, Proceedings of the Scs Multiconference hom Distributed Simulation, 1989
  15. Dorigo M.; V. Maniezzo i A. Colorni. Millora feedback as a search strategy, informe tècnic número 91-016, Dip. Elettronica, Politecnico di Milano, Italy, 1991
  16. G. Bilchev i I. C. Parmee. "The Ant Colony Metaphor for Searching Continuous Design Spaces", Proceedings of the Aisb Workshop on Evolutionary Computation. Terence C. Fogarty (editors), Evolutionary Computing Springer-Verlag, pàg. 25-39, abril de 1995.
  17. 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
  18. A. Martinoli, M. Yamamoto i F. Mondada. "On the modelling of bioinspired col·lectiva experiments with real robots", Fourth European Conference on Artificial Life Ecal-97, Brighton (Regne Unit), juliol de 1997.
  19. M. Dorigo. ANTS' 98, From Ant Colonies to Artificial Ants: First International Workshop on Ant Colony Optimization, ANTS 98, Brussel·les, Bèlgica, octubre de 1998.
  20. T. Stützle Parallelization Strategies fur Ant Colony Optimization, Proceedings of Ppsn-V, Fifth International Conference on Parallel Problem Solving from Nature, Springer-Verlag, volum 1498, pàg. 722-731, 1998.
  21. É. Bonabeau, M. Dorigo i G. Theraulaz. Swarm intel·ligència, Oxford University Press, 1999.
  22. M. Dorigo, G. Di Caro i T. Stützle. "Special issue on Ant Algorithms", Future Generation Computer Systems, volum 16, núm. 8, 2000
  23. Watt J. Gutjahr. "A graph-based Ant System and its convergence", Future Generation Computer Systems, volum 16, pàg. 873-888, 2000.
  24. S. Iredi, D. Merkle i M. Middendorf. "Bi-Criterion Optimization with Multi Colony Ant Algorithms", Evolutionary Multi-Criterion Optimization, First International Conference (Emo'01), Zuric, Springer Verlag, pàg. 359-372, 2001.
  25. L. Bianchi, L.M. Gambardella i M. Dorigo. An ant colony optimization approach to the probabilistic traveling salesman problem, Ppsn-Vii, Seventh International Conference hom Parallel Problem Solving from Nature, Lectura Notes in Computer Science, Springer Verlag, Berlín, Alemanya, 2002.

Bibliografia[modifica | modifica el codi]

  • É. 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[modifica | modifica el codi]