Poiché l’HSO ha dimostrato di essere estremamente performante nell’affrontare noti problemi ingegneristici, sembra essere un buon candidato per far fronte ai problemi di cell-formation applicati al Group technology.

3. H ARMONY SEARCH APPLICATO AL PROBLEMA DEL GROUP TECHNOLOGY

3.1 G ROUP TECHNOLOGY PROBLEM

Poiché l’HSO ha dimostrato di essere estremamente performante nell’affrontare noti problemi ingegneristici, sembra essere un buon candidato per far fronte ai problemi di cell-formation applicati al Group technology.

L’obiettivo di questo lavoro è quello di presentare le sue capacità (mantenere alte le performance di calcolo e la qualità della soluzione). Per far ciò è stato messo a confronto direttamente con un algoritmo meta-euristico (ACO-CF) molto recente pubblicato nel Marzo 2010 da Xiangyong Li, M.F. Baki e Y.P. Aneja “An ant colony optimization metaheuristic for machine-part cell formation problem”;Computer &

Operational Researche[15].

Nella cell formation, si utilizza solitamente una matrice binaria macchine/parti di dimensioni M x P (vedi Fig. 10).

Figura 10 Matrice macchine/parti

Le righe indicano le ‘M’ macchine del problema mentre le colonne rappresentano le

‘P’ parti. Ogni elemento binario della matrice

indica la relazione tra macchina ‘i’ e la parte ‘j’, in particolare ‘1’ indica che la macchina ‘i’ lavora la parte ‘j’, mentre ‘0’

che la parte non è lavorata dalla macchina.

La matrice mostra anche la similarità tra le parti e le macchine, elemento sul quale si basa il processo di raggruppamento di entrambi in celle di lavoro e famiglie.

Figura 11 Matrice ottimizzata

La matrice macchine/parti in figura 11 è il risultato di una ottimizzazione con metodi basati sulla similarità. In questo caso nella cella 1 lavorano le macchine 1 e 3 sulle parti 1 e 4, mentre nella cella 2 vengono lavorate le parti 3,5 e 2 dalle macchine 2 e 4.

In questo caso non ci sono ‘1’ fuori dai blocchi diagonali e non ci sono ‘0’ all’interno di quest’ultimi. Ciò significa che le due celle sono completamente indipendenti, ovvero che ogni famiglia di parti viene lavorata all’interno di un proprio gruppo di macchine.

Sfortunatamente è raro vedere un risultato cosi perfetto nelle realtà produttive, soprattutto quando il numero rispettivo di macchine e parti tende ad aumentare.

Figura 12 Matrice(2) macchine/parti

Figura 13 Matrice (2) ottimizzata

In Fig. 12 è rappresentata un’altra matrice macchine/parti con la relativa matrice ottimizzata(Fig. 13). Si nota subito come in questo caso siano presenti una eccezione, ed un vuoto nonostante la matrice sia la migliore che si possa ricavare a partire da quella iniziale (Matrice(2)). In questo caso la parte n° 3 è detta “parte eccezione” in quanto lavorata in due o più gruppi di macchine, mentre la macchina n°1 è detta “macchina collo di bottiglia” perché lavora due o più famiglie di parti.

In generale un risultato ottimale per una matrice macchine/parti deve soddisfare le

seguenti condizioni:

1. Minimizzare il numero di ‘0’ all’interno dei blocchi (vuoti) 2. Minimizzare il numero di ‘1’ all’esterno dei blocchi (eccezioni) Sulla base di queste condizioni, la Fig. 11 è un ottimo risultato per il problema n° 1, mentre la Fig. 13 è comunque il miglior risultato, e quindi l’ottimo, per il problema n°

2.

3.2 H ARMONY S EARCH O PTIMIZATION M ODIFIED

