Intelligenza artificiale - algoritmi evolutivi

Per  rappresentare  un  algoritmo  evolutivo  dobbiamo  codificare  le  soluzioni  o  in  modo  binario  o  attraverso  

numeri  reali.  La  popolazione  è  formata  dall’insieme  delle  soluzioni  candidate  codificate.  La  funzione  di  

fitness  indica  il  grado  di  precisione  di  ogni  soluzione  della  popolazione,  cioè  quanto  è  vicina  alla  solzuoine  

cercata.  Attraverso  degli  operatori,  chiamati  operatori  genetici  è  possibile  simulare  la  selezione,  

ricombinazione,  mutazione  e  sostituzione  dei  cromosomi  all’interno  della  popolazione  esistente.  

In  un  algoritmo  evolutivo  si  parte  da  una  popolazione  generata  casualmente,  la  quale  viene  sottoposta  alla  

funzione  di  fitness.  Ai  valori  restituiti  dalla  funzione  di  fitness  per  ogni  soluzione  candidata,  viene  applicato  

il  processo  di  selezione,  in  base  al  quale  vengono  scelte  le  soluzioni  che  più  si  avvicinano  alla  soluzione  

cercata.  Alle  soluzioni  sopravvissute  alla  selezione  viene  applicato  il  processo  di  ricombinazione,  in  base  al  

quale  vengono  scomposte  le  soluzioni  e  poi  ricombinate  in  base  a  criteri  prestabiliti.  Le  soluzioni  ora  

ricombinate  subiscono  il  processo  di  mutazione  in  base  al  quale  alcuni  termini  della  soluzione  vengono  

modificati  secondo  una  data  probabilità  di  mutazione.  Al  termine  della  mutazione  avviene  la  sostituzione  

della  popolazione  esistente,  che  può  avvenire  in  modo  totale  (cambio  generazionale)  o  secondo  politiche  di  

scelta  che  eliminano  le  soluzioni  peggiori  e  aggiungono  le  soluzioni  frutto  della  mutazione  alle  soluzioni  

migliori  (con  grado  di  fitness  più  alto)  già  esistenti.  

In  particolare  i  processi  di  selezione  e  ricombinazione  garantiscono  l’innovazione  delle  soluzioni,  e  i  processi  

di  selezione  e  mutazione  garantiscono  un  miglioramento  continuo.  L’innovazione  e  il  miglioramento  

continuo  delle  soluzioni  rappresentano  l’evoluzione  dell’algoritmo  verso  la  soluzione  ottima.  

2  –  Metodologie  

I  principali  algoritmi  evolutivi  sono  sostanzialmente  3:  

-­‐ Algoritmi  Genetici  

-­‐ Strategie  evolutive  

-­‐ Programmazione  evolutiva  

In  dettaglio  verranno  trattati  gli  algoritmi  genetici  

  Algoritmi  Genetici  

Gli  algoritmi  genetici  sono  un  modello  di  calcolo  che  si  ispira  alla  metafora  della  genetica  delle  popolazioni  

(Holland  1975  –Goldberg  1989).  

Non  si  possono  considerare  algoritmi  di  apprendimento  in  quanto  l’azione  svolta  da  questi  algoritmi  nel  

loro  funzionamento  è  principalmente  quella  di  individuare  il  massimo  di  una  funzione  data,  detta  funzione  

di  fitness.  

Larga  parte  delle  loro  applicazioni  sono  infatti  relative  all’ottimizzazione  di  funzioni,  discrete  o  continue  e  a  

problemi  di  ottimizzazione  combiantoria.  

Negli  algoritmi  genetici  il  processo  di  ricerca  della  soluzione  in  un  problema  di  ottimizzazione,  che  avviene  

tramite  un  particolare  bilanciamento  della  esigenza  di  esplorare  nuove  regioni  dello  spazio  delle  soluzioni  

(exploration)  e  di  quella  di  sfruttare  con  una  ricerca  locale  le  informazioni  già  a  disposizione  (exploitation),  è  

caratterizzato  dal  fatto  che  ad  ogni  iterazione  dell’algoritmo  viene  aggiornato  un  intero  insieme  di  soluzioni  

(popolazione).  

L’algoritmo  prevede  al  generazione  casuale  di  una  popolazione  inziale  e  finchè  la  condizione  di  

terminazione  non  interrompe  l’evoluzione  itera  sulla  popolazione  i  processi  di  selezione,  crossover,  

mutazione  e  sostituzione.  

Pseudocodice:  

generation = 0

Inizializza popolazione P(t)=P(0)

while not <condizione di terminazione>

do

generation = generation + 1

Calcola fitness di ciascun individuo

Selezione

Crossover(p )

cross

Mutazione(p )

mut

end while

I  parametri  da  cui  dipende  il  funzionamento  dell’algoritmo  sono  3:    

n:  numero  di  individui  della  popolazione  

pcross:  probabilità  di  crossover  (interno  all’operatore  di  crossover  tipicamente  pari  a  0.6)  

pmut:  probabilità  di  mutazione  (interno  all’operatore  di  mutazione  tipicamente  pari  a  0.01)  

La  condizione  di  terminazione  può  essere  fissata  da  un  numero  massimo  di  cicli  da  eseguire  o  da  un  numero  

di  cicli  in  cui  non  si  è  modificata  la  soluzione  precedente.  

L’algoritmo  funziona  nel  seguente  modo.  Sia  P(t)  la  popolazione  all’istante  t  di  n  cromosomi  e  P(0)  la  

popolazione  generata  casualmente  all’istante  0.  Il  ciclo  principale  di  un  algoritmo  genetico    genera  una  

nuova  popolazione  P(t+1)  a  partire  da  P(t)  applicando  alcuni  operatori.  Questi  operatori  modificano  alcuni  

individui  scelti  a  caso  dalla  popolazione  P(t)  ottenendo  cosi  la  popolazione  P(t+1)  i  cui  individui  sono  in  

probabilità  migliori  di  quelli  di  P(t),  essendo  con  probabilità  alta  solo  copie  degli  individui  di  P(t)  con  valori  

di  fitness  più  alta.  L’effetto  degli  algoritmi  genetici  è  quindi  quello  di  spostare  P(t)    verso  le  composizioni  

migliori,  ciò  corrisponde  a  dirigere  la  ricerca  del  massimo  della  funzione  fitness  verso  le  zone  nello  spazio  

delle  soluzioni  caratterizzate  da  più  alti  valori  della  stessa  funzione  di  fitness.  Il  modo  di  operare  degli  

algoritmi  genetici  è  tale  per  cui  il  raggiungimento  della  soluzione  ottima  non  è  dovuto  agli  interi  cromosomi  

ma  a  loro  parti  fortemente  correlate  con  alti  valori  della  funzione  di  fitness  dette  building  blocks.  Gli  

algoritmi  genetici  sono  quindi  efficaci  in  tutti  i  casi  in  cui  la  soluzione  può  essere  pensata  come  una  

collezione  di  building  blocks.  

Gli  operatori  genetici  principali  sono  4:  

Selezione