Le metaeuristiche

Con il termine “Metaeuristiche34” si fa comunemente riferimento ad un insieme di tecniche che tentano di unire diversi procedimenti euristici elementari, dando origine ad organismi più complessi, in grado di condurre una ricerca della soluzione ottimale più efficiente ed efficace. Si tratta di una particolare sotto-classe della grande famiglia delle euristiche, che si è diffusa in tempi relativamente recenti (circa da 30 anni), con l’obiettivo di provare a risolvere i limiti tecnici ed operativi della più grande famiglia delle euristiche. Gli studiosi C. Blum ed A. Roli, nel 2003 all’interno dell’articolo intitolato “Metaheuristics in combinational optimization: Overview and conceptual comparison” e pubblicato sul ACM Computing Surveys, vol. 35, forniscono una classificazione di tutte le caratteristiche principali di questa particolare classe di algoritmi.

• Si tratta di strategie che guidano il processo di ricerca

• Non sono legate al problema specifico

• Lo scopo è quello di esplorare lo spazio circostante in modo tale da trovare soluzioni il più possibile vicine a quella ottima

• Solitamente si tratta di metodi non deterministici e approssimati

• Forniscono meccanismi per evitare di rimanere intrappolati in delimitati spazi di ricerca

• Individuano concetti base in grado di consentire un astratto livello di descrizione

• Le odierne metaeuristiche avanzate sono basate sull’esperienza di ricerca, ovvero sulla memoria, che guida la ricerca stessa

L’importanza di questi algoritmi va individuata nel fatto che non solo tentano di avvicinarsi alla soluzione migliore per la risoluzione del problema, ma portano avanti un approfondimento anche di tutte quelle zone nello spazio che presentano una qualche influenza sul risultato finale. Per poter tentare di effettuare una classificazione anche di queste nuove tecniche, vengono individuate le due componenti fondamentali di ogni metaeuristica: il comportamento ed il funzionamento viene determinato sulla base dell’intensificazione e della diversificazione.

34 _{Il termine “metaeuristiche” venne utilizzato per la prima volta da Glover nel 1986, intendendo qualcosa}

L’intensificazione rappresenta proprio quella caratteristica particolare delle metaeuristiche rispetto alle classiche euristiche, poiché consiste nella continua ricerca di soluzioni non solo nelle immediate vicinanze locali rispetto al punto di partenza, ma presuppone un’attività di ricerca anche in quelle zone ritenute maggiormente interessanti. Per quanto riguarda la diversificazione, invece, comporta lo studio e l’analisi di aree dello spazio non ancora sottoposte ad approfondimento, in modo tale che l’algoritmo individui zone del tutto nuove. Solamente tramite una corretta unione di queste due componenti fondamentali per ciascuna metaeuristica risulta possibile l’individuazione di una vasta gamma di punti potenzialmente interessanti unitamente alla riduzione della perdita di tempo dovuta al calcolo computazionale derivante dall’osservazione di aree prive di una qualche forma di importanza. Una volta definiti i due fattori principali caratterizzanti queste tecniche, è possibile fornire una prima forma di classificazione in due macro-famiglie:

• “Metaeuristiche Trajectory-based”: si tratta di approcci che presentano una singola soluzione iniziale che rappresenta il punto di partenza dell’analisi, che verrà sostituito dalla nuova soluzione ottimale trovata di volta in volta col susseguirsi del step di ricerca. L’attività di ricerca che caratterizza ogni fase produce come risultato un punto di “ottimo locale”, motivo per cui queste tecniche vengono denominate anche “exploitation oriented”, cioè letteralmente orientate allo sfruttamento, promuovendo la funzione di intensificazione all’interno dello spazio di ricerca. Le più famose tecniche che fanno parte di questa tipologia di metaeuristiche sono la “Simulated Annealing” (SA), la “Tabu Search” (TA) e la “Variable Neighborhood Search” (VNS).

