Etiqueta: Computación evolutiva

Alineamiento de secuencias

Alineamiento de secuencias

En palabras de los investigadores Sanchez, Lopez y Maojo, en el artículo escrito el año 1999 sobre “bioinformatica y salud”, la bioinformática se encuentra en la intersección entre las ciencias de la vida y de la información, proporciona las herramientas y recursos necesarios para favorecer la investigación en biología molecular. Como campo interdisciplinario, comprende la investigación y el desarrollo de sistemas útiles para entender el flujo de información desde los genes a las estructuras moleculares, su función bioquímica, su conducta biológica y, finalmente, su influencia en las enfermedades y en la salud.

Los estímulos principales para el desarrollo de la bioinformática son: (1) El enorme volumen de datos generados por los distintos proyectos denominados genoma. (2) Los nuevos enfoques experimentales, basados en biochips, que permiten obtener datos genéticos a gran velocidad, bien de genomas individuales o de enfoques celulares, expresión génica. (3) El desarrollo de Internet, que permite el acceso universal a las bases de datos de información biológica. La magnitud de la información que genera las investigaciones realizadas sobre el genoma humano es tal que, probablemente, supera la generada por otras investigaciones en otras disciplinas científicas. Como se sabe, la vida es la forma más compleja de organización de la materia que se conoce. En estos momentos, las computadoras no clasificadas para uso civil más potentes del mundo están dedicadas a la investigación biológica, concretamente a la obtención y al análisis de las secuencias de nucleótidos de los genomas conocidos. Ante tal situación, uno de los retos de la bioinformática es el desarrollo de métodos que permitan integrar los datos genómicos, de secuencia, de expresión, de estructura, de interacciones y otras, para explicar el comportamiento global de la célula viva, minimizando la intervención humana. Dicha integración, sin embargo, no puede producirse sin considerar el conocimiento acumulado durante decenas de años, producto de la investigación de miles de científicos, recogido en millones de comunicaciones científicas.

La bioinformática se ocupa de la utilización y almacenamiento de grandes cantidades de información biológica, es decir, trata del uso de las computadoras para el análisis de la información biológica, entendida esta como la adquisición y consulta de datos, los análisis de correlación, la extracción y el procesamiento de la información. En otras palabras, la bioinformática es un área del espacio que representa la biología molecular computacional, que incluye la aplicación de las computadoras y de las ciencias de la información en áreas como la geonómica, el mapeo, la secuencia y determinación de las secuencias y estructuras por métodos clásicos. Las metas fundamentales de la bioinformática son la predicción de la estructura tridimensional de las proteínas a partir de su secuencia, la predicción de las funciones biológicas y biofísicas a partir de la secuencia o la estructura, así como simular el metabolismo y otros procesos biológicos basados en esas funciones. Muchos de los métodos de la computación y de las ciencias de la información sirven para estos fines, incluyendo el aprendizaje de las máquinas, las teorías de la información, la estadística, la teoría de los gráficos, los algoritmos, la inteligencia artificial, los métodos estocásticos, la simulación, la lógica, etc.

Ingresando en el tema del presente artículo, según los investigadores Smith y Waterman, en el artículo escrito el año 1981 sobre “identificación de secuencias moleculares comunes”, complementado con la opinión de los investigadores Schneider y Stephens, en el artículo escrito el año 1990 sobre “logotipos de secuencia: una nueva manera de ver las secuencias de consenso”, un alineamiento de secuencias en bioinformática es una forma de representar y comparar dos o más secuencias o cadenas de ácido desoxirribonucleico, acido ribonucleico o estructuras primarias proteicas para resaltar sus zonas de similitud, que podrían indicar relaciones funcionales o evolutivas entre los genes o proteínas consultados. Las secuencias alineadas se escriben con las letras, que representan aminoácidos o nucleótidos, en filas de una matriz en las que, si es necesario, se insertan espacios para que las zonas con idéntica o similar estructura se alineen.

Si dos secuencias en un alineamiento comparten un ancestro común, las no coincidencias pueden interpretarse como mutaciones puntuales o sustituciones, y los huecos como indels o mutaciones de inserción o borrado, introducida en uno o ambos linajes en el tiempo que transcurrió desde que divergieron. En el alineamiento de secuencias proteicas, el grado de similitud entre los aminoácidos que ocupan una posición concreta en la secuencia puede interpretarse como una medida aproximada de conservación en una región particular, o secuencia motivo, entre linajes. La ausencia de sustituciones, o la presencia de sustituciones muy conservadas en una región particular de la secuencia indican que esta zona tiene importancia estructural o funcional. Aunque las bases nucleotídicas del ácido desoxirribonucleico y ácido ribonucleico son bastante similares entre sí que con los aminoácidos, la conservación del emparejado de bases podría indicar papeles funcionales o estructurales similares. El alineamiento de secuencias puede utilizarse con secuencias no biológicas, como en la identificación de similitudes en series de letras y palabras del lenguaje humano o en análisis de datos financieros.

Secuencias muy cortas o muy similares pueden alinearse manualmente. Aun así, los problemas más interesantes necesitan alinear secuencias largas, muy variables y extremadamente numerosas que no pueden ser alineadas por seres humanos. El conocimiento humano se aplica principalmente en la construcción de algoritmos que produzcan alineamientos de alta calidad, y ocasionalmente ajustando el resultado final para representar patrones que son difíciles de introducir en algoritmos, especialmente en el caso de secuencias de nucleótidos. Las aproximaciones computacionales al alineamiento de secuencias se dividen en dos categorías: alineamiento global y alineamiento local. Calcular un alineamiento global es una forma de optimización global que “obliga” al alineamiento a ocupar la longitud total de todas las secuencias problema. Comparativamente, los alineamientos locales identifican regiones similares dentro de largas secuencias que normalmente son bastante divergentes entre sí. A menudo se prefieren los alineamientos locales, pero pueden ser más difíciles de calcular porque se añade el desafío de identificar las regiones de mayor similitud. Se aplican gran variedad de algoritmos computacionales al problema de alineamiento de secuencias, como métodos lentos, pero de optimización, como la programación dinámica, y métodos heurísticos o probabilísticos eficientes, pero no exhaustivos, diseñados para búsqueda a gran escala en bases de datos.

Según el investigador Robles, en la tesis de grado escrita el año 2003 denominada “clasificación supervisada basada en redes Bayesianas y su aplicación en biología computacional”, cuando se analizan secuencias se suelen utilizar de manera indiscriminada los términos de similitud y homología. Sin embargo, estos términos se refieren a conceptos muy distintos. Similitud es la característica resultante de la observación de que dos o más secuencias muestran algún grado de coincidencia en la secuencia de aminoácidos. La similitud, dado que es una observación, no puede ser un indicador a priori de ninguna relación biológica entre las secuencias, ya que ésta se podría deber a cambios que se hayan dado al azar. En cambio, se habla de homología cuando la similitud se puede atribuir a verdaderas razones evolutivas y no simplemente al azar. En este caso, se afirma que hay regiones de la secuencia conservadas en el tiempo. La similitud es producto de una medida, mientras que la homología es una hipótesis que se postula con base en la similitud de las secuencias estudiadas y otras características adicionales. Se puede hablar de un porcentaje de similitud entre dos secuencias pero no de un porcentaje de homología. Ya que la homología es una característica cualitativa, no es susceptible de ser medida, por lo que dos secuencias simplemente o son o no son homologas.

El alineamiento es el procedimiento que permite dar los primeros pasos hacia la conclusión de que dos o más secuencias son homologas. Consiste en establecer un segmento entre ellas, donde el número de coincidencias sea máximo. Una coincidencia se presenta cuando el aminoácido de la secuencia A es igual al de la secuencia B o bien si sus características físico-químicas, entre las que resaltan la hidrofobicidad, tamaño y carga, son similares. Los programas de alineamiento de secuencias utilizan matrices de sustitución, en las que a cada combinación posible de aminoácidos se le asigna un valor. Estas matrices de sustitución varían desde modelos simples que asignan el valor uno si los aminoácidos son iguales y cero si son distintos, hasta modelos más complejos evolutivos, estructurales o funcionales, que fijan un determinado costo por sustituir un aminoácido por otro dependiendo de ambos aminoácidos. Esta técnica, aparentemente sencilla, se hace más compleja en la medida en que el tamaño de las secuencias a comparar se hace mayor y, más aún, cuando se comparan más de dos secuencias. Para realizar esta tarea, se emplean distintos programas computacionales que dadas dos secuencias, generan el mejor alineamiento.

Referencias Bibliográficas

  • Sánchez F. Martin, López Campos G. & Maojo García V. (1999) Bioinformática y salud: impactos de la aplicación de las nuevas tecnologías para el tratamiento de la información genética en la investigación biomédica y la práctica clínica. Informática y Salud (19). Disponible en: http://www.seis.es/i_s/i_s19/i_s19l.htm
  • Schneider TD, Stephens RM (1990) Sequence logos: a new way to display consensus sequences. Nucleic Acids Res 18: pp. 6097-6100.
  • Smith, T.F., and Waterman, M.S. (1981) Identification of common molecular sequence, J. Mol. Biol., 1981, 147, pp. 195-197.
  • Robles Víctor (2003) Clasificación Supervisada basada en Redes Bayesianas. Aplicación en Biología Computacional. Tesis de doctorado. Universidad Politécnica de Madrid. Facultad de Informática. Madrid, 2003.
Guillermo Choque Aspiazu
http://www.eldiario.net
Marzo 5 de 2012
Algoritmos genéticos masivamente paralelos

Algoritmos genéticos masivamente paralelos

Según Beyer, en el artículo escrito el año 2001 acerca de la “teoría de las estrategias de la evolución”, las estrategias evolutivas son métodos computacionales que 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. Entre los años 1965 y 1973 Rechenberg las introdujo como método para optimizar parámetros reales para ciertos dispositivos. La misma idea fue desarrollada poco después por Schwefel entre los años 1975 a 1977. El campo de las estrategias evolutivas ha permanecido como un área de investigación activa, cuyo desarrollo se produce en su mayor parte, de modo independiente al de los algoritmos genéticos. En palabras de Michalewicz, en el libro escrito el año 1996 acerca de “Programa evolutivo = Algoritmo genético + Estructura de datos”, la programación evolutiva es prácticamente una variación de los algoritmos genéticos, donde lo que cambia es la representación de los individuos. En el caso de la programación evolutiva los individuos son tripletas cuyos valores representan estados de un autómata finito. Cada terna está formada por el valor del estado actual, un símbolo del alfabeto utilizado y el valor del nuevo estado. Fogel, Owens y Walsh fueron los creadores en 1966 de la programación evolutiva, una técnica en la cual los candidatos a soluciones a tareas determinadas son representados por máquinas de estados finitos, cuyos diagramas de estados de transición evolucionaban mediante mutación aleatoria, seleccionándose el que mejor se aproximara a la meta.

