Il mondo degli algoritmi è meraviglioso, con molteplici strategie e strumenti sviluppati 24 ore su 24 per soddisfare la necessità di elaborazione ad alte prestazioni. Quando infatti gli algoritmi si ispirano alle leggi naturali si osservano risultati interessanti. Gli algoritmi evolutivi appartengono a tale classe di algoritmi. Questi algoritmi sono progettati in modo da imitare determinati comportamenti e tratti evolutivi del genoma umano. Inoltre, tale progettazione algoritmica non è limitata solo agli esseri umani, ma può essere ispirata anche dal comportamento naturale di alcuni animali. Lo scopo fondamentale della creazione di tali metodologie è quello di fornire soluzioni realistiche, pertinenti e tuttavia a basso costo a problemi che finora sono irrisolvibili con mezzi convenzionali.

ascii di a in Java

Diverse tecniche di ottimizzazione si sono quindi evolute sulla base di tali algoritmi evolutivi e quindi hanno aperto il dominio delle metaeuristiche. Metaeuristico è stato derivato da due parole greche, vale a dire, Meta Senso un livello sopra E heuriskein Senso trovare . Algoritmi come Particle Swarm Optimization (PSO) e Ant Colony Optimization (ACO) sono esempi di intelligenza di sciame e metaeuristiche. L’obiettivo dell’intelligenza dello sciame è progettare sistemi multi-agente intelligenti prendendo ispirazione dal comportamento collettivo di insetti sociali come formiche, termiti, api, vespe e altre società animali come stormi di uccelli o banchi di pesci.

Sfondo:

La tecnica di ottimizzazione delle colonie di formiche è puramente ispirata al foraggiamento comportamento delle colonie di formiche, introdotto per la prima volta da Marco Dorigo negli anni '90. Le formiche sono insetti eusociali che preferiscono la sopravvivenza e il sostentamento della comunità piuttosto che come specie individuali. Comunicano tra loro utilizzando il suono, il tatto e i feromoni. Feromoni sono composti chimici organici secreti dalle formiche che innescano una risposta sociale nei membri della stessa specie. Si tratta di sostanze chimiche in grado di agire come ormoni all'esterno del corpo dell'individuo che secerne, per influenzare il comportamento degli individui riceventi. Poiché la maggior parte delle formiche vive sul terreno, utilizzano la superficie del suolo per lasciare tracce di feromoni che possono essere seguite (annusate) da altre formiche.
Le formiche vivono in nidi comunitari e il principio alla base dell'ACO è osservare il movimento delle formiche dai loro nidi per cercare cibo nel percorso più breve possibile. Inizialmente, le formiche iniziano a muoversi in modo casuale nei loro nidi in cerca di cibo. Questa ricerca randomizzata apre molteplici percorsi dal nido alla fonte di cibo. Ora, in base alla qualità e alla quantità del cibo, le formiche riportano indietro una parte del cibo con la necessaria concentrazione di feromoni lungo il percorso di ritorno. A seconda di queste prove con i feromoni, la probabilità di selezione di un percorso specifico da parte delle formiche successive sarebbe un fattore guida per la fonte di cibo. Evidentemente questa probabilità si basa sia sulla concentrazione che sulla velocità di evaporazione del feromone. Si può anche osservare che, poiché anche la velocità di evaporazione del feromone è un fattore decisivo, è possibile tenere facilmente conto della lunghezza di ciascun percorso.

Nella figura sopra, per semplicità, sono stati considerati solo due possibili percorsi tra la fonte di cibo e il formicaio. Le fasi possono essere così analizzate:

seleziona da più tabelle sql

