Optimización mediante la red Hopfield

La optimización es una acción para hacer que algo como el diseño, la situación, los recursos y el sistema sean lo más efectivos posible. Utilizando una semejanza entre la función de costo y la función de energía, podemos usar neuronas altamente interconectadas para resolver problemas de optimización. Este tipo de red neuronal es la red Hopfield, que consta de una sola capa que contiene una o más neuronas recurrentes completamente conectadas. Esto se puede utilizar para la optimización.

Puntos para recordar al usar la red Hopfield para la optimización:

• La función energética debe ser mínima de la red.

• Encontrará una solución satisfactoria en lugar de seleccionar uno de los patrones almacenados.

• La calidad de la solución encontrada por la red Hopfield depende significativamente del estado inicial de la red.

Problema del vendedor ambulante

Encontrar la ruta más corta recorrida por el vendedor es uno de los problemas computacionales, que se puede optimizar utilizando la red neuronal Hopfield.

Concepto básico de TSP

El problema del vendedor ambulante (TSP) es un problema de optimización clásico en el que un vendedor tiene que viajar nciudades, que están conectadas entre sí, manteniendo el costo y la distancia recorrida al mínimo. Por ejemplo, el vendedor tiene que recorrer un conjunto de 4 ciudades A, B, C, D y el objetivo es encontrar el recorrido circular más corto, ABC-D, para minimizar el costo, que también incluye el costo de viajar desde la última ciudad D a la primera ciudad A.

Representación matricial

En realidad, cada recorrido de TSP n-city puede expresarse como n × n matriz cuya i_th fila describe el i_thubicación de la ciudad. Esta matriz,M, para 4 ciudades A, B, C, D se puede expresar de la siguiente manera:

$$ M = \ begin {bmatrix} A: & 1 & 0 & 0 & 0 \\ B: & 0 & 1 & 0 & 0 \\ C: & 0 & 0 & 1 & 0 \\ D: & 0 & 0 & 0 & 1 \ end {bmatrix} $$

Solución de Hopfield Network

Al considerar la solución de este TSP de la red Hopfield, cada nodo de la red corresponde a un elemento de la matriz.

Cálculo de la función de energía

Para ser la solución optimizada, la función energética debe ser mínima. Sobre la base de las siguientes restricciones, podemos calcular la función de energía de la siguiente manera:

Restricción-I

La primera restricción, sobre la base de la cual calcularemos la función de energía, es que un elemento debe ser igual a 1 en cada fila de la matriz. M y otros elementos en cada fila deben ser iguales a 0porque cada ciudad puede aparecer en una sola posición en la gira TSP. Esta restricción se puede escribir matemáticamente de la siguiente manera:

$$ \ Displaystyle \ sum \ limits_ {j = 1} ^ n M_ {x, j} \: = \: 1 \: para \: x \: \ in \: \ lbrace1, ..., n \ rbrace $ PS

Ahora, la función de energía a minimizar, basada en la restricción anterior, contendrá un término proporcional a -

$$ \ Displaystyle \ sum \ limits_ {x = 1} ^ n \ left (\ begin {array} {c} 1 \: - \: \ Displaystyle \ sum \ limits_ {j = 1} ^ n M_ {x, j } \ end {matriz} \ right) ^ 2 $$

Restricción-II

Como sabemos, en TSP una ciudad puede ocurrir en cualquier posición en el recorrido, por lo tanto, en cada columna de la matriz. M, un elemento debe ser igual a 1 y otros elementos deben ser iguales a 0. Esta restricción se puede escribir matemáticamente de la siguiente manera:

$$ \ Displaystyle \ sum \ limits_ {x = 1} ^ n M_ {x, j} \: = \: 1 \: para \: j \: \ in \: \ lbrace1, ..., n \ rbrace $ PS

Ahora, la función de energía a minimizar, basada en la restricción anterior, contendrá un término proporcional a -

$$ \ Displaystyle \ sum \ limits_ {j = 1} ^ n \ left (\ begin {array} {c} 1 \: - \: \ Displaystyle \ sum \ limits_ {x = 1} ^ n M_ {x, j } \ end {matriz} \ right) ^ 2 $$

Cálculo de la función de costo

Supongamos una matriz cuadrada de (n × n) denotado por C denota la matriz de costos de TSP para n ciudades donde n > 0. A continuación se muestran algunos parámetros al calcular la función de costo:

• C_{x, y} - El elemento de la matriz de costos denota el costo de viajar desde la ciudad. x a y.

• La adyacencia de los elementos de A y B se puede mostrar mediante la siguiente relación:

$$ M_ {x, i} \: = \: 1 \: \: y \: \: M_ {y, i \ pm 1} \: = \: 1 $$

Como sabemos, en Matrix, el valor de salida de cada nodo puede ser 0 o 1, por lo tanto, para cada par de ciudades A, B podemos agregar los siguientes términos a la función de energía:

$$ \ Displaystyle \ sum \ limits_ {i = 1} ^ n C_ {x, y} M_ {x, i} (M_ {y, i + 1} \: + \: M_ {y, i-1}) $$

Sobre la base de la función de costo y el valor de restricción anteriores, la función de energía final E se puede dar de la siguiente manera:

$$ E \: = \: \ frac {1} {2} \ displaystyle \ sum \ limits_ {i = 1} ^ n \ displaystyle \ sum \ limits_ {x} \ displaystyle \ sum \ limits_ {y \ neq x} C_ {x, y} M_ {x, i} (M_ {y, i + 1} \: + \: M_ {y, i-1}) \: + $$

$$ \: \ begin {bmatrix} \ gamma_ {1} \ displaystyle \ sum \ limits_ {x} \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ limits_ {i} M_ {x, i} \ end {matriz} \ right) ^ 2 \: + \: \ gamma_ {2} \ Displaystyle \ sum \ limits_ {i} \ left (\ begin {matriz} {c} 1 \: - \ : \ Displaystyle \ sum \ limits_ {x} M_ {x, i} \ end {array} \ right) ^ 2 \ end {bmatrix} $$

Aquí, γ₁ y γ₂ son dos constantes de pesaje.