UNIDAD 1 ANTECEDENTES

Vista previa del material en texto

UNIDAD 1. ALGORITMOS GENÉTICOS.
En los últimos años, se ha experimentado un interés creciente en la aplicación de técnicas de inteligencia artificial al campo de la recuperación de información (RI) con el propósito de subsanar las carencias de los sistemas de RI (SRI) booleanos. En concreto, el paradigma de los algoritmos genéticos trabajan sobre una población de individuos, cromosomas, que codifican posibles soluciones al problema y adaptan dicha población en la búsqueda de soluciones mejores mediante un proceso evolutivo basado en selección natural (en forma de un proceso de selección probabilístico en el que las mejores soluciones se reproducen con mayor probabilidad que las peores) y en la aplicación de operadores genéticos, cruce y mutación, que modelan los procesos genéticos existentes en la naturaleza.
Existen diferentes formas de llevar a cabo la selección de los individuos. La más habitual consiste en obtener una distribución de probabilidad asociada a los cromosomas (habitualmente dividiendo la adaptación de cada uno entre la suma de la de toda la población), y en asociar dicha distribución a una ruleta, dando más espacio en la misma a aquellos individuos que presenten mayor probabilidad de selección (es decir, a los mejor adaptados). Esta ruleta se gira tantas veces como cromosomas existan en la población, copiando en la población intermedia el cromosoma escogido en cada caso.
Sobre esta población intermedia se aplican los operadores de cruce y mutación. El primero combina las características de dos cromosomas padre para obtener dos descendientes, mientras que el segundo provoca cambios aleatorios en único individuo para introducir diversidad en la población. Los dos tienen asociadas una probabilidad de aplicación. Los cromosomas más clásicos (usualmente empelados con cromosomas binarios) son el cruce simple en un punto (que genera un punto de cruce aleatorio e intercambia los genomas de los dos padres a ambos lados del mismo) y la mutación uniforme (que cambia el valor actual del gen por el valor complementario, 0 por 1 y 1 por 0).
Primeras investigaciones de algoritmos genéticos
El uso de ideas parecidas a los algoritmos genéticos no es nueva, algunos de sus pioneros comenzaron a experimentar en computadores digitales para simular los procesos genéticos en la década de los sesenta.
Frasser & Holland J. (1962)
Uno de los trabajos de esa época que se acerca bastante a la noción moderna de lo que hoy es los algoritmos genéticos es el trabajo de Frasser, en el cual se simula como se propagan las generaciones de individuos con fenotipos aceptables de acuerdo a una función epistática definida por él. Pero fue Holland quien en 1962 aplicará aquellas ideas en sistemas artificiales y posteriormente diera el fundamento teórico para lo que hoy se conoce como "Algoritmos genéticos" con su trabajo sobre sistemas adaptativos.
Bagley. (1967)
Uno de los primeros trabajos donde se menciona el nombre de algoritmos genéticos es el Bagley, el cual desarrolló un test para controlar las tareas a ejecutar en el juego de seis peones. El algoritmo permite encontrar el conjunto de parámetros necesarios para usar en una función de evaluación del juego y luego compararlo con algoritmos existentes. Bagley llegó a la conclusión de que su algoritmo no depende de la no linealidad del problema y se desenvuelve bien en una amplia gama de ambientes.
Rosenberg. (1967)
En 1967, Rosenberg desarrolla el primer algoritmo genético para optimización por multiobjetivos en sus trabajos de simulación biológica de poblaciones de células
Cavicchio D. (1972)
Cavicchio en el año 1972 publicó “Adaptative Search Using Simulated Evolution” en el cual aplica los algoritmos genéticos, problema de reconocimiento de imágenes y al problema de selección de modelos reconocimiento de patrones. En los trabajos de Rosenberg sobre simulación biológica aparecen uno de los primeros estudios sobre el uso de los algoritmos genéticos adaptativos, en donde los parámetros propios del algoritmo son optimizados por el mismo algoritmo, formando niveles de optimización que le permitían encontrar el conjunto de mejores valores para controlar el desenvolvimiento de células simuladas de escheriquia colli.
Hollstein
La primera disertación aplicada a problemas de optimización matemática se debe a Hollstein donde básicamente se dedica a aplicar los algoritmos genéticos para optimizar funciones de dos variables (z = f(x, y) ) usando diversos operadores genéticos (cruce, mutación, varios esquemas basados en prácticas de cría de animales y otros basados en horticultura).
Bosworth, Fee y Zeigler (1972)
En el año 1972, aparecen varios trabajos en los que se explora el uso de alfabetos de codificación máximos, en contra de lo recomendado por Holland de usar el menor alfabeto posible para cada problema. En este sentido podemos mencionar el trabajo de Bosworth, Fee y Zeigler. Llegando a la conclusión de que el uso de este tipo de codificación reduce el paralelismo implícito. Por lo que, Holland, es inapropiado llamar estos esquemas "Algoritmos genéticos".
De Jong K. (1975)
Uno de los trabajos más importantes, junto con los de Holland, que constituyen uno de los pilares fundamentales de los algoritmos genéticos, es el trabajo de De Jong titulado “An Analysis of the behaior Of a Class Of Genetic Adaptive Systems”. Su trabajo se centra en la aplicación de los algoritmos genéticos a través de la escogencia de funciones de optimización, para ello se construyó un ambiente de prueba  para cinco funciones a minimizar. Las funciones escogidas por él, presentan las siguientes características:
· Continuas / Discontinuas
· Convexas / No convexas
· Unimodales / Multimodales
· Cuadráticas / No cuadráticas
· Dimensiobalidad baja / Dimensiobalidad alta
· Determinísticas / Estocásticas.
Sus estudios pretendían ver el comportamiento de un  simple ante funciones con esas características, y poder evaluar de esa forma la influencia de los siguientes parámetros:
· Tamaño de la población
· Probabilidad de cruce
· Probabilidad de mutación
· Solape generacional
Holland J. (1975)
Jonh Holland intrigado por las características de los  mecanismos de evolución natural, en el año 1975, elabora un algoritmo  para resolver problemas en la forma como la naturaleza lo ha hecho, a través de la evolución. Así como en la naturaleza, el algoritmo resuelve el problema de encontrar buenos “cromosomas” (cadenas de dígitos binarios que representan variables de diseño) manipulando el material dentro de los cromosomas. La única información que necesita es la evaluación de cada cromosoma producido, en el ambiente en que se desenvuelve, para así seleccionar individuos más aptos, esto es aquellos con las mejores evaluaciones tienden a reproducirse más que aquellos con las peores. (Teorema fundamental de los algoritmos genéticos).
Estos algoritmos usan códigos simples y mecanismos de reproducción para resolver problemas cuya solución es extremadamente difícil usando otras técnicas.
Cruces
La idea principal del cruce se basa en que, si se toman dos individuos correctamente adaptados al medio y se obtiene una descendencia que comparta genes de ambos, existe la posibilidad de que los genes heredados sean precisamente los causantes de la bondad de los padres. Al compartir las características buenas de dos individuos, la descendencia, o al menos parte de ella, tiene una bondad mayor que cada uno de los padres por separado. Si el cruce no agrupa las mejores características en uno de los hijos es posible que la descendencia tenga peor ajuste que los padres.
CRUCE DE UN PUNTO.
Esta técnica fue propuesta por Holland, y fue muy popular durante muchos años. Hoy en día, sin embargo, no suele usarse mucho en la práctica debido a sus inconvenientes. Puede demostrarse, por ejemplo, que hay varios esquemas que no pueden formarse bajo esta técnica de cruza. Formalmente el operador de cruce por un punto puede definirse como:
1. Sea P1, P2 dos soluciones padres formadas P1[1], . . . , P1[n] y P2[1], . . . , P2[n] respectivamente
2. Generarun punto de cruce k, 1 ≤ k ≤ n
3. Las soluciones hijo C1 y C2 serán: 
a) C1 := P1[1], . . . , P1[k], P2[k + 1], . . . , P2[n] 
b) C2 := P2[1], . . . , P2[k], P1[k + 1], . . . , P1[n]
El cruce de un punto es la técnica más sencilla de cruce. Una vez seleccionados dos individuos se cortan sus cromosomas por un punto seleccionado aleatoriamente para generar dos segmentos diferenciados en cada uno de ellos: la cabeza y la cola. Se intercambian las colas entre los dos individuos para generar los nuevos descendientes. De esta manera ambos descendientes heredan información genética de los padres, tal como puede verse en la siguiente figura:
El cruce de un punto destruye esquemas en los que la longitud de definición es alta. Esto produce el denominado sesgo posicional: los esquemas que pueden crearse o destruirse por la cruza dependen fuertemente de la localización de los bits en el cromosoma.
El problema fundamental del cruce de un punto es que presupone que los bloques constructores son esquemas cortos y de bajo orden, y cuando esto no sucede (p.ej., con cadenas largas), suele no proporcionar resultados apropiados. Obviamente, las aplicaciones del mundo real suelen requerir cadenas largas y de ahí que esta cruza no se use comúnmente en dichos problemas. El cruce de un punto trata también preferencialmente algunas posiciones del cromosoma, como por ejemplo los extremos de una cadena.
CRUCE DEDOS PUNTOS.
El operador de cruce de dos puntos es similar al de un punto excepto que genera dos puntos de corte en vez de uno. Formalmente el operador de cruce por dos puntos puede describirse mediante el siguiente algoritmo:
1. Sea P1, P2 dos soluciones padres formadas P1[1], . . . , P1[n] y P2[1], . . . , P2[n] respectivamente
2. Generar dos puntos de cruce k1, k2, 1 ≤ k1 ≤ n, 1 ≤ k2 ≤ n y k1 < k2
3. Las soluciones hijo C1 y C2 serán: 
a) C1 := P1[1], . . . , P1[k1], P2[k1 + 1], . . . , P2[k2], P1[k2 + 1], . . . , P1[n] 
b) C2 := P2[1], . . . , P2[k1], P1[k1 + 1], . . . , P1[k2], P2[k2 + 1], . . . , P2[n]
Se trata de una generalización del cruce de un punto. En vez de cortar por un único punto los cromosomas de los padres como en el caso anterior se realizan dos cortes. Deberá tenerse en cuenta que ninguno de estos puntos de corte coincida con el extremo de los cromosomas para garantizar que se originen tres segmentos. Para generar la descendencia se escoge el segmento central de uno de los padres y los segmentos laterales de otro padre como lo muestra la siguiente figura:
Generalizando se pueden añadir más puntos de cruce dando lugar a algoritmos de cruce multipunto. Sin embargo existen estudios que desaprueban esta técnica propuesta por De Jong. Aunque se admite que el cruce de dos puntos aporta una sustancial mejora con respecto al cruce de un solo punto, el hecho de añadir un mayor número de puntos de cruce reduce el rendimiento del Algoritmo Genético. El problema principal de añadir nuevos puntos de cruce radica en que es más fácil que los segmentos originados sean corrompibles, es decir, que por separado quizás pierdan las características de bondad que poseían conjuntamente. Sin embargo no todo son desventajas y añadiendo más puntos de cruce se consigue que el espacio de búsqueda del problema sea explorado más a fondo.
El valor n = 2 es el que minimiza los efectos disruptivos (o destructivos) de la cruza y de ahí que sea usado con gran frecuencia. No existe consenso en torno al uso de valores para n que sean mayores o iguales a 3. Los estudios empíricos al respecto proporcionan resultados que no resultan concluyentes respecto a las ventajas o desventajas de usar dichos valores. En general, sin embargo, es aceptado que la cruza de dos puntos es mejor que la cruza de un punto.
CRUCE PROBABILISTICO O UNIFORME.
El cruce probabilístico o uniforme propone el intercambio aleatorio de bits entre los individuos padre dependiendo de una probabilidad fija p. Las variantes paramétricas del operador se obtienen considerando p entre 0 y 0,5, de acuerdo a la simetría del problema. El operador tradicional corresponde a utilizar un valor de p = 0,5. Aunque se puede implementar de muy diversas formas, la técnica implica la generación de una máscara de cruce con valores binarios. Si en una de las posiciones de la máscara hay un 1, el gen situado en esa posición en uno de los descendientes es copia del primer padre. Si por el contrario hay un 0 el gen se copia del segundo padre. Para producir el segundo descendiente se intercambian los papeles de los padres, o bien se intercambia la interpretación de los unos y los ceros de la máscara de cruce.
Tal como se puede apreciar en la figura, la descendencia contiene una mezcla de genes de cada uno de los padres. El número efectivo de puntos de cruce es fijo pero será por término medio L/2, siendo L la longitud del cromosoma (número de los alelos en representaciones binarias o de genes en otro tipo de representaciones).
Los operadores de recombinación descritos anteriormente, se utilizan para la realización de experimentos aplicados en problemas de optimización combinatoria.
Mutación
La mutación se basa en un operador básico, que brinda aleatoriedad a los individuos de una población. Si bien el operador de cruce se encarga de hacer una búsqueda en el espacio de posibles soluciones, es el operador de mutación el encargado de aumentar o reducir el espacio de búsqueda en un algoritmo genético y de proporcionar cierta variabilidad genética de los individuos.
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, 1985).
Schaffer y col. (1989) 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 solo 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 (1975) recomienda la utilización de una probabilidad de mutación del bit de l −1 , siendo l la longitud del string. Schaffer y col. (1989) utilizan resultados experimentales para estimar la tasa óptima proporcional a 1/λ0.9318l0.4535 , donde λ 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.
Existen diversos operadores de mutación.
Mutación gaussiana
La mutación gaussiana, propuesta por John Holland en 1975, funciona de la siguiente manera: dado un cromosoma x con un gen seleccionado para la mutación i, se le aplica una distribución normal N de media pi y desviación estándar s (parámetro). Dado un cromosoma p como j-ésimo de un gen seleccionado para mutación, se produce un cromosoma c de la siguiente forma:
Ci = Nδi , θ si j=i; Pi en caso contrario
Donde Nδi , θ es una distribución normal con media Pi y desviación estándar θ (parámetro). Alternativamente se puede disminuir el valor de θ a medida que aumente el número de generaciones.
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 enescoger λ individuos de entre los λ individuos que forman parte de la población en el tiempo t, y los λ individuos descendientes de los mismos. Dicho proceso se suele hacer fundamentalmente de dos formas distintas.
O bien los λ 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 2λ individuos, los λ individuos más adaptados al problema, siguiendo lo que podemos denominar un criterio de reducción elitista de grado λ. Podemos también considerar otros procedimientos de reducción que se colocan entre los anteriores, por ejemplo, si escogemos los λ1 mejores de entre padres y descendientes, escogiéndose los λ − λ1 restantes de entre los descendientes no seleccionados hasta el momento.
El concepto de reducción está ligado con el de tasa de reemplazamiento generacional, trg, 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 (1975) dicho reemplazamiento se efectuaba de 1 en 1, es decir trg = λ −1 , habitualmente dicho reemplazamiento se efectúa´ en bloque, trg = 1. De Jong (1975) 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, trg, de la población es seleccionada para ser cruzada. Los hijos resultantes podrán reemplazar a miembros de la población anterior.
Michalewicz (1992) introduce un algoritmo que denomina Algoritmo Genético modificado, MODGA, 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 λ − (r1 + r2) individuos son considerados como neutros y pasan directamente a formar parte de la población en la siguiente generación.
Concepto de programación evolutiva
Son una estrategia de optimización estocástica similar a los algoritmos genéticos, pero hacen un énfasis específico en los operadores genéticos tal y como se observan en la naturaleza y en estructura de datos que utilizan adaptada al problema. Por esto, a diferencia de los algoritmos genéticos, en la programación evolutiva no son restrictivos en cuanto a la representación del problema. Mientras en los algoritmos genéticos se hace necesaria una codificación de las soluciones del problema; en la programación evolutivo, tal representación se hace de forma directa.