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
Página siguiente |