Algoritmi evolutivi: cosa sono, in quali casi applicarli

Si tratta di processi ispirati alle principali teorie dell’evoluzione naturale della biologia moderna, da Darwin e Wallace a Weismann e Mendel. In generale, i pilastri fondamentali su cui si basano queste tecniche sono: riproduzione, variazione, competizione e selezione.
Nel mondo industriale moderno è necessario adattare continuamente il sistema produttivo per rispondere velocemente alle esigenze del mercato.

Il cambiamento può riguardare la modifica della configurazione di uno o più livelli dell’assetto aziendale: da un macchinario alla struttura del magazzino, dalla progettazione di un prodotto all’organizzazione aziendale e così via. Spesso non è possibile valutare tutte le possibili configurazioni e per questo le aziende si affidano all’esperienza o alle linee guida disponibili, per poi accontenta accontentarsi di livelli di prestazione non ottimali.

Nel campo dell’intelligenza artificiale sono stati sviluppati numerosi algoritmi che permettono di esplorare velocemente le possibili configurazioni di un sistema individuando quelle che permettono di raggiungere prestazioni migliori.

Algoritmi evolutivi, cosa sono

Un approccio applicato in diversi settori industriali è rappresentato da un insieme di meta-euristiche appartenenti alla categoria degli algoritmi evolutivi. Questi algoritmi si ispirano alle principali teorie dell’evoluzione naturale della biologia moderna: evoluzione e selezione naturale (Darwin, Wallace), selezionismo (Weismann) e genetica (Mendel). In generale, i pilastri fondamentali su cui si basano queste tecniche sono i seguenti:

• riproduzione
• variazione
• competizione e selezione

La riproduzione è il processo di generazione di nuovi elementi di una popolazione a partire dai genitori. La variazione è una sorta di mutazione, spesso inattesa e casuale che si ha nel processo di generazione della nuova progenie. Infine, la competizione tra i nuovi elementi e la selezione dei migliori sono i processi inevitabili di sopravvivenza in un ambiente con risorse limitate.

Per approfondire la conoscenza sul funzionamento di un algoritmo evolutivo si potrebbe provare a risolvere il seguente indovinello delle otto regine.

Nell’indovinello delle otto regine si devono posizionare otto regine, appunto, sulla scacchiera in modo tale che nessuna regina sia minacciata da un’altra. Per chi non avesse esperienza del gioco degli scacchi la regina può mangiare muovendosi in orizzontale, verticale e in diagonale di un numero a piacere di caselle. Per esempio, la regina in d5 di figura 1b minaccia le regine in b3, c6, f3, e h5. Le possibili disposizioni delle otto regine sulla scacchiera sono 4.426.165.368 (sì, più di 4 miliardi) e anche solo limitando le possibilità mettendo al massimo una regina per ciascuna riga (o colonna) avremmo comunque 16.777.216 possibili configurazioni da valutare e solo 92 soluzioni che risolvono l’indovinello. Provare tutte le possibili soluzioni non aiuterebbe la ricerca di una soluzione plausibile.

Un modo per risolvere il problema, esplorando un numero contenuto di configurazioni è l’utilizzo di un algoritmo genetico, un algoritmo evolutivo che si ispira al processo di trasmissione dei geni dal cromosoma dei genitori ai figli. L’algoritmo genetico si compone di una sequenza di operazioni:

1. generazione di una popolazione iniziale
2. crossover
3. mutazione
4. valutazione della popolazione
5. selezione

La fase 1 è eseguita una sola volta, all’inizio del processo, le fasi successive sono ripetute in sequenza per un numero di volte stabilito inizialmente. Solitamente si decide di fermare l’esecuzione dell’algoritmo dopo un certo periodo di tempo/numero di cicli o se la soluzione è soddisfacente.

Fase 1: Generazione di una popolazione iniziale

In generale la popolazione dell’algoritmo è composta da decine, centinaia o migliaia di elementi in modo tale da avere maggiore variabilità e poter esplorare un numero più ampio di configurazioni. Per questo esempio ci limiteremo a due soli elementi.

Le due configurazioni Genitore 1 e 2 in figura 1 non sembrano molto promettenti perché molte regine si minacciano a vicenda. La soluzione dell’indovinello sembrerebbe ancora lontana.

Fase 2: Crossover

Si immagina la scacchiera come se fosse una sequenza di cromosomi e si genera un Figlio prendendo metà del patrimonio genetico dei due genitori. A titolo di esempio, si potrebbe dividere le due scacchiere a metà, trasmettere la parte sinistra di Genitore 1 e la parte destra di Genitore 2 come mostra figura 2 e unire le due parti in un Figlio in figura 3.

