Computazione evolutiva

La computazione evolutiva è un sottocampo dell'intelligenza artificiale che consiste principalmente nell'ottimizzazione iterativa continua e combinatoria della soluzione di un problema. È nata durante gli anni sessanta guidata dall'idea di automatizzare la risoluzione di problemi.

La computazione evolutiva utilizza una progressione iterativa, ad esempio la crescita o lo sviluppo di una popolazione. La popolazione viene successivamente selezionata con una ricerca casuale guidata sfruttando processi paralleli per raggiungere l'obiettivo. Tali processi sono spesso ispirati ai meccanismi dell'evoluzione proposti da Charles Darwin. L'evoluzione può produrre processi altamente ottimizzati, ha dunque numerose applicazioni nell'ambito dell'informatica.

Storia

L'uso dei principi darwiniani per risolvere problemi in modo automatico risale agli anni Cinquanta. Prima degli anni Sessanta, questa idea era stata sviluppata in tre luoghi diversi in maniera non correlata.

La programmazione evolutiva fu introdotta da Lawrence J. Fogel negli Stati Uniti, mentre John Henry Holland definì il suo metodo un Algoritmo genetico. In Germania Ingo Rechenberg e Hans-Paul Schwefel introdussero le strategie evolutive. Queste aree si svilupparono in modo separato per circa quindici anni. All'inizio degli anni Novanta furono unificati, essendo considerati diversi rappresentanti di un'unica tecnologia, detta computazione evolutiva. Sempre all'inizio degli anni Novanta emerse una nuova corrente, che seguiva l'idea in generale: la programmazione genetica. Sin dagli anni Novanta, la computazione evolutiva è diventata essenzialmente computazione swarm-based, e gli algoritmi ispirati alla natura stanno diventando sempre più importanti.

Questi termini mostrano che il campo generale è definito con il termine computazione evolutiva, mentre la programmazione evolutiva, le strategie evolutive, gli algoritmi genetici e la programmazione genetica sono delle sotto aree.

Simulazioni di evoluzione utilizzando degli algoritmi evolutivi e la vita artificiale cominciarono con il lavoro di Nils Aall Barricelli negli anni Sessanta, sviluppato ed esteso poi da Alex Fraser, che pubblicò una serie di ricerche scientifiche sulla simulazione della selezione artificiale. L'evoluzione artificiale divenne un metodo di ottimizzazione riconosciuto grazie al lavoro di Ingo Rechenberg, che tra gli anni Sessanta e Settanta usò le strategie evolutive per risolvere problemi di natura ingegneristica molto complessi. Gli algoritmi genetici divennero popolari grazie agli scritti di John Henry Holland. Il crescente interesse accademico e il considerevole aumento del potere computazionale dei calcolatori portò allo sviluppo di applicazioni pratiche, tra cui l'evoluzione automatica dei programmi sui calcolatori. Gli algoritmi evolutivi sono ora usati per risolvere problemi multidimensionale in maniera più efficiente dei software prodotti da progettisti umani, e permettono anche di ottimizzare la progettazione di tali sistemi.

Tecniche

Le tecniche di computazione evolutiva impiegano soprattutto degli algoritmi meta-euristici di ottimizzazione matematica. In generale, il campo include:

• Ottimizzazione del formicaio (Ant colony optimization)
• Algoritmo dell'alveare artificiale (Artificial Bee Colony Algorithm)
• Sistema immunitario artificiale
• Vita artificiale (o anche organismo digitale)
• Algoritmi delle api (Bees algorithm)
• Algoritmi culturali (Cultural algorithm)
• Evoluzione differenziale (Differential evolution)
• algoritmi evolutivi
• Programmazione evolutiva
• Strategie evolutive
• Programmazione per espressione di geni (Gene expression programming)
• algoritmi genetici
• Programmazione genetica
• Ricerca dell'armonia (Harmony search)
• Modello evolutivo ad apprendimento(Learnable Evolution Model)
• Sistemi classificatori ad apprendimento(Learning classifier system)
• Particle Swarm Optimization
• auto-organizzazioni, come le mappe auto-organizzanti e il competitive learning
• Swarm intelligence

Algoritmi evolutivi

Gli algoritmi evolutivi sono un sottoinsieme della computazione evolutiva, poiché in genere impiegano solo tecniche che sfruttano meccanismi ispirati dall'evoluzione biologica, come la riproduzione, le mutazioni, la ricombinazione, la selezione naturale e la sopravvivenza del più forte. Le soluzioni candidate per l'ottimizzazione del problema rappresentano gli individui della popolazione, e la funzione di fitness determina l'ambiente in cui la soluzione "vive". L'evoluzione della popolazione si ottiene ripetendo in maniera iterata le operazioni descritte sopra.

