Algoritmi di Swarm Intelligence e loro applicazioni

Con i continui progressi nelle tecnologie (come machine to machine, telecomunicazioni wireless, intelligenza artificiale e analisi dei big data), l'Internet of Things (IoT) mira a connettere tutto per la condivisione delle informazioni e il processo decisionale intelligente. L'intelligenza dello sciame (Swarm Intelligence, SI), tema affrontato in uno degli articoli precedenti, fornisce la possibilità di un comportamento di gruppo attraverso la collaborazione in individui che hanno un'intelligenza limitata o assente. In questo articolo verranno esaminati alcuni algoritmi di Swarm Intelligence rappresentativi, riassumendo le loro principali applicazioni nell'IoT.

In natura molte creature, come pesci, uccelli e api, hanno comportamenti di gruppo. Le capacità dei singoli membri di un gruppo sono limitate, ma l'intero gruppo ha una forte vitalità. Questa non è solo una semplice sovrapposizione di abilità individuali ma anche un adattamento dei comportamenti individuali attraverso lo scambio di informazioni e la cooperazione, avendo come risultato l'intelligenza di gruppo.

Gli algoritmi SI sono stati progettati per studiare i principi della produzione di individui semplici che possono esibire comportamenti avanzati e complessi di ottimizzazione dello sciame attraverso la cooperazione, l'organizzazione, scambio di informazioni e apprendimento tra individui in un gruppo. Il potenziale parallelismo e le caratteristiche distribuite degli algoritmi SI consentono di risolvere problemi non lineari complessi con capacità avanzate in termini di autoadattabilità, robustezza e capacità di ricerca. Ad oggi, ci sono molti algoritmi di ottimizzazione ispirati al SI, come l'ottimizzazione classica dello sciame di particelle (PSO), della colonia di formiche (ACO) e delle colonie di api artificiali (ABC).

Di seguito, una loro panoramica.

L’algoritmo PSO (Particle Swarm Optimization) deriva dallo studio del comportamento degli stormi di uccelli nella ricerca del cibo: si suppone che ogni uccello non conosca l’effettiva posizione del cibo ma solo la sua distanza da esso e che modifichi istante per istante la sua velocità (quindi la sua posizione) per minimizzare tale distanza. L’ottimizzazione avviene in funzione dell’esperienza passata (miglior posizione raggiunta) della particella e del gruppo. Bilanciando opportunamente i vari contributi, si può garantire una completa esplorazione dello spazio di ricerca e il superamento di ottimi locali. Ciascuna soluzione viene valutata attraverso una funzione di costo da minimizzare, per permettere un confronto opportuno e credibile delle diverse alternative e modificare le soluzioni nel modo più opportuno.

L'algoritmo ACO (Ant Colony Optimization) è un’euristica che ricalca il comportamento naturale delle formiche. Si tratta di un algoritmo di ricerca del percorso ottimale tra un nodo di partenza (colonia di formiche) e un nodo obiettivo (cibo) basato sull'utilizzo di tecniche probabilistiche e sull'ottimizzazione metaeuristica. Riprendendo quanto accennato in precedenza, in natura le formiche si muovono a caso alla ricerca del cibo; quando lo trovano, tornano a ritroso fino alla colonia depositando sul terreno dei segnali chimici (feromoni) al fine di tracciare un sentiero tra cibo e colonia per le altre formiche (comportamento cooperativo). Quando altre formiche incontrano il sentiero tracciato dai feromoni, smettono di muoversi a caso e lo iniziano a percorrerlo anche loro. Col passare del tempo i feromoni evaporano e le formiche sono portate a compiere piccole variazioni di percorso. Il segnale dei feromoni tende a mantenersi più a lungo nei percorsi più brevi poiché sono anche quelli più frequentati dalle formiche. In conclusione, pur essendo ogni formica dotata di poca memoria e di scarsa intelligenza, tutte insieme riescono a risolvere un problema complesso senza bisogno di un'organizzazione centralizzata. Simile a questo algoritmo vi è l’algoritmo di ottimizzazione delle farfalle (BOA) che simula la popolazione di farfalle a trovare cibo. Ogni farfalla emette una certa concentrazione di profumo, percepisce l'odore di altre farfalle intorno e si sposta verso quella che emette più profumo.

