En este video conocerás cómo se implementa un algoritmo genético básico. Este ejemplo consiste en maximizar la función "f(x y)" que está en función de dos variables definidas en los rangos para "x igual a" y "y igual a", para lo cual se desea una precisión de cuatro decimales para ambas variables y vamos a resolverlo con un algoritmo genético simple. Para iniciar, vamos a partir de un ejemplo. El primer comentario que merece este ejemplo es que parecerÃa más sencillo utilizar un método numérico en contraposición a usar el algoritmo genético simple. Si lo desean, pueden intentar algún método numérico, pero pronto notarán que, si no se selecciona un buen valor de inicio, se corre el riesgo de caer en cualquier máximo local, un pico de la gráfica, sin ser precisamente el máximo global. Cuando se conoce la gráfica del problema es relativamente sencillo elegir este valor de inicio. En los siguientes apartados mostraremos que el algoritmo genético no necesita un buen valor de inicio y, sin embargo, podrá encontrar un valor cercano al óptimo como toda metaheurÃstica. Las caracterÃsticas que deben ser tomadas en cuenta por el algoritmo genético son las siguientes: optimizar una función, en este caso, vamos a maximizar una función "f(x, y)"; número de variables independientes, "dos", "x" y "y"; la precisión en decimales a usar para cada una de las variables es de cuatro; los intervalos de cada una de las variables son los siguientes, "x" en un rango de menos tres a 12.1 y "y" de 4.1 a 5.8. Las caracterÃsticas del algoritmo genético simple para este problema son las siguientes: utilizar una representación binaria, el método de selección será un método de selección proporcional, la cruza desde un punto, la mutación es aleatoria y son necesarios parámetros del algoritmo genético. Estos parámetros son los siguientes: número de generaciones, tamaño de la población o número de individuos, la probabilidad de cruza "Pc", la probabilidad de mutación "Pm". Y, finalmente, el algoritmo genético a programar va a tener la siguiente estructura, se parte de la población inicial, en la iteración "t=0" o en la generación cero. Esta población inicial, dado que está codificada en binario, se tiene que hacer un mapeo al dominio del problema y, posteriormente, evaluar la función. Después entraremos al ciclo evolutivo, en el cual tenemos las siguientes etapas: la etapa de selección, posteriormente cruza, mutación y, después de mutación, vamos a tener una nueva población, la cual tenemos que decodificar y evaluar; aquà estaremos incrementando nuestro contador de generaciones. Este proceso se va a repetir un número determinado de generaciones, que se definió al inicio del problema. Es importante recordar que, en el algoritmo genético simple, la representación de las posibles soluciones del problema es una cadena binaria. Continuando con el ejemplo, se hará uso de la siguiente expresión para codificar las dos variables del problema, "x" y "y", en los rangos y precisión especificados. La longitud de la cadena para la variable "x" está definida como, donde el lÃmite superior es igual a 12.1, el lÃmite inferior igual a menos 3.0 y la precisión es igual a "cuatro", quedando la ecuación de la siguiente manera. Redondeando el resultado, la cadena que representará a "x" será de una longitud de 18 bits. La longitud de la cadena para la variable "y" está definida como, donde el lÃmite superior es igual a 5.8, el lÃmite inferior es 4.1 con una precisión de 4, quedando de la siguiente manera. A pesar de que el resultado casi es un entero, se redondea al siguiente entero para evitar pérdida de algunos valores del rango. La cadena que representará a "y" será de una longitud de 15 bits. Finalmente, la longitud total de la cadena que representa al cromosoma o individuo será de 33 bits. La cadena está llena, inicialmente, de asteriscos o el carácter "don't care" y, posteriormente, serán reemplazados por "ceros" y "unos" al crear la población inicial. Observemos que, de los 33 bits, 18 son para la variable "x" y 15 son para la variable "y". Para poder evaluar el problema, el caso de estudio, el problema que queremos resolver, se procede a decodificar cada variable. Esto es, para cada individuo se muestran las potencias en base "dos" correspondientes para una rápida conversión, por lo que la primera subcadena binaria quedará mapeada a un valor real dentro de los rangos definidos para "x" de la siguiente manera, donde el lÃmite superior es igual a 12.1, el lÃmite inferior es igual a menos 3.0 y el tamaño es igual a 18, que es la longitud de la cadena, 18 bits. Este resultado queda de la siguiente manera. Vamos ahora a aplicar este mismo procedimiento para realizar la decodificación de la variable "y". Para este caso, el lÃmite superior es igual a 5.8, el lÃmite inferior es igual a 4.1 y el número de bits para representar esta variable, o sea, el tamaño, es igual a 15. El resultado queda de la siguiente manera. Finalmente, con el mapeo genotipo a fenotipo, esto significa de la cadena binaria a las variables de decisión en el dominio del problema, se procede a evaluar la función para obtener su valor objetivo. Teniendo ya definido cuál es el problema a resolver, qué es lo que se está buscando y cuáles son las variables de decisión a manipular, vamos a continuar con la descripción y definición de las estructuras de datos necesarias. Las estructuras de datos principales para el algoritmo genético básico son las siguientes: cromosoma o genotipo que corresponde a cada uno de los individuos de la población, una matriz de fenotipo, valores de la función objetivo y los valores de aptitud o "fitness". Estas estructuras de datos se discuten a continuación. La estructura de datos "cromosoma", la cual representa a todos los individuos, almacena una población de enteros en una matriz de tamaño, número de individuos por longitud del individuo. Cada renglón corresponde al genotipo de un individuo considerando, tÃpicamente, valores binarios. Es imprescindible aclarar que, en el algoritmo genético simple, todos los individuos de la población deben tener la misma longitud. Las variables de decisión o fenotipo, en el algoritmo genético se obtienen aplicando algún mecanismo de mapeo de la representación del cromosoma hacia el espacio de variables de decisión. AquÃ, cada cadena contenida en la estructura de datos "cromosoma" se decodifica a un vector renglón de orden número de variables, de acuerdo al número de dimensiones en el espacio de búsqueda y que corresponde al valor del vector de variables de decisión. Las variables de decisión son almacenadas en una matriz numérica de tamaño, número de individuos por número de variables. Asà como en la estructura de datos "cromosoma", cada renglón corresponde al fenotipo de un individuo en particular. Un ejemplo de la estructura de datos "fenotipo" es la siguiente, donde "DECODE" es una función que se utiliza para realizar el mapeo del genotipo a fenotipo. Aquà se pueden tener diferentes formas de realizar el mapeo, esto es de binario a entero, de binario a entero real, código Gray a entero o código Gray a entero irreal. La función objetivo es de suma importancia en el algoritmo genético. Es usada para evaluar el desempeño de los fenotipos en el dominio del problema. Los valores de la función objetivo pueden ser escalares o, en el caso de problemas multiobjetivos, vectoriales. Es importante resaltar que los valores de la función objetivo no son necesariamente los mismos que los valores de aptitud o "fitness". Los valores de la función objetivo son almacenados en una matriz numérica de tamaño, número de individuos por número de objetivos, donde número de objetivos será igual a "uno" para los casos de optimización monoobjetivo. Un ejemplo de la estructura de datos función objetivo es la siguiente, con "OBJFUN" representando una función objetivo arbitraria. AquÃ, en este punto, se define la función del problema que se desea resolver, la cual hemos presentado al inicio de este módulo. Los valores de aptitud se derivan de los valores de la función objetivo a través de una función de escalamiento o "rankeo". Las aptitudes son escalares no negativas y son almacenadas en un vector columna de longitud, número de individuos. Un ejemplo se muestra a continuación. Nuevamente, "fitness" es una función que transforma los valores objetivos a valores de aptitud arbitraria. Ahora si, ya cuentas con las herramientas necesarias para comenzar a programar un algoritmo genético.
