Algoritmos genéticos con codificación real en la optimización de funciones de una variable real (página 2)

El operador de selección o Darwiniano realiza la selección de las cadenas de acuerdo a su adaptabilidad para el posterior apareamiento.

El operador de cruzamiento o Mendeliano realiza la recombinación del material genético de dos cadenas padres.

El operador de Mutación al estilo del operador natural realiza la mutación de un gen dentro de un cromosoma o cadena a sus diferentes formas alelomorfas.

Para cada uno de estos operadores está asociado el uso de probabilidades y la generación de números aleatorios.

El AG ejecuta para un número fijo de generaciones o hasta que se satisface algún criterio de parada.

Algoritmos genéticos con codificación real En la formulación original de AG, las soluciones se han codificado usando el alfabeto binario. Sin embargo, se han aplicado codificaciones no binarias más naturales para los problemas particulares de aplicación. Entre ellas, destaca la codificación real, particularmente adecuada para problemas con parámetros en dominios continuos. Un cromosoma es un vector de números reales con un tamaño igual a la longitud del vector solución del problema. Los AG basados en este tipo de codificación se denominan AG con codificación real (AGCR).

En la actualidad, existe un creciente interés en la resolución de problemas de optimización reales usando AGCR, en campos tan diversos como la es ingeniería industrial, biotecnología, economía, control, diseño aeroespacial, y otros.

El operador de cruce juega un papel central en los AGCR. De hecho puede considerarse como una de las características que definen a estos algoritmos y es uno de los componentes a tener en cuenta para mejorar su eficacia. En el caso de los AGCR, este operador influye decisivamente sobre el nivel de diversidad en la población, y por ello, es un factor determinante para evitar el problema de la convergencia prematura. Esto explica que el principal esfuerzo en la investigación desarrollada para mejorar los AGCR se centre en la propuesta y estudio de nuevos operadores de cruce.

Operadores de cruce: Sean los dos cromosomas X = (x1,x2,…,xn) y Y = (y1, y2,…, yn) padres.

1. Cruzamiento plano (Radcliffe, 1991) Se selecciona aleatoriamente una posición i?{ 1,2,3,…,n}, entonces se obtiene un hijo H = (h1 ,h2,…,hi,…,hn) seleccionando aleatoriamente hi del intervalo [xi, yi], el resto de los componentes del hijo se toman de cualquiera de los dos

padres.

2. Cruzamiento simple (Wright, 1991; Michalelewics, 1992) Se selecciona aleatoriamente una posición i?{ 1,2,3,…,n-1}y se construyen dos nuevos hijos: H1 = (x1,x2,…,xi, yi+1, yi+2,.., yn)

H2 = (y1, y2,…,yi,xi+1,xi+2,…,xn)

3. Cruzamiento aritmético (Michalelewics, 1992) Se selecciona aleatoriamente una constante ??[0,1]y una posición i?{ 1,2,3,…,n}y se obtienen dos hijos de la siguiente forma:

H1 = (x1,x2,…, xi-1,?xi + (1-?)yi,xi+1,…, xn)

H 2 = (y1, y2,…, yi-1,?yi + (1-?)xi, yi+1,…, yn) La constante ? puede no cambiar en durante el todo el proceso, en ese caso, se trata de un cruzamiento aritmético uniforme, en caso contrario, es un cruzamiento aritmético no uniforme. 4. Cruzamiento BLX -a (Eshelman y otros, 1993) Se obtiene un hijo H = (h1 ,h2,…,hi,…,hn) dondehi se selecciona aleatoriamente del intervalo [XYmin – I *a,XYmax + I *a] siendo

xyi3 = – xi + XYmax = max(xi, yi)y XYmin = min(xi, yi),I = XYmax – XYmin , a ?[-0.25,1.25] y la posición i?{ 1,2,3,…,n}se seleccionan también aleatoriamente. El resto de los componentes del hijo se toman de cualquiera de los dos padres. Nota: El cruzamiento BLX -0.0 es igual al cruzamiento plano. 5. Cruzamiento lineal (Wright, 1991) Se toma una posición i?{ 1,2,3,…,n}aleatoriamente y se obtienen tres hijos con valores en el componente seleccionado iguales a: i i yi

yi 1 2

1 2 1 2

3 2 xi +

xi – xy1 =