La primera mención del término algoritmo genético y la primera publicación sobre una aplicación del mismo, se deben al investigador Bagley en la disertación presentada el año 1967 sobre “el comportamiento de los sistemas adaptativos que emplean algoritmos genéticos y correlacionales.” Bagley diseñó algoritmos genéticos para buscar conjuntos de parámetros en funciones de evaluación de juegos, y los comparó con los algoritmos de correlación, procedimientos de aprendizaje modelados después de los algoritmos de pesos variantes de ese periodo. Sin embargo el que es considerado como el creador de los algoritmos genéticos es el gran investigador John Holland a partir de su libro escrito el año 1975 titulado “Adaptación en sistemas naturales y artificiales”. En contraste con las estrategias evolutivas y la programación evolutiva, el propósito original de Holland no era diseñar algoritmos para resolver problemas concretos, sino estudiar, de un modo formal, el fenómeno de la adaptación tal y como ocurre en la naturaleza, y desarrollar vías para extrapolar esos mecanismos de adaptación natural a los sistemas computacionales. En el libro de Holland se presenta el algoritmo genético como una abstracción de la evolución biológica, y se proporciona el entramado teórico para la adaptación bajo el algoritmo genético. El algoritmo genético de Holland es un método para desplazarse, de una población de cromosomas, representado por bits a una nueva población, utilizando un sistema similar a la selección natural junto con los operadores de apareamiento, mutación e inversión inspirados en la genética. En este primitivo algoritmo, cada cromosoma consta de genes, y cada uno de ellos es una muestra de un alelo particular, cero o uno.

Holland adapta los operadores de selección, apareamiento, mutación e inversión a su algoritmo genético: (1) Selección. Este operador escoge entre los cromosomas de la población aquellos con capacidad de reproducción, y entre estos, los que sean más compatibles, producirán más descendencia que el resto. (2) Apareamiento. Este operador extrae partes de dos cromosomas, imitando la combinación biológica de dos cromosomas aislados. (3) Mutación. Operador que se encarga de cambiar, de modo aleatorio, los valores del alelo en algunas localizaciones del cromosoma. (4) Inversión. Este operador invierte el orden de una sección contigua del cromosoma, recolocando por tanto el orden en el que se almacenan los genes. La mayor innovación de Holland fue la de introducir un algoritmo basado en poblaciones con apareamientos, mutaciones e inversiones. Es más, Holland fue el primero en intentar colocar la computación evolutiva sobre una base teórica firme. Hasta hace poco, esta base teórica, fundamentada en la noción de esquemas, es la estructura sobre la que se edificaron la mayoría de los trabajos teóricos sobre algoritmos genéticos.

Sin embargo según los investigadores Alba y Cotta, en el tutorial escrito el año 2003 sobre “computación evolucionaría”, los algoritmos genéticos secuenciales suelen presentar las siguientes tres desventajas: (1) Para mantener grandes poblaciones de individuos se necesita mucha memoria y puede tornarse ineficiente abordar problemas con estos requerimientos de manera secuencial. (2) Al afrontar problemas complejos, la evaluación de la función de adaptabilidad puede ser muy costosa en tiempo de cómputo y el lapso demandado por una ejecución completa de un algoritmo genético podría ser inaceptable. (3) Los algoritmos genéticos secuenciales pueden converger prematuramente hacia valores subóptimos. Una solución para contrarrestar estos tres problemas consiste en paralelizar la ejecución de los algoritmos genéticos. Un algoritmo genético que utiliza más de un procesador para llevar a cabo su ejecución, es llamado algoritmo genético paralelo. Además de las mejoras en el rendimiento de los sistemas paralelos respecto de sus pares secuenciales, pueden lograrse beneficios adicionales referentes a la calidad de las soluciones.

En la tesis de doctorado del investigador Alba, escrita el año 1999 sobre “Análisis y Diseño de Algoritmos Genéticos Paralelos Distribuidos”, se menciona que antes de realizar la paralelización de un algoritmo, de cualquier tipo, es imprescindible realizar una primera fase de estudio acerca de los elementos del algoritmo que son susceptibles de paralelizarse. En el caso de los algoritmos genéticos resulta evidente que la evaluación de la adecuación de los individuos es una tarea cuya paralelización no afecta al comportamiento del algoritmo. Sin embargo, el operador de selección sí debe ser aplicado de forma global a toda la población si se quiere que el comportamiento del algoritmo siga siendo el mismo que el de la versión secuencial. Esta primera aproximación para la paralelización de los algoritmos genéticos dará lugar a un conjunto de algoritmos que recibirán el nombre de algoritmos maestro-esclavo. La otra gran aproximación a la paralelización de los algoritmos genéticos consiste en dividir la población inicial en subpoblaciones de mayor o menor tamaño que se comuniquen de alguna manera. Este sistema de paralelización es el que más éxito ha obtenido en comparación con su equivalente secuencial. Además de las mejoras de rendimiento debidas a la subdivisión del problema se ha demostrado que el hecho de considerar subpoblaciones que evolucionan independientemente suele, por lo general, ayudar en el proceso de búsqueda. Este tipo de algoritmos se dice que da lugar a especies o nichos de individuos separados. Dentro de esta segunda aproximación se pueden distinguir entre algoritmos de grano grueso y algoritmos de grano fino. La diferencia entre ambos es el tamaño de las poblaciones, que suele ser mayor en los primeros, y la forma en que los individuos interactúan los unos con los otros.

En el artículo de Gordon y Whitley, escrito el año 1993 y relacionado con “algoritmos genéticos paralelos y seriales como optimizadores de funciones”, se propone una clasificación de algoritmo genético paralelo que reconoce tres categorías: (1) Algoritmo genético paralelo de población global, una versión del modelo maestro-esclavo que utiliza selección por torneo y sus versiones elitistas para simplificar el paralelismo. (2) Algoritmo genético paralelo con modelo de islas y migración, similar a los modelos de Gorges-Schleuter, descrito en el articulo “paralelismo explicito de algoritmos genéticos a través de estructuras poblacionales”. (3) Algoritmos genéticos masivamente paralelos o algoritmos genéticos celulares, que asignan un número bajo de individuos por elemento de procesamiento. En este modelo, cada individuo se procesa en paralelo en cada generación y el apareamiento está limitado a un deme, o vecindad, del individuo. Usualmente la topología de conexión y la estructura de los demes es fija, y se corresponde con la topología de conexión de los elemento de procesamiento en la super computadora. La denominación celular se justifica por comportarse el algoritmo genético paralelo como un tipo particular de autómata celular.

Según Michalewicz, en la obra citada párrafos arriba, los algoritmos genéticos masivamente paralelos se caracterizan por asignar, en el caso ideal, un procesador a cada individuo. Es por esto que en general se utiliza en arquitecturas con un gran número de procesadores y alguna topología de interconexión entre ellos, tal como anillo, grilla, hipercubo, etc. Durante la ejecución del algoritmo un individuo puede solamente competir y aparearse con sus vecinos, los cuales se encuentran definidos según la topología de interconexión. El investigador Baluja, en el artículo escrito el año 1992 denominado “algoritmo genético paralelo masivamente distribuido”, modificó los algoritmos genéticos masivamente paralelos, introduciendo poblaciones estructuradas con solapamiento, que permiten la transferencia gradual de información genética sin la introducción súbita de cromosomas. Para el diseño de su modelo de algoritmo genético paralelo masivamente distribuido, Baluja analizó estructuras de las poblaciones y tamaños de las secciones solapadas, indicando que debe lograrse un compromiso entre la lentitud de propagación de soluciones para áreas de solapamiento pequeñas y la desviación de la idea de poblaciones múltiples al crecer las áreas y acercarse a un modelo panmíctico, en el que todos los individuos tienen la misma probabilidad de aparearse y el apareamiento es al azar.

Referencias Bibliográficas

  • Alba Enrique (1999) Análisis y Diseño de Algoritmos Genéticos Paralelos Distribuidos. Tesis de Doctorado, Universidad de Málaga.
  • Alba, E., Cotta, C. (2003) Tutorial on evolutionary computation. Disponible en http://www.lcc.uma.es/~ccottap/semEC/ec.html [Consulta: Marzo 2006]
  • Bagley, J.D. (1967) The behavior of adaptive systems which employ genetic and correlation algorithms. Dissertation Abstracts International. 1967. Vol. 28 No.12.
  • Baluja S. (1992) A Massively Distributed Parallel Genetic Algorithm. CMU-CS-92-196R, Carnegie Mellon.
  • Beyer, H.G. (2001) The Theory of Evolution Strategies. Natural Computing Series. Springer, Berlin.
  • Gordon V. & Whitley D. (1993) Serial and Parallel Genetic Algorithms as Function Optimizers. Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 177-183, 1993.
  • Gorges-Schleuter M. (1990) Explicit parallelism of genetic algorithms through population structures. Proceedings of 1st PPSN’90, pp. 150-159.
  • Holland, J. (1975) Adaptation in Natural and Artificial Systems. Ann Arbor, MI: The University of Michigan Press. • Michalewicz, Zbigniew (1996) Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1996.
Guillermo Choque Aspiazu
http://www.eldiario.net/
Febrero 27 de 2012
Operadores genéticos

Operadores genéticos

Los algoritmos genéticos constituyen una de las técnicas de computación evolutiva más difundidas como consecuencia de su versatilidad para resolver un amplio rango de problemas. Al constituir un caso de técnica evolutiva, los algoritmos genéticos basan su operativa en una emulación de la evolución natural de los seres vivos, trabajando sobre una población de soluciones potenciales evoluciona de acuerdo a interacciones y transformaciones únicas. Los individuos que constituyen la población se esfuerzan por sobrevivir: una selección programada en el proceso evolutivo, inclinada hacia los individuos más aptos, determinando aquellos individuos que formarán parte de la siguiente generación. El grado de adaptación de un individuo se evalúa de acuerdo al problema a resolver, mediante la definición de una función de adecuación al problema, la denominada función de adaptabilidad. Bajo ciertas condiciones, el mecanismo definido por los operadores inspirados por la genética natural y la evolución darwiniana lleva a la población a converger hacia una solución aproximada al óptimo del problema, luego de un determinado número de generaciones.

La formulación tradicional de un algoritmo genético fue presentada de excelente manera por el discípulo de Jhon Holland llamado David Goldberg, este último popularizó el uso de los algoritmos genéticos para una variada gama de problemas en las áreas de búsqueda, optimización y aprendizaje automático. En su formulación clásica, los algoritmos genéticos se basan en el esquema genérico de un algoritmo evolutivo. A partir de este esquema, el algoritmo genético define “operadores evolutivos” que implementan la recombinación de individuos, a través del operador de apareamiento, y la variación aleatoria para proporcionar diversidad, el operador de mutación. La característica distintiva de los algoritmos genéticos respecto a las otras técnicas evolutivas consiste en el uso fundamental del apareamiento como operador principal, mientras que la mutación se utiliza como operador secundario tan solo para agregar una nueva fuente de diversidad en el mecanismo de exploración del espacio de soluciones del problema. Inclusive la mutación puede llegar a ser un operador opcional o estar ausente en algunas variantes de algoritmos genéticos que utilizan otros operadores para introducir diversidad. En general, los algoritmos genéticos se han utilizado para trabajar con codificaciones binarias para problemas de búsqueda en espacios de cardinalidad numerable, aunque su alto nivel de aplicabilidad ha llevado a proponer su trabajo con codificaciones reales, e inclusive con codificaciones no tradicionales, dependientes de los problemas a resolver.

La gran mayoría de las variantes de algoritmos genéticos utiliza como principales operadores a la selección, el apareamiento o recombinación y la mutación. El mecanismo de selección determina el modo de perpetuar buenas características, que se asumen son aquellas presentes en los individuos más adaptados. El mecanismo de selección proporcional o selección por ruleta elige aleatoriamente individuos utilizando una ruleta sesgada, en la cual la probabilidad de ser seleccionado es proporcional a la adaptabilidad de cada individuo. Otros mecanismos de selección introducen diferentes grados de elitismo, conservando un cierto número prefijado de los mejores individuos a través de las generaciones. En el caso de la selección por torneo se escogen aleatoriamente un determinado número de individuos de la población, los cuales compiten entre ellos para determinar cuáles se seleccionarán para reproducirse, de acuerdo a sus valores de adaptación. El mecanismo de selección basado en el rango introduce el mayor grado de elitismo posible, al mantener entre generaciones un porcentaje generalmente elevado, de los mejores individuos de la población. Estas diferentes políticas de selección, conjuntamente con políticas similares utilizadas para determinar los individuos reemplazados por los descendientes generados posibilitan el diseño de diferentes modelos evolutivos para los algoritmos genéticos. Los esquemas de codificación binaria de tamaño fijo tienen como ventaja principal que resulta sencillo definir operadores evolutivos simples sobre ellos. En la formulación clásica de un algoritmo genético, denominada por Goldberg como algoritmo genético simple, se propone como operador de recombinación el apareamiento de un punto, que consiste en obtener dos descendientes a partir de dos individuos padres seleccionando un punto al azar, cortando los padres e intercambiando los trozos del cromosoma.

El operador tradicional de mutación introduce diversidad en el mecanismo evolutivo, simplemente modificando de manera aleatoria uno de los valores binarios del cromosoma. Sobre un esquema de codificación binaria la modificación consiste en invertir el valor binario de un alelo, y por ello recibe el nombre de mutación de inversión del valor de un bit. El operador tradicional de mutación introduce diversidad en el mecanismo evolutivo, simplemente modificando aleatoriamente uno de los valores binarios del cromosoma. Sobre un esquema de codificación binaria la modificación consiste en invertir el valor binario de un alelo, y por ello recibe el nombre de mutación de inversión del valor de un bit. Tanto el apareamiento como la mutación son operadores probabilísticos, en el sentido en que se aplican o no, teniendo en cuenta una tasa de aplicación del operador. Generalmente la tasa de aplicación del operador de apareamiento es elevada en un algoritmo genético simple, mientras que la tasa de aplicación del operador de mutación es muy baja, del orden de 0,001 para cada bit en la representación. Algunos operadores evolutivos más complejos han sido propuestos como alternativas para modificar el comportamiento del mecanismo de exploración del espacio de soluciones. Es habitual encontrar operadores de apareamiento multipunto en donde se utilizan dos o más puntos de corte o uniformes en donde para cada posición en el cromosoma se decide intercambiar material genético de acuerdo a una probabilidad prefijada.

El operador de selección juega un importante papel tanto en los algoritmos evolutivos secuenciales como en los paralelos, ya que guía la búsqueda y provoca la convergencia de la población de individuos. Por tanto, representa el tan importante compromiso entre exploración y explotación. De entre los operadores de selección proporcional a la adecuación, la implementación conocida como “ruleta” es la más popular. Sin embargo, también es de mayor complejidad algorítmica y con tendencia a cometer errores estocásticos respecto de la implementación conocida como “muestreo estocástico universal”. De hecho, la selección proporcional a la adecuación puede usarse para seleccionar un conjunto arbitrario de parejas y por tanto puede utilizarse en modelos secuenciales generacionales o de estado estacionario, así como en modelos paralelos distribuidos o celulares. La selección proporcional usa el valor de adecuación para seleccionar parejas o bien el individuo que se desea reemplazar. Algunos mecanismos utilizan una ordenación creciente atendiendo a la adecuación de los individuos para después seleccionar atendiendo a su posición en dicha ordenación. Esto reduce el error estocástico debido a valores de adecuación similares. Existen muchos otros mecanismos de selección interesantes como el torneo, y sobre todo variantes de estos modelos básicos que modifican de alguna forma la probabilidad de selección.

El operador de apareamiento es muy importante en el campo de los algoritmos genéticos. Existen numerosas variantes de él, todas ellas clasificables en tres categorías de alto nivel: (1) Operadores de apareamiento puros. Los cuales pueden ser aplicados en cualquier algoritmo genético. (2) Operadores de apareamiento híbridos: que mezclan un operador puro con una técnica no genética. (3) Operadores de apareamiento dependientes del problema: operadores que realizan operaciones basadas en el conocimiento del problema y por tanto son sólo aplicables a dicho problema. Existen numerosos tipos de apareamiento. El estándar es binario y genera dos hijos. Sin embargo no es raro encontrar aplicaciones que usan un apareamiento que genera un único hijo. También existen operadores de apareamiento típicos de problemas de reordenación y otros campos sobre todo de optimización combinatoria, en los que dicho operador transmite de padres a hijos la admisibilidad como solución al problema. El operador más tradicional genera aleatoriamente el mismo punto de apareamiento en ambos padres e intercambia los cuatro segmentos resultantes dando lugar a dos hijos nuevos. Existen numerosas extensiones a dos puntos y N puntos. Esta familia de operadores de apareamiento es eficiente y de aplicación bastante genérica. El apareamiento aritmético tradicional es un tipo especial de operador aritmético sesgado. El sesgo hacia el mejor padre de los dos últimos operadores permite introducir un componente de explotación en el comportamiento de exploración típico de cualquier apareamiento. Ambos operadores trabajan con independencia de la longitud de la cadena de parámetros, lo que supone una ventaja adicional en ciertos problemas.

El operador de mutación se describe por la instanciación a dos operadores concretos del operador genérico mencionado para un algoritmo genético. En el caso de genotipo binario se utiliza el tradicional operador de complemento de bits, mientras que en el caso de genotipo real se utiliza una definición propia que se encuentra implementada de forma parecida en la literatura asociada a este tipo de codificación. La mutación ha sido tradicionalmente entendida como un operador de segunda fila en los algoritmos genéticos. Sin embargo, numerosos estudios en este campo, así como en otros dominios donde la mutación es determinante, han puesto de manifiesto la gran importancia de este operador en problemas de complejidad real, ya que es el único que introduce nueva información en una población secuencial, permitiendo así escapar de óptimos locales y ampliando la exploración del algoritmo. Tanto el apareamiento como la mutación pueden sufrir un cambio dinámico durante la evolución en su conjunto de parámetros, típicamente en la probabilidad de aplicación. Esta característica ha proporcionado buenos resultados en algunos campos de aplicación aunque aún es un proceso relativamente caro debido a que dichos cambios surgen como consecuencia de una monitorización de la diversidad de la población, menor distancia de Hamming, mayor mutación o de la aportación que hacen a la adecuación de los descendientes generados.

Guillermo Choque Aspiazu
http://www.eldiario.net/
Diciembre 13 de 2010
Epigenómica computacional

Epigenómica computacional

La investigación biológica dedicada a elucidar los factores y mecanismos asociados y que causan enfermedades comunes crónicas-degenerativas se ha visto reforzada enormemente por la aparición de nuevas tecnologías que permiten por primera vez en la historia obtener una visión tanto general como detallada del funcionamiento de los organismos vivos. Estas tecnologías se agrupan dentro de lo que se denomina “ómicas” y se pueden clasificar en una serie de subgrupos principales que incluyen genómica, transcriptómica, proteómica y metabolómica. Con su aparición, también surgió la esperanza de que su uso diera lugar a rápidos descubrimientos que facilitarían de manera casi inmediata la capacidad de prevenir, diagnosticar y desarrollar nuevas terapias contra las enfermedades más comunes, entre las que destacan las cardiovasculares. Sin embargo, a pesar de los grandes progresos tecnológicos, la promesa de que las “ómicas” iban a producir rápidos avances en la medicina y la salud pública no se ha cumplido todavía, principalmente debido a las limitaciones conceptuales y experimentales que impiden considerar en su totalidad las complejas y dinámicas interacciones entre la abundancia de factores involucrados en la iniciación, el progreso y la manifestación de la enfermedad.

La disponibilidad de la secuencia completa del genoma humano es el punto de partida para la ingente tarea de comprender toda la información genómica, es decir, descifrar qué tipo de información conlleva el genoma, cómo está codificada, y sobre todo cómo se implementa de modo interactivo en el curso del desarrollo embrionario y durante la vida del organismo. Este último aspecto, que ocupa actualmente la atención de un gran número de investigadores biomédicos, se integra en el concepto de epigenómica e incluye la investigación con células madre, la diferenciación celular, la impronta genética, la senescencia y una gran parte de los procesos de regulación génica que tienen que ver con la organización del ácido desoxirribonucleico en cromatina. La epigenómica recuerda que lo que se transmite de una célula a otra no es sólo el ácido desoxirribonucleico sino la cromatina, es decir, la compleja estructura nucleoprotéica que contiene toda la información genómica en organismos eucariotas así como sus modificaciones durante el desarrollo y la diferenciación celular. Precisamente la base estructural de la epigenómica son cambios en la estructura y la función de la cromatina acompañados de modificaciones químicas de sus componentes, las proteínas cromosomales y el ácido desoxirribonucleico.

Los biólogos describen los organismos vivos utilizando dos términos muy amplios: genotipo y fenotipo. El genotipo se refiere al conjunto de la información genética contenido en el genoma de un organismo que es recibido de sus antecesores y transmitido a su descendencia. En los organismos complejos los genomas paterno y materno se recombinan durante la reproducción sexual dando lugar a individuos con una composición genómica única. A menudo el genotipo se define como el conjunto de los genes de un organismo, pero esta definición es inexacta. Lo que se transmite de generación en generación no es sólo la información que codifica para proteínas o para ácido ribonucleico, los genes propiamente dichos, sino todo el ácido desoxirribonucleico resultante de la fusión de dos células germinales, un espermatozoide y un óvulo, del cual sólo un pequeño porcentaje codifica para genes en el sentido clásico. El fenotipo, por su parte, describe la estructura del organismo, su forma y su tamaño, así como su función, que resultan en cada individuo de la ejecución de las instrucciones contenidas en su genotipo particular. La descripción del fenotipo y sus desviaciones es la tarea de los biólogos y los médicos desde hace siglos, aunque aún se siguen descubriendo nuevas especies y queda una enorme cantidad por descubrir.

Se denomina genómica al estudio de la organización molecular del ácido desoxirribonucleico y su cartografía física. La genómica engloba distintas subespecialidades. La genómica estructural estudia el plegamiento de las macromoléculas y su estructura tridimensional con la ayuda de técnicas derivadas de la física y la bioinformática, clasificando estas moléculas en familias funcionales. La genómica bioquímica estudia grupos de proteínas específicas y sus correspondientes “marcos de lectura abiertos”. Esto se lleva a cabo mediante su generación y expresión. La genómica química estudia los efectos de moléculas pequeñas para evaluar sus efectos moduladores en el estado celular o la expresión génica, preferiblemente en sistemas de alto rendimiento. La genómica funcional o fisiológica se centra en el análisis funcional de la totalidad del genoma y la integración de la estructura del ácido desoxirribonucleico, así como de su función molecular y la interacción de los genes y sus productos génicos. La proteómica, por su parte, estudia los proteomas. Un proteoma puede definirse como el conjunto de las proteínas expresadas por un genoma. Configura una disciplina fundamental de la era post-genómica que trata de descubrir la constelación de proteínas que otorgan a las células su estructura y función. Distintas tecnologías permiten obtener y comparar “instantáneas” de las proteínas que se expresan en un momento determinado en una célula-robótica, electroforesis 2D, espectrometría de masas, chips, bioinformática, etc. La proteómica puede definirse como la genómica funcional a nivel de las proteínas. Es la ciencia que correlaciona las proteínas con sus genes, estudia el conjunto completo de proteínas que pueden obtenerse de un genoma.

A menudo se atribuye a Conrad Waddington (1905-1975) la acuñación del término “epigenética” en el año 1942 como “la rama de la biología que estudia las interacciones causales entre los genes y sus productos que dan lugar al fenotipo”. Las primeras apariciones de la epigenética en la literatura datan de mediados del siglo diecinueve, aunque los orígenes del concepto pueden encontrarse ya en Aristóteles (384-322 AC). Aristóteles creía en la epigénesis: el desarrollo de la forma orgánica del individuo a partir de materia amorfa. Esta controvertida creencia fue el principal argumento en contra de la hipótesis que se mantenía de que el desarrollo del ser humano es a partir de cuerpos minúsculos completamente formados. Incluso en los primeros años del siglo veintiuno, aún no existe un consenso universal acerca de hasta qué punto las personas están preprogramadas o modeladas por el ambiente. El campo de la epigenética ha surgido como un puente entre las influencias genéticas y ambientales. En el siglo veintiuno, la definición más comúnmente encontrada del término epigenética es “el estudio de cambios heredables en la función génica que se producen sin un cambio en la secuencia del acido desoxirribonucleico”.

La epigenómica es un área nueva que se encuentra en pleno desarrollo. Los primeros estudios epigenómicos comienzan en los años 1980 y se dan con mayor fuerza en los años 1990. En este nuevo siglo se ha producido una explosión bastante interesante de artículos sobre epigenómica, los que van de la mano del desarrollo de tecnologías computacionales que permiten estudiar el genoma y comparar tejidos normales con tumor, normales con premalignos, o tejidos expuestos con los no expuestos. En este entorno los cambios epigenómicos constituyen “la progresión natural de los cambios moleculares que se ven cuando un tejido que es normal se transforma por diferentes razones y llega a ser un tejido oncogénico. Como estos cambios ya se han visto en muchos tipos de cáncer, se está comenzando a desarrollar pruebas para detectar el cáncer en etapas tempranas, donde ya se ven estos cambios moleculares”, puntualizando que los médicos no pueden ver los cambios ni los pacientes sentirlos porque los cambios son a nivel molecular y los tejidos no se han expandido mostrando un cambio histológico.

En este entendido, la epigenómica analiza las interacciones entre genomas y proteomas, así como los patrones generales de mutilación y las señales de mutilación, y evalúa este tipo de información en las distintas especies. La genómica comparativa o filogenómica busca determinar el número de familias de proteínas diferentes codificadas por distintos genomas, la distribución de los genes codificantes en los diferentes genomas y cuántos de esos genes los comparten distintos genomas. La ortogenómica estudia los genomas de descendientes ortólogos, mientras que la paragenómica estudia genomas parálogos. Estos estudios incluyen la composición y la organización de dominios proteínicos en los diferentes organismos. La genómica genética incluye el análisis de perfiles de expresión y de huellas basadas en marcadores en cada individuo en una población que se segrega. La genómica computacional mide cuantitativa o cualitativamente una propiedad de interés Después se identifica computacionalmente los factores genéticos en regiones genómicas donde el patrón de variación genética se correlaciona con la distribución de rasgos entre las distintas cepas analizadas. El grado de correlación entre los rasgos y los agrupamientos de cepas dentro de cada bloque de haplotipos se evalúa mediante un análisis de la varianza. La nutrigenómica tiene como objetivo desvelar los efectos de los macronutrientes y los micronutrientes en la salud y la enfermedad en los distintos genotipos. La toxicogenómica busca entender las complejidades de un sistema biológico en su respuesta a factores tóxicos, mutagénicos o carcinogénicos. Reciben una consideración especial las homologías entre genes encargados de controlar las enfermedades en el genoma humano con respecto a compartir funciones tales como ciclo celular y estructura, adhesión celular, señalización, apoptosis, control neuronal y mecanismos de defensa.

 

Guillermo Choque Aspiazu
http://www.eldiario.net/
Junio 28 de 2010

Elitismo en algoritmos genéticos

Elitismo en algoritmos genéticos

Dentro del cómputo evolutivo existen diferentes paradigmas. Aunque todos los paradigmas se basan en la misma idea del neo-darwinismo y en el uso de una población de soluciones, difieren entre ellos por la forma de implementar los mecanismos de selección, apareamiento, mutación y elitismo. Los principales paradigmas son: los algoritmos genéticos, las estrategias evolutivas y la programación evolutiva. Aunque también existen otras técnicas como la programación genética, la evolución diferencial, la optimización mediante cúmulos de partículas, la optimización por colonia de hormigas, los algoritmos culturales, los sistemas inmunes artificiales y la búsqueda dispersa.

En la actualidad, el paradigma de algoritmos genéticos se presume como el más popular. Aunque existen propuestas similares, como la de Fraser, y la de Bremermann, se considera a John Holland como el que definió las bases de los algoritmos genéticos modernos. En cuanto a la representación, tradicionalmente hace uso de una cadena binaria, es decir, trabajan a nivel de genotipo, lo que equivale a transformar el problema de un espacio cualquiera al binario. Por ello, en el algoritmo genético una representación adecuada es un factor importante para obtener buenos resultados. Tradicionalmente, los algoritmos genéticos hacen uso de la selección proporcional con base en la adaptabilidad. Le da mayor importancia al operador de apareamiento que al de mutación, y no cuenta con mecanismos de auto-adaptación. En cuanto a la probabilidad de apareamiento se utilizan valores altos, al contrario de la probabilidad de mutación donde los valores usualmente son bajos.

Los algoritmos genéticos son técnicas de optimización que se basan en la evolución de las especies, son utilizados especialmente en problemas bastante complicados donde las técnicas tradicionales de optimización no obtienen buenos resultados. El pensamiento evolutivo actual gira en torno al Neo-Darwinismo, que está basado principalmente en las ideas de Darwin, Weismann y Mendel, el cual establece que toda la vida en el planeta puede ser explicada a través de: selección, apareamiento, mutación y competencia. En sí, en los algoritmos evolutivos se requiere codificar las estructuras del problema de optimización, definir las operaciones entre los individuos, una función de adaptabilidad y los mecanismos de selección. Los algoritmos genéticos inicialmente se conocieron como planes reproductivos, y fueron introducidos por John H. Holland a principios de los años sesenta y fueron utilizados en el aprendizaje automático. El algoritmo genético es un algoritmo evolutivo en el cual el apareamiento es el operador principal y la mutación es un operador secundario, en cuanto al otro operador se utiliza a manera de selección probabilística

Coloquialmente, por élite se entiende un grupo pequeño que por algún motivo, característica, facultad o privilegio es superior o mejor en comparación al grueso de una población determinada; con cualidades o prerrogativas de las que la gran mayoría no disfrutan. En general, se habla de élite como sinónimo de elegido, escogido, eminente o distinguido. Esta concepción tiene más o menos el mismo significado con que éste término es manejado en las ciencias sociales. Es común también que se le llame elitista a quienes son selectivos, a quienes discriminan a otros, a los que manifiestan repulsión por lo común o popular, que le dan una valoración negativa o califican peyorativamente a los conceptos de masa y mayoría. Un algoritmo genético, desde el punto de vista de la optimización, es un método poblacional de búsqueda dirigida basada en probabilidad. Bajo una condición bastante débil, que el algoritmo mantenga elitismo, es decir, guarde siempre al mejor elemento de la población sin hacerle ningún cambio, se puede demostrar que el algoritmo converge en probabilidad al óptimo. En otras palabras, al aumentar el número de iteraciones, la probabilidad de tener el óptimo en la población tiende a uno. Un algoritmo genético emula el comportamiento de una población de individuos que representan soluciones y que evoluciona en base a los principios de la evolución natural: reproducción mediante operadores genéticos y selección de los mejores individuos, correspondiendo éstos a las mejores soluciones del problema a optimizar.

El método más utilizado para mejorar la convergencia de los algoritmos genéticos es el elitismo. Este método consiste básicamente en realizar la etapa de selección en dos partes: (1) Se realiza un muestreo en una élite de “ere” miembros de entre los mejores de la población inicial y se incorporan directamente a la población final, sin pasar por la población intermedia. (2) La población auxiliar de criadores se muestrea de entre los “total menos ere” restantes miembros de la población inicial. Normalmente, el tamaño de la élite “ere” es bastante pequeño y el tipo de muestreo es bien directo o bien por sorteo, ambos en la variedad diversa.

Para aprovechar las ventajas del modelo del proceso evolutivo en la resolución de un problema de optimización, se deben establecer las siguientes correspondencias: (1) Una apropiada codificación de las posibles soluciones del problema representará a éstas de la misma forma que el cromosoma. Representa a los individuos de la especie. Dada esta unívoca relación, se usarán indistintamente los términos solución, codificación, cromosoma o individuo. (2) La adecuación de cada solución será una medida del comportamiento de ésta en el problema particular considerado. Normalmente, es el valor objetivo de la solución. Así, una solución está más adecuada a un problema cuanto mejor sea su valor objetivo. (3) La definición de algunos operadores genéticos que, al actuar sobre una o varias soluciones, suministren una o más soluciones al alterar genéticamente los cromosomas. Juegan el papel del apareamiento y la mutación en el proceso evolutivo natural.

En principio aparenta una cierta conveniencia contar con una estrategia de selección estricta para que mejore rápidamente la población y converja el algoritmo, es decir, que la población se acumule alrededor de un genotipo óptimo. Esto no es cierto. Lo que ocurre es que la población se acumula rápidamente alrededor de algún individuo que es bueno, comparativamente con el resto de los individuos considerados a lo largo de la ejecución del algoritmo, pero este individuo puede no ser el mejor posible. A esto se le suele llamar convergencia prematura. No se puede asegurar pero sí procurar que lo anterior no ocurra. Además de la explotación es necesario que exista exploración. El algoritmo genético debe, no sólo seleccionar de entre lo mejor que ha encontrado, sino procurar encontrar mejores individuos. En la estrategia de selección normalmente se incluye un elemento extra que sirve de “ancla”. Si sólo se hace selección forzando que sea más probable elegir al mejor individuo de la población pero sin asegurarlo, es posible que este individuo se pierda y no forme parte de la siguiente generación. Para evitar lo anterior se fuerza la selección de los mejores individuos de la generación para pasar intactos a la siguiente. A esta estrategia se le denomina elitismo y puede ser generalizada especificando que permanezcan en la población los mejores individuos de las pasadas generaciones.

El mecanismo elitista pretende asegurar que aquel o aquellos individuos que son los más aptos de la población actual sobrevivan y continúen participando en el proceso evolutivo, pasando a la siguiente generación de manera intacta, sin recombinarse ni mutarse. Implementar este mecanismo asegura que la mejor aptitud encontrada hasta el momento, el mejor individuo hasta el momento, no se perderá en la siguiente generación. El elitismo es importante, pues garantiza, a través de pruebas matemáticas, la convergencia global del algoritmo genético. Se acepta que con el elitismo, cuando se mantiene una copia del mejor individuo es posible garantizar convergencia global para un problema de optimización. En este dominio existen variantes de modelos elitistas a las que se denominan elitismo parcial y elitismo total. Por elitismo parcial se quiere decir que en una población de tamaño “ene” se mantiene una copia de los mejores “eme” individuos hasta el total de generaciones definidas. Por elitismo total se quiere decir que se mantiene una copia de los mejores “ene” individuos, el total de individuos de la población, hasta el total de generaciones definidas.

Bajo ciertas condiciones muy generales, la introducción del elitismo garantiza la convergencia teórica al óptimo global; en la práctica, mejora la velocidad de convergencia de los algoritmos genéticos cuando la función de evaluación es unidmodal, es decir, no hay subóptimos, sin embargo la velocidad de convergencia empeora con funciones fuertemente multimodales. Con tamaños de población pequeños se consiguen efectos similares a los del elitismo introduciendo un proceso de reinicialización periódica en los algoritmos genéticos: cada vez que el algoritmo genético converge se salvan los mejores individuos, se reinicializan los demás y se vuelve a comenzar. La reinicialización tiene efectos beneficiosos sobre las prestaciones del método debido a que introduce diversidad, requisito especialmente crítico en los algoritmos genéticos con poblaciones pequeñas.

 

Guillermo Choque Aspiazu
http://www.eldiario.net/
Marzo 15 de 2010

Análisis de secuencias genómicas

Análisis de secuencias genómicas

La bioinformática, según una de sus definiciones más sencillas, es la aplicación de la tecnología de computadoras a la gestión y análisis de datos biológicos. Los términos bioinformática, biología computacional y, en ocasiones, biocomputación, utilizados en muchas situaciones como sinónimos, hacen referencia a campos de estudios interdisciplinarios muy vinculados, que requieren el uso o el desarrollo de diferentes técnicas que incluyen informática, matemática aplicada, estadística, ciencias de la computación, inteligencia artificial, química y bioquímica para solucionar problemas, analizar datos, o simular sistemas o mecanismos, todos ellos de índole biológica, y usualmente, pero no de forma exclusiva, en el nivel molecular. El núcleo principal de estas técnicas se encuentra en el uso de recursos computacionales para solucionar o investigar problemas sobre escalas de tal magnitud que sobrepasan el discernimiento humano. La investigación en biología computacional se solapa a menudo con la biología de sistemas.

Las técnicas computacionales han pasado a ser una herramienta fundamental para el manejo y análisis de la información biológica. Si bien esto es aplicable a cualquier área de la biología, es particularmente importante en la biología molecular. Esto se evidencia en el desarrollo, mantenimiento y permanente actualización de gigantescas bases de datos públicas de secuencias biológicas tanto de ácidos nucléicos como de proteínas; y en la tendencia creciente en el uso de herramientas bioinformáticas o de biocomputación como apoyo a las técnicas experimentales. Los proyectos de secuenciamiento como el del “Genoma Humano” y el de varios organismos de estudio, están generando enormes cantidades de información imposible de analizar sin el uso de herramientas computacionales. El desarrollo de la bioinformática y la biocomputación ha generado técnicas de análisis de secuencias de ácidos nucléicos y proteínas con múltiples objetivos: determinación de homología, alineamiento de secuencias homólogas, predicción de estructura, filogenia, evolución molecular, diseño de fármacos, entre otros.

La revolución en instrumentación para la secuenciación eficiente y automatizada de genomas ha generado una explosión en la cantidad de datos de tipo biológico almacenados en diferentes bases de datos públicas, datos que se han acumulado principalmente en las dos últimas décadas a partir del proyecto genoma humano, estas bases de datos crecen constantemente de tal forma que existe una brecha creciente entre la capacidad de generar nuevos datos y la capacidad para analizarlos. El verdadero reto está en extraer información útil y con sentido biológico a partir del análisis de la información almacenada en las bases de datos de genomas, en vista de lo anterior el desarrollo de nuevos algoritmos y técnicas de análisis de datos de secuencias de genomas debe ser estratégica para cualquier grupo de investigación interesado en generar nuevo conocimiento o valor agregado a partir de los datos experimentales generados en sus laboratorios o a partir de la información disponible en forma pública.

Las características particulares de las secuencias de genomas tales como redundancia, degeneración, discontinuidad de la información y baja relación señal/ruido; hacen que el desarrollo de algoritmos para la búsqueda e identificación de patrones de interés en secuencias genómicas sea una tarea no trivial, un patrón de interés en general presenta un alto grado de incertidumbre. En el análisis de secuencias de genomas se han aplicado una diversidad de técnicas desarrolladas no necesariamente para el análisis de información de carácter biológico, tal es el caso de las caminatas aleatorias, el juego del caos, análisis de propiedades lingüísticas y gramaticales, función de autocorrelación, análisis de Fourier, análisis de mapas de recurrencia, etc. Este conjunto de técnicas matemáticas, lingüísticas, y computacionales; generan información de aspectos no biológicos del genoma a diferentes escalas dentro de una secuencia, ya que algunas técnicas generan información de carácter global sobre una secuencia y otras generan información de tipo local permitiendo estudiar el comportamiento a lo largo de una secuencia. Sin embargo, la información generada o su interpretación no se integra a detalle con la información biológica para dar un mejor análisis de las características del genoma.

Por otra parte, las técnicas de mayor uso en bioinformática se basan principalmente en propiedades estadísticas de los datos, y la visualización de dicha información se limita al uso de elementos básicos tales como tablas, motifs logos, árboles de clasificación, etc. La falta de integración de la información generada por diferentes técnicas de análisis no convencionales en bioinformática con el conocimiento biológico, así como las limitaciones de la información que es posible generar a partir de análisis estadísticos, base de buena parte de las técnicas más utilizadas en el análisis de genomas, motiva esta línea de investigación en la cual se propone la aplicación de conceptos de fusión de datos, con el objetivo de reducir la incertidumbre en la identificación de patrones de interés biológico en secuencias de genomas. La fusión de datos requiere de la integración de diversas áreas de la computación tales como: bases de datos, tecnologías para la Web, aprendizaje de máquina, procesamiento y análisis de gran cantidad de datos, visualización de información, interfaces humano-computadora, entre otras.

Desde que el fago Φ-X174 fuera secuenciado el año 1977 de manera provisional, un año más tarde se publicaría la secuencia completa definitiva, las secuencias de ácido desoxirribonucleico de cientos de organismos han sido decodificadas y guardadas en bases de datos. Esos datos son analizados para determinar los genes que codifican para ciertas proteínas, así como también secuencias reguladoras. Una comparación de genes en una especie o entre especies puede mostrar similitudes entre funciones de proteínas, o relaciones entre especies. Con la creciente cantidad de datos, desde hace mucho se ha vuelto poco práctico analizar secuencias de ácido desoxirribonucleico manualmente. Hoy se usan programas de computadora para estudiar el genoma de miles de organismos, conteniendo miles de millones de nucleótidos. Estos programas pueden compensar mutaciones, con bases intercambiadas, borradas o insertadas en la secuencia de ácido desoxirribonucleico, para identificar secuencias que están relacionadas, pero que no son idénticas. Una variante de este alineamiento de secuencias se usa en el proceso de secuenciación.

La secuenciación conocida como “perdigonada” o su equivalente en el idioma inglés “shotgun”, fue usada por el Instituto de Investigación Genómica “TIGR”, conocido más tarde como el “Instituto Craig Venter” para secuenciar el primer genoma de bacteria, el Haemophilus influenzae. Esta secuenciación proporciona una lista secuencial de nucleótidos y ofrece las secuencias de miles de pequeños fragmentos de ácido desoxirribonucleico, cada uno de aproximadamente 600 a 800 nucleótidos de largo. Las terminaciones de estos fragmentos se superponen y, cuando son alineados de la manera correcta, constituyen el genoma completo del organismo en cuestión. El secuenciamiento shotgun proporciona datos de secuencia rápidamente, pero la tarea de ensamblar los fragmentos puede ser bastante complicada para genomas muy grandes. En el caso del proyecto “Genoma Humano”, llevó varios meses de tiempo de procesador, en una estación DEC Alpha, para ensamblar los fragmentos. El secuenciamiento shotgun es el método utilizado como favorito para secuenciar los genomas y los algoritmos de ensamblado genómico constituyen un área crítica de la investigación en bioinformática.

Otro aspecto de la bioinformática en análisis de secuencias es la búsqueda automática de genes y secuencias reguladoras dentro de un genoma. No todos los nucleótidos dentro de un genoma son genes. Dentro del genoma de organismos más avanzados, grandes partes del ácido desoxirribonucleico no sirven a ningún propósito obvio. Este ácido desoxirribonucleico, conocido como “ácido desoxirribonucleico basura”, puede, sin embargo, contener elementos funcionales todavía no reconocidos. La bioinformática sirve para estrechar la brecha entre los proyectos de genoma y proteoma, por ejemplo, en el uso de secuencias de ácido desoxirribonucleico para la identificación de proteínas.

