Rappresentazione del genotipo
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 mediante una stringa binaria di n elementi, dove l' elemento x- esimo indica se l'elemento x è scelto (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 di 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 ciascuna città esattamente una volta e tornare 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.
