Definizioni e terminologia

Per esplicare la terminologia utilizzata nel formalizzare problemi con l'approccio genetico viene ora brevemente svolta la trattazione di un generico problema di ottimizzazione, cui può essere ricondotto quello relativo alla ricerca degli angoli ottimali per l'emulatore.

Il generico problema di ottimizzazione ha come obiettivo quello di determinare un $x_0\in X$ tale che $f(\cdot)$ sia massima in $x_0$ con $f\: : \: X \rightarrow R$ arbitraria funzione reale, cioè tale che $f(x_0)=max_{x \in X} f(x)$.

In pratica spesso non è possibile ottenere soluzioni globalmente ottime in senso stretto, come richiesto dalla relazione precedente, tuttavia una vasta classe di problemi può essere efficacemente risolta richiedendo solamente che la funzione di valutazione assuma per le soluzioni valori il più possibile prossimi al massimo.

Il dominio delle singole soluzioni indicato con $X$ è in generale uno spazio in n dimensioni; l'algoritmo genetico non lavora sull'effettiva soluzione ma su una sua versione codificata tipicamente in binario o in virgola mobile.

La versione codificata della generica soluzione si ottiene dalla funzione codifica

$$c\: : \: X \rightarrow S\; ,$$

dove con $S$ si indica lo spazio delle stringhe in binario o virgola mobile che descrivono le soluzioni

L'insieme delle possibili soluzioni, cioè l'insieme di tutti gli $x_i$ con $x_i \in X$ , prende il nome di popolazione, invece la funzione $f$, che assegna ad ogni membro della popolazione (individuo) la valutazione sulla sua attitudine a risolvere il problema in questione, viene chiamata funzione di fitness.

In questo senso il problema può essere riformulato in questi termini: determinare $x_0\in X$ tale che $f(c(x_0))$ sia quanto più prossimo possibile al massimo assoluto.

La struttura base algoritmo genetico può essere così riassunta [6] :

• Generazione di una popolazione iniziale $P_0$ di soluzioni come sottoinsieme di quelle possibili, ottenuta con campionamento casuale o con strategie dipendenti dal problema.
• Ciclo WHILE: finchè non si ragguinge la condizione di terminazione (che può essere fissata come numero di generazioni o come minima distanza dal massimo globale per la funzione fitness), si eseguono in sequenza:
  • selezione degli individui per l'incrocio;
  • generazione della coppia di figli e valutazione del loro fitness;
  • eventuale processo di mutazione casuale;
  • definizione della nuova popolazione.

Nel seguito si darà breve spiegazione delle procedure utilizzate:

• Selezione: procedura che seleziona gli individui da incrociare; chiaramente genitori con alto valore di fitness producono in genere figli altrettanto dotati, tuttavia talvolta l'incrocio di genitori poco performanti produce figli con fitness superiore alla media. Pertanto sono state sviluppate raffinate tecniche di selezione che permettono di applicare diverse strategie di selezione, dipendentemente dalle caratteristiche del problema affrontato.
• Cross Over (incrocio): metodo per fondere l'informazione genetica di due individui e generare altrettanti figli. Vengono utilizzati, con opportune occorrenze per generazione, diversi tipi di cross over sia semplici che multipli, e con differenti strategie di cesura dei genitori.
• Mutazione: l'operatore mutazione introduce deformazioni casuali nel patrimonio genetico di un generico individuo spesso scelto casualmente. Tale operazione serve a introdurre nuove soluzioni, preservando la diversità del materiale genetico della popolazione che altrimenti tenderebbe a convergere precocemente verso soluzioni spesso banali.

Gli algoritmi genetici presentano perculiarità che li rendono competitivi rispetto ai tradizionali metodi di ottimizzazione in quanto possono lavorare agevolmente su domini di soluzioni n-dimensionali, continui o discreti, inoltre l'informazione codificata rende computazionalmente rapido il calcolo ed efficace lo sfruttamento della memoria [11] .

Si sottilenea che l'algoritmo lavora su un sottoinsieme di soluzioni, in questo modo si può pervenire più facilmente a una soluzione prossima all'ottimo, scongiurando la convergenza verso massimi relativi e senza la necessità di sviluppare calcoli addizionali come le derivate.

Anche la terminologia utilizzata viene mutuata dall'ambito biologico-evoluzionistico; si parla infatti di popolazione per indicare il dominio delle possibili soluzioni, di soggetto per indicare una possibile soluzione, le cui specifiche attitudini sono contenute nei geni e cromosomi. Il singolo cromosoma contiene pertanto l'informazione sulla performance del soggetto rispetto a un ben determinato parametro.