Un primo problema affrontato è stato quello di stabilire il numero di celle sul quale andare ad operare nella costruzione della soluzione poiché l’ACO-CF ottimizza tale valore durante la costruzione dell’armonia. Nel nostro caso la soluzione più semplice ma non meno efficace è stata quella di stabilire inizialmente il numero di celle sul quale andare ad operare e generare di conseguenza tutto l’insieme delle soluzioni.

Andando poi ad effettuare un ciclo su tutte le celle (che ovviamente hanno un valore massimo corrispondente al numero di macchine) si è riusciti a coprire un ampio spazio delle possibili soluzioni.

Data la matrice binaria del problema iniziale se K è il numero di celle stabilite, una soluzione ammissibile è data da un vettore macchine di M elementi, e da una vettore parti di P elementi con M e P rispettivamente il numero delle macchine e delle parti.

Assegnamo quindi la macchina ‘i’ alla cella ‘k’ con ∈ {1,2. . } e la parte ‘j’ alla cella

‘k’ con ∈ {1,2 … } e ∈ {1,2 … } mettendo il valore della cella di assegnamento nell’elemento i-imo e j-imo dei rispettivi vettori.

Un elemento del vettore soluzione presenta quindi una doppia informazione:

 macchina di riferimento (indice del vettore)

 cella di assegnamento (valore della variabile)

La soluzione in mostrata in Fig. 11 può essere rappresentata attraverso i due vettori seguenti:

1 2 1 2

Figura 14 Vettore macchine

In Fig. 14 è rappresentato il vettore macchine costituito da quattro elementi nel quale l’indice dell’elemento dà l’indicazione della macchina, il valore del bit indica la cella di assegnamento, quindi le macchine n° 1 e 3 sono attribuite alla cella n° 1 mentre la n° 2 e la 4 alla cella n° 2. In Fig. 15 è stato invece riprodotto il vettore delle parti per il quale valgono le stesse considerazioni.

Indice = 1 macchina N°1

1 2 2 1 2

Figura 15 Vettore parti

Poiché notoriamente le macchine sono in numero inferiore rispetto alle parti è stato ritenuto più efficiente suddividere la HM in tre sotto-matrici, una dedicata ai vettori delle macchine (Harmony Memory Macchine – HMM), una ai vettori delle parti (Harmony Memory Parti - HMP) con il medesimo numero di righe ma diverse colonne, ed un’altra per le fitness function (Harmony Memory Fitness - HMF) dove nell’elemento “i” è stata memorizzata la funzione obiettivo ricavata dalla combinazione del vettore macchine e parti di riga “i” delle rispettive sotto matrici.

Per aumentare le originali capacità dell’Harmony search tradizionale di esplorare ampie porzioni dello spazio mantenendo un buon rapporto tra velocità e qualità delle soluzioni sono state implementate alcune modifiche nella procedura.

La struttura intrinseca dell’algoritmo è pressoché uguale ovvero una armonia è rappresentata da un vettore di note/variabili realizzato attraverso il meccanismo tradizionale di random selection, pitch selection e pitch adjusting.

La bontà della soluzione è valutata secondo il criterio stabilito dall’algoritmo Ant colony ovvero

( ) = − + con:

A = numero di operazioni del problema

E = numero di eccezioni generati dalla soluzione V = numero di vuoti generati dalla soluzione

Inoltre, l'algoritmo introduce nuovi concetti che aiutano a trovare soluzioni migliori e

si muove un passo in avanti nella direzione di emulare il comportamento umano. Un

musicista che improvvisa una nuova composizione è influenzato dalle prime opere (le

sue e quelle di altri compositori, che costituiscono la base delle conoscenze

personali) e di solito tende a sfruttare al massimo questo patrimonio. La HSO

originale simula questo comportamento con la replica nella nuova armonia di una

singola nota da una nota armonia, ma manca della capacità di introdurre e

conservare porzioni più grandi di una composizione.

Per ovviare a questa mancanza si sfruttano le caratteristiche degli algoritmi genetici ed in particolare la procedura di crossover tra due soluzioni padre-madre che permette di crearne due nuove, figlie delle due.

