Un procedimento di seeding per algoritmi genetici applicati al flow-shop

 4
cromosomi dei genitori. Analogamente, ricercando soluzioni di problemi complessi, gli 
Algoritmi Genetici (che nel prosieguo saranno indicati semplicemente con il loro 
acronimo GA, Genetic Algorithms) combinano fra di loro pezzi di soluzioni esistenti. 
 
In biologia lo sviluppo di idee moderne relative ai processi coinvolti nell’evoluzione è 
iniziato nel 1859 con la pubblicazione degli studi di Charles Darwin in “On the origin of 
species by means of natural selection”, studi successivamente sviluppati dall’abate 
Gregor Mendel, colui che per primo propose un approccio scientifico alla natura, alle 
proprietà e all’identificazione del materiale ereditario. 
Darwin, facendo sue le teorie di J.B. Lamarck (fondate sulla legge dell’uso e non uso 
degli organi e su quella d’ereditabilità dei caratteri acquisiti) e quelle dell’economista 
inglese Th. Maltus (“ogni popolazione tende a moltiplicarsi all’infinito”), dedusse che la 
gran maggioranza degli individui muore prima di potersi riprodurre e ciò avviene per il 
possesso di caratteri sfavorevoli. Questa è la selezione naturale darwiniana. La lotta per 
l’esistenza, per il cibo, per l’acqua, o il territorio, funge da filtro per individuare i pochi 
individui destinati a sopravvivere ed a riprodursi. Dato che le esigenze ambientali 
cambiano continuamente, la selezione naturale favorisce caratteri via via diversi e così gli 
esseri viventi si trasformano lentamente di generazione in generazione (Lamarck aveva 
illustrato l’esempio delle giraffe che, costrette dalla necessità di trovare cibo, hanno 
modificato, naturalmente nei secoli, le caratteristiche del loro collo). Nella lotta per la 
sopravvivenza non sono favoriti necessariamente gli individui più forti o veloci o i più 
intelligenti, ma solo quelli che riescono a riprodursi di più, quelli che hanno sviluppato 
un migliore adattamento all’ambiente. Privo delle conoscenze di genetica e di biologia 
molecolare necessarie, Darwin aveva compreso la necessità dell’esistenza di variazioni 
ereditarie, ma non era in grado di spiegarle. 
In perfetta analogia con gli eventi descritti, i GA partendo da un’iniziale popolazione di 
cromosomi, ognuno dei quali rappresenta una possibile soluzione del problema, 
associano ad ognuno di questi un certo livello d’adattamento, il “fitness score”, 
dipendente dalla bontà della soluzione del problema. Gli individui migliori, in altre 
parole con maggiore fitness, si riproducono combinandosi con altri individui e si ottiene 
così una nuova popolazione di possibili soluzioni, prodotta dalla selezione degli individui 
migliori della generazione corrente. In questo modo, dopo molte generazioni, le buone 
 5
caratteristiche vengono propagate a tuta la popolazione. Favorendo l’accoppiamento tra 
gli individui più adatti vengono esplorate le aree più promettenti dello spazio di ricerca. 
Per avere una maggiore comprensione è necessario dare alcune indicazioni: il vettore 
componente, o cromosoma, è una stringa, scritta in codice binario, di 0 e 1. La codifica è 
la più utilizzata per varie ragioni; la principale è storica: Holland e i suoi collaboratori 
concentrarono il loro interesse su di essa. Fornirono una giustificazione teorica; infatti 
confrontarono due codifiche capaci di trasportare la stessa informazione, una con pochi 
alleli e stringhe lunghe (ad esempio, stringhe binarie di lunghezza 100) e l’altra con pochi 
alleli e stringhe corte (ad esempio, stringhe decimali di lunghezza 30). Holland sosteneva 
che la prima permettesse un più elevato grado di parallelismo implicito. Goldberg ha 
rilevato come tale rappresentazione contenga sufficienti vantaggi, anche se negli ultimi 
anni alcuni studiosi, principalmente Antonisse, hanno evidenziato una sua difficile 
applicazione in problemi di più complessa schematizzazione. Per riferirsi ai cromosomi, 
secondo il contesto, si possono utilizzare termini quali stringhe, vettori o soluzioni. Ogni 
cromosoma può essere pensato come un punto dello spazio di ricerca (insieme delle 
soluzioni candidate). Continuando l’analogia genetica, le variabili saranno geni, i 
possibili valori di ognuno di loro alleli, e la posizione di una variabile in una stringa 
verrà indicata come locus. Inoltre, così come in genetica si parla di genotipo per riferirsi 
alla costituzione genetica di un organismo o di un virus, e di fenotipo per indicare le 
proprietà osservabili in un organismo che risultano dall’interazione tra il genotipo e 
l’ambiente, nel linguaggio dei GA il primo termine indicherà una stringa codificata, il 
secondo sarà il set decodificato di parametri. 
 6
