Puoiaggiungere e riempire il template secondo leistruzioni e poi rimuovere questo avviso. Se non sei in grado di riempirlo in buona parte, non fare nulla; non inserire template vuoti.
Unalgoritmo genetico è unalgoritmoeuristico utilizzato per tentare di risolvere problemi diottimizzazione per i quali non si conoscono altri algoritmi efficienti dicomplessità lineare o polinomiale. L'aggettivo "genetico", ispirato al principio dellaselezione naturale edevoluzione biologica teorizzato nel 1859 daCharles Darwin, deriva dal fatto che, al pari del modello evolutivo darwiniano che trova spiegazioni nella branca dellabiologia dettagenetica, gli algoritmi genetici attuano dei meccanismi concettualmente simili a quelli dei processibiochimici scoperti da questa scienza.
La nascita degli algoritmi genetici trova origine dalle prime teorizzazioni diIngo Rechenberg che, per la prima volta, nel 1960, cominciò a parlare di "strategie evoluzionistiche" all'interno dell'informatica.
La vera prima creazione di un algoritmo genetico è tuttavia storicamente attribuita aJohn Henry Holland che, nel 1975, nel libroAdaptation in Natural and Artificial Systems pubblicò una serie di teorie e di tecniche tuttora di fondamentale importanza per lo studio e lo sviluppo della materia. Agli studi di Holland si deve infatti sia il teorema che assicura la convergenza degli algoritmi genetici verso soluzioni ottimali sia il cosiddettoteorema degli schemi, conosciuto anche come "teorema fondamentale degli algoritmi genetici"[senza fonte]. Quest'ultimo teorema fu originariamente pensato e dimostrato su ipotesi di codifica binaria ma nel 1991, Wright, l'ha estesa a casi di codifica connumeri reali dimostrando anche che una tale codifica è preferibile nel caso di problemi continui d'ottimizzazione[senza fonte].
Enormi contributi si devono anche aJohn Koza che nel 1992 inventò laprogrammazione genetica ossia l'applicazione degli algoritmi genetici alla produzione di software in grado di evolvere diventando capace di svolgere compiti che in origine non era in grado di svolgere.
Nel 1995Stewart Wilson re-inventò isistemi a classificatori dell'intelligenza artificiale ri-denominandoli comeXCS e rendendoli capaci di apprendere attraverso le tecniche degli algoritmi genetici mentre nel 1998 Herrera e Lozano presentarono un'ampia rassegna di operatori genetici. Gli operatori di Herrera e Lozano sono applicabili a soluzioni codificate mediante numeri reali ed hanno reso il campo dei numeri reali un'appropriata e consolidata forma di rappresentazione per gli algoritmi genetici in domini continui.
In sintesi gli algoritmi genetici consistono in algoritmi che permettono di valutare diverse soluzioni di partenza (come se fossero diversi individui biologici) e che ricombinandole (analogamente alla riproduzione biologica sessuata) ed introducendo elementi di disordine (analogamente alle mutazioni genetiche casuali) producono nuove soluzioni (nuovi individui) che vengono valutate scegliendo le migliori (selezione ambientale) nel tentativo di convergere verso soluzioni "di ottimo". Ognuna di queste fasi di ricombinazione e selezione si può chiamare generazione come quelle degli esseri viventi. Nonostante questo utilizzo nell'ambito dell'ottimizzazione, data la natura intrinsecamente casuale dell'algoritmo genetico, non vi è modo di sapere a priori se sarà effettivamente in grado di trovare una soluzione accettabile al problema considerato. Se si otterrà un soddisfacente risultato, non è detto che si capisca perché abbia funzionato, in quanto non è stato progettato da nessuno ma da una procedura casuale.
Gli algoritmi genetici rientrano nello studio dell'intelligenza artificiale e più in particolare nella branca dellacomputazione evolutiva, vengono studiati e sviluppati all'interno del campo dell'intelligenza artificiale e delle tecniche disoft computing, ma trovano applicazione in un'ampia varietà di problemi afferenti a diversi contesti quali l'elettronica[1], la biologia[2] e l'economia[3].
Prima dell'effettiva spiegazione del funzionamento degli algoritmi genetici, è necessario premettere che questi ereditano e riadattano dalla biologia alcune terminologie che vengono qui preventivamente presentate per una successiva maggiore chiarezza espositiva:
Cromosoma: una delle soluzioni ad un problema considerato. Generalmente è codificata con un vettore di bit o di caratteri.
Popolazione: insieme di soluzioni relative al problema considerato.
Gene: parte di un cromosoma. Generalmente consiste in una o più parti del vettore di bit o caratteri che codificano il cromosoma.
Fitness: grado di valutazione associato ad una soluzione. La valutazione avviene in base ad una funzione appositamente progettata dettafunzione di fitness.
Crossover: generazione di una nuova soluzione mescolando delle soluzioni esistenti.
Mutazione: alterazione casuale di una soluzione.
Un tipicoalgoritmo genetico, nel corso della sua esecuzione, provvede a fare evolvere delle soluzioni secondo il seguente schema di base:
Generazione casuale della prima popolazione di soluzioni (cromosomi).
Applicazione dellafunzione difitness alle soluzioni (cromosomi) appartenenti all'attuale popolazione.
Selezione delle soluzioni considerate migliori in base al risultato della funzione di fitness e della logica di selezione scelta.
Procedimento di crossover per generare delle soluzioni ibride a partire dalle soluzioni scelte al punto3.
Creazione di una nuova popolazione a partire dalle soluzioni identificate al punto4.
Riesecuzione della procedura a partire dal punto2 ed utilizzando la nuova popolazione creata al punto5.
L'iterazione dei passi presentati permette l'evoluzione verso una soluzione ottimizzata del problema considerato.
Poiché questo algoritmo di base soffre del fatto che alcune soluzioni ottime potrebbero essere perse durante il corso dell'evoluzione e del fatto che l'evoluzione potrebbe ricadere e stagnare in "ottimi locali" spesso viene integrato con la tecnica dell'"elitarismo" e con quella dellemutazioni casuali. La prima consiste in un ulteriore passo precedente al punto3 che copia nelle nuove popolazioni anche gli individui migliori della popolazione precedente, la seconda invece successiva al punto4 introduce nelle soluzioni individuate delle occasionali mutazioni casuali in modo da permettere l'uscita da eventuali ricadute in ottimi locali.
Come accennato, le soluzioni al problema considerato, siano esse quelle casuali di partenza o quelle derivate da evoluzione, devono essere codificate con qualche tecnica.
Le codifiche più diffuse sono:
Codifica vettoriale binaria: è la più diffusa, consiste in un vettore din campi binari dove i valori 1 o 0 identificano delle caratteristiche elementari della soluzione. I vantaggi di questa tecnica risiedono nel fatto di essere semplice da implementare e da gestire durante l'intera evoluzione. Gli svantaggi consistono nelle difficoltà intrinseche della conversione delle soluzioni in questa codifica e dalle scarse possibilità rappresentative.
Codifica vettoriale reale: come la codifica vettoriale binaria ma vengono utilizzati dei numeri reali. Il vantaggio è quello di introdurre una maggiore espressività e versatilità nella codifica, a scapito di un'aumentata complessità.
Codifica vettoriale diretta: consiste in una codifica vettoriale dove ogni campo contiene direttamente i valori relativi al problema. Il vantaggio è quello di una facile codifica, lo svantaggio risiede nella difficile gestione dell'algoritmo e nella difficile progettazione della funzione di fitness e dei processi di crossover e mutazione.
Codifica ad albero: Ogni cromosoma è unalbero di alcuni oggetti come ad esempio funzioni e comandi di un linguaggio di programmazione. In questo caso, per la sua particolare semantica e sintassi, viene spesso utilizzato il linguaggio di programmazioneLisp che semplifica notevolmente le operazioni di codifica.
All'interno della codifica vettoriale è giusto introdurre anche i concetti di "schema" e di "blocchi costruttori" strettamente legati poi alteorema degli schemi di Holland.
La funzione di fitness è quella che permette di associare ad ogni soluzione uno o più parametri legati al modo in cui quest'ultima risolve il problema considerato. Generalmente è associata alle prestazioni computazionali e quindi alle prestazioni temporali della soluzione.
A causa di complessi fenomeni di interazione non lineare (epistaticità), non è dato per scontato né che da due soluzioni promettenti nasca una terza più promettente né che da due soluzioni con valori di fitness basso venga generata una terza con valore di fitness più basso. Per ovviare a questi problemi, durante la scelta delle soluzioni candidate all'evoluzione, oltre che sul parametro ottenuto dalla funzione di fitness ci si basa anche su particolari tecniche di "selezione". Le più comuni sono:
Selezione a roulette: la probabilità che una soluzione venga scelta per farla evolvere è direttamente proporzionale al valore restituito dalla funzione di fitness. Questa tecnica presenta dei problemi nel caso in cui ci siano delle grosse differenze di valori perché le soluzioni peggiori verrebbero selezionate troppo raramente.
Selezione per categoria: simile alla selezione per roulette ma la valutazione è effettuata in maniera proporzionale alla somma del valore della funzione di fitness per ogni coppia possibile di soluzioni. Il problema presentato da questa tecnica di scelta è rappresentato dalla lentezza di convergenza nel caso in cui ci siano delle differenze troppo piccole tra coppie di soluzioni candidate.
Selezione a torneo: le soluzioni vengono raggruppate e si procede a valutarle con un algoritmo come quello presentato nelle righe successive.
A. Scegliere in maniera casuale gli individui appartenenti alla popolazione.
B. Scegliere l'individuo migliore e impostare la sua probabilità di scelta a.
C. Scegliere il secondo individuo migliore e impostare la probabilità di scelta a.
D. Scegliere il terzo individuo migliore e impostare la sua probabilità di scelta a.
...proseguire fino ad esaurire le soluzioni scelte.
Selezione di Boltzmann: le soluzioni vengono scelte con un grado di probabilità che, agli inizi dell'algoritmo, favorisce l'esplorazione e che poi tende a stabilizzarsi. I parametri utilizzati dalla selezione di Boltzmann sono:
Per semplicità, durante la spiegazione del crossover, si farà riferimento alle codifiche vettoriali ma il procedimento per le codifiche ad albero è simile ed invece che essere applicato ai campi dei vettori viene applicato ai nodi dell'albero. In base ad unoperatore stabilito inizialmente, alcune parti dei geni delle soluzioni candidate all'evoluzione vengono mescolate per ricavare nuove soluzioni.
Gli operatori più comunemente utilizzati sono:
Crossover ad un punto
Crossover ad un punto: consiste nel considerare due soluzioni adatte all'evoluzione e nel tagliare i loro vettori di codifica in un punto casuale o predefinito per ottenere due teste e due code. La prima nuova soluzione ottenuta sarà data dalla combinazione della testa della prima soluzione con la coda della seconda, mentre la seconda nuova soluzione sarà data dalla coda della prima soluzione con la testa della seconda.
Crossover a due punti
Crossover a due punti: consiste nel considerare due soluzioni adatte all'evoluzione e nel tagliare i loro vettori di codifica in due punti predefiniti o casuali al fine di ottenere una testa, una parte centrale ed una coda dalla prima e dalla seconda soluzione. La prima nuova soluzione sarà data dalla testa e della coda della prima soluzione e dalla parte centrale della seconda soluzione. La seconda nuova soluzione sarà data dalla parte centrale della prima soluzione e dalla testa e dalla coda della seconda soluzione.
Crossover uniforme
Crossover uniforme: consiste nello scambiare casualmente dei bit tra le soluzioni candidate all'evoluzione. Si segnala l'esistenza anche di crossover uniformi parziali ossia dei crossover uniformi dove lo scambio di bit è limitato ad una percentuale fissa o dinamica dei cromosomi candidati all'evoluzione.
Crossover aritmetico: consiste nell'utilizzare un'operazione aritmetica per creare la nuova soluzione. (es.XOR o unAND).
Non è detto che il crossover debba avvenire ad ogni iterazione dell'algoritmo genetico. Generalmente la frequenza di crossover è regolata da un apposito parametro comunemente denominato.
La mutazione consiste nella modifica pseudocasuale di alcune parti dei geni in base a coefficienti definiti inizialmente.Queste modifiche alle volte sono utilizzate per migliorare il valore della funzione di fitness per la soluzione in questione e altre volte sono utilizzate per ampliare lo spazio di ricerca ed attuare la tecnica dell'elitarismo per non far ricadere l'evoluzione in ottimi locali.La frequenza con cui deve avvenire una mutazione è generalmente regolata da un apposito parametro comunemente denominato.
Nel caso in cui si abbia più di un obiettivo da ottimizzare, è possibile utilizzare un algoritmo genetico multiobiettivo.
Sostanzialmente l'algoritmo funziona come quando va a perseguire un singolo obiettivo, quindi parte sempre da un certo numero di possibili soluzioni (la popolazione) e cerca di individuare, mediante diverse iterazioni, un certo numero di soluzioni ottimali, che si andranno a trovare su unfronte di Pareto. La diversità sta nel fatto che ora esistono due o più funzioni fitness da valutare.
Ilproblema dello zaino consiste nel riuscire ad inserire in uno zaino con una certa capienza più oggetti possibili prelevati da un elenco dato rispettando anche particolari vincoli di peso.La soluzione ottima consiste nel riuscire ad inserire nello zaino quanti più oggetti possibili senza superare i limiti di peso imposti.
Codifica: il metodo più semplice per codificare questo problema è quello di utilizzare dei vettori binari. Il vettore di una soluzione dovrebbe avere la lunghezza del numero totale degli oggetti disponibili e, per ogni campo, dovrebbe presentare un '1' o uno '0'. Uno dei due valori andrebbe ad identificare l'oggetto come presente nello zaino, l'altro come assente. Ovviamente le soluzioni dovrebbero essere formulate in maniera coerente col problema, non potrebbero essere inseriti oggetti per un peso superiore a quello ammesso o per uno spazio superiore a quello disponibile.
Fitness: la funzione di fitness dovrebbe essere progettata in maniera tale da tenere conto sia del numero di oggetti inseriti all'interno dello zaino sia del suo peso.
Selezione, crossover e mutazione: per la metodica di selezione, crossover e mutazione sarebbe opportuno valutare differenti possibilità e probabilità a seconda della dimensione del problema. Per un problema con uno zaino piccolo, una particolare metodica potrebbe rivelarsi efficace ma non è detto che lo sia anche per un problema con uno zaino molto grande e viceversa. Il crossover e la mutazione devono essere ovviamente predisposti per mantenere la coerenza del problema considerato. In questo caso ad esempio, non sarebbe accettabile un crossover o una mutazione che vanno ad inserire lo stesso oggetto due volte nella stessa soluzione.
Ilproblema del commesso viaggiatore consiste nel riuscire a visitare almeno una volta tutte le città presenti in un elenco, sfruttando al meglio i collegamenti tra queste e percorrendo meno strada possibile.
Codifica: probabilmente, il metodo più semplice per codificare questo problema è quello mediante l'utilizzo di vettori di interi. Il campo di un vettore associato ad un cromosoma andrebbe ad identificare in maniera univoca una delle città da visitare mentre il suo posizionamento andrebbe ad identificare l'ordine di visita. Ovviamente questa codifica deve rispettare dei vincoli legati alla natura del problema quali la presenza di una città almeno una volta in ogni cromosoma.
Fitness: la funzione di fitness dovrebbe valutare i cromosomi in base alla distanza da percorrere per attuare il percorso codificato.
Selezione, crossover e mutazione: per la metodica di selezione, crossover e mutazione sarebbe opportuno valutare differenti possibilità e probabilità a seconda della dimensione del problema. Per un problema di poche città, una particolare metodica potrebbe rivelarsi efficace ma non è detto che lo sia anche per un problema con molte città e viceversa. Il crossover e la mutazione devono essere ovviamente predisposti per mantenere la coerenza del problema considerato. In questo caso ad esempio, non sarebbe accettabile un crossover o una mutazione che vanno a rimuovere la visita di una città da una soluzione.
Acovea:softwareopen source studiato per trovare il profilo migliore delle opzioni di ottimizzazione delcompilatoregcc che rappresenta un problema di elevata complessità[4].
John Holland, "Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence", Bradford Books, 1992ISBN 0262581116
D.B. Fogel,Evolutionary computation: toward a new philosophy of machine intelligence, IEEE Press, NewYork, 1995ISBN 0-7803-5379-X
J.R. Koza,Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992ISBN 0-262-11170-5
Poli, R., Langdon, W. B., McPhee, N. F. (2008),A Field Guide to Genetic Programming, Lulu.com, disponibile gratuitamente via internetISBN 978-1-4092-0073-4
Alden H. Wright, Genetic Algorithms for Real Parameter Optimization, 1991[1]
A questa voce o sezione va aggiunto iltemplate sinottico{{Algoritmo}}
