Source: https://www.scribd.com/document/182121259/bioinformatica
Timestamp: 2019-01-19 20:26:52+00:00

Document:
PL_TSS_ALG_GEN_AA_7_3
Pour La Journée Pédagogique Sur La Mode
Algoritmos Evolutivos y Algoritmos Genéticos
N.I.A.: 100027597
A partir de la creación de estas estrategias evolutivas aparecieron otras vías de investigación como son: Algoritmos Genéticos (Goldberg). que recogen un conjunto de modelos basados en la evolución de los seres vivos. química. inspirado en el principio darviniano de selección natural y reproducción genética. Programación Evolutiva (Fogel). Los algoritmos genéticos constituyen una técnica poderosa de búsqueda y optimización con un comportamiento altamente paralelo. facilidad en diseño y localización. tienen mayor longevidad y por tanto mayor probabilidad de reproducción. transporte de materiales y muchos otros problemas que involucran de alguna manera procesos de optimización. y Estrategias de Evolución (Rechenberg/Schwefel). Esta investigación fue fundamentalmente académica. . en donde la estrategia de evolución más conocida hoy en día son los algoritmos genéticos. inspirados en la naturaleza. todas las dotes mentales y corporales tienden a progresar en dirección a la perfección. y a partir de entonces el desarrollo de estas técnicas ha sido continuo. interpolación de superficies. siendo aplicados constantemente en la ingeniería. juegos.ALGORITMOS EVOLUTIVOS Y ALGORITMOS GENÉTICOS “Así como la selección natural trabaja exclusivamente para y por el bien de cada ser viviente. acústica. cálculo de estrategias de mercado. La aparición de computadores de grandes prestaciones y bajo coste a mediados de los 80 permite aplicar los algoritmos evolutivos a la resolución de ciertos problemas de ingeniería que antes eran inabordables. El inicio de la utilización de las estrategias evolutivas en la solución de este tipo de problemas data del año 1960 cuando John Holland planteó la posibilidad de incorporar los mecanismos naturales de selección y supervivencia a la resolución de problemas de Inteligencia Artificial (“Adaptation in Natural and Artificial Systems”). programación y secuenciación de operaciones. astronomía y astrofísica. En este principio de selección de los individuos más aptos. programación de rutas. ingeniería aeroespacial. La simulación de procesos de evolución natural de las especies da como resultado una técnica de optimización estocástica que posteriormente fue llamada algoritmos evolutivos. Los individuos descendientes de estos individuos tienen una mayor posibilidad de transmitir sus códigos genéticos a las próximas generaciones. El Origen de las Especies Introducción Muchos problemas de optimización que aparecen en los ámbitos de las ingenierías son muy difíciles de solucionar por medio de técnicas tradicionales. siendo su realización práctica en aquella época muy difícil. Programación Genética (Koza). contabilidad lineal de procesos. y que fueron enmarcados dentro de las técnicas no convencionales de optimización para problemas del mundo real. Las aplicaciones de los algoritmos genéticos han sido muy conocidas en áreas como diseño de circuitos. Actualmente los algoritmos genéticos han cobrado gran importancia por su potencial como una técnica importante para la solución de problemas complejos. tecnología de grupos. por lo que a menudo se aplican algoritmos evolutivos.” Charles Darwin. reconocimiento de patrones.
En la actualidad los algoritmos bio-inspirados (ABs) son uno de los campos más prometedores de investigación en el diseño de algoritmos. de imitación de “comportamiento”. Son algoritmos no determinísticos. a través del mecanismo de la evolución natural. La computación bio-inspirada se basa en emplear analogías con sistemas naturales o sociales para diseñar métodos heurísticos no determinísticos de “búsqueda”. y el campo en el que nos situamos es el de la computación bio-inspirada. y son adaptativos (utilizan realimentación con el entorno para modificar el modelo y los parámetros). etc. . los más aptos. Darwin publica su libro El origen de las especies que levantó agrias polémica en el mundo científico por las revolucionarias teorías que sostenían que las especies evolucionan acorde al medio. De esta manera el universo pasaba de ser una creación de Dios estática y perfecta y se planteaba como un conjunto de individuos en constante competición y evolución para poder perpetuar su especie en el tiempo. los que mejor se adapten al medio sobreviven para perpetuar sus aptitudes. Algunos modelos de computación bioinspirados son: Algoritmos evolutivos Redes neuronales Algoritmos inmunológicos Algoritmos basados en inteligencia de enjambres (swarm intelligence) y dentro de ellos. en casi todos los organismos. que a menudo presentan. Computación evolutiva La computación evolutiva es una rama de la computación emergente que engloba técnicas que simulan la evolución natural. Las especies se crean. Fondo Histórico En 1859. para adaptarse a éste. como consecuencia de dos procesos primarios: la selección natural y la reproducción (cruce). constituyendo así una metáfora biológica para resolver problemas.Modelos de computación bio-inspirados En este apartado se pretende situar en un marco más general los temas que se tratarán en más profundidad. Parte de un hecho observado en la naturaleza: los organismos vivos poseen una destreza consumada en la resolución de los problemas que se les presentan. La evolución natural es un proceso de cambio sobre una población reproductiva que contiene variedades de individuos con algunas características heredables y en donde algunas variedades difieren en su aptitud (éxito reproductivo). implícitamente. Los algoritmos bioinspirados modelan (de forma aproximada) un fenómeno existente en la naturaleza. evolucionan y desaparecen si no se adaptan de forma que solo los mejores. una estructura paralela (múltiples agentes). de “aprendizaje”. La evolución se produce. y obtienen sus habilidades. y constituye un enfoque alternativo para abordar problemas complejos de búsqueda y aprendizaje a través de modelos computacionales de procesos evolutivos. los algoritmos basados en colonias de hormigas. casi sin proponérselo.
dada por las transformaciones de la población. hasta que la llegada de los nuevos trabajos de Holland. Algoritmos Evolutivos Este término es empleado para describir sistemas de resolución de problemas de optimización o búsqueda basados en el ordenador empleando modelos computacionales de algún mecanismo de evolución conocido como elemento clave en su diseño e implementación. Los algoritmos evolutivos son especialmente útiles cuando nos encontramos con problemas difíciles o altamente irresolubles. Friedberg. la computación ve en dicho marco un claro proceso de optimización: se toman los individuos mejores adaptados –mejores soluciones temporales –. multimodalidad. gracias entre otros factores a que añade flexibilidad y adaptabilidad en la resolución. La computación evolutiva se ha convertido en un concepto general adaptable para resolución de problemas. se cruzan –mezclan–. fuerte no linealidad. Cada ciclo de transformación y selección constituye una generación. Los algoritmos evolutivos combinan la búsqueda aleatoria. Esta población se somete a ciertas transformaciones y después a un proceso de selección. Computación Evolutiva y Optimización Un problema de optimización requiere hallar un conjunto de parámetros de forma que se cumpla un cierto criterio de calidad que se quiere optimizar. con una búsqueda dirigida dada por la selección. como lo son aquellos caracterizados por una alta dimensionalidad. Box y otros. Rechenberg. Los algoritmos evolutivos trabajan con una población de individuos.De acuerdo con esta visión de la evolución. Procedimiento de selección basado en la aptitud de los individuos para resolver el problema. en especial problemas difíciles de optimización. generando nuevos individuos –nuevas soluciones– que contendrán parte del código genético –información– de sus antecesores. maximizando o minimizando una cierta función de evaluación f(x) dada. Procedimiento de transformación para construir nuevos individuos a partir de los anteriores. que favorece a los mejores. La estructura general de los algoritmos evolutivos responde al siguiente esquema: . de forma que después de cierto número de generaciones se espera que el mejor individuo de la población esté cerca de la solución buscada. no diferenciabilidad. que representan soluciones candidatas a un problema. y el promedio de adaptación de toda la población se mejora. Principales Componentes: Población de individuos. es decir. que son una representación (no necesariamente directa) de posibles soluciones. el campo permaneció en desconocimiento por tres décadas debido a la ausencia de una plataforma computacional poderosa y defectos metodológicos de los primeros métodos (Fogel). presencia de ruido y cuando se trata con funciones dependientes del tiempo. Hoy en día el incremento de su empleo en la ciencia es exponencial. combinables con la robustez y las ventajas de la búsqueda global. Originada a finales de los años 50 con los trabajos de Bremermann. Schwefel y Fogel cambiaron lentamente el escenario.
Kursawe. Utiliza recombinación o cruce (crossover aritmético). Para realizar dicho refinamiento de las soluciones. de tal forma que son denominadas en conjunto algoritmos evolutivos como una manera de diferenciarlas de los algoritmos genéticos. ya sea determinística o probabilística. Trabaja con vectores de números reales Dcon desviaciones estándarD que codifican las posibles soluciones de problemas numéricos. P(t+1) := seleccionar [P’(t) Q]. fue diseñada inicialmente con la meta de resolver problemas de optimización discretos y continuos. end Características La característica fundamental de los algoritmos evolutivos radica en los métodos de generación de soluciones: se parte de un conjunto de soluciones iniciales y se van empleando un conjunto de operadores de búsqueda para ir refinando la solución final. Trabajan con una población de cadenas binarias para la representación del problema. y el espacio de soluciones posibles es explorado aplicando transformaciones a éstas soluciones candidatas tal y como se observa en los organismos vivientes: cruce. Atmar y otros. Rudolph. Ostermeier. inicialmente fue diseñada como un intento de crear inteligencia artificial. y emplea los mecanismos de mutación y selección. Como método de selección emplean en mecanismo de la ruleta (a veces con elitismo).t :=0. Inicializar P(t). La representación del problema se realiza mediante números reales (cualquier estructura de datos). elimina las peores soluciones de la población y no genera copia de aquellos individuos con una aptitud por debajo de la aptitud promedio. El procedimiento es muy similar a las estrategias evolutivas con la diferencia de que no emplea la recombinación. con soluciones análogas a cromosomas. evaluar [P’(t)]. Constituyen el paradigma más completo de la computación evolutiva ya que . se pueden utilizar técnicas clásicas Dcomo el seguimiento del gradiente (Hill Climbing) D complementadas con mecanismos biológicos de exploración: población de soluciones. Algoritmos Genéticos: Modelan el proceso de evolución como una sucesión de frecuentes cambios en los genes. inversión y mutación. mutación y la operación de selección. Evaluar P(t) While no se termine do begin P’(t) := variación [P(t)]. operadores genéticos. Programación Evolutiva: Técnica introducida por Fogel y extendida por Burgin. Clasificación Existen las siguientes modificaciones sobre el esquema general: Estrategias Evolutivas: Técnica desarrollada por Rechenberg y Schwefel y extendida por Herdy. t:=t+1. principalmente experimentales y considerados difíciles. y otros.
que surjan dentro del campo de la computación evolutiva. Son muy flexibles ya que pueden adoptar con facilidad nuevas ideas. además de mecanismos de selección. y como operadores de variación emplea crossover y modificación. se pueden hibridar fácilmente con otros paradigmas y enfoques. descritos mediante Expresiones-S de LISP representadas habitualmente como árboles. los individuos son programas o autómatas de longitud variable. generales o específicas. algo de mutación Métodos de selección Selección de rueda de ruleta (a veces con elitismo) Diferentes tipos de selección: lambda. aunque no tengan ninguna relación con la computación evolutiva. Además. lambda+mu. NOTA: El diagrama de funcionamiento de los algoritmos genéticos responde al siguiente esquema: Si Generación Población Inicial Evaluación de la Función Objetivo Criterios de Optimización alcanzados ? Mejor Individuo No Solución Inicio Generar Nueva Población Selección Recombinación hahghsdh Mutación Programación genética: Desarrollada por Koza..resumen de modo natural todas las ideas fundamentales de dicho enfoque. Se trata del paradigma con mayor base teórica. Como resumen de las técnicas comentadas se presenta la siguiente tabla resumen: Algoritmo Algoritmos genéticos (Goldberg) Estrategias de Evolución (Rechenberg/Schwefel) Programación evolutiva (Fogel) Programación genética (Koza) Representación del problema Cadena binaria Vector de reales + desviaciones estándar Números reales Expresiones-S de LISP representadas habitualmente como árboles Operadores de variación Mutación y crossover Mutación gaussiana y crossover aritmético (diferentes tipos) Mutación Crossover.. Diversos tipos de selección Diversos tipos de selección .mu.
por lo que estos evolucionan a través de generaciones. pero las copias no son perfectas. unas pocas pueden resultar prometedoras y pueden mostrar actividad. de nuevo por puro azar. En una algoritmo genético cada individuo esta definido como una estructura de datos que representa una posible solución del espacio de búsqueda del problema. Se realizan múltiples copias de ellas. llamado población. por tanto. aunque sólo sea actividad débil e imperfecta. Para la obtención de las próximas generaciones se crean nuevos individuos. que es obtenido usando algunas medidas de acuerdo con el problema a resolver. llamados hijos. repitiendo este proceso cientos o miles de rondas. que representan las soluciones del problema. pueden descubrirse soluciones muy buenas del problema. Estos cromosomas están compuestos por una cadena de símbolos que en muchos casos esta presentada en números binarios. . Esta descendencia prosigue con la siguiente generación. tras varias iteraciones el algoritmo converge al individuo con mejor valor de aptitud. convirtiéndolos en mejores soluciones del problema. se introducen cambios aleatorios durante el proceso de copia. utilizando dos estrategias de evolución básicas como son el operador de cruce y el de mutación (empleadas generalmente de forma aleatoria). que básicamente se realiza sobre los valores de aptitud de los individuos. Las candidatas que han empeorado o no han mejorado con los cambios en su código son eliminadas de nuevo. se seleccionan y copian estos individuos vencedores hacia la siguiente generación con cambios aleatorios. las variaciones aleatorias introducidas en la población pueden haber mejorado a algunos individuos.Algoritmos genéticos Estructura general Los algoritmos genéticos son estrategias de búsqueda estocástica basados en el mecanismo de selección natural y en algunos casos se involucran aspectos de genética natural. sin embargo. Las estrategias de evolución trabajan sobre los individuos. Entre el conjunto de soluciones candidatas generadas aleatoriamente muchas no funcionarán en absoluto y serán eliminadas. hacia la solución del problema. pero. y a través de las generaciones el individuo con mayor valor de aptitud tiene mayores posibilidades de ser seleccionado en la siguiente generación. sobre la población obtenida tras el cruce y la mutación. imitando a la evolución biológica como estrategia para resolver problemas Los algoritmos genéticos difieren de las estrategias de búsqueda convencionales en que estos (los AGs) trabajan sobre un conjunto de potenciales soluciones. y el proceso se repite. por puro azar. De nuevo. Estas candidatas prometedoras se conservan y se les permite reproducirse. el cual representara el óptimo o subóptimo del problema. Las expectativas son que la aptitud media de la población se incrementará en cada ronda y. formando un nuevo acervo de soluciones candidatas que son nuevamente sometidas a una ronda de evaluación de aptitud. Esta población esta compuesta de una serie de soluciones llamadas individuos y un individuo esta conformado por una serie de posiciones que representan cada una de las variables involucradas en los procesos de optimización y que son llamados cromosomas. El operador de selección debe mantener constante el número de individuos de la población. Una nueva generación es obtenida mediante la utilización del operador de selección. en otras palabras. más completas o más eficientes. Dentro de la población cada individuo es diferenciado de acuerdo con su valor de aptitud.
continuos o espacios de búsqueda combinados. los algoritmos genéticos no requieren información matemática adicional sobre optimización. por lo que pueden tomar otro tipo de funciones objetivo y todo tipo de restricciones (lineales y no lineales) definidas sobre espacios discretos. Trabajan sobre un conjunto de soluciones. Los diferentes valores de un gen son llamados alelos. un organismo resultante. los algoritmos genéticos proveen una gran flexibilidad para ser combinados con heurísticas específicas para la solución de un problema en particular. El conjunto completo de cromosomas se llama genotipo y un individuo en particular.Vocabulario en Algoritmos Genéticos Los algoritmos genéticos toman para su definición terminología utilizada en Genética Natural y Ciencia Computacional. Por ello. en muchos casos no encontrando soluciones globales para el problema. La robustez de los operadores de evolución hace muy efectivos a los algoritmos genéticos en procesos de búsqueda de soluciones globales. no sobre una solución única. no sobre las soluciones mismas. También se enmarcan en este campo problemas con muchas restricciones y problemas con espacios de búsqueda muy grandes. Cada cromosoma contiene una serie de valores individuales llamados genes. A diferencia de las soluciones obtenidas con un algoritmo genético. Uno o más cromosomas pueden ser requeridos para conformar una población. dejando de lado los procesos de derivación u otra información adicional. Gracias a estas características. buscando soluciones óptimas en las cercanías de esta solución particular. por lo que la literatura específica es una combinación entre los términos naturales y los artificiales. Componentes de un Algoritmo Genético Los algoritmos genéticos se pueden caracterizar a través de los siguientes componentes: Definición del problema a optimizar: Los algoritmos genéticos tienen su campo de aplicación importante en problemas de optimización complejos. se llama fenotipo. no reglas determinísticas. Cada gen contiene información valiosa de una variable en particular y su ubicación dentro del individuo se conoce como loco. las búsquedas tradicionales operan sobre una solución particular del problema. por esto se debe tener en cuenta: La Estructura de codificación con la cual se construyen las soluciones para el problema se llaman cromosomas. Utilizan información simple para determinar la aptitud de los individuos. Este tipo de optimización difiere en muchos aspectos de los procesos convencionales de optimización. Usan procesos de transición probabilística para la búsqueda de la solución. ya que los algoritmos genéticos: Trabajan sobre un conjunto codificado de soluciones. . donde se tiene diferentes parámetros o conjuntos de variables que deben ser combinadas para su solución.
y en cada vez se elige al individuo que “posea” la sección en la que se pare la ruleta). La codificación de números reales en cadenas de números binarios se debe hacer teniendo en cuenta el siguiente proceso y la precisión requerida para la solución del problema: xi [ai . pero otros pueden utilizarse en combinación. esto puede representarse como un juego de ruleta: cada individuo obtiene una sección de la ruleta. debido a su facilidad de manipulación por los operadores genéticos. Esta aptitud viene dada por una función que es la unión entre el mundo natural y el problema a resolver matemáticamente. Selección proporcional a la aptitud: los individuos más aptos tienen más probabilidad de ser seleccionados. sino que este número binario etiqueta un número dentro del intervalo inicialmente fijado. bi ] en donde el rango de la variable debe quedar dividida en (bi ai ) 10 p . su fácil transformación en números enteros o reales. (La mayoría de los AGs no utilizan elitismo puro. Selección por rueda de ruleta: una forma de selección proporcional a la aptitud en la que la probabilidad de que un individuo sea seleccionado es proporcional a la diferencia entre su aptitud y la de sus competidores. Luego la ruleta se hace girar. además de la facilidad que da para la demostración de teoremas. para cada variable es calculada como 2 mi 1 < (bi ai ) 10 p < 2 mi 1 Decodificación del cromosoma: Para determinar el número real que la cadena binaria de caracteres representa. o algunos de los mejores. (Conceptualmente. Algunos de estos métodos son mutuamente exclusivos. pero los más aptos obtienen secciones mayores que las de los menos aptos. son copiados hacia la siguiente generación en caso de que no surja nada mejor). . sino que usan una forma modificada por la que el individuo mejor.Representación para la solución del problema: Para la solución de un problema en particular es importante definir una estructura del cromosoma de acuerdo con el espacio de búsqueda. Es importante tener en cuenta que la cadena no representa un número real. Operadores Evolutivos: Selección Un algoritmo genético puede utilizar muchas técnicas diferentes para seleccionar a los individuos que deben copiarse hacia la siguiente generación. algo que se hace a menudo. Evaluación de un individuo: Nos muestra el valor de aptitud de cada uno de los individuos. donde p es la precisión requerida por el proceso (determinando así su potencia) La longitud de la cadena binaria de caracteres denotada por mi. pero no la certeza. Las diferentes variantes en la operación de selección son: Selección elitista: se garantiza la selección de los miembros más aptos de cada generación. Esta función de aptitud es particular para cada problema particular a resolver y representa para un algoritmo genético lo que el medio ambiente representa para los humanos. En el caso de los algoritmos genéticos la representación más utilizada es la representación binaria. pero abajo se listan algunos de los más comunes.
El segundo método se llama cruce. Selección generacional: la descendencia de los individuos seleccionados en cada generación se convierte en toda la siguiente generación. Este método puede ser útil para seleccionar más tarde. y uno de los individuos contribuye todo su código anterior a ese punto y el otro individuo contribuye todo su código a partir de ese punto para producir una descendencia. e implica elegir a dos individuos para que intercambien segmentos de su código. Operadores Genéticos: Cruce y Mutación Una vez que la selección ha elegido a los individuos aptos. y los miembros de cada subgrupo compiten entre ellos. reemplazando a algunos de los miembros menos aptos de la siguiente generación. Selección por estado estacionario: la descendencia de los individuos seleccionados en cada generación vuelven al acervo genético preexistente. Al igual que una mutación en los seres vivos cambia un gen por otro. y la selección se basa en este ranking. en lugar de las diferencias absolutas en aptitud. en el que se establece un punto de intercambio en un lugar aleatorio del genoma de los dos individuos.Selección escalada: al incrementarse la aptitud media de la población. en el que el valor de una posición dada en el genoma de la descendencia corresponde al valor en esa posición del genoma de uno de . Este proceso pretende simular el proceso análogo de la recombinación que se da en los cromosomas durante la reproducción sexual. Se conservan algunos individuos entre generaciones. produciendo una “descendencia” artificial cuyos individuos son combinaciones de sus padres. cuando todos los individuos tengan una aptitud relativamente alta y sólo les distingan pequeñas diferencias en la aptitud. Selección por torneo: se eligen subgrupos de individuos de la población. La ventaja de este método es que puede evitar que individuos muy aptos ganen dominancia al principio a expensas de los menos aptos. Existen dos estrategias básicas para llevar esto a cabo. Las evaluaciones de los primeros niveles son más rápidas y menos discriminatorias. mientras que los que sobreviven hasta niveles más altos son evaluados más rigurosamente. Las formas comunes de cruzamiento incluyen al cruzamiento de un punto. lo que reduciría la diversidad genética de la población y podría obstaculizar la búsqueda de una solución aceptable. una mutación en un algoritmo genético también causa pequeñas alteraciones en puntos concretos del código de un individuo. y sometiendo a una evaluación de aptitud más rigurosa y computacionalmente más costosa sólo a los que sobreviven a esta prueba inicial. La primera y más sencilla se llama mutación. Sólo se elige a un individuo de cada subgrupo para la reproducción. No se conservan individuos entre las generaciones. Selección jerárquica: los individuos atraviesan múltiples rondas de selección en cada generación. La ventaja de este método es que reduce el tiempo total de cálculo al utilizar una evaluación más rápida y menos selectiva para eliminar a la mayoría de los individuos que se muestran poco o nada prometedores. éstos deben ser alterados aleatoriamente con la esperanza de mejorar su aptitud para la siguiente generación. la fuerza de la presión selectiva también aumenta y la función de aptitud se hace más discriminadora. y al cruzamiento uniforme. Selección por rango: a cada individuo de la población se le asigna un rango numérico basado en su aptitud.
produciendo un nuevo individuo que es híbrido de sus progenitores. Tras muchas evaluaciones. iría obteniendo un valor cada vez más preciso de la aptitud media de cada uno de estos espacios. y si la solución que descubren resulta subóptima. Los operadores genéticos en este caso son operadores con memoria. por lo que cualquier mejora en alguna parte dará como resultado una mejora en el sistema completo.los padres o al valor en esa posición del genoma del otro padre. Sin embargo. No es necesario decir que hay pocos . Ventajas de los Algoritmos genéticos El primer y más importante punto es que los algoritmos genéticos son intrínsecamente paralelos. Otra ventaja del paralelismo es que. guardando en cada iteración los códigos genéticos de los mejores individuos a través de las generaciones. ya que los AGs tienen descendencia múltiple. En el contexto de los algoritmos evolutivos. un AG que evalúe explícitamente un número pequeño de individuos está evaluando implícitamente un grupo de individuos mucho más grande. Los procesos de evolución darviniana generalmente son procesos miméticos a través de las generaciones. al evaluar la aptitud de una cadena particular. La mayoría de los problemas que caen en esta categoría se conocen como “no lineales”. Image mutation Individuo sufriendo una mutación en la posición 4. Por tanto. La mayoría de los otros algoritmos son en serie y sólo pueden explorar el espacio de soluciones hacia una solución en una dirección al mismo tiempo. la aptitud de cada componente es independiente. esto se conoce como teorema del esquema. pueden explorar el espacio de soluciones en múltiples direcciones a la vez. Debido al paralelismo que les permite evaluar implícitamente muchos esquemas a la vez. Si un camino resulta ser un callejón sin salida. Cruce y mutación Efecto de estos dos operadores genéticos en los individuos de una población de cadenas de 8 bits. cada uno de los cuales contiene muchos miembros. el AG puede dirigirse hacia el espacio con los individuos más aptos y encontrar el mejor de ese grupo. Image crossov er Proceso de cruce: el punto de intercambio se establece entre las posiciones quinta y sexta del genoma. elegido con un 50% de probabilidad. dándoles una mayor probabilidad en cada ejecución de encontrar la solución. no se puede hacer otra cosa que abandonar todo el trabajo hecho y empezar de nuevo. pueden eliminarlo fácilmente y continuar el trabajo en avenidas más prometedoras. demasiado vasto para hacer una búsqueda exhaustiva en un tiempo razonable. y es la ventaja principal de los AGs sobre otros métodos de resolución de problemas. cambiando el 0 de esa posición de su genoma por un 1. un algoritmo genético sondea al mismo tiempo cada uno de los espacios a los que pertenece dicha cadena. De la misma manera. En un problema lineal. los algoritmos genéticos funcionan particularmente bien resolviendo problemas cuyo espacio de soluciones potenciales es realmente grande.
mutación y cruzamiento.problemas como éste en la vida real. En lugar de utilizar información específica conocida a priori para guiar cada paso y realizar cambios guiados expresamente hacia la mejora. en contraste. o tiene muchos óptimos locales. tras muestrear directamente sólo regiones pequeñas del vasto paisaje adaptativo. Muchos problemas de la vida real no pueden definirse en términos de un único valor que hay que minimizar o maximizar. Si una solución particular a un problema con múltiples objetivos optimiza un parámetro hasta el punto en el que ese parámetro no puede mejorarse más sin causar una correspondiente pérdida de calidad en algún otro parámetro. es decir. Muchos algoritmos de búsqueda pueden quedar atrapados en los óptimos locales. cruzamiento y mutación. imposible de explorar exhaustivamente. . por otro lado. pero. De manera similar. La no linealidad produce una explosión combinatoria en el número de posibilidades. las soluciones que son mejores que todas las que son similares a ella. perdiendo así cualquier solución novedosa que pueda existir. los AGs realizan cambios aleatorios en sus soluciones candidatas y luego utilizan la función de aptitud para determinar si esos cambios producen una mejora. y encontrar con éxito resultados óptimos o muy buenos en un corto periodo de tiempo. La no linealidad es la norma. sino que deben expresarse en términos de múltiples objetivos. Mediante sus componentes de paralelismo. debe inevitablemente comenzar descartando muchos caminos a priori. esa solución se llama óptimo paretiano o no dominada. resulta ser una de sus ventajas: a saber. de nuevo. han demostrado su efectividad al escapar de los óptimos locales y descubrir el óptimo global incluso en paisajes adaptativos muy escabrosos y complejos. Los algoritmos evolutivos. cualquier técnica que dependa de conocimiento previo fracasará cuando no esté disponible tal conocimiento. su uso del paralelismo les permite producir múltiples soluciones. a menudo involucrando contrapartidas: uno sólo puede mejorar a expensas de otro. selección. cualquier estrategia de resolución de problemas que dependa de un conocimiento previo. donde cambiar un componente puede tener efectos en cadena en todo el sistema. Finalmente. todos los caminos de búsqueda posibles están abiertos teóricamente a un AG. individualmente. La mayoría de los problemas prácticos tienen un espacio de soluciones enorme. puede parecer un desastre. los AGs no saben nada de los problemas que deben resolver. los AGs no se ven afectados negativamente por la ignorancia. en combinación pueden conducir hacia mejoras en la aptitud mucho mayores. una de las cualidades de los algoritmos genéticos que. Los cuatro componentes principales de los AGs -paralelismo. Como sus decisiones están basadas en la aleatoriedad. a primera vista. El paralelismo implícito de los AGs les permite superar incluso este enorme número de posibilidades.trabajan juntos para conseguir esto. igualmente buenas. Los AGs. el reto se convierte entonces en cómo evitar los óptimos locales. Los AGs son muy buenos resolviendo estos problemas: en particular. ruidosa. y luego un supervisor humano puede seleccionar una de esas candidatas para su utilización. al carecer de ideas preconcebidas basadas en creencias establecidas sobre “cómo deben hacerse las cosas” o sobre lo que “de ninguna manera podría funcionar”. donde posiblemente una solución candidata optimiza un parámetro y otra candidata optimiza uno distinto. y donde cambios múltiples que. los AGs no tienen este problema. Otra ventaja notable de los algoritmos genéticos es que se desenvuelven bien en problemas con un paisaje adaptativo complejo: aquéllos en los que la función de aptitud es discontinua. pero que no son mejores que otras soluciones distintas situadas en algún otro lugar del espacio de soluciones. Otra área en el que destacan los algoritmos genéticos es su habilidad para manipular muchos parámetros simultáneamente. son perjudiciales. al mismo problema. cambia con el tiempo.
explorando regiones que algoritmos producidos con inteligencia podrían no haber tenido en cuenta. el propio código del programa sí cambia. El problema de cómo escribir la función de aptitud debe considerarse cuidadosamente para que se pueda alcanzar una mayor aptitud y verdaderamente signifique una solución mejor para el problema dado. Si se elige mal una función de aptitud o se define de manera inexacta. para la mayoría de las situaciones. y pueden representar muchos tipos diferentes de problema con éxito. en las que la situación de los puntos mejorados ofrecen información engañosa sobre dónde se encuentra probablemente el óptimo global. no son la panacea. es definir a los individuos como listas de números -binarios. La solución a este problema es la misma para los algoritmos genéticos y la evolución biológica: la evolución no es un proceso que deba encontrar siempre el óptimo global. enteros o realesdonde cada número representa algún aspecto de la solución candidata. como son el tamaño de la población. al cambiar demasiado rápido para que la selección llegue a producir convergencia. Si el tamaño de la población es demasiado pequeño. y revelando potencialmente soluciones asombrosas y creativas. El lenguaje utilizado para especificar soluciones candidatas debe ser robusto. Además de elegir bien la función de aptitud. se demostrará que todas ellas pueden superarse y que ninguna de ellas afecta a la validez de la evolución biológica. aunque en realidad lo que está pasando es que el AG está haciendo lo que se le pidió hacer. el ritmo de mutación y cruzamiento. eso será suficiente. incluso aunque el óptimo global no pueda alcanzarse fácilmente desde ese punto. La primera y más importante consideración al crear un algoritmo genético es definir una representación del problema. Hay dos maneras principales para conseguir esto. puede alterarse el desarrollo de esquemas beneficiosos y la población puede entrar en catástrofe de errores. no lo que sus creadores pretendían que hiciera). La solución ha sido “la evolución de la evolutividad”: las adaptaciones que alteran la habilidad de una especie para adaptarse. puede que el algoritmo genético sea incapaz de encontrar una solución al problema. o puede acabar resolviendo el problema equivocado (esta última situación se describe a veces como la tendencia del AG a “engañar”. Un problema con el que los algoritmos genéticos tienen dificultades son los problemas con las funciones de aptitud “engañosas”. Un problema muy conocido que puede surgir con un AG se conoce como convergencia prematura. Los AGs tienen ciertas limitaciones.pueden viajar extensamente por el paisaje adaptativo. Si un individuo que es más apto que la mayoría de sus . el tipo y fuerza de la selección. sin embargo. utilizada por la mayoría de los algoritmos genéticos. puede que el algoritmo genético no explore suficientemente el espacio de soluciones para encontrar buenas soluciones consistentemente. Puede funcionar casi igual de bien alcanzando la una solución muy buena aunque no sea la realmente óptima y. La primera. debe ser capaz de tolerar cambios aleatorios que no produzcan constantemente errores fatales o resultados sin sentido. es decir. Ambos métodos producen representaciones robustas ante la mutación. Limitaciones de los Algoritmos Genéticos Aunque los algoritmos genéticos han demostrado su eficiencia y potencia como estrategia de resolución de problemas. En otro método. Si el ritmo de cambio genético es demasiado alto o el sistema de selección se escoge inadecuadamente. también deben elegirse cuidadosamente los otros parámetros de un AG. la programación genética.
La selección escalada.competidores emerge muy pronto en el curso de la ejecución. en lugar de rastrear el paisaje adaptativo lo bastante a fondo para encontrar el óptimo global. por rango y por torneo son tres de los métodos principales para conseguir esto. simplemente es que los métodos analíticos tradicionales consumen mucho menos tiempo y potencia computacional que los AGs y. Los métodos más comunes implementados por los investigadores en AGs para solucionar este problema implican controlar la fuerza selectiva. varios investigadores aconsejan no utilizar algoritmos genéticos en problemas resolubles de manera analítica. donde incluso una variación aleatoria en el ritmo de reproducción puede provocar que un genotipo se haga dominante sobre los otros. No es que los algoritmos genéticos no puedan encontrar soluciones buenas para estos problemas. a menudo está demostrado matemáticamente que ofrecen la única solución exacta. provocando que el algoritmo converja hacia el óptimo local que representa ese individuo. se puede reproducir tan abundantemente que merme la diversidad de la población demasiado pronto. . Esto es un problema especialmente común en las poblaciones pequeñas. Finalmente. para no proporcionar tanta ventaja a los individuos excesivamente aptos. a diferencia de los AGs.
Documents Similar To bioinformatica

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución