Parte IV
Appendici
Appendice A
Introduzione sugli algoritmi
genetici
Un algoritmo genetico (GA) è un algoritmo euristico ispirato al principio della selezione naturale ed evoluzione biologica teorizzato nel 1859 da Charles Darwin.
L’aggettivo genetico deriva dal fatto che il modello evolutivo darwiniano trova spiegazioni nella branca della biologia detta genetica e dal fatto che gli algoritmi genetici attuano dei meccanismi concettualmente simili a quelli dei processi biochimici.
In sintesi si può dire che gli algoritmi genetici consistono in algoritmi che permettono di valutare delle soluzioni di partenza di un dato problema e che ricombinandole ed introducendo elementi di disordine sono in grado di crearne di nuove nel tentativo di convergere a soluzioni ottime.
Queste tecniche vengono di norma utilizzate per tentare di risolvere problemi di ottimizzazione per i quali non si conoscono altri algoritmi efficienti di complessità lineare o polinomiale.
Nonostante questo utilizzo, data la natura intrinseca di un algoritmo genetico, non vi è modo di sapere a priori se sarà effettivamente in grado di trovare una soluzione accettabile al problema considerato.
Gli algoritmi genetici rientrano nello studio dell’intelligenza artificiale e più in particolare nella branca della computazione evolutiva, vengono studiati e sviluppati all’interno del campo dell’intelligenza artificiale e delle tecniche di soft computing ma trovano applicazione in un’ampia varietà di problemi afferenti a diversi contesti quali l’elettronica, la biologia e l’economia.
In realtà, non è garantito che un GA trovi una soluzione ottima globale; un GA è in grado di trovare soluzioni buone in tempi ragionevoli.
Prima dell’effettiva spiegazione del funzionamento degli algoritmi genetici è necessa-rio premettere che questi ereditano e riadattano dalla biologia alcune terminologie che vengono preventivamente presentate per una successiva maggiore chiarezza espositiva, preso un problema, la cui soluzione è data da un set di variabili, nella risoluzione mediante algoritmi genetici possiamo individuare:
• Gene(Figura A.1): Il gene rappresenta una delle variabili da ottimizzare, essa è codificata mediante un vettore di bit (quindi il valore numerico della variabile viene convertito in valore binario), nel caso un cui la variabile sia un vettore o una matrice essa viene scomposta nelle sue componenti o elementi e ad ognuno viene assegnato un gene.
• Cromosoma(Figura A.1): Il cromosoma è l’insieme di tutti i geni che rappresen-tano una soluzione del problema.(Come in biologia, un cromosoma raccogli più geni insieme) esso è quindi codificato mediante un vettore di Bit la cui lunghezza è la somma delle lunghezze dei singoli geni. Ogni cromosoma quindi rappresenta un punto nello spazio di ricerca.
• Individuo(Figura A.1): Un individuo è l’espressione di un cromosoma.
• Popolazione(Figura A.1):Insieme di individui di cui ognuno di essi è una possibile soluzione al problema considerato.
• Funzione di Fitness: La fitness costituisce l’ambiente in cui le popolazioni vivono, è una funzione che dà un voto ad ogni singolo individuo, determinando quanto ognuno di essi sia vicino o lontano dalla soluzione desiderata. Per un problema di ottimizzazione la funzione di fitness può coincidere con la funzione obiettivo (o una sua trasformazione).
• Crossover: Esso è l’atto di riproduzione tra due individui di una data popolazione che da origine a due individui di una generazione successiva. I cromosomi di due individui di una data generazione vengono tagliati ad un’altezza casuale, che però è uguale per entrambi (Figura A.2) ogni cromosoma è quindi diviso in due spezzoni, lo spezzone A e lo spezzone B del cromosoma 1 (A1 B1) e lo spezzone A e B del cromosoma 2 (A2 B2), viene effettuato lo scambio degli spezzoni B tra i due cromosomi in modo che si generino due cromosomi completamente nuovi (A1 B2 , A2 B1) i cromosomi appena generati faranno parte della generazione
successiva (Figura A.2).
• Mutazione(Figura A.3): Come succede fisicamente in natura, i geni possono essere alterati attraverso influenze del mondo esterno, nel sistema degli algoritmi genetici la mutazione avviene cambiando il valore di un bit all’interno di un gene, passando da 1 a 0 o vicevarsa, la probabilità di tale evento è settata dall’operatore ma deve esssere comunque sotto una certa soglia, pena la divergenza della soluzione.
Figura A.1: Differenza tra Geni, Cromosomi, Popolazione/Individui
Un tipico algoritmo genetico, nel corso della sua esecuzione, provvede a fare evolvere delle soluzioni secondo il seguente schema di base:
Figura A.2: Operazione di crossover
Figura A.3: Operazione di mutazione
2. Generazione: Generazione casuale della prima popolazione di soluzioni (cromoso-mi di generazione 1 G1) tale generazione può essere totalmente casuale oppure partire da un valore un valore settato dall’utente, vengono caricati in maniera totalmente casuale i vettori cromosomi e di coneguenza creati in individui to-talmente casuali, la quantità di individui è un’altro importante parametro da settare a priori della ottimizzazione.
3. Valutazione Applicazione della funzione di fitness alla popolazione. dopo questa fase ogni individuo avrà un voto più alto più si avvicina al valore desiderato della funzione di fitness.
4. Selezione: Gli individui migliori sono selezionati per la riproduzione. Sono inseriti in una popolazione intermedia G1-2. Gli individui entrano nella popolazione di accoppiamento con una certa probabilità (probabilità di Crossover) tanto maggiore quanto è alto il loro voto rispetto alla fitness (principio della ruota fortuna truccata).
5. Crossover: Si applica l’operatore di crossover agli individui ne G1-2. Si ottiene una nuova popolazione intermedia G1-3.
6. Mutazione: l’operatore di mutazione è applicato con una certa probabilità (pro-babilità di mutazione) agli individui di G1-3. Viene prodotta una popolazione G1-4 che però ha un numero minore di individui rispetto a G1.
7. Selezione per rimpiazzamento e sopravvivenza: la nuova generazione G2 contiene gli individui della popolazione G1-4 ma deve poter includere anche altri individui per ritornare allo stesso numero di individui della generazione G1.
Sono possibili più algoritmi di selezione. Ad esempio, un sottoinsieme di individui di G1 che non sono stati selezionati per la riproduzione, oppure gli individui migliori di G1.
8. Creata la nuova popolazione completa (G2) la si riporta al punto 3 e il ciclo continua sino a che non si raggiunge la funzione obbiettivo o in numero massimo di generazioni imposte.
Il rimpiazzamento e la mutazione sono introdotti per evitare che alcune soluzioni ottime possano essere perse durante il ciclo di ottimizzazione, e per questo il rimpiazza-mento promuove i migliori individui della generazione G(i-1) alla generazione G(i), ma che al contempo bisogna garantire che l’algoritmo non sia forzato a bloccarsi all’interno di in ottimi locali particolarmente profondi che porterebbero a pensare che essi sono la soluzione ottima, per questo viene utilizzata la mutazione che permette di perturbare il sistema e portarlo alla ricerca del vero ottimo.