Fase 3: Mutazione

La mutazione genetica è un cambiamento, spesso casuale, che comporta una modifica del genoma. Analogamente, l’algoritmo genetico applica una variazione alla configurazione Figlio in figura 3 cambiando la posizione di uno o più elementi del genoma. Al fine della buona riuscita dell’algoritmo una mutazione “fortunata” della configurazione è lo spostamento di e1 in f1 e f3 in e3 che genera una soluzione dell’indovinello in figura 4.

Fase 4: Valutazione

La valutazione degli elementi della popolazione permette di scartare le configurazioni peggiori. In questo caso un criterio potrebbe essere quello di contare il numero di coppie di regine che si minacciano. Ad esempio, Genitore 1 ha 7 coppie di regine minacciate ed è una configurazione leggermente migliore di Genitore 2 che ne ha 8. Il Figlio Mutato in figura 4 è una soluzione dell’indovinello dove non ci sono coppie di regine che si minacciano.

Fase 5: Selezione

Adesso abbiamo 3 configurazioni Genitore 1, Genitore 2 e Figlio Mutato, che si valuta con il criterio del numero di coppie di regine minacciate, rispettivamente 7, 8 e 0. La selezione permette solo agli elementi migliori di sopravvivere e in questo caso le soluzioni migliori sono Genitore 1 e Figlio Mutato perché sono configurazioni con un numero minore di regine minacciate.

A questo punto l’algoritmo può interrompersi e mettere a disposizione le soluzioni trovate oppure continuare a esplorare configurazioni ripartendo dalla Fase 2.

Gli algoritmi evolutivi sono una valida opzione per poter risolvere un vasto panorama di problemi. I principi alla base del funzionamento sono generici e adattabili a molteplici utilizzi.

L’applicazione degli algoritmi evolutivi

Per questi motivi, gli algoritmi evolutivi sono stati applicati con successo a molti problemi sia classici sia industriali. A titolo di esempio, il problema di scheduling è un problema che ogni azienda industriale si trova ad affrontare quando una serie di lavorazioni deve essere svolta in un determinato tempo e secondo una determinata sequenza, occupando delle risorse spesso limitate, come strumenti, macchinari o materie prime.

In questa categoria di problemi l’obiettivo è trovare la giusta configurazione di assegnamento di operazioni e risorse per ottimizzare la produzione. Un’altra applicazione trasversale a molti settori industriali riguarda i problemi di instradamento per la logistica interna ed esterna, più in dettaglio: decidere quanti mezzi sono necessari per la movimentazione, quali percorsi sono migliori e quando i mezzi devono mettersi in movimento. Gli algoritmi evolutivi sono anche stati applicati a problemi di specifici settori, ad esempio, la verifica dei componenti dei telefoni cellulari.

Conclusioni

Per concludere, quando si usano queste tecniche una particolare attenzione deve essere rivolta alla scelta della funzione di valutazione degli elementi della popolazione. Da un lato, gli algoritmi evolutivi funzionano meglio se la valutazione della configurazione descrive con maggiore l’accuratezza la bontà della soluzione. Riprendendo l’esempio dell’Indovinello delle Regine un criterio per valutare una scacchiera potrebbe essere binario: giusto o sbagliato. Una configurazione è giusta se risolve l’indovinello, sbagliata altrimenti.

Però, come abbiamo visto, ci sono diverse gradazioni di sbagliato: 7 coppie di regine si minacciano, 8 coppie di regine… In questo modo abbiamo una descrizione migliore di quanto siamo distanti dalla soluzione e questo semplifica il lavoro del nostro algoritmo perché permette di scartare le soluzioni peggiori e tenere quelle più vicine all’obiettivo (anche se non sempre aiuta).

Dall’altro lato la valutazione è l’operazione con maggior costo computazionale e una funzione complessa può rallentare l’esecuzione dell’algoritmo.

In breve, i benefici e i punti deboli degli algoritmi evolutivi sono i seguenti:

Pro

più veloci di altri algoritmi
semplici: richiedono poca conoscenza del dominio di applicazione
l’interruzione anticipata restituisce comunque una soluzione

Contro

non si ha certezza di aver trovato l’ottimo assoluto
può non essere facile definire una funzione di valutazione

Bibliografia

Kaufmann, Paul, Castillo, Pedro A. (Eds.), “Proceedings of the 22nd International Conference, EvoApplications” 2019, Held as Part of EvoStar 2019, Leipzig, Germany, April 24–26, 2019.

Sanchez, Ernesto, Giovanni Squillero, and Alberto Tonda. “Industrial applications of evolutionary algorithms.” 2012.