Algoritmi genetici - Guida rapida

L'algoritmo genetico (GA) è una tecnica di ottimizzazione basata sulla ricerca basata sui principi di Genetics and Natural Selection. Viene spesso utilizzato per trovare soluzioni ottimali o quasi ottimali a problemi difficili che altrimenti richiederebbero una vita per risolverli. Viene spesso utilizzato per risolvere problemi di ottimizzazione, nella ricerca e nell'apprendimento automatico.

Introduzione all'ottimizzazione

L'ottimizzazione è il processo di making something better. In ogni processo, abbiamo una serie di input e una serie di output come mostrato nella figura seguente.

L'ottimizzazione si riferisce alla ricerca dei valori degli input in modo tale da ottenere i valori di output "migliori". La definizione di “migliore” varia da problema a problema, ma in termini matematici si riferisce alla massimizzazione o alla minimizzazione di una o più funzioni obiettivo, variando i parametri di input.

L'insieme di tutte le possibili soluzioni o valori che gli input possono assumere costituiscono lo spazio di ricerca. In questo spazio di ricerca si trova un punto o un insieme di punti che fornisce la soluzione ottimale. Lo scopo dell'ottimizzazione è trovare quel punto o insieme di punti nello spazio di ricerca.

Cosa sono gli algoritmi genetici?

La natura è sempre stata una grande fonte di ispirazione per tutta l'umanità. Gli algoritmi genetici (GA) sono algoritmi basati sulla ricerca basati sui concetti di selezione naturale e genetica. I GA sono un sottoinsieme di un ramo di calcolo molto più ampio noto comeEvolutionary Computation.

Le GA sono state sviluppate da John Holland e dai suoi studenti e colleghi presso l'Università del Michigan, in particolare David E. Goldberg, e da allora sono state sperimentate su vari problemi di ottimizzazione con un alto grado di successo.

In GA, abbiamo un file pool or a population of possible solutionsal problema dato. Queste soluzioni subiscono quindi ricombinazione e mutazione (come nella genetica naturale), producendo nuovi bambini, e il processo si ripete su varie generazioni. Ad ogni individuo (o soluzione candidata) viene assegnato un valore di fitness (basato sul valore della sua funzione oggettiva) e agli individui più in forma viene data una maggiore possibilità di accoppiarsi e produrre individui più “in forma”. Ciò è in linea con la teoria darwiniana della "sopravvivenza del più adatto".

In questo modo continuiamo a “evolvere” individui o soluzioni migliori nel corso delle generazioni, fino a raggiungere un criterio di arresto.

Gli algoritmi genetici sono di natura sufficientemente casuale, ma funzionano molto meglio della ricerca locale casuale (in cui proviamo solo varie soluzioni casuali, tenendo traccia delle migliori finora), poiché sfruttano anche le informazioni storiche.

Vantaggi delle GA

Gli GA hanno diversi vantaggi che li hanno resi immensamente popolari. Questi includono:

Non richiede alcuna informazione derivata (che potrebbe non essere disponibile per molti problemi del mondo reale).
È più veloce ed efficiente rispetto ai metodi tradizionali.
Ha ottime capacità parallele.
Ottimizza funzioni sia continue che discrete e anche problemi multi-obiettivo.
Fornisce un elenco di soluzioni "buone" e non solo una singola soluzione.
Ottiene sempre una risposta al problema, che migliora nel tempo.
Utile quando lo spazio di ricerca è molto ampio e sono coinvolti molti parametri.

Limitazioni di GA

Come ogni tecnica, anche le GA soffrono di alcune limitazioni. Questi includono:

Le GA non sono adatte a tutti i problemi, specialmente i problemi che sono semplici e per i quali sono disponibili informazioni derivate.
Il valore di fitness viene calcolato ripetutamente, il che potrebbe essere costoso dal punto di vista computazionale per alcuni problemi.
Essendo stocastico, non ci sono garanzie sull'ottimalità o sulla qualità della soluzione.
Se non implementato correttamente, GA potrebbe non convergere verso la soluzione ottimale.

GA - Motivazione

Gli algoritmi genetici hanno la capacità di fornire una soluzione "abbastanza buona" "abbastanza veloce". Ciò rende gli algoritmi genetici attraenti per l'uso nella risoluzione dei problemi di ottimizzazione. I motivi per cui sono necessari GA sono i seguenti:

Risolvere problemi difficili

Nell'informatica, c'è una vasta serie di problemi, che sono NP-Hard. Ciò significa essenzialmente che anche i sistemi informatici più potenti impiegano molto tempo (anche anni!) Per risolvere il problema. In uno scenario del genere, le GA dimostrano di essere uno strumento efficiente da fornireusable near-optimal solutions in un breve lasso di tempo.

Fallimento dei metodi basati sul gradiente

I metodi tradizionali basati sul calcolo funzionano partendo da un punto casuale e muovendosi nella direzione del gradiente, fino a raggiungere la cima della collina. Questa tecnica è efficiente e funziona molto bene per le funzioni obiettivo a picco singolo come la funzione di costo nella regressione lineare. Ma, nella maggior parte delle situazioni del mondo reale, abbiamo un problema molto complesso chiamato paesaggi, che sono fatti di molti picchi e molte valli, che fa fallire tali metodi, poiché soffrono di una tendenza intrinseca a rimanere bloccati all'ottimo locale come mostrato nella figura seguente.

