Algoritmo genetico: differenze tra le versioni

Versione delle 20:39, 30 lug 2015

Versione attuale delle 10:17, 8 mag 2024

(41 versioni intermedie di 23 utenti non mostrate)

Riga 1:

{{tmp|Algoritmo}}

Un '''algoritmo genetico''' è un [[algoritmo]] [[euristico]] utilizzato per tentare di risolvere problemi di [[Ottimizzazione (matematica)|ottimizzazione]] per i quali non si conoscono altri algoritmi efficienti di [[Teoria della complessità computazionale|complessità]] lineare o polinomiale. L'aggettivo "genetico", ispirato al principio della [[selezione naturale]] ed [[evoluzione]] biologica teorizzato nel 1859 da [[Charles Darwin]]. L'aggettivo "genetico", deriva dal fatto che, al pari ildel modello evolutivo darwiniano che trova spiegazioni nella branca della [[biologia]] detta [[genetica]] e dal fatto che, gli algoritmi genetici attuano dei meccanismi concettualmente simili a quelli dei processi [[biochimica|biochimici]] scoperti da questa scienza.

In sintesi si può dire che gli algoritmi genetici consistono in algoritmi che permettono di valutare delle soluzioni di partenza 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 [[Teoria della complessità computazionale|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<ref>{{en}}[http://www.informatik.uni-osnabrueck.de/papers_pdf/xplorer_report_volker.pdf Progettazione di disposizioni LVSI attraverso algoritmi genetici. Studio di Volker Schnecke ed Oliver Vornberger dell'Università di Osnabruck]</ref>, la biologia<ref>{{en}}[http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2143927/ Presentazione di un algoritmo per lo studio del ripiegamento proteico di M.J. Bayley, J. Jones, G. William e M.P. Williamson, NCBI USA]</ref> e l'economia<ref>{{en}}[http://static.wingedleopard.net/lucas/projects/urchine/paper.pdf Gli algoritmi genetici nell'economia di J.L. Reddinger, Montana State University]</ref>.

== Storia ==

Line 10 ⟶ 7:

La vera prima creazione di un algoritmo genetico è tuttavia storicamente attribuita a [[John Henry Holland]] che, nel 1975, nel libro ''Adaptation 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 cosiddetto [[teorema 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 con [[numero reale|numeri reali]] dimostrando anche che una tale codifica è preferibile nel caso di problemi continui d'ottimizzazione{{senza fonte}}.

Enormi contributi si devono anche a [[John Koza]] che nel 1992 inventò la [[programmazione genetica]] ossia l'applicazione degli algoritmi genetici alla produzione di software in grado di evolvere e diventando capace di svolgere compiti che in origine non era in grado di svolgere.

Nel 1995 [[Stewart Wilson]] re-inventò i [[sistemi a classificatori]] dell'intelligenza artificiale ri-denominandoli come [[XCS]] 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.

== Descrizione ==

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 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]]<ref>{{Cita testo|lingua=en}}[|url=http://www.informatik.uni-osnabrueck.de/papers_pdf/xplorer_report_volker.pdf |titolo=Progettazione di disposizioni LVSI attraverso algoritmi genetici. Studio di Volker Schnecke ed Oliver Vornberger dell'Università di Osnabruck]}}</ref>, la biologia<ref>{{Cita testo|lingua=en}}[http|url=https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2143927/ |titolo=Presentazione di un algoritmo per lo studio del ripiegamento proteico di M.J. Bayley, J. Jones, G. William e M.P. Williamson, NCBI USA]}}</ref> e l'[[economia]]<ref>{{Cita testo|lingua=en}}[|url=http://static.wingedleopard.net/lucas/projects/urchine/paper.pdf |titolo=Gli algoritmi genetici nell'economia di J.L. Reddinger, Montana State University]|urlarchivio=https://web.archive.org/web/20160305091654/http://static.wingedleopard.net/lucas/projects/urchine/paper.pdf }}</ref>.

== Funzionamento ==

Line 32 ⟶ 34:

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 tecnichetecnica dell'"elitarismo" e con quella delle [[mutazione genetica|mutazioni]] casuali. La prima consiste in un ulteriore passo precedente al punto ''3'' che copia nelle nuove popolazioni anche gli individui migliori della popolazione precedente, la seconda invece successiva al punto ''4'' introduce nelle soluzioni individuate delle occasionali mutazioni casuali in modo da permettere l'uscita da eventuali ricadute in ottimi locali.

=== La codifica ===

Come accennato, le soluzioni al problema considerato, siano questeesse quelle casuali di partenza o quelle derivate da evoluzione, devono essere codificate con qualche tecnica.

Le codifiche più diffuse sono:

Line 49 ⟶ 51:

=== La logica di selezione ===

A causa di complessi fenomeni di interazione non lineare ([[epistaticità]]), non è dato per scontato né che da due soluzioni promettenti ne nasca una terza più promettente né che da due soluzioni con valori di fitness basso ne 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 Igli individui appartenenti alla popolazione.

**B. Scegliere l'individuo migliore e impostare la sua probabilità di scelta a <math>p</math>.

**C. Scegliere il secondo individuo migliore e impostare la probabilità di scelta a <math>p*(1-p)</math>.

**D. Scegliere il terzo individuo migliore e impostare la sua probabilità di scelta a <math>p*(1-p)^2</math>.

**...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:

Line 64 ⟶ 66:

=== Il crossover ===

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 un [[operatore (matematica)|operatore]] stabilito inizialmente, alcune parti dei geni delle soluzioni candidate all'evoluzione vengono mescolate per ricavare nuove soluzioni.

In base ad un [[operatore]] stabilito inizialmente, alcune parti dei geni delle soluzioni candidate all'evoluzione vengono mescolate per ricavare nuove soluzioni.

Gli operatori più comunemente utilizzati sono:

[[File:Computational.science.Genetic.algorithm.Crossover.One.Point.svg|thumbnailthumb|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.

[[File:Computational.science.Genetic.algorithm.Crossover.Two.Point.svg|thumbnailthumb|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.

[[File:Computational.science.Genetic.algorithm.Crossover.Uniform.Crossover.svg|thumbnailthumb|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. [[Algebra di Boole#XOR|XOR]] o un [[Algebra di Boole#AND|AND]]).

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 <math>p_c</math>.

Riga 87:

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 algoritmoobiettivo, 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 un [[Ottimo paretiano|fronte di Pareto]]. La diversità sta nel fatto che ora esistono due o più funzioni fitness da valutare.

==Esempi didattici==

Riga 106:

==Progetti reali con algoritmi genetici==

*[[Acovea]]: [[software]] [[open source]] studiato per trovare il profilo migliore delle opzioni di ottimizzazione del [[compilatore]] [[gNU Compiler Collection|gcc]] che rappresenta un problema di elevata complessità<ref>{{Cita testo|lingua=en}}[|url=http://freecode.com/projects/acovea |titolo=Codice e informazioni del programma Acovea]|urlarchivio=https://web.archive.org/web/20121013001940/http://freecode.com/projects/acovea }}</ref>.

== Note ==

Riga 114:

* John Holland, "Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence", Bradford Books, 1992 ISBN 0262581116

* D.B. Fogel, ''Evolutionary computation: toward a new philosophy of machine intelligence'', IEEE Press, NewYork, 1995 ISBN 0-7803-5379-X

* J.R. Koza, ''Genetic programming: on the programming of computers by means of natural selection'', MIT Press, Cambridge, MA, 1992 ISBN 0-262-11170-5

* Poli, R., Langdon, W. B., McPhee, N. F. (2008), ''A Field Guide to Genetic Programming'', Lulu.com, disponibile gratuitamente via internet ISBN 978-1-4092-0073-4

* Alden H. Wright, Genetic Algorithms for Real Parameter Optimization, 1991 [http://citeseer.ist.psu.edu/wright91genetic.html]

* {{en}}cita [web|url=http://www.econ.iastate.edu/tesfatsi/holland.GAIntro.htm |titolo=''Genetic Algorithms'' di J. Holland]|lingua=en}}

* {{en}}cita [web|url=http://www.it-weise.de/projects/book.pdf |titolo=Global Optimization Algorithms - Theory and Application]|lingua=en|accesso=27 maggio 2008|urlarchivio=https://web.archive.org/web/20080911075107/http://www.it-weise.de/projects/book.pdf|urlmorto=sì}}

== Voci correlate ==

* [[AlgoritmiAlgoritmo evolutivievolutivo]]

* [[Programmazione evolutiva]]

* [[Programmazione genetica]]

Riga 129:

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* {{en}} [http://www.obitko.com/tutorials/genetic-algorithms/example-function-minimum.php Esempio animato e interattivo di un algoritmo genetico (richiede java).]

* {{FOLDOC|genetic algorithm|genetic algorithm}}

* {{en}} [http://www.obitko.com/tutorials/genetic-algorithms/tsp-example.php Esempio animato e interattivo di un algoritmo genetico per la risoluzione del problema del commesso viaggiatore (richiede java).]

* {{en}}cita [web|url=http://www.obitko.com/tutorials/genetic-algorithms/example-function-minimum.php |titolo=Esempio animato e interattivo di un algoritmo genetico (richiede java).]|lingua=en}}

* {{en}} [http://www.geneoverload.com/ Gioco multigiocatore di strategia online basato su Algoritmici Genetici (richiede registrazione).]

* {{en}}cita [web|url=http://www.obitko.com/tutorials/genetic-algorithms/tsp-example.php |titolo=Esempio animato e interattivo di un algoritmo genetico per la risoluzione del problema del commesso viaggiatore (richiede java).]|lingua=en}}

* [http://www.e-nuts.net/it/algoritmi-genetici Braccio meccanico ad apprendimento genetico] Simulazione fisica di un braccio meccanico con autoapprendimento basato su algoritmi genetici (richiede download del programma).

* {{en}}cita [web|url=http://www.geneoverload.com/ |titolo=Gioco multigiocatore di strategia online basato su Algoritmici Genetici (richiede registrazione).]|lingua=en|accesso=9 ottobre 2011|urlarchivio=https://web.archive.org/web/20110925015119/http://www.geneoverload.com/|urlmorto=sì}}

* [{{cita testo|url=http://www.e-nuts.net/it/algoritmi-genetici |titolo=Braccio meccanico ad apprendimento genetico]|urlarchivio=https://web.archive.org/web/20070611132153/http://www.e-nuts.net/it/algoritmi-genetici }} Simulazione fisica di un braccio meccanico con autoapprendimento basato su algoritmi genetici (richiede download del programma).

{{Genetica}}

{{Apprendimento automatico}}

{{Portale|Biologia|matematica}}

{{Controllo di autorità}}

{{Portale|ingegneria|statistica|biologia|informatica}}

[[Categoria:Intelligenza artificiale]]

[[Categoria:Apprendimento automatico]]

[[Categoria:Algoritmi di ricerca|Genetico]]

[[Categoria:Matematica per la genetica]]