Intelligenza artificiale - algoritmi evolutivi

Gli  algoritmi  evolutivi  

1  –  Descrizione  

Gli  algoritmi  evolutivi  sono  una  famiglia  di  tecniche  stocastiche  per  la  risoluzione  di  problemi  che  fa  parte  

della  più  ampia  categoria  dei  "modelli  a  metafora  naturale".  Essi  trovano  la  loro  ispirazione  in  biologia  e,  in  

particolare,  si  basano  sull'imitazione  dei  meccanismi  della  cosiddetta  "evoluzione  naturale".    

Questi  algoritmi  si  basano  sul  rendere  artificiale  i  concetti  della  biologia  reale  e  modellando  attraverso  

opportuni  operatori  e  funzioni  un  modello  evolutivo  biologico.  

La  metafora  che  guida  il  gli  algoritmi  evolutivi  si  basa  sulla  teoria  sull’evoluzione  di  C.  Darwin.  

Riassumendo  il  pensiero  di  Darwin  possiamo  vedere  che  in  natura  un  individuo  deve  adattarsi  all’ambiente  

in  cui  vive  per  sopravvivere  e  riprodursi.  Ogni  individuo  si  distingue  per  la  propria  capacità  di  adattarsi  e  

quindi  sopravvivere,  capacità  misurata  dai  biologi  tramite  un  grado  di  adattamento  chiamato  fitness.  La  

selezione  naturale  elimina  dalla  popolazione  gli  individui  che  non  sono  stati  in  grado  di  adattarsi  

all’ambiente.  La  genetica  delle  popolazioni  viene  continuamente  variata  tramite  lo  scambio  di  cromosomi  

che  avviene  nella  riproduzione  degli  individui  sopravvissuti  alla  selezione  naturale.  Alla  riproduzione  degli  

individui  oltre  che  al    mescolamento  dei  cromosomi  si  deve  anche  la  comparsa  di  una  nuova  popolazione  di  

individui  che  andranno  a  rimpiazzare  al  generazione  precedente  facendo  ripartire  il  ciclo  evoluzionistico.  Ad  

ogni  passaggio,  grazie  alla  selezione  naturale  e  al  mescolarsi  dei  cromosomi,  compare  una  popolazione  

contenente  individui  aventi  i    cromosomi  migliori  e  quindi  più  evoluti  dei  predecessori.  

Analogamente  in  ambiente  artificiale  si  può  inquadrare  un  problema  come  un  ambiente,  la  cui  popolazione  

è  fatta  dalle  possibili  soluzioni  dello  stesso.  Una  soluzione,  per  sopravvivere  deve  quindi  essere  adatta  a  

risolvere  il  problema,  cioè  avere  il  grado  più  alto  di  fitness.  Tramite  la  selezione  delle  soluzioni  migliori  della  

popolazioni,  cioè  quelle  aventi  fitness  maggiore,  si  potrà  far  evolvere  soluzioni  sempre  migliori  e  a  grado  di  

fitness  sempre  maggiore.  Mescolando  le  varie  componenti  delle  soluzioni  migliori  si  creano  nuove  

popolazioni  di  soluzioni  che  rimpiazzeranno  le  precedenti.  Il  ciclo  riparte  dall’inizio  con  la  nuova  

popolazione  di  soluzioni  permettendo  l’evolversi  delle  soluzioni  migliori.  

Si  possono  cosi  mappare  le  analogie  tra  il  mondo  della  biologia  e  quello  degli  algoritmi  evolutivi:  

Individui   Soluzioni  

Cromosomi   Stringhe  

Popolazione   Popolazione  

Genetica   Operatori  genetici  

Competizione   Selezione  

Sopravvivenza   Accuratezza  della  soluzione  rispetto  al  problema  

Sopravvivenza:  scopo  dell’evoluzione   Sopravvivenza:  soluzione  di  un  problema  

Un  limite  degli  algoritmi  evolutivi  è  dato  dal  fatto  che  non  si  fermano  automaticamente  al  raggiungimento  

della  soluzione  ottima,  ma  continuano  a  ciclare  all’infinito.  Bisogna  imporre  loro  un  numero  predefinito  di  

generazioni  sulle  quali  evolversi.  

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 &n