Fase 1: tutte le formiche sono nel loro nido. Non c'è contenuto di feromoni nell'ambiente. (Per la progettazione algoritmica, la quantità residua di feromone può essere considerata senza interferire con la probabilità) Fase 2: le formiche iniziano la loro ricerca con uguale probabilità (0,5 ciascuna) lungo ciascun percorso. Chiaramente il percorso curvo è il più lungo e quindi il tempo impiegato dalle formiche per raggiungere la fonte di cibo è maggiore rispetto all'altro. Fase 3: Le formiche attraverso il percorso più breve raggiungono prima la fonte di cibo. Ora, evidentemente, si trovano ad affrontare un dilemma di selezione simile, ma questa volta a causa della scia di feromoni lungo il percorso più breve già disponibile, la probabilità di selezione è maggiore. Fase 4: più formiche ritornano per il percorso più breve e successivamente aumenta anche la concentrazione di feromoni. Inoltre, a causa dell'evaporazione, la concentrazione di feromoni nel percorso più lungo si riduce, diminuendo la probabilità di selezione di questo percorso nelle fasi successive. Pertanto, l’intera colonia utilizza gradualmente il percorso più breve con probabilità più elevate. Quindi, si ottiene l'ottimizzazione del percorso.

Progettazione algoritmica:

Per quanto riguarda il comportamento delle formiche di cui sopra, è ora possibile sviluppare un progetto algoritmico. Per semplicità sono state considerate un'unica fonte di cibo e una singola colonia di formiche con solo due percorsi di attraversamento possibili. L'intero scenario può essere realizzato attraverso grafici pesati in cui la colonia di formiche e la fonte di cibo fungono da vertici (o nodi); i percorsi fungono da bordi e i valori dei feromoni sono i pesi associati ai bordi.
Lasciamo stare il grafico Sol = (V, E) dove V, E sono gli spigoli e i vertici del grafico. I vertici secondo la nostra considerazione sono IN_S (Vertice di origine – colonia di formiche) e IN_D (Vertice di destinazione – Fonte di cibo), I due bordi sono E₁ E E₂ con lunghezze l₁ E l₂ assegnato a ciascuno. Ora si può presumere che i valori dei feromoni associati (indicativi della loro forza) lo siano R₁ E R₂ per i vertici E₁ed E₂rispettivamente. Pertanto, per ciascuna formica, la probabilità iniziale di selezione del percorso (tra E₁ed E₂) può essere espresso come segue:

Evidentemente se R₁>R₂, la probabilità di scegliere E₁è più alto e viceversa. Ora, ritornando per la via più breve, dite E_io, il valore del feromone viene aggiornato per il percorso corrispondente. L'aggiornamento viene effettuato in base alla lunghezza dei percorsi e alla velocità di evaporazione del feromone. Pertanto, l’aggiornamento può essere realizzato gradualmente come segue:

A seconda della lunghezza del percorso –

Nell'aggiornamento di cui sopra, i = 1, 2 e 'K' funge da parametro del modello. Inoltre l'aggiornamento dipende dalla lunghezza del percorso. Più breve è il percorso, maggiore è il feromone aggiunto. In base al tasso di evaporazione del feromone –

Il parametro 'v' appartiene all'intervallo (0, 1] che regola l'evaporazione dei feromoni. Inoltre, i = 1, 2.

Ad ogni iterazione, tutte le formiche vengono posizionate al vertice sorgente V_S(colonia di formiche). Successivamente, le formiche si spostano da V_Sa V_D(fonte di cibo) seguendo il passaggio 1. Successivamente, tutte le formiche effettuano il viaggio di ritorno e rinforzano il percorso scelto in base al passaggio 2.

convertire una stringa in una data

Pseudocodice:

 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'aggiornamento dei feromoni e i calcoli dell'idoneità nello pseudocodice sopra possono essere trovati attraverso le implementazioni graduali menzionate sopra.
Pertanto, è stata stabilita l'introduzione della tecnica di ottimizzazione ACO. L'applicazione dell'ACO può essere estesa a diverse problematiche come le famose TSP (problema del commesso viaggiatore) .

Riferimenti:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf