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:
# "**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.
# "**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.&nbsp;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.&nbsp;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.&nbsp;181–231
* Vose, Michael D (1999), *The Simple Genetic Algorithm: Foundations and Theory*, MIT Press, Cambridge, MA.

## Ligazóns externas 
**En castelán:**
# Tutorial de algoritmos genéticos 
# 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.
*  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 
* 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