Algunas herramientas para analizar secuencias son: (1) GCG Accelrys. El paquete Accelrys GCG es una herramienta muy potente para el análisis de secuencias de ácidos nucléicos y proteínas con más de ciento treinta herramientas distintas. El paquete es de uso completo con una interfaz gráfica XWindow que utiliza la herramienta SeqLab. Existe una versión web accesible desde máquinas virtuales Seqweb, más fácil de usar pero con un número limitado de herramientas. (2) EMBOSS. El EMBOSS es un paquete de aplicaciones gratuito, de código abierto, específicamente desarrollado para el análisis de secuencias de ácidos nucléicos y de aminoácidos. Para evitar el uso de líneas de comandos, EMBOSS proporciona a los usuarios con una interfaz gráfica agradable utilizando el wEMBOSS accesible desde máquinas virtuales. Como característica adicional, EMBOSS incluye más de ciento cincuenta aplicaciones distintas. (3) SeqTrim. Constituye un programa desarrollado en la Universidad de Málaga para el pre-procesamiento de secuencias de nucleótidos. Es capaz de detectar las trazas de secuencias de mala calidad así como distintos tipos de contaminación: restos de vector, adaptadores, secuencias genómicas bacterianas y otros.

 

Guillermo Choque Aspiazu
http://www.eldiario.net/
Marzo 22 de 2010

Algoritmo genético de grano fino

Algoritmo genético de grano fino

Los algoritmos evolutivos basan su funcionamiento en un mecanismo análogo a los procesos evolutivos naturales, con el objetivo de resolver problemas de búsqueda y optimización. En el caso de los algoritmos genéticos, durante el proceso se mantiene una población de soluciones que evolucionan de acuerdo a operaciones de selección, apareamiento, reemplazo y mutación, siguiendo la idea de la supervivencia de los individuos más aptos. El grado de adaptación de un individuo se evalúa de acuerdo al problema a resolver, mediante una función de adaptabilidad. Los algoritmos genéticos son una robusta herramienta de optimización que pueden ser utilizados para resolver un amplio abanico de problemas de manera eficiente y precisa. Son tres operadores básicos los que dirigen la búsqueda en los algoritmos genéticos. La función de selección predispone la búsqueda hacia soluciones prometedoras. La calidad de cada individuo viene dada por la función de adaptabilidad, que es específica al problema a ser resuelto. Las funciones de apareamiento y mutación introducen variación al combinar el conjunto actual de soluciones prometedoras.

Las técnicas de procesamiento paralelo y distribuido se aplican al modelo clásico de algoritmo genético con el objetivo de obtener mejoras desde el punto de vista de la eficiencia y para perfeccionar la calidad de la búsqueda genética. Desde la perspectiva de la eficiencia, paralelizar un algoritmo genético permite afrontar la lentitud de convergencia para problemas cuya dimensión motiva el uso de poblaciones numerosas, o múltiples evaluaciones de funciones de adaptación costosas. Desde el punto de vista algorítmico, los algoritmos genéticos paralelos pueden explotar el paralelismo intrínseco del mecanismo evolutivo, trabajando simultáneamente sobre varias poblaciones semi-independientes para resolver el mismo problema. Intercambios eventuales de soluciones o migraciones, introducen diversidad para evitar problemas de convergencia en óptimos locales. Complementariamente, los algoritmos genéticos paralelos pueden aprovechar características de paralelismo propias del problema, analizando concurrentemente diferentes secciones del espacio de búsqueda.

Los estudios recientes han demostrado que la paralelización puede mejorar significativamente el rendimiento de los algoritmos genéticos. Muchos operadores de búsqueda pueden ser distribuidos fácilmente, y obtenerse así grandes incrementos de velocidad en problemas difíciles. Existen dos enfoques generales para “paralelizar” algoritmos genéticos: el primero es conocido como maestro-esclavo y el segundo de grano grueso o fino. La arquitectura maestro-esclavo suele emplearse cuando la función de adaptabilidad, que determina la calidad de cada solución individual, es el operador más costoso. La función de evaluación se distribuye entre un número determinado de procesadores esclavos y todos los operadores restantes: mutación, apareamiento y selección, se ejecutan en el procesador maestro. En los algoritmos genéticos en paralelo de grano fino o de grano grueso, la población se divide en subpoblaciones organizadas en una red. Todos los operadores en cada subpoblación se ejecutan a través de un elemento de procesamiento separado que contiene a la subpoblación. Las diferentes subpoblaciones pueden comunicarse por medio de diversas topologías de red y patrones de comunicación.

Los algoritmos genéticos pueden clasificarse en dos grandes clases: (1) En la primera clase, los algoritmos genéticos en paralelo maestro-esclavo, distribuyen las funciones de adaptabilidad entre procesadores esclavos. La información la recolecta el procesador maestro, que procesa la población de soluciones candidato, aplicando operadores de selección, apareamiento y mutación. Posteriormente envía las nuevas soluciones a sus esclavos para que sean evaluadas. (2) La segunda clase son los algoritmos genéticos en paralelo de grano fino y de grano grueso, donde la población se distribuye entre un número dado de procesadores. Cada procesador procesa su subpoblación. Se permite que las subpoblaciones se comuniquen entre sí e intercambien soluciones a algunos intervalos. Pueden usarse varias topologías de conexión y patrones de comunicación.

Los algoritmos genéticos de grano fino dividen la población en pequeñas subpoblaciones que contienen sólo una o dos soluciones que están conectadas en topología de rejilla. Los individuos se comunican únicamente con su vecindario. El propósito original de los algoritmos genéticos de grano fino era usar un gran número de pequeños procesadores, donde cada procesador procesaría una única solución. En los algoritmos genéticos de grano grueso, las subpoblaciones son más grandes y la comunicación se reduce al intercambio de soluciones sólo de vez en cuando o después de que los algoritmos hayan convergido. Varias topologías comunes para la comunicación incluyen anillos, rejillas, hipercubos, grafos fuertemente conexos y grafos aleatorios con un número fijo de enlaces para cada elemento de proceso. Cada una de las paralelizaciones puede representar una mejora significativa para algunos problemas. Si la función de adaptabilidad se lleva la mayoría de recursos computacionales, los algoritmos genéticos en paralelo maestro-esclavo suelen dar buenos resultados. Sin embargo, cuando la función de evaluación no requiere un tiempo significativamente mayor que los otros operadores, los algoritmos genéticos de grano fino o grueso pueden mejorar aún más el rendimiento. Como se ha mencionado, los algoritmos genéticos de grano fino fueron diseñados originalmente para ejecutarse en máquinas con un gran número de pequeños procesadores conectados en topología de rejilla. Mientras la optimización se realiza, se podría esperar que soluciones parciales de gran calidad se propaguen de un sitio a otro de la rejilla en un proceso parecido a la difusión. Este comportamiento es interesante en sí mismo, y puede eliminar problemas de convergencia prematura, y puede también mejorar la ejecución del algoritmo en máquinas monoprocesador. Estas son algunas razones que se utilizan a momento de elegir un algoritmo de grano fino.

En una implementación especifica de un algoritmo genético de grano fino, la población de soluciones candidato se ha acotado a una rejilla bidimensional, donde cada posición de la rejilla puede contener una solución particular o estar vacía. En cada iteración del algoritmo, todas las soluciones pasan por el operador de apareamiento, en el que el individuo se combina con un vecino escogido al azar de su vecindario. El individuo, pasa entonces por un operador de mutación que realiza una ligera modificación a la solución actual. Si el nuevo individuo es de una calidad mayor, entonces reemplaza al individuo original. Esto introduce la presión de selección que discrimina la búsqueda hacia soluciones de mayor calidad. A continuación, puede aplicarse un operador local de búsqueda para afinar la solución particular. De este modo, un algoritmo genético realiza una búsqueda global, mientras que el operador local de búsqueda trata de mejorar el individuo en algún pequeño vecindario.

Un programa es paralelo si en cualquier momento de su ejecución puede ejecutar más de un proceso. Para crear programas paralelos eficientes hay que crear, destruir y especificar procesos así como la interacción entre ellos. Básicamente existen tres formas de paralelizar un programa: (1) Paralelización de grano fino. La paralelización del programa se realiza a nivel de instrucción. Cada procesador hace una parte de cada paso del algoritmo, selección, apareamiento y mutación, sobre la población común. (2) Paralelización de grano medio. Los programas se paralelizan a nivel de bucle. Esta paralelización se realiza habitualmente de forma automática en los compiladores. (3) Paralelización de grano grueso. Se fundamentan en la descomposición del dominio de datos entre los procesadores, siendo cada uno de ellos el responsable de realizar los cálculos sobre sus datos locales. La paralelización de grano grueso tiene como atractivo la portabilidad, ya que se adapta perfectamente tanto a multiprocesadores de memoria distribuida como de memoria compartida.

Una de las principales ventajas de los algoritmos genéticos es que permite que sus operaciones se puedan ejecutar en paralelo. Debido a que la evolución natural trata con una población entera y no con individuos particulares, excepto para la fase de selección, durante la cual existe una competencia entre los individuos y en la fase de reproducción, en donde se presentan iteraciones entre los miembros de la población, cualquier otra operación de la población, en particular la evaluación de cada uno de los miembros de la población, pueden hacerse separadamente. Por lo tanto, casi todas las operaciones en los algoritmos genéticos son implícitamente paralelas. Se ha establecido que la eficiencia de los algoritmos genéticos para encontrar una solución optima, está determinada por el tamaño de la población. Por lo tanto, una población grande requiere de más memoria para ser almacenada. También se ha probado que toma mayor cantidad de tiempo para lograr la convergencia. Al utilizar computadoras en paralelo, no solamente se provee de más espacio de almacenamiento, sino también con el uso de ellos se podrán producir y evaluar más soluciones en un tiempo más pequeño. Debido al paralelismo, es posible incrementar el tamaño de la población, reducir el costo computacional y mejorar el desempeño de los algoritmos genéticos.

 

Guillermo Choque Aspiazu
http://www.eldiario.net/
Enero 11 de 2010
Algoritmo genético distribuido

Algoritmo genético distribuido

En los últimos años, la comunidad científica ha mostrado un creciente interés en una nueva técnica de búsqueda basada en la teoría de la evolución y que se conoce como “algoritmo genético”. Esta técnica se basa en los mecanismos de selección que utiliza la naturaleza, de acuerdo a los cuales los individuos más aptos de una población son los que sobreviven, al adaptarse de forma más fácil a los cambios que se producen en su entorno. Hoy en día se sabe que estos cambios se efectúan en los genes de un individuo, los cuales constituyen la unidad básica de codificación de cada uno de los atributos de un ser vivo, y que los atributos más deseables, es decir aquellos que le permiten a un individuo adaptarse mejor a su entorno, se transmiten a sus descendientes cuando éste se reproduce sexualmente. Un investigador de la Universidad de Michigan llamado John Holland estaba consciente de la importancia de la selección natural, y a fines de los años 1960 desarrolló una técnica que permitió incorporarlos en un programa de computadora. Su objetivo era lograr que las computadoras aprendieran por sí mismas. A la técnica que inventó Holland se le llamó originalmente “planes reproductivos”, pero se hizo popular hacia el año 1975 con el nombre de “algoritmos genéticos”.

Una definición bastante completa de un algoritmo genético es la siguiente: “Un algoritmo genético es un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales, con respecto al tiempo, usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas, 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 asociado a los cromosomas biológicos, y se les asocia además una cierta función matemática que refleja su grado de adaptabilidad.

Por su parte, un sistema distribuido se define como una colección de computadoras autónomas conectadas por una red, y con el software distribuido adecuado para que el sistema sea visto por los usuarios como una única entidad capaz de proporcionar facilidades de computación. El desarrollo de los sistemas distribuidos vino de la mano de las redes locales de alta velocidad a principios de los años 1970. Más recientemente, la disponibilidad de computadoras personales de altas prestaciones, estaciones de trabajo y servidores ha resultado en un mayor desplazamiento hacia los sistemas distribuidos en detrimento de las computadoras centralizadas multiusuario. Esta tendencia se ha acelerado por el desarrollo de software para sistemas distribuidos, diseñado para soportar el desarrollo de aplicaciones distribuidas. Este software permite a las computadoras coordinar sus actividades y compartir los recursos del sistema: hardware, software y datos. Los sistemas distribuidos se implementan en diversas plataformas hardware, desde unas pocas estaciones de trabajo conectadas por una red de área local, hasta Internet, una colección de redes de área local y de área extensa interconectados, que en lazan millones de computadoras.

De retorno a la idea central de la presente propuesta, el proceso de evolución, similarmente a lo que sucede en los seres vivos, toma lugar en el código fundamental de los individuos o estructuras. En la implementación tradicional de los algoritmos genéticos las variables de diseño del problema a ser optimizado son codificadas en un alfabeto en particular, inicialmente códigos binarios, más recientemente números reales, y concatenadas para generar cromosomas artificiales. Posteriormente, el proceso de selección natural toma lugar y los cromosomas con códigos más saludables tienen mayor probabilidad de reproducirse que aquellos más débiles. Una vez seleccionados para reproducción y basados en la fortaleza de sus representaciones, los cromosomas se combinan mediante la aplicación de diferentes operadores de apareamiento, el material genético es intercambiando con el fin de producir diferente descendencia. Por otro lado, en el proceso de mutación ocurre un cambio repentino en una posición particular del cromosoma lo cual altera su estructura y lo hace diferente del cromosoma de sus padres.

Los procesos de evolución artificial dependen de los mecanismos de los diferentes operadores y parámetros involucrados en su construcción. La selección inapropiada de ellos hace que se presente un modo severo de falla en el algoritmo genético denominado convergencia prematura. El mismo es originado por la carencia de diversidad en la población, lo cual afecta el balance del algoritmo entre explotar lo que ya conoce y explorar nuevas posibilidades que podrían funcionar mejor. Entre los factores que pueden hacer que se pierda este delicado balance, se encuentran los siguientes: la pérdida de material importante dentro del cromosoma debido a la presión de selección, la distorsión o ruido en la probabilidad de selección, la destrucción de esquemas o cadenas de estructuras con información importante, debido al operador de apareamiento y una inadecuada escogencia de los valores de los parámetros probabilísticos que guían los diferentes operadores genéticos. Cuando el algoritmo cae en este modo de falla el mismo queda a la deriva y es conducido hacia una región del espacio de diseño donde seguramente no se encuentra el óptimo global.

El proceso de selección es la manera como los individuos son escogidos para ser apareados. La correcta elección del modelo usado para realizar esta operación es un factor importante que ayuda a evitar la selección inadecuada de padres, por el hecho que si los cromosomas que portan valiosa información nunca son seleccionados para la reproducción, el material genético contenidos en ellos puede considerarse perdido si no hay una vía para pasar esta información a otros individuos. Otra fuente de pérdida de material genético importante es la destrucción de las cadenas de información o esquemas, situación que puede presentarse cuando el punto de apareamiento separa material genético que pertenece a un hiperplano que contiene una solución óptima. En la literatura especializada se pueden conseguir numerosas técnicas que reducen la probabilidad de alterar estas cadenas o bloques de construcción y mejorar el proceso de selección.

La correcta elección de parámetros tales como tamaño de población, tasa de mutación y probabilidad de apareamiento, entre otros, es uno de los tópicos más estudiados debido a que al variar sus valores repercuten directamente en el balance entre la exploración y explotación del espacio de diseño, representando la vía como los algoritmos genéticos encuentran soluciones en los diferentes hiperplanos del espacio de búsqueda. A fin de preservar la diversidad en la población se desarrollaron algoritmos de tipo distribuido y celular basándose en la teoría de “separación espacial”. En esta teoría la población total es dividida en pequeñas subpoblaciones, cada una de las cuales evoluciona independiente y simultáneamente de acuerdo a un algoritmo genético especifico. Periódicamente un mecanismo de migración intercambia individuos entre las subpoblaciones, permitiendo inyectar nueva diversidad dentro de las subpoblaciones convergentes.

Los algoritmos genéticos distribuidos se construyen combinando diferentes tipos de operadores genéticos, los cuales exhiben diferentes grados de exploración o explotación, en las diferentes subpoblaciones que componen la topología distribuida de subpoblaciones. Por ejemplo, en el trabajo de Herrera y Lozano escrito el año 2000, se aplican diferentes operadores de apareamiento de tipo real a cada subpoblación, los cuales presentan diferencias en sus propiedades de exploración-explotación y en el grado en que son aplicadas, para proponer un algoritmo genético distribuido gradual y codificado en punto flotante. Así mismo, en la literatura se encuentran también algoritmos genéticos distribuidos pero codificados en binario como el propuesto por Potts y sus colegas el año 1994, donde se propone el uso de diferentes grados y niveles del operador de mutación para modificar el carácter de explotación o exploración de las diferentes subpoblaciones.

Una metodología de optimización propuesta se encuentra dividida en dos niveles. En un nivel macro, un conjunto de subpoblaciones aisladas son construidas sobre los vértices de un cubo formando una topología hipercúbica basándose en un algoritmo genético distribuido. Por otro lado a nivel micro, en el interior de cada subpoblación, se ejecuta un algoritmo genético más simple con el fin de generar los individuos que en posteriores etapas migraran a las subpoblaciones vecinas. Las estrategias de migración empleadas se basan en la emigración del mejor individuo de cada subpoblación cada cierto número de subgeneraciones internas.

 

Guillermo Choque Aspiazu
http://www.eldiario.net/
Octubre 5 de 2009
Algoritmo genético paralelo

Algoritmo genético paralelo

Los algoritmos genéticos son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización, basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más aptos, postulados por Charles Darwin. Por imitación de este proceso, los algoritmos genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. Un algoritmo genético consiste en una función matemática que toma como entradas a los ejemplares y retorna como salidas cuáles de ellos deben generar descendencia para la nueva generación. Son tres operadores básicos los que dirigen la búsqueda en estos algoritmos. La función de selección predispone la búsqueda hacia soluciones prometedoras. La calidad de cada individuo viene dada por la función de adaptabilidad, que será específica al problema a resolver. Las funciones de apareamiento y mutación introducen variaciones al realizar combinaciones en el conjunto actual de soluciones prometedoras.

Un algoritmo genético desarrolla una población de soluciones potenciales con vistas a resolver un problema dado. La primera población de soluciones se genera aleatoriamente. Se usa una medida de la calidad de las soluciones, expresada de forma usual en forma de una o varias funciones, para seleccionar las mejores soluciones de la población actual. Las soluciones seleccionadas pasan por los operadores de apareamiento y mutación para crear una población de nuevas soluciones. El proceso se repite hasta que se cumplan los criterios de finalización especificados por el usuario. Los algoritmos prosiguen discriminando de forma repetida la búsqueda de regiones de una mayor calidad, y combinando trozos prometedores de soluciones para formar combinaciones nuevas. De esta forma, los problemas que son descomponibles en problemas de dificultad definida se resuelven de manera eficiente, en tiempos cuadráticos o sub-cuadráticos. Muchos problemas difíciles pueden afrontarse en tiempo sub-cuadrático con respecto al número de variables. Sin embargo, para problemas muy grandes, incluso un tiempo sub-cuadrático puede llevar a enormes requisitos computacionales. Para resolver estos problemas de manera eficiente, se ha realizado un gran esfuerzo de investigación que ha llevado al estudio de la paralelización de algoritmos genéticos.

Estudios recientes han demostrado que la paralelización puede mejorar significativamente el rendimiento de los algoritmos genéticos. Muchos operadores de búsqueda pueden ser distribuidos fácilmente, y obtenerse así grandes incrementos de velocidad en problemas difíciles. Los algoritmos genéticos paralelos pueden clasificarse en dos grandes clases. La primera clase es denominada algoritmos genéticos en paralelo maestro-esclavo, estos se encargan de distribuir las funciones de adaptabilidad entre los procesadores esclavos. La información la recolecta el procesador maestro, que procesa la población de soluciones candidatas, aplicando operadores de selección, apareamiento y mutación. Posteriormente envía las nuevas soluciones a sus esclavos para que sean evaluadas. La segunda clase son los algoritmos genéticos en paralelo de grano fino y de grano grueso, donde la población se distribuye entre un número dado de procesadores. Cada procesador procesa su sub-población. Se permite que las sub-poblaciones se comuniquen entre sí e intercambien soluciones en algunos intervalos. Pueden usarse varias topologías de conexión y patrones de comunicación. Los algoritmos genéticos de grano fino dividen la población en pequeñas sub-poblaciones que contienen sólo una o dos soluciones que están conectadas en topología de rejillas bidimensionales. Los individuos se comunican únicamente con su vecindario. El propósito original de los algoritmos genéticos de grano fino era usar un gran número de pequeños procesadores, donde cada procesador procesaría una única solución. En cambio en los algoritmos genéticos de grano grueso, las sub-poblaciones son más grandes y la comunicación se reduce al intercambio de soluciones sólo de vez en cuando o después de que los algoritmos hayan convergido. Varias topologías comunes para la comunicación incluyen anillos, rejillas, hipercubos, grafos fuertemente conexos y grafos aleatorios con un número fijo de enlaces para cada elemento de proceso.

Cada una de las paralelizaciones puede representar una mejora significativa para algunos problemas. Si la función de adaptabilidad se lleva la mayoría de recursos computacionales, los algoritmos genéticos en paralelo maestro-esclavo suelen dar buenos resultados. Sin embargo, cuando la función de evaluación no requiere un tiempo significativamente mayor que los otros operadores, los algoritmos genéticos de grano fino o grueso pueden mejorar aún más el rendimiento. Como se ha mencionado antes, los algoritmos genéticos de grano fino fueron diseñados originalmente para ejecutarse en máquinas con un gran número de pequeños procesadores conectados en topología de rejilla. Mientras la optimización se realiza, uno podría esperar que soluciones parciales de gran calidad se propaguen de un sitio a otro de la rejilla en un proceso parecido a la difusión. Este comportamiento es interesante en si mismo, y puede eliminar problemas de convergencia prematura, y puede también mejorar la ejecución del algoritmo en máquinas monoprocesador.

Un programa es paralelo si en cualquier momento de su ejecución puede realizar más de un proceso. Para crear programas paralelos eficientes se debe crear, destruir y especificar procesos así como la interacción entre ellos. Básicamente existen tres formas de paralelizar un programa: (1) Paralelización de grano fino. La paralelización del programa se realiza a nivel de instrucción. Cada procesador hace una parte de cada paso del algoritmo, selección, apareamiento y mutación, sobre la población común. (2) Paralelización de grano medio. Los programas se paralelizan a nivel de bucle. Esta paralelización se realiza habitualmente de un modo automático en los compiladores. (3) Paralelización de grano grueso. Se basa en la descomposición del dominio de datos entre los procesadores, siendo cada uno de ellos el responsable de realizar los cálculos sobre sus datos locales. La computación paralela se ha convertido en una parte fundamental en todas las áreas de cálculo científico, ya que permite la mejora del rendimiento simplemente con la utilización de un mayor número de procesadores, memorias y la inclusión de elementos de comunicación que permitan a los procesadores trabajar conjuntamente para resolver un determinado problema.
Se puede decir que los algoritmos genéticos tienen una estructura que se adapta perfectamente a la paralelización. De hecho la evolución natural es en sí un proceso paralelo ya que evoluciona utilizando varios individuos. Los principales métodos de paralelización de los algoritmos genéticos consisten en la división de la población en varias sub-poblaciones. El tamaño y distribución de la población entre los distintos procesadores constituye uno de los factores fundamentales a la hora de paralelizar el algoritmo. Existen varias formas de paralelizar un algoritmo genético. La primera y más intuitiva es la global, que consiste básicamente en paralelizar la evaluación de los individuos manteniendo una población. Otra forma de paralelización global consiste en realizar una ejecución de distintos algoritmos genéticos secuenciales simultáneamente, siendo que estas dos formas de paralelización no cambian la estructura del algoritmo utilizado. El resto de aproximaciones sí cambian la estructura del algoritmo y dividen la población en sub-poblaciones que evolucionan por separado e intercambian individuos cada cierto número de generaciones. Si las poblaciones son pocas y grandes, se tiene la paralelización de grano grueso. Si el número de poblaciones es grande y con pocos individuos en cada población se tiene la paralelización de grano fino. Por último, existen algoritmos que mezclan propiedades de estos dos últimos y que se denominan mixtos.

Además de conseguir tiempos de ejecución bastante pequeños, al paralelizar un algoritmo genético se está modificando el comportamiento algorítmico, y esto hace que se pueda obtener otras soluciones y experimentar con las distintas posibilidades de implementación y los distintos factores que influyen en ella. Estas poblaciones van evolucionando por separado para detenerse en un momento determinado e intercambiar los mejores individuos entre ellas. Técnicamente existen tres características importantes que influyen en la eficiencia de un algoritmo genético paralelo: (1) La topología que define la comunicación entre sub-poblaciones. (2) La proporción de intercambio, referida al número de individuos a intercambiar. (3) Los intervalos de migración, que se refiera a la periodicidad con que se intercambian los individuos.

 

Guillermo Choque Aspiazu
http://www.eldiario.net/
Junio 29 de 2009
Algoritmo genético simple

Algoritmo genético simple

En los últimos años, la comunidad científica internacional ha mostrado un creciente interés en una nueva técnica de búsqueda basada en la teoría de la evolución y que se conoce como “algoritmo genético”. Esta técnica se basa en los mecanismos de selección que utiliza la naturaleza, de acuerdo a los cuales los individuos más aptos de una población son los que sobreviven, al adaptarse más fácilmente a los cambios que se producen en su entorno. Hoy en día se sabe que estos cambios se efectúan en los genes, que constituye la unidad básica de codificación de cada uno de los atributos de un ser vivo, y que los atributos más deseables del mismo se transmiten a sus descendientes, cuando éste se reproduce sexualmente.

John Holland desde pequeño, se preguntaba cómo logra la naturaleza, crear seres cada vez más perfectos, teniendo en cuenta además que todo se lleva a cabo a base de interacciones locales entre individuos, y entre estos y lo que les rodea. No sabía la respuesta, pero tenía una cierta idea de como hallarla: tratando de hacer pequeños modelos de la naturaleza, que tuvieran alguna de sus características, y ver cómo funcionaban, para luego extrapolar sus conclusiones a la totalidad. De hecho, ya de pequeño hacía simulaciones de batallas célebres con todos sus elementos: mapas que copiaba y que cubría luego de pequeños ejércitos que se enfrentaban entre sí. Hacia los años 1950 entró en contacto con las primeras computadoras, donde pudo llevar a cabo algunas de sus ideas, aunque no se encontró con un ambiente intelectual fértil para propagarlas. Fue a principios de los años 1960, en la Universidad de Michigan en Ann Arbor, donde, dentro del grupo “Lógica Computacional”, sus ideas comenzaron a desarrollarse y a dar frutos. Y fue, además, leyendo un libro escrito por un biólogo evolucionista, R. A. Fisher, titulado “Teoría Genética de la Selección Natural”, como comenzó a descubrir los medios para llevar a cabo sus propósitos de comprensión de la naturaleza. De ese libro aprendió que la evolución era una forma de adaptación más potente que el simple aprendizaje, y tomó la decisión de aplicar estas ideas para desarrollar programas bien adaptados para un fin determinado.

En la Universidad de Michigan, Holland impartía un curso titulado “Teoría de sistemas adaptativos”. Dentro de este curso, y con una participación activa por parte de sus estudiantes, fue donde se crearon las ideas que más tarde se convertirían en los algoritmos genéticos. Por tanto, cuando Holland se enfrentó a los algoritmos genéticos, los objetivos de su investigación fueron dos: (1) imitar los procesos adaptativos de los sistemas naturales, y (2) diseñar sistemas artificiales que retengan los mecanismos importantes de los sistemas naturales. David Goldberg, uno de los grandes expertos de los algoritmos genéticos, conoció a Holland, y se convirtió en su estudiante. Golberg era un ingeniero industrial trabajando en diseño de redes de tuberías, y fue uno de los primeros que trató de aplicar los algoritmos genéticos a problemas industriales. Aunque Holland trató de disuadirle, porque pensaba que el problema era excesivamente complicado como para aplicarle algoritmos genéticos, Goldberg consiguió lo que quería, escribiendo un algoritmo genético en una computadora personal Apple II. Estas y otras aplicaciones creadas por estudiantes de Holland convirtieron a los algoritmos genéticos en un campo suficientemente aceptado como para celebrar la primera “Conferencia Internacional sobre Algoritmos Genéticos” el año 1985.

Los algoritmos genéticos son 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. El proceso de selección natural descrito de una manera sencilla es: se tiene una población, esa población se multiplica por medio del intercambio de genes, de la nueva generación sólo sobreviven los más capaces de adaptarse a su medio ambiente para así formar una nueva población “mejor” que la anterior. Este ciclo se repite a través del tiempo. Sin embargo, hay ocasiones en que se producen mutaciones en los individuos, lo que origina cambios drásticos en las características del individuo, y con esto se evita que se llegue a un “estancamiento”, en la evolución.

Se dice que el proceso evolutivo es aleatorio en el sentido de que se generan poblaciones cuyas características se parecen a las de sus padres, pero varían de manera aleatoria. Luego, estas poblaciones son “probadas” en el ambiente para ver cuál se “adapta” mejor. Sobreviven los que se adaptan mejor al medio ambiente, pero no se sabe para qué se quiere adaptar al medio ambiente, es decir, con qué fin. Cuando la gente se enfrentó con problemas que no podían ser solucionados por métodos matemáticos o analíticos, y que la única forma de resolverlos era a través de prueba y error dirigido, es decir, probar dónde se creía que podía mejorarse el resultado, se dio cuenta de que este proceso era similar al proceso que seguía la naturaleza, así que se intentó copiar su manera de operar y se crearon los algoritmos genéticos, que en la actualidad sólo son una rama de una extensa materia conocida como computación evolutiva que, en resumen, es la ciencia computacional cuyos algoritmos imitan el proceso evolutivo de la naturaleza.

En un algoritmo genético simple, primero, se genera de manera aleatoria la población inicial, que está constituida por un conjunto de cromosomas, o cadenas de caracteres que representan las soluciones posibles del problema. A cada uno de los cromosomas de esta población se le aplica la función de adaptabilidad a fin de saber qué tan buena es la solución que se está codificando. Sabiendo la adaptabilidad de cada cromosoma, se procede a la selección de los que se aparean en la siguiente generación. Dos son los métodos de selección más comunes: (1) La ruleta. Este método es bastante simple, y consiste en crear una ruleta en la que cada cromosoma tiene asignada una fracción proporcional a su adaptabilidad. (2) El torneo. La idea de este método es muy simple. Se baraja la población y después se hace competir a los cromosomas que la integran en grupos de tamaño predefinido en un torneo del que resultarán ganadores aquellos que tengan valores de adaptabilidad más altos. Una vez realizada la selección, se procede al apareamiento o reproducción sexual de los individuos seleccionados. En esta etapa, los sobrevivientes intercambiarán material cromosómico y sus descendientes formarán la población de la siguiente generación. Las dos formas más comunes de reproducción sexual son: uso de un punto único de apareamiento y uso de dos puntos de apareamiento.

Normalmente el apareamiento se maneja dentro de la implementación del algoritmo genético simple como un porcentaje que indica con qué frecuencia se efectuará. Esto significa que no todas las parejas de cromosomas se aparearan, sino que habrán algunas que pasarán intactas a la siguiente generación. De hecho existe una técnica desarrollada hace algunos años en la que el individuo más apto a lo largo de las distintas generaciones no se aparea con nadie, y se mantiene intacto hasta que surge otro individuo mejor que él, que lo desplaza. Dicha técnica es llamada elitismo. Además de la selección y el apareamiento, existe otro operador llamado mutación, el cual realiza un cambio a uno de los genes de un cromosoma elegido de manera aleatoria. Cuando se usa una representación binaria, el gen seleccionado se sustituye por su complemento. Este operador permite la introducción de nuevo material cromosómico en la población, tal y como sucede con sus equivalentes biológicos. Al igual que el apareamiento, la mutación se maneja como un porcentaje que indica con qué frecuencia se efectuará, aunque se distingue de la primera por ocurrir mucho más esporádicamente.

La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pueden ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla: (1) Su espacio de búsqueda, sus posibles soluciones, debe estar delimitado dentro de un cierto rango. (2) Debe definirse una función de adaptabilidad que indique qué tan buena o mala es una cierta respuesta. (3) Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora. El primer punto es muy importante, y lo más recomendable es intentar resolver problemas que tengan espacios de búsqueda discretos aunque éstos sean muy grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de búsqueda continuos, pero preferentemente cuando exista un rango de soluciones relativamente pequeño.

 

Guillermo Choque Aspiazu
www.eldiario.net
Marzo 30 de 2009
Translate »