Concetti fondamentali degli Algoritmi Genetici 
Sono tre gli elementi fondamentali della teoria degli Algoritmi Genetici di Holland: il 
Teorema degli Schemi, la Building Block Hypothesis e il Parallelismo Implicito. 
I GA, per funzionare adeguatamente, secondo Holland devono scoprire, ricombinare e 
favorire in modo “altamente parallelo”, buoni “blocchi costitutivi” di soluzioni, cioè 
combinazioni di valori di bit conferenti maggiore idoneità alle stringhe nelle quali sono 
presenti. 
Il concetto principale è il concetto di schema. Uno schema viene costruito introducendo 
un simbolo * nell’alfabeto dei geni e rappresenta l’insieme di stringhe che possono essere 
descritte dal modello costituito da 0, 1 e . Ad esempio, lo schema 1***0 rappresenta 
l’insieme di stringhe di 5 bit che cominciano con 1 e finiscono con 0. Le stringhe che 
corrispondono a tale modello sono dette istanze. 
Altri due concetti importanti sono l’ordine e la lunghezza. 
Per ordine di uno schema o(S) si intende il numero di posizioni fissate nello schema, cioè 
il numero di “1” e “0”. E’ un indice della specificità dello schema. 
Considerando ad esempio lo schema di lunghezza 10,  
S1=***001*110 si ha un ordine o(S1)=6. 
Tale nozione è molto importante nel calcolo della probabilità di sopravvivenza di uno 
schema alla mutazione. 
Con lunghezza definita δ(S), si intende, invece, la distanza tra la prima e l’ultima 
posizione fissata del cromosoma. Essa è indice della compattezza dell’informazione 
contenuta. In precedenza δ(S1)=10-4=6. 
Sarà usata per la probabilità di sopravvivenza dello schema a seguito dell’applicazione 
del crossover. 
Il comportamento dei GA è stato formalizzato da John Holland nel Teorema degli 
schemi. 
 7
Il Teorema degli Schemi, la Building Block Hypothesis e il Parallelismo Implicito 
La nostra trattazione esula da tali argomenti, pertanto enunceremo soltanto il testo di tali 
definizioni rimandando a testi specializzati per la spiegazione approfondita. 
Per Holland schemi brevi, di basso ordine, con un’idoneità media superiore alla media 
saranno rappresentati da un numero di istanze crescente in modo esponenziale nel 
tempo. 
Il Teorema degli Schemi costituisce un limite inferiore perché contempla solo gli effetti 
distruttivi del crossover e della mutazione. In realtà, il crossover è considerato il mezzo 
principale dei GA per la sua capacità di ricombinare istanze di buoni schemi per costruire 
istanze di schemi di ordine superiore. 
La supposizione che il processo in base al quale operano i GA sia questo fu detta da 
Goldberg Building Block Hypothesis: Un GA raggiunge performance vicine all’ottimo 
attraverso la giustapposizione di schemata corti, di basso ordine e di elevata 
performance detti building block. 
Infine, la valutazione implicita simultanea di un gran numero di schemi di una 
popolazione di n stringhe fu definita da Holland parallelismo implicito. 
Per Holland, inoltre, i GA permettono di trovare il giusto equilibrio tra exploitation ed 
exploratio; il sistema deve continuare ad esplorare nuove possibilità, ma deve anche 
incorporare e sfruttare le soluzioni già trovate e più promettenti. 
 8
