使用 Hopfield 网络进行优化

优化是使设计、情况、资源和系统等尽可能有效的行为。利用成本函数和能量函数之间的相似性，我们可以使用高度互连的神经元来解决优化问题。Hopfield 网络就是这种神经网络，它由包含一个或多个完全连接的循环神经元的单层组成。这可用于优化。

使用 Hopfield 网络进行优化时要记住的要点 −

• 能量函数必须是网络的最小值。

• 它将找到令人满意的解决方案，而不是从存储的模式中选择一个。

• Hopfield 网络找到的解决方案的质量在很大程度上取决于网络的初始状态。

旅行商问题

寻找推销员旅行的最短路线是计算问题之一，可以使用 Hopfield 神经网络进行优化。

TSP 的基本概念

旅行商问题 (TSP) 是一个经典的优化问题，其中推销员必须前往 n 个相互连接的城市，并保持成本和旅行距离最小。例如，推销员需要前往 4 个城市 A、B、C、D，目标是找到最短的环形路线，即 A-B-C–D，以最小化成本，其中还包括从最后一个城市 D 前往第一个城市 A 的成本。

矩阵表示

实际上，n 个城市 TSP 的每次行程都可以表示为 n × n 矩阵，其中 i_th 行描述 i_th 城市的位置。这个矩阵 M 代表 4 个城市 A、B、C、D，可以表示为 −

$$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}$$

Hopfield 网络解决方案

在考虑使用 Hopfield 网络解决此 TSP 问题时，网络中的每个节点都对应矩阵中的一个元素。

能量函数计算

要获得优化解决方案，能量函数必须最小。基于以下约束，我们可以计算能量函数如下 −

约束-I

第一个约束，我们将以此为基础计算能量函数，即矩阵M的每一行中必须有一个元素等于 1，而每一行中的其他元素必须等于 0，因为每个城市在 TSP 行程中只能出现在一个位置。此约束可以用数学形式写成如下 −

$$\displaystyle\sum\limits_{j=1}^n M_{x,j}\:=\:1\:for \: x\:\in \:\lbrace1,...,n brace$$

现在，基于上述约束，要最小化的能量函数将包含一个与 成比例的项 −

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

约束-II

众所周知，在 TSP 中，一个城市可以出现在行程中的任何位置，因此在矩阵 M 的每一列中，一个元素必须等于 1，其他元素必须等于 0。此约束在数学上可以写成如下 −

$$\displaystyle\sum\limits_{x=1}^n M_{x,j}\:=\:1\:for \: j\:\in \:\lbrace1,...,n brace$$

现在，基于上述约束，要最小化的能量函数将包含一个与 − 成比例的项

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

成本函数计算

假设一个 (n × n) 的方阵，记为 C，表示 n 个城市的 TSP 成本矩阵，其中 n > 0。以下是计算成本函数 −

• C_{x, y} −成本矩阵的元素表示从城市x到y的旅行成本。

• A和B元素的相邻关系可以用以下关系−表示

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

众所周知，在矩阵中，每个节点的输出值可以是0或1，因此对于每对城市A，B，我们可以将以下项添加到能量函数−

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

基于上述成本函数和约束值，最终的能量函数E可以表示为 −

$$E\:=\:\frac{1}{2}\displaystyle\sum\limits_{i=1}^n\displaystyle\sum\limits_{x}\displaystyle\sum\limits_{y eq 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{array} ight)^2\:+\: \gamma_{2} \displaystyle\sum\limits_{i} \left(\begin{array}{c}1\:-\:\displaystyle\sum\limits_{x} M_{x,i}\end{array} ight)^2 \end{bmatrix}$$

这里，γ₁ 和 γ₂ 是两个加权常数。