Aprendizaje computacional y algoritmos heurísticos para la resolución de problemas

Por Eduardo Vázquez

Xalapa, Veracruz. 17 de septiembre de 2018 (Agencia Informativa Conacyt).- Con la implementación de algoritmos heurísticos es posible tener decisiones inteligentes para resolver problemas específicos, afirmó la doctora Marcela Quiroz Castellanos, del Centro de Investigación en Inteligencia Artificial (CIIA) de la Universidad Veracruzana (UV).

Como parte de su actual investigación, la integrante del cuerpo académico del CIIA busca unir dos áreas de la inteligencia artificial —aprendizaje computacional y algoritmos heurísticos— para entender la generación de posibilidades de decisiones y cómo estas pueden resolver ciertos problemas que se presentan en la vida cotidiana y en sectores más amplios, como la industria y el mercado.

Durante una conversación con la Agencia Informativa Conacyt, la investigadora comentó cómo ha desarrollado el diseño de estos algoritmos, cuáles son sus características y cómo estos son un avance también para el área de la minería de datos.

Agencia Informativa Conacyt (AIC): ¿Cuál es la relación entre aprendizaje computacional y el método de la generación de algoritmos heurísticos?

Marcela Quiroz Castellanos (MQC): En el aprendizaje computacional la idea es poder utilizar algoritmos computacionales y de inteligencia artificial para aprender o para extraer conocimiento en distintas situaciones. Normalmente lo que necesitamos son datos, pero ya de dónde vienen esos datos y cómo los extraes es otro punto importante.

Doctora Marcela Quiroz en el patio del Centro de Investigación en Inteligencia Artificial.En mi caso, estoy utilizando el aprendizaje computacional para tratar de entender el comportamiento de algoritmos heurísticos. Los algoritmos heurísticos es otra línea de la inteligencia artificial, de lo que trata es de simular el comportamiento que tenemos los humanos y animales para solucionar problemas a los que se enfrentan en el día a día.

Había una corriente en operaciones de logística donde lo que quieres es minimizar o maximizar algún recurso. Quieres maximizar las ganancias en algún proceso que realizas en tu empresa o quieres minimizar los tiempos en que realizas una tarea. Para poder identificar de qué manera llevar a cabo ese procedimiento se diseñan métodos de solución que te dicen cómo puedes realizar ese proceso para que obtengas los mejores beneficios.

Resultó que conforme fueron resolviendo este tipo de problemas, se encontraron con que muchos eran muy difíciles. Los métodos para generar las soluciones tardaban mucho tiempo. Podían tardar años dependiendo de las computadoras, aun hablando de computadoras con las mejores capacidades que en la actualidad existen para ciertos problemas en particular. Si tú viajabas corriendo para generar las posibles soluciones para después decir cuál es la que te permite obtener el mejor beneficio, eso tomaría años.

Desde la inteligencia artificial comenzó a verse que por qué no mejor en lugar de tratar de ver todas las posibles soluciones y quedarse con la mejor, no imitamos la forma en cómo nosotros los seres vivos abordamos este tipo de problemas. Realmente no vemos todas las soluciones posibles y luego tomamos la mejor, sino que vamos tomando decisiones paso a paso inteligentemente con base en nuestra experiencia y entonces en un tiempo corto generamos una solución, que si bien no es la mejor entre todo el universo de soluciones son aceptables con la que hemos vivido.

Estos algoritmos no garantizan que siempre vamos a encontrar la mejor solución posible, sino que la van a buscar de una forma basada en la experiencia, con reglas inteligentes que intentarán encontrar una buena solución. Si bien es cierto que encontrarán buenas soluciones, nada nos garantiza que van a encontrar la mejor solución. Cuando nosotros observamos este mismo algoritmo aplicado a distintos problemas, nos damos cuenta que para algunos obtiene mejores soluciones que para otros. Yo lo que estoy haciendo es tratar de explicar por qué a estos algoritmos heurísticos ante ciertos problemas obtienen soluciones muy buenas, a veces soluciones regulares y en otras ocasiones soluciones malas.

Para esto aplico el aprendizaje computacional. Estoy tratando de complementar dos ramas de la inteligencia artificial que en principio cada una iba de su lado para analizar cuáles son las soluciones que me darían los algoritmos heurísticos, internamente cómo están trabajando para construir las soluciones y los comportamientos distintos que tienen cuando se enfrentan con problemas con características diferentes, para poder obtener modelos que me predigan en un futuro qué algoritmos elegir ante un problema.

AIC: ¿En qué consiste tener, como agentes racionales, una decisión inteligente?

MQC: Vamos a pensar que yo quiero resolver un problema muy sencillo como generar una ruta con una distancia mínima. Nosotros tenemos herramientas disponibles, como por ejemplo Google Maps, pero nos genera la distancia entre dos puntos. Pero qué tal si yo quiero visitar muchos puntos al mismo tiempo. No solo quiero ir de la escuela a la casa, quiero generar una ruta óptima. Quiero salir de mi casa, quiero ir al supermercado, luego quiero ir al trabajo, luego visitar a una amiga, luego al parque y después regresar a mi casa. Yo podría tener distintas opciones dado que todos los puntos están conectados entre sí. Quiero ir a todos esos lugares, pero no me importa el orden en el que vayan. Iré en el orden que sea conveniente de tal manera que el recorrido lo haga en el menor tiempo.