Nel nostro algoritmo è stato applicato il TwoPoint crossover come mostrato in fig. 11

Figura 16 Twopoint crossover

Per poter selezionare il patrimonio genetico delle armonie migliori è stata assegnata a ciascuna soluzione una probabilità di essere selezionati proporzionale al proprio valore di fitness mentre la scelta dei due punti di taglio è stata presa in maniera random. In questo modo, si creano nuove armonie ma sempre sfruttando parti delle migliori create fino a quel momento.

Quindi con probabilità PC l’algoritmo sceglie due armonie madre e ne crea due figlie applicando direttamente il crossover.

Il parametro PC regola in questa prima fase la crescita esponenziale delle soluzioni ed in particolar modo valori bassi per la probabilità di crossover assicurano un grande incremento per le soluzioni che presentano valori di fitness sopra la media. Questa strategia sfrutta al limite la conoscenza di cui si dispone al momento dell'elaborazione di una nuova soluzione, sacrificando l'esplorazione dello spazio di ricerca. Valori di PC molto grandi, ovvero prossimi ad 1, riducono il fattore esponenziale a valori bassi; in questo caso, l'incremento del numero di nuove armonie, ovvero l'utilizzazione della conoscenza disponibile, è limitato, a vantaggio di una robusta esplorazione dello spazio di ricerca. Per PC tendente ad 1, si implementa una strategia di ricerca che assomiglia molto a quella random.

Occorre scegliere opportunamente il valore di PC per assicurare un buon compromesso fra le esigenze contrastanti cui si è accennato, vale a dire l'esplorazione dello spazio di ricerca e l'utilizzazione della conoscenza acquisita.

E' noto anche che la maggior parte i musicisti è in grado di improvvisare nuove

composizioni per un certo periodo, dopo di ché una certa diminuzione della creatività

o semplicemente la voglia di esplorare nuovi generi musicali porta a riutilizzare parte

dei primi lavori, o prendere ispirazione dagli altri compositori.

A volte questo determina la nascita di nuove ispirazioni e il miglioramento complessivo delle composizioni. Questo aspetto ricorda strettamente quello che si verifica quando la HSO, dopo un numero generalmente elevato di iterazioni, diventa incapace di esplorare nuove sezioni dello spazio delle soluzioni e comincia a visitare ripetutamente le stesse sequenze, senza ulteriori miglioramenti.

Per ovviare alla inevitabile convergenza dell’algoritmo verso un minimo locale è stata introdotta una procedura chiamata Harmony Recovery (HR) che dipende dall’Entropia della HM. Dopo un determinato numero di iterazioni, che può essere definito e controllato per mezzo di un Harmony Recovery Ratio (HRR), l'algoritmo aumenta la probabilità di effettuare una Recovery della memoria. Eseguita tale recovery si procede ad aumentare la probabilità di Crossover per sfruttare in maniera efficiente le soluzioni buone trovate sino a quel momento.

In generale l’algoritmo procede generando per prima cosa le due matrici (Harmony Memory Macchine, Harmony Memory Parti ) in modo casuale e valutando ogni volta, per ogni coppia di vettori, la bontà della soluzione da inserire nella matrice delle fitness function (come nel HSO originale).

Successivamente comincia la procedura iterativa che dura fino a quando le condizioni di terminazione sono state rispettate o il massimo numero di iterazioni viene raggiunto. Nel presente lavoro sia l’Ant Colony che l’MHSO vengono arrestati quando il numero massimo di iterazioni viene raggiunto, anche se il numero massimo di iterazioni cambia poiché il primo essendo un costruttivo, risulta meno veloce nella creazione della soluzione ma necessita di un numero inferiore di iterazioni, mentre il secondo è si molto più veloce ma necessita di un numero maggiore di iterazioni per trovare una buona soluzione.

3.2.1 Procedura iterativa

