1. GENERALIDADES
1.1. INTRODUCCIÓN
1.1.1.
Reseña Historica
Los algoritmos genéticos (AG), fueron inventados
en 1975 por John Holland, de la Universidad de Michigan. Los AG
son, simplificando, algoritmos de optimización, es decir,
tratan de encontrar la mejor solución a un problema dado
entre un conjunto de soluciones posibles. Los mecanismos de los
que se valen los AG para llevar a cabo esa búsqueda pueden
verse como una metáfora de los procesos de
evolución biológica.
John Holland desde pequeño, se preguntaba
cómo logra la naturaleza, crear seres cada vez más
perfectos. No sabía la respuesta, pero tenía una
cierta idea de como hallarla: tratando de hacer pequeños
modelos de la naturaleza, que tuvieran alguna de sus
características, y ver cómo funcionaban, para luego
extrapolar sus conclusiones a la totalidad.
Fue a principios de los 60, en la Universidad de
Michigan en Ann Arbor, donde, dentro del grupo Logic of
Computers, sus ideas comenzaron a desarrollarse y a dar frutos. Y
fue, además, leyendo un libro escrito por un
biólogo evolucionista, R. A. Fisher, titulado La
teoría genética de la selección natural,
como comenzó a descubrir los medios de llevar a cabo sus
propósitos de comprensión de la naturaleza. De ese
libro aprendió que la evolución era una forma de
adaptación más potente que el simple aprendizaje, y
tomó la decisión de aplicar estas ideas para
desarrollar programas bien adaptados para un fin
determinado.
En esa universidad, Holland impartía un curso
titulado Teoría de sistemas adaptativos. Dentro de este
curso, y con una participación activa por parte de sus
estudiantes, fue donde se crearon las ideas que más tarde
se convertirían en los AG.
Por tanto, cuando Holland se enfrentó a los AG,
los objetivos de su investigación fueron dos:
imitar los procesos adaptativos de los sistemas naturales,
y diseñar sistemas artificiales (normalmente
programas) que retengan los mecanismos importantes de los
sistemas naturales.
Unos 15 años más adelante, David Goldberg,
actual delfín de los AG, conoció a Holland, y se
convirtió en su estudiante. Goldberg era un ingeniero
industrial trabajando en diseño de pipelines, y fue uno de
los primeros que trató de aplicar los AG a problemas
industriales. Aunque Holland trató de disuadirle, porque
pensaba que el problema era excesivamente complicado como para
aplicarle AG, Goldberg consiguió lo que quería,
escribiendo un AG en un ordenador personal Apple II. Estas y
otras aplicaciones creadas por estudiantes de Holland
convirtieron a los AG en un campo con bases suficientemente
aceptables como para celebrar la primera conferencia en 1985,
ICGA´85.
1.1.2.
¿Que son los Algoritmos
Genéticos?
Los AG son métodos adaptativos que pueden usarse
para resolver problemas de búsqueda y optimización.
Están basados en el proceso genético de los
organismos vivos. A lo largo de las generaciones, las poblaciones
evolucionan en la naturaleza de acorde con los principios de la
selección natural y la supervivencia de los mas fuertes,
postulados por Darwin (1859). Por imitación de este
proceso, los AG son capaces de ir creando soluciones para
problemas del mundo real. La evolución de dichas
soluciones hacia valores óptimos del problema depende en
buena medida de una adecuada codificación de las
mismas.
En la naturaleza los individuos de una población
compiten entre si en la búsqueda de recursos tales como
comida, agua y refugio. Incluso los miembros de una misma especie
compiten a menudo en la búsqueda de un compañero.
Aquellos individuos que tienen mas éxito en sobrevivir y
en atraer compañeros tienen mayor probabilidad de generar
un gran numero de descendientes. Por el contrario individuos poco
dotados producirán un menor numero de descendientes. Esto
significa que los genes de los individuos mejor adaptados se
propagaran en sucesivas generaciones hacia un número de
individuos creciente. La combinación de buenas
características provenientes de diferentes ancestros,
puede a veces producir descendientes "superindividuos", cuya
adaptación es mucho mayor que la de cualquiera de sus
ancestros. De esta manera, las especies evolucionan logrando unas
características cada vez mejor adaptadas al entorno en el
que viven.
El poder de los AG proviene del hecho de que se trata de
una técnica robusta, y pueden tratar con éxito una
gran variedad de problemas provenientes de diferentes
áreas, incluyendo aquellos en los que otros métodos
encuentran dificultades. Si bien no se garantiza que el AG
encuentre la solución optima del problema, existe
evidencia empírica de que se encuentran soluciones
de un nivel aceptable, en un tiempo competitivo con el resto de
algoritmos de optimización combinatoria.
Página siguiente  |