A New Meta-Heuristic for Improving General Multi-Start Procedures

En el mundo de la optimización, los científicos e ingenieros a menudo se enfrentan a un problema que parece simple pero esconde un laberinto de posibilidades: cómo ubicar un conjunto de instalaciones, como almacenes o torres de telefonía celular, para servir a una población dispersa de la manera más eficiente posible. El objetivo es minimizar la distancia total que las personas deben recorrer para llegar a la instalación más cercana. Esto se conoce como el problema del p-mediano. Debido a que el panorama de soluciones posibles es tan vasto e irregular, lleno de innumerables picos locales que parecen la mejor respuesta pero que en realidad son solo trampas, los investigadores confían en una estrategia llamada procedimiento de inicio múltiple (multi-start). Imagine intentar encontrar el punto más alto en una cadena montañosa cubierta de niebla dejando caer a un excursionista en un lugar aleatorio, dejándolo escalar hasta que no pueda subir más y luego repitiendo este proceso miles de veces desde diferentes puntos de partida. El mejor pico encontrado entre todos esos intentos es usualmente la respuesta. Sin embargo, incluso con miles de intentos, los excursionistas podrían perderse el verdadero sumo debido a que el terreno es tan complejo.

Dos investigadores, Zvi Drezner y Jack Brimberg, han propuesto un nuevo método para ayudar a estos excursionistas digitales a encontrar mejores picos sin necesidad de dedicar significativamente más tiempo a la búsqueda. Llaman a esta nueva técnica POST. En lugar de simplemente ejecutar la búsqueda miles de veces y elegir el mejor resultado único, POST toma los mejores pocos resultados de un lote de búsquedas y los utiliza para crear nuevos puntos de partida híbridos. Es un poco como tomar los rasgos más fuertes de los mejores excursionistas y combinarlos para crear un nuevo guía que comience la escalada desde una ubicación más prometedora. Los investigadores probaron este método en cuarenta y ocho escenarios diferentes que involucraban hasta diez mil puntos de demanda y cien instalaciones. Descubrieron que este nuevo enfoque mejoró consistentemente las mejores soluciones conocidas para cada uno de los casos de prueba, encontrando mejores respuestas en aproximadamente el mismo tiempo que tomaba realizar la búsqueda estándar.

El núcleo del desafío radica en la naturaleza misma del problema. Cuando se intenta ubicar instalaciones en un plano plano para servir a un grupo de puntos, el paisaje matemático es increíblemente accidentado. Contiene millones de óptimos locales, que son soluciones que son mejores que sus vecinos inmediatos pero no las mejores en general. Los algoritmos estándar a menudo se quedan atrapados en estos picos locales. La forma tradicional de superar esto es simplemente ejecutar el algoritmo de búsqueda muchas veces, comenzando desde ubicaciones aleatorias, con la esperanza de que uno de esos inicios aleatorios aterrice lo suficientemente cerca del verdadero óptimo global para permitir que el algoritmo escale hasta la cima. Los investigadores utilizaron un poderoso algoritmo de mejora llamado CLUST, que es actualmente una de las herramientas más efectivas para este trabajo, y lo ejecutaron desde ochenta mil puntos de partida diferentes en sus pruebas iniciales.

La innovación en POST es lo que sucede después de esas ejecuciones iniciales. En lugar de detenerse una vez que se encuentra el mejor resultado, los investigadores toman los cinco mejores resultados distintos de un lote más pequeño de ejecuciones y los tratan como "padres". Luego crean nuevos resultados "hijos" mezclando las ubicaciones de las instalaciones de estos padres. Para hacer esto, trazan una línea imaginaria a través del centro del grupo combinado de instalaciones. Las instalaciones del primer padre que se encuentran en un lado de la línea se emparejan con las instalaciones del segundo padre que se encuentran en el otro lado. Esto crea una nueva configuración que hereda las fortalezas de ambos padres. Los investigadores generan varias de estas nuevas configuraciones, ejecutan el algoritmo de mejora en ellas y observan si conducen a incluso mejores soluciones. Si lo hacen, el proceso se repite, utilizando los nuevos mejores resultados como los padres para la siguiente ronda de mezcla.