Formulazione generica di un Algoritmo Genetico 
In generale il processo evolutivo simulato da un AG può essere raffigurato da  
t←t+1 
select P(t) from P(t-1) 
recombine P(t) 
evaluate P(t) 
Un semplice GA funziona così: 
1) Si inizi con una popolazione di n cromosomi formati da p bit. 
2) Si calcoli l’idoneità f(x) di ogni cromosoma. Per ogni problema da risolvere viene 
costruita una funzione fitness. In base al valore di tale parametro è decisa la 
sopravvivenza del cromosoma. Per costruire tale funzione si deve valutare il grado di 
adattamento al problema. Il valore numerico fornito da essa si suppone proporzionale 
all’utilità o abilità dell’individuo rappresentato dal cromosoma. 
3) Si ripetano i passaggi seguenti finchè non vengono cr4eati n discendenti, uno per 
ogni cromosoma: 
- Selezione di una coppia di cromosomi genitori dalla popolazione iniziale. 
- Realizzazione, con probabilità Pc (probabilità che i due genitori si incrocino), 
dell’incrocio della coppia da un punto scelto a caso per formare i due figli. 
- Mutazione dei 2 discendenti in ogni locus con probabilità Pm e inserimento dei nuovi 
cromosomi nella nuova popolazione. 
4) Si sostituisca la nuova popolazione a quella corrente. 
5) Si torni al passo 2. 
 
Dal passo tre viene realizzata la riproduzione. La selezione iniziale della popolazione è 
argomento di questa tesi. Per quanto riguarda i due operatori di combinazione dei 
cromosomi si parla di crossover e di mutazione. Dopo aver aggiornato la popolazione, e 
quindi i parametri che la caratterizzano, e aver creato la nuova generazione si applica un 
test d’uscita. Consiste evidentemente nel controllo di uno o più di questi parametri per 
stabilire se interrompere o continuare la reiterazione del GA. Alcuni parametri possono 
essere la numerosità della popolazione o il numero massimo di generazioni consentite. 
L’insieme di generazioni è indicato con il termine di esecuzione. 
 
 9
Codifica dei problemi 
Anche se non esiste un buon metodo per stabilire anticipatamente il potenziale di un GA, 
spesso questo si è dimostrato competitivo e capace di fornire performance migliori di 
altri metodi. La sua prestazione, infatti, dipende notevolmente dai dettagli, in pratica dal 
tipo di codifica scelta, dagli operatori adottati, dal criterio per stabilire il successo. Negli 
ultimi anni, proprio per questo motivo, è stata riaperta la discussione sulla migliore 
metodologia di representation dei cromosomi. 
Codifica binaria 
E’ in assoluto la più utilizzata, i cromosomi sono stringhe di 1 e 0. Sono state realizzate 
numerose estensioni dello schema di codifica binaria di base adottato da Holland, qui 
citiamo la Codifica Grey e quella diploide di Goldberg ed Hillis. 
 
Binaria   0000   0001   0010   0011   0100   0101   0110 
Grey       0000   0001   0011   0010   0110   0111   0101 
 
Pur essendo considerate da Holland le più adatte spesso, tali tipi di codifica risultano 
inapplicabili, come nel caso, ad esempio, del commesso viaggiatore e quello 
dell’evoluzione dei pesi nelle reti neurali. Sono invece utili nel Knapsack problem. In tali 
casi vengono utilizzati i classici operatori di crossover e mutazione. 
Codifica con permutazione 
Può essere usata in problemi di ordinamento, come il TSP. Tutti i cromosomi sono una 
stringa di numeri. 
 
CROMOSOMA A      12345678 
CROMOSOMA B      85647321