PDF de programación - EKIPO 5 - Algoritmos genéticos

EKIPO 5

ALGORITMOS GENETICOS



Los algoritmos genéticos consisten en generar una serie de posibles soluciones al
azar y en ir creando sucesivas generaciones (soluciones hijas, mezcla de otras
soluciones posibles anteriores), dando más importancia y más peso a las mejores
soluciones.


El objetivo de los AG es buscar dentro de un espacio de hipótesis candidatas la
mejor de ellas. En los AG la mejor hipótesis es aquella que optimiza a una métrica
predefinida para el problema dado, es decir, la que más se aproxima a dicho valor
numérico una vez evaluada por la función de evaluación.


Algoritmos Genéticos Generacionales
Se asemejan a la forma de reproducción de los insectos, donde una generación pone huevos, se aleja
geográficamente o muere y es substituida por una nueva. En este momento se realizan cruces en una
piscina de individuos, los descendientes son puestos en otra, al final de la fase reproductiva se elimina la
generación anterior y se pasa a utilizar la nueva. Este modelo también es conocido como Algoritmo
Genético Canónico.
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. Se presentarán aquí los
conceptos básicos que se requieren para abordarla, así como unos sencillos ejemplos que permitan a los
lectores comprender cómo aplicarla al problema de su elección.

En los últimos años, la comunidad científica internacional ha mostrado un creciente interés en una nueva
técnica de búsqueda basada en la teoría de la evolución y que se conoce como el algoritmo genético. 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.



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.

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

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

dentro de un cierto rango.

mala es una cierta respuesta.

• Las soluciones deben codificarse de una forma que resulte relativamente fácil de

implementar en la computadora



Los algoritmos genéticos se revalorizaron ya que poseen las siguientes ventajas
competitivas:

• Solo necesitan asesoramiento del experto cuando se agregan o suprimen

variables al modelo. Los Sistemas Expertos requieren la presencia del
mismo ante cada modificación del entorno.

• Los algoritmos genéticos solo requieren el asesoramiento del experto para

identificar las variables pertinentes , aunque no es necesario que éstos
definan sus valores ni sus relaciones (las reglas) iniciales o finales. Los
Sistemas Expertos solo trabajan con las reglas y valores que les dictan los
seres humanos



3.7. Algoritmos Genéticos Paralelos

En este apartado se introducirán tres maneras diferentes de explotar el paralelismo de
los Algoritmos Genéticos, por medio de los denominados modelos de islas. Para una
profundización sobre el tema puede consultarse Stender.

Modelos de islas.

La idea básica consiste en dividir la población total en varias subpoblaciones en cada
una de las cuales se lleva, a cabo un Algoritmo Genético. Cada cierto número de
generaciones, se efectúa un intercambio de información entre las subpoblaciones,
proceso que se denomina migración. La introducción de la migración hace que los
modelos de islas sean capaces de explotar las diferencias entre las diversas
subpoblaciones, obteniéndose de esta manera una fuente de diversidad genética. Cada
subpopulación es una "isla", definiéndose un procedimiento por medio del cual se
mueve el material genético de una "isla" a otra. La determinación de la, tasa de
migración, es un asunto de capital importancia, ya que de ella puede depender la
convergencia prematura de la búsqueda.
Se pueden distinguir diferentes modelos de islas en función de la comunicación entre las
subpoblaciones. Algunas comunicaciones típicas son las siguientes:

• Comunicación en estrella, en la cual existe una subpoblación que es

seleccionada como maestra (aquella que tiene mejor media en el valor de la
función objetivo), siendo las demás consideradas como esclavas. Todas las
subpoblaciones esclavas mandan sus h1 mejores individuos (h1, > 1) a la
subpoblación maestra la cual a su vez manda sus h2 mejores individuos (h2 > 1)
a cada una de las subpoblaciones esclavas. Véase Figura 12.

Figura 12



• Comunicación en red, en la cual no existe una jerarquía entre las

subpoblaciones, mandando todas y cada una de ellas sus h3 (h3 > 1) mejores
individuos al resto de las subpoblaciones. Véase Figura 13.

Figura 13



• Comunicación en anillo, en la cual cada subpoblación envía sus h4 mejores

individuos (h4 > 1), a una población vecina, efectuándose la migración en un
único sentido de flujo. Véase Figura 14.

El modelo de islas ha sido utilizado por varios autores (Whitley y Starkweather,
Gorges-Schleuter, Tanese).



CLASES DE ALGORITMOS GENÉTICOS

Algoritmos Genéticos Generacionales
Se asemejan a la forma de reproducción de los insectos, donde una generación pone
huevos, se aleja geográficamente o muere y es substituida por una nueva. En este
momento se realizan cruces en una piscina de individuos, los descendientes son puestos
en otra, al final de la fase reproductiva se elimina la generación anterior y se pasa a
utilizar la nueva. Este modelo también es conocido como Algoritmo Genético
Canónico.

Algoritmos Genéticos de estado Fijo.
Utilizan el esquema generacional de los mamíferos y otros animales de vida larga,

donde coexisten padres y sus descendientes, permitiendo que los hijos sean educados
por sus progenitores, pero también que a la larga se genere competencia entre ellos.
En este modelo, no solo se deben seleccionar los dos individuos a ser padres, si no
también cuales de la población anterior serán eliminados, para dar espacio a los
descendientes.
La diferencia esencial entre el reemplazo generacional y el modelo de estado fijo es que
las estadísticas de la población son recalculadas luego de cada cruce y los nuevos
descendientes están disponibles inmediatamente para la reproducción. Esto permite al
modelo utilizar las características de un individuo prometedor tan pronto como es
creado.
Algunos autores dicen que este modelo tiende a evolucionar mucho más rápido que el
modelo generacional, sin embargo investigaciones de Goldberg y deb [GOLDBERG
93], encontraron que las ventajas parecen estar relacionadas con la alta tasa de
crecimiento inicial, ellos dicen que los mismos efectos pueden ser obtenidos en rangos
de adaptación exponencial o selección por competencia. No encontraron evidencia que
este modelo sea mejor que el Generacional.

Algoritmos Genéticos Paralelos.
Parte de la metáfora biológica que motivo a utilizar la búsqueda genética consiste en
que es inherentemente paralela, donde al evolucionar se recorren simultáneamente
muchas soluciones, cada una representada por un individuo de la población. Sin
embargo, es muy común en la naturaleza que no solo sea una población evolucionando,
si no varias poblaciones, normalmente aisladas geográficament