Nosotros somos la última línea de defensa en optimización: Carlos Coello Coello

• El Colegio Nacional inició el primer curso titulado Una introducción a la computación evolutiva: conceptos básicos y aplicaciones, impartido por el colegiado Carlos Coello Coello
• En la primera sesión, realizada en el Aula Mayor de la dependencia, el doctor en Ciencias de la Computación explicó que el objetivo de la optimización global es encontrar el óptimo de cualquier problema, es decir, la mejor solución posible en todo el espacio de búsqueda
• El Neodarwinismo, fundamento de la computación evolutiva, es la síntesis moderna de tres grandes corrientes científicas: la teoría de la evolución de Darwin, la genética de Mendel y la teoría del plasma germinal de Weismann: Coello Coello.

¿Evolución natural en una computadora?, sin duda, sobre todo si es con la intención de resolver los múltiples problemas de la optimización. Esta ha sido la principal línea argumentativa bajo cual, Carlos Coello Coello, inició su primer curso impartido como miembro de El Colegio Nacional y que se titula: Una introducción a la computación evolutiva: conceptos básicos y aplicaciones. Éste se lleva a cabo en el aula mayor de la institución, de manera abierta y gratuita para todo público, desde ayer lunes 15 y hasta el próximo viernes 19 de enero, en punto de las 18 horas.

Coello comenzó la sesión dedicando un buen tiempo a los conceptos básicos de la computación y la optimización, así como de lo que significan los algoritmos evolutivos y las metaheurísticas. Recordó que la computación evolutiva es un área en la que ha trabajado desde hace casi 30 años, mediante la cual simula la evolución natural, pero en una computadora.

En esta primera sesión, el doctor en Ciencias de la Computación por la Universidad Tulane, EE. UU., explicó que los algoritmos son procedimientos implementados en una computadora para realizar tareas particulares y suelen ser deterministas, es decir, predictivos si se conocen sus entradas.

Sin embargo, los algoritmos evolutivos son estocásticos, esto significa que, dadas las mismas entradas, no siempre producen la misma salida. “Tienen un componente relacionado con los números aleatorios debido a que simulan un proceso con incertidumbre que se basa en probabilidades”. De acuerdo con el colegiado, en el tema de algoritmos existen clases de problemas, como la clase P, a la que pertenecen los problemas que se pueden resolver en tiempo polinomial en una computadora determinística, una computadora que sabe a dónde moverse en el siguiente momento del tiempo, como es el caso de la búsqueda binaria o el Quicksort para ordenar listas.

También se encuentran los problemas a los que el gremio de la computación le teme, conocidos como NP, o problemas que pueden ser resueltos en tiempo polinomial, pero usando una computadora no determinística, artilugio que, en realidad, no existe, sino que es una abstracción inventada por los expertos en computo. Es decir, es un ordenador que sirve para mapear un algoritmo de una computadora no determinística a una determinística, el problema es que todavía no se sabe hacer de manera eficiente. Esa es una de las preguntas más importantes en materia de algoritmos ¿se puede hacer esto de manera eficiente?

Dentro de la clase de problemas NP, existe una subclase llamada problemas NP completos, que son todos los algoritmos que se conocen para resolver un problema que requieren tiempo exponencial, lo que tarda demasiado. “Un ejemplo muy famoso es el problema del viajero que tiene una lista de ciudades que quiere visitar y recorrer, pero minimizándola en función del costo sin dejar de lado ninguna de las ciudades de la lista. Por ejemplo, si se tienen diez ciudades, todas las soluciones posibles son 181 mil, no son tantas para las computadoras modernas, pero si en vez de 10 hay 20 o 50 ciudades, la cantidad de soluciones crece muy rápido, esos son los exponenciales”.

Por complejo que pueda sonar, este es un problema con muchísimas aplicaciones, por ejemplo, lo usan las empresas de logística y paquetería para encontrar la ruta que va a consumir menos tiempo y va a costar menos dinero, también tiene aplicaciones con las rutas de las líneas aéreas”, por citar sólo un par de casos.