Nella prima fase l’algoritmo rispecchia quella che è la prima parte della vita del musicista fatta quindi di esplorazioni più o meno focalizzate dei vari ambiti musicali.

L’obiettivo è uscire da questa prima fase con una serie di “buone” soluzioni sulle

quali lavorare successivamente con l’MHSO vero e proprio. In questa fase si utilizza

una PC (probabilità di crossover) compresa tra 0.3-0.5, funzione anche del numero

della popolazione iniziale (dimensione della HM) mentre nella fase successiva tale

valore scende a 0.1.

In ogni caso una volta creata la Harmony memory, ad ogni iterazione si procede nel modo seguente:

Si estrae un numero random. Se questo è minore della PC allora si esegue il crossover tra due vettori delle parti; le due armonie possono anche essere soggette, a seconda del PAR, ad una procedura di pitch adjusting identica a quella della HSO tradizionale. I corrispettivi vettori macchine vengono invece realizzati in maniera costruttiva secondo tre metodologie:

a. Local Search Guidata(PLS) b. Pitch Selection (1-PLS)xPS c. Random Guidata (1-PLS)x(1-PS)

L’estrazione di un numero random decide se intraprendere la Local search Guidata oppure costruire il vettore macchine tramite PS (probabilità di Pitch Selection) e RG (probabilità di Random Guidata) .

Se il numero è inferiore a PLS comincia la ricerca locale guidata che assegna ogni macchina, tenendo conto del vettore parti già generato, nella cella che minimizza la funzione:

( ) = ∗ + (1 − ) ∗

Dove e rappresentano rispettivamente le eccezioni ed i vuoti creati andando ad inserire la macchina x nella cella k. Il valore di p da il peso ai due parametri ed è stato scelto pari a 0.7.

Se invece il numero random è maggiore di PLS si intraprende la costruzione alternativa del vettore macchine, ovvero per ogni variabile viene estratto un numero random per decidere se assegnare la macchina tenendo conto della HMM (procedura di pitch selection) oppure secondo una procedura definita Random Guidata che funziona nel modo seguente:

dato il vettore delle famiglie delle parti (celle) ogni macchina x avrà una certa probabilità di essere assegnata nella cella k data dalla sommatoria di tutte le parti lavorate dalla macchina presenti nella cella, rapportata al totale delle parti lavorate dalla macchina.

= ∑

∑

= 1, . . , = numero di parti lavorate dalla macchina x

La procedura in caso di Crossover termina con la realizzazione del vettore delle macchine.

Qualora invece il numero random fosse maggiore di PC, il vettore delle parti viene realizzato tramite:

 Pitch Selection

 Random

In maniera costruttiva, per ogni elemento del vettore viene estratto un numero random che se inferiore al PRR (Parti Random Rate) permette di estrarre il numero della cella da attribuire alla variabile in maniera random (ovviamente preso tra un range di valori ammissibili). In caso di numero superiore al PRR la cella viene scelta con la classica procedura di Pitch Selection dalla HMP con una probabilità funzione della cumulata delle fitness function delle varie armonie.

Una volta realizzati entrambi i vettori, parti e macchine, per cercare di migliorare la funzione obiettivo si realizza una ulteriore ricerca locale sfruttando la procedura di Pitch Adjusting (mutazione) su entrambi i vettori con l’obiettivo di cercare in un numero limitato di soluzioni vicine qualcuna che migliori la fitness. In ogni ciclo di Pitch Adjusting sui vettori si valuta la funzione obiettivo che solo se incrementata rende effettiva la mutazione. In questo caso il Pitch Adjusting sul vettore macchine è leggermente modificato perché è comunque necessario mutare la variabile tenendo in qualche modo conto del vettore delle parti già creato, infatti una macchina soggetta a mutazione viene assegnata in una certa cella tenendo conto dell’efficienza parziale delle celle misurata come:

= −

+ ∗ /

Con:

Ap = numero di operazioni nella cella k Ep = numero di eccezioni nella cella k Vp = numero di vuoti nella cella k

