Schaffer (SCH)

Il più semplice e il più studiato problema di test è stato introdotto da Schaffer nel 1984 [15]. Si tratta di un problema a singola variabile con due obiettivi da ottimizzare che si ottiene minimizzando due parabole.

( ) ( ) ( )  =  _{= −}   − < <  (9.5)

Il fronte ottimo di Pareto del problema SCH è un insieme convesso di soluzioni appartenenti all’intervallo x = [0,2] (figura 9.3a), la cui forma è determinata dalla seguente espressione:

(

)

Le soluzioni ottime appartengono all’intervallo [0,4] (figura 9.3b linea scura), mentre per gli altri valori obiettivo fuori dall’intervallo si hanno soluzioni dominate.

Figura 9.3 – Fronte ottimo di pareto nel problema di Schaffer.

Gli algoritmi sono stati testati sul problema SCH per 200 generazioni utilizzando 4 processori con ciascuno 40 individui. I risultati ottenuti evidenziano comportamenti simili in tutti e quattro gli algoritmi per quanto riguarda la capacità di identificare correttamente il fronte. Mentre se consideriamo il numero di soluzioni che migrano si hanno delle differenze (figura 9.4). Infatti, l’algoritmo dei microconi e dei coni di separazione evidenziano un numero molto alto di migrazioni, con picchi concentrati nelle prime generazioni (figura 9.4a cono di separazione, figura 9.4b microcono di separazione).

Figura 9.4 – Numero totale di migrazioni della popolazione durante le generazioni.

Bisogna sottolineare che nel caso degli algoritmi di separazione casuale e a graduatoria (figura 9.4c e figura 9.4d) è possibile regolare il livello di migrazione. In queste simulazioni si è scelto di non usare alcuna migrazione, perché entrambi gli algoritmi individuano correttamente il fronte ottimo di Pareto, nonostante che la comunicazione tra i processori sia minima o nulla.

Questi risultati possono essere forvianti perché dimostrano come sia possibile trovare il fronte ottimo senza scambiare informazioni tra i processori. Questo osservazione non è corretta perché tale fenomeno è strettamente legato alla semplicità del problema SCH e non è valido in generale. Se consideriamo i risultati da un altro punto di vista, ci accorgiamo che l’algoritmo dei coni di separazione, e in particolare quello dei microconi, hanno un alto numero di migrazioni, nonostante che gli altri algoritmi riescano a risolvere il problema senza scambiare soluzioni tra i processori.

processori per poter condividere i risultati e aumentare la velocità di convergenza (paragrafo 8.1.2), mentre nell’algoritmo dei microconi e dei coni di separazione la migrazione ha anche un altro ruolo: quello di spostare le soluzioni che non si trovano nelle aree dedicate al processore (verifica dell’ammissibilità). Adesso, considerando che il problema SCH sia risolvibile senza la cooperazione tra i processori, risulta molto probabile che gli algoritmi dei coni e dei microconi utilizzino la migrazione principalmente per trasferire le soluzioni non ammissibili. Questo utilizzo della migrazione non giustifica però un così alto livello di comunicazione tra i processori, soprattutto perché avviene in fasi dove oramai è stata raggiunto il fronte ottimo di Pareto.

In conclusione gli algoritmi dei microconi e dei coni di separazione hanno elevato costo di comunicazione legato a migrazioni che risultano non necessarie e che possono deteriorare le prestazioni considerevolmente.

Il problema di test SCH permette di confrontare l’algoritmo dei coni di separazione di Deb con l’algoritmo dei microconi. Nel capitolo 6 si è visto come il primo sia un caso particolare del secondo, quando ogni processore ha un solo microcono. Quindi variando il numero di microconi è possibile valutare l’andamento del numero di migrazioni tra i processori.

Figura 9.5 – Media delle migrazioni al variare del numero di microconi per processore.

Per ottenere il grafico (figura 9.5) sono state fatte 5 prove per 50 generazioni utilizzando 4 processori con 40 individui ciascuno. Per ogni prova si è fatta una media delle migrazioni dalla 20-esima generazione in poi per avere una distribuzione di soluzioni stabile. Infine per ricavare il grafico si è calcolata un ulteriore media dei valori trovati per ogni prova. Si nota che il numero di migrazioni minore si ha nel caso di un solo microcono (figura 9.5), che è la situazione equivalente all’algoritmo dei coni di separazione, mentre per un numero di microconi maggiore si hanno valori più alti. Questo andamento è legato al differente comportamento della mutazione e del crossover.

Quando le soluzioni si trovano fuori dei microconi vengono migrate. Nell’algoritmo dei coni di separazione queste soluzioni sono create dalla mutazione (figura 9.6a) e dal crossover tra soluzioni che si trovavano sul confine del cono (figura 9.6b), mentre nel caso dei microconi di separazione si aggiunge un terzo caso (figura 9.6c).

Figura 9.6 – I tre tipi di ricombianzione (mutazione, crossover e crossover tra microconi diversi).

Quando un processore possiede più di un microcono lo spazio ammissibile degli obiettivi è frammentato in più aree. Per cui può accadere che il crossover avvenga tra due soluzioni di microconi diversi e che il risultato sia una soluzione non ammissibile (figura 9.6c). Inoltre, più microconi ci sono, più è facile che il crossover del secondo tipo (figura 9.6b) generi una soluzione non ammissibile, perché il numero aree separate è aumentato e

quindi anche il numero di confini. La stessa cosa accade anche per la mutazione perché le soluzioni si trovano in microconi più piccoli ed è più facile oltrepassare i confini. Questi tre fenomeni uniti aumentano il numero di migrazioni tra i processori.

L’andamento del grafico (figura 9.5) entra in contraddizione con quanto detto perché non ha un andamento completamente crescente. Questo fenomeno si spiega semplicemente con il meccanismo della frammentazione illustrato nel capitolo dei microconi (paragrafo 6.2.2). Quando il numero di microconi è molto elevato si ha una distribuzione migliore nello spazio e il fenomeno della frammentazione diminuisce perché si crea un minor conflitto con la crowding distance. Bisogna aggiungere che, sebbene la migrazione si riduca, rimane sempre molto maggiore rispetto al cono si separazione, che è il caso con un solo microcono.

Un ultima osservazione sul problema SCH riguarda il comportamento dell’algoritmo del cono di separazione nelle prime generazioni. Proprio questo particolare esempio porta alla luce un difetto di questo algoritmo. Si osserva che nelle prime generazioni si hanno un numero di migrazioni tale che tutti i processori, tranne uno, trasmettono tutte le loro soluzioni. Infatti, si misurano 120 migrazioni che corrispondo a tre processori con 40 soluzioni ciascuno (figura 9.4a).

Figura 9.7 – Fronte generato dell’algoritmo del cono di separazione al variare delle generazioni.

Dal grafico si vede che alla prima generazione si hanno le soluzioni di tutti i processori (figura 9.7a), mentre nella seconda le soluzioni di uno solo (figura 9.7b). Questo comportamento ha un enorme influenza sulle prestazioni perché si hanno generazioni dove è in funzione un solo processore. Inoltre, i computer senza soluzioni hanno difficoltà a ripopolarsi perché devono aspettare che qualche soluzione migri nella loro area, con la possibilità che questo non accada.