Minimización de Funciones

• La utilización del modelo de Hopfield para la resolución de problemas de minimización se basa en la idea de intentar fijar el objetivo del problema mediante una expresión matemática, (función de coste) que haya que minimizar.
• Se compara dicha expresión con la general de la función de energía de una Red de Hopfield, determinándose los valores de los pesos y de los umbrales en términos de parámetros de la función objetivo para que ambas expresiones sean equivalentes.

Problema del Viajante

• Dadas N ciudades se debe de encontrar la ruta más corta que visite a cada una de ellas:
  • N=5 12 caminos
  • N=10 181.440 caminos no abordable
  • N=50 3*exp(62) caminos

Solución:

Se utiliza una Red de Hopfield con N*N neuronas. Salidas en [0,1]. Cuando se alcance la estabilidad las neuronas de la red tendrán salidas binarias. Nos imaginamos las neuronas de la red distribuidas dimensionalmente:

Cada fila: representa una ciudad del recorrido. Cada columna: la posición de la ciudad en la ruta.

Se determina ahora la función de coste:

• 1º Término: Sólo una ciudad puede aparecer en una parada en la ruta
• 2º Término: En una parada sólo se corresponde a una ciudad
• 3º Término: En el recorrido sólo hay N ciudades.
• 4º Término: Distancia total del recorrido.

Se compara con la expresión general de la función de energía de Hopfield.

M. González Penedo