PDF de programación - Computación Evolutiva - Algoritmos Genéticos

UNL - FICH - Departamento de Informática - Ingeniería Informática

Inteligencia Computacional

Computación Evolutiva
Algoritmos Genéticos

Temas a tratar

- Generalidades de los algoritmos de computación evolutiva.
- Diseño de la solución de un problema mediante algoritmos genéticos.
- Aplicación de la técnica de algoritmos genéticos.

Objetivos

- Aprender los fundamentos de la técnica.
- Aplicar las técnicas de computación evolutiva a problemas reales.
- Comprender la potencialidad de la técnica y sus limitaciones más

importantes.

- Implementar un algoritmo genético completo.
- Comparar a los algoritmos genéticos con otras técnicas de optimización y

búsqueda de soluciones.

1

Computación Evolutiva: Algoritmos Genéticos

1.

Introducción

Los algoritmos genéticos (AGs) junto con las estrategias evolutivas y la
programación evolutiva constituyen un nuevo enfoque a la solución de
numerosos problemas de optimización y búsqueda. Esta técnica está en el
contexto de una nueva ciencia denominada computación evolutiva. El campo
de las aplicaciones de la computación evolutiva no reconoce fronteras. Es
posible resolver problemas de las características más diversas.

La analogía en que se basan los AGs estriba en reconocer el mecanismo
esencial del proceso evolutivo en la naturaleza. Los componentes fundamen-
tales de éste mecanismo son los cromosomas, el material genético de un
individuo biológico, que determinan sus características únicas. Los cambios
en el material genético de las especies permiten el proceso de adaptación.

Las fuerzas que subyacen al proceso evolutivo son: la selección natural,
la recombinación de material genético y la mutación, fenómenos que se
presentan durante la reproducción de las especies. La competencia entre
los individuos por los recursos naturales limitados y por la posibilidad de
procreación o reproducción permite que sólo los más fuertes o más adaptados
sobrevivan. Esto significa que el material genético de los mejores individuos
sobrevive y se reproduce, mientras que los genes de los individuos más débiles
o menos adaptados, mueren o se extinguen. Y de esta forma la naturaleza
optimiza la solución al problema de la vida.

Se propone a los AGs como una técnica computacional que intenta imitar
el proceso evolutivo de la naturaleza, para el diseño de sistemas artificiales
adaptativos.

2. Estructura de un AG

Los AGs clásicos, manipulan una población de soluciones potenciales
codificadas en cadenas binarias que las representan. Este conjunto de
cadenas representan el material genético de una población de individuos.
Los operadores artificiales de selección, cruza y mutación son aplicados para
buscar los mejores individuos –mejores soluciones– a través de la simulación
del proceso evolutivo natural. Cada solución potencial se asocia con un valor
de fitness, el cual mide qué tan buena es comparada con las otras soluciones
de la población. Este valor de fitness es la simulación del papel que juega el
ambiente en la evolución natural darwiniana.

El paradigma de los algoritmos genéticos puede esquematizarse como

sigue:

Inteligencia Computacional - FICH-UNL

2

Computación Evolutiva: Algoritmos Genéticos

Inicializar(Población)
MejorFitness=Evaluar(Población)
Mientras (MejorFitness<FitnessRequerido)

Selección=Seleccionar(Población)
Población=CruzarYMutar(Selección)
MejorFitness=Evaluar(Población)

FinMientras

Para comenzar, se inicializa la población completamente al azar. En la
inicialización hay que tener en cuenta que la distribución de valores debe ser
uniforme para cada rango representado por los cromosomas. A continuación
se decodifica el genotipo en fenotipo de esta población inicial y evalúa el
fitness para cada individuo. Es decir, se le asigna un valor numérico a su
capacidad de supervivencia; en el espacio de soluciones de nuestro problema
medimos qué tan bien resuelve el problema cada individuo.

Luego entramos en el bucle de optimización o búsqueda. Este ciclo
termina cuando nuestro AG ha encontrado una solución adecuada para el
problema. Es decir, deberemos valernos del fitness para el mejor individuo
y de un umbral para evaluar esta condición de finalización.

Durante el proceso evolutivo artificial, se aplican varios operadores.
Mediante un proceso fuertemente estocástico se genera una nueva población
de individuos tomando en cuenta su fitness. Básicamente durante la selección
se decide cuáles individuos serán padres de la nueva generación. La nueva
población puede reemplazar completamente a la población anterior o
solamente a los peores individuos, las peores soluciones.

Con los cromosomas candidatos a ser padres de la nueva población se
efectúan cruzas y mutaciones. Las cruzas son intercambios de genes: el
proceso consiste en intercambiar segmentos de los cromosomas de las parejas
seleccionadas en forma aleatoria. Cuando un cromosoma sufre una mutación,
el alelo de uno de sus genes cambia en forma aleatoria. Las mutaciones
ocurren según una probabilidad de mutación, esta probabilidad es uno de
los parámetros que gobierna la evolución.