Ottenere rapidamente una buona soluzione

Alcuni problemi difficili come il problema del venditore in viaggio (TSP), hanno applicazioni del mondo reale come la ricerca del percorso e la progettazione VLSI. Ora immagina di utilizzare il tuo sistema di navigazione GPS e ci vogliono pochi minuti (o anche poche ore) per calcolare il percorso "ottimale" dalla sorgente alla destinazione. Il ritardo in tali applicazioni del mondo reale non è accettabile e quindi una soluzione "abbastanza buona", che viene fornita "velocemente" è ciò che è richiesto.

Questa sezione introduce la terminologia di base richiesta per comprendere GA. Inoltre, in entrambi è presentata una struttura generica di GApseudo-code and graphical forms. Si consiglia al lettore di comprendere adeguatamente tutti i concetti introdotti in questa sezione e di tenerli a mente durante la lettura anche di altre sezioni di questo tutorial.

Terminologia di base

Prima di iniziare una discussione sugli algoritmi genetici, è essenziale avere familiarità con la terminologia di base che verrà utilizzata in questo tutorial.

Population- È un sottoinsieme di tutte le possibili soluzioni (codificate) al problema dato. La popolazione per un GA è analoga alla popolazione per gli esseri umani tranne per il fatto che al posto degli esseri umani, abbiamo soluzioni candidate che rappresentano gli esseri umani.
Chromosomes - Un cromosoma è una di queste soluzioni al problema dato.
Gene - Un gene è una posizione di un elemento di un cromosoma.
Allele - È il valore che un gene assume per un particolare cromosoma.

Genotype- Il genotipo è la popolazione nello spazio di calcolo. Nello spazio di calcolo, le soluzioni sono rappresentate in un modo che può essere facilmente compreso e manipolato utilizzando un sistema informatico.
Phenotype - Il fenotipo è la popolazione nello spazio delle soluzioni del mondo reale in cui le soluzioni sono rappresentate in un modo in cui sono rappresentate nelle situazioni del mondo reale.
Decoding and Encoding - Per problemi semplici, il file phenotype and genotypegli spazi sono gli stessi. Tuttavia, nella maggior parte dei casi, gli spazi del fenotipo e del genotipo sono diversi. La decodifica è un processo di trasformazione di una soluzione dal genotipo allo spazio fenotipo, mentre la codifica è un processo di trasformazione dal fenotipo allo spazio genotipo. La decodifica dovrebbe essere veloce poiché viene eseguita ripetutamente in un GA durante il calcolo del valore di fitness.

Ad esempio, considera il problema dello zaino 0/1. Lo spazio Fenotipo è costituito da soluzioni che contengono solo i numeri di articolo degli articoli da prelevare.

Tuttavia, nello spazio genotipo può essere rappresentato come una stringa binaria di lunghezza n (dove n è il numero di elementi). UN0 at position x lo rappresenta x^thl'elemento viene scelto mentre un 1 rappresenta il contrario. Questo è un caso in cui gli spazi del genotipo e del fenotipo sono diversi.

Fitness Function- Una funzione fitness definita semplicemente è una funzione che prende la soluzione come input e produce l'idoneità della soluzione come output. In alcuni casi, la funzione fitness e la funzione obiettivo possono essere le stesse, mentre in altri potrebbero essere diverse in base al problema.
Genetic Operators- Questi alterano la composizione genetica della prole. Questi includono crossover, mutazione, selezione, ecc.

Struttura basilare

La struttura di base di un GA è la seguente:

Iniziamo con una popolazione iniziale (che può essere generata casualmente o seminata da altre euristiche), selezionare i genitori da questa popolazione per l'accoppiamento. Applicare operatori di crossover e di mutazione sui genitori per generare nuovi discendenti. E alla fine questi discendenti sostituiscono gli individui esistenti nella popolazione e il processo si ripete. In questo modo gli algoritmi genetici cercano effettivamente di imitare in una certa misura l'evoluzione umana.

Ciascuno dei passaggi seguenti viene trattato in un capitolo separato più avanti in questo tutorial.

Uno pseudo-codice generalizzato per un GA è spiegato nel seguente programma:

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best

Una delle decisioni più importanti da prendere durante l'implementazione di un algoritmo genetico è decidere la rappresentazione che useremo per rappresentare le nostre soluzioni. È stato osservato che una rappresentazione impropria può portare a scarse prestazioni dell'AG.

Pertanto, la scelta di una corretta rappresentazione, avere una corretta definizione delle mappature tra il fenotipo e gli spazi genotipici è essenziale per il successo di un GA.

In questa sezione, presentiamo alcune delle rappresentazioni più comunemente utilizzate per gli algoritmi genetici. Tuttavia, la rappresentazione è altamente specifica per il problema e il lettore potrebbe scoprire che un'altra rappresentazione o un mix delle rappresentazioni qui menzionate potrebbe adattarsi meglio al suo problema.

Rappresentazione binaria

Questa è una delle rappresentazioni più semplici e più utilizzate nelle GA. In questo tipo di rappresentazione il genotipo è costituito da stringhe di bit.

