Anar al contingut

Algoritme de la colónia de formigues

De L'Enciclopèdia, la wikipedia en valencià
Algoritme de la colónia de formigues
El comportament de les formigues va ser font d'inspiració d'una tècnica d'optimisació basada en metaheurísticas.

En ciències de la computació i en investigació operativa, el algoritme de la colónia de formigues, algoritme formiga o optimisació per colónia de formigues (Ant Colony Optimization, ACO) és una tècnica provabilística per a solucionar problemes computacionals que poden reduir-se a buscar els millors camins o rutes en grafos.

Este algoritme és un membre de la família dels algoritmes de colónia de formigues, dins dels métodos d'inteligència d'eixams. Inicialment propost per Marco Dorigo en 1992 en la seua tesis de doctorat,[1][2] el primer algoritme va sorgir com a método per a buscar el camí òptim en un grafo, basat en el comportament de les formigues quan estes estan buscant un camí entre la colónia i una font d'aliments. L'idea original s'ha diversificado per a resoldre una àmplia classe de problemes numèrics, i com a resultat, han sorgit gran cantitat de problemes nous, basant-se en diversos aspectes del comportament de les formigues.

Descripció general

Resum

En el nostre món natural, les formigues (inicialment) vaguen de manera aleatòria, a l'encert, i una volta trobada menjar retornen a la seua colónia deixant un rastre de feromones. Si atres formigues troben dit rastre, és provable que estes no seguixquen caminant aleatoriamente, pot ser que estes seguixquen el rastre de feromones, retornant i reforçant-ho si estes troben menjar finalment.[3]

No obstant, al pas del temps el rastre de feromones comença a evaporar-se, reduint-se aixina la seua força d'atracció. Quant més temps li prenga a una formiga viajar pel camí i retornar de regrés una atra volta, més temps tenen les feromones per a evaporar-se. Un camí curt, en comparació, és marchat més freqüentment, i per lo tant la densitat de feromones es fa més gran en camins curts que en els llarcs. L'evaporament de feromones també té la ventaja d'evitar convergència a òptims locals. Si no hi haguera evaporament en absolut, els camins elegits per la primera formiga tendirien a ser excessivament atractius per a les següents formigues. En este cas, l'espai de busca de solucions seria llimitat.

Per tant, quan una formiga troba un bon camí entre la colónia i la font de menjar, hi ha més possibilitats de que atres formigues seguixquen este camí i en una retroalimentació positiva es conduïx finalment a totes les formigues a un sol camí. L'idea de l'algoritme colónia de formigues és imitar este comportament en "formigues simulades" caminant a través d'un grafo que representa el problema en qüestió.

Detallat

L'idea original prové de l'observació de l'explotació dels recursos alimentaris entre formigues, en el que les habilitats cognitives de les formigues són individualment llimitades i en conjunt són capaços de buscar el menor camí existent entre la font de menjar i el seu niu o colónia.

  1. La primera formiga troba la font d'aliments (F) a través de qualsevol camí (a), llavors retorna a la colónia (N), deixant despuix de sí un rastre de feromones;
  2. Les formigues indiscriminadament seguixen quatre camins possibles, pero l'enfortiment de la pista fa més atractiu la ruta més curta;
  3. Les formigues prenen la ruta més curta i llargues porcions d'atres rutes escomencen a perdre el seu rastre de feromones.

En una série d'experiments en una colónia de formigues a on existix l'elecció de dos rutes de distàncies diferents que duen fins a la font de menjar, els biòlecs varen observar que les formigues tendixen a usar la ruta més curta.[4] [5] El següent model explica este comportament:

  1. Una formiga (cridada “blitz”) vaga de manera aleatòria al voltant de la colónia.
  2. Si esta troba una font de menjar, retorna a la colónia de manera més o menys directa, deixant despuix de sí un rastre de feromones.
  3. Estes feromones són atractives, les formigues més propenques es voran atretes per elles i seguiran la seua pista de manera més o menys directa.
  4. Retornant a la colónia estes formigues hauran enfortit dita ruta.
  5. Si existixen dos rutes per a que apleguen a la mateixa font d'aliments llavors, en una mateixa cantitat de temps donat, la ruta més curta serà recorreguda per més formigues que la ruta més llarga.
  6. La ruta més curta haurà aumentat en cantitat de feromones i per tant escomençarà a ser més atractiva.
  7. La ruta més llarga anirà desapareixent degut a que les feromones són volàtils.
  8. Finalment, totes les formigues hauran determinat i triat el camí més curt.

