El món algorítmic és preciós amb diverses estratègies i eines que s'estan desenvolupant durant tot el dia per respondre a la necessitat d'informàtica d'alt rendiment. De fet, quan els algorismes s'inspiren en lleis naturals, s'observen resultats interessants. Els algorismes evolutius pertanyen a aquesta classe d'algorismes. Aquests algorismes estan dissenyats per imitar certs comportaments així com trets evolutius del genoma humà. A més, aquest disseny algorítmic no només està limitat als humans, sinó que també es pot inspirar en el comportament natural de certs animals. L'objectiu bàsic de la fabricació d'aquestes metodologies és proporcionar solucions realistes, rellevants i, tanmateix, de baix cost a problemes que fins ara no es poden resoldre per mitjans convencionals.

Així, han evolucionat diferents tècniques d'optimització basades en aquests algorismes evolutius i, per tant, han obert el domini de la metaheurística. Metaheurística s'ha derivat de dues paraules gregues, és a dir, Meta significat un nivell per sobre i heuriskein significat trobar . Algorismes com l'optimització de l'eixam de partícules (PSO) i l'optimització de la colònia de formigues (ACO) són exemples d'intel·ligència d'eixam i metaheurística. L'objectiu de la intel·ligència d'eixams és dissenyar sistemes intel·ligents multiagents inspirant-se en el comportament col·lectiu d'insectes socials com ara formigues, tèrmits, abelles, vespes i altres societats animals com estols d'ocells o bancs de peixos.

Antecedents:

La tècnica d'optimització de la colònia de formigues està purament inspirada en el buscant menjar comportament de les colònies de formigues, introduït per primera vegada per Marco Dorigo a la dècada de 1990. Les formigues són insectes eusocials que prefereixen la supervivència i el manteniment de la comunitat més que com a espècie individual. Es comuniquen entre ells mitjançant el so, el tacte i la feromona. Feromones Són compostos químics orgànics secretats per les formigues que desencadenen una resposta social en membres de la mateixa espècie. Aquests són productes químics capaços d'actuar com a hormones fora del cos de l'individu secretor, per afectar el comportament dels individus receptors. Com que la majoria de formigues viuen a terra, utilitzen la superfície del sòl per deixar rastres de feromones que poden seguir (olorar) per altres formigues.
Les formigues viuen en nius comunitaris i el principi subjacent de l'ACO és observar el moviment de les formigues des dels seus nius per tal de buscar aliment en el camí més curt possible. Inicialment, les formigues comencen a moure's aleatòriament a la recerca d'aliment al voltant dels seus nius. Aquesta cerca aleatòria obre diverses rutes des del niu fins a la font d'aliment. Ara, en funció de la qualitat i la quantitat del menjar, les formigues porten una part del menjar de tornada amb la concentració necessària de feromones al seu camí de retorn. Depenent d'aquests assaigs de feromones, la probabilitat de selecció d'un camí específic per part de les formigues següents seria un factor orientador de la font d'aliment. Evidentment, aquesta probabilitat es basa en la concentració així com en la velocitat d'evaporació de la feromona. També es pot observar que com que la velocitat d'evaporació de la feromona també és un factor decisiu, la longitud de cada camí es pot explicar fàcilment.

A la figura anterior, per senzillesa, només s'han considerat dos possibles camins entre la font d'aliment i el niu de formigues. Les etapes es poden analitzar de la següent manera:

Etapa 1: Totes les formigues estan al seu niu. No hi ha contingut de feromones al medi ambient. (Per al disseny algorítmic, la quantitat de feromones residuals es pot considerar sense interferir amb la probabilitat) Etapa 2: Les formigues comencen la cerca amb la mateixa probabilitat (0,5 cadascuna) al llarg de cada camí. És evident que el camí corbat és més llarg i, per tant, el temps que triguen les formigues a arribar a la font d'aliment és més gran que l'altre. Etapa 3: les formigues pel camí més curt arriben abans a la font d'aliment. Ara, evidentment, s'enfronten a un dilema de selecció similar, però aquesta vegada a causa del rastre de feromones al llarg del camí més curt que ja està disponible, la probabilitat de selecció és més alta. Etapa 4: tornen més formigues pel camí més curt i, posteriorment, també augmenten les concentracions de feromones. A més, a causa de l'evaporació, la concentració de feromones en el camí més llarg es redueix, disminuint la probabilitat de selecció d'aquest camí en etapes posteriors. Per tant, tota la colònia utilitza gradualment el camí més curt amb més probabilitats. Així, s'aconsegueix l'optimització del camí.

Disseny algorítmic:

convertir una cadena en una data

Pel que fa al comportament anterior de les formigues, ara es pot desenvolupar un disseny algorítmic. Per simplicitat, s'ha considerat una única font d'aliment i una sola colònia de formigues amb només dos camins de possible travessa. Tot l'escenari es pot realitzar mitjançant gràfics ponderats on la colònia de formigues i la font d'aliment actuen com a vèrtexs (o nodes); els camins serveixen com a vores i els valors de feromones són els pesos associats a les vores.
Sigui el gràfic G = (V, E) on V, E són les arestes i els vèrtexs de la gràfica. Els vèrtexs segons la nostra consideració són EN_s (Vèrtex font – colònia de formigues) i EN_d (Vèrtex de destinació - Font d'aliment), Les dues vores són I₁ i I₂ amb llargs L₁ i L₂ assignat a cadascun. Ara, es pot suposar que els valors de feromones associats (indicatius de la seva força). R₁ i R₂ per als vèrtexs E₁i E₂respectivament. Així, per a cada formiga, la probabilitat inicial de selecció del camí (entre E₁i E₂) es pot expressar de la següent manera:

Evidentment, si R₁> R₂, la probabilitat d'escollir E₁és superior i viceversa. Ara, mentre tornem per aquest camí més curt digues E_i, el valor de la feromona s'actualitza per al camí corresponent. L'actualització es fa en funció de la longitud dels camins, així com de la velocitat d'evaporació de la feromona. Per tant, l'actualització es pot realitzar pas a pas de la següent manera:

Segons la longitud del camí -

A l'actualització anterior, i = 1, 2 i 'K' serveixen com a paràmetre del model. A més, l'actualització depèn de la longitud del camí. Més curt és el camí, més alta serà la feromona afegida. D'acord amb la velocitat d'evaporació de la feromona:

El paràmetre 'v' pertany a l'interval (0, 1] que regula l'evaporació de feromones. A més, i = 1, 2.

A cada iteració, totes les formigues es col·loquen al vèrtex font V_s(colònia de formigues). Posteriorment, les formigues es mouen de V_sa V_d(font d'aliment) després del pas 1. A continuació, totes les formigues realitzen el seu viatge de tornada i reforcen el camí escollit en funció del pas 2.

pitó de cadena f

Pseudocodi:

 Procedure AntColonyOptimization: Initialize necessary parameters and pheromone trials; while not termination do : Generate ant population; Calculate fitness values associated with each ant; Find best solution through selection methods; Update pheromone trial; end while end procedure>

L'actualització de feromones i els càlculs d'aptitud al pseudocodi anterior es poden trobar mitjançant les implementacions pas a pas esmentades anteriorment.
Així, s'ha establert la introducció de la tècnica d'optimització ACO. L'aplicació de l'ACO es pot estendre a diversos problemes com el famós TSP (Problema del venedor viatger) .

Referències:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf