Algoritmos geneticos

HISTORIA E INTRODUCCION A LOS ALGORITMOS GENETICOS
2010-05-15 Santiago Nájera

1. Introducción
Podemos decir que los conceptos de algoritmos genéticos comienzan con Charle Darwin, quien en el año de 1837, realizó un primer bosquejo de un árbol evolucionario, como parte de su libro Transmutación de las Especies (1837), en los cual explica la posibilidad de que una especie se transforme enotra, con lo cual se explicaría la distribución geográfica de las especies. No obstante estos conceptos fueron desarrollados y plasmados de una mejor manera en el año de 1859, cuando Darwin publica su libro “El origen de las especies mediante la selección natural o la conservación de las razas favorecidas en la lucha por la vida" más conocido como el origen de las especies, donde explica su teoríasobre la sobrevivencia de los mejores, lo cual se explica en la introducción de su obra donde el autor escribe lo siguiente:

“Como de cada especie nacen muchos más individuos de los que pueden sobrevivir, y como, en consecuencia, hay una lucha por la vida, que se repite frecuentemente, se sigue que todo ser, si varía, por débilmente que sea, de algún modo provechoso para él bajo las complejas y aveces variables condiciones de la vida, tendrá mayor probabilidad de sobrevivir y, de ser así, será naturalmente seleccionado. Según el poderoso principio de la herencia, toda variedad seleccionada tenderá a propagar su nueva y modificada forma.”

1.1. Relación entre la biología y la ciencia computacional. Estos conceptos creados por Darwin son el punto de partida de la computación evolutiva (ECpor sus siglas en ingles), misma que pretende recoger los conceptos de la biología, y similar algunos de estos procesos evolutivos, teniendo en cuenta que pese a que no todas estas teorías son cien por ciento comprobadas, gran parte son respaldadas por experimentación, tales como:
[1]

1. El proceso evolutivo se origina en los cromosomas y no en los organismo. 2. La selección Natural es elmecanismo por el el cual se mantienen aquellas características que mejor se adaptan. Punto de partida para lo cual se conoce como métodos de selección y métodos de cambio. 3. La evolución se da en el momento de la reproducción. De los conceptos tomados de las ciencias biológicas, aquel ha logrado una mayor popularidad y por tanto un gran desarrollo es el de algoritmos genéticos, mismos que en suinicio se los a representado mediante una cadena de bits de una tamaño determinado, en la cual cada posición dentro de la cadena representa o almacena una característica(Fleming y Purshouse), análogamente esto se puede representar los genes de un organismo biológico, a partir de estos conceptos se simula un sistema de reproducción mediante el concepto bit-string crossover, en las cuales dos cadenasde datos binarias son usadas como padres, y como respuesta se obtiene una combinación de estas (descendientes).

a) b)

1 1 0 1 0 0 1 0 1 0 0 1

c) 1 1 0 1 0 1 d) 1 0 1 0 0 0

El concepto de Crossover fue creado en 1975 por John H. Holland, quien en su libro, “Adaptación en Sistemas Naturales y Artificiales” señala como los cromosomas alinean y cambian parte de su código genético paracontinuar evolucionando.

[2]

El método de representación de los datos como cadenas de datos binarias es muy utilizado en la actualidad, no obstante se han generado distintos métodos de representar cadenas de datos, tales como el método desarrollado por John Koza, de la Universidad de Stamford, donde representa los datos en estructuras ramificadas (similar a los primeros conceptos de Darwin), coneste método los cambios se generan cambiando el operador, a través del cambio de valor de uno de los nodos o mediante sustitución de los sub arboles.

�� + 2

�� + �� ∗ 2

�� 2 − 1

De aquí que podemos decir que un algoritmo buscan similar los procesos biológicos, bajo la condición de que el algoritmo a lo largo del proceso mantenga el mejor elemento de la población sin hacerle cambios,...