Les formigues utilisen l'entorn com a mig de comunicació. Intercanvien informació de manera indirecta depositant feromones en la seua trayectòria, detallant l'estat del seu treball. L'informació intercanviada té un ambient local, solament una formiga ubicada prop d'a on les feromones varen ser depositades va a tindre una noció d'estes. Este sistema és cridat "Estigmergia (Stigmergy)" i ocorre en moltes societats d'animals (este sistema ha segut estudiat en el cas de la construcció dels pilars en els nius de termites). El mecanisme per a resoldre un problema massa complex per a ser abordat per formigues solament és un bon eixemple d'un sistema autoorganizado. Este sistema és basat en la retroalimentació positiva (el depòsit de feromones atrau atres formigues i estes enfortiran dita retroalimentació) i la retroalimentació negativa (malbarat de la ruta per evaporament). Teòricament, si la cantitat de feromones va ser la mateixa en totes les rutes durant tot el temps, cap ruta va ser elegida. No obstant, per la retroalimentació, una llaugera variació en una aresta amplificarà i llavors es permetrà elegir una ruta. L'algoritme es mourà d'un estat inestable en el que cap aresta és més forta que una atra, a un estat estable a on una ruta està composta per les arestes més fortes.

La filosofia bàsica de l'algoritme implica el moviment d'una colónia de formigues a través dels diferents estats del problema influenciat per dos polítiques de decisió a nivell local, rutes i atracció. D'esta manera, cada formiga incrementalmente construïx una solució del problema. Quan una formiga completa una solució, o durant la fase de construcció, les formigues evaluen la solució i modifiquen el valor de la ruta sobre les components utilisades en la solució. Esta informació de feromones dirigirà la busca de futures formigues. Ademés l'algoritme inclou dos mecanismes més, evaporament del rastre i accions daemon. L'evaporament del rastre reduïx tots els valors dels rastres evitant la possibilitat de caure en òptims locals. Les accions daemon són usades per a desviar el procés de busca d'una perspectiva local.

Extensions Comunes

Estes són algunes de les variacions més populars dels algoritmes de colónia de formigues (ACO Algorithms).

Sistema de Formigues

El sistema de formigues és el primer algoritme OCH propost. Es correspon en el funcionament descrit en l'anterior secció

Sistema Elitiste de Formigues

La millor solució global deposita feromones en cada iteración junt en totes les atres formigues.

Max-Min Sistema de Formigues (MMAS)

Agregada la cantitat màxima i mínima de feromones [tmax,tmin] Solament la millor iteración deposita feromones. Totes les arestes són inicialisades en tmax i re-inicialisades en tmax quan s'acosta a un estancament. [6]

Sistema de Colónia de Formigues

S'ha presentat anteriorment.[7]

Sistema de Formigues Basat en Rànquing (ASrank)

Totes les solucions es classifiquen d'acort la seua llongitut. La cantitat de feromones depositades és ponderada per a cada solució, de tal manera que les solucions en els camins més curts depositen més feromones que les solucions que en els camins més llarcs.

Colónia de Formigues Ortogonal Contínua (COAC)

El mecanisme de depòsit de feromones de COAC és permetre a les formigues la busca de solucions en conjunt i efectiva. Usant un método de disseny ortogonal, les formigues en un domini factible poden explorar les regions elegides d'una manera ràpida i eficient, en major capacitat de busca global i precisió. [8]

Optimisació de Colónia de Formigues en Llògica Difusa

Este método introduïx inteligència difusa dins de les formigues per a accelerar les habilitats de busca. [9]

Referències

  1. ↑ A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991.
  2. ↑ M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico vaig donar Milano, Italie, 1992.
  3. ↑ «Algoritmes en la naturalea» (en és). scienceblog. Consultat el 2023-01-24.
  4. ↑ S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, Self-organized shortcuts in the Argentine ant, Naturwissenschaften, volume 76, pages 579-581, 1989
  5. ↑ J.-L. Deneubourg, S. Aron, S. Goss et J.-M. Pasteels, The self-organizing exploratory pattern of the Argentine ant, Journal of Insect Behavior, volume 3, page 159, 1990
  6. ↑ T. Stützle et H.H. Hoos, MAX MIN Ant System, Future Generation Computer Systems, volume 16, pages 889-914, 2000
  7. ↑ M. Dorigo et L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, volume 1, numéro 1, pages 53-66, 1997.
  8. ↑ X Hu, J Zhang, and I Li (2008). Orthogonal methods based ant colony search for solving continuous optimization problems. Journal of Computer Science and Technology, 23(1), pp.2-18.
  9. ↑ Aloysius George, B. R. Rajakumar, Fuzzy Aided Ant Colony Optimization Algorithm to Solve Optimization Problem, Intelligent Informatics, Advances in Intelligent Systems and Computing, volume 182, pages 207-215.


Referències


Obtingut de «https://lenciclopedia.org/w/index.php?title=Algoritme_de_la_colónia_de_formigues&oldid=1407151»