Descargar

Computación Evolutiva

    2. Objetivo general
    3. Panorama histórico de la computación evolutiva
    4. Conceptos básicos. Los orígenes
    5. Programación evolutiva
    6. Estrategias evolutivas (EE)
    7. Algoritmos genéticos
    8. Clases de algoritmos genéticos
    9. Elementos de un algoritmo genético
    10. Operadores genéticos.
    11. Ciclo general de un algoritmo genético estándar
    12. Software
    13. Conclusión
    14. Bibliografía

     INTRODUCCIÓN

    En este tema se verá la forma en que los científicos han tomado a la evolución a través de la selección natural determinando que miembros de la población sobrevivirán hasta reproducirse y la reproducción sexual garantizando la mezcla y combinación de sus genes entre la descendencia.

    En la naturaleza, los individuos compiten entre sí por recursos tales como comida, agua refugio. Adicionalmente, los animales de la misma especie normalmente antagonizan para obtener una pareja.

    Veremos conceptos básicos de las técnicas más importantes de computación evolutiva. Luego comenzaremos a hablar de la computación evolutiva en particular. Iniciaremos con un recorrido histórico en el que se resumirán los logros más importantes en torno a la simulación de los procesos evolutivos como una herramienta para el aprendizaje y la optimización.

    Posteriormente se analizarán de manera general los 3 paradigmas principales que se utilizan hoy en día en la computación evolutiva: las estrategias evolutivas, la programación evolutiva y los algoritmos genéticos. En cada caso se abordará su inspiración biológica, su motivación, su funcionamiento y algunas de sus aplicaciones. Finalmente se estudiará el funcionamiento, fundamentos teóricos, implementación de los algoritmos genéticos, que es actualmente el paradigma evolutivo más utilizado por los investigadores que trabajan en esta disciplina.

    OBJETIVO GENERAL

    Comprender el concepto de la computación evolutiva, su importancia en el mundo actual así como su historia, sus conceptos básicos y sus diferentes aplicaciones.

    Computación Evolutiva

    La Computación Evolutiva interpreta la naturaleza como una inmensa máquina de resolver problemas y trata de encontrar el origen de dicha potencialidad para utilizarla en nuestros programas.

    Definición :Con el término de Computación Evolutiva se engloba al conjunto de técnicas que basándose en la simulación de los procesos naturales y la genética se utilizan para resolver problemas complejos de búsqueda y aprendizaje.

    Panorama histórico de la computación evolutiva

    Cannon 1932, visualizó la evolución natural como un proceso de aprendizaje. Alan Turing reconoció, en 1950, que debe haber una conexión obvia entre el aprendizaje de máquina y la evolución, y señaló que se podrían desarrollar programas para jugar ajedrez usando esta técnica.

    Campbell conjeturó en 1960 que en todos los procesos que llevan a la expansión del conocimiento, se involucra un proceso ciego de variación y supervivencia selectiva.

    Los primeros intentos de aplicar de manera formal la teoría de la evolución, apareció en las áreas de control de procesos estadísticos, aprendizaje de máquina y optimización de funciones. Tal vez el primer intento serio de este tipo se dio en el trabajo que realizaron Box y sus colegas en 1957, en el desarrollo de una técnica que denominaron operación evolutiva, la cual se aplicó a una planta de manufactura para manejarla.

    Friedberg intentó, en 1958, hacer que un programa en lenguaje máquina se mejorara a sí mismo, seleccionando instrucciones que se asociaran más frecuentemente con un resultado exitoso.

    Barricelli ofreció, en 1954, una de las primeras simulaciones que usaba principios evolutivos, utilizando los mismos procedimientos generales que se usan hoy en día en la disciplina conocida como vida artificial.

    Fogel el que introdujo la primera técnica evolutiva que realmente funcionó más o menos dentro de los lineamientos actuales de la computación evolutiva. Su programación evolutiva consistía en hacer evolucionar autómatas de estados finitos por medio de mutaciones artificial.

    Rechenberg y Schwefel 1965. desarrollaron una técnica, llamada estrategia evolutiva, se utilizó inicialmente para resolver problemas ingenieriles que desafiaban a los métodos de optimización tradicionales.

    CONCEPTOS BASICOS

    LOS ORIGENES

    La evolución se produce como resultado de dos procesos primarios: la selección natural y la reproducción sexual. La primera determina que miembros de la población sobrevivirán hasta reproducirse, la segunda garantiza la mezcla y combinación de sus genes entre la descendencia. En la fusión del óvulo y el espermatozoide, los cromosomas homologados se estiran y adosan uno al otro, y luego se entrecruzan en zonas intermedias, intercambiando así material genético. [Holland 92] .

    En la naturaleza, los individuos compiten entre sí por recursos tales como comida, agua refugio. Adicionalmente, los animales de la misma especie normalmente antagonizan para obtener una pareja. [Martín 95].

    Esta es la teoría de la evolución, especies naturales que van evolucionando para adaptarse al medio que las rodea y aquellos individuos que tenga más éxito en tal adaptación tendrán mejor probabilidad de sobrevivir hasta la edad adulta y probablemente un número mayor de descendientes, por lo tanto, mayores probabilidades de que sus genes sean propagados a los largo de sucesivas generaciones. La combinación de características de los padres bien adaptados, en un descendiente, puede producir muchas veces un nuevo individuo mucho mejor adaptado que cualquiera de sus padres a las características de su medio ambiente. Este proceso no debe verse en ningún momento como un proceso determinista, sino como un proceso con la fuerte componente estocástica. Es decir, si un individuo se adapta al entorno, lo más que se puede afirmar es que ese individuo tendrá mayor probabilidad de conservar sus genes en la siguiente generación que sus congéneres. Pero solo es una probabilidad, no es un hecho absolutamente seguro. Siempre existirá la posibilidad de que a pesar de estar muy dotado por alguna razón no consiga reproducirse. Pero en cuanto a la especie como un conjunto o población, si puede afirmarse que ira adaptándose al medio. [Martín 95] La idea surgió en la universidad de Michigan, Estados Unidos donde el profesor J. H. Holland quien, consciente de la importancia de la selección natural introdujo la idea de los Algoritmos Genéticos en los años sesenta y al final de esta década desarrollo una técnica que permitió incorporarla en un programa de computadora. Su principal objetivo era lograr que las computadoras aprendieran por sí mismas. A la técnica inventada por Holland se le llamo inicialmente Planes Reproductivos pero se hizo popular bajo el nombre de Algoritmos Genéticos, A.G. Obviamente desde aquellos años sesenta hasta ahora, muchas otras personas han contribuido de modo notable al desarrollo de estas ideas, abriéndose muchos nuevos frentes de trabajo y subdividiéndose la idea original en múltiples disciplinas. [Martín 95] Estas técnicas se usan principalmente en países desarrollados como Japón Estados Unidos y en Europa.

    En la naturaleza todos los seres vivos se enfrentan a problemas que deben resolver con éxito, como conseguir más luz del sol, o cazar una mosca. La Computación Evolutiva interpreta la naturaleza como una inmensa máquina de resolver problemas y trata de encontrar el origen de dicha potencialidad para utilizarla en nuestros programas.

    Los Algoritmos Genéticos son una de las más conocidas y originales técnicas de resolución de problemas dentro de lo que se ha definido como "Computación Evolutiva" (o "Algoritmos Evolutivos"), término que agrupa a los Algoritmos Genéticos, las Estrategias Evolutivas y la Programación Evolutiva. En realidad todas estas técnicas son muy parecidas y comparten muchos aspectos.

    Un Algoritmo Evolutivo es una técnica de resolución de problemas inspirada en la evolución de los seres vivos.

    En un Algoritmo Evolutivo se define una estructura de datos que admita todas las posibles soluciones a un problema.

    Cada uno de los posibles conjuntos de datos admitidos por esa estructura será una solución al problema. Unas soluciones serán mejores, otras peores.

    Solucionar el problema consistirá en encontrar la solución óptima, y por tanto, los Algoritmos Evolutivos son en realidad un método de búsqueda.

    Pero un método de búsqueda muy especial, en el que las soluciones al problema son capaces de reproducirse entre sí, combinando sus características y generando nuevas soluciones.

    En cada ciclo se seleccionan las soluciones que más se acercan al objetivo buscado, eliminando el resto de soluciones. Las soluciones seleccionadas se reproducirán entre sí, permitiendo de vez en cuando alguna mutación o modificación al azar durante la reproducción.

    Algoritmo Evolutivo

    • Es una técnica de resolución de problemas inspirada en la evolución de los seres vivos.
    • Programas computacionales cuyo fin es imitar el proceso de "selección natural" que según la teoría de Darwin rige el curso de la evolución

    Esquema de la computación evolutiva

    • Inteligencia artificial.
      • Enfoque simbólico o `top-down'.
      • Enfoque subsimbólico o `botton-up'.
        • Redes neuronales artificiales.
        • Computación evolutiva o algoritmos evolutivos.
          • Solidificación o recocido simulado (simulated annealing).
          • Algoritmos genéticos.
          • Estrategias evolutivas.
          • Clasificadores genéticos.
          • Programación genética.

    Fases de un Algoritmo Evolutivo

    • Opciones Generales.
      • Número de entidades.
      • Número de elementos (genes, reglas) por cada agente.
    • Método de Evaluación: Asignar un peso.
      • Desordenar las entidades antes de evaluarlas.
      • Diferentes formas de modificación de los pesos después de la evaluación. Por ejemplo, el peso de una entidad se puede calcular independientemente de las demás entidades, o se puede modificar posteriormente este valor, disminuyendo el peso si existe otra entidad muy parecida, analizando para ello un cierto subconjunto de la población vecina.
    • Método de Selección: ¿Quién muere? ¿Quién se reproduce?
      • Con o sin reemplazamiento.
      • Método de la ruleta.
      • Método de los torneos.
      • Seleccionar el n% mejor y el m% peor.
    • Método de Reproducción: Generar y mutar nuevos hijos.
      • Los padres pueden tomarse por parejas o en grupos más numerosos, elegidos al azar o en orden de pesos.
      • En el caso de detectar que los progenitores son muy parecidos, se puede realizar una acción especial, como incrementar la probabilidad de mutación.
      • Las entidades pueden comunicar a otras su conocimiento, ya sea a toda o a una parte de la población, directamente o a través de una pizarra, (una especie de tablón de anuncios).
      • Método de recombinación de genes: se puede tomar genes de uno u otro progenitor al azar, en un cierto orden, con uno, dos o más puntos de corte, etc.
      • Tasa de mutación variable.
      • Fijar una tasa de mutación diferente para cada individuo o incluso para cada gen.
      • Hacer que sea más probable que se produzca una mutación en un gen si en su vecino ya se ha producido.
      • Sustituir por mutaciones, genes sin utilidad, como reglas incorrectas o repetidas.
      • Tipos de mutaciones

    Algoritmo

    El algoritmo básico de la programación evolutiva es el siguiente:

    • Generar aleatoriamente una población inicial.
    • Se aplica mutación.
    • Se calcula la aptitud de cada hijo y se usa un proceso de selección mediante torneo (normalmente estocástico) para determinar cuales serán las soluciones que se retendrán.

    El termino computación evolutiva o algoritmos evolutivos, realmente engloba

    una serie de técnicas inspiradas biológicamente. En términos generales, para simular el proceso evolutivo en una computadora se requiere:

    • Codificar las estructuras que se replicaran.
    • Operaciones que afecten a los "individuos".
    • Una función de aptitud.
    • Un mecanismo de selección.

    Aunque hoy en día es cada vez mas difícil distinguir las diferencias entre los distintos tipos de algoritmos evolutivos existentes, suele hablarse de tres paradigmas principales:

    PROGRAMACIÓN EVOLUTIVA

    _Estrategias Evolutivas

    _Algoritmos Genéticos.

    Programas Evolutivos (PE)

    Son una estrategia de optimización estocástica similar a los Ags, pero hacen un énfasis específico en los operadores genéticos tal y como se observan en la naturaleza y en la estructura de datos que utilizan adaptada al problema. Por esto, a diferencia de los AGs, los PEs no son restrictivos en cuanto a la representación del problema. Mientras en los AGs se hace necesario una codificación de las soluciones del problema; en los PEs, tal representación se hace de forma directa.

    Historia

    Los programas evolutivos fueron presentados en 1994 por Michalewicz, cuando propuso incorporar conocimiento específico del problema a resolver en las estructuras de datos. Así, los PEs son métodos que incorporan directamente conocimiento específico a los AGs, puesto que permiten la utilización de estructuras de datos naturales. Esto permite, a su vez, la utilización de operadores genéticos sensibles al contexto, con el fin de mejorar la eficiencia del algoritmo de búsqueda sin perder gran parte de la propiedad de generalización. Además, de perder un poco de generalización, con la incorporación de conocimiento específico, también se pierde el paralelismo implícito (basado en alfabetos de símbolos mínimos). Sin embargo, esta pérdida se compensa con el procesamiento de información mas útil.

     Veamos el ejemplo del funcionamiento de la programación evolutiva que se indica en la figura 3.2. La tabla de transiciones de este autómata es la siguiente:

     En este autómata pueden ahora aplicarse cinco diferentes tipos de mutaciones:

    cambiar un símbolo de salida, cambiar una transición, agregar un estado, borrar un estado y cambiar el estado inicial. El objetivo es hacer que el autómata reconozca un cierto conjunto de entradas (o sea, una cierta expresión regular) sin equivocarse ni una sola vez.

    Aplicaciones

    Predicción

    Generalización

    Juegos

    Control automático

    Problema del viajero

    Planeación de rutas

    Diseño y entrenamiento de redes neuronales

    Reconocimiento de patrones.

    ESTRATEGIAS EVOLUTIVAS (EE)

    Esta técnica esta básicamente enfocada hacia la optimización paramétrica. En esencia son métodos estocásticos con paso adaptativo, que permiten resolver problemas de optimización paramétrica. A este método se le han agregado procedimientos propios de la computación evolutiva, que lo han convertido en un paradigma más de dicha metodología. Con tal mezcla, las EEs 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 determinística y operadores genéticos específicos de cruce y mutación. Además, su objetivo fundamental consiste en encontrar el valor real de un vector de N dimensiones.

    Las EEs pueden dividirse en dos tipos: Estrategias Evolutivas Simples y Estrategias Evolutivas Múltiples.

    • EEs Simples

    Son consideradas como procedimientos estocásticos de optimización paramétrica con paso adaptativo, esta característica las hace similares al temple 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 EEs 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.

    • EEs Múltiples:

    Surgen como respuesta a las debilidades de las EEs simples, las cuales tienden a converger hacia subóptimos. En las EEs múltiples existen múltiples individuos (población), y se producen en cada generación varios nuevos individuos, usando tanto mutación como cruce (también puede usarse cualquier otro operador). Se usa normalmente e cruce promedio, el cual genera un único descendiente de dos padres, promediando los valores de estos. 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.

    Algunas aplicaciones de las estrategias evolutivas son

    Problemas de ruteo y redes

    Bioquímica

    Óptica

    Diseño en ingeniería

    Magnetismo

    ALGORITMOS GENÉTICOS

    Los organismos vivos poseen destreza consumada en la resolución de problemas y se manifiesta una versatilidad capaz de avergonzar a los problemas más refinados. Una definición bastante completa de un Algoritmo Genético es la propuesta por Jhon Kosa [Coello 95]: Es un Algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del mas apto, y tras haberse presentado de forma natural una serie de operaciones genéticas de entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres (letras o números) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se asocian con una cierta función matemática que refleja su aptitud. Los Algoritmos Genéticos utilizan una analogía directa del fenómeno de evolución en la naturaleza. Trabajan con una población de individuos, cada uno representado una posible solución a un problema dado. A cada individuo se le asigna una puntuación de adaptación, dependiendo de que tan buena fue la respuesta al problema. A los más adaptados se les da la oportunidad de reproducirse mediante cruzamientos con otros individuos de la población, produciendo descendientes con características de ambos padres. Los miembros menos adaptados poseen pocas probabilidades de que sean seleccionados para la reproducción, y desaparecen. El evaluar esta adaptación no es sencillo de hacer, pues el entorno esta modificándose constantemente por lo que nunca se llegara al súper individuo perfecto, sino que la naturaleza tendera a optimizar los individuos de cada especie en las circunstancias actuales. Existen varios tipos de Algoritmos Genéticos, cada uno basado en una metáfora distinta de la naturaleza.

    Los algoritmos genéticos parten de una población inicial donde cada individuo se representa con un código genético (típicamente una secuencia de bits) en la que se encuentra codificada su información. Sobre esta población se realiza una serie de operaciones, en primer lugar se seleccionan parejas de soluciones para que se reproduzcan (a este proceso se le llama cruce), siendo los hijos una mezcla del código genético de los padres. A continuación se producen una serie de mutaciones que alteran los genes de los recién nacidos y por último de entre toda la población se eligen aquellos que van a sobrevivir desechándose el resto (la población en un algoritmo genético típico permanece constante en todas las iteraciones). Tanto a la hora de la reproducción, como en el momento de elegir las soluciones supervivientes en cada iteración, se favorece a aquellos individuos que según la función de evaluación sean más fuertes. El algoritmo terminará cuando se llegue a un número de iteraciones seleccionado previamente, o cuando se observe tras una serie de iteraciones no se ha detectado ninguna mejora en la población. El pseudo código sería el siguiente:

    Algoritmo

    Crear población inicial Evaluar la población Mientras No(condición salida) Seleccionar a los padres Combinar los genes de los padres para crear a los descendientes Mutar a los descendientes Evaluar la nueva población Elegir los individuos que sobrevivirán

    CLASES DE ALGORITMOS GENÉTICOS

    Algoritmos Genéticos Generacionales

    Se asemejan a la forma de reproducción de los insectos, donde una generación pone huevos, se aleja geográficamente o muere y es substituida por una nueva. En este momento se realizan cruces en una piscina de individuos, los descendientes son puestos en otra, al final de la fase reproductiva se elimina la generación anterior y se pasa a utilizar la nueva. Este modelo también es conocido como Algoritmo Genético Canónico.

    Algoritmos Genéticos de estado Fijo.

    Utilizan el esquema generacional de los mamíferos y otros animales de vida larga, donde coexisten padres y sus descendientes, permitiendo que los hijos sean educados por sus progenitores, pero también que a la larga se genere competencia entre ellos. En este modelo, no solo se deben seleccionar los dos individuos a ser padres, si no también cuales de la población anterior serán eliminados, para dar espacio a los descendientes. La diferencia esencial entre el reemplazo generacional y el modelo de estado fijo es que las estadísticas de la población son recalculadas luego de cada cruce y los nuevos descendientes están disponibles inmediatamente para la reproducción. Esto permite al modelo utilizar las características de un individuo prometedor tan pronto como es creado. Algunos autores dicen que este modelo tiende a evolucionar mucho más rápido que el modelo generacional, sin embargo investigaciones de Goldberg y deb [GOLDBERG 93], encontraron que las ventajas parecen estar relacionadas con la alta tasa de crecimiento inicial, ellos dicen que los mismos efectos pueden ser obtenidos en rangos de adaptación exponencial o selección por competencia. No encontraron evidencia que este modelo sea mejor que el Generacional. Algoritmos Genéticos Paralelos.

    Parte de la metáfora biológica que motivo a utilizar la búsqueda genética consiste en que es inherentemente paralela, donde al evolucionar se recorren simultáneamente muchas soluciones, cada una representada por un individuo de la población. Sin embargo, es muy común en la naturaleza que no solo sea una población evolucionando, si no varias poblaciones, normalmente aisladas geográficamente, que originan respuestas diferentes a la presión evolutiva. Esto origina dos modelos que toman es cuenta esta variación, y utilizan no una población como los anteriores si4 no múltiples concurrentemente.

    Modelos de Islas.

    Si se tiene una población de individuos, esta se divide en subpoblaciones que evolucionan independientemente como un Algoritmo Genético normal. Ocasionalmente, se producen migraciones entre ellas, permitiéndoles intercambiar material genético. Con la utilización de la migración, este modelo puede explotar las diferencias en las subpoblaciones; esta variación representa una fuente de diversidad genética. Sin embargo, si un número de individuos emigran en cada generación, ocurre una mezcla global y se eliminan las diferencias locales, y si la migración es infrecuente, es probable que se produzca convergencia prematura en las subpoblaciones.

    Modelo Celular

    Coloca cada individuo en una matriz, donde cada uno sólo podrá buscar reproducirse con los individuos que tenga a su alrededor (mas cerca de casa) escogiendo al azar o al mejor adaptado. El descendiente pasara a ocupar una posición cercana. No hay islas en este modelo, pero hay efectos potenciales similares. Asumiendo que el cruce esta restringido a individuos adyacentes, dos individuos separados por 20 espacios están tan aislados como si estuvieran en dos islas, este tipo de separación es conocido como aislamiento por distancia. Luego de la primera evaluación, los individuos están todavia distribuidos al azar sobre la matriz. Posteriormente, empiezan a emerger zonas como cromosomas y adaptaciones semejantes. La reproducción y selección local crea tendencias evolutivas aisladas, luego de varias generaciones, la competencia local resultara en grupos mas grandes de individuos semejantes.

    ELEMENTOS DE UN ALGORITMO GENETICO

    Como los Algoritmos Genéticos se encuentra basados en los procesos de evolución de los seres vivos, casi todos sus conceptos se basan en conceptos de biología y genética que son fáciles de comprender.

    Individuo Un individuo es un ser que caracteriza su propia especie. El individuo es un cromosoma y es el codigo de información sobre el cual opera el algoritmo. Cada solución parcial del problema a optimizar está codificada en forma de cadena o String en un alfabeto determinado, que puede ser binario. Una cadena representa a un cormosoma, por lo tanto tambien a un individuo y cada posición de la cadena representa a un gen. Esto significa que el algoritmo trabaja con una codificación de los parametros y no con los parametros en si mismos. El genotipo, es el conjunto de genes ordenados y representa las caracteristicas del individuo. Cada individuo tinen una medida de su adecuación como solución al problema. Población A un conjunto de individuos (Cromosomas) se le denomina población. El método de A.G´s consiste en ir obteniendo de forma sucesiva distintas poblaciones. Por otra parte un Algoritmo Genético trabaja con un conjunto de puntos representativos de diferentes zonas del espacio de búsqueda y no con un solo punto (como lo hace Hillclimbing).

    Función Fitness.

    La única restricción para usar un algoritmo genético es que exista una función llamada fitness, que le informe de cuan bueno es un individuo dado en la solución de un problema. Esta función fitness o de evaluación es el principal enlace entre el Algoritmo Genético a un problema real, es la efectividad y eficiencia de la función fitness que se tome, por lo tanto debe procurarse que la función fitness sea similar, si no igual a la función objetivo que se quiere optimizar. Esta medida se utiliza como parámetro de los operadores y guía la obtención de nuevas poblaciones.

    OPERADORES GENETICOS.

    Son los diferentes métodos u operaciones que se pueden ejercer sobre una población y que nos permite obtener poblaciones nuevas. Una vez que se ha evaluado cada individuo sobre una función fitness, se aplican los operadores genéticos. En Algoritmos Genéticos se destacan los siguientes operadores. Operador de Selección.

    El paso siguiente a la evaluación es escoger los miembros de la población que serán utilizados para la reproducción. Su meta es dar mas oportunidades de selección a los miembros más aptos de la población. Así funciona: se calcula el cociente entre el valor fitness de un individuo y la suma total de los valores fitness de todos los individuos de la población. Este resultado mide la probabilidad de selección Ps (i) de cada individuo.

    Para ver la fórmula seleccione la opción "Descargar" del menú superior

    Ecuación No. 1 Probabilidad de selección.

    Empezando desde la población P (t) de N individuos se obtiene una nueva población P(t+1) aplicando N veces el operador de selección. Los individuos se seleccionan de una especie de rueda de ruleta (como se muestra en la figura 1) donde cada uno tiene asignado un trozo en proporción a su probabilidad selecc

    Para ver el gráfico seleccione la opción "Descargar" del menú superiorión Ps.

    Figura No.1 Operador de Selección

    Este mecanismo puede causar problemas de convergencia prematura, causada por la aparición de un individuo que es mucho mejor que los otros de la población aunque esta lejos de optimo; las copias de este individuo pueden dominar rápidamente a la población, sin poder escapar de este mínimo local.

    Operador de Cruce

    Consiste en unir en alguna forma los cromosomas de los padres que han sido previamente selecciónados de la generación anterior para formar dos descendientes. Existen diversas variaciones, dependiendo del número de puntos de división a emplear y la forma de ver el cromosoma. El operador cruce se aplica en dos pasos: en el primero los individuos se aparean (se seleccionan de dos a dos) aleatoriamente con una determinada probabilidad, llamada probabilidad de cruce Pc; en el segundo paso a cada par de individuos seleccionados anteriormente se le aplica un intercambio en su contenido desde una posición aleatoria K hasta el final, con K Î [1, m-1], donde m es la longitud de individuo. K es el denominado punto de cruce y determina la subdivisión de cada padre en dos partes que se intercambian para formar dos nuevos hijos, según podemos ver en la figura 2 Esto se conoce como cruce ordinario o cruce de un punto. El objetivo del operador de cruce es recombinar subcadenas de forma eficiente; esta gestión recibe el nombre de construcción de bloques.

    Para ver el gráfico seleccione la opción "Descargar" del menú superior

    Figura No. 2 Operador de Cruce

    Mutación.

    El operador de mutación consiste en la alteración aleatoria de cada uno de los genes del individuo con una probabilidad de mutación PM, como se puede ver en la figura 3. El objetivo de la mutación es producir diversidad en la población. Si al generar aleatoriamente la población inicial o después de varias generaciones, en la misma posición de todos los cromosomas sólo aparece un único elemento del alfabeto utilizado, esto supondrá que con los operadores de reproducción y cruce, nunca cambiara dicho elemento, por lo que puede ocurrir que jamas se alcance la solución más optima a nuestro problema. La probabilidad de aparición del operador de mutación no debe ser grande para no perjudicar la correcta construcción de bloques. El operador de mutación origina variaciones elementales en la población y garantiza que cualquier punto del espacio de búsqueda pueda ser alcanzado.

    Para ver el gráfico seleccione la opción "Descargar" del menú superior

    Figura No. 3 Operador de Mutación

    CICLO GENERAL DE UN ALGORITMO GENETICO ESTANDAR

    El AG estándar se puede expresar en pseudocodigo con el siguiente ciclo. [Coello 95]: 1. Generar aleatoriamente la población inicial de individuos P(0). Generación = 0: 2. Mientras ( numero _ generaciones <= máximo _ números _ generaciones)

    Hacer

    {

    Evaluación;

    Selección;

    Reproducción;

    Generación ++;

    }

    3.Mostrar resultados;

    Fin de la generación

    Estas características de los AG, a su vez, describen las diferencias entre ellos, y otros métodos normales de optimización.

    1. Un Algoritmo Genético trabaja con codificación de los parámetros que busca optimizar y no con los parámetros en sí mismo.

    2. Un Algoritmo Genético trabaja con un conjunto de puntos representativos de diferentes zonas del espacio y no con un solo punto. Por el contrario necesita considerables recursos de computación.

    3. La aplicación de AG no depende de ninguna propiedad de la función a optimizar (derivable, continua, ni siquiera conocida), o de que el conjunto de posibles soluciones sea finito o no lo sea.

    4. Un AG utiliza reglas de transición probabilisticas, no deterministas, lo cual hace que dos aplicaciones consecutivas de un AG a un mismo problema puedan producir dos soluciones distintas.

    EL ejemplo siguiente nos da una pequeña ilustración de un Pseudocódigo de Algoritmo Genético.

    BEGIN /* Algoritmo Genético */

    Generar una población inicial.

    Computar la función de evaluación de cada individuo.

    WHILE NOT Terminado DO

    BEGIN /* Producir nueva Generación */

    FOR Tamaño Población /2 DO

    BEGIN /* Ciclo Reproductivo */

    Seleccionar dos individuos de la anterior generación

    El cruce (probabilidad de selección proporcional a la

    Función de evaluación de individuo).

    Cruzar con cierta probabilidad los dos individuos

    obtenida dos descendientes

    Mutar los dos descendientes con cierta probabilidad.

    Computar la función de evaluación de los dos

    descendientes Mutados.

    Insertar los dos descendientes mutados en la nueva

    generación.

    END

    IF La población ha convergido THEN

    Terminado =TRUE

    END

    END

    Algunas aplicaciones de los AGs son las siguientes

    • Optimización (estructural, de topologías, numérica, combinatoria, etc.)
    • Aprendizaje de maquina (sistemas clasificadores)
    • Bases de datos (optimización de consultas)
    • Reconocimiento de patrones (por ejemplo, imágenes)
    • Generación de gramáticas (regulares, libres de contexto, etc.)
    • Planeación de movimientos de robots
    • Predicción.

    Estrategias Evolutivas vs Programación Evolutiva

    La Programación Evolutiva usa normalmente selección estocástica, mientras que

    las estrategias evolutivas usan selección deterministica.

    Ambas técnicas operan a nivel fenotipico (es decir, no requieren codificación

    de las variables del problema).

    La programación evolutiva es una abstracción de la evolución al nivel de las

    especies, por lo que no se requiere el uso de un operador de recombinación (diferentes especies no se pueden cruzar entre si). En contraste, las estrategias evolutivas son una abstracción de la evolución al nivel de un individuo, por lo que la recombinación es posible.

     Tendencias futuras

    Las limitaciones de la representación binaria en algunas aplicaciones ha hecho de esta una ruta interesante de investigación, sobre todo en el contexto de problemas de manufactura y definición de rutas, en los cuales la respuesta se expresa en forma de permutaciones. Idealmente, debiera existir un tipo de representación suficientemente flexible como para permitir su utilización en una amplia gama de problemas de forma sencilla y natural.

    Filho [77] desarrollo un sistema llamado GAME (Genetic Algorithms Manipu-lation Environment), que constituye un paso importante en esta dirección. GAME usa una codificación de árbol en la que las hojas pueden ser enteros, caracteres,números reales o cadenas binarias.

    Gibson [101] también propuso una codificación híbrida similar a la de Filho.

    Su propuesta se basa en el uso de componentes de diferentes tipos en el contexto de modelado de procesos industriales.

    Existe amplia evidencia en la literatura especializada [159, 155, 190, 100, 115] de que el usar una representación adecuada puede simplificar tremendamente el proceso de búsqueda de un algoritmo genético, pero a pesar de eso, muchos investigadores suelen pasar por alto este importante hecho. Por lo tanto, es vital no únicamente reconocer que se requieren codificaciones mas poderosas, sino

    SOFTWARE

    En general, podemos clasificar el software para computación evolutiva en 3 grandes grupos:

    _Orientado a las aplicaciones: Son "cajas negras" diseñadas para ocultar

    detalles de los AGs y ayudar al usuario a desarrollar aplicaciones para dominios

    específicos tales como las finanzas, la programación de horarios, etc.

    _Orientado a los algoritmos: Se basan en modelos de AGs específicos y

    pueden subdividirse en 2 grupos:

    1. Sistemas Específicos: Contienen un solo algoritmo.

    2. Bibliotecas: Contienen una gama de algoritmos y operadores genéticos

    que pueden estar disponibles solo de manera precompilada.

    Cajas de herramientas (tool kits): Sistemas de programación que proporcionan

    muchas utilerías, algoritmos y operadores genéticos que pueden

    usarse para cualquier tipo de aplicación y que normalmente se proporcionan

    en forma de código fuente (al menos de manera parcial).

    A su vez, las cajas de herramientas se pueden subdividir en 2 grupos:

    1.Sistemas Educativos:

    2. Sistemas de propósito general:

    CONCLUSIÓN

    • Los algoritmos genéticos son un proceso de prueba y error.
    • Una de las partes mas importantes del algoritmo es la función de "adaptación". Sin ella la mutación se pueden "contaminar", y no hay evolución.
    • Solucionar el problema consistirá en encontrar la solución óptima, y por tanto, los Algoritmos Evolutivos son en realidad un método de búsqueda.
    • La Computación Evolutiva, en resumen, es la ciencia computacional cuyos algoritmos imitan el proceso evolutivo de la naturaleza.

    BIBLIOGRAFÍA

    1. http://www.redcientifica.com/doc/doc199904260012.html

    2. http://www.redcientifica.com/gaia/ce/ce_c.htm

    3.http://www.lania.mx/spanish/actividades/newsletters/1997-otono-invierno/evolutiv.html

    4.http://www.lania.mx/spanish/actividades/newsletters/1997-otono-invierno/evolutiv.html

    5. http://www.cimat.mx/talleres/pasados/2003/evolutiva/

    6. http://www.dccia.ua.es/ria/artics/sceta97.pdf

    7.http://www.lania.mx/spanish/actividades/newsletters/1999-primavera-verano/tendencias.html

    8. http://cursos.itam.mx/akuri/Semestre2/RNS/0123Pres/0.pdf

    9. http://pitagoras.usach.cl/~msanchez/ce/

    10. http://delta.cs.cinvestav.mx/~ccoello/talks.html

    11. http://www.psicologiacientifica.com/articulos/ar-h_gascon01.htm

    12.http://chue.ing.ula.ve/DOCENCIA/POSTGRADO/CURSOS/MSS05/ComputacionEvolutiva.html#PE

    13. http://www.elrinconcito.com/articulos/Genetico/Geneticos.htm

    14. http://delta.cs.cinvestav.mx/~ccoello/genetic.html

    15. http://delta.cs.cinvestav.mx/~ccoello/compevol/apuntes.pdf.gz

    16. http://kal-el.ugr.es/VidArt/VidaArti.html

    17. http://pitagoras.usach.cl/~msanchez/ce/

    18. http://members.tripod.com/jesus_alfonso_lopez/AgIntro.html

    19. http://www.iieh.com/comunidad/mherran.html

      

    José Madrigal García

    Mateo Luna Luna

    CUNDUACÁN TABASCO