ALGORITMO GENÉTICO SIMPLE
El Algoritmo Genético Simple, también denominado Canónico, se representa en la Figura . 1. Como se verá a continuación, se necesita una codificación o representación del problema, que resulte adecuada al mismo. Además se requiere una función de ajuste ó adaptación al problema, la cual asigna un número real a cada posible solución codificada. Durante la ejecución del algoritmo, los padres deben ser seleccionados para la reproducción, a continuación dichos padres seleccionados se cruzarán generando dos hijos, sobre cada uno de los cuales actuará un operador de mutación. El resultado de la combinación de las anteriores funciones será un conjunto de individuos (posibles soluciones al problema), los cuales en la evolución del Algoritmo Genético formarán parte de la siguiente población.
Figura 1
Codificación
Se supone que los individuos (posibles soluciones del problema), pueden representarse como un conjunto de parámetros (que denominaremos penes), los cuales agrupados forman una ristra de valores (a menudo referida como cromosoma). Si bien el alfabeto utilizado para representar los individuos no debe necesariamente estar constituido por el (0, l), buena parte de la teoría en la que se fundamentan los Algoritmos Genéticos utiliza dicho alfabeto. En términos biológicos, el conjunto de parámetros representando un cromosoma particular se denomina fenotipo. El fenotipo contiene la información requerida para construir un organismo, el cual se refiere como genotipo. Los mismos términos se utilizan en el campo de los Algoritmos Genéticos. La adaptación al problema de un individuo depende de la evaluación del genotipo. Esta última puede inferirse a partir del fenotipo, es decir puede ser computada a partir del cromosoma, usando la función de evaluación. La función de adaptación debe ser diseñada para cada problema de manera específica. Dado un cromosoma particular, la función de adaptación le asigna un número real, que se supone refleja el nivel de adaptación al problema del individuo representado por el cromosoma.
Durante la fase reproductiva se seleccionan los individuos de la población para cruzarse y producir descendientes, que constituirán, una vez. mutados, la siguiente generación de individuos. La selección de padres se efectúa al azar usando un procedimiento que favorezca a los individuos mejor adaptados, ya que a cada individuo se le asigna una probabilidad
de ser seleccionado que es proporcional a su función de adaptación. Este procedimiento se dice que está basado en la ruleta sesgada. Según dicho esquema, los individuos bien adaptados se escogerán probablemente varias veces por generación, mientras que, los pobremente adaptados al problema, no se escogerán más que de vez en cuando.
de ser seleccionado que es proporcional a su función de adaptación. Este procedimiento se dice que está basado en la ruleta sesgada. Según dicho esquema, los individuos bien adaptados se escogerán probablemente varias veces por generación, mientras que, los pobremente adaptados al problema, no se escogerán más que de vez en cuando.
Una vez seleccionados dos padres, sus cromosomas se combinan, utilizando habitualmente los operadores de cruce y mutación. Las formas básicas de dichos operadores se describen a continuación.
El operador de cruce, coge dos padres seleccionados y corta sus ristras de cromosomas en una posición escogida al azar, para producir dos subristras iniciales y dos subristras finales. Después se intercambian las subristras finales, produciéndose dos nuevos cromosomas completos (véase la Figura 2). Ambos descendientes heredan genes de cada uno de los padres. Este operador se conoce como operador de cruce basado en un punto. Habitualmente el operador de cruce no se aplica a todos los pares de individuos que han
Figura 2
sido seleccionados para emparejarse, sino que se aplica de manera aleatoria, normalmente con una probabilidad comprendida entre 0.5 y 1.0. En el caso en que el operador de cruce no se aplique, la descendencia se obtiene simplemente duplicando los padres.
El operador de mutación se aplica a cada hijo de manera individual, y consiste en la alteración aleatoria (normalmente con probabilidad pequeña) de cada gen componente del cromosoma. La Figura 3 muestra la mutación del quinto gen del cromosoma. Sí bien
Figura 3
puede en principio pensarse que el operador de cruce es más importante que el operador de mutación, ya que proporciona una exploración rápida del espacio de búsqueda, éste último asegura que ningún punto del espacio de búsqueda tenga probabilidad cero de ser examinado, y es de capital importancia para asegurar la convergencia de los Algoritmos Genéticos.
Para criterios prácticos, es muy útil la definición de convergencia introducida en este campo por De Jong en su tesis doctoral. Si el Algoritmo Genético ha sido correctamente implementado, la población evolucionará a lo largo de las generaciones sucesivas de tal manera que la adaptación media extendida a todos los individuos de la población, así como la adaptación del mejor individuo se irán incrementando hacia el óptimo global. El concepto de convergencia está relacionado con la progresión hacia la uniformidad: un gen ha convergido cuando al menos el 95 % de los individuos de la población comparten el mismo valor para dicho gen. Se dice que la población converge cuando todos los genes han convergido. Se puede generalizar dicha definición al caso en que al menos un poco de los individuos de la población hayan convergido.
La Figura 4 muestra como varía la adaptación media y la mejor adaptación en un Algoritmo Genético Simple típico.
Figura 4
A medida que el número de generaciones aumenta, es más probable que la adaptación media se aproxime a la del mejor individuo.
Ejemplo
Figura 5
Población
Tamaño de la población
Una cuestión que uno puede plantearse es la relacionada con el tamaño idóneo de la población. Parece intuitivo que las poblaciones pequeñas corren el riesgo de no cubrir adecuadamente el espacio de búsqueda, mientras que el trabajar con poblaciones de gran tamaño puede acarrear problemas relacionados con el excesivo costo computacional.
Goldberg efectuó un estudio teórico, obteniendo como conclusión que el tamaño óptimo de la población para ristras de longitud I, con codificación binaria, crece exponencialmente con el tamaño de la ristra.
Este resultado traería como consecuencia que la aplicabilidad de los Algoritmos Genéticos en problemas reales sería muy limitada, ya que resultarían no competitivos con otros métodos de optimización combinatoria. Alander, basándose en evidencia empírica sugiere que un tamaño de población comprendida entre l y 21 es suficiente para atacar con éxito los problemas por el considerados.
Población inicial
Habitualmente la población inicial se escoge generando ristras al azar, pudiendo contener cada gen uno de los posibles valores del alfabeto con probabilidad uniforme. Nos podríamos preguntar que es lo que sucedería si los individuos de la población inicial se obtuviesen como resultado de alguna técnica heurística o de optimización local. En los pocos trabajos que existen sobre este aspecto, se constata que esta inicialización no aleatoria de la población inicial, puede acelerar la convergencia del Algoritmo Genético. Sin embargo en algunos casos la desventaja resulta ser la prematura convergencia del algoritmo, queriendo indicar con esto la convergencia hacia óptimos locales.
Función objetivo
Dos aspectos que resultan cruciales en el comportamiento de los Algoritmos Genéticos son la determinación de una adecuada función de adaptación o función objetivo, así como la codificación utilizada.
Idealmente nos interesaría construir funciones objetivo con "ciertas regularidades", es decir funciones objetivo que verifiquen que para dos individuos que se encuentren cercanos en el espacio de búsqueda, sus respectivos valores en las funciones objetivo sean similares. Por otra parte una dificultad en el comportamiento del Algoritmo Genético puede ser la existencia de gran cantidad de óptimos locales, así como el hecho de que el óptimo global se encuentre muy aislado.
La regla, general para construir una buena función objetivo es que ésta debe reflejar el valor del individuo de una manera "real", pero en muchos problemas de optimización combinatoria, donde existe gran cantidad de restricciones, buena parte de los puntos del espacio de búsqueda representan individuos no válidos.
Para este planteamiento en el que los individuos están sometidos a restricciones, se han propuesto varias soluciones. La primera sería la que podríamos denominar absolutista, en la que 'aquellos individuos que no verifican las restricciones, no son considerados como tales, y se siguen efectuando cruces y mutaciones hasta obtener individuos válidos, o bien, a dichos individuos se les asigna una función objetivo igual a cero.
Otra posibilidad consiste en reconstruir aquellos individuos que no verifican las restricciones. Dicha reconstrucción suele llevarse a cabo por medio de un nuevo operador que se acostumbra a denominar reparador.
Otro enfoque está basado en la penalización de la función objetivo. La idea general consiste en dividir la función objetivo del individuo por una cantidad (la penalización) que guarda relación con las restricciones que dicho individuo viola. Dicha cantidad puede simplemente tener en cuenta el número de restricciones violadas ó bien el denominado costo esperado de reconstrucción, es decir el coste asociado a la conversión de dicho individuo en otro que no viole ninguna restricción.
Otra técnica que se ha venido utilizando en el caso en que la computación de la función objetivo sea muy compleja es la denominada evaluación aproximada de la función objetivo. En algunos casos la obtención de n funciones objetivo aproximadas puede resultar mejor que la evaluación exacta de una única función objetivo (supuesto el caso de que la evaluación aproximada resulta como mínimo n veces más rápida que la, evaluación exacta).
Un problema habitual en las ejecuciones de los Algoritmos Genéticos surge debido a la velocidad con la que el algoritmo converge. En algunos casos la convergencia es muy rápida, lo que suele denominarse convergencia prematura, en la cual el algoritmo converge hacia óptimos locales, mientras que en otros casos el problema es justo el contrario, es decir se produce una convergencia lenta del algoritmo. Una posible solución a estos problemas pasa por efectuar transformaciones en la función objetivo. El problema de la convergencia prematura, surge a menudo cuando la selección de individuos se realiza de manera proporcional a su función objetivo. En tal caso, pueden existir individuos con una adaptación al problema muy superior al resto, que a medida que avanza el algoritmo "dominan" a la población. Por medio de una transformación de la función objetivo, en este caso una comprensión del rango de variación de la función objetivo, se pretende que dichos "superindividuos" no lleguen a dominar a la población.
El problema de la lenta convergencia del algoritmo, se resolvería de manera análoga, pero en este caso efectuando una expansión del rango de la función objetivo.
La idea de especies de organismos, ha sido imitada en el diseño de los Algoritmos Genéticos en un método propuesto por Goldberg y Richardson, utilizando una modificación de la función objetivo de cada individuo, de tal manera que individuos que estén muy cercanos entre sí devalúen su función objetivo, con objeto de que la población gane en diversidad.
Función
Selección
La función de selección de padres más utilizada, es la denominada función de selección proporcional a la función objetivo, en la cual cada individuo tiene una, probabilidad de ser seleccionado como padre que es proporcional al valor de su función objetivo.
Denotando por (p super prop sub j,t) la probabilidad de que el individuo (I super j sub t) sea seleccionado como padre, se tiene que:
Función
Esta función de selección es invariante ante un cambio de escala, pero no ante una traslación.
Una de las maneras de superar el problema relacionado con la rápida convergencia proveniente de los superindividuos, que surge al aplicar la anterior función de selección, es el efectuar la selección proporcional al rango del individuo, con lo cual se produce una repartición más uniforme de la probabilidad de selección, tal y como se ilustra en la Figura 6. Si denotamos por rango(g(I super j sub t)) el rango de la función objetivo del individuo (I super j sub t) cuando
Figura 6
los individuos de la población han sido ordenados de menor a mayor (es decir el peor individuo tiene rango 1, mientras que el individuo con mejor función objetivo tiene rango lambda), y sea (p super rango sub j,t) la probabilidad de que el individuo (I super j sub t) sea seleccionado como padre cuando la selección se efectúa proporcionalmente al rango del individuo, se tiene que
Función
La suma de los rangos, lambda(lambda + 1)/2, constituye la constante de normalización.
La función de selección basada en el rango es invariante frente a la translación y al cambio de escala.
Otro posible refinamiento del modelo de selección proporcional, es el modelo de selección del valor esperado, el cual actúa de la manera siguiente: para, cada individuo If, se introduce un contador, inicialiazado en g(I super j sub t)/gt, donde, gt denota la media, de. ) a función objetivo en la generación t. Cada vez que el individuo (I super j sub t) es seleccionado para el cruce, dicho contador decrece en una cantidad c (c pertenece a (0, 5;.1)). El individuo en cuestión dejará de poder ser seleccionado en esa generación, cuando su contador sea negativo.
Un esquema de selección, introducido por Brindle, y que empíricamente ha proporcionado buenos resultados, es el denominado muestreo estocástico con reemplazamiento del resto, en el cual cada individuo es seleccionado un número de veces que coincide con la parte entera del número esperado de ocurrencias de dicho suceso, compitiendo los individuos por los restos. Es decir, si denotamos por n(I super j sub t) el número de veces que el individuo (I super j sub t) es seleccionado para el cruce, tenemos que:
Función
Baker introduce un método denominado muestreo universal estocástico, el cual utiliza un único giro de la ruleta siendo los sectores circulares proporcionales a la función objetivo. Los individuos son seleccionados a partir de marcadores (véase Figura 7), igualmente espaciados y con comienzo aleatorio.
Efectuando un paralelismo con los métodos de muestreo estadísticos, este último tipo
Figura 7
de selección de padres se relaciona con el muestreo sistemático, mientras que la selección proporcional a la función objetivo, está basada en el muestreo estratificado con fijación proporcional al tamaño. También el procedimiento de selección que hemos denominado muestreo estocástico con reemplazamiento del resto, mantiene un paralelismo con el muestreo estratificado con fijación de compromiso.
En el modelo de selección elitista se fuerza a que el mejor individuo de la población en el tiempo t, sea seleccionado como padre.
La selección por torneo, constituye un procedimiento de selección de padres muy extendido y en el cual la idea consiste en escoger al azar un número de individuos de la población, tamaño del torneo, (con o sin reemplazamiento), seleccionar el mejor individuo de este grupo, y repetir el proceso hasta que el número de individuos seleccionados coincida con el tamaño de la población. Habitualmente el tamaño del torneo es 2, y en tal caso se ha utilizado una versión probabilística en la cual se permite la selección de individuos sin que necesariamente sean los mejores.
Una posible clasificación de procedimientos de selección de padres consistirá en: métodos de selección dinámicos, en los cuales las probabilidades de selección varían de generación a generación, (por ejemplo la selección proporcional a la función objetivo), frente a métodos de selección estáticos, en los cuales dichas probabilidades permanecen constantes (por ejemplo la selección basada en rangos).
Si se asegura que todos los individuos tienen asignada una probabilidad de selección distinta de cero el método de selección se denomina preservativo. En caso contrario se acostumbra a denominarlo extintivo.
Cruce
El Algoritmo Genético Canónico descrito anteriormente utiliza el cruce basado en un punto, en el cual los dos individuos seleccionados para jugar el papel de padres, son recombinados por medio de la selección de un punto de corte, para posteriormente intercambiar las secciones que se encuentran a la derecha de dicho punto.
Se han investigado otros operadores de cruce, habitualmente teniendo en cuenta más de un punto de cruce. De Jong investigó el comportamiento del operador de cruce basado en múltiples puntos, concluyendo que el cruce basado en dos puntos, representaba una mejora mientras que añadir más puntos de cruce no beneficiaba el comportamiento del algoritmo. La ventaja de tener más de un punto de cruce radica en que el espacio de búsqueda puede ser explorado más fácilmente, siendo la principal desventaja el hecho de aumentar la probabilidad de ruptura de buenos esquemas.
En el operador de cruce basado en dos puntos, los cromosomas (individuos) pueden contemplarse como un circuito en el cual se efectúa la selección aleatoria de dos puntos, tal y como se indica en la Figura 8.
Figura 8
Desde este punto de vista, el cruce basado en un punto, puede verse como un caso particular del cruce basado en dos puntos, en el cual uno de los puntos de corte se encuentra fijo al comienzo de la ristra que representa al individuo. Véase Figura,9.
En el denominado operador de cruce uniforme (Syswerda) cada gen, en la descendencia se crea copiando el correspondiente gen de uno de los dos padres, escogido de acuerdo ' a una "máscara de cruce" generada aleatoriamente. Cuando existe un l en la "máscara de cruce", el gen es copiado del primer padre, mientras que cuando exista un 0 en la
Figura 9
"máscara de cruce", el gen se copia del segundo padre, tal y como se muestra en la Figura 10. En la literatura, el término operador de cruce uniforme se relaciona con la obtención
Figura 10
de la "máscara de cruce" uniforme, en el sentido de que cualquiera de los elementos del alfabeto tenga asociada la misma probabilidad. Hablando en términos de la teoría de la probabilidad la máscara de cruce está compuesta por una muestra aleatoria de tamaño A extraída de una distribución de probabilidad de Bernouilli de parámetro l/2.
Si tuviésemos en cuenta el valor de la función de adaptación de cada padre en el momento de generar la "máscara de cruce", de tal manera que cuanto mayor sea la función de adaptación de un individuo, más probable sea heredar sus características, podríamos definir, véase Larrañaga y Poza [26], un operador de cruce basado en la función objetivo, en el cual la "máscara de cruce" se interpreta como una muestra aleatoria de tamaño l proveniente de una distribución de Bernouilli de parámetro
Función
donde (I super j sub t) y I(super i sub t) denotan los padres seleccionados para ser cruzados.
El concepto de "máscara de cruce" puede también servir para representar los cruces basados en un punto y basados en múltiples puntos, tal y como se muestra en Figura 11.
Sirag y Weiser, modifican el operador de cruce en el sentido del Simulated Annealing. De esta manera el operador de cruce se modifica definiendo un umbral de energía H. y una temperatura T, las cuales influencian la manera en la que se escogen los bits individuales. Según el operador propuesto el bit (i + 1)-ésimo se tomará del padre opuesto al que se ha tomado el bit i-ésimo, con probabilidad exp( . (tetha sub c)/T), donde T es el parámetro "temperatura" el cual, al igual que en Simulated Annealing, decrecerá lentamente por medio de un programa de enfriamiento. Con altas temperaturas el comportamiento se asemeja al del operador de cruce uniforme, es decir con probabilidad cercana a la unidad los bits se van escogiendo alternativamente de cada padre. Por otra parte cuando el valor
Figura 11
del parámetro temperatura se acerca a cero el hijo "resultante coincide prácticamente con uno de los padres.
Existen otros operadores de cruce específicos para un determinado problema como son, por ejemplo, los definidos para el problema del agente de comercio.
Por otra parte, la idea de que el cruce debería de ser más probable en algunas posiciones ha sido descrita por varios autores (Schaffer y Morishima, Holland, Davis, Levenick).
Mutación
La mutación se considera un operador básico, que proporciona un pequeño elemento de aleatoriedad en la vecindad (entorno) de los individuos de la población. Si bien se admite que el operador de cruce es el responsable de efectuar la búsqueda a lo largo del espacio de posibles soluciones, también parece desprenderse de los experimentos efectuados por varios investigadores que el operador de mutación va ganando en importancia a medida que la población de individuos va convergiendo (Davis).
Schaffer y col. encuentran que el efecto del cruce en la búsqueda es inferior al que previamente se esperaba. Utilizan la denominada evolución primitiva, en la cual, el proceso evolutivo consta tan sólo de selección y mutación. Encuentran que dicha evolución primitiva supera con creces a una evolución basada exclusivamente en la selección y el cruce. Otra conclusión de su trabajo es que la determinación del valor óptimo de la probabilidad de mutación es mucho más crucial que el relativo a la probabilidad de cruce.
La búsqueda del valor óptimo para la probabilidad de mutación, es una cuestión que ha sido motivo de varios trabajos. Así, De Jong recomienda la utilización de una probabilidad de mutación del bit de (l super -1), siendo l la longitud del string. Schaffer y col. utilizan resultados experimentales para estimar la tasa óptima proporcional a l /(lambda super 0.9318),(l super 0.4535), donde lambda denota el número de individuos en la población.
Si bien en la mayoría de las implementaciones de Algoritmos Genéticos se asume que tanto la probabilidad de cruce como la de mutación permanecen constantes, algunos autores han obtenido mejores resultados experimentales modificando la probabilidad de mutación a medida que aumenta el número de iteraciones. Pueden consultarse los trabajos de Ackley, Bramlette, Fogarty y Michalewicz y Janikow.
Reducción
Una vez obtenidos los individuos descendientes de una determinada población en el tiempo t, el proceso de reducción al tamaño original, consiste en escoger lambda individuos de entre los Lambda individuos que forman parte de la población en el tiempo t, y los lambda individuos descendientes de los mismos. Dicho proceso se suele hacer fundamentalmente de dos formas distintas.
O bien los lambda individuos descendientes son los que forman parte de la población en el tiempo t + 1, es lo que se denomina reducción simple, o bien se escogen de entre los 2lambra individuos, los lambda individuos más adaptados al problema, siguiendo lo que podemos denominar un criterio de reducción elitista de grado lambda. Podemos también considerar otros procedimientos de reducción que se colocan entre los anteriores, por ejemplo, si escogemos los (lambda sub 1) mejores de entre padres y descendientes, escogiéndose los lambda . (lambda sub 1)y restantes de entre los descendientes no seleccionados hasta el momento.
El concepto de reducción está ligado con el de tasa de reemplazamiento generacional, (t sub rg) es decir en el porcentaje de hijos generados con respecto del tamaño de la, población.
Si bien en la idea primitiva de Holland [22] dicho reemplazamiento se efectuaba, de l en 1, es decir (t sub gr)=(lambda super -1), habitualmente dicho reemplazamiento se efectúa en bloque, (t sub gr)= 1. De Jong [13] introdujo el concepto de tasa de reemplazamiento generacional con el objetivo de efectuar un solapamiento controlado entre padres e hijos. En su trabajo, en cada paso una proporción, t,~, de la población es seleccionada para ser cruzada. Los hijos resultantes podrán reemplazar a miembros de la población anterior. Este tipo de Algoritmos Genéticos se conocen bajo el nombre de SSGA (Steady State Genetie Algorithm), un ejemplo de los cuales lo constituye GENITOR (Whitley y Kauth, Whitley).
Michalewicz introduce un algoritmo que denomina Algoritmo Genético Modificado, (MOD sub GA), en el cual para llevar a cabo el reemplazamiento generacional, selecciona al azar r1 individuos para la reproducción, así como r2 individuos (distintos de los anteriores) destinados a morir. Estas selecciones aleatorias tienen en consideración el valor de la función objetivo de cada individuo, de tal manera que cuanto mayor es la función objetivo, mayor es la probabilidad de que sea seleccionado para la reproducción, y menor es la probabilidad de que dicho individuo fallezca. El resto de los lambda . (r1 + r2) individuos son considerados como neutros y pasan directamente a formar parte de la población en la siguiente generación.
Algoritmos Genéticos Paralelos
En este apartado se introducirán tres maneras diferentes de explotar el paralelismo de los Algoritmos Genéticos, por medio de los denominados modelos de islas. Para una profundización sobre el tema puede consultarse Stender.
Modelos de islas.
La idea básica consiste en dividir la población total en varias subpoblaciones en cada una de las cuales se lleva, a cabo un Algoritmo Genético. Cada cierto número de generaciones, se efectúa un intercambio de información entre las subpoblaciones, proceso que se denomina migración. La introducción de la migración hace que los modelos de islas sean capaces de explotar las diferencias entre las diversas subpoblaciones, obteniéndose de esta manera una fuente de diversidad genética. Cada subpopulación es una "isla", definiéndose un procedimiento por medio del cual se mueve el material genético de una "isla" a otra. La determinación de la, tasa de migración, es un asunto de capital importancia, ya que de ella puede depender la convergencia prematura de la búsqueda.
Se pueden distinguir diferentes modelos de islas en función de la comunicación entre las
subpoblaciones. Algunas comunicaciones típicas son las siguientes:
- Comunicación en estrella, en la cual existe una subpoblación que es seleccionada como maestra (aquella que tiene mejor media en el valor de la función objetivo), siendo las demás consideradas como esclavas. Todas las subpoblaciones esclavas mandan sus h1 mejores individuos (h1, > 1) a la subpoblación maestra la cual a su vez manda sus h2 mejores individuos (h2 > 1) a cada una de las subpoblaciones esclavas. Véase Figura 12.
Figura 12
- Comunicación en red, en la cual no existe una jerarquía entre las subpoblaciones, mandando todas y cada una de ellas sus h3 (h3 > 1) mejores individuos al resto de las subpoblaciones. Véase Figura 13.
Figura 13
- Comunicación en anillo, en la cual cada subpoblación envía sus h4 mejores individuos (h4 > 1), a una población vecina, efectuándose la migración en un único sentido de flujo. Véase Figura 14.
El modelo de islas ha sido utilizado por varios autores (Whitley y Starkweather, Gorges-Schleuter, Tanese).
Figura 14
La lógica borrosa trata de acercar la matemática al lenguaje impreciso del hombre común. El ser humano se maneja habitualmente con conceptos vagos , los cuales no pueden ser representados por la matemática tradicional.
Si se pregunta a una serie de personas acerca del estado del clima , es factible que las respuestas sean del tipo:
- "Hace mucho calor".
- "Hace frio"
- "Hoy llovió mucho"
- "No llovió casi nada: Apenas unas gotitas"
Si alguien responde a la pregunta en forma concreta , su respuesta se parecería a :
"En este momento hay 30 grados centigrados y se espera que para el resto del día la temperatura se eleve hasta los 35 grados , para luego decaer a 20 grados a lo largo dela noche"
Este tipo de respuesta parece extractada del parte meteorológico del noticiero. Esperamos oír algo similar cuando miramos la televisión , pero no tenemos la expectativa de hacerlo cuando le preguntamos al compañero de trabajo que acaba de llegar si hace calor afuera del edificio.
Tenemos entonces que el hombre se maneja con términos vagos para muchas de las acciones de su vida. Una matemática estructurada para trabajar con conceptos precisos no puede entonces representar estos conceptos. La lógica borrosa trata de poder incorporar métodos para que conceptos vagos puedan ser utilizados como funciones matemáticas.
Esta ha tenido una utilidad práctica inmediata en los mecanismos de control de las maquinarias. La lógica borrosa no es un mecanismo de optimización en si mismo , pero vuelve mas flexibles a los sistemas de control de los dispositivos electrónicos , por lo que podríamos decir que se trata de un método optimizado de control.. La difusión que ha tenido en el mundo se le debe en gran parte a la incorporación que han hecho los japoneses durante la década de los 80's de estas técnicas en los productos que comercializan mundialmente , en especial los electrodomésticos. (No es raro ver un lavarropas o una heladera de marca japonesa con el logotipo de Fuzzy Logicincorporado). Si se utiliza lógica borrosa , un dispositivo automático puede ser programado con órdenes del tipo expuesto en el Cuadro GA6
Tipo de Órdenes plausibles de ser implementadas en un contexto de lógica borrosa
La formulación de este tipo de reglas es mucho mas sencilla de entender y explicar por los expertos humanos que deben introducir las mismas. Así mismo , la programación del software es mas simple al igual que su mantenimiento.
4.1. Funciones Borrosas
La lógica borrosa trabaja con las llamadas funciones borrosas , las cuales permiten efectuar las condiciones descriptas precedentemente.
Ejemplo: Para definir la función " mucho " dentro de una serie de valores se procede de la siguiente manera:
- Se toma la serie , se la ordena de mayor a menor y se extrae el valor mas grande y el valor mas chico. Estos valores corresponden al límite superior y al límite inferior de la serie.
Tenemos entonces que dada una serie variando de a0 hasta an elementos:
Ecuación 3
- Se establece como amplitud de la serie la diferencia del límite superior y el inferior:
Ecuación 4
- La función " mucho " queda definida como:
Ecuación 5
En una serie de números naturales , cuyos valores estén entre 0 y 1000 ; A=(LS-LI) ; A=(1000-0) ; A=1000
La función " mucho " fue definida como x/A , por lo que variará desde 0/1000 para x=0 hasta 1000/1000 para x=1000. Tendremos entonces un rango de valores entre 0 y 1.
Ecuación 6
Para facilitar los cálculos , si la serie no comienza de 0 o contiene valores negativos, conviene convertirla en serie de números positivos sumando a cada término el valor máximo negativo.
Ejemplo: la serie de {-3 -2 -1 0 1 2 3 4 5} puede ser convertida en {0 1 2 3 4 5 6 7 8} sumándole 3 a todos los términos.
La serie {3,4,5,6} puede ser convertida en {0,1,2,3} restándole 3 a todos los términos.
Por ello , la ecuación 3 se transforma en:
Ecuación 7
Donde LI0 y LS0 representan los límites originales. Estos límites se normalizan a LS1 y LI1 llevando la serie al rango {0..n}.
Ecuación 8
Veamos un caso concreto:
Supongamos la siguiente serie de temperaturas:
ÍTEM
( ti )
|
HORA
|
TEMPERATURA (GRADOS CELSIUS)
|
1
|
9
|
3
|
2
|
10
|
5
|
3
|
11
|
7
|
4
|
12
|
9
|
5
|
13
|
11
|
6
|
14
|
14
|
7
|
15
|
16
|
8
|
16
|
18
|
9
|
17
|
22
|
10
|
18
|
25
|
11
|
9
|
27
|
12
|
10
|
29
|
13
|
11
|
30
|
14
|
12
|
32
|
15
|
13
|
33
|
16
|
14
|
34
|
17
|
15
|
35
|
18
|
16
|
34
|
19
|
17
|
30
|
20
|
18
|
25
|
La pregunta que se sesea que se responda es ¿Hizo mucho calor a las 16 hs?. Esta pregunta es imposible de responder por los métodos tradicionales ya que la computadora solo puede retornar el valor 34 , pero no discriminar si eso es mucho o no. veamos como trabaja entonces la función " mucho "
Ecuación 9
Observamos que en definitiva la función " mucho " retorna un número representativo del 96,85%. Cuanto mas se acerque el número a 1 o 100% mas valedera será la afirmación. Cuanto mas se acerque a 0 , menos valedera será la misma. Solo en el caso que el resultado sea 0 o 1 (0% o 100%) se puede decir taxativamente que el enunciado es verdadero o falso., blanco o negro. Todos los valores intermedios caen bajo la categoría de "gris ". Un valor tendrá un " gris mas oscuro " ( que lo acercará al negro ) cuando su valor tienda a 1 . De la misma forma , será un " gris mas claro " ( que lo acercará al blanco ) si tiende a 0. No existen , entonces límites precisos para las categorías. volviéndose imprecisos los mismos ( de ahí la nomenclatura de lógica borrosa )
Dado que la función se acerca al 100% obtendremos como resultado que efectivamente hizo mucho calor a la hora señalada.
De la misma manera ,la función " Poco " puede ser descripta como la inversa de la función " mucho " , por lo que tendremos que :
Ecuación 10
Ecuación 11
Dado que el resultado de la función se acerca al 0% obtendremos como resultado que NO hizo poco calor a la hora señalada.
4.2. Algoritmos Genéticos basados en Lógica borrosa
Existe la posibilidad de planear la arquitectura de un GA para que sus funciones de convergencia y control, así como sus operadores genéticos estén basados en lógica borrosa. El GA estaría entonces programado para la supervivencia ante entornos borrosos. Esto acarrearía por un lado la ventaja de la programación de las mismas, aunque tendría un efecto en la supervivencia indistinta de ciertos especímenes con similar valor de la función borrosa aunque diferente valor absoluto. Ejemplo: Si se programa el GA para seleccionar los especímenes con valores " altos " , esto dará igual ponderación a un ejemplar con un 90% de performance (de la función "alto" ) que a uno con el 92% de la misma función.(Ambos son "altos").
Sin lógica borrosa el segundo ejemplar sería mas competitivo que el primero y lo aniquilaría. Dado que el efecto de utilizar o no esta lógica cambia la arquitectura del GA , su implementación no es en si misma ni buena ni mala , dependiendo de los objetivos del programador y de los resultados esperados.
Las diferencias entre un GA con y sin lógica borrosa pueden ser apreciadas en el Cuadro GA7
Cuadro GA7 Diferencias entre un GA con y sin lógica borrosa
Ejemplos de Aplicación
Ejemplo 1
Veamos cómo funciona un algoritmo genético:
Vamos a partir de una función f(x) muy sencilla:
f(x)=x2
Imagina que deseas encontrar el valor de x que hace que la función f(x) alcance su valor máximo, pero restringiendo a la variable x a tomar valores comprendidos entre 0 y 31. Aún más, a x sólo le vamos a permitir tomar valores enteros, es decir: 0,1,2,3,...,30, 31. Obviamente el máximo se tiene para x = 31, donde f vale 961. No necesitamos saber algoritmos genéticos para resolver este problema, pero su sencillez hace que el algoritmo sea más fácil de comprender.
Lo primero que debemos hacer es encontrar una manera de codificar las posibles soluciones(posibles valores de x). Una manera de hacerlo es con la codificación binaria. Con esta codificación un posible valor de x es (0,1,0,1,1). ¿Cómo se interpreta esto? Muy sencillo: multiplica la última componente (un 1) por 1, la penúltima (un 1) por 2, la anterior (un 0) por 4, la segunda (un 1) por 8 y la primera(un 0) por 16 y a continuación haz la suma: 11. Observa que (0,0,0,0,0) equivale a x = 0 y que (1,1,1,1,1) equivale a x = 31.
A cada posible valor de la variable x en representación binaria le vamos a llamar individuo. Una colección de individuos constituye lo que se denomina población y el número de individuos que la componen es el tamaño de la población. Una vez que tenemos codificada la solución, debemos escoger un tamaño de población. Para este ejemplo ilustrativo vamos a escoger 6 individuos.
Debemos partir de una población inicial. Una manera de generarla es aleatoriamente: coge una moneda y lánzala al aire; si sale cara, la primera componente del primer individuo es un 0 y en caso contrario un 1. Repite el lanzamiento de la moneda y tendremos la segunda componente del primer individuo (un 0 sí sale cara y un 1 sí sale cruz). Así hasta 5 veces y obtendrás el primer individuo. Repite ahora la secuencia anterior para generar los individuos de la población restantes. En total tienes que lanzar 5 * 6 = 30 veces la moneda.
Nuestro siguiente paso es hacer competir a los individuos entre sí. Este proceso se conoce como selección. La tabla 1 resume el proceso.
Tabla 1.- SELECCION
| (1) | (2) | (3) | (4) | (5) |
| 1 | (0,1,1,0,0) | 12 | 144 | 6 |
| 2 | (1,0,0,1,0) | 18 | 324 | 3 |
| 3 | (0,1,1,1,1) | 15 | 225 | 2 |
| 4 | (1,1,0,0,0) | 24 | 576 | 5 |
| 5 | (1,1,0,1,0) | 26 | 676 | 4 |
| 6 | (0,0,0,0,1) | 1 | 1 | 1 |
Cada fila en la tabla 1 está asociada a un individuo de la población inicial. El significado de cada columna de la tabla es el siguiente:
(1) = Número que le asignamos al individuo.
(2)= Individuo en codificación binaria.
(3) = Valor de x.
(4) = Valor de f(x).
Observa que el mejor individuo es el 5 con f = 676. Calcula la media de f y obtendrás fmed=324.3. En cuanto a la columna (5) ahora te lo explico. Una manera de realizar el proceso de selección es mediante un torneo entre dos. A cada individuo de la población se le asigna una pareja y entre ellos se establece un torneo: el mejor genera dos copias y el peor se desecha. La columna (5) indica la pareja asignada a cada individuo, lo cual se ha realizado aleatoriamente. Existen muchas variantes de este proceso de selección, aunque este método nos vale para ilustrar el ejemplo.
Después de realizar el proceso de selección, la población que tenemos es la mostrada en la columna (2) de la tabla 2. Observa, por ejemplo, que en el torneo entre el individuo 1 y el 6 de la población inicial, el primero de ellos ha recibido dos copias, mientras que el segundo cae en el olvido.
Tabla 2.- CRUCE
| (1) | (2) | (3) | (4) |
| 1 | (0,1,1,0,0) | 5 | 1 |
| 2 | (0,1,1,0,0) | 3 | 3 |
| 3 | (1,0,0,1,0) | 2 | 3 |
| 4 | (1,0,0,1,0) | 6 | 1 |
| 5 | (1,1,0,1,0) | 1 | 1 |
| 6 | (1,1,0,1,0) | 4 | 1 |
Tras realizar la selección, se realiza el cruce. Una manera de hacerlo es mediante el cruce 1X: se forman parejas entre los individuos aleatoriamente de forma similar a la selección. Dados dos individuos pareja se establece un punto de cruce aleatorio, que no es más que un número aleatorio entre 1 y 4 (la longitud del individuo menos 1). Por ejemplo, en la pareja 2-3 el punto de cruce es 3, lo que significa que un hijo de la pareja conserva los tres primeros bits del padre y hereda los dos últimos de la madre, mientras que el otro hijo de la pareja conserva los tres primeros bits de la madre y hereda los dos últimos del padre. La población resultante se muestra en la columna (2) de la tabla 3.
Tabla 3.- POBLACION TRAS EL CRUCE
| (1) | (2) | (3) | (4) |
| 1 | (0,1,0,1,0) | 10 | 100 |
| 2 | (1,1,1,0,0) | 28 | 784 |
| 3 | (0,1,1,1,0) | 14 | 196 |
| 4 | (1,0,0,0,0) | 16 | 256 |
| 5 | (1,1,0,1,0) | 26 | 676 |
| 6 | (1,0,0,1,0) | 18 | 324 |
En la columna (3) tienes el valor de x; en la siguiente tienes el valor de f correspondiente. Fíjate en que ahora el valor máximo de f es 784 (para el individuo 2), mientras que antes de la selección y el cruce era de 676. Además fmed ha subido de 324.3 a 389.3. ¿Qué quiere decir esto? Simplemente que los individuos después de la selección y el cruce son mejores que antes de estas transformaciones.
El siguiente paso es volver a realizar la selección y el cruce tomando como población inicial la de la tabla 3. Esta manera de proceder se repite tantas veces como número de iteraciones tú fijes. Y ¿cuál es el óptimo?. En realidad un algoritmo genético no te garantiza la obtención del óptimo pero, si está bien construido, te proporcionará una solución razonablemente buena. Puede que obtengas el óptimo, pero el algoritmo no te confirma que lo sea. Así que quédate con la mejor solución de la última iteración. También es buena idea ir guardando la mejor solución de todas las iteraciones anteriores y al final quedarte con la mejor solución de las exploradas.
Consideraciones adicionales
En problemas reales en los que se aplican los algoritmos genéticos, existe la tendencia a la homegeinización de la población, es decir a que todos los individuos de la misma sean idénticos. Esto impide que el algoritmo siga explorando nuevas soluciones, con lo que podemos quedar estancados en un mínimo local no muy bueno.
Existen técnicas para contrarrestar esta "deriva genética". El mecanismo más elemental, aunque no siempre suficientemente eficaz, es introducir una mutación tras la selección y el cruce. Una vez que has realizado la selección y el cruce escoges un número determinado de bits de la población y los alteras aleatoriamente. En nuestro ejemplo consiste simplemente en cambiar algunos(s) bit(s) de 1 a 0 ó de 0 a 1.
Ejemplo 2
Con la finalidad de aclarar mejor los conceptos cubiertos previamente, presentaremos ahora una sencilla aplicación del algoritmo genético a un problema de optimización:
Un grupo de financieros mexicanos ha resuelto invertir 10 millones de pesos en la nueva marca de vino "Carta Nueva". Así pues, en 4 ciudades de las principales de México se decide iniciar una vigorosa campaña comercial: México en el centro, Monterrey en el noroeste, Guadalajara en el occidente y Veracruz en el oriente. A esas 4 ciudades van a corresponder las zonas comerciales I, II, III y IV. Un estudio de mercado ha sido realizado en cada una de las zonas citadas y han sido establecidas curvas de ganancias medias, en millones de pesos, en función de las inversiones totales (almacenes, tiendas de venta, representantes, publicidad, etc.) Estos datos se ilustran en la tabla 2 y en la figura 4. Para simplificar los cálculos, supondremos que las asignaciones de créditos o de inversiones deben hacerse por unidades de 1 millón de pesos. La pregunta es: ¿en dónde se deben de asignar los 10 millones de pesos de los que se dispone para que la ganancia total sea máxima?
Inversión
(en millones) |
Beneficio I
|
Beneficio II
|
Beneficio III
|
Beneficio IV
|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0.28 | 0.25 | 0.15 | 0.20 |
| 2 | 0.45 | 0.41 | 0.25 | 0.33 |
| 3 | 0.65 | 0.55 | 0.40 | 0.42 |
| 4 | 0.78 | 0.65 | 0.50 | 0.48 |
| 5 | 0.90 | 0.75 | 0.62 | 0.53 |
| 6 | 1.02 | 0.80 | 0.73 | 0.56 |
| 7 | 1.13 | 0.85 | 0.82 | 0.58 |
| 8 | 1.23 | 0.88 | 0.90 | 0.60 |
| 9 | 1.32 | 0.90 | 0.96 | 0.60 |
| 10 | 1.38 | 0.90 | 1.00 | 0.60 |
Tabla 1. Datos obtenidos con la investigación de mercado en cada una de las regiones en estudio
1) Representación: Para poder aplicar el algoritmo genético, lo primero que necesitamos determinar es cuál será el esquema a utilizarse para representar las posibles soluciones del problema. En este caso necesitamos 4 bits (2^4 = 16) para representar cada solución, porque cada una admite 11 valores posibles (de 0 a 10). Como existen 4 valores independientes (uno por cada zona de estudio), se requieren entonces 16 bits (4 x 4) por cada cromosoma. Es importante hacer notar que se requiere una función de codificación (i.e., que transforme el valor de la inversión a binario) y una de decodificación (i.e., que realice el proceso inverso). Debido a que en este caso los 4 bits utilizados para representar una solución pueden producir más valores de los que se necesitan, se usará una función de ajuste que haga que los resultados producidos siempre se encuentren en el rango válido.
2) Función de Aptitud: Dado que el objetivo es obtener las inversiones que sumen 10, y que tengan un beneficio máximo, podemos usar la siguiente función de aptitud penalizada:
c1+c2+c3+c4F(x)=-------------500*V+1
donde c1, c2, c3 y c4 son las ganancias por zona, que se calculan de acuerdo a los valores de la tabla 2, y v es el valor absoluto de la diferencia entre la suma obtenida de las inversiones y 10. Nótese que cuando no se viole ninguna restricción (i.e., cuando la suma de inversiones sea exactamente 10) la función de aptitud no será "castigada".
3) Operadores: Se usará una cruza de 2 puntos. La probabilidad que se dará a la misma será del 80%. En cuanto a la mutación, se le asignará una probabilidad baja, que será del 1%. El tamaño de población manejado para este ejemplo será de 50 cromosomas, y se correrá el algoritmo genético durante 20 generaciones.
4) Resultados: El resultado obtenido en una corrida típica es un beneficio de 1.81 millones de pesos, correspondiente a invertir 4 millones en la zona comercial I, 3 millones en la zona II, 1 millón en la zona III y 2 millones en la zona IV. Esta es la solución óptima, la cual se obtuvo originalmente mediante programación dinámica. El tiempo que le tomó al algoritmo genético encontrar este valor fue de sólo 13 segundos. Debe hacerse notar que, en este caso, si deseáramos analizar inversiones que sumen otra cantidad, y en unidades menores al millón, el algoritmo genético tendría que modificarse de manera mínima, mientras que la programación dinámica requeriría una cantidad tal de trabajo que prácticamente se volvería inoperante.
