PDF de programación - Algoritmos Genéticos (I)

Algoritmos Genéticos (I)



© 2001 Javier Ventoso Reigosa

www.texelfactory.com

Artículo publicado en la revista Sólo Programadores Num. 89



Este primer artículo será de introducción a los Algoritmos Genéticos, veremos cómo
surgieron, su estructura y funcionamiento básico, sus virtudes y limitaciones.

Se le atribuye a John Holland ser el descubridor (junto con sus colegas y alumnos) de los
algoritmos genéticos en la década de los sesenta en la Universidad de Michigan, en donde
impartía un curso llamado “Teoría de sistemas adaptativos”. En un principio denominó a esta
técnica “planes reproductivos” pero más tarde se popularizó con el nombre de “algoritmos
genéticos”.
Lo cierto es que otros destacados personajes ya habían intuido antes que Holland la relación
beneficiosa entre el concepto de evolución y la computación.
Charles Babbage en su libro “Ninth Bridgewater Treatise” (1813) aprovecha su modelo
teórico de computadora para intentar ofrecer una prueba matemática de que Dios tenía
programada a la naturaleza para generar a todas las especies; habría creado las leyes que
generaban a las especies en lugar de crearlas directamente. Charles Darwin, padre de la
teoría de la selección natural (1859), conocía a Babbage y su libro y asistió en varias
ocasiones a sus “parties” en Londres, y es muy probable que ambos debatiesen sobre el
tema.
Después de Babbage, el propio John von Newmann estudió el problema abstracto de la
autorreplicación, pensaba que debía existir un código que describiera como se construye un
ser vivo y que dicho ser vivo tuviese la facultad de reproducirse. También Alan Turing realizó
en 1952 varios trabajos pioneros sobre uno de los problemas básicos de la embriología y
morfogénesis: ¿cómo puede la compleja topología de un organismo surgir de la simple
topología de una única célula fertilizada desde la que crece?.


John Holland fue el descubridor de los AGs.


Conceptos Básicos.
Antes de continuar es necesario repasar muy brevemente algunos conceptos que es
importante conocer para trabajar con AGs.

Gen: Es la unidad básica de material hereditario.
Cromosoma: Es un cuerpo en forma de filamento constituido principalmente por ADN y
proteína.
Genotipo: Es el conjunto de material genético de un organismo.
Fenotipo: Es el conjunto de caracteres observables de un organismo en contraposición con
el conjunto de genes que posee.
Locus: Es el lugar que ocupa un gen en un cromosoma.
Para comprenderlo mejor podemos imaginar que si el genotipo de un organismo estuviese
escrito en una gran enciclopedia cada tomo sería un cromosoma, cada página de cada
tomo sería un gen y el locus de un gen sería su número de página.
En cuanto al genotipo y fenotipo, es importante apuntar que un mismo genotipo puede dar
lugar a distintos fenotipos debido a variaciones en el ambiente. Lo cierto es que no todos los
genes se manifiestan en el fenotipo, algunos pueden estar enmascarados o neutralizados
por otros que los dominan o por el ambiente y aparecer sólo al cabo de varias
generaciones.


Imagen 1 - Esquema de las principales Técnicas de Búsqueda.



¿Qué es un Algoritmo Genético?
Los algoritmos genéticos (en adelante AGs) son métodos adaptativos que se emplean
principalmente para la resolución de problemas de búsqueda y optimización. Se enmarcan
dentro de la rama de Inteligencia Artificial conocida como Computación Evolutiva o
Algoritmos Evolutivos. Esta rama trata el estudio de los fundamentos y aplicaciones de
técnicas heurísticas de búsqueda que emplean los principios de la evolución natural. Existen
otras técnicas que junto con los AGs perteneces a esta rama, las más importantes son;
Programación Evolutiva, Estrategias Evolutivas, Programación Genética y Sistemas
Clasificadores. Las diferencias entre estas técnicas se basan principalmente en los diferentes
operadores que emplean y en las distintas técnicas de selección y reproducción de los
individuos de la población.
Los AGs son muy potentes y efectivos sobre todo para aquellos problemas con un gran
espacio de búsqueda y para los que no existe una técnica específica para resolverlo.
Podemos aprovecharnos de los AGs para realizar tareas muy complejas que de otra forma
sería muy difícil, o imposible, llevarlas a cabo con un enfoque más determinista; problemas
basados en variables con
ingeniería para
optimizaciones numéricas de algunos problemas no lineales que resultan muy difíciles de
resolver por métodos analíticos, son muy eficientes para el control de robots, e incluso
resultan muy útiles para el ajuste de los pesos de las conexiones de redes neuronales, etc.