xy2 = yi 3 2 1 2 El resto de los componentes de los hijos se toman de cualquiera de los dos padres.

En este tipo de cruzamiento, de los tres hijos obtenidos se seleccionan los dos con mejor aptitud.

6. Cruzamiento discreto (Muhlenbein y otros, 1993) Se toma una posición i?{ 1,2,3,…,n}aleatoriamente y se obtienen un hijo que tendrá en la posición seleccionada un número aleatorio seleccionado del conjunto formado por {xi, yi}. El resto de los componentes del hijo se toman de cualquiera de los dos padres.

{ Operadores de Mutación: Sea X = (x1,x2,…,xn)el cromosoma seleccionado para mutar y xi ?[ai,bi]el gen que mutará. En lo que sigue ' xi será el resultado de la aplicación del ' t en que ' operador de mutación a ese gen.

1. Mutación aleatoria (Michalelewics, 1992)

xi se toma aleatoriamente del intervalo [ai,bi]

2. Mutación no uniforme

Este operador dependen del número de la iteración (generación) actual

gmax es el número máximo de iteraciones (generaciones). se aplique y

xi+?(t,bi -xi ) if t =0 xi = xi+?(t,xi-ai ) if t =1 t es un número aleatorio escogido del conjunto {0,1} y: Donde ) )b t Gmax (1- ?(t, y) = y(1 – r Donde se toma aleatoriamente r?[0,1]y b es un parámetro seleccionado por el usuario, el cual determina el grado de dependencia respecto al número de iteraciones. Esta función da un valor en el rango [0, y]tal que la probabilidad de retornar un valor cercano a cero se incrementa a medida que el algoritmo avanza. El tamaño del intervalo de generación del gen debe hacerse pequeño con el paso de las iteraciones (generaciones)

En el software elaborado para la optimización de funciones de una variable real, en esta, su versión 1.0, en la representación de los cromosomas coinciden genotipo y fenotipo, evadiendo el proceso de transformar las soluciones

candidatas de una representación real a una cadena binaria y su proceso inverso, disminuyendo la pérdida de precisión al trabajar con herramientas discretas problemas continuos. El Software fue desarrollado en la plataforma Visual Studio 2005, en el lenguaje Microsoft Visual C# 2005. Fue diseñado siguiendo el paradigma orientado a objetos. Se implementan la selección por la ruleta y torneo, mutación aleatoria y no uniforme, cruzamientos aritméticos y BLX-a y una estrategia evolutiva elitista. El criterio de terminación es alcanzar una cantidad de generaciones. Pueden tratarse tanto problemas de máximo como de mínimo, funciones polinómicas, trigonométricas, exponenciales, y/o la composición de sumas, restas, productos o cocientes entre ellas. Se brindan estadísticas del proceso generacional. Esta es la ventana principal:

La siguiente figura muestra una ejecución: Se observan mejores resultados empleando cruzamiento BLX-a, mutación no uniforme y selección por la ruleta. Se ha empleado una estrategia evolutiva elitista, sembrando el mejor individuo de cada generación en la siguiente.

CONCLUSIONES 1. Es natural y no es complejo desde el punto de vista computacional la aplicación de los AGCR en problemas de optimización de funciones de una variable real. 2. La combinación de los operadores de selección por la Ruleta, cruzamiento BLX-a y mutación No Uniforme muestran mejor convergencia que otras combinaciones entre los operadores empleados. TRABAJOS FUTUROS 1. Mejorar el analizador sintáctico de expresiones empleado, de modo que se amplié la gama de funciones que se puedan procesar y su ingreso sea más cercano a la forma matemática usual. 2. Extender el análisis al caso n dimensional. 3. Implementar otros operadores genéticos y validar estadísticamente su eficiencia. BIBLIOGRAFIA 1. Francisco Herrera, Manuel Lozano, Ana M. Sánchez. Algoritmos Genéticos con Codificación Real: Operadores de Cruce Híbridos Basados en Entornos con Múltiples Descendientes. 2. F. Herrera, M. Lozano, J.L. Verdegay. Tackling real-coded genetic algorithms: operators and tools for the behavioural analysis. Artificial Intelligence Reviews 12(4): 265-319. 3. Daniel Gálvez Lio. Algoritmos Genéticos. 4. Manuel Lozano. Algoritmos genéticos con codificación real. 5. MSDN Library para Visual Studio 2005.