# 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.

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

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

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=⎡⎣⎢⎢⎢A:B:C:D:1000010000100001⎤⎦⎥⎥⎥

## Solution by Hopfield Network

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

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 −

j=1nMx,j=1forx{1,...,n}

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

x=1n(1j=1nMx,j)2

### Constraint-II

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 −

x=1nMx,j=1forj{1,...,n}

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

j=1n(1x=1nMx,j)2

### Cost Function Calculation

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 −
Mx,i=1andMy,i±1=1

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 −

i=1nCx,yMx,i(My,i+1+My,i1)

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

E=12i=1nxyxCx,yMx,i(My,i+1+My,i1)+

[γ1x(1iMx,i)2+γ2i(1xMx,i)2]

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