Algoritmi Evolutivi Multiobiettivo (MOEA)

Gli algoritmi evolutivi sono alcuni dei principali metodi per l’esplorazione del fronte di Pareto ottimale nei problemi di ottimizzazione multiobiettivo, che risultano troppo complessi per essere

44

risolti con metodi esatti. In questo studio, per la risoluzione del problema multiobiettivo in esame, è stato utilizzato l’algoritmo NSGAII, la cui sigla sta per Non-dominated sorting genetic algorithm II. In questo tipo di algoritmo le soluzioni del problema di ottimizzazione è ordinato secondo il criterio di non dominanza ed è stato sviluppato in seguito all’osservazione che gli algoritmi che usano il concetto di dominanza per la valutazione degli individui, e che per il loro ordinamento utilizzano una funzione di fitness, utilizzano un grado di complessità computazionale elevato.

L’NSGA II è stato sviluppato in seguito all’NSGA, nel quale la popolazione viene classificata secondo il concetto di dominanza, cioè tutti gli individui non dominati vengono classificati in rank e successivamente suddivisi in base al valore della propria funzione di fitness. Una volta formato il primo gruppo, questo viene momentaneamente ignorato, per procedere alla creazione di altri gruppi non dominati di ordine inferiore.

Questo processo continua fintanto che non vengono classificati tutti gli individui. Questo algoritmo presenta però i seguenti problemi:

 Alta complessità computazionale derivata dal processo di ordinamento della popolazione; presenta infatti una complessità O(MN3), dove M è il numero di obiettivi e N è la grandezza della popolazione. L’NSGA è dunque molto dispendioso se si utilizzano un alto numero di individui.

 Nell’NSGA non è presente il concetto di elitismo e usando il metodo di fitness sharing per assicurare la diversità della popolazione, viene richiesta la specificazione del parametro 𝜎_𝑠ℎ (parametro di confronto tra le soluzioni).

Nell’ NSGA II invece la popolazione viene suddivisa in ranks, in accordo con il concetto di non dominanza, cioè per due qualsiasi vettori decisione a e b, si dice che:

𝑎 𝑑𝑜𝑚𝑖𝑛𝑎 𝑏 𝑠𝑒 𝑓(𝑎) > 𝑓(𝑏) 𝑎 𝑑𝑜𝑚𝑖𝑛𝑎 𝑑𝑒𝑏𝑜𝑙𝑚𝑒𝑛𝑡𝑒 𝑏 𝑠𝑒 𝑓(𝑎) ≥ 𝑓(𝑏) 𝑎 è 𝑖𝑛𝑑𝑖𝑓𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑏 𝑠𝑒 𝑓(𝑎) ≱ 𝑓(𝑏)𝑒 𝑓(𝑏) ≱ 𝑓(𝑎)

Le migliori soluzioni non dominate saranno raggruppate nel rank 1, tali elementi verranno poi trascurati per fare in modo che lo stesso procedimento venga applicato agli individui rimanenti, così da determinare il rank 2, e così via fino a che ogni individuo non apparterrà ad un rank. La complessità computazionale di questo processo è l’insieme delle complessità richieste per l’identificazione di ogni insieme non dominato, il quale diminuisce all’aumentare del rank che si va ad identificare perchè la popolazione rimanente da esaminare è in continua diminuzione.

45

Il processo di classificazione ha quindi capacità O(MN2), cioè utilizzando il concetto di non dominanza si diminuisce di un grado la complessità computazionale rispetto all’algoritmo NSGA. Durante il processo di classificazione della popolazione, per ogni soluzione vengono calcolate due entità: il domination count che conteggia il numero di soluzioni che dominano una generica soluzione p e l’insieme Sp che raccoglie tutte le soluzioni dominate dalla soluzione p.

Tutte le soluzioni del fronte non dominato avranno il domination count pari a 0, e apparterranno al rank 1. Per ognuna di queste soluzioni verrà quindi esaminato ogni membro q dell’insieme Sp , il cui domination count verrà fissato a 1. Se nel fare ciò per ogni elemento q, il domination cont diventa 0, q verrà sistemato in una lista separata Q i cui membri appartengono al secondo fronte non dominato. Viene rieseguita la stessa procedura e verrà determinato il terzo fronte. Tale processo continua fino a che non si sono determinati tutti i fronti (ranks).

Al fine di preservare la diversità delle soluzioni dello stesso fronte non dominato, l’NSGAII utilizza la tecnica della crowing-distance che rappresenta la distanza media di due punti giacenti su ciascun lato del punto in questione. Alle soluzioni di ‘confine’ che presentano il valore massimo e minimo delle funzioni obiettivo, viene assegnato un valore di crowing-distance infinito; per quanto riguarda gli altri valori, la crowing-distance assumerà un valore pari alla differenza dei valori delle due soluzioni adiacenti. Il calcolo viene fatto per ogni obiettivo e per ogni individuo il valore complessivo è la somma dei valori di distanza corrispondenti; successivamente viene fatta la selezione, nella quale viene preferito l’individuo appartenente al rank più basso oppure a parità di rank, viene selezionato quello collocato in una regione meno affollata (crowing-distance maggiore).

In questo algoritmo viene inoltre inserito il concetto di elitismo, in modo che i migliori cromosomi di una generazione saranno presenti anche nella successiva. Per quanto riguarda la selezione invece si ha una selezione per torneo, durante la quale vengono disputate vere e proprie gare fra le soluzioni di una popolazione scelte in maniera del tutto casuale. La soluzione migliore viene poi selezionata per fare parte della mating pool, nella quale ogni soluzione viene incrociata con altre soluzioni ed eventualmente mutata. Durante il torneo, le soluzioni vengono confrontate sulla base della crowing distance e del rank di appartenenza, all’individuo con rank minore e crowing distance maggiore verrà attribuita maggiore probabilità di riprodursi. Tale processo viene ripetuto tante volte quanti sono i membri della popolazione iniziale, in modo che ogni individuo partecipi ad almeno 1 torneo. Il passo successivo è la creazione di nuovi individui messa in atto dal crossover, attraverso il quale viene scambiato del materiale genetico tra i due individui che poi sarà essere alterato dall’operatore di mutazione: nel caso in cui si usino variabili binarie viene generato un numero random nell’intervallo (0,1), se esso è minore della probabilità di mutazione fissata

46

dall’utente, verrà mutato da 0 a 1 (o viceversa) ogni elemento della stringa. Se invece si usano variabili reali, l’algoritmo usa la mutazione polinomiale.

3.2.1 NSGA II

L’algoritmo viene sviluppato come segue: inizialmente viene creata una popolazione di dimensione fissata dall’operatore in modalità random e vengono valutate le funzioni obiettivo che costituiscono il problema in esame, seguendo il concetto di Pareto dominanza. Ad ogni individuo viene assegnato un rank corrispondente al suo livello di non dominanza, di seguito la popolazione sarà ordinata in ordine ascendente. Tutto questo processo viene ripetuto tante volte, quante sono le generazioni fissate. Durante il ciclo, verrà generata una popolazione di discendenti tramite gli operatori di selezione per torneo, ricombinazione e mutazione. Quindi si valutano le funzioni obiettivo per ogni individuo della nuova popolazione che sarà anch’essa ordinata. Di seguito verrà considerata una popolazione formata da genitori e figli, cioè verrà creata la mating pool. In essa la popolazione sarà ordinata in base alla rank di ciascun individuo e si formeranno così i fronti non dominati nei quali si troveranno tutti gli individui appartenenti allo stesso rank. L’unificazione delle due popolazioni è finalizzata a garantire l’elitismo. Se il numero di individui appartenenti al primo rank è minore del numero di elementi presenti ad ogni generazione, i rimanenti individui saranno scelti dai rank successivi in ordine di importanza. La scelta del numero di generazioni da sviluppare, come per il numero di individui della popolazione è affidata all’utente.

L’algoritmo NSGA II può essere riassunto come segue:

1. Determinazione del numero di individui della popolazione, del numero di generazioni e del numero di obiettivi che si intendere raggiungere

2. Generazione casuale della popolazione

3. Valutare le funzioni obiettivo sulla base delle variabili appena generate 4. Assegnare un rank sulla base della Pareto-dominanza

for i=1:numero di generazioni

5. Generare una popolazione di figli 6. Applicare la selezione per torneo 7. Ricombinare e mutare le soluzioni

8. Calcolo delle funzioni obiettivo per le nuove popolazioni 9. Assegnare il Rank

47

10. Generare gruppi di fronti non dominati con i genitori e i figli 11. Loop per aggiungere soluzioni alla nuova generazione 12. Determinare la crowing-distance fra i punti di ogni fronte

13. Selezione dei punti con un fronte più basso (rank) e un’ampia crowding-distance 14. Passare alla generazione successiva