32.10 Metodi basati su popolazioni: algoritmi genetici e memetici

Parte 4 · Algoritmi euristici · Capitolo 32 · Capitolo 32: Metaeuristiche · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Metaeuristiche · App: TSP: simulated annealing e tabu search

Un algoritmo genetico (indicato con \(GA\)) mantiene una popolazione di soluzioni, codificate come stringhe (cromosomi). A ogni iterazione seleziona due genitori, preferendo i più adatti, li ricombina in un figlio (crossover), cambia alcuni geni casuali del figlio (mutazione), lo ripara se è inammissibile, e lo inserisce nella popolazione al posto di un individuo peggiore. Un algoritmo memetico applica inoltre una ricerca locale a ogni figlio.

• Lo pseudocodice di un \(GA\) steady-state per il KP con codifica binaria è il seguente; con \(memetic=\mathrm{true}\) è un algoritmo memetico.

Algoritmo: Algoritmo genetico e memetico per il KP

Input: istanza del KP \(p[1..n]\), \(w[1..n]\), \(c\); dimensione della popolazione \(P\); probabilità di mutazione \(p_m\); \(maxIter\); \(memetic\)

Output: miglior individuo della popolazione finale

1Function GeneticKP(\(p, w, c, P, p_m, maxIter, memetic\))

2for \(s := 1\) to \(P\) do ▹ popolazione iniziale casuale

3for \(j := 1\) to \(n\) do \(pop[s][j] := 1\) se \(\textsc{Rand}()<0.5\), altrimenti \(0\)

4\(\textsc{RepairKP}(pop[s])\);

5if \(memetic\) then \(\textsc{KPLocalSearch}(pop[s])\)

6\(fit[s] := \sum_j p[j]\,pop[s][j]\)

7end

8for \(it := 1\) to \(maxIter\) do

9\(a := \textsc{Tournament}()\); \(b := \textsc{Tournament}()\) \(cut := 1+\lfloor\textsc{Rand}()\cdot(n-1)\rfloor\) \(child := (pop[a][1..cut],\ pop[b][cut{+}1..n])\) ▹ selezione crossover a un punto

10for \(j := 1\) to \(n\) do \(\textsc{Rand}()<p_m\)\(child[j] := 1-child[j]\)

11\(\textsc{RepairKP}(child)\);

12if \(memetic\) then \(\textsc{KPLocalSearch}(child)\)

13\(worst :=\) l'ultimo indice \(s\) di minimo \(fit[s]\)

14if \(child\notin pop\) and \(\sum_jp[j]\,child[j] > fit[worst]\) then ▹ sostituzione

15\(pop[worst] := child\); \(fit[worst] := \sum_jp[j]\,child[j]\)

16end

17end

18return l'individuo di massimo \(fit\)

19Function Tournament()

20\(a := 1+\lfloor\textsc{Rand}()\cdot P\rfloor\); \(b := 1+\lfloor\textsc{Rand}()\cdot P\rfloor\)

21if \(fit[a]\ge fit[b]\) then return \(a\) else return \(b\)

Esegui in Colab:PythonC++

• Gli algoritmi genetici sono stati introdotti da Holland (1975) come modello dell'evoluzione naturale, e resi popolari come metodi di ottimizzazione da Goldberg (1989). Gli algoritmi memetici, in cui ogni individuo è migliorato da una ricerca locale, sono stati proposti da Moscato (1989).

• Codifica. Per il KP il vettore binario \(x\) è un cromosoma naturale: il gene \(j\) dice se l'oggetto \(j\) è selezionato. La fitness di un individuo è il suo profitto.

• Selezione. Un torneo binario estrae due individui a caso e tiene il più adatto: gli individui buoni hanno più probabilità di diventare genitori, ma ogni individuo ha una possibilità.

• Crossover. Il crossover a un punto prende i geni \(1,\dots,cut\) dal primo genitore e i geni \(cut+1,\dots,n\) dal secondo. L'idea è che le soluzioni buone condividano dei blocchi costitutivi buoni, e che ricombinare due genitori buoni possa mettere i blocchi buoni di entrambi in un solo figlio.

• Mutazione. Ogni gene viene invertito con una probabilità piccola \(p_m\), tipicamente \(\frac1n\): riporta nella popolazione geni che la selezione può aver perso.

• Riparazione. Il figlio può essere inammissibile. REPAIRKP toglie l'oggetto selezionato di efficienza minima finché la capacità non è rispettata (pareggi: l'oggetto di indice massimo). Le alternative sono le penalità, come nella Sezione 32.4.3, o codifiche in cui ogni cromosoma è ammissibile.

