Algoritmo xenético

Na Galipedia, a wikipedia en galego.

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, en lugar 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 gran é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 fácilmente paralelizábeis e poden, polo tanto, sacar vantaxe da redución do custo de hardware para cómputo en paralelo.

Índice

1 Descrición do algoritmo
- 1.1 Pseudocódigo
2 Referencias
3 Ligazóns externas

[editar] 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 probabilísticamente 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.

[editar] 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 condicion prefixada de finalización

[editar] Referencias

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