Computació evolutiva

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.

Etapes

El procés evolutiu al qual se sotmeten els individus està definit per cinc etapes: Inicialització, Avaluació, Selecció, Procreació i Reemplaçament.

La inicialització é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.

Vessants

Programació Evolutiva

Es tracta d'un mètode d'optimització que parteix d'un conjunt de dades per donar lloc a diverses solucions a una mateixa premissa. Per tal d'aconseguir-ho, s'empren operadors inspirats en les premisses de Charles Darwin, com poden ser les mutacions o els crossovers. El procés comença explorant el ventall d'opcions. Seguidament, s'avaluen les diferents opcions individualment i es determinen quins seran els subjectes de mostra que es faran servir per donar lloc a "la següent generació" (o resultar en material nou). S'utilitzen els operadors sobre els subjectes seleccionats i finalment, s'analitza el resultat. Es repeteix el procés tornant al pas dos tantes vegades com és necessari.

Estratègies Evolutives

Tècnica també basada en la teoria evolutiva de Darwin basada en variables d'un problema i paràmetres de l'estratègia evolutiva. Els individus de l'estratègia tenen una estructura semblant a:

I= <x₁, x₂, x_n..., ơ₁, ơ₂, ơ_n...>

S'enenen x com les variables i ơ com els parámetres. Aquesta tècnica té la capacitat d'autoadaptar-se.

Algorismes Genètics

Són algorismes que destrien a partir d'un procés de competència basat en la supervivència del més fort. Rep el nom de mecanisme de selecció, que empra aquestes premisses per determinar el nombre de cromosomes (en aquest context, el terme cromosoma fa referència a les característiques intrínseques dels subjectes que s'estudien).

Els algorismes genètics fan ús d'operadors genètics com són el crossover i la mutació. Aquesta tècnica funciona a la inversa de les altres: primer es presenten els possibles resultats i, posteriorment, a partir del ventall de subjectes, els cromosomes que presentes i aplicant els operadors, s'intenten reproduir.

Algunes implantacions

Algunes implementacions famoses d'algorismes evolutius són: Algorismes genètics, Programació genètica, Estratègia evolutiva i Algorismes d'estimació de distribució.