A = numero totale delle operazioni del problema

1 1 1

1 1 1

1 1 1 1 1 1 1 1 1

Figura 17 Matrice (3)

Per esempio dalla Fig. 17 si ricavano le seguenti efficienze parziali:

Efficienza cella 1 = ∗ = 0,29 Efficienza cella 2 = ∗ = 0,45

Una volta generata la nuova soluzione, indipendentemente da come sia stata generata e dal fatto che sia un vettore parti o macchine, è necessario valutare in primis se è ammissibile, dove l’unico vincolo di ammissibilità è la copertura di tutte le celle sia da parte del vettore parti, che di quello macchine. Qualora risultino una o più celle scoperte, per decidere quale parte, già assegnata, debba coprire la cella residua k, si utilizza una probabilità di scelta proporzionale al numero di parti presenti nelle celle diverse da k ponendo a 0 la probabilità di pescare dalle celle nelle quali è inserita una sola parte. Per le macchine vale la stessa procedura.

Ammesso che la soluzione sia ammissibile l’algoritmo procede con la valutazione dell’eventuale inserimento della Harmony Memory.

La peggiore, o meglio, un’armonia inefficiente (quella che sarà sostituita eventualmente da una nuova soluzione migliore) viene selezionata sulla base di un processo di selezione detto “roulette wheel selection” (Goldberg, 1989) piuttosto che sulla semplice valutazione della funzione di fitness nel HSO originale. Il procedimento si basa sul fatto che la probabilità di ogni armonia di essere selezionata e sostituita viene valutata sulla base di una cumulata delle funzioni di fitness, procedimento che si è mostrato molto efficace. L’efficacia è ovviamente maggiore per le soluzioni inefficienti. Se da un lato il rischio di rimozione di buone armonie è mantenuto molto basso merito di una corretta procedura di elitarismo, dall'altro l'algoritmo impedisce la minaccia di una precoce convergenza. Inoltre, questo consente una valutazione semplice e facile della probabilità di selezione.

L'armonia inefficiente selezionata viene finalmente sostituita e si prosegue quindi

verificando se la Harmony Memory sta tendendo ad un ottimo locale. Per fare ciò si

valuta l’entropia della matrice che se superiore ad un certo valore ER (Entropy rate)

permette letteralmente di esplodere la HM salvando solo la procedura migliore.

Poiché si è visto che reinserendo, immediatamente dopo la recovery, l’armonia migliore nella nuova Harmony Memory questa tende troppo velocemente alla suddetta armonia, si è pensato di mettere da parte tale soluzione e far evolvere la popolazione senza condizionamenti fino a che non risulti soddisfatta la seguente relazione:

| − | < 0.2 ∗ Dove:

X = valore della funzione obiettivo della soluzione migliore salvata

= ∗ ∑ media delle funzioni obiettivo della HM

Il valore dell’entropia viene calcolato valutando l’ordine all’interno della HM ovvero andando a contare il numero di soluzioni uguali rapportate alla dimensione della matrice.

L’ER non è un valore costante nel tempo ma ha un andamento del tipo:

=

Dove :

=

=

In questo modo nella prima parte, in particolar modo in gioventù, l’entropia necessaria a far esplodere la matrice deve essere molto alta, mentre tende ad un valore sempre più basso a mano a mano che le iterazioni si susseguono. In ogni caso è stato fissato un limite inferiore pari al 20%.

Una volta effettuata l’Harmony Recovery, le probabilità di crossover, pitch selection e random selection vengono riportate al valore iniziale (quello della fase giovanile) per favorire comunque una rapida ascesa delle fitness function della harmony memory.

La procedura completa dell’MHSO adattato al problema del group technology è la seguente:

set HMS,Iterazioni for Cella = 1 to Macchine

genera random Harmony Memory;

Set probabilità CR,PAR,PSP,PSM,RP,RM,LSG for I = 0 to Iterazioni do

if I < Iterazioni*0.2 // fase giovanile

