Algoritmo xenético

Un algoritmo xenético é unha técnica, usada tipicamente na informática, para atopar solucións aproximadas a problemas de procura e optimización. Os algoritmos xenéticos son unha clase particular dos algoritmos evolutivos.

A procura da solución máis apropiada (é dicir, do "individuo" mais axeitado seguindo o símil) comeza cunha poboación inicial, ou colección, de solucións posíbeis. En cada xeración, unha parte (ou todos) dos individuos desa poboación teñen "descendencia" por medio da operación de cruzamento, normalmente combinada cunha operación de mutación, ambas as operacións así etiquetadas polo símil coa evolución biolóxica.

En cada xeración, os individuos dunha poboación son avaliados con respecto a unha función de axeitamento (fitness), determinando así aqueles individuos mais axeitados para se reproducir ou para sobrevivir na seguinte xeración.

Obsérvese que, no canto de levar a cabo no espazo de hipóteses unha procura desde o xeral ao específico (procura e eliminación de candidatos), ou do simple ao complexo, un algoritmo xenético xera unha serie de hipóteses sucesivas por repetición de mutacións, combinacións e selección das mellores hipóteses coñecidas ata ese momento. Polo tanto, en cada iteración do algoritmo ocorren dous pasos:

1. "reprodución": xeración de novos "individuos" na poboación por medio de cruzamento e mutación dun subconxunto dos individuos existentes na poboación actual.
2. "selección": eliminación de parte dos individuos, normalmente daqueles que presentan un menor axeitamento.

A popularidade dos algoritmos xenéticos débese a varios factores como:

• A evolución pode verse como un método robusto de adaptación, de grande éxito nos sistemas biolóxicos.
• Os algoritmos xenéticos poden buscar en espazos de hipóteses que conteñen elementos en complexa interacción, de tal forma que a influencia de cada elemento sobre a medida de adaptación global das hipótese, sexa difícil de modelar.
• Os algoritmos xenéticos son facilmente paralelizábeis e poden, polo tanto, sacar vantaxe da redución do custo de hardware para cómputo en paralelo.

Descrición do algoritmo

O problema que confrontan os algoritmos xenéticos consiste en identificar o mellor individuo (é dicir, a mellor hipótese) dentro dunha poboación (espazo de hipóteses candidato), definindo o mellor individuo como aquel que optimiza unha medida numérica predefinida para o problema, chamado adaptación ou axeitamento (fitness) do individuo. Por exemplo, se a tarefa de aprendizaxe é o problema de aproximar unha función descoñecida dado un conxunto de adestramento de entradas e saídas, o axeitamento pode definirse como a precisión da hipótese sobre o conxunto de adestramento (porcentaxe de éxitos ao predicir a saída). Se a tarefa de aprendizaxe ten a forma dun xogo, o axeitamento pode medirse en termos da porcentaxe de partidas gañadas.

Aínda que os detalles de implementación varían entre diferentes algoritmos xenéticos, todo comparten en xeral a seguinte estrutura: O algoritmo opera iterativamente, actualizando un conxunto de hipótese chamada poboación. En cada iteración, todos os membros da poboación son avaliados de acordo a unhafunción de axeitamento. Unha nova poboación é xerada, seleccionando probabilisticamente os individuos de maior axeitamento na poboación presente. Algúns destes individuos pasan intactos á seguinte xeración. Outros son seleccionados para crear unha nova prole, aplicando operacións xenéticas como o cruzamento e a mutación.

Pseudocódigo

Escoller unha poboación inicial
Repetir
 avalía o grao de axeitamento dos individuos da poboación 
 Selecciona parellas de individuos para se reproducir
 Aplicar o operador de "cruzamento"
 Aplicar o operador de "mutación"
 Aplicar o operador de "selección", descartando un subconxunto de individuos
Ata que se acade unha condición prefixada de finalización

Bibliografía

En inglés:

• Goldberg, David E (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA.
• Goldberg, David E (2002), The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Addison-Wesley, Reading, MA.
• Harvey, Inman (1992), Species Adaptation Genetic Algorithms: A basis for a continuing SAGA, in 'Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life', F.J. Varela e P. Bourgine (eds.), MIT Press/Bradford Books, Cambridge, MA, pp. 346–354.
• Holland, John H (1975), "Adaptation in Natural and Artificial Systems", University of Michigan Press, Ann Arbor
• Koza, John (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection
• Michalewicz, Zbigniew (1999), Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag.
• Mitchell, Melanie, (1996), An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA.
• Schmitt, Lothar M (2001), Theory of Genetic Algorithms, Theoretical Computer Science (259), pp. 1–61
• Schmitt, Lothar M (2004), Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling, Theoretical Computer Science (310), pp. 181–231
• Vose, Michael D (1999), The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA.

Ligazóns externas

En castelán:

1. Tutorial de algoritmos genéticos Arquivado 28 de outubro de 2005 en Wayback Machine.
2. Algoritmos genéticos y computación evolutiva

En inglés:

• Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, dispoñible de forma gratuíta vía Lulu.com.
• (en inglés) Genetic Algorithms in Ruby
• https://web.archive.org/web/20050903002901/http://cs.felk.cvut.cz/~xobitko/ga/ - An online introduction to genetic algorithms with Java applets
• IlliGAL - Illinois Genetic Algorithms Laboratory - Download technical reports and code
• Golem Project - Automatic Design and Manufacture of Robotic Lifeforms
• Introduction to Genetic Algorithms Using RPL2
• Talk.Origins FAQ on the uses of genetic algorithms, by Adam Marczyk
• Genetic algorithm in search and optimization, by Richard Baker
• Differential Evolution using Genetic Algorithm
• Genetic algorithms and Markov Chain Monte Carlo: Differential Evolution makes Bayesian computing easy (genetic algorithm for statistical analysis)
• Introduction to Genetic Algorithms and Neural Networks including an example windows program
• Genetic Algorithm Solves the Toads and Frogs Puzzle (requires Java)
• Not-So-Mad Science: Genetic Algorithms and Web Page Design for Marketers by Matthew Syrett
• MIT OpenCourseWare | Health Sciences and Technology | HST.508 Genomics and Computational Biology, Fall 2002 | Lecture Notes Arquivado 31 de outubro de 2005 en Wayback Machine.
• A Genetic Algorithm Tutorial by Darrell Whitley Computer Science Department Colorado State University An excellent tutorial with lots of theory
• Evolutionary computing in search-based software engineering. Leo Rela. How evolutionary computing (specifically GA) is used in software engineering.
• Heuristics and artificial intelligence in finance and investment - The use of genetic algorithms in finance and investment.
• Commercial application of genetic algorithm software for database marketing, direct marketing list development, and predictive modeling