Computació evolutiva

Part d'una sèrie sobre
Biologia evolutiva
Pinsans de Darwin (il·lustració de John Gould)
Temes clau Introducció a l'evolució Proves de l'evolució Descendència comuna Proves de la descendència comuna
Processos i resultats Genètica de poblacions Variació Diversitat Mutació Selecció natural Adaptació Polimorfisme Deriva genètica Flux gènic Especiació Radiació adaptativa Cooperació Coevolució Coextinció Divergència Convergència Evolució paral·lela Extinció
Història natural Origen de la vida Història de la vida Cronologia de l'evolució Evolució dels éssers humans Filogènesi Biodiversitat Biogeografia Classificació Sistemàtica evolutiva Cladística Fòssil de transició Extinció massiva
Història de la teoria de l'evolució Vista general Renaixement Abans de Darwin Darwin L'origen de les espècies Abans de la síntesi Síntesi moderna Evolució molecular Evo-devo Recerca actual Història de l'especiació Història de la paleontologia (cronologia)
Branques i aplicacions Antropologia evolutiva Aplicacions de l'evolució Computació evolutiva Criminologia biosocial Darwinisme universal Ecologia evolutiva Economia evolutiva Epistemologia evolucionista Estètica evolutiva Ètica evolucionista Evolució del llenguatge Evolució experimental Experiments sobre l'especiació Filogènia Fisiologia evolutiva Genètica ecològica Medicina evolucionista Neurociència evolucionista Paleontologia Psicologia evolucionista Selecció artificial Sistemàtica Sociobiologia Teoria evolutiva de jocs
Aspectes socials Evolució com a fet i com a teoria Aspectes socials Controvèrsia entre el creacionisme i l'evolucionisme Crítiques a l'evolució Suport científic
Categoria

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ó.