Per alcuni problemi quando lo spazio della soluzione è costituito da variabili decisionali booleane - sì o no, la rappresentazione binaria è naturale. Prendiamo ad esempio il problema dello zaino 0/1. Se ci sono n elementi, possiamo rappresentare una soluzione con una stringa binaria di n elementi, dove l' elemento x- ^esimo indica se l'elemento x è selezionato (1) o meno (0).

Per altri problemi, in particolare quelli che si occupano di numeri, possiamo rappresentare i numeri con la loro rappresentazione binaria. Il problema con questo tipo di codifica è che bit diversi hanno un significato diverso e quindi gli operatori di mutazione e crossover possono avere conseguenze indesiderate. Questo può essere risolto in una certa misura utilizzandoGray Coding, poiché un cambiamento in un bit non ha un effetto massiccio sulla soluzione.

Rappresentazione di valore reale

Per i problemi in cui vogliamo definire i geni utilizzando variabili continue piuttosto che discrete, la rappresentazione a valore reale è la più naturale. La precisione di questi numeri in virgola mobile o con valore reale è tuttavia limitata al computer.

Rappresentazione intera

Per i geni a valori discreti, non possiamo sempre limitare lo spazio della soluzione a "sì" o "no" binario. Ad esempio, se vogliamo codificare le quattro distanze: Nord, Sud, Est e Ovest, possiamo codificarle come{0,1,2,3}. In questi casi, è auspicabile la rappresentazione di interi.

Rappresentazione di permutazione

In molti problemi, la soluzione è rappresentata da un ordine di elementi. In questi casi la rappresentazione della permutazione è la più adatta.

Un classico esempio di questa rappresentazione è il problema del venditore ambulante (TSP). In questo il venditore deve fare un giro di tutte le città, visitando ogni città esattamente una volta e tornando alla città di partenza. La distanza totale del tour deve essere ridotta al minimo. La soluzione a questo TSP è naturalmente un ordinamento o una permutazione di tutte le città e quindi l'uso di una rappresentazione di permutazione ha senso per questo problema.

La popolazione è un sottoinsieme di soluzioni nella generazione attuale. Può anche essere definito come un insieme di cromosomi. Ci sono molte cose da tenere a mente quando si ha a che fare con la popolazione GA:

La diversità della popolazione dovrebbe essere mantenuta altrimenti potrebbe portare a una convergenza prematura.
La dimensione della popolazione non dovrebbe essere mantenuta molto grande in quanto può causare un rallentamento di un GA, mentre una popolazione più piccola potrebbe non essere sufficiente per un buon pool di accoppiamento. Pertanto, una dimensione ottimale della popolazione deve essere decisa per tentativi ed errori.

La popolazione è generalmente definita come una matrice bidimensionale di - size population, size x, chromosome size.

Inizializzazione della popolazione

Esistono due metodi principali per inizializzare una popolazione in un GA. Sono -

Random Initialization - Popolare la popolazione iniziale con soluzioni completamente casuali.
Heuristic initialization - Popolare la popolazione iniziale utilizzando un'euristica nota per il problema.

È stato osservato che l'intera popolazione non dovrebbe essere inizializzata utilizzando un'euristica, in quanto può far sì che la popolazione abbia soluzioni simili e una diversità molto ridotta. È stato osservato sperimentalmente che le soluzioni casuali sono quelle che portano la popolazione all'ottimalità. Pertanto, con l'inizializzazione euristica, seminiamo la popolazione con un paio di buone soluzioni, riempiendo il resto con soluzioni casuali piuttosto che riempire l'intera popolazione con soluzioni basate su euristiche.

È stato anche osservato che l'inizializzazione euristica in alcuni casi influisce solo sull'idoneità iniziale della popolazione, ma alla fine è la diversità delle soluzioni che porta all'ottimalità.

Modelli di popolazione

Esistono due modelli di popolazione ampiamente utilizzati:

Stato stazionario

Nello stato stazionario GA, generiamo uno o due discendenti in ogni iterazione e sostituiscono uno o due individui dalla popolazione. Un GA a stato stazionario è anche noto comeIncremental GA.

Generazionale

In un modello generazionale, generiamo "n" discendenti, dove n è la dimensione della popolazione, e l'intera popolazione è sostituita dalla nuova alla fine dell'iterazione.

La funzione fitness definita semplicemente è una funzione che richiede a candidate solution to the problem as input and produces as output quanto “si adatta” al nostro quanto “buona” è la soluzione rispetto al problema in esame.

Il calcolo del valore di fitness viene eseguito ripetutamente in un GA e quindi dovrebbe essere sufficientemente veloce. Un calcolo lento del valore di fitness può influire negativamente su un GA e renderlo eccezionalmente lento.

Nella maggior parte dei casi la funzione fitness e la funzione obiettivo sono le stesse dell'obiettivo è massimizzare o minimizzare la funzione obiettivo data. Tuttavia, per problemi più complessi con più obiettivi e vincoli, un fileAlgorithm Designer potrebbe scegliere di avere una funzione fitness diversa.

Una funzione fitness dovrebbe possedere le seguenti caratteristiche:

