El artículo del algoritmo genético gana un premio

Un artículo con Maptek como co-autor fue premiado en la Conferencia de Computación Genética y Evolutiva en Denver, Colorado en julio.

Rompiendo la barrera de mil millones de variables en la optimización del mundo real con el uso de un algoritmo evolutivo personalizado escrito por Christie Myburgh y la Profesora Kalyanmoy Deb de la Universidad del Estado de Michigan, ganó el premio del mejor artículo en la categoría de algoritmo genético.

El Ingeniero Principal de Investigación y Desarrollo de Maptek Myburgh dijo que asistir a la Conferencia de Computación Genética y Evolutiva (GECCO), y en particular a la sesión de presentación, fue una gran experiencia.

“La sesión estaba llena y la gente estaba de pie en el pasillo para escuchar”, dijo Myburgh.

En el artículo se detalla una solución a un problema planteado de forma simple: Una fundición de metal produce diferentes tipos de piezas de fundición; cada colada requiere diferentes volúmenes de metales; usted tiene un número de pedidos totales de diferentes fundiciones para llenar, mediante el vertido desde series secuenciales de un crisol de volumen conocido, por lo general significativamente más grandes que cualquier fundición. ¿Cuáles son las secuencias requeridas de vertido para (a) llenar las órdenes y (b) reducir al mínimo el número de series?

Las series del crisol son caras debido a los costos de energía. Cada vertido de crisol retiene material si el metal líquido restante sólo puede llenar parcialmente un molde, por lo que es ya sea desperdicio o la necesidad de volver a calentar ese metal residual.

La secuencia óptima para la producción de las piezas fundidas para minimizar el desperdicio no es obvia. ¡Trate de hacerlo de forma manual con lápiz y papel para un crisol de 10L y órdenes al azar n = 20 entre un conjunto de tres piezas fundidas 3L, 4L y 5L!

Un enfoque de optimización basado en la población permitió a los autores desarrollar un método computacionalmente rápido para llegar a una solución casi óptima.

Dos programas populares (glpk y cplex) no son capaces de manejar alrededor de n=300 (10 pedidos y 30 series) y n=2000 (10 pedidos y 200 series) variables respectivamente, a pesar de ejecutarse por horas.

Sin embargo, el método propuesto de Myburgh y Deb es capaz de encontrar una solución casi óptima en menos de un segundo en la misma computadora.

Lo más destacado del estudio es que el método escala a una complejidad computacional casi lineal y por lo tanto puede manejar hasta n = mil millones en una PC portátil, ¡si así lo permite la memoria!

El Director de Desarrollo de Productos de Maptek Simon Ratcliffe dijo que una clase similar de algoritmos de optimización es crítica para el software de programación de minas Maptek Evolution, y la capacidad de escalar hasta grandes conjuntos de datos es vital.

“Esta es la belleza de la ciencia informática”, dijo Ratcliffe. “No se deben tomar los ejemplos a su valor nominal. Los algoritmos son abstractos y, por tanto, a menudo pueden proporcionar soluciones para una gran variedad de problemas aparentemente diferentes en el mundo real”.

“Una de las claves del análisis de ingeniería en el cálculo es detectar o saber cuándo una determinada clase de algoritmo puede ser aplicable en un nuevo dominio”.

“La personalización e incorporación de conocimientos específicos del dominio en el diseño de un algoritmo de optimización es crucial cuando se aplica a gran escala, a problemas complejos del mundo real y altamente restringidos.


Christie Myburgh (segunda a la izquierda) y Kalyanmoy Deb (tercera a la izquierda) con estudiantes del Laboratorio de Optimización e Innovación Computacional que asistió a GECCO 2016

Forge Inicio