Algoritmo Genetico

Passo 1: La popolazione iniziale

L’algoritmo genetico in questione prevede inizialmente di generare un certo numero di soluzioni, che andranno a costituire la popolazione iniziale, nel solo rispetto dei vincoli tecnologici dati dalle

precedenze, ma solo successivamente la stringa verrà suddivisa nelle varie stazioni sottostando al rispetto del tempo disponibile per ogni stazione.

In questo caso, verranno generate 4 stringhe di possibili soluzioni, con il metodo illustrato nel paragrafo 2.2.1.1 del capitolo 2. A partire dagli stessi dati di partenza della figura 1.1 di questa appendice, per la prima soluzione da creare, si genera un insieme contenente le operazioni disponibili dal punto di vista delle precedenze tecnologiche. Inizialmente, il suddetto insieme conterrà unicamente l’operazione 1, che pertanto verrà inserita al primo posto della stringa della prima soluzione.

SOLUZIONE 1: 1

Una volta inserita l’operazione 1, diventano disponibili le operazioni 2 e 3, tra le quali la scelta avviene casualmente e ricade, ad esempio, sull’operazione 2.

SOLUZIONE 1: 1 2

Ora le operazioni disponibili sono la 3 e la 4 e procedendo con lo stesso metodo fino ad esaurimento delle operazioni da inserire, una possibile soluzione è rappresentata dalla stringa seguente.

SOLUZIONE 1: 1 2 3 4 5 6 7 8

Procedendo in modo analogo, è possibile generare altre 3 stringhe, che possono essere le seguenti.

SOLUZIONE 2: 1 2 4 6 3 5 7 8

SOLUZIONE 3: 1 3 5 2 4 6 7 8

SOLUZIONE 4: 1 3 2 4 6 5 7 8

Compatibilmente con il tempo ancora disponibile nella prima stazione, è possibile inserirvi anche l’operazione numero 2, seguendo la sequenza della stringa, ma non è possibile inserire anche la numero 3, in quanto si eccede il tempo disponibile. E’ pertanto necessario chiudere la stazione 1 e aprirne una nuova e la situazione che si genera è mostrata sotto.

SOLUZIONE 1: 1 2 3

Alla fine della suddivisione, la prima stringa risulterà così distribuita su 4 stazioni.

SOLUZIONE 1: 1 2 3 4 5 6 7 8 4 stazioni

Analogamente, per le altre 3 soluzioni la situazione sarà la seguente.

SOLUZIONE 2: 1 2 4 6 3 5 7 8 4 stazioni

SOLUZIONE 3: 1 3 5 2 4 6 7 8 3 stazioni

SOLUZIONE 4: 1 3 2 4 6 5 7 8 4 stazioni

Dopo aver generato le prime 4 soluzioni come mostrato nel paragrafo precedente, è necessario calcolare, per ognuna, la funzione di fitness, nella quale vengono prese in considerazione il numero di stazioni utilizzate e la percentuale di tempo in cui ognuna viene occupata rispetto alla totalità del tempo disponibile. In particolare, la funzione di fitness viene calcolata tramite la formula sottostante, che deve essere minimizzata.

I valori della funzione di fitness che ne risulteranno per ogni soluzione saranno i seguenti. SOLUZIONE 1: F.O.= 3.54

SOLUZIONE 2: F.O.= 3.9 SOLUZIONE 3: F.O.= 2.25 SOLUZIONE 4: F.O.= 3.9

Una volta calcolata la funzione di fitness, si procede con la selezione delle stringhe che andranno a far parte delle soluzioni che genereranno le stringhe dei figli, stabilendo un valore k pari a 2 e selezionando quindi le prime due soluzioni. Tra queste, si copia la stringa con il valore di fitness migliore, ovvero la soluzione 1, scartando l’altra. Si procede allo stesso modo selezionando le due successive soluzioni, ovvero la 3 e la 4, copiando la soluzione 3 che ha una funzione di fitness migliore dell’altra. In sostanza, le due soluzioni che andranno a generare le stringhe di figli sono elencate sotto.

SOLUZIONE 1: 1 2 3 4 5 6 7 8

SOLUZIONE 3: 1 3 5 2 4 6 7 8

A partire dalle due soluzioni selezionate precedentemente, è necessario ora generare la stringa di figli, come delineato nei due metodi illustrati nel paragrafo 2.2.1.3

Metodo 1: Si seleziona casualmente una posizione della prima stringa, ad esempio la numero 4 e si

copiano gli elementi a destra di quella posizione nella stringa figlia, nelle stesse posizioni, cancellandoli contemporaneamente dall’altra soluzione, come mostrato nella figura sottostante.

SOLUZIONE 1: 1 2 3 4 5 6 7 8

SOLUZIONE 3: 1 3 5 2 4 6 7 8

FIGLIO: 5 6 7 8

Una volta cancellate le operazioni già inserite dalla seconda stringa, si prendono dalla stessa gli elementi rimasti in sequenza, andandoli a copiare nella stringa figlio, come mostrato in seguito.

posizione per entrambe le stringhe iniziali, si cancella l’operazione appena inserita da entrambe le stringhe e si fanno scorrere le attività non ancora inserite tutte verso sinistra. Le stringhe rimanenti dopo il primo passaggio, pertanto, sono le seguenti.

SOLUZIONE 1: 2 3 4 5 6 7 8

SOLUZIONE 3: 3 5 2 4 6 7 8

FIGLIO: 1

A questo punto, si inserisce casualmente uno dei due elementi che ora risultano iniziali alle stringhe delle soluzioni genitori, ovvero in questo caso l’operazione 2 per la soluzione 1 e l’attività 3 per la 3. Come appena detto, la selezione avviene casualmente e la scelta ricade ad esempio sull’operazione 2, che viene inserita nella stringa figlio e cancellata dai genitori con lo stesso procedimento di prima. Ciò che si ottiene è la situazione seguente.

SOLUZIONE 1: 3 4 5 6 7 8

SOLUZIONE 3: 3 5 4 6 7 8

FIGLIO: 1 2

Si procede in modo analogo a quanto appena descritto e la soluzione figlio che viene generata è mostrata sotto.

FIGLIO: 1 2 3 4 5 6 7 8

Una volta generata la soluzione con uno dei 2 metodi, si procede con la mutazione, che prevede di selezionare casualmente una posizione, ad esempio la numero 4, e di spostare l’operazione contenuta in un’altra postazione compatibilmente con i vincoli tecnologici. Ad esempio, nella postazione 4 è contenuta l’operazione 4, che può essere spostata nelle posizioni 3 e 5, tra le quali la scelta è effettuata casualmente e ricade, ad esempio sulla 3. La soluzione che si crea in questo modo è la seguente, ottenuta facendo scorrere verso destra tutti gli elementi successivi alla postazione 3 appena scelta.

Una volta eseguita la mutazione, si procede con la suddivisione delle stazioni come mostrato nel passo 1 e si continua l’algoritmo per il numero di iterazioni stabilito. Ovviamente qui a titolo di esempio è stata riportata la creazione di una sola stringa di figli, mentre nella realtà ne vengono generate molte di più, a seconda di quanti sono i genitori e del numero stabilito per i figli, per permettere i successivi accoppiamenti necessari.