Tugurium/GTI

Glosario Terminología Informática

Genetic Algorithm

0 GA
Técnica de búsqueda basada en la teoría de la evolución de Darwin. Se basa en un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse realizado una serie de operaciones genéticas de entre las que destaca la recombinación. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta función matemática que refleja su aptitud.
Los pasos que realiza un algoritmo genético son:
1 - Se genera un conjunto de 1-N soluciones válidas al problema. Normalmente, estas entidades se generan al azar, con valores de 20 a 200.
2 - Se evalúan las soluciones existentes, de manera que se eliminan unas y se mantienen otras (otra posibilidad sería limitar el tiempo de ejecución)
3 - Se permite la reproducción o recombinación de genes (normalmente por parejas) de las entidades existentes. Por ejemplo, se realizan cruzamientos de patrones a partir de cierto punto elegido al azar, de forma que los nuevos patrones posean un segmento de cada uno de los progenitores.
4 - Se efectúan mutaciones (cambios al azar en los genes) de los nuevos patrones, según una tasa determinada.
5 - Se continúa en el paso 2 hasta que se encuentre una entidad que se considere con sufciente peso.
Este tipo de computación evolutiva fue ideado por John Holland.
2004-04-28