Universidad Don Bosco Facultad de Ingeniería “Estudio monográfico sobre algoritmos genéticos y su implementación práctica” Presentado por Francisco Javier Zamora Santana Asesor Ingeniero Eduardo Rivera Agosto 2006 El Salvador, Centro América Índice Introducción 4 Capitulo I – Descripción del proyecto 1.1 Importancia de la investigación 6 1.1.1 Planteamiento del problema a resolver 6 1.1.2 Definición del tema 7 1.1.3 Justificación 8 1.2 Obejtivos 9 1.2.1 Objetivo general 9 1.2.2 Objetivos específicos 10 1.3 Alcances 10 1.4 Limitaciones 11 1.5 Delimitaciones 11 1.6 Metodología de la investigación 13 Capitulo II – Reseña histórica y bases teóricas 2.1 Que son las especies y como se relacionan 15 2.2 Darwin, Wallace y el origen de las especies 17 2.3 La evolución, principio unificador de la biología 20 2.4 Especies y su población, fundamento de la teoría de Darwin 21 2.5 Evolución. Debates, evidencias y pruebas 24 2.6 Principios de genética en la biología y en los algoritmos genéticos 27 Capitulo III – Algoritmos genéticos, variaciones y aplicaciones 3.1 Factores de la evolución y la resolución de problemas 31 3.2 Computación evolutiva 34 3.3 Funcionamiento de los algoritmos genéticos 36 3.4 Usos típicos de los algoritmos genéticos 40 3.5 Paralelismo en los algoritmos genéticos 43 3.6 Operación de los esquemas en la solución de problemas 45 3.7 Cuando utilizar algoritmos genéticos 47 2 3.8 Algunos ejemplos específicos de algoritmos genéticos 48 Capitulo IV - Selección y desarrollo de un algoritmo genético 4.1 Aplicación de algoritmos genéticos 86 4.2 Primer caso examinado 87 4.3 Segundo caso examinado 90 4.4 Tercer caso examinado 99 Capitulo V – Manual de usuario 113 Bibliografía 127 Anexos 128 3 Introducción Desde sus orígenes el ser humano ha tenido que superar dificultades de acuerdo a las condiciones bajo las que se encuentra. Está en su misma naturaleza buscar e idear soluciones a los diversos problemas que puede enfrentar. Conforme encuentra soluciones y desarrolla nuevas tecnologías, cada obstáculo se convierte en un nuevo reto que involucra un análisis mas profundo. Actualmente los avances en la ciencia y la tecnología ponen a disposición del hombre mucha información y, especialmente en la ingeniería, la solución de problemas requiere de estudios cada vez más complejos. Una estrategia común del hombre a lo largo de la historia ha sido la búsqueda de soluciones en su entorno natural. Se dice que el desarrollo tecnológico inició una vez este comenzó a vivir en grupo, es decir cuando se formaron las sociedades primitivas. Los expertos afirman que fue gracias a la convivencia grupal lo que dio la oportunidad para el desarrollo de un lenguaje, la forma más primitiva de comunicación se logró gracias a que los miembros del grupo ensayaban imitando a los demás. Desde las comunidades primitivas hasta el día de hoy, el ser humano ha podido perfeccionar soluciones funcionales aprendiendo del comportamiento a sus alrededores, encontrando una aplicación útil para su beneficio y descubriendo formas de cómo mejorar procedimientos y corregir errores; esto es lo que favorece su desarrollo. La imitación y el aprendizaje permiten al hombre avanzar en cognición y enfocarse en nuevos retos, pero aún cuando los problemas son diferentes y las variables a considerarse cambian, la técnica continua siendo siempre valida, pues diversos descubrimientos continuarán expandiendo los conocimientos hacia nuevos horizontes. La cantidad de aptitudes que el hombre ha logrado acumular a través de los años es impresionante y por ser un desarrollo progresivo muchas veces podría parecer que no hay campo de la ciencia del cual no se hayan realizado estudios previos. Sin embargo, conforme nuevas tecnologías se implementan y el pensamiento humano evoluciona, los problemas se vuelven más 4 complicados, por lo que requieren de soluciones más exactas, eficientes e involucran el uso de herramientas más avanzadas. Seguramente el reto más grande para todo científico se encuentra en si mismo. El mismo pensamiento humano ha sido siempre un misterio para el hombre y conforme se estudia su razonamiento surgen nuevas formas de enfocar los problemas. Muchos científicosi estiman que lo más avanzado en el conocimiento es la inteligencia artificial y su dominio ha llegado a ser considerado como la meta última del desarrollo tecnológico. Sin embargo en la actualidad todavía no se ha podido simular un método de aprendizaje que pueda ser comparado con la eficiencia de un individuo promedio. La inteligencia artificial básicamente tiene como finalidad emular el funcionamiento del cerebro del hombre en una máquina o computadora para que esta posea la habilidad de aprender y pensar de la misma forma que un ser humano. Si se alcanzara dicho objetivo muchas de las actividades que requieren de la supervisión y criterio del hombre podrían ser automatizadas y probablemente surgirían nuevas perspectivas para la resolución de problemas. La búsqueda intensa por simular comportamientos humanos, aprendizaje y toma de decisiones ha llevado a desarrollar áreas de estudio como las redes neuronales, el aprendizaje de máquina y la computación evolutiva. Siendo los algoritmos genéticos los más representativos de esta última área mencionada. La computación evolutiva es en términos generales una técnica de procesamiento de información que esta basada hasta cierto grado en la evolución de la vida biológica dentro del mundo natural. Su importancia radica en su utilidad y para lograr comprender claramente las oportunidades que esta presenta es necesario comprender claramente como evolucionan los organismos vivos. Los primeros capítulos de este documento contienen información relacionada con este tipo de problemas y las bases biológicas de los algoritmos genéticos. Finalmente se describe el i Revista SCIENTIFIC AMERICAN Volumen 294 Número 6- . Junio 2006 5 desarrollo de una aplicación desarrollada con el propósito de ejemplificar este tipo de aplicaciones. Capitulo I Descripción del proyecto 1.1 Importancia de la investigación Esta investigación podrá ser de gran utilidad al incorporar técnicas de programación relacionadas con la inteligencia artificial a la solución de problemas. Una de las áreas de gran importancia dentro de la inteligencia artificial son los algoritmos genéticos y esta tesis podrá ser utilizada posteriormente para aplicarlos a la solución de problemas. 1.1.1 Planteamiento del problema a resolver Actualmente en nuestro medio existe muy poca bibliografía que permita asistir los estudios de los algoritmos genéticos y su implementación en la programación. La mayor parte de la información disponible se encuentra en otros idiomas o está polarizada entre la teoría y la práctica. Por una parte se encuentran documentos muy científicos que dificultan su comprensión o uso práctico y por otro lado se encuentran los documentos que describen sorprendentes aplicaciones de los algoritmos genéticos pero que para discernirlos se necesita tener un amplio conocimiento previo de la materia. Esencialmente el proyecto planteado busca desarrollar un documento bibliográfico que permita comprender los algoritmos genéticos desde una perspectiva práctica, para este fin se auxiliará del desarrollo una aplicación que, a pesar de utilizar información ficticia para servir de ejemplo, esta orientada a resolver un problema muy común en el país. 6 1.1.2 Definición del tema El tema para la tesis de graduación se ha definido como “Estudio monográfico sobre algoritmos genéticos y su implementación práctica”. El proyecto consistirá en realizar una investigación bibliográfica enfocada a la implementación de la teoría en la solución de problemas prácticos. A continuación se describe mas detalladamente lo que formará parte de esta investigación y como pretende realizarse. Como punto de partida se estudiará información relevante de otras fuentes bibliográficas adaptándola a un modelo del documento diseñado con el propósito de guiar al lector hacia una aplicación práctica. Además de exponer los conceptos y elementos involucrados en el uso de estos algoritmos, en esta tesis también explicará como solucionar un problema incorporándolos en la programación de sistemas, para esto se hará uso de un ejemplo práctico que será utilizado a lo largo de la investigación para demostrar y aplicar los temas en estudio. La aplicación que se utilizará como ejemplo será un programa que, con un punto de origen y un punto de destino, utilizará los algoritmos genéticos para determinar la ruta más descongestionada al trasladarse dentro de un mapa diseñado con fines académicos. Este mapa simulará las calles de una ciudad imaginaria y las posibles rutas representarán las diferentes calles en las que un conductor podría transitar. Esta simulación de una ciudad será diseñada con algunas de las propiedades que se deben considerar al estudiar problemas de tránsito en una ciudad. Para que esta aplicación pueda ser de utilidad en la búsqueda de soluciones a los problemas de tráfico, se utilizarán y se asignarán valores a ciertas variables de tráfico que necesariamente deben ser monitoreadas en una ciudad real. 7 Este programa, de ser implementado en una ciudad real con datos reales, podría ser de utilidad para que los conductores puedan optar por las rutas menos congestionadas y así reducir los tiempos y costos de transporte. Si en una ciudad todos los conductores pudieran estar constantemente informados del tráfico vehicular, se lograría un mejor balance de vehículos en las calles de la ciudad. El desarrollo de esta aplicación a lo largo del documento no solo tiene como objetivo mostrar un ejemplo práctico sino también mantener el interés del lector en las diferentes etapas del documento. Como producto final se presentará un documento de utilidad para comprender el origen de estos algoritmos, su funcionamiento y aplicación. Anexo a este se incluirá, como complemento a la teoría, una aplicación práctica de software que exponga los conceptos estudiados en el documento. 1.1.3 Justificación Los motivos por los cuales se opto por esta investigación fueron: • La necesidad de mejorar y enfatizar la importancia de la inteligencia artificial en el aprendizaje actual. • El potencial en la implementación de algoritmos genéticos dentro de los sistemas de información. • La importancia de mostrar a los estudiantes de ingeniería en sistemas, que a pesar de ser una materia optativa, la inteligencia artificial esta al alcance de todos y debe ser de interés para optimizar procesos en sus aplicaciones. • La falta de disponibilidad de bibliografía útil para instruirse y aplicar los algoritmos genéticos en la solución de problemas prácticos. • La necesidad de incentivar la búsqueda de una solución para el problema de aglomeración de vehículos en nuestro país. Este trabajo de tesis se llevará a cabo teniendo siempre presente los puntos previamente mencionados y buscando ofrecer una solución congruente a los mismos. 8 El interés por desarrollar este proyecto de tesis proviene de la certeza que en un futuro los algoritmos genéticos tendrán un papel muy importante en la programación cotidiana. Como resultado de este trabajo se espera proporcionar una investigación lo suficientemente completa como para servir de apoyo bibliográfico. Como se mencionó anteriormente no se busca producir una gran cantidad de información, más bien, se busca crear una guía práctica en la que se describa el funcionamiento de estos algoritmos, sus variaciones e implementación en situaciones reales. Actualmente la mayoría de estudios en este campo se han hecho en otros países y prácticamente todo el material de apoyo para una nueva investigación se encuentra en el idioma inglés. Aun cuando es conveniente que todo estudiante complemente sus investigaciones con otra bibliografía, especialmente escrita en el idioma inglés, este trabajo se podría utilizar como una fuente de información más accesible, es decir como un punto de partida. Orientado a ser herramienta para el estudio de estos algoritmos, el proyecto de tesis debe ser de utilidad para estudiantes de informática que en algún momento necesiten emplearlos con sus propios proyectos de programación. Con este propósito en mente, la investigación se complementará haciendo referencia al estudio de una aplicación de algoritmos que se llevará a cabo paralelamente. 1.2 Objetivos 1.2.1 Objetivo general Proporcionar una fuente bibliográfica útil para los estudiantes de ingeniería que, sin tener amplios conocimientos en la inteligencia artificial, estén interesados en instruirse sobre los algoritmos genéticos o que deseen optimizar sus aplicaciones mediante la implementación de los mismos. 9 1.2.2 Objetivos específicos • Aportar a la biblioteca de la UDB material de apoyo para el estudio de algoritmos genéticos e inteligencia artificial. • Asistir a un estudiante, sin conocimientos previos en la materia, proporcionando una visión acertada de los algoritmos genéticos así como su utilidad. • Presentar los algoritmos genéticos y sus conceptos auxiliándose de una aplicación práctica expuesta para ejemplificar las fases de su desarrollo. • Desarrollar una simulación sencilla en software para PC que haciendo uso de los algoritmos genéticos demuestre su utilidad en la solución de problemas sociales y sirva como punto de partida para el desarrollo de otras aplicaciones. • Proveer, con esta investigación, una guía de carácter descriptivo, mostrando datos acompañados de una explicación orientada a su posible utilidad en otras aplicaciones. • Exponer la forma en que afecta la alteración de las variables genéticas y como se realiza la selección de la configuración más adecuada para un problema específico. 1.3 Alcances • El material bibliográfico que se pretende documentar incluirá los orígenes de los algoritmos genéticos, los personajes que han estado directamente involucrados en el desarrollo de los mismos, sus avances y actuales aplicaciones. También estará contenida la información necesaria para comprender los procesos y funciones involucrados en el funcionamiento de estos algoritmos. • El documento será presentado en un formato accesible al estudiante de manera tal que toda la información incluida será relevante en el proceso de desarrollo de aplicaciones en las que se implementen los algoritmos genéticos. • Los algoritmos genéticos que serán estudiados y utilizados a lo largo de este proyecto estarán basados en los diseñados en la dedada de los 60 por el profesor John H. Holland de Universidad de Michigan en Ann Arbor. 10 • La bibliografía estará apoyada en el desarrollo de una aplicación demostrativa que será documentada desde proyección hasta su finalización y funcionamiento. Esta aplicación será utilizada para ejemplificar como puede abstraer una codificación adecuada de variables y procesos necesarios para la solución de problemas mediante el uso de algoritmos genéticos. • La aplicación demostrativa a desarrollar buscará encontrar la solución a un problema de transporte en el cual se busca desplazarse desde un punto dado A hasta otro punto dado B. En la simulación se tomarán en cuenta una serie de parámetros que servirán para simular condiciones de tráfico específicas en una ciudad. • La aplicación tendrá como finalidad facilitar la comprensión de los algoritmos genéticos y mostrar como la alteración de variables genéticas puede influir en el desempeño de estos algoritmos y su efectividad. Sin embargo, como la aplicación tratará un problema de tráfico vehicular, la solución planteada será lograr una mejor distribución de automóviles en las calles de la ciudad bajo el supuesto de que un alto porcentaje de usuarios utilizarían esta aplicación para evitar transitar en calles congestionadas. 1.4 Limitaciones A pesar de tener establecido un tiempo prudencial para el desarrollo de la investigación, el período de desarrollo para esta tesis limita en cierta forma los detalles y la decoración de la aplicación práctica. Como se mencionó anteriormente el propósito central de la tesis servir como herramienta de estudio, por lo que la mayor parte del tiempo deberá ser invertido en ejemplificar su utilidad didáctica y no en su decoración. 1.5 Delimitaciones • Todo material bibliográfico estará enfocado a facilitar el estudio de los algoritmos genéticos y a la comprensión de su funcionamiento por lo que mucha de la información disponible que no sea relevante o que no este acorde con el propósito de este proyecto será desechada. 11 • La recopilación de material bibliográfico no tiene como propósito generar grandes volúmenes de información. Más bien, busca generar material útil explicado bajo un formato accesible que, apoyándose en ejemplos reales, faciliten una visión práctica de estos algoritmos. • Tanto la aplicación demostrativa a desarrollar como el documento bibliográfico, tienen como propósito facilitar el estudio de los algoritmos genéticos. Si bien es cierto están estrechamente relacionados, no se busca facilitar la comprensión de la aplicación con el documento ni viceversa, mas bien ambos se complementan para alcanzar el mismo fin. • Esta aplicación práctica se desarrollará bajo Visual Basic 6.0 para proveer una interfaz gráfica que facilite a los usuarios la comprensión de su funcionamiento. El programa también tendrá la opción de alterar ciertas variables de entrada para demostrar su incidencia en el resultado del algoritmo. • La aplicación estará limitada a encontrar la ruta más conveniente para trasladarse de un punto a otro en un mapa específicamente diseñado para explicar la codificación y funcionamiento de los algoritmos genéticos. El mapa estará limitado a un radio fijo de aproximadamente dieciséis cuadras, cuyas calles estarán establecidas con un sentido y una cantidad de carriles especifica, no variable. • Los resultados proporcionados por la aplicación estarán sujetos a los cambios en las variables genéticas. Las condiciones de tráfico sobre las calles podrán ser modificadas de manera que la aplicación mostrará la solución que mejor se adapte al ambiente bajo el cual se ejecuta el algoritmo. Esta solución podrá variar dependiendo de las alteraciones realizadas en las variables genéticas. • La aplicación no deberá ser tomada como una solución absoluta o una única solución al problema. Deberá ser tomada como una guía para ser estudiada. El problema utilizado de ejemplo podría ser resuelto con otras variaciones y otros parámetros en las variables genéticas. Sin embargo la eficiencia de las variantes en la solución estaría ligada a la 12 sensibilidad de los parámetros que describan los diferentes segmentos de las calles de la ciudad. Por ser una aplicación con fines demostrativos, no tendría sentido presentar una gran cantidad de pruebas exhaustivas con alteraciones mínimas. 1.6 Metodología de la investigación Este proyecto de investigación, como se mencionó anteriormente, consiste en hacer una recopilación de información bibliográfica, analizarla y exponerla de forma práctica implementándola paralelamente en una aplicación de software. En una primera instancia se deberá obtener la información que será estudiada, para esto se utilizará un método de selección analítica bajo el cual se determinará si la bibliografía encontrada es aplicable o no para los objetivos de la tesis. Este método consiste en consultar diversas de fuentes de información como por ejemplo libros, trabajos de tesis o documentos de investigación ya publicados, disponibles en las bibliotecas universitarias del país. Por otro lado, también se tratarán de explotar al máximo los recursos disponibles en Internet, ya sea en idioma español o inglés. Esta recopilación será la base de la cual se partirá para la elaboración del proyecto. La información será analizada dentro del contexto de la investigación y se evaluará la utilidad que esta podría presentar para un estudiante de computación. Si la información no demuestra una utilidad concreta en el estudio o se encuentra aplicada dentro de un proceso específico que no sea de interés, la información será descartada. Una vez determinada la utilidad del material bibliográfico este deberá ser incorporado al trabajo de tesis adaptándolo al formato y al esquema original. Para esto se utilizará una metodología explicativa estructuralista, ya que su finalidad será explicar el porqué y el cómo influye el elemento o concepto del algoritmo en estudio, sin alterar su estructura inherente. En otras 13 palabras, la información bibliográfica será analizada y adaptada para poder ser explicada, mas no será distorsionada de su concepto original. A lo largo del desarrollo del proyecto se utilizará principalmente la técnica documental pues estará constantemente refiriéndose a las diferentes fuentes de información. Sin embargo, la investigación no es absolutamente teórica. Se realizará una aplicación práctica enlazada correspondientemente con la teoría, para la cual será necesario aplicar técnicas de campo que faciliten la descripción de los conceptos utilizados en la aplicación. 14 Capitulo I I Reseña histórica y bases teóricas 2.1 Que son las especies y como se relacionan Uno de los principios más importantes dentro de la biología es la evolución de las especies, sin embargo este principio también ha demostrado ser de gran utilidad para las ciencias de la computación. Es indispensable tener un claro concepto de lo que es una especie y como se limita antes de comprender como estas se modifican con el tiempo. La palabra especie proviene del latín species y en general es un conjunto de individuos que, además de los caracteres genéricos, tienen en común otros por los cuales se asemejan entre sí y pueden ser distinguidos de individuos pertenecientes a las demás variedades. A lo largo de los años este concepto ha cambiado constantemente, desde los tiempos de Aristóteles ya se establecía que los géneros se dividen en especies pero esta, a su vez, puede convertirse en género con respecto a las subdivisiones secundarias. Entre las diferentes definiciones podemos encontrar varias citas que muestran las formas en que se maneja el concepto. “Contamos tantas especies cuantas formas distintas fueron creadas en el principio”ii. “Especie es el conjunto de los individuos descendientes uno de otro o de padres comunes y de los que se les parecen tanto como aquellos entre si”iii. “Especie es la colección de todos los individuos que se parecen más entre si que a otros; que por fecundación recíproca pueden dar individuos fértiles, y que se reproducen por generación, de tal ii Linneo, “Phylosophya botanica” iii Georges Cuvier (1769-1832) 15 manera que, por analogía, se les puede suponer a todos procedentes originariamente de un solo individuo”iv. “Especie es el conjunto de todos los individuos cualitativamente idénticos que no presentan entre sí, en sus elementos vivos, mas que diferencias cuantitativas”v. “Todos los individuos fecundos entre sí y cuyos descendientes son también indefinidamente fecundos”vi. A pesar de que la definición de una especie ha sido analizada muchas veces, el verdadero dilema ocurre al momento de limitar que es y hasta donde las características de un individuo se asemejan lo suficiente como para no ser considerado parte de una diferente. La determinación de los límites es puramente subjetiva y, por tanto, expuesta a las modalidades de la interpretación personal. Algunos conceptos usuales son muy antiguos y en ciertas ocasiones anteriores a su establecimiento científico. Si no se dieran los cambios en las especies, sería muy fácil definir cada una de ellas y sus miembros, estableciendo que grupo de individuos son cualitativamente idénticos. Pero en la realidad una entidad definida de esa forma no es realmente una especie, sino lo que usualmente se llama una línea pura o un clon. Sin embargo, existen muchas diferencias entre las cualidades de cada miembro de una especie y a su vez existen cambios que como conjunto se llevan a cabo. La clave esta en definirlas como agrupaciones de organismos biológicos que compongan una unidad natural de reproducción. Este es el punto definitivo, originalmente se puede reproducir y engendrar crías que como adultos serán similares a sus padres. Existen algunas excepciones, pues se da el caso en que dentro de una misma especie se encuentren individuos que no puedan reproducirse entre ellos. Como ejemplo podemos tener a iv Augustin Pyrame de Candolle (Ginebra, suiza, 4 de febrero de 1778– 9 de septiembre de 1841) v Félix le Dantec vi Rennolls, K. and Laumonier, Y. Analysis of species hyperdiversity in the tropical rain forests of Indonesia: the problem of non-observance. Environmental Forest Science. 1998; 54355-362. 16 los perros, en que las razas de perros grandes no pueden reproducirse con perros pequeños, sin embargo ambas razas forman una misma especie. Este es uno de los puntos más interesantes al momento de estudiar las especies y su evolución. Así como en los perros pueden existir amplias variaciones que hoy conocemos como razas, también existen otros animales que no permiten diversificaciones. Los chita por ejemplo, solamente se pueden reproducir entre ellos y por tanto solo pueden procrear crías con ninguna o pocas mutaciones. Las especies, como las que ahora habitan en el planeta, proceden de otras distintas que existieron en el pasado, a través de un proceso de descendencia con modificación. Esto es precisamente la evolución biológica, es el proceso histórico de transformación de unas especies en otras descendientes, e incluye la extinción de la gran mayoría de las que hasta el momento han existido. Es claro que la evolución biológica es un proceso largo y muchas veces imperceptible. Sin embargo, esto nos indica que no es posible que una especie pueda procrear otra totalmente diferente. Dentro de la población de individuos se pueden originar nuevas subespecies, finalmente cuando una de estas pierde el vinculo característico que la une con las demás se considera una unidad diferente. La idea de evolución por modificación y derivación implica la existencia de antepasados comunes para cualquier par de especies. 2.2 Darwin, Wallace y el origen de las especies Charles Darwin publicó en 1859 su obra “El origen de las especies” y con esta publicación quedó establecida de forma definitiva la idea de la evolución biológica. Sin embargo los estudios en la biología evolutiva habían producido numerosas teorías, de hecho en el mismo año que Darwin nació se publicaba la obra filosofía de la evolución, por Jean-Baptiste Monet, Caballero de Lamarck, autor de la primera teoría organizada de la evoluciónvii. vii http://natureduca.iespana.es/bio_teorias_evol.htm 17 La teoría de Lamarck fue vivamente atacada en su tiempo, hasta el extremo de ser silenciada. El mayor rechazo llegó de los grupos religiosos, que preveían el derrumbe de las explicaciones basadas en la Biblia sobre el origen de los seres vivos. Sin embargo, se mantuvo esta corriente de pensamiento evolucionista, sirviendo de base para lo que terminaría siendo una verdadera revolución en las ideas biológicas del momento, y que desembocaría en los trabajos de Darwinviii. El naturalista británico recopiló e interpretó un gran número de observaciones y experimentos de muy diversas disciplinas de investigación y los presentó como un argumento irrefutable en favor del hecho de la evolución. Pero a su vez suministró un mecanismo para explicar las adaptaciones complejas y características de los seres vivos: la selección natural. Desde 1802 cuando el teólogo W. Paley publica la obra Teología natural, donde argumentaba que el diseño funcional de los organismos evidenciaba la existencia de un creador omnisapiente, existía un gran reto para las ideas de biología evolutiva. Él afirmaba, utilizando el ojo humano como ejemplo por su delicado diseño, que únicamente podría haber sido obra directa de Dios. Para los naturalistas que querían explicar los fenómenos biológicos por procesos naturales, explicar la adaptación, la maravillosa adecuación de los organismos a su ambiente, constituía el problema fundamentalix. El argumento del diseño de Paley tenía una gran influencia en los naturalistas del siglo XIX, a pesar de que esta visión en la que existía una intervención directa de un creador, violaba incuestionablemente el concepto de naturaleza que se había establecido con el desarrollo de la física en los siglos XVI y XVII. Los fenómenos del Universo, según esta nueva concepción, eran explicables por procesos naturales. La naturaleza, por si sola, era un objeto aceptable para preguntar y contestar científicamente. Con la publicación del estudio de Darwin se introduce esta revolución en la biología. Lo verdaderamente revolucionario en Darwin fue el proponer un mecanismo natural para explicar la génesis, diversidad y adaptación de los organismosx. viii http://natureduca.iespana.es ix http://biologia.uab.es/divulgacio/sn/sn.htm x http://biologia.uab.es/divulgacio/sn/sn.htm 18 El gran reto de Darwin era explicar las complejas adaptaciones de los organismos vivos, como el diseño funcional de un ojo, por mecanismos naturales. La solución de Darwin fue proponer el mecanismo de la selección natural. Como se podrá ver mas adelante, este concepto es de gran interés no solo para comprender la evolución biológica sino también la computación evolutiva. Para obtener las respuestas que buscaba, Darwin se embarcó como naturalista en el velero Beagle, a bordo del cual viajó alrededor del mundo durante cinco años. Allí recogió infinidad de datos de carácter geológico, zoológico y botánico en los que se inspiró para formular sus puntos de vista. De regreso a Inglaterra, en 1837 se instaló en Londres, ocupándose de la redacción de su diario del viaje y de la elaboración de su estudio sobre los arrecifes de coralxi. La publicación de los estudios de Darwin requirió ser apresurada por las circunstancias del momento, si bien es cierto se exponía a los ataques de los seguidores de la teoría creacionista, recibió una carta procedente del archipiélago malayo, de Sir Alfred Wallace, un biólogo británico, nacido en Monmouth (hoy Gwent)xii. Él se encontraba realizando una investigación y en la expedición observó las diferencias zoológicas fundamentales entre las especies de animales de Asia y las de Australia y estableció la línea divisoria zoológica -conocida como línea de Wallace- entre las islas malayas de Borneo y Célebes. Aquí formuló su teoría de la selección natural que comunicó a Darwin en 1858xiii. Finalmente, en 1859, el 24 de Noviembre, a los doce meses de haber recibido el manuscrito de Wallace, publicó su obra "Origin of Species", de la que Wallace recibiría un ejemplar y del cual opinó: "Perdurará tanto como los Principia de Newton. El señor Darwin ha donado al mundo una ciencia nueva, y su nombre, a juicio mío, se destaca por encima del de muchos filósofos antiguos y modernos. ¡¡La fuerza de la admiración me impide decir más!!". El hecho de que ambos investigadores se interesaran y estuvieran determinados a desarrollar estudios relacionados en diferentes partes del mundo fue una de las coincidencias más xi http://natureduca.iespana.es/biog_darwin.htm xii http://www.terra.es/personal/cxc_9747/transformismo.html xiii http://www.terra.es/personal/cxc_9747/el_origen.html 19 portentosas de la historia de la ciencia. Refiriéndose a Darwin, Wallace escribió una vez: "Ni en sueños me hubiera acercado yo a la perfección de su libro. Confieso mi agradecimiento de que no me incumbiera presentar la teoría al mundo". Sin embargo la teoría de Wallace difiere de la de Darwin en algunas cuestiones importantes; por ejemplo, niega que la selección natural sea suficiente para dar cuenta del origen del hombre, lo cual requiere, según Wallace, la intervención divina directa. También creyó que el proceso evolutivo había finalizado en los hombres y que la evolución sería imposible en adelantexiv. 2.3 La evolución, principio unificador de la biología Se dice que el concepto de evolución llego a unificar muchos de los diferentes estudios dentro de la biología, al definir apropiadamente la evolución es posible comprender las propiedades que diferencian a los organismos unos de otros y como estos se adaptan al medio en el que habitan. Por medio de la evolución se puede explicar la proximidad existente entre especies diferentes. El genético evolucionista Theodosius Dobzhansky una vez afirmó que “la teoría evolutiva se relaciona con el resto de la biología de forma análoga a como el estudio de la historia se relaciona con las ciencias sociales”xv. Realmente el concepto de evolución es sencillo pero, posiblemente por lo difícil que fue su aceptación, la mayor parte de las personas tienden a confundir lo que en sí afirma esta teoría. Comúnmente se piensa que las especies pueden ser ordenadas en una cadena evolutiva, empezando desde las bacterias a través de los animales "inferiores", hasta los animales "superiores" y, finalmente, hasta el hombre. En realidad, la idea de una gran cadena del ser, que se remonta a Carolus Linnaeus (1707-78), fue echada por tierra por la idea de Darwin de la descendencia comúnxvi. Las pequeñas, pero muy significativas, equivocaciones de este concepto afectan en gran medida los estudios de la alteración en las especies y de toda la biología en general. Por tanto afectan xiv http://www.terra.es/personal/cxc_9747/el_origen.html xv "Genética y el origen de las especies" publicada en 1937 xvi http://bioinformatica.uab.es/divulgacio/evol.html 20 también los estudios de computación evolutiva que tiene su fundamento en estos mismos enunciados. La palabra evolución tiene una variedad de significados. Frecuentemente se le menciona como el hecho de que todos los organismos estén relacionados a través de la descendencia con un antepasado común. También se le llama de esta forma a la teoría de cómo aparecieron los primeros organismos vivos, lo cual es errado puesto que debe llamarse abiogénesis. Y, otras veces, la gente utiliza la palabra cuando realmente quieren decir selección natural, lo que es en realidad uno de los mecanismos de la evolución. Básicamente lo que Darwin afirmaba es que la alteración en las especies es un proceso de adaptación natural en la cual, en una primera etapa se produce la mutación, recombinación y acontecimientos al azar, es decir producción de la variabilidad genética, para en una segunda etapa quedar regulada esa variabilidad mediante la selección natural, y en la cual el proceso artificial generado por el hombre no produce variabilidadxvii. 2.4 Especies y su población, fundamento de la teoría de Darwin El pensamiento poblacional Hay grandeza en esta concepción de la vida,... que mientras este planeta ha ido girando según la constante ley de la gravitación, se han desarrollado y se están desarrollando, a partir de un comienzo tan sencillo, infinidad de formas cada vez más bellas y maravillosas Charles Darwin La mayor dificultad que tuvo que enfrentar Darwin para introducir su teoría de la evolución fue sin lugar a dudas el tener que desafiar las ideas que se tenían en su tiempo sobre los seres vivos. Se consideraban las especies como entidades fijas que no cambiaban, puesto que habían sido creadas directamente por Dios estas eran perfectas y no tenían necesidad de cambio. Para imponer su teoría de la evolución y de la selección natural, Darwin tuvo que introducir una nueva forma de entender la variación en la naturaleza, el pensamiento poblacionalxviii. xvii http://anthro.palomar.edu/evolve/evolve_2.htm xviii http://bioinformatica.uab.es/divulgacio/evol.html#revolucion 21 En aquel entonces las diferencias en la forma, en la conducta o en la fisiología de los organismos de una misma especie no eran más que imperfecciones, errores en la materialización de la idea de la especie. En contraste con esta visión, la variación individual, lejos de considerarla superficial, fue expuesta por Darwin como la piedra angular de la evolución. La variación en el seno de las especies o poblaciones es lo único real, es la materia prima de la evolución, a partir de la que se va a crear toda la diversidad biológica. Son las diferencias existentes entre los organismos de una especie las que, al magnificarse en el espacio y en el tiempo, producirán nuevas poblaciones, nuevas especies, y por extensión, toda la diversidad biológica. Bajo la visión darviniana, la variación es la única realidad de las especies. No hay un color de piel en la especie humana ideal. Cada individuo con su variación característica es un elemento esencial de nuestra especiexix. Cuando Darwin exponía sus ideas respecto al hombre, afirmaba que éste condiciona la evolución de determinadas especies para su propio aprovechamiento mediante la selección artificial, sin embargo en su obra explicó que el hombre por si mismo no produce variabilidad; lo único que hace es exponer intencionadamente seres orgánicos a nuevas condiciones de vida, y luego la naturaleza actúa sobre la organización, y causa la variabilidad. Es claro que el hombre puede seleccionar y selecciona las variaciones que la naturaleza le da, y de este modo las puede controlar como desee. Adapta así animales y plantas a su propio beneficio o placer. Puede hacerlo metódicamente o puede hacerlo inconscientemente, preservando los individuos que le son más útiles de momento, sin pensar en alterar la especie. No hay motivo aparente para que los principios que han actuado con tanta eficacia en la domesticación no hayan actuado en la naturaleza. Nacen más individuos de los que pueden sobrevivir. La más ligera ventaja de un ser sobre los demás con los cuales entra en competencia, una mejor adaptación a las condiciones físicas que le rodean, por mínima que sea, cambiará el equilibrio en su favor. Pero es importante evitar confundir los enunciados de Darwin en su obra “El origen de las especies” con los términos de evolución. De lo contrario se puede llegar a malinterpretar la evolución con los cambios morfológicos de una especie, es decir los cambios físicos en el xix http://bioinformatica.uab.es/divulgacio/evol.html#revolucion 22 organismo de algunos individuos de la población. En realidad puede ocurrir evolución sin cambio morfológico; y puede ocurrir cambio morfológico sin evolución. Un ejemplo claro somos los humanos, en general en las poblaciones los individuos son más altos ahora que en el pasado reciente, como resultado de una dieta y medicina mas favorables. Cambios como éste, inducidos solamente por alteraciones en el entorno, no cuentan como evolución, porque no son hereditarios; en otras palabras, el cambio no se transmite a la descendencia del organismo. Lo que en la biología se conoce como el fenotipo de un organismo esta constituido por sus propiedades morfológicas, fisiológicas, bioquímicas y de comportamiento. El fenotipo de un organismo está determinado por sus genes y su entorno. La mayoría de los cambios debidos al entorno son bastante sutiles, por ejemplo, las diferencias en el tamaño. Los cambios fenotípicos a gran escala son debidos obviamente a cambios genéticos, y por tanto a la evolución. Otro de los conflictos que se dan al confundir los enunciados de Darwin con la evolución misma es que se tiende a considerar como progreso, pero existe un gran peligro al hacer esa afirmación, las poblaciones simplemente se adaptan a su entorno actual. No se hacen necesariamente mejores con el tiempo en ningún sentido absoluto. Un carácter o estrategia que es exitosa en una ocasión puede no serlo en otra. Paquin y Adams demostraron esto experimentalmente. Sembraron un cultivo de levadura y lo mantuvieron durante muchas generaciones. Ocasionalmente, surgía una mutación que permitía a su portador reproducirse mejor que sus contemporáneos. Estas cepas mutantes acababan sustituyendo a las cepas anteriormente dominantes. Se tomaron muestras de las cepas más exitosas del cultivo en varias ocasiones. En posteriores experimentos de competición, todas las cepas vencían a las cepas inmediatamente anteriores que dominaban en el cultivo. Sin embargo, algunas muestras del principio podían vencer a las cepas que surgieron al final del experimento. La habilidad competitiva de una cepa siempre era mejor que la de la anterior, pero la competitividad, en un sentido general, no estaba aumentando. El éxito de cualquier organismo depende del comportamiento de sus contemporáneos. No es probable que exista un diseño o estrategia óptimos para la mayoría de los caracteres o comportamientos, sólo contingentesxx. xx http://the-geek.org/intro-biologia.html 23 Por otra parte, los organismos no son objetivos pasivos de su entorno. Todas las especies y en especial el ser humano modifican su propio entorno. Como mínimo, los organismos recogen nutrientes de sus alrededores y depositan desechos. A menudo, los productos de desecho benefician a otras especies. El estiércol animal es un fertilizante para las plantas. Inversamente, el oxígeno que respiramos es un producto de desecho de las plantas. Las especies no cambian simplemente para adaptarse a su entorno; también modifican su entorno para adecuarlo a ellas. Los castores construyen presas para crear un estanque apropiado para mantenerse y sacar adelante a las crías. Alternativamente, cuando el entorno cambia, las especies pueden migrar a climas adecuados o buscar micro entornos a los que estén adaptadasxxi. Es importante aclarar que en las publicaciones de Darwin aún existen afirmaciones que no han podido ser demostradas por los registros fósiles, esto muchas veces puede generar confusiones y provocar dudas sobre la evolución en si. En el siguiente capítulo se presentarán aclaraciones al respecto, sin embargo, los conceptos que se manejarán a lo largo de este estudio no entrarán en conflicto con los debates existentes puesto que la computación evolutiva se basa en las adaptaciones de los organismos a su entorno y la supervivencia del más apto. 2.5 Evolución. Debates, evidencias y pruebas Actualmente rara vez se discute el tema públicamente. Sin embargo, hay una discusión constante entre científicos sobre casi todos los aspectos de la teoría evolutiva. La controversia no es en si la evolución, más bien, los medios por los cuales sucede. El punto en discusión no esta basado en la evolución, sino en la teología. Se debate si las formas de vida se originaron debido a una coincidencia de circunstancias favorables o no. La teoría de Darwin de la selección natural es la única que pretende explicar cómo los hombres y otras especies son exclusivamente el resultado de fuerzas naturales. Esta es la razón por la cual la teoría del Darwin entra en excesiva discusión, la evolución realmente no juega un papel tan importante. Es la teoría de Darwin la que se enseña en las escuelas, y el hecho de que la mayoría de textos en el tema no hacen la distinción crucial entre la "evolución" y "Darwinismo" tiende a xxi http://www.ewtn.com/library/HOMELIBR/DEATHDAR.TXT 24 complicar más las cosas. Aunque su nombre es sinónimo de su teoría, la idea de la evolución ya se había mencionado desde los antiguos filósofos griegos, si bien es cierto las publicaciones de Darwin mostraron pruebas concretas de la evolución, a su vez también pretendían proporcionar una explicación de cómo ocurrió la evolución, una en que el origen de la vida era un proceso puramente mecánico y sin intervención alguna de Diosxxii. La evolución que se da en una escala reducida, en el interior de una especie y en el intervalo de unas pocas generaciones, se denomina micro evolución. La macro evolución es la evolución a gran escala, y abarca periodos considerables de tiempo, y grandes procesos de transformación; en el caso más extremo comprendería toda la evolución de la vida. Por medio de su teoría de la selección natural, Darwin pretendía afirmar que una cierta forma de vida original desconocida fue desarrollada y diversificada convirtiéndose en una variedad extensa de todas las plantas y animales que vemos hoy. Este es un punto crucial que frecuentemente entra en debate por los críticos científicos. Darwin observó las evidencias de micro evolución, sin embargo no de macro evolución. Él se refiere constantemente a los cambios pequeños que ocurren dentro en un cierto plazo a la población de una especie. Tal evolución es común, realmente las variedades de pinzones que Darwin observó en las islas de las Islas Galápagos no son mas que otro ejemplo de micro evolución. Sin evidencia empírica directa, Darwin afirmaba que dentro de períodos de tiempo excesivamente largos estos micro cambios podrían dar lugar a la macro evolución, que consiste en saltos realmente grandes como por ejemplo el de la ameba al reptil y luego al mamífero. Este es el punto en que su teoría funciona únicamente con problemas que todavía no se resuelven en las mentes de muchos científicos. Existen dos lugares posibles para buscar la demostración de la teoría de Darwin: los experimentos fósiles del expediente y de la crianza con los animales. Si la teoría de Darwin está correcta, el expediente fósil debe demostrar innumerables adaptaciones graduales entre especies anteriores y las más recientes. Darwin estaba enterado, sin embargo, que el expediente fósil de época no demostraba nada que lo apoyara. Había discontinuidades enormes entre los cambios en especies animales y entre los grupos importantes de plantas. Él dio como hecho, en su capítulo "Las imperfecciones del expediente geológico", xxii http://www.ewtn.com/library/Theology/zschonevo2.HTM 25 que el futuro de la paleontología completara los vacíos, que él admitió ser "la objeción más grave a mi teoría". Las cantidades enormes de fósiles que se han obtenido en excavaciones desde entonces, en todo caso, hacen más evidentes los espacios que preocuparon Darwin. Jay Gould, biólogo de Harvard, llama a esta carencia del cambio gradual en el expediente del fósil el "secreto comercial" de la paleontología moderna. El expediente fósil demuestra exactamente lo que se demostró en el aquellos días de Darwin, que las especies aparecen repentinamente en un estado completamente desarrollado y cambiaron poco o nada en absoluto antes de desaparecer. Hace cerca de 550 millones de años, al principio de la era cambriana, había una explosión de las formas de vida complejas, como moluscos, medusas, trilobites, para lo cuál no se puede encontrar una sola forma ancestral en rocas anterioresxxiii. El paleontólogo Stephen Stanley escribe que “el expediente fósil no demuestra convincentemente una sola transición a partir de una especie a otra”. Muchas de las secuencias representativas de la pendiente ancestral son conjeturas y se están desechando constantemente. Paleontólogos, en efecto, encuentran en un fósil de una especie extinta y hacen escalando poco a poco un panorama que la conecta con un animal último o anterior, pero nunca encuentran las formas transitorias que la teoría de Darwin exigexxiv. No obstante, si nos centramos en la evolución por si misma no existen dudas al respecto, independientemente la micro evolución pueda convertirse en macro evolución con el pasar del tiempo, es un hecho que mediante observaciones a poblaciones de especies actuales a pequeña escala se puede obtener evidencia directa de evolución. La selección artificial efectuada por el hombre en el perro o el caballo son claros ejemplos que muestran el potencial de modificación de una especie. Por su propia dimensión temporal, no es posible demostrar la macro evolución directamente, para esto se requeriría de un registro fósil extenso. La historia de la vida es una historia de extinciones, con unos pocos supervivientes. El 99,9% de las especies que han existido alguna vez xxiii http://www.stephenjaygould.org/ xxiv http://www.digisys.net/users/hoppnrmt/transitionfossils.htm 26 están hoy extintas. Grupos enteros de organismos, como los dinosaurios, los trilobites, los ameboideos, se han extinguido sin dejar descendiente algunoxxv. Como señala el reconocido paleontólogo S. Gould, el registro fósil no es un relato convencional que conduce a los diferentes linajes a más excelencia, más complejidad, más diversidad. La historia de la vida no muestra dirección ni sentido. La evolución es una narración de eliminación masiva seguida de diferenciación en el interior de unos cuantos supervivientes. Es prácticamente imposible determinar la dirección de la evolución porque la importancia de los acontecimientos concretos son los verdaderos agentes de la historia, ya sean hechos contingentes, como la extinción masiva, o la posesión de una variante adaptativa adecuada cuando ésta es requeridaxxvi. 2.6 Principios de genética en la biología y en los algoritmos genéticosxxvii Todos los organismos vivos están compuestos por células, cada célula contiene el mismo sistema de uno o más cromosomas, los cromosomas son secuencias de ADN, que sirven como un tipo de "modelo" para el organismo. Un cromosoma, por concepto, se puede dividir en genes, cada uno de los cuales codifica una proteína particular. En cierta forma, se puede considerar un gen como la codificación de un rasgo o característica del organismo, como ejemplo el color de los ojos. Las diferentes "codificaciones posibles" para un rasgo, como un ojo puede ser azul, verde o café, se llaman alelos. Cada gen está situado en un lugar geométrico particular, es decir una posición especifica en el cromosoma. Muchos organismos tienen múltiples cromosomas en cada célula. La colección completa de material genético que son todos los cromosomas tomados juntos, se llama el genoma del organismo. El término genotipo se refiere al sistema de genes contenido en un genoma particular. Se dice que si dos individuos tienen genomas idénticos, entonces también tienen el mismo genotipo. El genotipo da origen a las características físicas del fenotipo. El fenotipo es el xxv http://bioinformatica.uab.es/divulgacio/evol.html#revolucion xxvi http://bioinformatica.uab.es/divulgacio/evol.html#revolucion xxvii An Introduction to Genetic Algorithms, Mitchell Melanie -A Bradford Book The MIT Press, Cambridge, Massachusetts • London, England - Fifth printing, 1999, First MIT Press paperback edition, 1998 - Copyright © 1996 Massachusetts Institute of Technology 27 conjunto de rasgos o características visibles de un organismo, por ejemplo, el color del cabello, el peso o la presencia o ausencia de una enfermedad. Los rasgos fenotípicos no son necesariamente genéticos. Los organismos cuyos cromosomas están ordenados en pares se llaman diploide; los organismos cuyos cromosomas están desapareados se llaman haploide. En la naturaleza, la mayoría de las especies que se reproducen sexualmente son diploides, entre estos los seres humanos, que cada uno tiene 23 pares de cromosomas en cada célula somática en el cuerpo. Durante la reproducción sexual, la recombinación o cruce, los genes de cada uno de los padres se intercambian entre cada par de cromosomas para formar un gameto, es decir un solo cromosoma, y entonces los gametos de los dos padres se aparean hasta crear un sistema de cromosomas diploide completo. En la reproducción sexual haploide, los genes se intercambian entre cromosomas singulares de los dos padres. El descendiente está sujeto a una mutación, en la cual las partículas elementales de la DNA llamados nucleótidos se heredan al descendiente, los cambios resultan a menudo por errores de copiado. La aptitud de un organismo se define típicamente como la probabilidad que tiene el organismo para vivir y reproducirse, esto es conocido también como viabilidad. También se define en función del número de descendientes que el organismo logra tener, lo cual se conoce también como fertilidad. En el contexto de algoritmos genéticos, los términos biológicos se utilizan con la intención de mantener la analogía con biología verdadera, aún cuando las entidades a las que se refieren son mucho más simples que las biológicas. Para conocer la evolución en los algoritmos genéticos, es necesario conocer primero como se desarrolla este campo en el ambiente natural. En los algoritmos genéticos, el término cromosoma se refiere típicamente a una solución posible a un problema, codificado a menudo como cadena de bits. Los "genes" son por lo general bits aislados o pequeñas cadenas adyacentes de bits que codifican un elemento particular de la solución del candidato. Un ejemplo sería, en el contexto de la optimización de una función de múltiples parámetros, los bits que codificaban un parámetro particular se podrían considerar como un gen. 28 Un alelo en una secuencia de bits tiene un valor ya sea un cero o uno; Si se utilizan alfabetos más complejos más alelos son posibles en cada posición geométrica. El cruce consiste en por lo general en intercambiar material genético entre dos sujetos haploides, que contienen un solo cromosoma. La mutación consiste en el mover elementos dentro de una secuencia de bits, intercambiando el símbolo en un lugar geométrico aleatoriamente elegido por un nuevo símbolo también aleatoriamente elegido. La mayoría de los algoritmos genéticos emplean individuos haploides, particularmente, los individuos de un solo cromosoma. El genotipo de un individuo en un algoritmo genético que usa secuencias de bits es simplemente la configuración de bits en el cromosoma de ese individuo. En general no existe una noción de fenotipo en el contexto de los algoritmos genéticos, aunque muchos investigadores han experimentado más recientemente con algoritmos en los cuales se utiliza un nivel genotípico y un nivel de fenotipo. Los cromosomas en una población de algoritmos genéticos toman típicamente la forma de cadenas de bits. Cada posición geométrica en el cromosoma tiene dos alelos posibles, uno y cero. Cada cromosoma se puede visualizar como un punto en el espacio de la búsqueda de las soluciones del candidato. El algoritmo procesa las poblaciones de cromosomas substituyendo sucesivamente a una población por otra. Esto frecuentemente requiere de una función de aptitud que asigne un valor a cada cromosoma en la población que esta siendo procesada. La aptitud de un cromosoma depende de que tan eficientemente el cromosoma solucione el problema tratado. Capitulo II I Algoritmos genéticos, variaciones y aplicaciones 29 Realmente no existe una definición rigurosa de lo que es un algoritmo genético. No existe un modelo aceptado por todos los investigadores de computación evolutiva y que diferencie a estos algoritmos de otros métodos evolutivos en la computación. Sin embargo, se puede afirmar que la mayoría de los métodos llamados algoritmos genéticos tienen por lo menos ciertos elementos en común. Entre estos tenemos las poblaciones de cromosomas, la selección según aptitud, el cruce para producir nuevos descendientes y la mutación al azar del nuevo elemento. A continuación se citarán algunas de las definiciones actualmente publicadas. Un algoritmo genético es un proceso de búsqueda que optimiza una función objetivo F manteniendo una población P de soluciones posibles y que implementa operaciones inspiradas por la genética (conocidos cruce y mutación) para generar una nueva población a partir de la generación anterior. Generalmente las soluciones posibles se encuentran codificadas como cadenas. - Bob Carterxxviii Son algoritmos que codifican las soluciones con una estructura parecida a la de un cromosoma o genoma. El algoritmo genético genera una población de genomas y luego aplica cruces y mutaciones a cada individuo para generar nuevos individuos. Utiliza un criterio de selección en el cual los individuos más aptos sean utilizados para aparearse. Siendo la función objetivo la que determina la aptitud o que tan bueno un individuo es. - Matthew Wallxxix Los algoritmos genéticos son una parte de la computación evolutiva, la cual continúa creciendo rápidamente en el área de la inteligencia artificial. Como su nombre lo indica están inspirados por la teoría de Darwin de la evolución. En pocas palabras, la solución encontrada por un algoritmo genético es mas bien evolucionada. - Marek Obitkoxxx Los algoritmos genéticos son algoritmos diseñados para buscar, enfatizar y procrear buenas soluciones para un problema de forma altamente paralela. - James Matthewsxxxi xxviii Carter and Park, "How good are genetic algorithms at finding large cliques" (BU-CS-TR 93-015) Section 4 discusses implementation on CM-5 xxix A Genetic Algorithm for Resource-Constrained Scheduling - by Matthew B Wall, Submitted to the Department of Mechanical Engineering on 14 May 1996 in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Mechanical Engineering. xxx http://cs.felk.cvut.cz/~xobitko/ga/ - August and September of 1998 at the Hochschule für Technik und Wirtschaft Dresden (FH) (University of Applied Sciences). xxxi James Matthews, A "hello world!" genetic algorithm example, http://www.generation5.org /content/2003/gahelloworld.asp 30 Un algoritmo genético es un método de búsqueda que espera un resultado igual o muy cercano a la solución de un problema dado. - Yi Wangxxxii 3.1 Factores de la evolución y la resolución de problemas Con base en los conceptos de la evolución biológica, vale la pena analizar que es lo que convierte la evolución y adaptación al medio de los organismos uno de los mecanismos mejor diseñados para solucionar problemas de computación en muchos campos. Ya es conocido que la gran mayoría de problemas en los sistemas de computación requieren buscar con un número enorme de posibilidades para encontrar soluciones. Un ejemplo concreto que puede facilitar esta explicación es el problema de la proteína, planteado a la ingeniería en sistemas para encontrar un algoritmo que buscará entre un número muy extenso de secuencias posibles del aminoácido de una proteína con las características especificadasxxxiii. Otro ejemplo en el que se hace evidente la necesidad de búsqueda es en un sistema de reglas o las ecuaciones que pronostican índices económicos y mercados financieros, tal como la devaluación respecto a la moneda extranjeraxxxiv. Tales problemas de búsqueda a menudo se pueden beneficiar del paralelismo en los algoritmos genéticos, pues muchas posibilidades se exploran simultáneamente de una manera eficiente. Cuando se habla del paralelismo en sistemas de cómputo, básicamente se refiere a muchos procesos ejecutándose y evaluándose al mismo tiempo, esto es una estrategia inteligente para decidir cual es el sistema de secuencias disponibles más conveniente para evaluar. Muchos problemas de cómputo requieren un programa de computadora que se adapte dinámicamente, es decir que continuamente muestre un buen desempeño en un ambiente cambiante. Una de las características de estos sistemas es que tienden a ser robustos, ya que por lo general pretenden controlar tareas en ambientes variables y que las interfaces de la aplicación deben adaptarse a las preferencias de los diferentes usuarios. Por otro lado se encuentran también los xxxii Jahau Lewis Chen and Yi-Cheng Tsao. Optimal design of machine elements using genetic algorithms. Chung- Kuo Chi Hsueh Kung Ch'eng Hsueh Pao, 14(2):193-199, April 1993. xxxiii Hunter, Searls, and Shavlik 1993 xxxiv Esben Sloth Andersen, Evolutionary Economics: Post-Schumpetrian Contributions 31 programas que buscan ante todo innovar, la construcción de algo verdaderamente nuevo y original, por ejemplo un nuevo algoritmo para lograr una tarea o aún un nuevo descubrimiento científico. Finalmente, muchos problemas de cómputo requieren las soluciones complejas que son difíciles de programar de forma lineal. Como ejemplo principal tenemos el problema de crear inteligencia artificial. En los inicios de esta ciencia, los pioneros de la inteligencia artificial creyeron que simular la inteligencia humana sería una tarea que consistiría de manera directa codificar a un programa las reglas que proveerían de inteligencia. Los sistemas expertos fueron el resultado de esta concepción optimista pero demasiado simplificada. En la actualidad, la mayoría de investigadores de Inteligencia Artificial están convencidos que la inteligencia profunda es demasiado compleja para poder ser codificada manualmente de forma deductiva. No obstante, creen que la mejor ruta a la inteligencia artificial es por medio de un paradigma inductivo, es decir empezando por lo básico y simulando su desarrollo, en el cual los seres humanos escriban solamente reglas muy simples, y los comportamientos complejos tales como la inteligencia emergen del uso y de la interacción masiva, siempre paralelo a las reglas simples originales. El estudio de los programas de computadora inspirados por el sistema nervioso humano es un ejemplo claro de la filosofía que busca hacer surgir la inteligencia a partir de interacciones y aprendizaje; la computación evolutiva es otro. En las simulaciones del sistema nervioso las reglas son en cierta forma el principio mismo de las neuronas, es decir, una activación que se separa y se consolida o debilita dependiendo de las conexiones; el comportamiento al que se aspira es el reconocimiento y el aprendizaje sofisticados de patrones. En el cómputo evolutivo las reglas son típicamente "selección natural" con variaciones debido al cruce, la mutación o ambos. En este caso el comportamiento al que se aspira es uno con capacidad de diseño de soluciones eficientes a problemas complejos y capacidad de adaptar estas soluciones ante un ambiente constantemente cambiante. La evolución biológica es una fuente de inspiración atractiva para tratar estos problemas. En efecto, la evolución un método de búsqueda entre un número enorme de las posibilidades para encontrar "soluciones óptimas". 32 En biología el sistema enorme de posibilidades es el sistema de secuencias genéticas posibles, y las "soluciones deseadas" son los organismos capaces de sobrevivir, adaptarse y de reproducirse en sus ambientes naturales. La evolución se puede también considerar como método para diseñar soluciones innovadoras a los problemas complejos. Por ejemplo, el sistema inmune mamífero es una solución maravillosa desarrollada al problema de los gérmenes que invaden el cuerpo. Desde esta perspectiva, los mecanismos de la evolución pueden inspirar métodos de cómputo para realizar búsquedas. Por supuesto la aptitud de un organismo biológico depende de muchos factores, como por ejemplo si este puede resistir a las características físicas de su ambiente y si puede competir o cooperar con los otros organismos alrededor de ella. Los criterios de aptitud en los organismos cambian continuamente mientras las criaturas se desarrollan, por lo que la evolución está buscando en un sistema que cambia de posibilidades constantemente. Una búsqueda de soluciones ante condiciones en constante cambio es exactamente lo qué se requiere para los programas de “computación adaptiva”. Por otra parte, la evolución es un método de búsqueda masiva en paralelo, es decir que el trabajo que se realiza sobre una especie y a la vez, tal como lo muestra la evolución, cambia millones de especies en paralelo. Desde cierta perspectiva, las reglas bajo las cuales se rige la evolución son notablemente simples. Las especies se desarrollan por medio de la variación aleatoria, ya sea mediante la mutación, la recombinación u otro operador. Luego la selección natural en la cual los más aptos tienden a sobrevivir y reproducirse, les permite propagar así su material genético a las generaciones futuras. Pero a pesar de ser reglas simples se considera que han producido, por lo menos en gran parte, la variedad y complejidad extraordinaria que existe actualmente en la biosfera 3.2 Computación evolutivaxxxv El desarrollo de los algoritmos genéticos como una rama de la inteligencia artificial fue el producto de un proceso en el que diferentes estrategias fueron diseñadas con el enfoque xxxv http://www.redcientifica.com/doc/doc199904260012.html 33 deductivo que se exponía anteriormente. La clave para el desarrollo de estos algoritmos fue sin duda alguna la computación evolutiva. Cuando se habla de computación evolutiva se hace referencia a varias técnicas de resolución de problemas, por lo general bastante complejos, en las que se pretende implementar los procesos naturales de evolución. Bajo el término de Computación evolutiva se engloba a un amplio conjunto de técnicas basadas en la emulación de los procesos naturales de evolución. El mayor logro de esta ciencia en la solución de problemas es el uso de mecanismos de selección de soluciones potenciales y de construcción de nuevos candidatos por recombinación de características de otros ya presentes, de modo parecido a como ocurre en la evolución de los organismos naturales. Es importante aclarar que el propósito principal no es reproducir los fenómenos naturales, más bien aprovechar las ideas generales que se pueden obtener a partir de estos. Efectivamente, en el momento en que se tienen varios candidatos para solución de un problema surge inmediatamente la necesidad de establecer criterios de calidad y de selección, siempre basándose en la idoneidad de la solución. También surge la idea de combinar características de buenas soluciones para obtener otras mejores. Dado que fue en el comportamiento natural donde inicialmente se plantearon problemas de ese tipo, es evidente que al aplicar tales ideas en la resolución de problemas científicos y técnicos, se obtengan procedimientos bastante parecidos a los ya encontrados por la naturaleza tras un largo periodo de adaptación. La computación evolutiva surge a finales de los años 60 cuando John Holland se planteó la posibilidad de incorporar los mecanismos naturales de selección y supervivencia para resolver una gran cantidad de problemas de Inteligencia Artificial que ya habían sido resueltos muy eficientemente por la naturaleza pero que resultaban decepcionantemente inabordables mediante computadoras. Los resultados de sus investigaciones fueron registrados en su libro “Adaptación en sistemas naturales y artificiales”, que con el paso del tiempo ha sido considerado como el punto de arranque de la Computación Evolutiva. Los intereses de Holland y sus colaboradores fueron en principio académicos, buscaban introducir un marco más amplio para relacionar la inteligencia artificial con la intención de 34 resolver ciertos problemas genéricos que constantemente aparecían en dicha disciplina. Al llevar a la práctica las ideas de Holland resultaban, cuando menos, poco eficientes. Sin embargo, a mediados de los 80 con la aparición de computadores de altos recursos y bajo costo el problema cambió por completo. Actualmente las computadoras pueden ser utilizadas para resolver exitosamente cierto tipo de problemas de ingeniería y de las ciencias sociales que anteriormente eran tratados con dificultad. Posiblemente como consecuencia del esfuerzo divulgador de los autores de esta nueva ciencia y debido también a las nuevas posibilidades que se descubrían, el desarrollo de la computación evolutiva a partir de entonces fue espectacular. Figura 3.1 – Subdivisiones de la inteligencia artificial 3.3 Funcionamiento de los algoritmos genéticosxxxvi xxxvi An Introduction to Genetic Algorithms Mitchell Melanie A Bradford Book The MIT Press Cambridge, Massachusetts • London, England Fifth printing, 1999 Inteligencia Inteligencia artificialartificial Enfoque Enfoque inductivoinductivo Enfoque Enfoque DeductivoDeductivo Sistemas Sistemas ExpertosExpertos Computación Computación evolutivaevolutiva Programación Programación genéticagenética Redes Redes NeuronalesNeuronales Co-Evolución Co-Evolución CooperativaCooperativa Algoritmos Algoritmos GenéticosGenéticos 35 Dado un problema claramente definido y una representación de las soluciones posibles en cadenas de bits, el funcionamiento de un algoritmo genético simple puede describirse de la siguiente forma: 1. Se comienza con una población aleatoriamente generada de n cromosomas representados por cadenas de l bits, las cuales son soluciones posibles para el problema. 2. Se calcula la aptitud f(x) de cada cromosoma x en la población. 3. Se repiten los siguientes pasos hasta que han generado n descendientes: a. Seleccionar un par de cromosomas de la generación padre actual, siendo la probabilidad de selección una función de aptitud en aumento. La selección se hace "con el reemplazo", es decir que un mismo cromosoma se puede seleccionar más de una vez para convertirse en padre de la nueva generación. b. La probabilidad Pc, es decir "probabilidad de cruce" o "tasa de cruce", intercambia la pareja en un punto aleatoriamente elegido con una probabilidad uniforme, para formar dos descendientes. Si no ocurre ningún cruce, los dos descendientes son copias exactas de sus padres respectivos. Es necesario tomar en cuenta que aquí la tasa de cruce está definida como la probabilidad que dos padres se intercambien sobre un solo punto. Hay también versiones de algoritmos genéticos con “tráfico de múltiples puntos" en el cual la tasa de cruce para un par de padres es el número de puntos en los cuales ocurre el intercambio. c. Se hace mutar a los descendientes en cada lugar geométrico con la probabilidad Pm, que es la probabilidad de la mutación o la tasa de la mutación, y se colocan los cromosomas alterados en la nueva población. d. Si n es impar, un nuevo miembro de la población puede ser desechado al azar. 4. Se sustituye la población actual por una nueva población. 5. Se repite el proceso a partir del paso 2. Cada repetición de este proceso se llama generación. Un algoritmo genético se repite típicamente de 50 a 500 o más veces. El sistema entero de generaciones se le llama una iteración. Al final de una iteración hay por lo general uno o más cromosomas altamente aptos en la población. Puesto First MIT Press paperback edition, 1998 Copyright © 1996 Massachusetts Institute of Technology 36 que la aleatoriedad desempeña un papel importante en cada iteración, dos iteraciones con diferentes números de semillas aleatoriamente generadas producirán diversos comportamientos. Tanto así que los investigadores de algoritmos genéticos han reportado diferentes promedios estadísticos para un mismo problema, tales como la mejor aptitud encontrada en una iteración o la generación en la que se descubre al individuo con la mejor aptitud. El procedimiento simple descrito es la base para la mayoría de los algoritmos genéticos. Hay un número de detalles que es necesario tomar en cuenta, por ejemplo el tamaño de la población y las probabilidades de cruce y de mutación, el éxito del algoritmo depende muy a menudo en gran parte a estos detalles. Con este ejemplo se describirá más detenidamente el algoritmo simple definido anteriormente. Suponiendo que es l =8, longitud de la cadena; que f(x) es igual a la cantidad de números unos en la secuencia de bits x, esta es una función extremadamente simple de aptitud usada aquí solamente con propósitos ilustrativos. Suponiendo que el tamaño n de la población es igual a 4, que Pc = 0.7 y que Pm = 0.00. La población inicial generada al azar puede ser similar a la tabla 2.1. Realmente los valores típicos de l y n suelen estar entre los 50 y 1000, pero los valores dados para las probabilidades Pc y Pm son bastante comunes. Nombre del Cromosoma Cadena del cromosoma Aptitud A 00000110 2 B 11101110 6 C 00100000 1 D 00110100 3 Tabla 2.1 – Población de genomas aleatoriamente generados Un método común de selección en los algoritmos genéticos es la selección del mas apto, en la cual el número de veces que se espera que un individuo se reproduzca es igual a su aptitud 37 dividida entre la aptitud promedio de toda la población. Esto es equivalente a lo que los biólogos llaman "selección de viabilidad". Un método simple de implementar la selección en base a la aptitud es utilizando el "muestreo de la ruleta" (Goldberg 1989a), que es conceptualmente equivalente a asignar a cada uno de los individuos una rebanada de una rueda circular, donde el tamaño del área es proporcional a la aptitud del individuo. Se hace girar la ruleta y se detiene sobre una rebanada, seleccionando así al individuo correspondiente. En el ejemplo mencionado n = 4, la ruleta se haría girar cuatro veces; las primeras dos vueltas podrían elegir los cromosomas B y D para ser padres, y las segundas dos vueltas pudieron elegir los cromosomas B y C para ser padres. Es posible que A no sea seleccionada es debido a la aleatoriedad. Si la ruleta fuera hecha girar muchas veces, los resultados medios estarían más cerca a los valores previstos. Una vez que seleccionen a un par de padres, con la probabilidad Pc, se cruzan para formar a 2 descendientes. Si no se cruzan, entonces los descendientes son copias exactas de cada padre. En el ejemplo, si los padres B y D se cruzan a partir de la primera posición de bits para formar los descendientes entonces E = 10110100 y F = 01101110. Después, cada descendiente estaría sujeto a la mutación en cada posición geométrica con la probabilidad Pm. Por ejemplo, si el descendiente E es transformado en el sexto lugar geométrico formaría E’ = 10110000, los descendientes F y C no sufrirían ninguna mutación, Pero el descendiente B sería transformado en el primer lugar geométrico para formar B’ = 01101110. La nueva población estaría formada por los cromosomas de la tabla 2.2. Nombre del Cromosoma Cadena del cromosoma Aptitud E’ 10110000 3 F 01101110 5 C 00100000 1 B’ 01101110 5 Tabla 2.2 – Población después de haber evolucionado 38 Es importante recalcar que en la nueva población, a pesar de que la mejor secuencia que tenía aptitud de 6, se perdió, sin embargo la aptitud media incremento de 12/4 a 14/4. La continua iteración de este procedimiento dará eventualmente como resultado una secuencia de solo números 1. 3.4 Usos típicos de los algoritmos genéticosxxxvii Por lo general los algoritmos genéticos son utilizados en problemas de búsqueda, sin embargo es importante definir de manera exacta el término "búsqueda" y compararlo con sus otros significados en la informática. Hay por lo menos tres significados diferentes de la "búsqueda" y estos se describen a continuación. Inicialmente tenemos la búsqueda de datos almacenados, aquí el problema consiste en recuperar eficientemente la información almacenada en una computadora. Por ejemplo en una base de datos grande se puede realizar una búsqueda de los nombres y de las direcciones almacenadas bajo un orden específico. En estos casos al investigar la manera mas conveniente de buscar, la "búsqueda binaria" es un método eficiente para encontrar los registros deseadosxxxviii. También tenemos la búsqueda de trayectorias para alcanzar metas, aquí el problema es encontrar eficientemente una serie de acciones que moverán un sistema desde un estado inicial dado a una meta predeterminada. Esta forma de búsqueda es fundamental para muchos enfoques en la inteligencia artificial. Un ejemplo simple y bastante familiar en los estudios de inteligencia artificial es la búsqueda de una ruta para desplazarse. Un sistema requiere encontrar una ruta para desplazarse de un punto a otro. A lo largo del recorrido muchas decisiones son necesarias para finalmente encontrar el destino, la solución es el conjunto de decisiones que definen la ruta a utilizar. A cada una de las posibles decisiones tomadas se le puede llamar un movimiento. xxxvii GENETIC ALGORITHMS AND TRADITIONAL SEARCH METHODS – Melanie Mitchell xxxviii Data Structures and Algorithms II Lecture 3: String Search Algorithms http://www.macs.hw.ac.uk/~alison/alg/lectures/l3.pdf 39 Los algoritmos de búsqueda discutidos en la mayoría de textos de inteligencia artificial, son métodos para encontrar eficientemente la mejor o, así como en este caso, más corta trayectoria del estado inicial al estado final. Los algoritmos típicos son "búsqueda de primera profundidad", "rama y límite," y "A *"xxxix, los cuales no serán explicados puesto que están fuera del contexto de este documento. Finalmente tenemos la búsqueda de soluciones, la cual es una clase más general de búsqueda que la "búsqueda de trayectorias para alcanzar metas". La idea es encontrar eficientemente la solución a un problema en un espacio más grande de soluciones posibles. En especial este tipo de problemas son los que comúnmente se resuelven implementando algoritmos genéticos. Existe una clara diferencia entre la primera clase de búsquedas y las otras dos. En el primer caso se refiere a los problemas en los cuales se requiere encontrar un dato o alguna secuencia especifica en una colección de información explícitamente almacenada. En los siguientes dos tipos de búsqueda, la información que se requiere no se encuentra explícitamente almacenada. En realidad se crean las soluciones posibles mientras el proceso de la búsqueda se realiza. Por ejemplo, los métodos de búsqueda utilizados en inteligencia artificial para solucionar problemas de trayectorias no parten de un árbol completo de búsqueda en el que todos los nodos, que en este caso serían todos los movimientos posibles, están previamente almacenados en memoria. Para la mayoría de los problemas de este tipo hay demasiados nodos posibles en el árbol para almacenarlos todos. Mas bien, el árbol de búsqueda se elabora gradualmente de manera que depende del algoritmo particular y la meta es encontrar una solución óptima o de alta calidad, examinando solamente una porción pequeña del árbol. Asimismo, al buscar un espacio de soluciones posibles con un algoritmo genético, no todas las soluciones posibles se formulan y se evalúan inicialmente; En realidad el algoritmo es un método para encontrar soluciones óptimas o aceptables examinando solamente una fracción pequeña de los candidatos posibles. xxxix A parallel depth first search branch and bound algorithm for the quadratic assignment problem – Bernard Mans, Thierry Mautor and Catherine Roucairol (Jan 18 1994) 40 La búsqueda de soluciones incluye a la búsqueda de trayectorias, puesto que una trayectoria a través de un árbol de búsqueda se puede codificar como una solución posible. Para el problema del desplazamiento en una ciudad, las soluciones posibles podrían ser listas de movimientos del estado inicial a un cierto otro estado, pero en este caso seria correcto solamente si el estado final es la meta. Sin embargo, muchas búsquedas de trayectorias son resueltas mejor por las técnicas de inteligencia artificial utilizando árboles binarios, en los que soluciones parciales pueden ser evaluadas, ya que por medio de las técnicas de algoritmos genéticos las soluciones posibles completas deben ser generadas antes de que puedan ser evaluadas. Es importante tener en cuenta que los métodos normales de búsqueda por árboles de inteligencia artificial no pueden ser aplicados siempre. No todos los problemas requieren encontrar una trayectoria de un estado inicial a una meta. Realmente muchas soluciones buscadas tienden a cambiar conforme nuevas alternativas son encontradas y en estas búsquedas no es de interés la forma en que se obtiene la mejor alternativa. Los algoritmos genéticos ofrecen un método general para solucionar las búsquedas de soluciones así como otras técnicas inspiradas en la computación evolutiva. En términos generales se pueden resumir de la siguiente manera. 1. Se elije al azar una solución posible, codificada como cadena de bits. Y se denomina a esta cadena “solución actual”. 2. Sistemáticamente se altera por mutación cada bit en la cadena, empezando de izquierda a derecha y uno a la vez, registrando la aptitud de las cadenas mutantes que resultan. 3. Si cualquiera de los resultados de la mutación muestran un aumento de la aptitud, entonces se asigna como nueva “solución actual” a la cadena que muestre la mejor aptitud. 4. Si no hay aumento de la aptitud, entonces se mantiene la cadena de “solución actual” y se regresa al paso 1. Si no, se pasa al paso 2 con un nuevo “solución actual”. 5. Cuando un número necesario de evaluaciones de aptitud del sistema han sido realizadas, se selecciona como resultado la cadena con la mejor aptitud encontrada. 41 La aplicación de este simple algoritmo será discutido en el siguiente capítulo, en el cual se analizarán las circunstancias en las que este puede desarrollarse de manera optima. En la inteligencia artificial tales métodos generales que pueden trabajar en una gran variedad de problemas, se les llama los métodos débiles para distinguirlos de los métodos fuertes diseñados especialmente para trabajar en problemas específicos. Todas las búsquedas de soluciones generan inicialmente un conjunto de soluciones posibles que dentro del algoritmo genético es la población inicial, luego evalúan las soluciones posibles según algunos criterios de aptitud, decide en base de esta evaluación cuales candidatos serán almacenados y cuales desechados. Finalmente se producen variantes usando una cierta clase de operadores de mutación en los candidatos sobrevivientes. 3.5 Paralelismo en los algoritmos genéticos xl Aunque los algoritmos genéticos pueden ser descritos de forma simple y programados rápidamente, su comportamiento puede ser complicado y todavía existen diferentes opiniones sobre cómo trabajan de de forma optima y para qué tipos de problemas es posible adecuarlos. Muchos estudios se han realizado en los fundamentos teóricos de los algoritmos genéticos, pero tradicionalmente se asume que, en un nivel muy general, un algoritmo genético funciona descubriendo, acentuando, y recombinado bloques de valores de manera paralela. La idea en si consiste en que las mejores soluciones están compuestas por bloques que combinando sus valores por segmentos forman soluciones eficientes y por tanto son mas aptos dentro de las secuencias a las que pertenecen. Holland introdujo la noción de esquemas en 1975 para formalizar la noción informal de los denominados "bloques de edificio". Un esquema es un sistema de cadenas de bits que se pueden describir por una plantilla compuesta de unos, ceros y asteriscos, los asteriscos que representan datos indiferentes. Por ejemplo, el esquema H = 1 * * * * 1 representa el sistema de todas las xl Genetic Algorithms Computer programs that "evolve" in ways that resemble natural selection can solve complex problems even their creators do not fully understand by John H. Holland - http://www.econ.iastate.edu/tesfatsi/holland.GAIntro.htm 42 cadenas de 6 bits que comiencen y terminen con 1. Las secuencias que caben esta plantilla, por ejemplo 100111 y 110011 forman parte del esquema H. Este esquema contiene dos bits definidos lo que es equivalente a decir de orden 2. Es importante aclarar que no cada subconjunto posible del sistema de cadenas de bits con longitud x se puede describir como un esquema; de hecho, la gran mayoría no lo son. Hay 2x cadenas posibles de longitud x, por lo que los subconjuntos posibles de secuencia son 22x, pero hay solamente 3x esquemas posibles. Sin embargo, un principio fundamental en la teoría tradicional de algoritmos genéticos, es que los esquemas son en si los “bloques de edificio” que el algoritmo puede procesar con eficacia bajo los operadores de selección, como por ejemplo la mutación y lo conocido como crossover. Estas definiciones tienen como propósito simplificar los procesos del algoritmo genético, pues no se operan directamente las cadenas de bits sino los esquemas, Cualquier cadena de bits dada de longitud x es un caso de 2x esquemas diferentes. Por ejemplo, la secuencia 11 es un caso del **, es decir forma parte de las cuatro cadenas de bits posibles de longitud 2. Pero a su vez pertenece al esquema, * 1, 1 *, y al esquema 11 que contiene únicamente la secuencia, 11. Entonces cualquier población dada de n cadenas de bits puede contener casos entre 2x y nx2x esquemas posibles. Si todas las secuencias son idénticas, entonces hay casos de exactamente 2x esquemas diferentes; si no, el número es menor o igual a nx2x. Esto significa que, en una generación dada, mientras el algoritmo genético está evaluando explícitamente la aptitud de las n secuencias en la población, él realmente está estimando implícitamente la aptitud media de un número mucho más grande esquemas, donde la aptitud media de ese esquema se define como la aptitud media de todos los casos posibles de ese esquema. Por ejemplo, en una población de n secuencias aleatoriamente generadas, como promedio la mitad de las secuencias serán casos del esquema 1***··· * y la otra mitad serán casos de 0 ***···*. Las evaluaciones de aproximadamente n/2 secuencias que son casos de 1***··· * dan un estimado de la aptitud promedio de ese esquema, esto es una estimación porque los casos evaluados adentro una población son solamente una muestra pequeña de todos los casos posibles. Así como los esquemas no son representados ni son evaluados explícitamente por el algoritmo 43 genético, las estimaciones de la aptitud promedio del esquema no son calculadas ni son almacenadas explícitamente. Sin embargo, el comportamiento del algoritmo, en términos del aumento y disminución del número de casos en los esquemas dados de la población, puede ser descrito como si realmente calculara y almacenara estos promedios. 3.6 Operación de los esquemas en la solución de problemasxli En la solución de problemas computacionales se utiliza como base la noción de los "esquemas" y se hace evidente su importancia para los algoritmos genéticos. El propósito original de John Holland para desarrollar los algoritmos genéticos era construir un marco teórico para la adaptación según se ve en la naturaleza y aplicarlo al diseño de sistemas artificiales adaptivos. Según Holland, un sistema adaptivo debe persistentemente identificar, examinar e incorporar las características estructurales de la teoría evolutiva para desempeñarse óptimamente en un ambiente específico. Los esquemas están diseñados para ser una formalización de tales características estructurales. En el contexto de la genética, los esquemas corresponden a las agrupaciones de genes que en conjunto efectúan una cierta adaptación en un organismo; la evolución descubre y propaga tales agrupaciones. Por supuesto, la adaptación es posible solamente en un mundo en el cual haya un ambiente con una estructura que pueda ser descubierta y explotada. La adaptación es imposible en un ambiente que carece de cambios o de cierto grado de aleatoriedad. El análisis de los esquemas de Holland demostró que un algoritmo genético, al mismo tiempo en que explícitamente calcula la aptitud de los miembros de una población n, estima implícitamente la aptitud promedio de un número mucho más grande de esquemas, esto se da expresamente al calcular las aptitudes promedio de los casos observados dentro de esquemas en la población. Hace esto sin necesitar de memoria o tiempo adicional de cómputo, únicamente el necesario para procesar los n miembros de la población. xli Muhlenbein, H, 1992, “How genetic algorithms really work: I. mutation and hill-climbing.” In Parallel Problem Solving from Nature 2, Manner, R & Manderick, B, 44 Holland llamaba a esto "paralelismo implícito". Por supuesto que la exactitud de estas estimaciones esta claramente sujeta a las variaciones de los esquemas en cuestión. El análisis de Holland también demostró que para los esquemas cuya aptitud se calcula sobre el promedio reciben un alto número de "ensayos", es decir, numero de casos en la población. El teorema del esquema se ha interpretado para implicar eso específicamente, en un algoritmo genético, los esquemas cortos y de “bajo orden” cuya aptitud media esta sobre el valor promedio recibirá un número exponencial de muestras a lo largo del tiempo. El análisis de Holland sugiere que la selección se enfoque, de forma incremental, en buscar en los subconjuntos con aptitud estimada por encima del promedio. Estos estarán definidos por los esquemas observados con aptitud por encima del promedio. Mientras tanto, mediante el cruce los "bloques de edificio" de alta capacidad de adaptación se unen en una misma secuencia para crear otras secuencias de una aptitud cada vez más alta. La mutación desempeña un papel semejante a una póliza de seguro, cerciorándose de que la diversidad genética nunca se pierda completamente en cualquier lugar geométrico. Holland enmarca la adaptación como tensión entre la "exploración", es decir la búsqueda de nuevas y útiles adaptaciones, y la "explotación", que es el uso y la propagación de estas adaptaciones. La tensión se hace visible puesto que cualquier movimiento enfocado en la exploración, es decir en la prueba de nuevos esquemas no vistos o en los esquemas que de casos vistos que han probado tener hasta cierto punto baja aptitud, reducen en la misma medida la explotación de esquemas previamente probados y de alta adaptación. Para cualquier sistema o población que deba de hacer frente a ambientes con un cierto grado de imprevisión, un equilibrio óptimo entre la exploración y la explotación deben ser encontrados. El sistema tiene que mantenerse continuamente probando nuevas posibilidades, de lo contrario se podría “sobre adaptar” y volverse completamente inflexible ante nuevos cambios, pero a su vez tiene que incorporar y utilizar continuamente sus experiencias previas como guía para el comportamiento futuro. Los algoritmos genéticos originales propuestos por Holland tenían un "plan de adaptación" para lograr un equilibrio apropiado entre la exploración y la explotación en un sistema adaptivo. El 45 análisis de esquemas demostró que, dadas ciertas condiciones, el algoritmo genético alcanza de hecho un equilibrio casi óptimo. Los argumentos para esto se basan en secuencias binarias y el cruce de un solo punto. Los esquemas útiles, según lo definido por Holland, son una clase de los subconjuntos de secuencias binarias de alta adaptación que evitan la interrupción significativa mediante el cruce y la mutación y pueden sobrevivir así para re-combinarse con otros esquemas. 3.7 Cuando utilizar algoritmos genéticosxlii En los diferentes estudios documentados de los algoritmos genéticos se pueden encontrar una gran cantidad de usos acertados, pero hay también muchos casos en los cuales estos algoritmos se desempeñan mal. En muchas ocasiones se ha intentado determinar bajo que circunstancias de uso potencial particular, un algoritmo genético es buen método a utilizar, sin embargo, no existe una respuesta rigurosa. Muchos investigadores están de acuerdo con las nociones que es conveniente utilizarlos si el espacio en el que se buscará es grande o si se sabe que no es perfectamente liso y uniforme, como por ejemplo en una única curva continua. En caso de que el espacio de búsqueda no esta bien definido o si la función de aptitud es ruidosa, si la tarea no requiere encontrar el grado óptimo global o en caso es suficiente encontrar rápidamente una solución relativamente buena, un algoritmo genético tendrá muy buenas probabilidades de ser competitivo o de sobrepasar otros métodos "débiles", es decir los métodos que no utilizan conocimientos específicos del espacio en su procedimiento de la búsqueda. Si un espacio de búsqueda no es grande, entonces puede ser recorrido exhaustivamente y finalmente se puede garantizar que se ha encontrado la mejor solución posible, mientras que un algoritmo genético podría converger en un grado óptimo local en lugar de encontrar la mejor solución global. Si el espacio es liso o uniforme, un algoritmo enfocado al gradiente tal como el xlii An Introduction to Genetic Algorithms Mitchell Melanie A Bradford Book The MIT Press Cambridge, Massachusetts • London, England Fifth printing, 1999 First MIT Press paperback edition, 1998 Copyright © 1996 Massachusetts Institute of Technology 46 de la pendiente mas inclinada será mucho más eficiente que un algoritmo genético al explotar la gráfica de aptitudes para las soluciones posibles. Si el espacio esta bien definido, al igual que el espacio para el conocido problema del vendedor que viaja por ejemplo, los métodos de búsqueda que usan la heurística de dominios específicos se pueden diseñar a menudo de forma que superan cualquier método del propósito general tal como lo son los algoritmos genéticos. Si la función de aptitud es ruidosa, es decir que implica evaluar soluciones de medidas de un proceso real, un método de búsqueda que examina una posible solución a la vez, tal como los algoritmos basados en las pendientes se puede desviar de forma irrecuperable por el ruido. Sin embargo un algoritmo genético tiene dificultades para mantener un desempeño estable ante la presencia de ruido en cantidades pequeñas, esto se debe a que trabaja en base a información estadística de aptitud que se acumula sobre muchas generaciones. Estas guías generales, por supuesto, no predicen estrictamente cuando un algoritmo genético será un método eficaz de búsqueda y competitivo con otros procedimientos conocidos. El funcionamiento de un algoritmo genético dependerá mucho de detalles tales como el método para codificar las soluciones posibles, los operadores, los ajustes de parámetros y el criterio particular para el éxito de adaptarse. 3.8 Algunos ejemplos específicos de algoritmos genéticos xliii Mientras el poder de la evolución gana reconocimiento cada vez más generalizado, los algoritmos genéticos se utilizan para abordar una amplia variedad de problemas en un conjunto xliii Algoritmos genéticos y computación evolutiva Adam Marczyk 2004 http://the-geek.org/docs/algen/algen.html#key-58 47 de campos sumamente diverso, demostrando claramente su capacidad y su potencial. Esta sección analizará algunos de los usos más notables en los que han tomado parte. 3.8.1 Acústica Sato et al. 2002xlivutilizaron algoritmos genéticos para diseñar una sala de conciertos con propiedades acústicas óptimas, maximizando la calidad del sonido para la audiencia, para el director y para los músicos del escenario. Esta tarea implica la optimización simultánea de múltiples variables. Comenzando con una sala con forma de caja de zapatos, el AG de los autores produjo dos soluciones no dominadas, ambas descritas como “con forma de hoja” (p. 526). Los autores afirman que estas soluciones tienen proporciones similares al Grosser Musikvereinsaal de Viena, el cual está considerado generalmente como una de las mejores -si no la mejor- salas de conciertos del mundo, en términos de propiedades acústicas. Porto, Fogel y Fogel 1995xlv utilizaron programación evolutiva para adiestrar a redes neuronales para distinguir entre reflexiones sonoras desde distintos tipos de objetos: esferas metálicas hechas por el hombre, montañas submarinas, peces y plantas, y ruido aleatorio de fondo. Tras 500 generaciones, la mejor red neuronal que evolucionó tenía una probabilidad de clasificación correcta que iba desde el 94% al 98%, y una probabilidad de clasificación errónea entre un 7,4% y un 1,5%, que son “probabilidades razonables de detección y falsa alarma” (p. 21). Esta red evolucionada igualó las prestaciones de otra red desarrollada mediante recocido simulado, y superó consistentemente a redes entrenadas mediante propagación hacia atrás, las cuales “se atascaban repetidamente en conjuntos de pesos subóptimos que no producían resultados satisfactorios” (p. 21). En contraste, ambos métodos estocásticos demostraron su capacidad para superar estos óptimos locales y producir redes más pequeñas, efectivas y robustas; pero los autores sugieren que el algoritmo evolutivo, a diferencia del recocido simulado, opera sobre una xliv Sato, S., K. Otori, A. Takizawa, H. Sakai, Y. Ando y H. Kawamura. ``Applying genetic algorithms to the optimum design of a concert hall.'' Journal of Sound and Vibration, vol.258, no.3, p. 517-526 (2002) xlv Porto, Vincent, David Fogel y Lawrence Fogel. ``Alternative neural network training methods.'' IEEE Expert, vol.10, no.3, p.16-22 (junio de 1995). 48 población, y por tanto se beneficia de la información global sobre el espacio de búsqueda, conduciendo potencialmente hacia un rendimiento