La funzione fitness dovrebbe essere sufficientemente veloce per essere calcolata.
Deve misurare quantitativamente quanto è adatta una data soluzione o quanto individui possono essere prodotti dalla soluzione data.

In alcuni casi, il calcolo diretto della funzione fitness potrebbe non essere possibile a causa delle complessità intrinseche del problema in questione. In questi casi, eseguiamo l'approssimazione della forma fisica in base alle nostre esigenze.

L'immagine seguente mostra il calcolo della forma fisica per una soluzione dello zaino 0/1. Si tratta di una semplice funzione fitness che si limita a sommare i valori di profitto degli articoli prelevati (che hanno un 1), scansionando gli elementi da sinistra a destra fino a riempire lo zaino.

La selezione dei genitori è il processo di selezione dei genitori che si accoppiano e si ricombinano per creare discendenti per la generazione successiva. La selezione dei genitori è molto cruciale per il tasso di convergenza dell'AG, poiché i buoni genitori guidano le persone verso soluzioni migliori e più adatte.

Tuttavia, è necessario prestare attenzione per evitare che una soluzione estremamente adatta si impossessi dell'intera popolazione in poche generazioni, poiché ciò porta a soluzioni vicine l'una all'altra nello spazio delle soluzioni, con conseguente perdita di diversità. Maintaining good diversitynella popolazione è estremamente cruciale per il successo di un GA. Questo assorbimento dell'intera popolazione da parte di una soluzione estremamente adatta è noto comepremature convergence ed è una condizione indesiderabile in un GA.

Selezione proporzionata del fitness

La selezione proporzionale del fitness è uno dei modi più popolari di selezione dei genitori. In questo ogni individuo può diventare genitore con una probabilità proporzionale alla sua forma fisica. Pertanto, gli individui più in forma hanno maggiori possibilità di accoppiarsi e propagare le loro caratteristiche alla generazione successiva. Pertanto, una tale strategia di selezione applica una pressione selettiva agli individui più in forma nella popolazione, evolvendo individui migliori nel tempo.

Considera una ruota circolare. La ruota è divisa inn pies, dove n è il numero di individui nella popolazione. Ogni individuo riceve una porzione del cerchio che è proporzionale al suo valore di fitness.

Sono possibili due implementazioni della selezione proporzionale alla forma fisica:

Selezione della ruota della roulette

Nella selezione della ruota della roulette, la ruota circolare è divisa come descritto in precedenza. Si sceglie un punto fisso sulla circonferenza della ruota come mostrato e la ruota viene ruotata. La regione della ruota che si trova davanti al punto fisso viene scelta come genitore. Per il secondo genitore, viene ripetuto lo stesso processo.

È chiaro che un individuo più in forma ha una maggiore torta sulla ruota e quindi una maggiore possibilità di atterrare davanti al punto fisso quando la ruota viene ruotata. Pertanto, la probabilità di scegliere un individuo dipende direttamente dalla sua forma fisica.

Per quanto riguarda l'implementazione, utilizziamo i seguenti passaggi:

Calcola S = la somma di una finezza.
Genera un numero casuale compreso tra 0 e S.
Partendo dalla parte superiore della popolazione, continuare ad aggiungere le finezze alla somma parziale P, fino a P <S.
L'individuo per il quale P supera S è l'individuo scelto.

Campionamento stocastico universale (SUS)

Stochastic Universal Sampling è abbastanza simile alla selezione della ruota della roulette, tuttavia invece di avere un solo punto fisso, abbiamo più punti fissi come mostrato nell'immagine seguente. Pertanto, tutti i genitori vengono scelti in un solo giro della ruota. Inoltre, una tale configurazione incoraggia le persone altamente in forma a essere scelte almeno una volta.

È da notare che i metodi di selezione proporzionati all'idoneità non funzionano nei casi in cui l'idoneità può assumere un valore negativo.

Selezione del torneo

Nella selezione dei tornei K-Way, selezioniamo K individui dalla popolazione a caso e selezioniamo i migliori tra questi per diventare genitori. Lo stesso processo viene ripetuto per la selezione del genitore successivo. La selezione del torneo è anche estremamente popolare nella letteratura in quanto può funzionare anche con valori di fitness negativi.

Selezione del rango

