
Un algoritmo genetico è un algoritmo euristico utilizzato per tentare di risolvere problemi di ottimizzazione per i quali non si conoscono altri algoritmi efficienti di complessità lineare o polinomiale. L'aggettivo "genetico", ispirato al principio della selezione naturale ed evoluzione biologica teorizzato nel 1859 da Charles Darwin, deriva dal fatto che, al pari del modello evolutivo darwiniano che trova spiegazioni nella branca della biologia detta genetica, gli algoritmi genetici attuano dei meccanismi concettualmente simili a quelli dei processi biochimici scoperti da questa scienza.
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, la biologia e l'economia.
La nascita degli algoritmi genetici trova origine dalle prime teorizzazioni di Ingo 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 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". 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 numeri reali dimostrando anche che una tale codifica è preferibile nel caso di problemi continui d'ottimizzazione.
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 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.
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:
Un tipico algoritmo genetico, nel corso della sua esecuzione, provvede a fare evolvere delle soluzioni secondo il seguente schema di base:
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 delle 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.
Come accennato le soluzioni al problema considerato, siano queste quelle casuali di partenza o quelle derivate da evoluzione, devono essere codificate con qualche tecnica.
Le codifiche più diffuse sono:
All'interno della codifica vettoriale è giusto introdurre anche i concetti di "schema" e di "blocchi costruttori" strettamente legati poi al teorema 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 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:
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 stabilito inizialmente, alcune parti dei geni delle soluzioni candidate all'evoluzione vengono mescolate per ricavare nuove soluzioni.
Gli operatori più comunemente utilizzati sono:
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 formula_9.
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 formula_10.
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 un fronte di Pareto. La diversità sta nel fatto che ora esistono due o più funzioni fitness da valutare.
In questa sezione verranno analizzati ed affrontati dei problemi didattici per mostrare come si applica un algoritmo genetico.
Il problema 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.
Il problema 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.


In statistica, il clustering o analisi dei gruppi (dal termine inglese "cluster analysis" introdotto da Robert Tryon nel 1939) è un insieme di tecniche di analisi multivariata dei dati volte alla selezione e raggruppamento di elementi omogenei in un insieme di dati. Le tecniche di "clustering" si basano su misure relative alla somiglianza tra gli elementi. In molti approcci questa similarità, o meglio, dissimilarità, è concepita in termini di distanza in uno spazio multidimensionale. La bontà delle analisi ottenute dagli algoritmi di "clustering" dipende molto dalla scelta della metrica, e quindi da come è calcolata la distanza. Gli algoritmi di "clustering" raggruppano gli elementi sulla base della loro distanza reciproca, e quindi l'appartenenza o meno ad un insieme dipende da quanto l'elemento preso in esame è distante dall'insieme stesso.
Le tecniche di "clustering" si possono basare principalmente su due "filosofie":
Esistono varie classificazioni delle tecniche di clustering comunemente utilizzate. Una prima categorizzazione dipende dalla possibilità che un elemento possa o meno essere assegnato a più cluster:
Un'altra suddivisione delle tecniche di clustering tiene conto del tipo di algoritmo utilizzato per dividere lo spazio:
Queste due suddivisioni sono del tutto trasversali, e molti algoritmi nati come "esclusivi" sono stati in seguito adattati nel caso "non-esclusivo" e viceversa.
Gli algoritmi di clustering di questa famiglia creano una partizione delle osservazioni minimizzando una certa funzione di costo:
dove formula_2 è il numero dei cluster, formula_3 è il formula_4-esimo cluster e formula_5 è la funzione di costo associata al singolo cluster. L'algoritmo più famoso appartenente a questa famiglia è il k-means, proposto da MacQueen nel 1967. Un altro algoritmo abbastanza conosciuto appartenente a questa classe è il Partitioning Around Medioid (PAM).
Le tecniche di clustering gerarchico non producono un partizionamento "flat" dei punti, ma una rappresentazione gerarchica ad albero. 
Questi algoritmi sono a loro volta suddivisi in due classi:
Una rappresentazione grafica del processo di clustering è fornita dal dendrogramma.
In entrambi i tipi di clustering gerarchico sono necessarie funzioni per selezionare la coppia di cluster da fondere ("agglomerativo"), oppure il cluster da dividere ("divisivo").
Nel primo caso, sono necessarie funzioni che misurino la "similarità" (o, indistintamente, la "distanza") tra due cluster, in modo da fondere quelli più simili. Le funzioni utilizzate nel caso agglomerativo sono:
Nei 4 casi precedenti, formula_10 indica una qualsiasi funzione distanza su uno spazio metrico.
Invece nel clustering divisivo è necessario individuare il cluster da suddividere in due sottogruppi. Per questa ragione sono necessarie funzioni che misurino la compattezza del cluster, la densità o la sparsità dei punti assegnati ad un cluster. Le funzioni normalmente utilizzate nel caso divisivo sono:
Nel "Clustering density-based", il raggruppamento avviene analizzando l'intorno di ogni punto dello spazio. In particolare, viene considerata la densità di punti in un intorno di raggio fissato.
Un esempio è il metodo di clustering Dbscan.
Algoritmi di clustering molto usati sono:
Il QT ("Quality Threshold") Clustering (Heyer et al., 1999) è un metodo alternativo di partizionare i dati, inventato per il clustering dei geni. Richiede più potenza di calcolo rispetto al "K"-Means, ma non richiede di specificare il numero di cluster "a priori", e restituisce sempre lo stesso risultato quando si ripete diverse volte.
L'algoritmo è:
La distanza tra un punto ed un gruppo di punti è calcolata usando il concatenamento completo, cioè come la massima distanza dal punto di ciascun membro del gruppo (vedi il "Clustering gerarchico agglomerativo" sulla distanza tra i cluster nella sezione clustering gerarchico).
