Comprendi cosa succede, con visualizzazione e codice
Il problema del commesso viaggiatore (TSP) è un noto problema np-hard, che ha evidenti applicazioni pratiche nella vita reale. Ciò è utile, ad esempio, se si pianifica un viaggio in Europa e si stima il tempo di viaggio da punto a punto tra i siti.
Con solo 30 città, ci sarebbero più di 10³⁰ possibili permutazioni. Risolvere il TSP con 30 città con la forza bruta non è fattibile (il numero di granelli di sabbia sulla Terra è “solo” 10¹⁹).
Entro la fine di questo articolo, risolvere tali problemi con l’algoritmo evolutivo (EA) sarà facile per te. Sarai in grado di ottenere tu stesso il seguente risultato.
Ancora più importante, capirai cosa succede esattamente dietro le quinte e come ciascun componente (in particolare i vari tipi di mutazioni) contribuisce alla soluzione.
Molte guide usano erroneamente le parole Algoritmo Genetico (GA) e Algoritmo Evolutivo (EA) in modo intercambiabile.
GA, nella sua forma canonica, comporta i seguenti elementi (1):
1. Rappresentazione: stringhe di bit
2a. Selezione dei genitori: proporzionale alla forma fisica
2b. Ricombinazione: crossover a un punto
3. Mutazione: capovolgimento di bit
4. Selezione per la sopravvivenza: prossima generazione
GA è un sottoinsieme di EA.
In questa guida trattiamo aspetti di EA che non sono discussi in GA. In particolare ci concentreremo sugli aspetti relativi permutazione rappresentazione, spiegando con visualizzazioni e codice intuitivi.
Prima di procedere oltre, dobbiamo essere chiari sull’uso delle terminologie (2).
Fenotipi
Le soluzioni nel contesto del problema originale. Questi devono essere interpretati “così come sono” senza alcuna decodificazione; e sono agnostici anche rispetto al modo in cui vengono derivate le soluzioni.
Genotipi
Le codifiche che rappresentano il fenotipo. Potrebbe trattarsi di una stringa di bit, numeri interi o persino numeri in virgola mobile. Una mappatura deterministica converte ciascun genotipo nel corrispondente fenotipo.
Fitness
Una misura proveniente da una funzione che funge da base per la selezione. Ci permette di confrontare due genotipi (e quindi due soluzioni) e definire quale è “migliore”.
Popolazione
Raccolta di genotipi individuali, tipicamente di dimensione costante. Attraverso le iterazioni, i membri della popolazione cambiano attraverso il processo di ricombinazione, mutazione e selezione dei sopravvissuti.
Ri combinazione
Una variazione binaria, in cui due discendenti vengono creati da due genotipi genitoriali, fondendo i loro attributi nel processo.
Mutazione
Una variazione unaria eseguita su un singolo genotipo. Il cambiamento è casuale e serve a mantenere la diversità nella popolazione.
Selezione dei sopravvissuti
Il processo per determinare quali individui (rappresentati dal loro genotipo) rimarranno nella popolazione per la generazione successiva. L’obiettivo è mantenere le selezioni più promettenti, mantenendo la diversità per favorire potenziali miglioramenti futuri.
EA segue il seguente quadro.
Prima ancora di parlare di qualsiasi tipo di matematica o codice, dobbiamo inquadrare il problema e formulare il genotipo in modo tale che si adatti adeguatamente allo spazio delle soluzioni.
L’EA va oltre le rappresentazioni binarie e di permutazione, ma non approfondiremo ulteriormente qui.
La popolazione verrà quindi inizializzata con copie casuali del genotipo appropriato.
3.1.1 (Perché no) Rappresentazione binaria
Usare i bit per rappresentare il genotipo è una scelta naturale, poiché riflette la realtà. L’uomo, così come altri organismi, ha il DNA come materiale genetico. Possiamo pensare a una sequenza di DNA come a una stringa di 1 e 0, al posto di “A-T” e “C-G”.
La rappresentazione binaria funziona magnificamente quando il problema intrinseco coinvolge decisioni binarie: l’esempio perfetto è un problema con lo zaino, in cui ogni bit indica se l’elemento corrispondente è selezionato o meno.
Anche se tutto può essere rappresentato in bit, non è appropriato utilizzare i bit per rappresentare soluzioni a problemi non binari.
Si suppone che la mutazione modifichi la soluzione con uguali probabilità e garantisca che la soluzione risultante sia valida. Cambiare un numero da 7 (0111) a 8 (1000) richiede quattro capovolgimenti di bit, mentre cambiarlo a 3 (0011) o 5 (0101) o 6 (0110) richiede solo un capovolgimento di bit: le probabilità sono diverse. Usare la codifica Gray (3) non è sufficiente per risolvere questa discrepanza nella distanza di Hamming, e insistere su tale rappresentazione porterà a distorcere il processo evolutivo.
Inoltre, potrebbero essere necessari aggiustamenti dopo la ricombinazione e/o la mutazione, se viene utilizzata una rappresentazione binaria per rappresentare una permutazione. Questo perché ciascun indice si verifica esattamente una volta e il genotipo risultante potrebbe corrispondere a un fenotipo non valido.
3.1.2 Rappresentazione della permutazione
Questo ci porta a usare le permutazioni come genotipo. Oltre a TSP, questo è applicabile anche ai problemi che richiedono di selezionare una sequenza. Potrebbe essere una sequenza di luoghi da visitare, una sequenza di attività da completare, l’assegnazione di corrispondenze o il posizionamento dell’inventario in un magazzino.
Avere il genotipo come sequenza di indici è l’ideale in questo caso, perché possiamo essere certi di un fenotipo valido dopo le variazioni. Ad esempio, se ci sono 12 città tra cui scegliere, il genotipo può essere (9,2,6,1,7,8,11,0,4,3,10,5). Vedremo che esistono diversi modi per eseguire variazioni garantendo allo stesso tempo che ciascun numero intero appaia esattamente una volta.
Possiamo iniziare con il seguente schema per generare una popolazione. (Per brevità, escludo l’importazione di librerie poiché sono banali.)
class Evolutionary:
def __init__(self, task):
self.task = taskdef generate_genome(self, length):
genome = np.arange(length)
np.random.shuffle(genome)
return genome
def generate_population(self, size, genome_length):
population = (self.generate_genome(genome_length) for _ in range(size))
return population
Nell’EA, il processo di selezione dei genitori, variazione e selezione per la sopravvivenza avviene in modo iterativo per garantire che la popolazione nel suo insieme migliori attraverso le generazioni.
Se uno qualsiasi dei tre passaggi non viene implementato correttamente, l’intero algoritmo può andare in pezzi.
La selezione dei genitori, come uno dei tre pilastri, è importante perché i figli sono varianti dei loro genitori. Ricordiamo che ogni individuo è in realtà un genotipo, che è una rappresentazione di una soluzione candidata.
Quando combiniamo due genitori e applichiamo la ricombinazione (Sezione 3.3.1) per ottenere nuovi genotipi, ciò che realmente accade è che gli aspetti di due soluzioni vengono mescolati insieme, dando origine a nuove soluzioni candidate. Sebbene non sia una garanzia che genitori con una forma fisica più elevata abbiano una prole migliore, le probabilità saranno a nostro favore.
Tuttavia, dobbiamo trovare un equilibrio tra esplorazione e sfruttamento, proprio come nell’apprendimento per rinforzo. È una cattiva idea selezionare i due genitori più adatti nel 100% dei casi, perché la mancanza di diversità ci impedirebbe di trovare la soluzione ottimale (4).
3.2.1 Ruota della roulette per la selezione del genitore
L’ipotetica ruota della roulette ha la sua area direttamente proporzionale alla forma fisica di ciascun individuo. Ciascuna area rappresenta la probabilità di selezionare ciascun rispettivo individuo come genitore.
Un avvertimento è che i valori di fitness dovrebbero essere positivi. Prova tu stesso quanto segue e parlerà più forte di mille parole.
population=('A', 'B', 'C', 'D', 'E')
weights = (-.1, -.2, -.3, -.3, 1)
for _ in range(100):
x = random.choices(
population=population, weights=weights, k=2
)
print(x)
Vedrai che tutti i pesi negativi hanno zero possibilità di essere selezionati e che un peso altamente negativo non sarebbe diverso da un peso leggermente negativo. Non è quello che vogliamo in EA, perché una soluzione un po’ scadente dovrebbe essere significativamente preferita a una estremamente pessima.
In TPS, un modo comune di rappresentare l’idoneità è negare la distanza tra le città (vedrai il codice nella Sezione 4.1). In questo caso, dobbiamo normalizzare la forma fisica in modo tale che siano positivi. Questo potrebbe essere fatto sottraendo dall’idoneità minima (cioè più negativa), aggiungendo poi qualche piccolo epsilon in modo che anche la soluzione peggiore abbia una probabilità diversa da zero di essere selezionata.
Questa scelta di base è in realtà più importante di quanto sembri e richiede una certa discrezione da parte del data scientist. Considera quanto segue:
Il modo in cui viene definita la forma fisica è rilevante. Nel caso di cui sopra, fa sicuramente la differenza se un’idoneità pari a 100 fosse già “garantita” e incorporata, o se individuo A se lo è guadagnato ed è stato effettivamente un degno contendente degli altri.
3.2.2 Torneo per la selezione dei Genitori
Un altro approccio popolare è quello della selezione del torneo. Questo approccio viene utilizzato per garantire che i genitori più adatti non finiscano per dominare la maggior parte del tempo.
In questo caso, ciò che accade è che un piccolo sottoinsieme della popolazione viene selezionato casualmente e viene scelto l’individuo più adatto tra questo gruppo. Nell’esempio seguente (dove la dimensione del cerchio rappresenta la rispettiva forma fisica di ciascun individuo), l’individuo viola verrà selezionato come genitore per questa particolare corsa.
Ciò aiuta a mantenere la diversità, che è un aspetto importante come menzionato all’inizio della Sezione 3.2. Se fosse stata utilizzata la selezione della ruota della roulette, le probabilità che questo individuo viola venisse selezionato sarebbero piuttosto basse.
Nel codice, la selezione del torneo o la ruota della roulette per la selezione del genitore può essere implementata come segue:
class Evolutionary:
def selection(self, population, fitness_func, method='tournament'):
if method == 'tournament':
k = min(5, int(0.02*len(population)))
sub_population1 = random.choices(
population=population, k=k
)
sub_population2 = random.choices(
population=population, k=k
)
return (
sorted(sub_population1, key=fitness_func, reverse=True)(0),
sorted(sub_population2, key=fitness_func, reverse=True)(0)
)
else: # roulette wheel
min_fitness = min((fitness_func(gene) for gene in population))
selected = random.choices(
population=population,
weights=(fitness_func(gene)+eps-min_fitness for gene in population),
k=2
)
return tuple(selected)
Ho impostato la dimensione della sottopopolazione su 5 o 2% della popolazione, a seconda di quale sia inferiore. Naturalmente sei libero di modificare questo numero. Più piccoli sono questi iperparametri, maggiore sarà l’esplorazione (e meno lo sfruttamento).
In questo articolo hai imparato a conoscere i diversi componenti che compongono EA, esplorando la logica dei diversi approcci per la selezione dei genitori.
Ci sono molte cose nuove da assorbire in un unico articolo. Il tempo di lettura è già di 8 minuti e ci sono molti concetti più importanti in EA che devono essere discussi. Per mantenere l’apprendimento appetibile, per questo articolo è tutto.
Rimanete sintonizzati per il prossimo articolo, Algoritmo evolutivo: spiegazione delle mutazioniche verrà presentato entro le prossime 48 ore. Lì imparerai a conoscere la ricombinazione, la mutazione e la selezione per la sopravvivenza. La ricombinazione nel genotipo basato sulla permutazione non è banale come i crossover, ma le spiegazioni saranno supportate con intuizione, visualizzazione e codice in modo tale da poter essere chiaramente comprese anche senza esperienza precedente. Quindi metteremo insieme tutto il codice e risolveremo il TSP.
(1) DE Goldberg, Algoritmi genetici nella ricerca, ottimizzazione e machine learning (1989), Addison-Wesley
(2) AE Eiben e JE Smith, Introduzione al calcolo evolutivo (2015), Springer-Verlag Berlino Heidelberg
(3) C. Faloutsos, Hashing multiattributo utilizzando codici grigi (1986), In Atti della conferenza internazionale ACM SIGMOD del 1986 sulla gestione dei dati
(4) F. Vafaee, G. Turán, PC Nelson e TY Berger-Wolf, Bilanciare l’esplorazione e lo sfruttamento in un algoritmo genetico guidato dalla diversità adattiva (2014), Nel 2014 il Congresso IEEE sul calcolo evolutivo
Fonte: towardsdatascience.com
