Artificial Neural Network 简明教程

Optimization Using Hopfield Network

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

Optimization is an action of making something such as design, situation, resource, and system as effective as possible. Using a resemblance between the cost function and energy function, we can use highly interconnected neurons to solve optimization problems. Such a kind of neural network is Hopfield network, that consists of a single layer containing one or more fully connected recurrent neurons. This can be used for optimization.

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

Points to remember while using Hopfield network for optimization −

The energy function must be minimum of the network.
It will find satisfactory solution rather than select one out of the stored patterns.
The quality of the solution found by Hopfield network depends significantly on the initial state of the network.

Travelling Salesman Problem

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

Finding the shortest route travelled by the salesman is one of the computational problems, which can be optimized by using Hopfield neural network.

Basic Concept of TSP

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

Travelling Salesman Problem (TSP) is a classical optimization problem in which a salesman has to travel n cities, which are connected with each other, keeping the cost as well as the distance travelled minimum. For example, the salesman has to travel a set of 4 cities A, B, C, D and the goal is to find the shortest circular tour, A-B-C–D, so as to minimize the cost, which also includes the cost of travelling from the last city D to the first city A.

Matrix Representation

实际上，n 个城市 TSP 的每个行程都可以表示为 n × n ，其中 ith 行描述 ith 个城市的方位。此矩阵 M ，适用于 4 个城市 A、B、C、D，可以表示为以下形式 −

Actually each tour of n-city TSP can be expressed as n × n matrix whose ith row describes the ith city’s location. This matrix, M, for 4 cities A, B, C, D can be expressed as follows −

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 解决方案时，网络中的每个节点对应于矩阵中的一个元素。

While considering the solution of this TSP by Hopfield network, every node in the network corresponds to one element in the matrix.

Energy Function Calculation

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

To be the optimized solution, the energy function must be minimum. On the basis of the following constraints, we can calculate the energy function as follows −

Constraint-I

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

First constraint, on the basis of which we will calculate energy function, is that one element must be equal to 1 in each row of matrix M and other elements in each row must equal to 0 because each city can occur in only one position in the TSP tour. This constraint can mathematically be written as follows −

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

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

Now the energy function to be minimized, based on the above constraint, will contain a term proportional to −

\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。此约束在数学上可以写成以下形式 −

As we know, in TSP one city can occur in any position in the tour hence in each column of matrix M, one element must equal to 1 and other elements must be equal to 0. This constraint can mathematically be written as follows −

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

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

Now the energy function to be minimized, based on the above constraint, will contain a term proportional to −

\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 。以下是在计算成本函数时的一些参数 −

Let’s suppose a square matrix of (n × n) denoted by C denotes the cost matrix of TSP for n cities where n > 0. Following are some parameters while calculating the cost function −

Cx, y − The element of cost matrix denotes the cost of travelling from city x to y.
Adjacency of the elements of A and B can be shown by the following relation −

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

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

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

As we know, in Matrix the output value of each node can be either 0 or 1, hence for every pair of cities A, B we can add the following terms to the energy function −

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

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

On the basis of the above cost function and constraint value, the final energy function E can be given as follows −

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 是两个加权常量。

Here, γ1 and γ2 are two weighing constants.