You are here: Home > Linee di Ricerca > Metodi di sintesi ed ottimizzazione > Algoritmi Genetici

Algoritmi Genetici

Gli algoritmi genetici sono strumenti per risolvere problemi di ricerca e di ottimizzazione che seguono un procedimento euristico ispirato alla genetica e al principio della selezione naturale di Charles Darwin [2],[3]. Con questo procedimento, guidato dal principio della selezione naturale, si cerca di ricavare un insieme di individui che, con l’avanzare delle generazioni, migliori sempre più e permetta di trovare la soluzione ottima del problema o una sua approssimazione. Spesso ci si riferisce agli individui con il nome di cromosomi per via della loro struttura e delle operazioni con cui si possono modificare. Infatti, ogni soluzione viene descritta da un insieme di caratteristiche del tutto simili ai geni, sulle quali vengono utilizzati gli stessi operatori di mutazione e crossover presenti nella genetica per creare nuovi individui.
La struttura base di un algoritmo genetico prevede un ciclo che simula il processo evolutivo di una popolazione. Ogni ciclo rappresenta la vita di una generazione e al suo interno sono svolte le operazioni per generare una nuova popolazione formata da individui sempre migliori. Ogni GA agisce sul cromosoma ed ogni cromosoma è rappresentativo di un individuo della popolazione. Il cromosoma è a sua volta costituito da un insieme di geni, che costituiscono la codifica (binaria, reale, etc.) di tutti i parametri che si vogliono ottimizzare. Ogni gene rappresenta quindi un argomento della funzione, in genere multidimensionale, che caratterizza il problema e di cui si vuole calcolare il minimo o il massimo. Ogni cromosoma codifica una possibile soluzione del problema, mentre un numero predefinito di cromosomi, determina la dimensione della popolazione. Durante il processo di ottimizzazione la popolazione viene fatta evolvere ed indirizzata verso la soluzione ottima mediante un criterio di selezione regolato dalla funzione di fitness, il cui scopo è quello di dare una misura del grado di bontà di ogni singola soluzione. L'algoritmo genetico si sviluppa nelle seguenti fasi:

  • generazione casuale di una popolazione iniziale con un numero predeterminato di individui e calcolo del valore di fitness per ognuno di essi;
  • selezione degli individui migliori in base al valore di fitness e creazione di una nuova generazione attraverso l’operatore di cross-over e di mutazione. I nuovi individui sono generati da due genitori (cromosomi) della generazione precedente;
  • sostituzione, intera o parziale, della vecchia generazione con la nuova e calcolo dei valori di fitness da assegnare ai nuovi individui.

Se si raggiunge il criterio di terminazione, l’algoritmo si arresta e la soluzione ottima è rappresentata dal cromosoma il cui valore di fitness è il minore.