Algoritmos genéticos con codificación real en la optimización de funciones de una variable real

RESUMEN Los Algoritmos Genéticos (AG) se basan en los procesos hereditarios de los organismos biológicos y el principio de la evolución natural de las especies. Procesan poblaciones de cromosomas en función de su aptitud, los cuales representan soluciones candidatas en un espacio de búsqueda de soluciones, usando operadores de selección, cruzamiento y mutación. La bibliografía referencia mayoritariamente el alfabeto binario para la codificación de los cromosomas y la aplicación de los operadores genéticos. La codificación real es natural para representar problemas con parámetros en dominios continuos. Se presenta un software para la optimización de funciones de una variable empleando AG con codificación real, de modo que, 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. Se observan mejores resultados empleando cruzamiento BLX-a, mutación no uniforme y selección por la ruleta.

INTRODUCCION

Los Algoritmos Genéticos (AG1) surgen como herramientas para la solución de complejos problemas de búsqueda y optimización, producto del análisis de los sistemas adaptativos en la naturaleza, y como resultado de abstraer la esencia de su funcionamiento.

Los métodos de búsqueda y optimización han sido objeto de estudio desde los primeros años de la computación extendiéndose desde los métodos basados en el cálculo, pasando por los métodos enumerativos, hasta llegar a los algoritmos de búsqueda aleatoria. Los métodos de búsqueda y optimización tradicionales, los basados en el cálculo, enumerativos y aleatorios puros son analizados y criticados en términos de robustez, ello no significa que no sean útiles; pudiendo servir de complemento a esquemas más robustos para la creación de híbridos.

El término Algoritmo Genético se usa por el hecho de que estos simulan los procesos de la evolución darwiniana a través del uso de operadores genéticos que operan sobre una población de individuos que “evoluciona” de una generación a otra.

DESARROLLO Los Algoritmos Genéticos (AG) son métodos de búsqueda de propósito general basados en los principios de la genética natural, es decir, son algoritmos de búsqueda basados en los mecanismos de la selección natural y la genética.

Los Algoritmos Genéticos son un ejemplo de método que explota la búsqueda aleatoria “guiada” que ha ganado popularidad en los últimos años debido a la posibilidad de aplicarlos en una gran gama de campos y a las pocas exigencias que impone al problema.

En el trabajo con AG se maneja una serie de términos “importados” de la genética natural. No siempre es adecuada la analogía, pero estos son comúnmente aceptados: 1 En el texto se utilizará AG tanto para el plural como para el singular.

En qué consisten y cómo funcionan los AG Los AG trabajan a partir de una población inicial de estructuras artificiales que van modificando repetidamente a través de la aplicación de los siguientes operadores genéticos: •

•

• Operador de Selección o Darwiniano

Operador de Cruzamiento o Mendeliano

Operador de Mutación Para utilizar los AG es necesario encontrar una posible estructura para representar las soluciones. Se busca en un espacio de estados, una instancia de esta

estructura representa un punto o un estado en el espacio de búsqueda de todas las posibles soluciones. Así, una estructura de datos en el AG consistirá en uno o más cromosomas (frecuentemente uno), el cual se representa comúnmente como una cadena de bits (existen otras representaciones). Cada cromosoma (cadena) es una concatenación de un número de subcomponentes llamados genes. La posición de un gen en el cromosoma se conoce como locus y sus valores como alelos. En la representación como cadena de bits, un gen es un bit o una cadena de bits, un locus es su posición en la cadena y un alelo es su valor (0 ó 1 si es un bit).

Al optimizar una estructura usando un AG se necesita una medida de la calidad de cada estructura en el espacio de búsqueda. La función de adaptabilidad es la encargada de esta tarea. En una maximización de funciones, la función objetivo frecuentemente actúa como la función de adaptabilidad.

Los AG realizan una maximización por defecto, para los problemas de minimización los valores de la función objetivo pueden ser negados y traslados con vistas a tomar valores positivos para producir así la adaptabilidad.

El mecanismo de un AG simple es como sigue: • El AG simple genera aleatoriamente una población de n estructuras (caden