Introduzione

Gli algoritmi genetici (GA) sono metodi adattativi che possono essere usati per risolvere problemi di ricerca e ottimizzazione. Sono basati sui processi genetici degli organismi biologici. Dopo molte generazioni, le popolazioni si evolvono secondo i principi della selezione naturale e della sopravvivenza del migliore, come teorizzato per la prima volta da Charles Darwin nella sua opera "L'origine delle specie" . Imitando questi processi, gli algoritmi genetici sono in grado di evolvere soluzioni per problemi del mondo reale, se sono stati codificati opportunamente. Per esempio possono essere usati per disegnare ponti col massimo rapporto forza/peso o per determinare il disegno meno dispendioso per tagliare forme dalla stoffa. Possono anche essere usati per processi di controllo in linea, come una centrale chimica. I principi di base dei GA sono stati definiti per la prima volta da Holland: essi simulano quei processi che nelle popolazioni naturali sono essenziali per l'evoluzione. Quali processi esattamente siano essenziali o quali giochino un ruolo trascurabile (o nessuno) per l'evoluzione è un problema della ricerca, ma i principi di base sono chiari. In Natura, gli individui di una popolazioni competono uno con l'altro per risorse come cibo, acqua e territorio. Inoltre membri della stessa specie spesso competono per attrarre un compagno. Quegli individui che hanno più successo nella sopravvivenza e nella riproduzione avranno un numero relativamente grande di discendenti. Gli individui che si mostreranno essere meno adatti produrranno poca o forse nessuna prole. Questo significa che i geni degli individui più adattati (fit individuals) saranno trasmessi a un crescente numero di individui in ciascuna delle generazioni successive. La combinazione delle buone caratteristiche di diversi antenati possono a volte produrre una discendenza molto adattata (superfit), la cui qualità è superiore a quella di ciascun genitore. In questo modo le specie si evolvono e diventano sempre più adattate al loro ambiente. I GA usano una diretta analogia con il comportamento della natura. Lavorano con una popolazione di individui, ciascuno dei quali rappresenta una possibile soluzione del problema posto. A ogni individuo è associato un punteggio di adattamento "fitness score" a seconda di quanto sia buona la soluzione al problema. In natura è equivalente a stabilire quanto un individuo riesce a competere per le risorse. Gli individui migliori hanno la possibilità di riprodursi incrociandosi con altri individui della popolazione. Questo produce nuovi individui discendenti che condividono alcune caratteristiche di ciascun genitore. Gli individui meno adattati hanno meno probabilità di riprodursi e quindi si estinguono. Una intera nuova popolazione di possibili soluzioni è così prodotta dalla selezione degli individui migliori della generazione corrente che accoppiandosi tra loro producono un nuovo insieme di individui. Questa nuova generazione contiene una proporzione più alta delle caratteristiche possedute dagli individui buoni della precedente generazione. In questo modo dopo molte generazioni le buone caratteristiche vengono propagate a tutta la popolazione, essendo mischiate e scambiate con altre buone caratteristiche. Favorendo l'accoppiamento tra gli individui più adatti, vengono esplorate la aree più promettenti dello spazio di ricerca. Se il GA è stato costruito bene, la popolazione convergere a una soluzione ottima del problema. I GA non sono gli unici algoritmi che si basano su analogie con la natura. Le reti neurali sono basate sul comportamento dei neuroni nel cervello. Possono essere usate per una varietà di applicazioni: riconoscimento di un modello, machine learning, image processing e sistemi esperti. Le loro applicazioni spesso sono le stesse dei GA, inoltre i GA possono essere usati per disegnare reti neurali. La potenza degli Algoritmi Genetici viene dal fatto che hanno una tecnica robusta e possono essere usati con successo in molti campi, e in problemi che altri metodi diffici lmente riescono a risolvere. I GA non garantiscono di trovare una soluzione ottima per un problema, ma generalmente trovano una soluzione sufficientemente buona e in tempi sufficientemente rapidi. Dove esistono tecniche specializzate per risolvere partico lari problemi queste hanno spesso prestazioni migliori dei GA sia in termini di accuratezza che di velocità . Il terreno migliore dei GA sono dunque le aree dove non esistono tecniche specializzate. Dove esistono tecniche che funzionano bene, si possono avere miglioramenti "ibridizzandole" con i GA.