Computació evolutiva

De Viquipèdia
Dreceres ràpides: navegació, cerca

La computació evolutiva és una tècnica d'optimització numèrica proposada per primer cop per John Holland el 1975, en el llibre Adaptation in Natural and Artificial Systems.

La tècnica està inspirada en l'evolució de poblacions a la natura. Cada possible solució del problema, que s'intenta optimitzar, es codifica mitjançant un cromosoma, i s'hi aplica un procés evolutiu, on al final de diverses generacions, els individus de la població són solucions relativament bones al problema.

El procés evolutiu al qual se sotmeten els individus està definit per cinc etapes:

  • Inicialització
  • Avaluació
  • Selecció
  • Procreació
  • Reemplaçament

La incialització és primer pas, on es creen tots els individus de la població. Molt sovint els individus creats són aleatoris. A continuació són avaluats i en la fase de selecció, típicament se seleccionen estocàsticament aquells individus amb una avaluació (fitness) més alta, aquest fitness també és conegut, com el grau d'adaptació a l'entorn.

A continuació, es generen nous individus, basant-se en aquells seleccionats. Per fer-ne de nous, típicament s'apliquen creuaments i mutacions dels cromosomes, però recents avanços en aquesta àrea han desenvolupat noves maneres de generar individus, per exemple amb models probabilístics com les xarxes Baiesianes.

Quan ja s'han generat els individus de la nova població, es reemplacen els individus de l'antiga població pels nous. Per fer aquest reemplaçament es poden manternir diferents estratègies, com elitisme, steady state, etc.

Aquest cicle es tanca amb l'avaluació dels individus de la nova població. El cicle evolutiu va iterant fins que s'assoleixen les condicions d'aturada, que poden ser un nombre màxim de generacions, un nombre màxim d'avaluacions, el grau de diversitat genètica a la població, etc.

Algunes implementacions famoses d'algorismes evolutius són: