Algoritme evolutiu

Antena de la nau espacial ST5 de la NASA. Esta intrincada forma va ser trobada usant un algoritme evolutiu, en el propòsit de conseguir el millor patró de radiació per a la nau.

Els algoritmes evolutius són métodos d'optimisació i busca de solucions basats en els postulats de l'evolució biològica. En ells es manté un conjunt d'entitats que representen possibles solucions, les quals es mesclen, i competixen entre sí, de tal manera que les més aptes són capaces de prevaldre a lo llarc del temps, evolucionant cap a millors solucions cada volta.

Els algoritmes evolutius, i la computació evolutiva, són una branca de l'inteligència artificial. Són utilisats principalment en problemes en espais de busca extensos i no llineals, en a on atres métodos no són capaços de trobar solucions en un temps raonable.

Seguint la terminologia de la teoria de l'evolució, les entitats que representen les solucions al problema es denominen individus o cromosomes, i el conjunt d'estos, població. Els individus són modificats per operadors genètics, principalment el creuament, que consistix en l'informació de dos o més individus; la mutació, que és un canvi aleatori en els individus; i la selecció, consistent en l'elecció dels individus que sobreviuran i conformaran la següent generació. Ya que els individus que representen les solucions més adequades al problema tenen més possibilitats de sobreviure, la població va millorant gradualment.

Paradigmes

Sol parlar-se de tres paradigmas principals d'algoritmes evolutius:

• Programació evolutiva
• Estratègies evolutives
• Algoritmes genètics

Cada u d'estos paradigmes es va originar independentment i en distintes motivacions. Actualment, els algoritmes tendixen a combinar característiques d'estos tres i a incloure mecanismes d'atres camps d'estudi, tals com l'aprenentage automàtic, uns atres algoritmes de busca, o diferents estructures de senyes. Algunes de les tendències actuals són les següents:

• Evolució diferencial
• Models provabilístics
• Evolució simulada
• Algoritmes culturals
• Algoritmes meméticos
• Programació genètica

Comparació d'algoritmes evolutius

La taula següent presenta algunes diferències entre els distints tipos d'algoritmes evolutius. Les característiques indicades en esta taula corresponen a les implementacions originals. Actualment les diferències entre ells tendixen a borrar-se a mida que es transferixen característiques d'un a un atre, fent difícil la distinció.

Algoritme	codificació	selecció	operadors	reinserció	parametrización	aplicació original/principal	observacions
Algoritme genètic	binaria	a l'encert, basat en funció d'eixercite (ruleta, torneig)	Aplicats segons provabilitat: creuament (1 o 2 punts, uniforme, etc.), mutació (negació de bit, a l'encert)	tongada de pares per fills mantenint al millor individu de la població anterior	fixa	optimisació discreta
Estratègia evolutiva	discreta o contínua	aleatòria	dissenyades d'acort al problema a resoldre: recombinació (optativa), mutació	elegida determinísticamente, per mig de rànquing de millor descendència ($(\mu /\rho ,\lambda )-ES$) o pares i descendència ($(\mu /\rho +\lambda )-ES$)	self-adaptive	optimisació general	notació $\mu$: número de pares, $\rho$: número d'individus elegits per a evolucionar, $\lambda$: descendència
Programació evolutiva	?	?	dissenyades d'acort al problema a resoldre: recombinació, mutació	?	?	?
Programació genètica	arbres	?	creuament (intercanvi de branques), mutació (canvi en contingut de nodo o tota la branca)	?	?	evolució de programes (generalment en lisp)
Algoritme memético	qualsevol	?	distints operadors de busca local	?	?	També cridat algoritme lamarckiano, busca local genètica, algoritme evolutiu híbrit, o algoritme evolutiu de Baldwin
Algoritme cultural	qualsevol	?	qualsevol	?	?	optimisació general, simulació social	conte ademés en un espai de creències, en a on es guarda experiència adquirida durant la busca
Evolució diferencial	contínua	aleatòria	mutació i recombinació, el resultat del primer és operat en el segon	comparant el resultat dels operadors i els individus de la generació anterior	Fixa, de dos paràmetros que controlen la velocitat del canvi, F i GR	optimisació contínua	l'operador de mutació, prou singular, de fet combina individus elegits aleatoriamente

Bibliografia

• Carmona, Enrique J.; Fernández, Severino (2020). Fonaments de la Computació Evolutiva. Marcombo. ISBN 978-8426727558.