L'ABC (Artificial Bee Colony) è un algoritmo basato sugli sciami, ispirato al modello di approvvigionamento delle colonie di api. Nel sistema, la qualità di una risorsa alimentare dipende da diversi fattori, come la distanza dall'alveare, la quantità di cibo presente e la facilità di estrazione; a ciascuna risorsa è assegnata un'ape il cui compito è quello di memorizzare le informazioni relative alla risorsa (distanza, direzione, utilizzabilità). Raccolte queste informazioni, le api impiegate condividono le informazioni raccolte con le altre, con una probabilità che è proporzionale alla bontà della risorsa stessa. La comunicazione delle informazioni avviene tramite la waggle dance: con questa danza, l'ape definisce distanza (durata della danza) e direzione della risorsa (calcolando l'angolo che questa forma ha con la direzione del sole). Maggiore è la quantità di informazioni relative a una risorsa che viene condivisa nell'alveare, maggiore è la possibilità che altre api siano reclutate per il suo sfruttamento. Il sistema prevede, inoltre, che quando una risorsa alimentare si estingue, essa potrà essere abbandonata. In questo caso le api impiegate ad essa associata si trasformeranno in esploratori e si dedicheranno alla ricerca di una risorsa nelle vicinanze dell'alveare. In applicazioni reali, si definisce lo spazio delle soluzioni come lo spazio entro cui si muovono le api artificiali: una soluzione sarà associata ad una fonte di cibo e la quantità di nettare corrisponde alla qualità (fitness) della soluzione stessa.

Tutti gli algoritmi prima descritti trovano applicazione nel contesto dell’IoT, in modo particolare nelle reti wireless di sensori (WSN). WSN è la base della futura rete IoT ed è una rete wireless composta da un grande numero di sensori statici o mobili in modo auto-organizzato. WSN può raccogliere, elaborare e trasmettere le informazioni rilevate degli oggetti all'interno della copertura della rete e riferire a utenti. Per le sue caratteristiche di basso costo e alta adattabilità, ha attirato ampia attenzione negli ultimi anni ed è stata ampiamente applicato in svariati campi, come quello militare, agricolo, monitoraggio ambientale ecologico, industria e medicina. Attualmente, l'obiettivo principale del design WSN è migliorare le prestazioni, risparmiare energia e garantire una comunicazione sicura. A differenza delle reti wireless tradizionali, la scala di WSN è spesso molto ampia e i nodi sono spesso distribuiti in modo casuale nella rete. Il WSN ha ancora capacità limitate in un nodo o in una rete. Ad esempio, ogni nodo ha capacità di calcolo e comunicazione limitate e la sua energia è spesso limitata. Pertanto, la progettazione efficiente dei protocolli di routing deve tenere conto del percorso di comunicazione tra i nodi del sensore (sorgente) e il centro di comando (ricevitore) per risparmiare energia. Inoltre, i protocolli devono essere auto-organizzati e resistenti a guasti e perdite.

Dunque, si comprende bene come gli algoritmi SI hanno caratteristiche promettenti, come l'auto-adattabilità, la robustezza e la capacità di ricerca, per risolvere problemi non lineari complessi, che sono attributi chiave richiesti dal WSN. Pertanto, un numero crescente di algoritmi di routing basati su SI ha trovato applicazione nel routing WSN.

Il PSO, ad esempio, viene utilizzato per cercare il centro energetico della rete e i nodi più vicini a questo oppure per ridurre al minimo la distanza di trasmissione aggiornando i nodi del cluster e per ottimizzare il consumo energetico della rete, mentre versioni ottimizzate di ACO e ABC sono usate per algoritmi e protocolli di routing ottimali che sono le chiavi per risparmiare energia di comunicazione e quindi prolungare la durata della rete.

Con il 5G in rapida crescita, inoltre, l'IoT diventa più complesso e eterogeneo ma più promettente. Attualmente, a causa dell'energia limitata dei nodi WSN, i problemi chiave risiedono nella selezione efficiente dei nodi (selezione CH) e nella collaborazione dei nodi (es. problema di localizzazione), che dalle prime analisi si è dimostrato essere risolvibili da algoritmi SI.

La stessa Wonderlab, infine, in un progetto di Ricerca & Sviluppo, ha analizzato l’applicabilità dell’algoritmo ACO nel contesto del Talent Management, nello specifico per creare percorsi di apprendimento personalizzati in una piattaforma e-learning.

In un settore lavorativo in cui sono richieste sempre nuove competenze, ogni apprendista deve essere indirizzato nell’acquisire quelle giuste richieste, affine allo stesso tempo ai propri interessi. Ogni apprendista, quindi, viene paragonato ad una formica. I percorsi maggiormente effettuati da altri utenti che appartengono allo stesso cluster diventano quelli ottimali e che hanno maggiori possibilità di essere scelti anche dal soggetto in questione. Questi diventano da traccia per gli altri utenti che sono affini ai propri interessi. L’algoritmo si basa sull’idea che le formiche seguano, nel medio-lungo termine, il percorso più conveniente per raggiungere la loro meta che sia cibo o sia l’ingresso del nido. Le formiche che intraprendono un percorso non ottimale vedono la loro scelta scartata in breve tempo grazie ad un meccanismo di volatilità dei messaggi ormonali con cui gli insetti comunicano e questo garantisce la convergenza verso una soluzione ottima in breve tempo.