Capitolo 1 : Computazione evolutiva
Il termine "calcolo evolutivo" si riferisce sia a un'area dell'intelligenza artificiale e del soft computing nel campo dell'informatica che studia vari algoritmi di ottimizzazione, sia a una famiglia di algoritmi per l'ottimizzazione globale che si ispirano all'evoluzione biologica. Per parlare più tecnicamente, appartengono alla famiglia dei risolutori di problemi per tentativi ed errori basati sulla popolazione che hanno un sapore di ottimizzazione metaeuristica o stocastica.
Il processo di calcolo evolutivo inizia con la generazione di un pool preliminare di possibili soluzioni, che viene poi migliorato iterativamente. Al fine di sviluppare ogni nuova generazione, prima rimuoviamo le soluzioni meno desiderabili utilizzando un processo stocastico, e poi apportiamo piccoli aggiustamenti casuali. Nel linguaggio della biologia, una popolazione di potenziali soluzioni viene "mutata" dopo essere stata esposta alla selezione naturale (o anche alla selezione artificiale). Di conseguenza, la popolazione finirà per crescere in fitness, ovvero la funzione di fitness che l'algoritmo ha selezionato per rappresentare il fitness.
Come risultato della sua capacità di fornire soluzioni altamente ottimali in una varietà di contesti problematici, gli approcci di calcolo evolutivo stanno diventando sempre più importanti nel campo dell'informatica. Sono disponibili molte altre versioni ed estensioni, ognuna delle quali è adattata a una particolare famiglia di problemi o struttura dati. Nel campo della biologia evoluzionistica, il calcolo evoluzionistico viene utilizzato occasionalmente anche sotto forma di metodo sperimentale in-silico per indagare vari aspetti dei processi evolutivi generali.
L'idea di imitare i processi evolutivi per risolvere i problemi risale a un'epoca precedente all'invenzione dei computer e include esempi come la proposta di Alan Turing nel 1948 di una tecnica nota come ricerca genetica. L'obiettivo principale di Holland era quello di utilizzare algoritmi genetici per ricercare l'adattamento e capire come potesse essere riprodotto, in contrasto con le altre tecniche, che erano in gran parte focalizzate sulla ricerca di soluzioni ai problemi. Una tecnica di selezione artificiale è stata utilizzata per modificare le popolazioni di cromosomi, ognuno dei quali è stato rappresentato come stringhe di bit. Questa procedura ha selezionato alcuni bit 'alleli' inclusi all'interno della stringa di bit. Le interazioni tra cromosomi sono stati uno dei tanti approcci utilizzati per replicare la ricombinazione del DNA che avviene naturalmente tra vari tipi di animali. Gli algoritmi genetici di Holland monitoravano enormi popolazioni, mentre i sistemi precedenti potevano tracciare solo una singola creatura ottimale alla volta (facendo competere la prole con i loro genitori) (avendo molti organismi in competizione ogni generazione).
Negli anni '90 è emerso un nuovo metodo di calcolo evolutivo che in seguito sarebbe stato noto come programmazione genetica. John Koza è stata una delle tante persone che hanno sostenuto questa linea di pensiero. All'interno di questo tipo di algoritmo, la cosa che si stava evolvendo era in realtà un programma che era stato creato in un linguaggio di programmazione di alto livello (c'erano stati alcuni tentativi precedenti già nel 1958 di utilizzare il codice macchina, ma avevano avuto scarso successo). I programmi utilizzati da Koza erano chiamati Lisp S-expressions, e si possono concettualizzare queste espressioni come alberi costituiti da sottoespressioni. Questo modello consente ai programmi di scambiare sottoalberi, il che è simile alla miscelazione di materiale genetico. Il grado in cui un programma è in grado di svolgere con successo un compito predeterminato gli fa guadagnare un punteggio, e quel punteggio viene poi impiegato in un processo di selezione artificiale. Il concetto di programmazione genetica è stato utilizzato con successo in una serie di aree, tra cui la pianificazione, l'induzione della sequenza e il riconoscimento dei modelli.
Sebbene i loro contributi non rientrassero necessariamente in uno dei principali rami storici dell'argomento, un gran numero di persone in più ha avuto un ruolo nello sviluppo dell'informatica evoluzionistica nel corso della sua storia. Nils Aall Barricelli sviluppò le prime simulazioni al computer dell'evoluzione nel 1953, utilizzando algoritmi evolutivi e approcci di vita artificiale. I primi risultati di queste simulazioni furono pubblicati nel 1954.
La maggior parte delle volte, i metodi di ottimizzazione metaeuristica sono coinvolti nelle strategie di calcolo evolutivo. Il dominio può essere suddiviso nelle seguenti categorie:
Modellazione basata su agenti
Ottimizzazione delle colonie di formiche
Sistema immunitario artificiale
Vita artificiale (vedi anche organismo digitale)
Algoritmi culturali
Evoluzione differenziale
Sviluppo o evoluzione in doppia fase
Le tecniche per la stima delle distribuzioni
Algoritmi evolutivi
Programmazione evolutiva
Strategia di evoluzione
Programmazione dell'espressione genica
Algoritmo genetico
Programmazione genetica
Evoluzione grammaticale
Modello di evoluzione apprendibile
Sistemi di classificazione dell'apprendimento
Algoritmi memetici
Neuroevoluzione
Ottimizzazione dello sciame di particelle
Auto-organizzazione, compreso l'uso di mappe auto-organizzanti, nonché l'apprendimento competitivo
Intelligenza dello sciame
Il campo del calcolo evolutivo contiene un sottocampo noto come algoritmi evolutivi. Gli algoritmi evoluzionistici sono un sottocampo del calcolo evolutivo perché, in generale, coinvolgono solo tecniche che implementano meccanismi evolutivi ispirati all'evoluzione biologica. Questi meccanismi evolutivi includono la riproduzione, la mutazione, la ricombinazione, la selezione naturale e la sopravvivenza del più adatto. Le soluzioni candidate al problema dell'ottimizzazione agiscono come membri di una popolazione e la funzione di costo è responsabile della determinazione dell'ambiente in cui le soluzioni "vivono" (vedi anche funzione di fitness). Dopo aver ripetutamente assoggettato la popolazione ai suddetti operatori, l'evoluzione della popolazione avrà infine luogo.
Ci sono due fattori primari all'opera in questo processo che insieme forniscono le basi dei sistemi evolutivi: Ricombinazione La varietà essenziale e, quindi, la capacità di originalità sono prodotte attraverso la mutazione e il crossover, mentre la selezione funziona come forza trainante per migliorare la qualità genetica.
La stocasticità può essere vista in molte sfaccettature di un processo evolutivo come questo. I bit di informazione che sono stati alterati a seguito della ricombinazione e della mutazione sono selezionati in modo casuale. D'altra parte, gli operatori di selezione possono essere deterministici o stocastici a seconda della situazione. Nel secondo scenario, le persone che hanno una forma fisica più elevata hanno una maggiore probabilità di essere scelte rispetto alle persone che hanno una forma fisica inferiore, ma nella maggior parte dei casi, anche gli individui meno in forma hanno la possibilità di diventare genitori o di vivere.
La teoria dei sistemi dinamici è collegata agli algoritmi genetici perché vengono utilizzati per fare previsioni sugli stati futuri di un sistema. Queste previsioni possono essere utilizzate per modellare i sistemi biologici e la biologia dei sistemi. Gli algoritmi genetici forniscono metodologie di modellazione. Questo è solo un metodo drammatico per richiamare l'attenzione sulla natura ordinata, ben controllata e altamente organizzata dello sviluppo in biologia; Tuttavia, potrebbe essere ingannevole.
Nonostante ciò, l'applicazione degli algoritmi e dell'informatica, in particolare della teoria computazionale, è anch'essa cruciale per il processo di comprensione dell'evoluzione stessa; Questo è vero anche quando si ignora la somiglianza con i sistemi dinamici.
Il valore di questa teoria è che riconosce che non esiste una regolamentazione centrale dello sviluppo; piuttosto, la crescita degli organismi è la conseguenza delle interazioni locali sia all'interno che tra le cellule. I concetti che sembrano portare a una somiglianza apparentemente stretta tra i processi che avvengono all'interno delle cellule e il funzionamento a basso livello degli attuali computer sono quelli che ci sembrano essere le teorie più promettenti riguardo ai parallelismi programma-sviluppo.
In questo confronto è incluso anche il parallelo tra l'informatica e l'interazione tra i sistemi di ereditarietà e la struttura biologica, che si ritiene riveli una delle sfide più serie nella comprensione degli inizi della vita.
Automi evolutivi.
L'elenco dei ricercatori attualmente in attività è intrinsecamente fluido e non intende essere esaustivo. Nel 2007 è stato pubblicato uno studio che analizza la rete della comunità.
Kalyanmoy Deb
Kenneth A De Jong
Peter J. Fleming
David B. Fogel
Stephanie Forrest
David E. Goldberg
John Henry Holland
Theo Jansen
John Koza
Zbigniew Michalewicz
Melanie Mitchell
Peter Nordin
Riccardo Poli
Ingo Rechenberg
Hans-Paul Schwefel
Di seguito è riportato un elenco delle conferenze più importanti nel campo del calcolo evolutivo:
La Conferenza sull'Informatica e il Calcolo Genetico ed Evolutivo dell'Association for Computing Machinery (GECCO), Convention on Evolutionary Computation tenuta dall'IEEE (CEC), EvoStar è un'organizzazione ombrello che comprende quattro...