• “Metaeuristiche Population-based”: con questa denominazione si fa riferimento ad un insieme di tecniche che utilizza una popolazione di soluzioni. Questa popolazione iniziale viene generata automaticamente tramite una macchina e viene sviluppata in ogni fase grazie ad un procedimento iterativo, che porta alla sostituzione degli elementi meno interessanti a favore dei nuovi individui generati all’interno della nuova generazione. Diversamente con quanto avveniva con le tecniche Trajectory-based, questi metodi vengono comunemente identificati anche con il termine “exploration oriented”, dal momento che la loro principale abilità risiede nella capacità di diversificare le zone di ricerca. Alcuni esempi facenti parte questa famiglia possono essere gli “Evolutionary Algorithms” (EA), la “Ant Colony Optimization” (ACO), la “Artificial Bee

Colony” (ABC), la “Differential Evolution” (DE) e in conclusione la “Particle Swarm Optimization” (PSO), che sarà oggetto di approfondimento nelle prossime pagine,

Prima di procedere con la definizione puntuale di questa particolare tipologia di metaeuristica e delle caratteristiche principali che presenta, viene di seguito fornita una classificazione più dettagliata di tutte le varie metaeuristiche che si possono trovare nello studio di questa disciplina, vista la straordinaria proliferazione di queste tecniche nel recente passato.

• “Single pointsearch vs. population-based”: come facilmente intuibile dal nome, il primo insieme di tecniche genera un singolo punto ottimale che viene fatto muovere all’interno dello spazio di ricerca, mentre nel secondo tipo l’esplorazione avviene tramite una pluralità di soluzioni (denominate “popolazione”), come analizzato in una precedente definizione. Dunque queste due classi di metaeuristiche differiscono l’una dall’altra per via del numero di elementi utilizzati contemporaneamente all’interno dell’analisi.

• “Nature inspired vs. non-nature inspired”: in questo caso la differenza tra le due differenti sotto-categorie la fa l’essenza stessa della metaeuristica, che può basarsi su un intrinseco paragone al mondo naturale, come per esempio gli Algoritmi Genetici (GA) che riprendono concetti evolutivi o i cosiddetti “Ant Algorithms”, i quali si rifanno ai comportamenti tenuti in natura dalle formiche. Per quanto riguarda invece le tecniche basate su metafore non naturali, alcuni esempi sono dati dai “Fireworks Algorithms”, basati sulle traiettorie assunte dai vari frammenti di un fuoco d’artificio, oppure la “Tabu Search”.

• “Dynamic vs. static objective function”: ciò che differenzia queste due famiglie è proprio la tipologia di funzione obiettivo che viene adoperata all’interno del particolare metodo. Difatti, mentre nel primo caso questa, essendo dinamica, si aggiorna durante l’intero processo immagazzinando l’insieme di informazioni rilevanti generate durante l’arco dell’analisi, nel secondo caso la funzione obiettivo rimane statica e identica dall’inizio alla fine.

• “Memory usage vs. memory-less methods”: questa classificazione fa riferimento al diverso grado di utilizzo della memoria nel procedimento delle metaeuristiche. I metodi che fanno parte della prima categoria ricordano i

procedimenti e i risultati passati (di breve o di medio lungo periodo), diversamente dal secondo gruppo, che invece ricorre esclusivamente allo stato presente del contesto di riferimento, per stabilire come procedere in futuro.

• “One vs. various neighborhood structures”: le metaeuristiche che possono essere considerate facenti parte la prima classe esposta sono caratterizzate dall’avere sempre la stessa struttura di elementi vicini durante l’intera analisi, in modo tale che l’intero complesso di vicinanza rimanga stabile senza subire cambiamenti. Viceversa, le metaeuristiche appartenenti al secondo gruppo elencato, presentano una struttura di vicinato soggetta a modifiche dinamiche e continue dovute all’esigenza di una costante diversificazione all’interno dell’intero processo.