articulo uriel.pdf
TRANSCRIPT
APLICACIÓN DE ALGORITMOS GENETICOS PARA LA OPTIMIZACIÓN DE FUNCIONES EN N-VARIABLES
Autor: Bernal Magallanes Uriel Ervey (ITL). Asesor: Cuevas de la Rosa
Francisco Javier (CIO)
RESUMEN
En ramas de la ciencia e ingeniería se necesita resolver problemas, los cuales consisten en optimizar una función matemática que representa el modelo del problema a resolver. La naturaleza de este tipo de problemas en algunos casos los hace intratables por los métodos analíticos existentes, o en ocasiones son difíciles de resolver por estos métodos. En este trabajo se propone utilizar un Algoritmo Genético Simple (AGS) para optimizar funciones en n-variables, utilizando codificación binaria de parámetros continuos, selección por ruleta, y mutación. INTRODUCCIÓN
Los Algoritmos Genéticos (AGs) son algoritmos de búsqueda, optimización y máquinas de aprendizaje basados en la selección natural, genética y el neo-darwinismo [2] .Fueron desarrollados por John Holland a principios de los años 70 [1]. Estos algoritmos constan de una población inicial de individuos, y también de un conjunto de operadores.
Selección: selecciona los
individuos que se van a reproducir, en base a su función de aptitud.
Cruza: intercambia el material
genético de dos individuos para generar dos nuevos individuos.
Mutación: modifica el cromosoma de un individuo que es seleccionado de manera aleatoria.
El Algoritmo Genético Simple (AGS) consiste de las siguientes etapas:
1- Generar una población aleatoria
de n individuos con una codificación binaria de l-bits.
2- Calcular la aptitud de cada individuo.
3- Seleccionar a los individuos probabilísticamente en base a su aptitud.
4- Aplicar operadores genéticos (cruza y mutación) para generar la siguiente población.
Se repiten las etapas 2, 3, y 4 hasta que cierta condición se cumpla, o se
cumpla cierto número m de generaciones.
Algunas ventajas de los AGs sobre otras técnicas de optimización se muestran a continuación:
Optimiza con un conjunto de parámetros codificados de forma continua o discreta.
El cálculo de derivadas no es requerido.
Trabaja con una población de soluciones en un espacio de búsqueda y no con un único valor.
Puede ser programado utilizando cómputo paralelo.
Puede optimizar funciones muy complejas que son difíciles de derivar analíticamente o que no son diferenciables.
Puede saltar óptimos locales. Al final del proceso iterativo se
obtiene un conjunto de soluciones y no solo una solución.
Puede trabajar con datos experimentales o datos generados numéricamente.
Optimización
Sea una función definida en un intervalo [a, b] para todas las variables independientes y sea
es un valor máximo sí
APLICACIÓN DE ALGORITMOS GENETICOS PARA LA OPTIMIZACIÓN DE FUNCIONES EN N-VARIABLES
Autor: Bernal Magallanes Uriel Ervey (ITL). Asesor: Cuevas de la Rosa
Francisco Javier (CIO)
7to. Verano Estatal de Investigación CONSEJO DE CIENCIA Y TECNOLOGÍA DEL ESTADO DE GUANAJUATO
De lo contrario es un valor mínimo sí
Por naturaleza los AGs maximizan, entonces para minimizar funciones se utiliza la siguiente propiedad:
En caso de que el rango de sea negativo en el espacio de búsqueda, se suma a la función una
constante c, de donde OBJETIVO
Desarrollar un algoritmo genético
simple, que optimice funciones en n variables con parámetros continuos. MATERIALES Y MÉTODOS Codificación binaria
La codificación utilizada para un objeto
de n-variables en una cadena binaria seria:
Figura 1) Codif icación del cromosoma
Para nuestro caso La longitud de la cadena binaria esta dada por: Decodificación
La decodificación de binario a decimal, para cada variable con precisión debe hacerse de la forma:
, donde a y b son los extremos en el intervalo cerrado [a, b].
Selección por Ruleta
Esta técnica fue propuesta por De Jong [1]. El algoritmo de la selección por ruleta consiste en los siguientes pasos:
1. Calcular la suma de los valores
esperados de cada individuo T. 2. Repetir n veces(n es el tamaño
de la población). 3. Generar un número aleatorio r
entre [0, T ]. 4. Ciclar a través de los individuos
de la población sumando los valores esperados hasta que la suma sea mayor o igual a r. El individuo que haga que esta suma exceda r será seleccionado.
Valor esperado de cada individuo: Cruza de un punto
Esta técnica fue propuesta por Holland [1], consiste en escoger de manera aleatoria un punto de corte en los dos padres, e intercambiar información genética a la derecha de este punto entre los dos individuos.
Figura 2) Operación de cruza
Mutación
La mutación se refiere a modificar el valor de una cadena que representa a un cromosoma con una probabilidad de
mutación pm. Para aplicar este operador se genera
un valor aleatorio Rm ∈ [0,1], y en cada alelo se aplica el operador de mutación invirtiendo el valor del bit, si y solo si
APLICACIÓN DE ALGORITMOS GENETICOS PARA LA OPTIMIZACIÓN DE FUNCIONES EN N-VARIABLES
Autor: Bernal Magallanes Uriel Ervey (ITL). Asesor: Cuevas de la Rosa
Francisco Javier (CIO)
7to. Verano Estatal de Investigación CONSEJO DE CIENCIA Y TECNOLOGÍA DEL ESTADO DE GUANAJUATO
Rm ≤ pm. En la mayoría de los casos pm oscila entre 0.01 y 0.02 [4]. RESULTADOS Función a maximizar
Para maximizar funciones, se probó con la función de Himmelblau.
Figura 3) Gráfica de la función de Himmelblau
Esta función tiene un máximo local en
de donde
El algoritmo genético se probó con los siguientes parámetros:
Población 20 individuos Intervalo [-1,0]
Precisión 4 bits N° generaciones 80
Pm 0.3 La mejor solución obtenida fue f=181.5875950617284. Función a minimizar
Para minimizar funciones, se probó con la siguiente función que no tiene interpretación gráfica.
Esta función tiene un mínimo en
de donde
El algoritmo genético se probó con los siguientes parámetros:
Población 20 individuos
Intervalo [-3,3] Precisión 6 bits
N° generaciones 60
Pm 0.1 La mejor solución obtenida fue f=13.420634920634921 CONCLUSIONES Y DISCUSIÓN En este trabajo se desarrolló un AGS para la optimización de funciones en n-variables. Este algoritmo se probó con funciones diferenciables y funciones que son difíciles de resolver con métodos analíticos, llegando a obtenerse buenos resultados en todas las pruebas. Algunas desventajas que presentan estos AGs:
En algunos casos convergen prematuramente.
Pueden Llegar a ser costosos computacionalmente.
REFERENCIAS BIBLIOGRÁFICAS
1. Carlos A. Coello, “Introducción a la computación evolutiva”, México D.F, 2004.
2. F. Javier Cuevas, Otoniel Gonzales, Yamily Susuky, Daniel Hernández, Martha Rocha, Noé Alcalá,”Genetic algorithms applied to optics and engineering”, México León Gto.
3. William H. Hsu, “Genetic algorithms “, USA Manhattan KS.
4. Diego Torres Armenta, “Digitalización de objetos a través de técnicas de proyección de luz estructurada y reconstrucción mediante técnicas de computación suave”, México León Gto.