Rand = numero random

If Rand < CR

Genera 2 nuovi vettori parti con crossover Controlla ammissibilità vettori parti Rand = numeroRandom

If Rand < LSG // Local Search Guidata

Genera i vettori macchine con la local Search Guidata else

for j = 0 to high(VettoreMacchine) // Random Guidata o // Pitch selection

Rand = numero random If Rand < PSM

Pitch selection da HMM Else

Random Guidata Rand = numero random If Rand < PAR

Pitch adjusting macchine (mutazione) End for

Controlla ammissibilità vettori macchine End if

Fai una neighborySearch (ricerca locale di soluzioni migliori) else

For j = 0 to high(vettoreParti) // Costruzione vettore Parti Rand = numeroRandom

If Rand < PSP

Pitch selection da HMP Else

Random selection Parti Rand = numero random If Rand < PAR

Pitch adjusting parti (mutazione) End for

Controlla ammissibilità vettore parti Rand = numeroRandom

If Rand < LSG // Costruzione vettore Macchine

Genera i vettori macchine con la local Search Guidata else

For j = 0 to high(vettoreMacchine) Rand = numeroRandom If Rand < PSM

Pitch selection da HMM Else

Random guidata Macchine End if

Rand = numero random If Rand < PAR

Pitch adjusting macchine End for

End if

Controlla ammissibilità vettore macchine

Fai una neighborySearch // ricerca locale di soluzioni migliori End if

Valuta l’efficacia della nuova armonia  ENewHarmony

Confrontala con quella di una soluzione inefficienteEOldHarmony If EnewHamony > EoldHarmony

Aggiorna la HM End if

Valuta ER // valutazione dell’entropia If ER >

Salva la migliore soluzione e rigenera random tutta la HM Reinserisci nella HM la miglior soluzione

End if

End if // fine della gioventù

Cambia le probabilità CR,PAR,PSP,PSM,RP,RM,LS if I > Iterazioni*0.2

calcola delta D // cambio probabilità dopo eventuale HRecovery if D <

inserisci la soluzione salvata nella HM End if

C = C+1 If C = ̅

Torna alle Probabilità adulto End if

Rand = numero random If Rand < CR

Genera 2 nuovi vettori parti con crossover Controlla ammissibilità vettori parti Rand = numeroRandom

If Rand < LSG

Genera i vettori macchine con la local Search Guidata else

for j = 0 to high(VettoreMacchine) Rand = numero random If Rand < PSM

Pitch selection da HMM Else

Random Guidata Rand = numero random If Rand < PAR

Pitch adjusting macchine End for

Controlla ammissibilità vettori macchine End if

Fai una neighborySearch // ricerca locale di soluzioni migliori else

For j = 0 to high(vettoreParti) Rand = numeroRandom If Rand < PSP

Pitch selection da HMP

Else

Random selection Parti Rand = numero random If Rand < PAR

Pitch adjusting parti End for

Controlla ammissibilità vettore parti Rand = numeroRandom

If Rand < LSG

Genera i vettori macchine con la local Search Guidata else

For j = 0 to high(vettoreMacchine) Rand = numeroRandom If Rand < PSM

Pitch selection da HMM Else

Random guidata Macchine End if

Rand = numero random If Rand < PAR

Pitch adjusting Macchine End for

End if

Controlla ammissibilità vettore macchine

Fai una neighborySearch (ricerca locale di soluzioni migliori) End if

Valuta l’efficacia della nuova armonia  ENewHarmony

Confrontala con quella di una soluzione inefficienteEOldHarmony If EnewHamony > EoldHarmony

Aggiorna la HM End if

Valuta ER // valutazione entropia If ER >

Salva la migliore soluzione e rigenera random tutta la HM Setta le probabilità da giovane

C = 0 End if End if

End for (fine harmony)

Confronta la miglior soluzione con le precedenti ottenute Aggiorna se migliore

End For // passa alla cella successiva