PDF de programación - Algoritmos geneticos

ALGORITMOS GENETICOS

ÍNDICE

1. Introducción

1.1 Antecedentes

1.2 Definición

1.3 Problemática

1.4 Ventajas y Desventajas

1.5 Limitaciones

1.6 Como saber si es posible usar un Algoritmo Genético



2. Extensiones y Modificaciones del Algoritmo Genético Simple

3.1. Población

3.1.1. Tamaño de la población

3.1.2. Población inicial

3.2. Función objetivo

3.3. Selección

3.4. Cruce

3.5. Mutación

3.6. Reducción

Ejemplos de Aplicación

5.1 Ejemplo 1

Referencias (Bibliografía)



1. Introducción

1.1. Antecedentes
El algoritmo genético es una técnica de búsqueda basada en la teoría de la evolución de
Darwin, que ha cobrado tremenda popularidad en todo el mundo durante los últimos años

Esta técnica se basa en los mecanismos de selección que utiliza la naturaleza, de acuerdo a
los cuales los individuos más aptos de una población son los que sobreviven, al adaptarse
más fácilmente a los cambios que se producen en su entorno. Hoy en día se sabe que estos
cambios se efectúan en los genes de un individuo (unidad básica de codificación de cada uno
de los atributos de un ser vivo), y que sus atributos más deseables (i.e., los que le permiten
adaptarse mejor a su entorno) se transmiten a sus descendientes cuando éste se reproduce
sexualmente.

Un investigador de la Universidad de Michigan llamado John Holland era consciente de la
importancia de la selección natural, y a fines de los 60s desarrolló una técnica que permitió
incorporarla a un programa. Su objetivo era lograr que las computadoras aprendieran por sí
mismas. A la técnica que inventó Holland se le llamó originalmente "planes reproductivos",
pero se hizo popular bajo el nombre "algoritmo genético" tras la publicación de su libro en
1975.

Una definición bastante completa de un algoritmo genético es la propuesta por John Koza:

"Es 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
presentado de forma natural una serie de operaciones genéticas de entre las que destaca la
recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de
caracteres (letras o números) 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. "



1.2. Definición

Los Algoritmos Genéticos (AGs) 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 más
fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos 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.

Un algoritmo genético consiste en una función matemática o una rutina de software que
toma como entradas a los ejemplares y retorna como salidas cuales de ellos deben generar
descendencia para la nueva generación.

Versiones más complejas de algoritmos genéticos generan un ciclo iterativo que directamente
toma a la especie (el total de los ejemplares) y crea una nueva generación que reemplaza a
la antigua una cantidad de veces determinada por su propio diseño. Una de sus
características principales es la de ir perfeccionando su propia heurística en el proceso de
ejecución, por lo que no requiere largos períodos de entrenamiento especializado por parte
del ser humano, principal defecto de otros métodos para solucionar problemas, como los
Sistemas Expertos.

1.3. Problemática

Los principios básicos de los Algoritmos Genéticos fueron establecidos por Holland, y se
encuentran bien descritos en varios textos . Goldberg, Davis, Michalewicz, Reeves.

En la naturaleza los individuos de una población compiten entre sí 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 más
éxito en sobrevivir y en atraer compañeros tienen mayor probabilidad de generar un gran
número de descendientes. Por el contrario individuos poco dotados producirán un menor
número de descendientes. Esto significa que los genes de los individuos mejor adaptados se
propagarán 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.

Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural. Trabajan
con una población de individuos, cada uno de los cuales representa una solución factible a un
problema dado. A cada individuo se le asigna un valor ó puntuación, relacionado con la
bondad de dicha solución. En la naturaleza esto equivaldría al grado de efectividad de un
organismo para competir por unos determinados recursos. Cuanto mayor sea la adaptación
de un individuo al problema, mayor será la probabilidad de que el mismo sea seleccionado
para reproducirse, cruzando su material genético con otro individuo seleccionado de igual
forma. Este cruce producirá nuevos individuos . descendientes de los anteriores . los cuales
comparten algunas de las características de sus padres. Cuanto menor sea la adaptación de
un individuo, menor será la probabilidad de que dicho individuo sea seleccionado para la
reproducción, y por tanto de que su material genético se propague en sucesivas
generaciones.

De esta manera se produce una nueva población de posibles soluciones, la cual reemplaza a
la anterior y verifica la interesante propiedad de que contiene una mayor proporción de
buenas características en comparación con la población anterior. Así a lo largo de las
generaciones las buenas características se propagan a través de la población. Favoreciendo el
cruce de los individuos mejor adaptados, van siendo exploradas las áreas más prometedoras
del espacio de búsqueda. Si el Algoritmo Genético ha sido bien diseñado, la, población
convergerá hacia una solución óptima del problema.

1.4. Ventajas y Desventajas

No necesitan conocimientos específicos sobre el problema que intentan resolver.

• Operan de forma simultánea con varias soluciones, en vez de trabajar de forma

secuencial como las técnicas tradicionales.

• Cuando se usan para problemas de optimización maximizar una función objetivo-

resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas
tradicionales.

• Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivamente

paralelas.

las otras técnicas.

• Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de

• Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en

cierta medida de los parámetros que se utilicen tamaño de la población, número de
generaciones, etc.-.

• Pueden converger prematuramente debido a una serie de problemas de diversa

índole.

1.5. Limitaciones

El poder de los Algoritmos Genéticos 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 Algoritmo Genético encuentre la solución óptima, 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. En el caso de
que existan técnicas especializadas para resolver un determinado problema, lo más probable
es que superen al Algoritmo Genético, tanto en rapidez como en eficacia. El gran campo de
aplicación de los Algoritmos Genéticos se relaciona con aquellos problemas para los cuales no
existen técnicas especializadas. Incluso en el caso en que dichas técnicas existan, y funcionen
bien, pueden efectuarse mejoras de las mismas hibridándolas con los Algoritmos Genéticos.

1.6. Como Saber si es Posible usar un Algoritmo Genético

La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de
optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos
los problemas pudieran ser apropiados para la técnica, y se recomienda en general tomar en
cuenta las siguientes características del mismo antes de intentar usarla:

• Su espacio de búsqueda (i.e., sus posibles soluciones) debe estar delimitado dentro

de un cierto rango.

• Debe poderse definir una función de aptitud que nos indique qué tan buena o mala

•

es una cierta respuesta.
Las soluciones deben codificarse de una forma que resulte relativamente fácil de
implementar en la computadora.

El primer punto es muy importante, y lo más recomendable es intentar resolver problemas
que tengan espacios de búsqueda discretos aunque éstos sean muy grandes. Sin embargo,
también podrá intentarse usar la técnica con espacios de búsqueda continuos, pero
preferentemente cuando exista un rango de soluciones relativamente pequeño.

La función de aptitud no es más que la función objetivo de nuestro problema de
optimización. El algoritmo genético únicamente maximiza, pero la minimización puede
realizarse fácilmente utilizando el recíproco de la función maximizante (debe cuidarse, por