Genetic Algorithm: una panoramica

Un Fisico in HKN: la metamorfosi

29 June 2018

La chiave del successo? Leggere!

13 July 2018

Introduzione

Un algoritmo genetico è un procedimento euristico di intelligenza artificiale per la risoluzione e l’ottimizzazione di problemi ispirato al processo di selezione naturale che governa l’evoluzione biologica.

L’algoritmo si basa sui concetti di “popolazione” e “individuo”: a partire da una popolazione iniziale di individui casuali, a ogni iterazione viene creata opportunamente una nuova popolazione dalla precedente, in base alla prestazione dei singoli individui.

Esso può essere suddiviso in diversi step:

valutazione e selezione;
riproduzione e crossover;

mutazione.

Valutazione e selezione

Una volta settato l’obiettivo da raggiungere o i parametri su cui basare il calcolo delle performance è possibile ordinare gli individui e selezionare tra essi i generatori della prole: i più adatti avranno una maggiore probabilità di riprodursi.

In generale (ma non sempre) è anche molto importante includere nella funzione di valutazione degli individui il parametro “diversità”, perché permette di evitare che l’algoritmo si blocchi in corrispondenza di un massimo locale, magari ancora molto distante (e quindi difficilmente superabile dalle sole mutazioni) e molto inferiore rispetto al massimo globale che si desidera venga raggiunto, e di sfruttare al massimo il potere ricombinatorio fornito dal crossover.

Esistono numerose strategie di selezione, tra le più comuni:

etilism (mantenere sempre inalterato nella popolazione successiva l’individuo più prestante,

in modo da non fare mai passi indietro nell’evoluzione della popolazione)

truncation (selezionare in blocco la porzione di individui che ha performato meglio)
tournament selection (avviare diversi “tornei” tra pochi individui scelti a caso dalla

popolazione; il vincitore di ogni torneo è selezionato per la riproduzione)

roulette-wheel (la probabilità di selezionare ogni individuo è calcolata normalizzando a 1 la

propria idoneità, valutate precedentemente)

reward-based (la prestanza dell’individuo viene calcolata sommando alla propria il valore

ereditato dai genitori)

Riproduzione e crossover

Ottenute le coppie di individui da far riprodurre, entra in gioco il crossover:

single/two-point (scelti a caso uno o più punti di crossover, il nuovo individuo riceverà

alternatamente porzioni di genoma da uno e dall’altro genitore)

uniform (ogni gene sarà sottoposto a crossover e potrà essere ereditato casualmente da uno o

dall’altro genitore)

arithmetic (l’intero genoma del nuovo individuo sarà ottenuto tramite un’operazione

matematica applicata ai due genomi dei genitori)

Mutazione

Dopo aver generato la nuova popolazione, vengono applicate (casualmente e con una data probabilità) le mutazioni:

gene inversion (un singolo gene viene sostituito dal suo inverso)
order changing (due singoli geni vengono scambiati tra loro)
arithmetic (viene svolta una determinata operazione matematica su alcuni geni)

Spunti ulteriori

Il crossover e le mutazioni sono gli operatori genetici più comuni e agiscono a livello di individuo, tuttavia è possibile progettare algoritmi più complessi, che prendano in considerazione le interazioni tra gruppi diversi e agiscano a livello di comunità; alcuni esempi:

miscelazione: un processo che distrugge gruppi precedentemente formati e aggiunge i loro individui ad una popolazione mista;
raggruppamento: un processo che forma nuovi gruppi da popolazioni miscelate durante l’esecuzione dell’algoritmo;
colonizzazione: un processo mediante il quale un gruppo estinto (nella fase di selezione a livello di gruppo, che avviene molto meno frequentemente rispetto che a livello di individuo) viene sostituito da individui di un gruppo di coloni;
migrazione: un processo attraverso il quale gli individui possono lasciare i propri gruppi e trasferirsi ai gruppi vicini.

L’idea di fondo può essere sfruttata anche a livello di individuo, ad esempio introducendo una probabilità che arrivi un individuo originato in modo completamente casuale durante la fase di creazione di una nuova generazione (prendendo quindi il posto di un “figlio” della popolazione precedente).

Considerazioni finali

Dalla mia esperienza, ritengo che lo studio di questa famiglia di algoritmi possa rappresentare un buon punto di partenza per i neofiti che desiderino approcciarsi al mondo dell’IA, in particolare perché è possibile creare piccoli progetti molto semplici per iniziare e man mano passare a problemi più articolati in modo graduale, fino ad arrivare a simulazioni anche molto complesse (nella gestione delle quali questo tipo di algoritmo, se tarato in modo appropriato, si dimostra molto potente ed efficace).

Per iniziare: Travelling salesman problem (http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5).