Coello Coello explicó también que la optimización se refiere a la capacidad de resolver una ecuación de la manera más eficiente posible y utilizando la menor cantidad de recursos. En el área de optimización, se busca resolver problemas (con espacios de búsqueda muy grandes, sin enumerar las soluciones y existe la optimización) desde dos enfoques, el no lineal y la lineal.

“Para la optimización no lineal se encuentran los métodos directos y los no directos; los primeros se basan en ciertas propiedades del espacio de búsqueda, por ejemplo, una aleatoria cuya desventaja principal es que no puede garantizar convergencia, es decir, no puede asegurar que siempre va a llegar a lo óptimo. En tanto, los segundos, como el método del gradiente conjugado, puede garantizar llegar a lo óptimo, pero no siempre es aplicable, porque no se puede derivar la función”.

Explicó que cuando se intenta resolver un problema de optimización en general, “si la función a optimizar se encuentra en forma algebraica, es importante intentar resolverla primero con técnicas clásicas de programación matemática, antes de utilizar cualquier heurística” y recomendó varias herramientas de software comerciales que incluyen algoritmos que ayudara al proceso de optimización.

Sin embargo, en matemáticas, hay problemas que no se pueden resolver de manera eficiente o que simplemente no se pueden resolver usando un algoritmo, pues, requiere de tiempo polinomial, es decir, “es esa frontera, de aquello que ya no es realizable con estas técnicas que han desarrollado los matemáticos por muchos años, donde entramos nosotros, los que hacemos metaheurísticas. Dicho de otra forma, somos la última línea de defensa en optimización y se recurre a nosotros cuando nada de lo anterior funciona”.

El colegiado sostuvo que la optimización global es una de las áreas que tiene la optimización y su objetivo principal es encontrar el óptimo, o los óptimos globales, de cualquier problema, “lo que buscamos es encontrar la mejor solución posible en todo el espacio de búsqueda”.

Pero en la práctica, la mayoría de los problemas de optimización tienen algún tipo de restricción, por ejemplo, si se quiere utilizar una red de agua potable de una colonia de la Ciudad de México, para implementar la solución, se tendrían que ocupar tubos comprados en una tienda y no todas las medidas son iguales, entonces, para que la optimización sea precisa, el modelo tendría que tomar en cuenta los tamaños comerciales de los tubos, de lo contrario no es óptima. “Mientras más información se pueda utilizar del modelo real en el modelo computacional es mejor”.

La heurística al paso del tiempo

Agregó que a la computación evolutiva interesan aquellos problemas que no son lineales, aquellos para los cuales no es posible conocer la solución óptima. En este caso se hace uso de la optimización combinatoria, “un problema complejo con variables numéricas enteras donde se motiva el uso de las heurísticas”, palabra derivada del del griego que significa encontrar o descubrir, aunque su significado ha variado a lo largo de la historia

“El reino de las heurísticas empieza donde termina el dominio de las técnicas tradicionales, no hay un traslape. Si se puede resolver con las otras, resulta un desperdicio intentar usar las metaheurísticas, porque sería como querer matar una mosca con una escopeta. Tienen un optimizador muy poderoso y el problema no lo amerita”.

En palabras del colegiado, en los orígenes de la inteligencia artificial, en los años 50, la palabra heurística se usaba como el antónimo de algorítmico, un proceso que no se reducía a un algoritmo y se basaba en el conocimiento empírico de la experiencia humana. “Eso es en lo que se traduce el conocimiento heurístico, un conjunto de reglas que definen cómo el ser humano resuelve una tarea. Esta es una de las pocas palabras que existen en la inteligencia artificial cuyo significado ha cambiado en el tiempo. Fue en los años 80, cuando la heurística se comenzó a utilizar como adjetivo y se refirió a las técnicas que mejoran el desempeño en promedio de la solución de un problema”.

Técnica que busca soluciones buenas

