C++ Neural Networks and Fuzzy Logic by Valluru B. Rao M&T Books, IDG Books Worldwide, Inc. ISBN: 1558515526   Pub Date: 06/01/95

Performance of the Hopfield Network

Let us now look at Hopfield and Tank’s approach at solving the TSP.

Hopfield and Tank Example

The Hopfield network’s use in solving the traveling salesperson problem is a pioneering effort in the use of the neural network approach for this problem. Hopfield and Tank’s example is for a problem with 10 cities. The parameters used were, A₁= 500, A₂ = 500, A₃ = 200, A₄ = 500, τ = 1, λ = 50, and m = 15. A good solution corresponding to a local minimum for E is the expected, if not the best, solution (global minimum). An annealing process could be considered to move out of any local minimum. As was mentioned before, the traveling salesperson problem is one of those problems for which a single approach cannot be found that will be successful in all cases. There isn’t very much guidance as to how to choose the parameters in general for the use of the Hopfield network to solve the traveling salesperson problem.

C++ Implementation of the Hopfield Network for the Traveling Salesperson Problem

We present a C++ program for the Hopfield network operation for the traveling salesperson problem. The header file is in the Listing 15.1, and the source file is in the Listing 15.2. A tsneuron class is declared for a neuron and a network class for the network. The network class is declared a friend in the tsneuron class. The program follows the procedure described for setting inputs, connection weights, and updating.

Program Details

The following is a listing of the characteristics of the C++ program along with definitions and/or functions.

•  The number of cities, the number of iterations, and the distances between the cities are solicited from the user.

•  The distances are taken as integer values. If you want to use real numbers as distances, the type for distance matrix needs to be changed to float, and corresponding changes are needed for calcdist ( ) function, etc.

•  tourcity and tourorder arrays keep track of the cities that have to be covered and the order in which it is to be done.

•  A neuron corresponds to each combination of a city and its order in the tour. The ith city visited in the order j , is the neuron corresponding to the element j + i*n, in the array for neurons. Here n is the number of cities. The i and the j vary from 0 to n – 1. There are n² neurons.

•  mtrx is the matrix giving the weights on the connections between the neurons. It is a square matrix of order n².

•  An input vector is generated at random in the function main ( ), and is later referred to as ip

•  asgninpt ( ) function presents the input vector ip to the network and determines the initial activations of the neurons.

•  getacts ( ) function updates the activations of the neurons after each iteration.

•  getouts ( ) function computes the outputs after each iteration. la is used as abbreviation for lambda in its argument.

•  iterate ( ) function carries out the number of iterations desired.

•  findtour ( ) function determines the tour orders of cities to be visited using the outputs of the neurons. When used at the end of the iterations, it gives the solution obtained for the traveling salesperson problem.

•  calcdist ( ) function calculates the distance of the tour in the solution.

Listing 15.1 Header file for the C++ program for the Hopfield network for the traveling salesperson problem

//trvslsmn.h  V. Rao,  H. Rao
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>

#define MXSIZ 11

class tsneuron
        {
        protected:
        int cit,ord;
        float output;
        float activation;
        friend class network;

        public:
        tsneuron() { };
        void getnrn(int,int);
        };

class network
        {
        public:
        int  citnbr;
        float pra,prb,prc,prd,totout,distnce;

        tsneuron (tnrn)[MXSIZ][MXSIZ];
        int dist[MXSIZ][MXSIZ];
        int tourcity[MXSIZ];
        int tourorder[MXSIZ];
        float outs[MXSIZ][MXSIZ];
        float acts[MXSIZ][MXSIZ];
        float mtrx[MXSIZ][MXSIZ];
        float citouts[MXSIZ];
        float ordouts[MXSIZ];

        network() { };
        void getnwk(int,float,float,float,float);
        void getdist(int);
        void findtour();
        void asgninpt(float *);
        void calcdist();
        void iterate(int,int,float,float,float);
        void getacts(int,float,float);
        void getouts(float);

//print functions

        void prdist();
        void prmtrx(int);
        void prtour();
        void practs();
        void prouts();
        };