A lo mejor un recorrido que sea de mi casa a la escuela y de ahí al supermercado. Eso me va a llevar 20 minutos. Otro que fuera ir a mi casa y de ahí al parque. Eso me llevaría 15 minutos. Así yo puedo ir generando distintas formas de recorrer esos puntos y cada una me va a dar un tiempo. Eso es lo que me diría qué tan buena o mala es mi solución. Por ejemplo, la que se tarda 20 minutos es peor que la que se tarda 15. Pero a lo mejor hay una que se tarda 12. No lo sé. Yo tendría que ir generando las distintas formas de recorrer esos puntos para ver cuál es la mejor. La mejor sería la que lleve menos tiempo.

Si tengo cinco puntos para generar mi ruta, no sería tan difícil generar todas las posibles permutaciones de recorrer los puntos y ver cuál es la mejor. Pero cuando estoy resolviendo problemas de la vida real en el sentido de una empresa que reparte productos a distintos clientes, ya no son cinco. Si quiero planear en tiempos más grandes, por ejemplo en un mes, cómo van a quedar las rutas de todos, ya estamos hablando de más. Lo que ocurre es que conforme va creciendo el número de puntos que están en la ruta, el número de posibles formas va creciendo de manera exponencial.

Solo puedo generar algunas y ahí utilizaría una heurística. ¿Cómo son las decisiones inteligentes? Las decisiones inteligentes son, por ejemplo, si estoy ahora en un punto en particular y pienso a dónde me conviene ir en este momento para que mi tiempo total sea el menor, puedo ir a lo que me quede más cerca, esa podría ser una decisión. Un tanto inteligente quizá es como uno como ser humano pensaría. Pero a lo mejor podría calcular el promedio de las distancias entre los puntos que me hacen falta visitar y voy a ver cuál es la que me conviene visitar. Así puedo registrar distintas maneras de cómo podría tener la solución.

AIC: Según esta explicación, ¿cómo afectaría el contexto a los resultados esperados durante la implementación de los algoritmos heurísticos?

MQC: Claro. Yo puedo tener distintos tipos de problemas a resolver y en algunos me tengo que estar adaptando a condiciones cambiantes. Entonces tendría que preparar mis heurísticas para que consideren el cambio de condiciones. Tengo que adaptarme para eso. Otro contexto podría ser un problema distinto.

Hablando del mismo problema en sí, el de recorrer rutas, contextos distintos también puede ser las características del caso que voy a resolver. Por ejemplo, si yo conozco con anticipación los puntos para generar la ruta, puede haber problemas distintos con las mismas características. En algunos las distancias entre los pares de puntos a visitar podrían ser muy parecidas, en otros podrían ser muy distintas, en otros podría haber como una distribución o algo que describa cómo se comportan estas distancias, en otros qué tantos puntos hay que visitar y eso haría que existieran mayores rutas posibles.

Eso afectaría en el sentido de cuándo me conviene utilizar un algoritmo o no y para eso sirve este aprendizaje computacional. No es algo que se haga en el momento en el que yo estoy construyendo la solución. Es algo que se hace una vez que yo he aplicado mi algoritmo heurístico para resolver muchos problemas. Estoy extrayendo información de ahí que luego voy a analizar para extraer conocimiento. Finalmente se convierte en un problema de minería de datos.

AIC: ¿Cuáles han sido los casos de aplicación de este modelo que usted trabaja?

MQC: Estoy trabajando con el empacado de contenedores. Estoy analizando el comportamiento y el procedimiento para insertar objetos en estos contenedores y lograr que quepa el menor número de ellos. Lo que he estado haciendo es identificar cuándo puede ser más difícil el problema si las características que te dan son tales o cuáles.

Para ese mismo problema, estoy analizando una serie de algoritmos para ver también cada uno qué afinidad tiene con qué tipo de problemas. Uno de los algoritmos que estoy analizando es un algoritmo genético, lo que hace es ir construyendo soluciones simulando el proceso de evolución de las especies, donde lo que trata de hacer es a partir de un conjunto de soluciones ir construyendo otras soluciones que van heredando características de las soluciones padre, por decirlo así y trata de ir mejorando esa población hasta en algún punto llegar a una estabilidad en la cual ya la solución tiene características deseables que da la mejor solución ante el problema.

Ahora estoy en esa parte, intento explicar las características de ese algoritmo y hasta hoy lo que he logrado hacer es que esté en el punto donde presenta un comportamiento muy robusto, lo cual es bueno para cualquier instancia nueva que llegue. Ya tiene la inteligencia para poder resolver el problema.

image icon01 Descargar fotografías.