interdependencias muy complejas, en

Son muy efectivos para problemas de búsqueda y optimización.


Funcionamiento.
Básicamente un AG se basa en la utilización de los mismos mecanismos que emplea la
naturaleza para la evolución de las especies. Los individuos que mejor se adaptan a su
entorno sobreviven sobre los que están peor adaptados. La parte interesante es que cada
individuo de la población de un AG representa una posible solución al problema que
intentamos resolver, por supuesto para ello tendremos que codificar cada individuo como
una representación válida del problema y necesitaremos también crear una función que
permita determinar hasta que punto cada individuo evoluciona correctamente para poder
actuar en consecuencia.

Los individuos con una mejor adaptación tendrán más posibilidades de reproducirse que
aquellos que posean un código genético peor, de esta forma las mejores secuencias
genéticas se propagarán en cada nueva generación por medio de los cruces entre los
mejores individuos. Si el AG está bien diseñado la población convergerá hacia la solución del
problema, o al menos hacia una solución óptima en un plazo de tiempo razonablemente
corto.
El esquema básico del funcionamiento de un AG simple es el siguiente:
- Crear la población inicial de forma aleatoria.
- Evaluar a cada uno de los individuos de la población.
- Crear una nueva población a partir del cruzamiento y mutación de los mejores individuos
de la población actual.
- Repetir proceso con la nueva población hasta que el algoritmo converja.


Los AGs emplean los mismos mecanismos que la evolución natural.



Imagen 2 - Charles Darwin, padre de la teoría de la selección natural.



resulta extremadamente

Función de Evaluación.
Un buen diseño de la función de evaluación (también conocida como función objetivo o
función de adaptación)
importante para el correcto
funcionamiento de un AG. Esta función determina el grado de adaptación o aproximación
de cada individuo al problema y por lo tanto permite distinguir a los mejores individuos de los
peores. A esta puntuación en función de su proximidad a la mejor solución del problema se
le denomina fitness.
Veamos un ejemplo; supongamos que hacemos un AG de prueba para que encuentre un
punto determinado en un espacio tridimensional. Cada individuo tendrá codificado en su
código genético un punto de ese espacio 3D, y la función de evaluación hallaría la inversa
de la distancia del punto buscado al punto codificado en cada individuo. De esta forma los
mejores individuos serían aquellos que estuviesen más próximos al punto a encontrar (los que
tengan un fitness mayor). Sobra mencionar que este problema es sólo de ejemplo, ya
sabemos de antemano cuál es el punto a buscar, pero nos sirve para ilustrar la utilidad y
funcionamiento de la función de evaluación.

individuo puede suponer un coste
Para ciertos problemas,
computacional demasiado elevado, para estos casos se puede implementar una función de
evaluación aproximada.


la evaluación de cada

Una población de 25 a 100 individuos es suficiente para muchos problemas.


Selección.
Existen distintos métodos para la selección de los padres que serán cruzados para la
creación de nuevos individuos, uno de los más utilizados se denomina función de selección
proporcional a la función de evaluación. Se basa en que la probabilidad de que un
individuo sea seleccionado como padre es proporcional al valor de su función de
evaluación. Esto hace que los mejor individuos sean los seleccionados para el proceso de
reproducción. Esta técnica puede producir el inconveniente de que la población converja
prematuramente hacia un resultado óptimo local. Esto significa que pueden aparecer
“superindividuos” muy similares entre si, de forma que la diversidad genética sea bastante
pobre y el algoritmo se estanque en una solución buena (óptimo local) pero no la mejor.
Trataremos éste y otros problemas más adelante con mayor detalle.
Otro método de selección es el de la Ruleta, consiste en asignar una porción de la “ruleta” a
cada individuo de forma que el tamaño de cada porción sea proporcional a su fitness. Los
mejores individuos dispondrán de una porción mayor y por lo tanto de más posibilidades de
ser seleccionados.
El método de Torneo consiste en hacer competir a los individuos en grupos aleatorios
(normalmente parejas), el que tenga el fitness más elevado será el ganador. En el caso de
competición por parejas se deben realizar dos torneos. Con este método de selección nos
aseguramos de que al menos dos copias del mejor individuo de la población actuarán
como progenitores para la siguiente generación. Este método tiene ev