Algoritmi genetici - Fondamenti

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 fenotipico, 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