Scopri Polaris

Compliance & Certificazioni

Brand page

Artificial Intelligence

Trasformazione Digitale

Approfondimenti

Digital twin

Simulation

IoT

Big Data

Advanced Manufacturing

Additive Manufacturing

Cyber Security

Industria 4.0

Augmented Reality/Virtual Reality

Potenziare la catena del valore

Agricolture 4.0

Polaris

Ageria

Deepclever

Strategy

Software Aziendali

The Polaris AI Team

Change Management

Finance Consulting

Infrastructure Services

Zero Based Mindset

Supply Chain

Algoritmi evolutivi: cosa sono, in quali casi possono essere applicati

Industria 4.0

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.

Genitore 1

Figura 1
Genitore 1 e Genitore 2 sono due possibili soluzioni che non risolvono l’indovinello delle otto regine.

Genitore 2

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.

Genitore 1

Figura 1
Consideriamo le scacchiere come sequenze di DNA e teniamo la parte sinistra di Genitore 1 e la parte destra di Genitore 2.

Genitore 2

Figura 3
Figlio prima della mutazione. La metà sinistra di Genitore 1 unita alla metà destra di Genitore 2.

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.

Figura 4
Soluzione

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.

Cyber physical system

Cyber physical system

La sinergia tra tecnologie IoT e Big Data è una delle basi della Cyber-Physical Convergence (e dei corrispondenti Cyber-Physical Production Systems – CPPS). La Cyber Physical Convergence è caratterizzata da un processo circolare (Information Value Loop) tra il mondo...

leggi tutto
AI Generativa: cos’è, come funziona e casi d’uso

AI Generativa: cos’è, come funziona e casi d’uso

Dall’uscita di ChatGPT a Novembre 2022, l’AI generativa è il discorso più sentito negli ufficio: “Ma lo usi?”, “E cosa ci fai?" ... Cerchiamo di fare un po' di chiarezza! Introduzione all'Intelligenza Artificiale Generativa Nel vasto campo dell'intelligenza...

leggi tutto
Simulation

Simulation

Simulazione tra macchine interconnesse per ottimizzare i processi Sistemi di simulazione per l’analisi e l’ottimizzazione dei processi, con possibilità di essere interconnesse agli impianti/macchine. Il concetto di simulazione è legato a quello di “Fabbrica digitale“....

leggi tutto
Deep Learning e dataset sintetici

Deep Learning e dataset sintetici

Come affrontare la mancanza di dati In applicazioni come Industria 4.0, non sempre i dati disponibili rispondono alle necessità delle strutture algoritmiche complesse, né riportano labeling corretti. Ecco perché si ricorre a dati sintetici, per sopperire a tutte...

leggi tutto