Analisi teorica

In questo paragrafo si cercherà di spiegare teoricamente come funzionano gli algoritmi genetici, benchè una trattazione rigorosa risulti difficile e complessa dal punto di vista analitico; complessità che deriva dai meccanismi che costituiscono la struttura algoritmica stessa.

Per i tradizionali metodi di ottimizzazione deterministica, come il metodo del gradiente o il metodo di Newton, è naturale che la convergenza delle soluzioni verso l'ottimo sia sorretta e guidata da risultati teorici, che ne assicurano la convergenza stessa e ne specificano la velocità o l'ordine con cui si realizza. Nel caso dei metodi di ottimizzazione probabilistica il supporto teorico viene a mancare, in quanto il comportamento dell'algoritmo non è deterministico, pertanto non possono venir enunciati e dimostrati teroremi che ne descrivano il comportamento. Si possono tuttavia enunciare risultati riguardo la convergenza in media.

Nel caso degli algoritmi genetici, la convergenza verso la soluzione ottima non trova facilmente giustificazione teorica in quanto la transizione da una generazione a un'altra coinvolge nel caso più semplice tre operatori probabilistici, selezione, cross over e mutazione, che rendono la struttura esageratamente complicata sul piano teorico. Inoltre ogni operatore probabilistico citato può venir invocato dalla procedura con parametri di controllo diversi da iterazione a iterazione, influenzando in modo determinante il comportamento in convergenza.

Pertanto per gli algoritmi genetici non possono venir enunciati teoremi di convergenza in senso stretto, tuttavia si riportano risultati che dimostrano l'efficienza degli algortimi stessi in un ampia varietà di applicazioini, seppur non si possano considerare di validità generale.

Per comodità ci si riferirà a un generico algoritmo genetico di ottimizzazione, con una popolazione di $m$ individui codificati in stringhe di lunghezza $n$.

Definizione 5.1.1   Una stringa $H=(h_1, ... , h_n)$ definita sull'alfabeto $\mathcal{A}=\{ 0,1,* \}$ è chiamata schema di lunghezza $n$; ogni $h_i$ è un bit assegnato se $h_i \in \{0, 1 \}$, mentre è un bit libero se $h_i= \{ * \}$.

Definizione 5.1.2   Una stringa $S=(s_1, ... , s_n)$ di lunghezza $n$ definita sull'alfabeto $\{ 0,1 \}$, appartiene allo schema $H=(h_1, ... , h_n)$ se e solo se ogni bit assegnato dello schema coincide con il corrispondente nella stringa

$$\forall i \in \left\lbrace j \vert h_j \neq * \right\rbrace \: : \: s_i=h_i \;.$$ (5.1.1)

Definizione 5.1.3   Dato uno schema $H$ di lunghezza $n$, si definisce $\mathcal{O}(H)$, ordine dello schema $H$, come il numero di bit assegnati.

$$\mathcal{O}(H)=\vert\left\lbrace i \in \left\lbrace 1, ... , n\right\rbrace \vert h_i \neq *\right\rbrace \vert$$ (5.1.2)

Definizione 5.1.4   Dato uno schema $H$ di lunghezza $n$, si definisce $\delta (H)$, distanza dello schema $H$, come la distanza tra il primo e l'ultimo dei bit assegnati.

$$\delta(H)=max\left\lbrace i\vert h_i \neq * \right\rbrace - min\left\lbrace i\vert h_i \neq * \right\rbrace$$ (5.1.3)