Computació evolutiva
De Viquipèdia
La computació evolutiva és una tècnica d'optimització numèrica proposada per primer cop per John Holland al 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'aplica un procés evolutiu, on al final de varies 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 es seleccionen estocàsticament aquells individus amb una avaluació (fitness) més alta, aquest fitness també és conegut, com el grau d'adaptació al 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 reemplaçen 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 la 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:
- Algorismes genètics
- Programació genètica
- Estratègia evolutiva
- Algorismes d'estimació de distribució
