Download Algoritmos Genéticos: Herramientas de Inteligencia Artificial con su
Document related concepts
Transcript
Entrevista al Dr. Ángel Kuri Morales del CIC-IPN Algoritmos Genéticos: Herramientas de Inteligencia Artificial con su Propia Evolución Verónica Hernández López Los algoritmos genéticos son un resultado de los avances de la computación y de la genética. Son herramientas de la inteligencia artificial porque aprenden simulando parcialmente los mecanismos de la evolución. Su característica principal es su eficacia para optimizar casi cualquier problema. En el Laboratorio de Inteligencia Artificial del Centro de Investigación en Computación (CIC) del Instituto Politécnico Nacional (IPN) se desarrolla el proyecto Reconocimiento de patrones utilizando un algoritmo genético universal, a cargo del doctor Ángel Kuri Morales, quien presentó recientemente su libro “A Comprehensive Approach to Genetic Algorithms in Optimization and Learning” (“Enfoque Integral de Algoritmos Genéticos en la Optimización y Aprendizaje”), que es parte de la colección Ciencia de la Computación que editan conjuntamente el CIC y la Dirección de Publicaciones y Materiales Educativos del IPN. El investigador también se desempeña como subdirector de Investigación Aplicada del CIC y desde su tesis doctoral (“Genetic Automata and Information System Losslessness”, 1985-1987) se dedica a este campo, aunque admite que en aquel entonces era tan nuevo que ni siquiera había una amplia difusión de los libros acerca del tema. No obstante, trabajó sobre algunas cuestiones ya existentes pero que desconocía- e inventó otras, ahora incluidas en su publicación. Computación Evolutiva Los algoritmos genéticos son parte de la Computación Evolutiva, que según explicó el doctor Kuri “simula el proceso de selección natural desde un punto de vista neodarwiniano. Esto es, cuando Darwin elaboró su teoría de la evolución, se dio cuenta que las especies evolucionaban poco a poco. Eso lo hizo concebir que la diferenciación de las especies se daba por pequeños cambios accidentales que, vistos después de mucho tiempo, parecían tener un propósito específico. “En su época fue muy revolucionario porque iba contra las enseñanzas bíblicas, que señalaban que la creación se hizo por obra de Dios en siete días. Darwin analizó las características de los antecesores de las especies e infirió que se trataba de un proceso evolutivo. En esa época no se conocía el mecanismo de la herencia desde el punto de vista molecular. Este se descubrió mucho después, en los años 50 de este siglo, cuando Watson y Crick encontraron la forma helicoidal del DNA. Después de esto, se entendió mejor que los cambios ocurrían porque en el proceso de copia de la información -contenida en los núcleos de las células- a veces hay errores. Unos se deben a que el mecanismo de copia no es perfecto y otros a que hay agentes exógenos que producen cambios en los genes. “Finalmente, la probabilidad de falla en el proceso de copia de la información genética es bajísima. Lo que llama la atención no es que haya errores sino que sean tan pocos. Si nosotros tomamos la perspectiva de que un ser vivo es la respuesta a los problemas que plantea el medio ambiente, aquel es un diseño de la naturaleza que pretende resolver los problemas de su entorno. Un ejemplo es el del cuerpo de los pingüinos: el volumen de estos animales les permite nadar con muy baja resistencia y a la vez almacenar la grasa en su cuerpo. Este parece ser el mejor diseño. Pareciera como si un ingeniero lo hubiera creado. Pero tal vez el más interesante de todos los diseños lo constituyan los seres humanos, quienes tienen en su cerebro una caja de simulación que les permite representar eventos que todavía no suceden. Eso es lo que le otorga su principal ventaja evolutiva al ser pensante. A diferencia de cualquier otro animal, puede tomar acciones ante eventos del futuro. “Más tarde, a alguien se le ocurrió que si simulaba eso en la computadora podía diseñar aplicaciones en, por ejemplo, la ingeniería, la economía, la toma de decisiones financieras, etcétera. Un algoritmo genético trabaja de esa forma, con conjuntos de individuos y propone soluciones distintas. Simulamos que la representación, frecuentemente binaria, corresponde a los genes del individuo, su ADN, y su interpretación –como números, por ejemplo- a las características observables –el color de sus ojos, su estatura, etcétera. A los individuos, los describimos como cadenas de números y un conjunto de éstas forman una población. Así se generan infinidad de individuos y representamos lo que hace la naturaleza. Luego, observamos las características que constituyen a las mejores soluciones y calificamos a los individuos –de manera análoga a la forma en que a naturaleza “califica” a los individuos más aptos permitiéndoles sobrevivir con mayor probabilidad. De la población escogemos a los individuos más sobresalientes y seleccionamos un subconjunto de ellos. De esta forma imitamos el procedimiento de selección natural. “Después la naturaleza creó el sexo. El sexo es un invento maravilloso de la evolución, a través del cual los genes de ambos padres se combinan para rápidamente privilegiar las características que son más adecuadas para que el individuo sobreviva en su entorno. Si analizamos la evolución de los seres vivos, durante la mayor parte de su historia los organismos fueron asexuales y evolucionaban lentamente. Cuando apareció el sexo la evolución se hizo mucho más rápida. En computación hacemos lo mismo. De los individuos tomamos una cantidad determinada de características que van a ser del padre y otras tantas de la madre y se intercambian, de tal suerte que estamos haciendo lo mismo que los seres vivos. Nosotros tenemos 50% de la madre y el otro 50 del padre, pero somos distintos de los dos. Eso también se hace con algoritmos genéticos. “Finalmente, igual que en la naturaleza, se consideran las mutaciones. Contamos con individuos nuevos con las características de los mejores, pero mezclados y además con ciertas mutaciones para explorar nuevas características. En la computadora tenemos la ventaja de que podemos hacer eso varias miles o millones de veces por segundo. Lo que a la naturaleza le toma millones de años, nosotros lo hacemos en unos segundos. El resultado es que tengo una población de individuos y entre ellos, uno va a ser el mejor. Como por arte de magia resolvemos el problema de la manera más económica posible porque en cada generación hacemos un proceso de selección, cruzamiento y mutación, para finalmente encontrar al mejor individuo. “Por ejemplo, en el CIC, un estudiante de maestría hizo su tesis sobre el tema de las estructuras para construcción utilizando algoritmos genéticos y encontró que son casi 40% más baratas de las que se diseñan sin tomar en cuenta a éstos últimos”. Todo Empezó en los 60… ¿Desde cuándo se usan los algoritmos genéticos? ¿Desde cuándo existen? Al respecto, el doctor Kuri refirió: “En los 60, dos investigadores alemanes -Shwefel y Rechenberg- inventaron las estrategias evolutivas, con las que diseñaron elementos de avión. Ellos trabajaron la evolución, pero sin tomar en consideración la parte genética, sin hacer mezclas de ese tipo. Simple y sencillamente tomaron en cuenta la herencia y la mutación. Tuvieron mucho éxito pero como su trabajo tenía implicaciones militares, se clasificó la tecnología y no se alentó la publicación del tema. Una década después, el estadounidense John Holland se aplicó a la misma idea, pero sí consideró la parte genética. Fue precisamente él quien los bautizó como algoritmos genéticos. “El auge de esta técnica empezó a principios de los 80 y realmente se reconoció como una cuestión muy útil a principios de los 90. A partir de entonces ha tenido una explosión fantástica; según el investigador mexicano Carlos Coello se publican alrededor de 100 artículos diarios sobre el tema. Parece exagerado, pero quiere decir que muchísima gente se dedica a esto”. Sí Funcionan, pero ¿Siempre? El investigador politécnico, cuya especialidad es en electrónica digital, diseño lógico, arquitectura de máquinas, microprocesadores, sistemas de telecomunicaciones digitales y, por supuesto, en algoritmos genéticos y su aplicación a la inteligencia artificial, señaló que los científicos están convencidos de que los algoritmos genéticos sí funcionan. Ejemplos existen en diversos países del mundo y en México. Sin embargo, argumentó que es necesario saber en qué casos trabajan y cómo hacer para que siempre sean funcionales. “Necesitamos detectar qué problemas hay en este sistema evolutivo para luego tratar de corregirlos. Como gente de computación, me interesa dar con un programa que sea aplicable a la gran mayoría de los problemas. Así tiene que ser; no puedo ofrecer un sistema que a veces realice bien su función y otras no. “Los algoritmos genéticos se catalogan dentro de las herramientas de la inteligencia artificial porque el algoritmo aprende. Pero, hay que quitarse de la mente el significado antropocéntrico que se tiene de la palabra “aprender”: el de abrir un libro y estudiar. La naturaleza aprende, eso es la evolución. Nosotros somos un producto muy acabado de un aprendizaje de muchos millones de años. Así lo hace un algoritmo genético: aprende simulando la evolución. Claro que es una simulación parcial, ya que hay muchos elementos no considerados porque no son necesarios ni útiles en el presente contexto. “Tal es el caso de las cadenas genéticas que son diploides. Esto es, cadenas dobles que permiten que los caracteres llamados recesivos se manifiesten en el individuo solo si ambos progenitores los presentan. ¿Para qué le sirve eso a la naturaleza? para que aquellas cosas que fueron buenas en algún momento para la especie, no se olviden. No obstante, esto en algoritmos genéticos no se usa normalmente porque no lo necesitamos. A nosotros no nos interesa recordar lo que sucedió con las anteriores generaciones porque en la computadora puedo trabajar con 100 millones de generaciones en tiempos cortos”. Sus Aplicaciones son muy Vastas Los algoritmos genéticos han sido aplicados con éxito en infinidad de problemas, actuando como un proceso de cómputo que emula la forma de proceder de la evolución genética y opera sobre una población de individuos que representan las soluciones potenciales a un determinado problema. Al respecto, el doctor Kuri puntualizó: “Los algoritmos genéticos son herramientas para optimizar casi cualquier problema, ya que éstos pueden trabajar con base en la descripción del medio ambiente, lo cual permite resolver muchos problemas de optimización. “Una de las áreas donde se aplican es en el aprendizaje automático. En inteligencia artificial se conocen como sistemas expertos o programas para la resolución de problemas a los que se cuestiona sobre lo qué hay que hacer y da respuestas. Hay ejemplos de sistemas expertos, por ejemplo, en medicina, abogacía, etc. La mayor parte de los sistemas expertos no incorporan todas las reglas ni todo el conocimiento. Queremos que nuevas reglas se vayan descubriendo ¿y cómo las descubrimos? con algoritmos genéticos”. El doctor Kuri ha publicado cerca de 18 trabajos respecto a los algoritmos genéticos. Uno de los primeros fue para hacer modelación de sistemas económicos y predicciones en la economía mexicana: “Aunque los sistemas económicos son caóticos -no existen reglas claras para ellos- sólo exhiben esa característica caótica temporalmente. Hay segmentos de tiempo donde sí se comportan de manera más o menos razonable. Por ello, es posible hacer análisis en períodos de estabilidad y lograr predicciones. “Otro de los campos en los que opera esta herramienta es en el reconocimiento de formas, algo difícil y complicado para la computadora. Un estudiante del CIC está haciendo su doctorado sobre algoritmos genéticos, lo cual lo está conduciendo a resolver un problema de reconocimiento de rostros. “Por otra parte, tenemos en las telecomunicaciones un ámbito más sofisticado en el que también son aplicables. Cuando enviamos información de un continente a otro utilizamos satélites que funcionan como espejos. Esto es así porque las señales de alta frecuencia atraviesan la ionosfera y hay que reflejarlas. Poner un satélite en órbita es muy costoso, por lo que es importante optimizar el uso de los canales de comunicación. Si quiero hacer un uso eficiente de éstos, envío información y no solamente datos. Aunque en realidad mando los dos, busco que los últimos vayan plenos de información. La compresión de datos se puede realizar con los algoritmos genéticos, ya que éstos aprenden la estructura de los mensajes y me permiten transmitir más información por el mismo canal. “Otro problema es que en Internet, las imágenes tardan en llegar porque la información no se comprime al máximo. Podríamos usar algoritmos genéticos para comprimirla del lado del transmisor y descomprimirla de lado del receptor. Usted vería que transferencia de imágenes es mucho más rápida. En eso se está trabajando. “Otra cuestión que se usa mucho en computación son las redes neuronales que pretenden simular la estructura del cerebro. Es un mecanismo interesante que aprende también, pero hay que entrenarlo. A las redes neuronales pueden entrenarlas los algoritmos genéticos para que aprendan mejor. Así hacemos inteligencia artificial, pero no directamente. Las redes neuronales se usan en el sector financiero, en análisis de auditorías o en análisis de riesgo financiero, por ejemplo. Pero su desempeño es mejor cuando las entrenan los algoritmos genéticos. También Tienen Limitaciones… Sin embargo, el doctor Kuri admitió que: “Los algoritmos genéticos no son una panacea. Aunque los casos en los que no funcionan bien son pocos es muy importante identificar cuáles son sus limitaciones y para lograr esto hay que entenderlos. “Cuando los algoritmos genéticos encuentran las soluciones lo hacen muy rápidamente y en problemas muy complicados, pero se parecen a los humanos en que no necesariamente hallan cuál es la mejor. ¿Qué hacemos nosotros? Probablemente tomamos la decisión más rápida o lo que más se aproxima a lo mejor que pudimos haber hecho. Ese es el caso de los algoritmos genéticos; no encuentran siempre la mejor solución ¿cómo sabemos cuál es la mejor solución en un caso inesperado? Generalmente no lo sabemos, pero sí podemos encontrar una suficientemente buena. Así sucede con el algoritmo genético, que rara vez no encuentra una solución cercana a lo óptimo”. Otro aspecto que interviene en el funcionamiento de los algoritmos genéticos, indicó el investigador del CIC es el de los problemas “engañosos”. Hay información en los genes que pueden llevar al algoritmo hacia una solución errónea. El algoritmo puede engañarse, es decir, el algoritmo “cree” que va muy bien porque que cierta información genética lo lleva hacia un destino equivocado. De ahí la tarea de los especialistas para que esto no pase. En los ejemplos que he mencionado no hay engaño. Son problemas muy específicos aquellos en donde se presenta esta situación. No son problemas que ocurran frecuentemente en la vida real”. Además, el doctor Kuri explicó que hay muchas variaciones de algoritmos genéticos. “Por ejemplo, con el elitismo hacemos que el mejor individuo de toda la progenie nunca muera. En algoritmos genéticos esto se puede hacer; en la naturaleza no. O puedo conservar al mejor individuo y hacer cruzamientos “pangenéticos”. Esto es, se toma un padre y se hace que tenga miles de descendientes. De manera normal, eso no se lleva a cabo porque típicamente se toman parejas. Pero yo puedo encontrar a un individuo que esparza su herencia genética en toda la población. El que haya muchas variantes es lo que hace interesante el estudio de los algoritmos genéticos. Podemos hacer que las poblaciones sean grandes o chicas, que se reproduzcan mucho o poco, que muten en gran o poca cantidad”. Enfoque Integral y el Trabajo del CIC Respecto a su especialidad, el doctor Kuri publicó recientemente el libro “A Comprehensive Approach to Genetic Algorithms in Optimization and Learning” (“Enfoque Integral de Algoritmos Genéticos en la Optimización y Aprendizaje”), dividido en dos volúmenes. El primero que se presentó es acerca de lo qué son los algoritmos genéticos, cómo y por qué funcionan: “La teoría matemática de los algoritmos genéticos es muy incipiente porque se trata de un fenómeno muy complejo, al igual que los de la herencia y la selección natural; además de ser muy complicada porque es probabilística. Para su manejo adecuado, es conveniente conocer una serie de disciplinas como la estadística, la teoría de la información y de la computabilidad, entre otras”. Su autor dijo que con esta publicación da al lector la posibilidad de encontrar lo que necesita para entender lo que son los algoritmos genéticos, aunque no sepa estadística o teoría de la información; y está dirigida a los estudiantes de los últimos semestres de la carrera de computación y de los primeros años de posgrado. Respecto al trabajo que se realiza en México en este campo, el doctor Kuri expresó que en las diferentes instituciones de educación superior se llevan a cabo investigaciones, algunas en la cuestión práctica, otras en la teórica. Por ejemplo, en el ITAM, el Tecnológico de Monterrey, en Nuevo León; la Universidad de Sonora, la UNAM y por supuesto el IPN. Paralelamente, la ingeniería nacional está aplicando estas herramientas, pero en general “los empresarios mexicanos son muy cautelosos y tienden a no arriesgarse con tecnologías de vanguardia. Primero, porque en México se diseña poco y después porque algunos empresarios prefieren a comprar cosas ya probadas aunque hayan sido diseñadas con otro tipo de usuarios en mente: son consumidores, más que generadores, de tecnología. “El CIC tiene como meta producir nuestra propia ciencia y como consecuencia nuestra propia tecnología. Solamente así podemos ser independientes. Mientras no seamos dueños de nuestra tecnología, difícilmente podemos aspirar a una verdadera independencia. Si usted ve la historia, en todos los casos, las culturas hegemónicas son dueñas de la tecnología: en el siglo pasado, por ejemplo, los ingleses y en éste, los americanos. Toma tiempo. Este es un esfuerzo a mediano plazo. Por decreto no podemos cambiar la mentalidad de la sociedad mexicana, ésta y el grupo científico tienen que convencerse de que pueden asumir su compromiso social. “Por eso mi libro no está escrito en español, sino en inglés. Simplemente me gustaría que lo leyera más gente. Es una meta ambiciosa, ya que su distribución deberá darse en el IPN y a nivel internacional. El segundo libro está en proceso y trata sobre aplicaciones”. Sin embargo, el doctor Kuri Morales está por finalizar, junto con José Galaviz, Algoritmos Genéticos, un nuevo libro del IPN, en español. Continuará la evolución… ¿Los algoritmos genéticos van a seguir su evolución? El doctor Kuri asegura que así ocurrirá porque son muy nuevos en una ciencia como la computación, muy joven de por sí: “Los algoritmos genéticos y las redes neuronales, paradigmas inspirados ambos en analogías con la naturaleza, se han hecho posibles porque se ha abaratado la computadora. Si hace 15 años yo hubiera planteado el paradigma evolutivo, éste hubiera sido prácticamente incosteable, porque cuando se simulan 10 mil generaciones ocupo minutos de cómputo. En el tiempo en que estudié el doctorado, el minuto de CPU valía miles de dólares y me lo hubieran negado. “Los algoritmos genéticos son una mezcla del avance de la computación y de la genética. Si las computadoras no fueran tan rápidas y tan baratas este tipo de técnicas no tendrían sentido, serían muy caras. En la medida en que las computadoras sigan evolucionando y se abaraten, este tipo de cuestiones se hará más atractivas. “Actualmente, a un algoritmo genético aprender le toma segundos o minutos. Con las nuevas máquinas –más rápidas – aprenderá en milésimas de segundo. Y entonces tendremos algoritmos genéticos hasta en el horno de microondas; podrán, también, reconocer la voz de los dueños de la casa para abrirles la puerta. Los algoritmos genéticos permitirán que las computadoras sepan cuáles son las preferencias de su dueño...”