Alla base del processo vi sono due elementi chiave: la ricombinazione e la mutazione, le quali creano la diversità necessaria e l'introduzione di nuovi elementi, mentre la selezione agisce come un fattore per migliorare la qualità degli individui in una popolazione.

Molti aspetti di tale processo evolutivo sono stocastici. Le informazioni modificate tramite ricombinazione e mutazione sono scelti raramente. Dall'altro lato, gli operatori di selezione possono essere sia stocastici che deterministici. Nel primo caso, gli individui con una funzione di fitness più elevata hanno maggiori possibilità di essere selezionati rispetto agli individui con una funzione di fitness più bassa, ma di solito anche gli individui più deboli hanno qualche possibilità di riprodursi e sopravvivere.

Nomi illustri nel campo della computazione evolutiva

• Thomas Baeck
• Wolfgang Banzhaf
• Kalyanmoy Deb
• Francesco Cadini
• Kenneth A De Jong
• Gusz Eiben
• Peter J. Fleming
• David E. Goldberg
• Emma Hart
• John Henry Holland
• John Koza
• Zbigniew Michalewicz
• Peter Nordin
• Riccardo Poli (professore)
• Ingo Rechenberg
• Marc Schoenauer
• Hans-Paul Schwefel
• Jim Smith
• Xin Yao

Bibliografia

• Th. Bäck, D.B. Fogel, and Z. Michalewicz (Editors), Handbook of Evolutionary Computation, 1997, ISBN 0750303921
• Th. Bäck and H.-P. Schwefel. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1):1–23, 1993.
• W. Banzhaf, P. Nordin, R.E. Keller, and F.D. Francone. Genetic Programming — An Introduction. Morgan Kaufmann, 1998.
• S. Cagnoni, et al., Real-World Applications of Evolutionary Computing, Springer-Verlag Lecture Notes in Computer Science, Berlin, 2000.
• R. Chiong, Th. Weise, Z. Michalewicz (Editors), Variants of Evolutionary Algorithms for Real-World Applications, Springer, 2012, ISBN 3642234232
• K. A. De Jong, Evolutionary computation: a unified approach. MIT Press, Cambridge MA, 2006
• A. E. Eiben and M. Schoenauer, Evolutionary computing, Information Processing Letters, 82(1): 1–6, 2002.
• A. E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, First edition, 2003, ISBN 3-540-40184-9,
• D. B. Fogel. Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. IEEE Press, Piscataway, NJ, 1995.
• L. J. Fogel, A. J. Owens, and M. J. Walsh. Artificial Intelligence through Simulated Evolution. New York: John Wiley, 1966.
• D. E. Goldberg. Genetic algorithms in search, optimization and machine learning. Addison Wesley, 1989.
• J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.
• P. Hingston, L. Barone, and Z. Michalewicz (Editors), Design by Evolution, Natural Computing Series, 2008, Springer, ISBN 3540741097
• J. R. Koza. Genetic Programming: On the Programming of Computers by means of Natural Evolution. MIT Press, Massachusetts, 1992.
• F.J. Lobo, C.F. Lima, Z. Michalewicz (Editors), Parameter Setting in Evolutionary Algorithms, Springer, 2010, ISBN 3642088929
• Z. Michalewicz, Genetic Algorithms + Data Structures - Evolution Programs, 1996, Springer, ISBN 3540606769
• Z. Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics, Springer, 2004, ISBN 978-3-540-22494-5
• I. Rechenberg. Evolutionstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Fromman-Hozlboog Verlag, Stuttgart, 1973. (DE)
• H.-P. Schwefel. Numerical Optimization of Computer Models. John Wiley & Sons, New-York, 1981. 1995 – 2nd edition.
• D. Simon. Evolutionary Optimization Algorithms Archiviato il 10 marzo 2014 in Internet Archive.. Wiley, 2013.

Voci correlate

• Programmazione evolutiva
• Computazione evolutiva interattiva
• Algoritmi evolutivi
• Algoritmi genetici
• Soft computing

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla computazione evolutiva

Collegamenti esterni

• (EN) evolutionary computing, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

Controllo di autorità	LCCN (EN) sh95003989 · J9U (EN, HE) 987007546715505171