En 1993, el científico inglés Alec Harley Reeves aseguró que una heurística es una técnica que busca soluciones buenas, es decir, casi óptimas y a un costo computacional razonable (definido por el usuario), que puede ir desde segundos hasta meses, según el problema y la paciencia.

La palabra metaheurística, la que se usa actualmente, la acuñó Fred Glover en 1986, y la define como un procedimiento de búsqueda de alto nivel que aplica una regla o conjunto de reglas, una o más heurísticas, que se basan en una fuente de conocimiento. “Y lo que queremos es explorar el espacio de búsqueda de manera más eficiente, esto significa no generar todas las soluciones posibles, sino la mejor”.

Coello Coello explicó que las metaheurísticas en optimización se pueden ver como métodos numéricos de búsqueda directa, en otras palabras, no requieren derivadas. Y aunque parecen tener muchas limitantes, se han vuelto populares en los últimos 30 años, porque la mayoría de los problemas del mundo real no pueden ser resueltos usando técnicas de programación matemática.

“Se han vuelto populares porque son flexibles y fáciles de usar. Son la última línea de defensa en optimización, no existe otra más. Su limitante es que no pueden garantizar el óptimo global, pues, hay problemas tan costosos, computacionalmente hablando, que no se puede aplicar esta técnica”.

Sin embargo, hoy en día, aseguró el colegiado, sí podemos optimizar el cambio de orbita de un satélite o el ala de un avión, a diferencia de hace varias décadas años, cuando estos problemas eran, sino imposibles, de resolución muy compleja. “En la actualidad, todo lo difícil en que puedan pensar, el problema más complicado, es donde entra la metaheurística”.

Neodarwinismo, metaheurísticas bioinspiradas y algoritmos evolutivos

Dentro de las muchas metaheurísticas que existen, explicó Coello Coello a la comunidad asistente en el aula mayor de El Colegio, así como a quienes siguieron esta primera sesión a través de las distintas plataformas digitales de la institución, “hay una clase que ha tomado popularidad, se trata de las metaheurísticas bioinspiradas, porque sus reglas, sus heurísticas están basadas en un proceso que existe en la naturaleza y que es simulado. Ahí entran los algoritmos evolutivos”, puntualizó el especialista.

Dijo que desde Georges-Louis Leclerc, quien planteó que los cambios que existen en los seres vivos se debían a la acción de factores externos, pasando por Johann Gregor Mendel, quien encontró las tres leyes básicas que gobiernan la herencia que dio origen a la genética, así como por Charles Darwin, quien presentó, en 1858, los primeros bosquejos de su teoría El origen de las especies, hasta August Weismann, quien formuló la teoría del plasma germinal a finales del siglo XIX, que planteó que la herencia en un organismo multicelular se efectúa únicamente por medio de células germinales, es decir, la unión de un espermatozoide con el óvulo, se ha construido la historia de la evolución de los seres humanos.

“Todo lo anterior lleva al término Nedarwinismo, que implica la síntesis moderna de tres teorías científicas: la de la evolución de Darwin, la genética de Mendel y la del plasma germinal de Weismann, ese es el fundamento de la computación evolutiva. Actualmente, los algoritmos que desarrollamos simulan el Neodarwinismo, teoría que plantea que toda la complejidad de vida del planeta, que es enorme, se puede explicar a través de cuatro procesos: la reproducción, la mutación, la competencia y la selección”, concluyó el colegiado.

La primera sesión del curso Una introducción a la computación evolutiva: conceptos básicos y aplicaciones, que se lleva a cabo del 15 al 19 de enero en el Aula Mayor de El Colegio Nacional, se encuentra disponible en el Canal de YouTube de la institución: elcolegionacionalmx.

Sigue las transmisiones en vivo de El Colegio Nacional
a través de nuestras plataformas digitales:
Página web: www.colnal.mx
YouTube: elcolegionacionalmx
Facebook: ColegioNacional.mx
Twitter: @ColegioNal_mx
Correo: prensa@colnal.mx