Este ciclo de mezcla y mejora se repite en varios lotes. Los investigadores probaron diferentes formas de organizar estos lotes. En una configuración, ejecutaron la búsqueda inicial mil veces, tomaron los cinco mejores resultados, los mezclaron y repitieron todo este ciclo setenta veces. En otra, ejecutaron la búsqueda diez mil veces y repitieron el ciclo ocho veces. En una tercera, ejecutaron la búsqueda completa de ochenta mil veces en un solo lote. Los resultados mostraron un patrón claro: dividir la búsqueda en lotes más pequeños y refinar repetidamente los mejores resultados encontrados en cada lote produjo mejores resultados que ejecutar la búsqueda completa de una sola vez. El método que ejecutó mil búsquedas iniciales y repitió el ciclo de refinamiento setenta veces produjo las mejoras más consistentes, encontrando mejores soluciones que cualquier método anterior para los cuarenta y ocho casos de prueba.

Los investigadores se aseguraron cuidadosamente de que el tiempo adicional dedicado a este proceso de mezcla fuera insignificante. Debido a que los nuevos puntos de partida creados mediante la mezcla ya son soluciones de alta calidad, el algoritmo de mejora converge en un óptimo local mucho más rápido que desde un punto de partida aleatorio. El tiempo total requerido por el método POST fue solo ligeramente superior al enfoque de inicio múltiple estándar, pero encontró consistentemente resultados superiores. Para los casos de prueba uniformes, el nuevo método mejoró las mejores soluciones conocidas en un promedio de 0.062 por ciento, y para los casos no uniformes, en un 0.068 por ciento. Aunque estos porcentajes puedan parecer pequeños, en el contexto de la logística y la planificación de instalaciones a gran escala, representan ahorros significativos en distancia y costo.

El estudio también exploró los límites de este enfoque. Los investigadores señalaron que si el procedimiento de inicio múltiple ya había encontrado la solución absolutamente óptima, el método POST no podría mejorarla más. Sin embargo, dado que el problema del p-mediano es conocido por tener millones de óptimos locales, es muy improbable que una búsqueda estándar encuentre la respuesta perfecta por azar. El hecho de que POST mejorara los resultados en cada instancia sugiere que las búsquedas estándar se estaban quedando atrapadas en picos locales que POST pudo sortear. Los investigadores también observaron que aumentar el número de búsquedas iniciales en un solo lote no siempre conducía a mejores resultados; de hecho, los lotes más pequeños con más repetición funcionaron mejor. Esto respalda un principio que llaman "Menos es Más", sugiriendo que es más efectivo explorar profundamente y repetidamente unos pocos áreas prometedoras que lanzar una red amplia una sola vez y esperar lo mejor.

El éxito de POST no se limitó a un solo tipo de problema. Los investigadores lo probaron tanto en instancias uniformes, donde los puntos de demanda están distribuidos uniformemente, como en instancias no uniformes, donde los puntos están agrupados de formas específicas. En ambos escenarios, el método superó a las técnicas anteriores, incluyendo los mejores resultados de otros estudios recientes que habían tomado meses de tiempo computacional para lograrse. El nuevo método logró estos resultados en una fracción del tiempo, siendo el tiempo total de ejecución para la configuración más efectiva de unos trece días para el conjunto completo de pruebas. Los investigadores también proporcionaron una fórmula para estimar cómo escalaría el tiempo de ejecución con el tamaño del problema, señalando que a medida que el número de puntos de demanda aumentaba diez veces, el tiempo requerido aumentaba aproximadamente entre quince y diecisiete veces, mientras que duplicar el número de instalaciones aumentaba el tiempo en menos de un factor de dos.

Mirando hacia el futuro, los autores sugieren que esta técnica podría aplicarse a otros problemas de optimización que actualmente se resuelven utilizando enfoques de inicio múltiple, como la agrupación de puntos de datos o la partición de redes. Proponen que la investigación futura podría explorar diferentes formas de seleccionar las soluciones "padre", quizás eligiéndolas no solo por su calidad sino también por qué tan diferentes son entre sí, para asegurar una búsqueda más diversa. También sugieren que aumentar el número de soluciones en el conjunto de élite utilizado para la mezcla podría arrojar mejores resultados, aunque esto requeriría más potencia de cómputo. El estudio concluye que, al añadir un simple paso de post-optimización a los algoritmos existentes, los investigadores pueden mejorar significativamente la calidad de las soluciones sin un aumento prohibitivo en el esfuerzo, ofreciendo una nueva herramienta poderosa para abordar algunos de los problemas de planificación espacial más complejos.