Algunas cuestiones notables sobre el modelo de Hopfield en optimización

Résumé

El modelo de Hopfield continuo puede utilizarse como heurística para resolver problemas de optimización combinatoria, como es el caso del problema del viajante TSP. Consiste en una red neuronal recurrente con una ecuación diferencial asociada, cuyos estados evolucionan de un punto inicial a un punto de equilibrio mediante la minimización de una función de Lyapunov. Asociando dicha función con la función objetivo y restricciones del problema de optimización, se consigue que los puntos de equilibrio se correspondan con soluciones factibles del problema de optimización. Aplicando la formulación original de Hopfield al TSP, este proceso deja un parámetro libre. Históricamente, los investigadores en el campo han utilizado valores pequeños de dicho parámetro, sin explicar por qué se obtienen mejores soluciones. Esta memoria analiza la relación entre el parámetro libre y el punto de silla del modelo de Hopfield. Mientras que en problemas pequeños este resultado garantiza poder obtener siempre la solución óptima, en problemas más complejos como el TSP resulta más complicado. No obstante, las cuencas de atracción para las mejores soluciones se hacen más amplias en las proximidades del punto de silla cuando el parámetro libre decrece. Así, los puntos situados en las proximidades del punto de silla serán excelentes candidatos a punto inicial de la simulación. Con el objetivo de continuar mejorando la calidad de las soluciones del modelo de Hopfield, se propone el modelo Divide-y-Vencerás, un modelo basado en dos modelos de Hopfield consecutivos. Este modelo conecta en la primera fase ciudades vecinas y en una segunda fase los grupos de ciudades conectados en la fase anterior. En ambos casos, se deducen las correspondientes parametrizaciones del problema y se resuelven con el modelo de Hopfield. Finalmente, se estudia cómo un caso particular del modelo de Hopfield utilizado en la segunda fase del modelo Divide-y-Vencerás, se comporta en realidad como un algoritmo 2-opt, siempre y cuando se elija adecuadamente el punto inicial. Todos estos resultados mejoran el rendimiento del modelo de Hopfield como heurística, equiparándolo al algoritmo 2-opt en calidad de solución.