La selezione del grado funziona anche con valori di fitness negativi e viene utilizzata principalmente quando gli individui nella popolazione hanno valori di fitness molto vicini (questo accade di solito alla fine della corsa). Ciò porta ogni individuo ad avere una quota quasi uguale della torta (come nel caso della selezione proporzionata all'idoneità) come mostrato nell'immagine seguente e quindi ogni individuo, indipendentemente da quanto in forma l'uno rispetto all'altro, ha approssimativamente la stessa probabilità di essere selezionato come genitore. Questo a sua volta porta a una perdita nella pressione di selezione verso individui più in forma, costringendo l'AG a fare scelte povere dei genitori in tali situazioni.

In questo, rimuoviamo il concetto di valore di fitness durante la selezione di un genitore. Tuttavia, ogni individuo nella popolazione è classificato in base alla propria forma fisica. La selezione dei genitori dipende dal grado di ogni individuo e non dalla forma fisica. Gli individui di grado superiore sono preferiti di più rispetto a quelli di grado inferiore.

Cromosoma	Valore fitness	Rango
UN	8.1	1
B	8.0	4
C	8.05	2
D	7.95	6
E	8.02	3
F	7.99	5

Selezione casuale

In questa strategia selezioniamo casualmente i genitori dalla popolazione esistente. Non c'è pressione di selezione verso individui più in forma e quindi questa strategia viene solitamente evitata.

In questo capitolo discuteremo di cosa sia un operatore crossover insieme ai suoi altri moduli, i loro usi e vantaggi.

Introduzione a Crossover

L'operatore di crossover è analogo alla riproduzione e al crossover biologico. In questo viene selezionato più di un genitore e una o più discendenti vengono prodotte utilizzando il materiale genetico dei genitori. Il crossover viene solitamente applicato in un GA con un'alta probabilità -p_c .

Operatori di crossover

In questa sezione discuteremo alcuni degli operatori di crossover più comunemente usati. È da notare che questi operatori di crossover sono molto generici e GA Designer potrebbe scegliere di implementare anche un operatore di crossover specifico per il problema.

Crossover a un punto

In questo crossover a un punto, viene selezionato un punto di crossover casuale e le code dei suoi due genitori vengono scambiate per ottenere nuovi discendenti.

Crossover multipunto

Il crossover a più punti è una generalizzazione del crossover a un punto in cui i segmenti alternati vengono scambiati per ottenere nuove molle.

Crossover uniforme

In un crossover uniforme, non dividiamo il cromosoma in segmenti, piuttosto trattiamo ciascun gene separatamente. In questo, essenzialmente lanciamo una moneta per ogni cromosoma per decidere se sarà incluso o meno nella prole. Possiamo anche polarizzare la moneta su un genitore, per avere più materiale genetico nel bambino da quel genitore.

Ricombinazione aritmetica intera

Questo è comunemente usato per rappresentazioni di numeri interi e funziona prendendo la media ponderata dei due genitori utilizzando le seguenti formule:

Child1 = α.x + (1-α) .y
Bambino2 = α.x + (1-α) .y

Ovviamente, se α = 0,5, allora entrambi i figli saranno identici come mostrato nell'immagine seguente.

Davis 'Order Crossover (OX1)

OX1 viene utilizzato per crossover basati su permutazioni con l'intenzione di trasmettere informazioni sull'ordinamento relativo alle derivazioni. Funziona come segue:

Crea due punti di crossover casuali nel genitore e copia il segmento tra di loro dal primo genitore alla prima prole.
Ora, partendo dal secondo punto di incrocio nel secondo genitore, copia i numeri inutilizzati rimanenti dal secondo genitore al primo figlio, avvolgendo l'elenco.
Ripeti per il secondo figlio con il ruolo del genitore invertito.

Esistono molti altri crossover come Partially Mapped Crossover (PMX), Order based crossover (OX2), Shuffle Crossover, Ring Crossover, ecc.

Introduzione alla mutazione

In termini semplici, la mutazione può essere definita come un piccolo aggiustamento casuale nel cromosoma, per ottenere una nuova soluzione. Viene utilizzato per mantenere e introdurre la diversità nella popolazione genetica e di solito viene applicato con una bassa probabilità -p_m. Se la probabilità è molto alta, il GA viene ridotto a una ricerca casuale.

La mutazione è la parte dell'AG che è correlata all '“esplorazione” dello spazio di ricerca. È stato osservato che la mutazione è essenziale per la convergenza del GA mentre il crossover non lo è.

Operatori di mutazione

In questa sezione vengono descritti alcuni degli operatori di mutazione più comunemente utilizzati. Come gli operatori di crossover, questo non è un elenco esaustivo e il progettista di GA potrebbe trovare più utile una combinazione di questi approcci o un operatore di mutazione specifico del problema.

Bit Flip Mutation

In questa mutazione di capovolgimento di bit, selezioniamo uno o più bit casuali e li invertiamo. Viene utilizzato per GA con codifica binaria.

Ripristino casuale

Il ripristino casuale è un'estensione del capovolgimento di bit per la rappresentazione intera. In questo, un valore casuale dall'insieme di valori consentiti viene assegnato a un gene scelto a caso.

Scambia mutazione

Nella mutazione di scambio, selezioniamo due posizioni sul cromosoma a caso e scambiamo i valori. Questo è comune nelle codifiche basate sulla permutazione.

Mutazione Scramble

La mutazione Scramble è anche popolare con le rappresentazioni di permutazione. In questo, dall'intero cromosoma, viene scelto un sottoinsieme di geni ei loro valori vengono codificati o mescolati in modo casuale.

Mutazione di inversione

Nella mutazione inversa, selezioniamo un sottoinsieme di geni come nella mutazione scramble, ma invece di mescolare il sottoinsieme, semplicemente invertiamo l'intera stringa nel sottoinsieme.

La politica di selezione dei sopravvissuti determina quali individui devono essere cacciati e quali devono essere mantenuti nella generazione successiva. È fondamentale in quanto dovrebbe garantire che gli individui più in forma non siano espulsi dalla popolazione, mentre allo stesso tempo dovrebbe essere mantenuta la diversità nella popolazione.

Alcuni GA impiegano Elitism. In termini semplici, significa che l'attuale membro più in forma della popolazione viene sempre propagato alla generazione successiva. Pertanto, in nessuna circostanza il membro più adatto della popolazione attuale può essere sostituito.

La politica più semplice è quella di cacciare membri casuali dalla popolazione, ma un tale approccio ha spesso problemi di convergenza, pertanto le seguenti strategie sono ampiamente utilizzate.

Selezione basata sull'età

Nella selezione basata sull'età, non abbiamo la nozione di forma fisica. Si basa sulla premessa che ogni individuo è ammesso nella popolazione per una generazione finita in cui è autorizzato a riprodursi, dopodiché viene espulso dalla popolazione, non importa quanto sia buona la sua forma fisica.

Ad esempio, nel seguente esempio, l'età è il numero di generazioni per le quali l'individuo è stato nella popolazione. I membri più anziani della popolazione, cioè P4 e P7, vengono espulsi dalla popolazione e le età degli altri membri vengono incrementate di uno.

Selezione basata sul fitness

In questa selezione basata sul fitness, i bambini tendono a sostituire gli individui meno in forma nella popolazione. La selezione degli individui meno idonei può essere effettuata utilizzando una variazione di una qualsiasi delle politiche di selezione descritte in precedenza: selezione del torneo, selezione proporzionata alla forma fisica, ecc.

Ad esempio, nell'immagine seguente, i bambini sostituiscono gli individui meno in forma P1 e P10 della popolazione. È da notare che poiché P1 e P9 hanno lo stesso valore di fitness, la decisione di rimuovere quale individuo dalla popolazione è arbitraria.

La condizione di conclusione di un algoritmo genetico è importante per determinare quando terminerà una corsa GA. È stato osservato che inizialmente il GA progredisce molto velocemente con soluzioni migliori che arrivano ogni poche iterazioni, ma questo tende a saturare nelle fasi successive in cui i miglioramenti sono molto piccoli. Di solito vogliamo una condizione di terminazione tale che la nostra soluzione sia vicina all'ottimale, alla fine della corsa.

Di solito, manteniamo una delle seguenti condizioni di risoluzione:

Quando non c'è stato alcun miglioramento nella popolazione per le iterazioni X.
Quando raggiungiamo un numero assoluto di generazioni.
Quando il valore della funzione obiettivo ha raggiunto un certo valore predefinito.

Ad esempio, in un algoritmo genetico teniamo un contatore che tiene traccia delle generazioni per le quali non c'è stato alcun miglioramento nella popolazione. Inizialmente, impostiamo questo contatore su zero. Ogni volta che non generiamo discendenti migliori degli individui della popolazione, incrementiamo il contatore.

Tuttavia, se l'idoneità di una qualsiasi delle molle è migliore, azzeriamo il contatore. L'algoritmo termina quando il contatore raggiunge un valore predeterminato.

Come altri parametri di un GA, anche la condizione di terminazione è altamente specifica per il problema e il progettista di GA dovrebbe provare varie opzioni per vedere quale si adatta meglio al suo particolare problema.

Fino ad ora in questo tutorial, tutto ciò che abbiamo discusso corrisponde al modello di evoluzione darwiniano: selezione naturale e variazione genetica attraverso la ricombinazione e la mutazione. In natura, solo le informazioni contenute nel genotipo dell'individuo possono essere trasmesse alla generazione successiva. Questo è l'approccio che abbiamo seguito finora nel tutorial.

Tuttavia, altri modelli di adattamento a vita - Lamarckian Model e Baldwinian Modelesistono anche. È da notare che qualunque sia il modello migliore, è aperto al dibattito ei risultati ottenuti dai ricercatori mostrano che la scelta dell'adattamento per tutta la vita è altamente specifica per il problema.

Spesso ibridiamo un GA con la ricerca locale, come in Memetic Algorithms. In questi casi, si potrebbe scegliere di andare con il modello Lamarckiano o Baldwiniano per decidere cosa fare con gli individui generati dopo la ricerca locale.

Modello Lamarckian

Il modello lamarckiano afferma essenzialmente che i tratti che un individuo acquisisce durante la sua vita possono essere trasmessi alla sua prole. Prende il nome dal biologo francese Jean-Baptiste Lamarck.

Anche se, la biologia naturale ha completamente ignorato il lamarckismo poiché tutti sappiamo che possono essere trasmesse solo le informazioni nel genotipo. Tuttavia, dal punto di vista del calcolo, è stato dimostrato che l'adozione del modello Lamarckiano dà buoni risultati per alcuni dei problemi.

Nel modello lamarckiano, un operatore di ricerca locale esamina il vicinato (acquisendo nuovi tratti) e, se viene trovato un cromosoma migliore, diventa la prole.

Modello Baldwin

Il modello Baldwin è un'idea intermedia che prende il nome da James Mark Baldwin (1896). Nel modello Baldwin, i cromosomi possono codificare una tendenza all'apprendimento di comportamenti benefici. Ciò significa che, a differenza del modello Lamarckiano, non trasmettiamo i tratti acquisiti alla generazione successiva, né ignoriamo completamente i tratti acquisiti come nel Modello Darwiniano.

Il modello Baldwin si trova nel mezzo di questi due estremi, in cui la tendenza di un individuo ad acquisire determinati tratti è codificata piuttosto che i tratti stessi.

In questo modello baldwiniano, un operatore di ricerca locale esamina il vicinato (acquisendo nuovi tratti) e, se viene trovato un cromosoma migliore, assegna solo l'idoneità migliorata al cromosoma e non modifica il cromosoma stesso. Il cambiamento di fitness significa la capacità dei cromosomi di “acquisire il tratto”, anche se non viene trasmesso direttamente alle generazioni future.

Le GA sono di natura molto generale e applicarle a qualsiasi problema di ottimizzazione non darebbe buoni risultati. In questa sezione, descriviamo alcuni punti che potrebbero aiutare e assistere un progettista di GA o un implementatore di GA nel loro lavoro.

Introdurre la conoscenza del dominio specifica del problema

È stato osservato che la conoscenza del dominio più specifica per il problema che incorporiamo nell'AG; i migliori valori oggettivi che otteniamo. L'aggiunta di informazioni specifiche sul problema può essere eseguita utilizzando il crossover specifico del problema o operatori di mutazione, rappresentazioni personalizzate, ecc.

L'immagine seguente mostra la visione di Michalewicz (1990) dell'EA -

Ridurre l'affollamento

L'affollamento si verifica quando un cromosoma altamente in forma riesce a riprodursi molto e in poche generazioni l'intera popolazione è piena di soluzioni simili con una forma fisica simile. Ciò riduce la diversità che è un elemento cruciale per garantire il successo di una GA. Esistono numerosi modi per limitare l'affollamento. Alcuni di loro sono -

Mutation per introdurre la diversità.
Passaggio a rank selection e tournament selection che hanno una pressione di selezione maggiore rispetto alla selezione proporzionata alla forma fisica per individui con forma fisica simile.
Fitness Sharing - In questo la forma fisica di un individuo è ridotta se la popolazione contiene già individui simili.

La randomizzazione aiuta!

È stato osservato sperimentalmente che le migliori soluzioni sono guidate da cromosomi randomizzati poiché conferiscono diversità alla popolazione. L'implementatore GA dovrebbe fare attenzione a mantenere una quantità sufficiente di randomizzazione e diversità nella popolazione per i migliori risultati.

Ibridazione di GA con la ricerca locale

La ricerca locale si riferisce al controllo delle soluzioni nelle vicinanze di una data soluzione per cercare valori oggettivi migliori.

A volte può essere utile ibridare GA con la ricerca locale. L'immagine seguente mostra i vari luoghi in cui è possibile introdurre la ricerca locale in un GA.

Variazione di parametri e tecniche

Negli algoritmi genetici, non esiste una "taglia unica" o una formula magica che funzioni per tutti i problemi. Anche dopo che l'AG iniziale è pronto, ci vuole molto tempo e impegno per giocare con parametri come la dimensione della popolazione, la mutazione e la probabilità di crossover ecc. Per trovare quelli che soddisfano il problema particolare.

In questa sezione vengono presentati alcuni argomenti avanzati in Algoritmi genetici. Un lettore che cerca solo un'introduzione alle GA può scegliere di saltare questa sezione.

Problemi di ottimizzazione vincolata

I problemi di ottimizzazione vincolata sono quei problemi di ottimizzazione in cui dobbiamo massimizzare o minimizzare un dato valore di funzione obiettivo che è soggetto a determinati vincoli. Pertanto, non tutti i risultati nello spazio della soluzione sono fattibili e lo spazio della soluzione contiene regioni ammissibili come mostrato nell'immagine seguente.

In un tale scenario, gli operatori di crossover e di mutazione potrebbero darci soluzioni che sono irrealizzabili. Pertanto, meccanismi aggiuntivi devono essere impiegati nel GA quando si tratta di problemi di ottimizzazione vincolati.

Alcuni dei metodi più comuni sono:

Utilizzando penalty functions che riduce l'idoneità delle soluzioni non fattibili, preferibilmente in modo che l'idoneità sia ridotta proporzionalmente al numero di vincoli violati o alla distanza dalla regione ammissibile.
Utilizzando repair functions che prendono una soluzione irrealizzabile e la modificano in modo da soddisfare i vincoli violati.
Not allowing infeasible solutions entrare nella popolazione.
Usare un special representation or decoder functions che garantisce la fattibilità delle soluzioni.

Background teorico di base

In questa sezione, discuteremo del teorema Schema e NFL insieme all'ipotesi del blocco di costruzione.

Teorema dello schema

I ricercatori hanno cercato di capire la matematica alla base del funzionamento degli algoritmi genetici e lo Schema Theorem di Holland è un passo in quella direzione. Nel corso dell'anno sono stati apportati vari miglioramenti e suggerimenti al Teorema dello schema per renderlo più generale.

In questa sezione, non approfondiamo la matematica del Teorema dello schema, piuttosto cerchiamo di sviluppare una comprensione di base di cosa sia il Teorema dello schema. La terminologia di base da conoscere è la seguente:

UN Schemaè un "modello". Formalmente, è una stringa sull'alfabeto = {0,1, *},

dove * è non importa e può assumere qualsiasi valore.

Pertanto, * 10 * 1 potrebbe significare 01001, 01011, 11001 o 11011

Dal punto di vista geometrico, uno schema è un iperpiano nello spazio di ricerca della soluzione.
Order di uno schema è il numero di posizioni fisse specificate in un gene.

Defining length è la distanza tra i due simboli fissi più lontani nel gene.

Il teorema dello schema afferma che questo schema con fitness superiore alla media, lunghezza di definizione corta e ordine inferiore ha maggiori probabilità di sopravvivere al crossover e alla mutazione.

Ipotesi dei mattoni

I blocchi predefiniti sono schemi di lunghezza bassa definizione di ordine basso con la forma fisica media sopra indicata. L'ipotesi di elementi costitutivi afferma che tali elementi costitutivi servono come base per il successo e l'adattamento delle GAs man mano che progredisce identificando e ricombinando successivamente tali "building blocks".

Teorema di No Free Lunch (NFL)

Wolpert e Mac già nel 1997 hanno pubblicato un articolo intitolato "No Free Lunch Theorems for Optimization". In sostanza afferma che se facciamo una media sullo spazio di tutti i possibili problemi, tutti gli algoritmi della scatola nera non rivisitati mostreranno le stesse prestazioni.

Significa che più comprendiamo un problema, il nostro GA diventa più specifico per il problema e offre prestazioni migliori, ma compensa ciò eseguendo male per altri problemi.

Apprendimento automatico basato su GA

Gli algoritmi genetici trovano applicazione anche nell'apprendimento automatico. Classifier systems sono una forma di genetics-based machine learning(GBML) che vengono frequentemente utilizzati nel campo del machine learning. I metodi GBML sono un approccio di nicchia all'apprendimento automatico.

Esistono due categorie di sistemi GBML:

The Pittsburg Approach - In questo approccio, un cromosoma codifica una soluzione, quindi l'idoneità viene assegnata alle soluzioni.
The Michigan Approach - una soluzione è tipicamente rappresentata da molti cromosomi e quindi l'idoneità è assegnata a soluzioni parziali.

Va tenuto presente che nei sistemi GBML sono presenti anche problemi standard come crossover, mutazione, Lamarckian o Darwiniano, ecc.

Gli algoritmi genetici sono utilizzati principalmente in problemi di ottimizzazione di vario genere, ma sono spesso utilizzati anche in altre aree di applicazione.

In questa sezione, elenchiamo alcune delle aree in cui vengono utilizzati frequentemente gli algoritmi genetici. Questi sono -

Optimization- Gli algoritmi genetici sono più comunemente usati nei problemi di ottimizzazione in cui dobbiamo massimizzare o minimizzare un dato valore di funzione obiettivo sotto un dato insieme di vincoli. L'approccio per risolvere i problemi di ottimizzazione è stato evidenziato durante il tutorial.
Economics - Le GA sono anche utilizzate per caratterizzare vari modelli economici come il modello della ragnatela, la risoluzione dell'equilibrio della teoria dei giochi, il prezzo degli asset, ecc.
Neural Networks - Gli GA sono utilizzati anche per addestrare le reti neurali, in particolare le reti neurali ricorrenti.
Parallelization - Le GA hanno anche ottime capacità parallele e si dimostrano mezzi molto efficaci per risolvere determinati problemi e forniscono anche una buona area di ricerca.
Image Processing - I GA vengono utilizzati per varie attività di elaborazione di immagini digitali (DIP) e per la corrispondenza dei pixel densi.
Vehicle routing problems - Con più finestre temporali morbide, più depositi e una flotta eterogenea.
Scheduling applications - I GA vengono utilizzati anche per risolvere vari problemi di pianificazione, in particolare il problema della presentazione del tempo.
Machine Learning - come già discusso, l'apprendimento automatico basato sulla genetica (GBML) è un'area di nicchia nell'apprendimento automatico.
Robot Trajectory Generation - I GA sono stati utilizzati per pianificare il percorso che un braccio robotico prende spostandosi da un punto all'altro.
Parametric Design of Aircraft - Le GA sono state utilizzate per progettare velivoli variando i parametri e sviluppando soluzioni migliori.
DNA Analysis - Gli GA sono stati utilizzati per determinare la struttura del DNA utilizzando dati spettrometrici sul campione.
Multimodal Optimization - I GA sono ovviamente ottimi approcci per l'ottimizzazione multimodale in cui dobbiamo trovare molteplici soluzioni ottimali.
Traveling salesman problem and its applications - Le GA sono state utilizzate per risolvere il TSP, che è un noto problema combinatorio utilizzando nuove strategie di crossover e di impacchettamento.

È possibile fare riferimento ai seguenti libri per migliorare ulteriormente la conoscenza del lettore degli algoritmi genetici e del calcolo evolutivo in generale -

Algoritmi genetici nella ricerca, ottimizzazione e apprendimento automatico di David E. Goldberg.
Algoritmi genetici + Strutture dati = Programmi evolutivi di Zbigniew Michalewicz.
Algoritmi genetici pratici di Randy L. Haupt e Sue Ellen Haupt.
Ottimizzazione multi-obiettivo utilizzando algoritmi evolutivi di Kalyanmoy Deb.

Next page ↱