• Sostituzione. Nella versione steady-state dello pseudocodice, il figlio sostituisce l'individuo peggiore se è migliore e non è già nella popolazione; i duplicati farebbero perdere alla popolazione la sua diversità.

• Selezione e sostituzione intensificano (la popolazione si concentra sulle soluzioni buone); crossover e mutazione diversificano. Senza ricerca locale, un \(GA\) è bravo a trovare regioni promettenti ma lento a raggiungerne gli ottimi locali: l'algoritmo memetico aggiunge l'intensificazione mancante.

Esempio 32.11: \(GA\) sull'istanza di riferimento del KP

Con \(P=4\), \(p_m=\frac14\) e \(seed=36\). I primi \(16\) numeri casuali costruiscono la popolazione iniziale (gene \(1\) se il numero è minore di \(0.5\)):

\[ \begin{array}{lll}pop[1]: & 0.0003,\ 0.7354,\ 0.2018,\ 0.5114 & \to (1,0,1,0) \\ pop[2]: & 0.1796,\ 0.8825,\ 0.6936,\ 0.4391 & \to (1,0,0,1) \\ pop[3]: & 0.4547,\ 0.6489,\ 0.8061,\ 0.6990 & \to (1,0,0,0) \\ pop[4]: & 0.9148,\ 0.2446,\ 0.9246,\ 0.0692 & \to (0,1,0,1)\end{array} \]

Tutti e quattro gli individui sono ammissibili: \(pop[1]=(1,0,1,0)\), \(pop[2]=(1,0,0,1)\), \(pop[3]=(1,0,0,0)\), \(pop[4]=(0,1,0,1)\), con fitness \((16,14,10,11)\).

Iterazione 1 (numeri casuali \(0.1614\), \(0.2771\), \(0.8030\), \(0.4063\), \(0.0295\), \(0.7238\), \(0.2032\), \(0.4957\), \(0.4620\)). Il primo torneo estrae gli individui \(1+\lfloor 4\cdot 0.1614\rfloor=1\) e \(1+\lfloor 4\cdot 0.2771\rfloor=2\), e seleziona \(a=1\) (fitness \(16>14\)); il secondo estrae \(4\) e \(2\) e seleziona \(b=2\) (fitness \(14>11\)). Il taglio è \(1+\lfloor 3\cdot 0.0295\rfloor=1\): il figlio prende il gene \(1\) da \(pop[1]\) e i geni \(2\), \(3\), \(4\) da \(pop[2]\), \(child=(1,0,0,1)\). Solo il secondo numero di mutazione, \(0.2032\), è minore di \(p_m=0.25\): il gene \(2\) si inverte, \(child=(1,1,0,1)\), di peso \(12>9\). La riparazione toglie l'oggetto \(4\), l'oggetto selezionato di efficienza minima: \(child=(1,1,0,0)\), di peso \(9\) e profitto \(17\). Sostituisce l'individuo peggiore, \(pop[3]\) di fitness \(10\).

L'iterazione 2 seleziona \(a=2\) e \(b=3\), taglia dopo il gene \(1\) e costruisce \((1,1,0,0)\), senza mutazione: è già nella popolazione, e viene scartato. L'iterazione 3 seleziona \(a=2\) e \(b=1\), taglia dopo il gene \(3\), costruisce \((1,0,0,0)\), e la mutazione inverte i geni \(1\) e \(4\): \((0,0,0,1)\), di profitto \(4\), peggiore di ogni individuo, scartato.

Il miglior individuo è \((1,1,0,0)\): \(GA(I)=17=z(I)\), trovato da crossover, mutazione e riparazione insieme.

• Su KP20, con \(P=10\), \(p_m=0.05\) e \(300\) iterazioni, per \(seed=1,\dots,10\):

	min	media	max	ottime	profitto migliore per seme
\(GA\)	\(508\)	\(516.9\)	\(521\)	\(4\)	\(521,519,521,508,514,521,510,519,521,515\)
memetico	\(521\)	\(521.0\)	\(521\)	\(10\)	\(521,521,521,521,521,521,521,521,521,521\)

• Il \(GA\) semplice raggiunge l'ottimo \(521\) in \(4\) esecuzioni su \(10\); l'algoritmo memetico in ogni esecuzione. La ricerca locale rende ogni individuo un ottimo locale, e il crossover ricombina allora ottimi locali invece di soluzioni arbitrarie.

---

Avanti: 32.11 Confronto e conclusioni