Artificial Neural Network 简明教程

Optimization Using Hopfield Network

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

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

  1. 网络的能量函数必须最小。

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

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

Travelling Salesman Problem

寻找推销员行进的最短路线是其中一个计算问题，可以通过使用霍普菲尔德神经网络来优化它。

Basic Concept of TSP

旅行商问题 (TSP) 是一种经典的优化问题，在该问题中，推销员必须游览 n 个城市，这些城市彼此相连，同时保持成本和距离最小。例如，推销员必须游览一组城市 A、B、C、D，目标是找到最短的环形路线 A-B-C–D，以使成本最小化，其中还包括从最后一个城市 D 到第一个城市 A 的出行成本。

travelling salesman problem

Matrix Representation

实际上，n 个城市 TSP 的每个行程都可以表示为 n × n ，其中 ith 行描述 ith 个城市的方位。此矩阵 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}

Solution by Hopfield Network

在考虑 Hopfield 网络的 TSP 解决方案时，网络中的每个节点对应于矩阵中的一个元素。

Energy Function Calculation

为了成为优化的解决方案，能量函数必须为最小值。在以下约束的基础上，我们可以计算能量函数，如下所示 −

Constraint-I

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

\displaystyle\sum\limits_{j=1}^n M_{x,j}\:=\:1\:for \: x\:\in \:\lbrace1,…​,n\rbrace

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

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

Constraint-II

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

\displaystyle\sum\limits_{x=1}^n M_{x,j}\:=\:1\:for \: j\:\in \:\lbrace1,…​,n\rbrace

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

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

Cost Function Calculation

假设一个 n × n 平方矩阵由 C 表示，表示 n 城市 TSP 的成本矩阵，其中 n > 0 。以下是在计算成本函数时的一些参数 −

  1. Cx, y − 成本矩阵的元素表示从城市 x 到 y 出行的成本。

  2. A 和 B 元素的邻接关系可以通过以下关系式表示−

M_{x,i}\:=\:1\:\: 和\:\: 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\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{array}\right)^2\:+\: \gamma_{2} \displaystyle\sum\limits_{i} \left(\begin{array}{c}1\:-\:\displaystyle\sum\limits_{x} M_{x,i}\end{array}\right)^2 \end{bmatrix}

此处， γ1 和 γ2 是两个加权常量。