Computación Evolutiva
Introducción
“Yo al igual que Dios no juego al azar ni creo en la casualidad” V de Vendetta
La naturaleza encuentra brillantes soluciones a los problemas mediante la evolución continuada de las especies. Ligeras variaciones aleatorias en los genes de los descendientes, dan lugar a individuos con diferente capacidad de adaptación a su entorno. Primando la reproducción de los mejor adaptados, la especie evoluciona a formas cada vez más eficientes para sobrevivir en su entorno.
La computación evolutiva es una rama de la inteligencia artificial utilizada principalmente en problemas con espacios de búsqueda extensos y no lineales, en donde otros métodos no son capaces de encontrar soluciones en un tiempo razonable. Ésta toma su inspiración en los procesos naturales de la evolución, el hecho de que muchos científicos hayan elegido a la evolución natural como medio de inspiración para la creación de algoritmos no es nada sorprendente, ya que el poder de la evolución (la forma en la que ésta se manifiesta ) es evidente en todas las especies del planeta. Este tipo de computación ayuda a la resolución de problemas en los que su espacio de búsqueda es tan amplio que es imposible poder abarcarlo todo para entregar la solución óptima.
La evolución natural puede ser vista de la siguiente manera: se tiene un medio ambiente con una cierta población de individuos que intentan sobrevivir y reproducirse en dicho medio. La calidad (fitness) de estos individuos está dada por su medio ambiente, en donde, los mejores individuos (los más aptos) son aquellos que logran el objetivo de adaptarse al medio ambiente y por tanto reproducirse, generando con esto una descendencia capaz de adaptarse mejor al medio que sus predecesores.
La idea original de la computación evolutiva es intentar emular a la evolución natural, en donde, la calidad de los individuos en un medio ambiente es generada a través de una función, normalmente llamada función de fitness, los individuos son soluciones completas generadas normalmente al azar y se evalúan a modo de que los mejores individuos sean capaz de reproducirse y dejar descendencia (semillas o nuevas soluciones posibles), las cuales a su vez pasarán por la misma función de calidad para ver quienes podrán reproducirse en una futura generación y el proceso se repite hasta cumplir con una condición de paro.
La computación evolutiva ofrece la posibilidad de resolver problemas cuyo espacio de búsqueda sea muy complejo o tenga demasiados óptimos locales en los cuales los algoritmos tradicionales converjan demasiado rápido en una solución factible.
Historia de la computación evolutiva
La idea básica de aplicar los principios darwinianos para la automatización de solución de problemas complejos data de los años 40. Ya en 1948 Alan Turing propuso “la búsqueda de la evolución genética” y por 1962 Bremermann ya había realizado experimentos acerca de la “optimización de la evolución y la recombinación”.
Los primeros ejemplos de algoritmos genéticos aparecieron a principios de los años 60, programados en computadoras por biólogos evolutivos que buscaban explícitamente realizar modelos de aspectos de la evolución natural. A ninguno de ellos se le ocurrió que esta estrategia podría aplicarse de manera más general para la solución de diversas índoles, pero ese reconocimiento no tardaría en llegar, de hecho en palabras de Mitchell[35] “La computación evolutiva estaba definitivamente en el aire en los días formativos de la computadora electrónica”.
En 1962 H.J. Bremermann había desarrollado algoritmos inspirados en la evolución para optimización de funciones y aprendizaje automático, pero sus trabajos generaron poca reacción. En 1965 surgió un desarrollo más exitoso, cuando Ingo Rechenberg y Schwefel dieron a conocer lo que llamaron “estrategias evolutivas” [23,24]. En esta técnica no había población ni cruzamiento; un padre mutaba para producir un descendiente, y se conservaba el mejor de los dos, convirtiéndose en el padre de la siguiente ronda de mutación. Versiones posteriores introdujeron la idea de población.
El siguiente desarrollo importante en el campo vino en 1966, cuando L.J. Fogel, A.J. Owens y M.J. Walsh[19,20] introdujeron en América una técnica que llamaron programación evolutiva. En este método, las soluciones candidatas para los problemas se representaban como máquinas de estado finito sencillas; al igual que en la estrategia evolutiva de Rechenberg, su algoritmo funcionaba mutando aleatoriamente una de estas máquinas simuladas y conservando la mejor de las dos. También al igual que las estrategias evolutivas, hoy en día existe una formulación más amplia de la técnica de programación evolutiva que todavía es un área de investigación en curso. Sin embargo, lo que todavía faltaba en estas dos metodologías era el reconocimiento de la importancia del cruzamiento.
En 1962, el trabajo de John Holland [21,22] estableció las bases para desarrollos posteriores; y lo que es más importante, Holland fue también el primero en proponer explícitamente el cruzamiento y otros operadores de recombinación. Sin embargo, el trabajo fundamental en el campo de los algoritmos genéticos apareció en 1975, con la publicación del libro “Adaptation in natural and artificial systems'' por parte de Holland. Este libro fue el primero en presentar sistemática y rigurosamente el concepto de sistemas digitales adaptativos utilizando la mutación, la selección y el cruzamiento, simulando el proceso de la evolución biológica como estrategia para resolver problemas. El libro también intentó colocar a los algoritmos genéticos sobre una base teórica firme introduciendo el concepto de esquema [35,36]. Ese mismo año, la importante tesis de Kenneth De Jong “ Analisys of the behaviour of a class of genetic adaptative system” estableció el potencial de los AGs demostrando que podían desenvolverse bien en una gran variedad de funciones de prueba, incluyendo paisajes de búsqueda ruidosos, discontinuos y multimodales[30] .
Estos trabajos establecieron un interés más generalizado en la computación evolutiva. Entre principios y mediados de los 80, los algoritmos genéticos se estaban aplicando en una amplia variedad de áreas, desde problemas matemáticos abstractos como el bin-packing y la coloración de grafos hasta asuntos tangibles de ingeniería como el control de flujo en una línea de ensamble, reconocimiento, clasificación de patrones y optimización estructural etc.[30].
Al principio, estas aplicaciones eran principalmente teóricas, sin embargo, al seguir proliferando la investigación, los algoritmos genéticos migraron hacia el sector comercial, al cobrar importancia con el crecimiento exponencial de la potencia de computación y el desarrollo de Internet. Hoy en día, la computación evolutiva es un campo floreciente, y los algoritmos genéticos están resolviendo problemas de interés cotidiano en áreas de estudio tan diversas como la predicción en la bolsa y la planificación de la cartera de valores, ingeniería aeroespacial, diseño de microchips, bioquímica y biología molecular, diseño de horarios en aeropuertos y líneas de montaje y en el corazón de todo esto se halla nada más que la simple y poderosa teoría de Charles Darwin: que el azar en la variación, junto con la ley de la selección, es una técnica de resolución de problemas de inmenso poder y de aplicación casi ilimitada.
Características generales de los algoritmos evolutivos
La idea básica de todas las técnicas de los algoritmos evolutivos es la siguiente:
- · Obtener una población inicial de individuos (soluciones factibles).
- Determinar un medio ambiente para la población que cause una selección natural.
- · Determinar una función de calidad para los individuos dentro del medio ambiente.
La idea detrás de ésto es cruzar y mutar a los individuos, en la cruza se seleccionan a dos o mas individuos (padres), se toman características de los mismos y se generan nuevos individuos a partir de la combinación de las características de los padres. En la mutación se toma a un individuo mediante cierta probabilidad y se altera su código ligeramente, hasta generar a un nuevo individuo. Estos parámetros permiten entre otras cosas crear diversidad (por medio de la mutación) y explotar soluciones factibles para obtener una mejor solución (por medio de la cruza).
Cabe mencionar que el proceso de mutación y cruza es estocástico ya que al seleccionar a los individuos se requiere de la generación de números aleatorios, sin embargo, el proceso de seleccionar a los individuos más aptos mediante técnicas como ruleta o torneo sesga la búsqueda hacia zonas prometedoras del espacio de búsqueda.
La Figura muestra el pseudocódigo general de un algoritmo evolutivo:
Es fácil ver que este pseudocódigo cae dentro de la categoría de los algoritmos generate-and-test. La función de evaluación representa una estimación heurística de la solución de calidad y el proceso de búsqueda es guiada por la variación de los operadores. Los algoritmos evolutivos poseen un número de partes que pueden ayudarlo a posicionarlos, como se menciono antes dentro de los métodos generate-and-test y estos son:
- · Son basados en población, procesan varias soluciones candidato simultáneamente.
- · Usan la recombinación para mezclar la información de varios candidatos.
- · Son estocásticos.
Su esquema general se muestra en la Figura:
La representación de los candidatos puede variar significativamente, siendo las mas comunes:
- · Cadenas de String de un cierto alfabeto (algoritmos genéticos)
- · Vectores con valores reales(Estrategias evolutivas)
- · Máquinas de estado finito(Programación evolutiva)
- · Árboles(Programación genética)
Sin embargo, existen representaciones alternativas dependiendo del problema que se quiere resolver.
Componentes de los algoritmos evolutivos
Los componentes principales de los algoritmos evolutivos son los siguientes:
Representación
El primer paso de un algoritmo evolutivo es construir los candidatos. Es necesario pasar del contexto original del problema a su espacio de soluciónes donde la evolución toma su lugar, esto es , construir el fenotipo y el genotipo.
Los objetos que forman las soluciones posibles del problema son llamados fenotipos, mientras que su codificación, es decir, los individuos con los cuales trabaja el algoritmo evolutivo son llamados genotipos. El proceso de transformar un fenotipo a genotipo se le llama codificación y al proceso contrario (genotipo - fenotipo) se le conoce como decodificación, tanto al genotipo como al fenotipo se les conoce como representaciones de una solución. La Figura 4 muestra un esquema de lo anterior.
Función de calidad
El objetivo de la función de calidad es representar los requerimientos para la adaptación de los individuos en el medio ambiente. Esta función es asignada a las representaciones de los individuos (sea genotípica o fenotípica) para determinar su calidad dentro del medio ambiente y asignar su probabilidad de supervivencia o cruza dentro de la población.
Población
La población es un conjunto de soluciones (genotipos o fenotipos) en un medio ambiente, y es la unidad que evoluciona en los algoritmos evolutivos, ya que los individuos son solo elementos estáticos que no cambian o se adaptan, la evolución se da al pasar de generación en generación, aunque , por supuesto , un número mayor de individuos otorga una mayor diversidad en el espacio de solución de un problema.
Mecanismo de selección de padres
Este mecanismo es el encargado de seleccionar los individuos que podrán generar descendencia. Normalmente los individuos con una mayor calidad (definida mediante la función de calidad) tienen mayor posibilidad de ser elegidos, sin embargo, si sólo los de mejor calidad son elegidos se puede presentar la situación de encontrarse atrapado en algún óptimo local, esto es, puede que el algoritmo pierda diversidad.
Mecanismo de selección de supervivientes
Similar al mecanismo de selección de padres, con la diferencia del momento en que operan, ya que mientras la selección de padres actúa antes de generar la descendencia, el mecanismo de supervivencia actúa después de generada la descendencia y es la encargada de elegir a los individuos de mejor calidad (aunque depende del algoritmo evolutivo adaptado) para que pasen a la siguiente generación.
Operadores de variación
Su objetivo es crear nueva descendencia a partir de una anterior y con esto generar nuevas soluciones candidato. Como tal tenemos los siguientes:
Mutación
Es una pequeña variación impuesta a un individuo, este operador es siempre estocástico y su objetivo radica en brindar una mayor diversidad a la población.
Recombinación o cruza
Es el proceso de combinar dos o más individuos para generar nuevos con características similares a sus predecesores, a este proceso se le llama descendencia. Al igual que la mutación, este operador es estocástico, aunque la selección de los individuos a cruzarse puede variar, ya sea por la implementación de una ruleta de probabilidades, el uso de un torneo, etc.
El objetivo es explotar varias soluciones dadas al combinar individuos y generar nuevos.
Inicialización
Es la primera población, normalmente generada por individuos aleatorios, sin embargo, puede ser que se genere con base en una estrategia implementada para ayudar al algoritmo en el proceso de búsqueda.
Condición de término
Existen varias condiciones de terminación para los algoritmos evolutivos, entre las más populares tenemos :
- · El máximo tiempo de procesamiento permitido por el CPU.
- · Por un periodo de tiempo determinado.
- · Por un determinado número de generaciones (ciclos del algoritmo).
- · El valor de la función de aptitud de la población alcanzó el valor de un umbral (no se detectan mejoras significativas).
- · La función de calidad ha llegado a su límite (se encontró al mejor individuo o a un óptimo deseable).
Una vez terminado el algoritmo se procede normalmente a devolver aquellos individuos que maximicen o minimicen la función de calidad según sea el caso deseado.
Clasificación de la computación evolutiva
Existen diferentes paradigmas dentro de la computación evolutiva, la mayoría de ellos difiere generalmente en la representación de los individuos, aunque otras lo hacen en la forma y utilización de los componentes del algoritmo evolutivo. Las principales se presentan a continuación.
Algoritmos Genéticos
Los algoritmos genéticos fueron inicialmente concebidos por Holland como resultado de su estudio acerca del comportamiento adaptativo [28] y plasmados en su libro “Adaptation in natural and artificial system”.
Los algoritmos genéticos en su versión más estricta poseen una representación binaria, una función de calidad que les permita sobrevivir en un medio ambiente y que actúe generacionalmente, deben tener una probabilidad de mutación muy baja y hacen énfasis en una cruza inspirada genéticamente.
Representación
La parte mas difícil de trabajar con este tipo de algoritmos es su representación, si bien, los algoritmos genéticos simples requieren de una representación binaria, ello no es una regla, y es posible crear representaciones diversas, entre las mas comunes están la representación usando valores enteros y de valores de punto flotante. Sin embargo ,en este tipo de representaciones se debe tener especial cuidado en que los operadores al momento de ser aplicados sobre un individuo no generen valores inválidos. Supongamos que tenemos un individuo con representación decimal y que parte del individuo codifica una dirección como Norte, Sur , Este y Oeste, el individuo codifica esto de la siguiente manera Norte = 1, Sur =2,Este =3, Oeste = 4, entonces tenemos cuatro números posibles 1-2-3-4 , sin embargo , es posible que el operador de mutación entregue un 5 ó 6 al mutar esta sección de dicho individuo.
Selección de candidatos
La selección de los candidatos tanto para cruzarse como para formar parte de la nueva generación usualmente se logra implementando ya sea una ruleta, en la cual a cada individuo le corresponde determinada porción de probabilidad dependiendo de su contribución al total de aptitud en la población Se gira la ruleta y se selecciona al individuo correspondiente, este método asegura en cierta medida que los individuos con mejor calidad serán los elegidos para reproducción. Otro método popular es implementar torneos, en los cuales se seleccionan dos o mas individuos y se elige al mejor candidato determinado por su función de calidad, en ambas metodologías el proceso se repite hasta obtener el número de individuos requeridos para reproducción.
Es común en los algoritmos genéticos conservar de generación en generación ciertos individuos con el fin de que éstos generen descendencia, normalmente se seleccionan a los mejores de la generación anterior, los cuales reemplazan a los peores de la nueva generación (determinado por la función de calidad).
Mutación
La mutación en los algoritmos genéticos es el operador encargado de generar diversidad en la población, cambia (muta) una parte de un individuo. Normalmente se efectúa después de la recombinación o cruza. Existen diversos tipos de mutaciones, y algunas cambian dependiendo la representación de los individuos. Dentro de las más comunes tenemos las siguientes:
· Mutación Binaria: en representaciones binarias se toma cada bit por separado y se estima su probabilidad de mutar, si esta fue positiva, es decir, se mutará, cambiara su número de 0 a 1 ó de 1 a 0 según sea el caso.
· Mutación Swap: En este tipo de mutación no es necesario una representación binaria como tal, simplemente se debe seleccionar dos posiciones(alelos) de un individuo aleatoriamente y se intercambian de lugar.
· Mutación de Inserción: Parecido a la mutación swap, aquí se seleccionan dos posiciones (alelos) de un individuo aleatoriamente y se cambia la posición de uno de los allelos de tal forma que ambas estén juntas.
· Mutación de Inversión: Aquí se seleccionan dos posiciones de un individuo, se toman todos las posiciones intermedias y se invierte su orden.
Recombinación ó cruza
Para muchos el más importante de los operadores en los algoritmos genéticos. La cruza es la encargada de explotar las soluciones posibles, su función es la de generar una nueva población (crear descendencia) generación tras generación. En su forma básica selecciona dos individuos (llamados padres) , toma la información de ambos y crea un nuevo individuo con partes de información de los dos individuos seleccionados con anterioridad.
Existen diversas formas de cruzar a los individuos seleccionados, algunas inspiradas en la biología y otras propias de la representación elegida, las más comunes son las siguientes:
Recombinación de N-puntos: De la misma manera que la anterior, con la diferencia de que aquí es posible seleccionar mas de un punto.
Cruza uniforme: En este tipo de cruza se asigna una probabilidad (normalmente de 0.5) a cada parte del individuo(alelo) y se efectúa un volado, de tal manera que si gana el individuo 1, esa parte de él pasará al nuevo individuo, si pierde será el individuo 2 quien proporcione su gen. El proceso se repite para todas las partes de los individuos. Este tipo de cruza puede generar varios individuos a partir de solo dos predecesores.
Estrategias Evolutivas
Las estrategias evolutivas fueron inventadas en la década de 1960 por Rechenberg y Schwefel quienes estaban trabajando en la Universidad Técnica de Berlín en aplicaciones concernientes a la optimización de formas, ellos describieron un algoritmo básico llamado los dos eslabones de la estrategia evolutiva.
Este tipo de algoritmos trabajan con una población de individuos que pertenecen al dominio de los números reales, que mediante los procesos de mutación y de recombinación evolucionan para alcanzar el óptimo de la función objetivo.
Cada individuo de la población es una solución potencial al problema, la representación de cada individuo de la población consta de 2 tipos de variables: las variables objeto y las variables estratégicas. Las variables objeto son los posibles valores que hacen que la función objetivo alcance el óptimo global y las variables estratégicas son los parámetros mediante los que se gobierna el proceso evolutivo o, en otras palabras, las variables estratégicas indican de qué manera las variables objeto son afectadas por la mutación.
Haciendo una analogía más precisa, el genotipo en las estrategias evolutivas es el conjunto formado por las variables objeto y las variables estratégicas y el fenotipo son las variables objeto, ya que conforme se da la variación de éstas, se percibe un mejor o peor desempeño del individuo.
Las estrategias evolutivas pueden definirse como algoritmos evolutivos enfocados hacia la optimización paramétrica, teniendo como características principales que utilizan una representación a través de vectores reales, una selección de supervivientes determinística y operadores genéticos específicos de cruce y mutación.
Las estrategias evolutivas pueden dividirse en dos tipos: Simples y Múltiples.
- · Simples: Son consideradas como procedimientos estocásticos de optimización paramétrica con paso adaptativo. Esta característica las hace similares al recocido simulado. En este caso, se hace evolucionar un solo individuo usando únicamente a la mutación como operador genético. Son relativamente sencillas, y se denominan también estrategias evolutivas de dos miembros. Debido a que evoluciona un solo individuo a la vez, no son consideradas estrictamente como métodos evolutivos. A pesar de ser muy sencillas, son de gran utilidad práctica y han sido utilizadas, con algunas mejoras, para resolver problemas reales en diversas áreas.
- Múltiples: Surgen como respuesta a las debilidades de las estrategias evolutivas simples, las cuales tienden a converger hacia subóptimos. En las estrategias evolutivas múltiples existen múltiples individuos (población), y se producen en cada generación varios nuevos individuos, usando los operadores de mutación y cruza. En cuanto a los criterios de · reemplazo, siempre se usa un esquema determinístico pudiéndose utilizar una estrategia de inserción o de inclusión.
Mutación
Es el operador principal de las estrategias evolutivas, Realiza un cambio en los valores de las variables de los individuos añadiendo ruido aleatorio obtenido mediante una función de distribución Normal. Las desviaciones típicas a aplicar se encuentran dentro del mismo individuo (son calculadas a partir del individuo mismo) y coevolucionan junto con la solución.
Recombinación o cruza
En las estrategias evolutivas el cruce se realiza de una forma literalmente sencilla, simplemente se toman dos individuos y a partir de ellos se generara un nuevo individuo, el cual en cada casilla del arreglo de números reales se coloca el promedio del valor que sus predecesores tienen en la misma posición.
Programación Evolutiva
La programación evolutiva fue desarrollada originalmente para simular la evolución como un proceso de aprendizaje para poder generar inteligencia artificial. Esta rama de la computación evolutiva es prácticamente una variación de los algoritmos genéticos, donde el cambio más significativo es la representación de los individuos, puesto que aquí cada individuo de la población esta formado por una máquina de estado finito.
Desarrollada en la década de 1960 por Lawrence J. Fogel [20] , enfatiza los nexos de comportamiento entre padres e hijos, en vez de buscar emular a los operadores genéticos específicos[31]. Su objetivo principal es construir individuos que sean capaces de reconocer un cierto conjunto de entradas y proporcionar salidas correspondientes a las mismas.
El algoritmo básico de la programación evolutiva es el siguiente :
- · Generar aleatoriamente una población inicial.
- · Aplicar mutación a los individuos de la población.
- · Se calcula la aptitud de cada hijo y se usa un proceso de selección de supervivientes mediante torneo (normalmente estocástico) para determinar cuales serán las soluciones que se retendrán.
- · Se repite el proceso hasta cumplir con una condición de paro
Es importante destacar que este tipo de algoritmos no usan el operador de recombinación o cruza puesto que son una abstracción de la evolución a nivel de las especies [31] y parten de la idea de que individuos de diferentes especies pueden cruzarse.
Mutación
Existen 5 formas posibles de mutar a un individuo cuya representación sea una máquina de estado finito, estas son las siguientes:
- · Cambiar un símbolo de salida.
- · Cambiar una transición.
- · Agregar un estado.
- · Borrar un estado.
- · Cambiar el estado inicial.
Programación Genética
Este tipo de algoritmos son una variación de los algoritmos genéticos, en donde su diferencia mas sustancial es la representación de los individuos, puesto que aquí cada individuo es representado por un árbol. El objetivo principal de esta técnica de la computación evolutiva es la evolución automática de programas usando ideas basadas en la selección natural, permitiendo realizar regresión simbólica, esto es, permiten obtener además de un dato numérico predictivo, una expresión matemática en función de las variables de entrada[32].
Básicamente son una metodología automatizada inspirada por la evolución biológica para encontrar programas informáticos que mejor realicen una tarea definida por el usuario. Es por ello que son una técnica de aprendizaje de máquina particular que utiliza un algoritmo evolutivo para optimizar una población de programas informáticos según una función de calidad determinada por la habilidad de un programa para realizar una tarea computacional dada.
Tomando como base el tipo de representación de los individuos dentro de esta técnica es fácil entender su gran potencial, por ejemplo tomando en cuenta la siguiente fórmula lógica :
su representación se muestra en la Figura:
Incluso es fácil representar algún programa informático, por ejemplo , tomando como base el siguiente algoritmo :
Int i = 1
While (i< 20)
i = i+1;
su representación se muestra en la Figura:
Mutación
El operador de mutación empleado en este paradigma no difiere en gran medida al de los algoritmos genéticos, el mecanismo mas usual es seleccionar a un individuo con base en cierta probabilidad, posteriormente se seleccionara un nodo de ese individuo y se verificará su probabilidad de mutación del nodo específico, si este nodo será mutado se prosigue a realizar un cambio aleatorio en el nodo seleccionado, cuidando que esta mutación no incumpla con las normas del individuo, por ejemplo , no genere ciclos infinitos en el caso de ser un programa, o tenga cierta lógica, por ejemplo no cambie una función de tal manera que pregunte si X == X etc.
Recombinación o cruza
La idea básica de este operador en la programación genética es seleccionar dos individuos(padres), posteriormente para cada individuo seleccionar un nodo aleatoriamente, una ves teniendo esto se intercambia la información de los nodos, generando con esto dos nuevos individuos(hijos).
Programación Memética
Los algoritmos meméticos son técnicas de optimización que combinan sinérgicamente la búsqueda basada en poblaciones (algoritmos evolutivos) y las búsquedas locales (Tabú, Recosido Simulado etc.). Su idea fundamental es mantener una cierta población mediante los operadores tradicionales de los algoritmos evolutivos(cruza y mutación) e ir evolucionando estos individuos mediante mejoras significativas a cada uno con búsquedas locales, es aquí donde se diferencian de los algoritmos genéticos, puesto que en los algoritmos meméticos el individuo evoluciona constantemente al aplicarse un procedimiento meta heurístico en él, dado que tienen la capacidad de evolucionar por sí solo mediante una búsqueda local. Los diseñadores de algoritmos meméticos prefieren denominarle agente a un individuo. La Tabla muestra las diferencias entre un algoritmo genético y un memético[33]
La primera diferencia significativa entre estas dos técnicas de la computación evolutiva es la codificación de los individuos, puesto que en los algoritmos genéticos se parte de cadenas que mediante codificación se obtiene una solución (fenotipo y genotipo), sin embargo, ésta no es una restricción para los algoritmos meméticos, ya que éstos se basan en una experiencia de la persona que los esta creando. Entonces es posible ajustar cualquier tipo de modelo como individuo, en ocasiones, los individuos pueden tener algún programa o mejora significativa en ellos mismos.
En el caso de la mutación, para los demás algoritmos evolutivos esta es un proceso estocástico, sin embargo, en los meméticos se prefiere sea una mutación especializada en el problema, la cual deberá modificar a un agente (individuo) significativamente con la idea de que mejore su calidad.
El operador de cruza también se ve afectado, puesto que en los algoritmos meméticos es guiada, es decir, se pretende cruzar individuos de tal forma que su descendiente obtenga específicamente lo mejor de ambos, motivo por el cual su desarrollo y modelo depende exclusivamente del problema en cuestión, el ejemplo mas común de esto es la cruza EAX[34] (Edge Assembly Crossover) diseñada específicamente para problemas del agente viajero.
La diferencia más significativa es la aplicación de búsquedas locales para mejorar a los agentes (individuos) de la población, pues es la principal fuerza de los algoritmos meméticos, ya que sus agentes son capaces de evolucionar individualmente, al mismo tiempo que evoluciona la población gracias a los operadores de cruza y mutación. Existen diversos momentos en los cuales pueden aplicarse los operadores de búsqueda locales, normalmente se prefiere sea después de aplicar los operadores de mutación y cruza. Sin embargo, puede ocurrir al generar la población inicial, o inclusive al terminar el ciclo de generaciones. En este último caso se dice que trabaja como si un algoritmo genético diera buenas semillas a un algoritmo de búsqueda local.
Características generales
- Los algoritmos meméticos son algoritmos híbridos que incorporan conocimiento y combinan estrategias de búsqueda.
- Se potencia al mecanismo cooperativo de los algoritmos evolutivos incorporando un mecanismo guiado de competición.
- Los individuos tienen la potencialidad de intentar mejoras, y compiten entre sí por propagar su descendencia.
- En la terminología de los algoritmos meméticos, a los individuos se los denomina agentes.
- La operativa de un algoritmo memético es la de un algoritmo evolutivo tradicional, con el agregado de una búsqueda local.
Estructura
La Figura muestra la estructura general de un algoritmo memético
Aquí se puede observar las diferentes etapas en las cuales puede efectuarse la búsqueda local. Cabe señalar que cuando aparece después de los operadores ya sea de cruza o de mutación, normalmente no ocurre generación tras generación, en vez de ésto se prefiere actúe cada determinado periodo, el cual puede ser determinado por un número fijo de generaciones o por algún otro motivo tal como la detección de estancamiento en las mejoras de algunos agentes (individuos) o en la población en general.
La Figura muestra el pseudocódigo de un algoritmo memético en su aspecto mas general:
Bibliografía
[1]Wren, A., Scheduling, Timetabling and Rostering - a Special Relationship, Lecture Notes in Computer Science 1153. Springer-Verlag, Berlín, Heidelberg, New York, págs. 46-75,1996.
[2] Metaheuristics Networks “International Timetabling Competition” http://www.idsia.ch/Files/ttcomp2002/ consultado el 16-10-2010.
[3] Schaerf, Andrea, A survey of automated Timetabling, Technical Report CS-R9567, CWI - Centrum voor Wiskunde en Informática, 1995.
[4] John Fredy Franco Baquero, Eliana Mirledy Toro Ocampo, Ramón Alfonso Gallego Rendón, Problema de asignación óptima de salones resuelto con Búsqueda tabú, INGENIERÍA & DESARROLLO, Número 24 Julio-diciembre, 2008 ISSN: 0122-3461
[5] White, G. M. Chan P. W., Towards the construction of optimal examination timetables. INFOR 17 (1979), pp. 219–229.
[6] Fifher, J. G., Shier, D. R., A heuristic procedure for large-scale examination scheduling problems. Technical Report 417, Department of Mathematical Sciences, Clemson University, 1983.
[7] White, G. M., “Constrained satisfaction, not so constrained satisfaction and the Timetabling problem”. In: A Plenary Talk in the Proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling, University of Applied Sciences, Konstanz, Aug., 16–18, 2000 (2000), pp. 32–47.
[8]Burke,E.K.,Newall,J.P.,Weare,R.F.,1996b.AmemeticalgorithmforUniversity exam Timetabling. In: Burke and Ross (1996) pp. 241–250.
[9] Schaerf, Andrea, A survey of automated Timetabling, Technical Report CS-R9567, CWI - Centrum voor Wiskunde en Informática, 1995.
[10] Carter, M. W., Laporte, G., Recent developments in practical examination Timetabling. In: Burke and Ross, pp. 3–21, 1996.
[11] José Ma. Mejía Caballero , Asignación de horarios de clases universitarias mediante algoritmos, Universidad del norte división de postgrados e investigaciones en ingeniería, maestría en ingeniería industrial, Barranquilla-atlántico 2008, tesis de grado
[12]M. Carrasco and M. Pato. “A Multiobjective Genetic Algorithm for the Class/Teacher Timetabling Problem”. Lecture Notes in Computer Science. Vol. 2079, pp. 3-17. 2001
[13] docCF http://www.grupocfdeveloper.com/ consultado el 16-10-2010
[14] UNTIS http://www.grupet.at/espanol/produkte/untis/uebersicht_untis.php consultado el 16-10-2010
[15] GES http://www.grupoges.com.mx/ consultado el 16-10-2010
[16] PATAT,”International Timetabling Competition” http://www.cs.qub.ac.uk/itc2007/ consultado el 16-10-2010
[17] Facultad de Psicología, Universidad Veracruzana http://www.uv.mx/facpsi/ consultado el 16-10-2010
[18] A. E. Eiben, J.E. Smith , Introducction to evolutionary computing, natural computing series, springer.
[19] L.J. Fogel, P.J. Angeline, T. Bäck, Eda. Proceedings of the 5th Annual Conference on Evolutionary Programming, MIT Press , Cambridge, MA, 1996.
[20] L.J. Fogel, A.J. Owens, M.J. Walsh. Artificial Intelligence through Simulated Evolution, Wiley, Chichester, UK, 1966.
[21] J.H. Holland. Genetic algorithms and the optimal allocation of trials. SIAM J. Of Computing, 2pp.88-105, 1973.
[22]J.H. Holland. Adaption in Natural and artificial Systems. MIT Press, Cambridge, MA, 1992. 1st. Edition: 1975, The University of Michigan Press, Ann Arbor.
[23] I. Rechenberg. Evolution strategie: optimierung Technisher Systeme nach Prinzipien des Biologischen Evolution. Fromman-Hozlboog Verlag, Stuttgart, 1973.
[24] H.P. Schwefel. Evolution and Optimum Seeking. Wiley , New York 1995.
[25] T. Bäck Evolutionary Algorithms in Theory and Practice. Oxford University Press, Oxford. UK, 1996.
[26] T. Bäck, D.B. Fogel, Z. Michalewicz, Eds. Evolutionary Computating 1: Basic Algorithms and Operators . Institute of Physics Publishing. Bristol. 2000.
[27] T. Bäck , D.B. Fogel, Z. Michalewicz, Eds. Evolutionary Computation 2: Advance Algorithms and Operators. Institute of Physics Publishing, Bristol, 2000.
[28] A.E.Eiben, Z. Michaelewicz, Eds. Evolutionary Computation. IOS Press, 1998.
[29] Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs, springer, Berlín, Heidelberg, New York, 3rd edn., 1996.
[30] David E. Goldberg, Genetic Algoritms in Search Optimization & Machine Learning, Addison-Wesley Publishing Company.
[31] Santana Quintero,Luis Vicente, Coello Coello Carlos A. ,Una introducción a la computación evolutiva y algunas de sus aplicaciones en economia y finanzas, Revista de métodos cuantitativos para la economía y la empresa paginas 3-25, diciembre 2006.
[32] Pervys Rengifo Rengifo, Leonardo Jiménez, Programación Genética, Fundación universitaria Konrad Lorenz, Facultad de matemáticas e ingenierías , ingeniería en sistemas.
[33]Pablo Moscato, Carlos Cotta, An Introduction to memetic Algorithms, Inteligencia artificial, Revista iberoamericana de inteligencia artificial, No. 19 ,pp 131-148, ISSN: 1137-3601.
[34] Yuichi Nagata, Shigenubo Kobayashi, An analysis of Edge Assembly Crossover for the Traveling Salesman Problem,0-7803-5731-0/99 1999 IEEE.
[35] Mitchell, Melanie. An Introduction to Genetic Algorithms. MIT Press, 1996.
[36] Haupt, Randy y Sue Ellen Haupt. Practical Genetic Algorithms. John Wiley & Sons, 1998.
[37] Baumelt Zdenek · Sucha Premysl · Hanz alek Zdenek An Evolutionary Algorithm in a Multistage Approach for an Employee Rostering Problem with a High Diversity of Shifts PATAT 2010
[38] Burke, E.K., Cowling, P., De Causmaecker, P. and Berghe, G.V.: A Memetic Approach to the Nurse Rostering Problem. Applied Intelligence 15, 199-214 (2001)
[39] http://www.asap.cs.nott.ac.uk/ASAP_Brochure20072008.pdf consultado el 12 de enero del 2011
[40] http://www.cs.qub.ac.uk/itc2007/winner/finalorder.htm consultado el 12 de enero del 2011
[41] Ms.C: Arsenio Celorrio Sánchez, Pruebas de hipótesis no paramétricas de K-S, http://www.monografias.com/trabajos11/docima/docima.shtml, consultado el 15 de enero del 2011.
[42] Hart, William E.; Krasnogor, Natalio; Smith, J.E. (Eds.). Recent Advance in Memetic Algoritmics, Studies in Fuzziness and Soft Computing, Vol. 166, ISBN 978-3-540-22904-9
2 comentarios:
ES MUY BUENA TU INFORMACION ME GUSTO MUCHO Y ME AYUDO A MI TRABAJO :)
Hola Fermin
Me agrada tu blog por la información contenida
Me fue de ayuda en cuanto a mi tarea
Saludos
Publicar un comentario