Finalmente, la población nace y se decodifica el genotipo en fenotipo
para evaluar su fitness. Al volver al principio del ciclo evolutivo verificamos
nuevamente si nuestro mejor individuo supera los requisitos de la búsqueda,
en caso contrario volvemos a repetir todo el proceso para obtener una nueva
generación.

Inteligencia Computacional - FICH-UNL

3

Computación Evolutiva: Algoritmos Genéticos

3. Diseño de la solución de un problema

mediante AGs

Cuando queremos resolver un problema mediante AGs debemos determinar
un conjunto de especificaciones clave:

Representación de los individuos:
¿cómo representamos una solución
de nuestro problema mediante cromosomas?, ¿a partir de un conjunto de
cromosomas dado, cómo obtenemos una solución? Deberemos determinar
de qué forma se traduce el fenotipo en genotipo y viceversa.

Función de fitness:
¿cómo medimos la capacidad de supervivencia de un
individuo, sus posibilidades de procrear y transferir la información de sus
genes a la próxima generación? En el dominio de las soluciones debemos
poder medir qué tan buena es cada solución con relación a las demás.

Mecanismo de selección:
tenemos toda una población evaluada según
el fitness y debemos elegir a los individuos que serán padres de la próxima
generación. No es tan sencillo como elegir los M mejores. Veremos algunas
formas de realizar una selección que, si bien premia a los mejores, no deja
de dar la posibilidad azarosa de que uno de los peores individuos sea padre,
como sucede en la naturaleza.

Operadores de variación y reproducción:
los operadores básicos son
las cruzas y mutaciones. Sin embargo, a pesar de que limitemos el estudio
sólo a estos operadores, veremos varias formas de aplicarlos. A partir de los
operadores podemos reproducir y obtener la nueva población. Durante la
reproducción también tenemos que considerar algunas opciones.

4. Representación de los individuos

El primer aspecto a resolver es la codificación del problema en un
alfabeto finito. Tradicionalmente se han empleado cadenas binarias, pero
recientemente se están empleando esquemas más flexibles. Deberemos
encontrar la forma de pasar desde el espacio del genotipo al espacio del
fenotipo como muestra la Figura 1.
Para los AGs utilizamos la base canónica {0, 1} en cadenas de
longitud fija y finita para representar soluciones de nuestro problema. Lo

Inteligencia Computacional - FICH-UNL

4

Computación Evolutiva: Algoritmos Genéticos

Figura 1. Representación de los individuos. Buscamos la forma de codificar
soluciones en cromosomas y viceversa.

que representamos en estas cadenas depende de la aplicación. Podemos
representar las conexiones, componentes y valores de éstos para un circuito
electrónico; las líneas del código de un programa; los pesos y conexiones
estructurales de una red neuronal y una infinidad de ejemplos más. Entre
estos también encontramos a los coeficientes de un filtro ARMA o de un
sistema no lineal.

Vamos a utilizar el caso más sencillo que consiste en representar una serie
de coeficientes que describen algún sistema. Podemos utilizar un cromosoma
para cada coeficiente. El cromosoma codificará en forma binaria el valor del
coeficiente. Existen muchos métodos para codificar en forma binaria un valor
real o entero, sólo veremos el caso más sencillo.

Deberemos decidir con qué resolución queremos representar a cada
coeficiente. Cuando más bits tenga nuestra cadena más amplio será el
espacio de búsqueda. Es decir, deberemos establecer un compromiso entre
la resolución de la codificación y la cantidad de dimensiones del espacio de
búsqueda.

Suponga que necesitamos codificar un coeficiente x en el rango [a, b]

mediante un cromosoma de n bits (genes). Debemos seguir dos pasos:

1. Aplicar un factor de escala y truncamiento para convertir al real x en

un entero X perteneciente al rango [0, 2n − 1]

2. Convertir el entero X en un número binario.

Para decodificar y transformar el genotipo en fenotipo aplicamos los

pasos inversos:

1. Convertimos el número binario de la cadena del cromosoma en entero

X.

Inteligencia Computacional - FICH-UNL

5

Espacio delfenotipo4.565561.253456Espacio delgenotipo1101100101010011CodificaciónDecodificación Computación Evolutiva: Algoritmos Genéticos

2. Aplicar un factor de escala para convertir el entero X perteneciente al

rango [0, 2n − 1] en el real x en [a, b].

5. Función de fitness

Debemos obtener ahora una medida para conocer qué tan buena es la
solución de cada individuo. Esta función trabaja en el dominio del problema,
sobre el fenotipo de cada individuo. Por lo tanto para obtener el valor de
fitness para un individuo deberemos previamente hacerlo nacer, y en algunos
casos crecer, a partir de su genotipo para luego evaluar objetivamente qué tan
bueno