13,863,642 members
Add your own
alternative version

#### Stats

7.9K views
278 downloads
11 bookmarked
Posted 1 Aug 2017
Licenced CPOL

# Solving the Travelling Salesman Problem With a Particle Swarm Optimizer

, 1 Aug 2017
A way of adapting a particle swarm optimizer to solve the travelling salesman problem.

## Introduction

The Particle Swarm Optimizer employs a form of artificial intelligence to solve problems. It is particularly good at finding solutions to functions that use multiple, continuously variable, values. This piece is concerned with modifying the algorithm to tackle problems, such as the travelling salesman problem, that use discrete, fixed values.

## Background

Particle Swarm Optimizers (PSO) were discussed and demonstrated in an earlier article. As stated in that piece, the basic idea is to move (fly) a group (swarm) of problem solving entities (particles) throughout the range of possible solutions to a problem. This range is known as the problem space. The movement of particles within the problem space has a random component but is mainly guided by three factors.

1. The present position of the particle.
2. The best position found by the particle, known as personal best or pBest.
3. The best position found  in the swarm, known a global best or gBest.

Modern variations of the algorithm use a local best position rather than a global best. This tends to ensure better exploration of the problem space and prevents too rapid a convergence to some regional minimal value. In these variations, the swarm is divided into  groups of particles known as informers. Information is exchanged between every member of a group to determine the local best position for that group The particles are reorganised into new groups if a certain number of iterations pass without the global best value changing.

## The Original PSO Formula.

The formula for dealing with continuously variable, values is
Vid=vid*W+C1*rand(pid-xid)+C2*Rand(pgd-xid)
where
vid is the current velocity and Vid is the new velocity. The velocity, in this case, is the amount by which the position is changed.
W, C1,C2 are constants. The approximate values for the constants are C1=C2=1.4 W=0.7
Rand and rand are two randomly generated doubles >=0 and <1
xid is the current position, pid is the personal best position and pgd is the global best position. The position is then updated by adding the new velocity to it. xid=xid+Vid. This formula is applied to each dimension of the position.

## The Travelling Salesman Problem.

The problem is to find the shortest distance that a salesman has to travel to visit every city on his route only once and to arrive back at the place he started from. It’s not a totally academic exercise. A similar situation arises in the design of wiring diagrams and printed circuit boards. It is a well-documented problem with many standard example lists of cities. There have been lots of papers written on how to use a PSO to solve this problem. The method used here is based on an article named, A combination of genetic algorithm and particle swarm optimization method for solving traveling salesman problem. By Keivan Borna and Razieh Khezri

## Using a PSO to Update the Salesman’s Route.

As we have seen, the new position of a particle is influenced to varying degrees by three factors. They are, the particle’s present position, its best previous position and the best position found within its group. The salesman's route can be updated by dividing it into three sections, one for each of the three factors, where the size of each section is determined by that section's relative strength. The sections can then be joined together to form an updated route. But there is a problem with this approach. Cities can only be listed once and sections may contain cities that have already been listed in a previous route section. So there needs to be mechanism to ensure that every city is added to the route and that no city is duplicated in the process.

In the diagram above, the section selected from the Current Route is 6,3,5. These cities are added to the new route. The Personal Best Route has the section 1,3,2 selected. Selection 3 has already been added, so only cities 1 and 2 are added. The Local Best Route has section 7,3 selected. City 3 has already been added so only city 7 gets selected. Finally, the two cities that have not been selected, cities 0 and 4, are added to the new route in the order that they appear in the Current Route.
The selection of cities to be added is facilitate by using BitArrays. One `BitArray` is used as an availability mask with all the bits being set initially to true. Another `BitArray` is used as a Selection Mask for the segment to be added. To illustrate this, consider the situation after the Current Segment has been added.

## The Example Application.

### Random Number Generation.

The application generates a lot of random numbers so it was worth looking to find the best random number generator (RNG). After a lot of research, I found that `System.Random` was as good as any and better than most. If you are interested in exploring the quality of RNGs, there is a link here to the Diehard series of 15 tests written in C#. For some reason, I couldn’t get test 2 to run, perhaps I was a little short of the 80 million bits required for the sample data.

### The Intercity Lookup Table.

To find the distance between two cities, the app uses a lookup table in the form of a two dimensional matrix. For example, to get the distance between city A and city B. Look up the row for city A and the column for city B. The distance is given at the intersection of the row and the column. The table was implemented in the form of an Indexer so that it became, in effect, a read-only two dimensional array. It was thought that, as the table was shared by multiple objects, it was best to make it immutable

```public class LookUpTable<T> : ILookUpTable<T>
{
public LookUpTable(T[,] arr)
{
this.arr = arr;
}

private readonly T[,] arr;

// The indexer allows the use of [,] operator.
public T this[int r, int c]
{
get
{
return arr[r, c];
}
}

public int RowCount
{
get
{
return arr.GetLength(0);
}
}
public int ColCount
{
get
{
return arr.GetLength(1);
}
}
}```

### Implementation

The sample application implements the swarm as an array of `TspParticle` objects. It uses a `SwarmOptimizer` to optimize the swarm. The optimizer’s attributes, such as swarm size and number of epochs, are read in from the app.config file.

```public int Optimize(ITspParticle[] swarm, PsoAttributes psoAttributes)
{
this.BestGlobalItinery = swarm[0].CurrentRoute.Clone();
int[] particleIndex = this.InitArray(psoAttributes.SwarmSize);
int epoch = 0;
int staticEpochs = 0;
while (epoch < psoAttributes.MaxEpochs)
{
bool isDistanceImproved = false;
foreach (ITspParticle particle in swarm)
{
double distance = particle.Optimize(psoAttributes);
if (distance < this.BestGlobalItinery.TourDistance)
{
particle.CurrentRoute.CopyTo(this.BestGlobalItinery);
isDistanceImproved = true;
this.consoleWriter.WriteDistance(distance);
}
}
if (!isDistanceImproved)
{
staticEpochs++;
if (staticEpochs == psoAttributes.MaxStaticEpochs)
{
this.UpdateInformers(swarm, particleIndex, psoAttributes.MaxInformers);
staticEpochs = 0;
}
}
epoch++;
}
return (int)this.BestGlobalItinery.TourDistance;
}
```

Each particle contains references to its `CurrentRoute`, `PersonalBestRoute` and `LocalBestRoute` in the form of integer arrays containing the order of the cities to be visited, where the last city listed links back to the first city. The routes are updated using a `ParticleOptimizer`.

```public int[] GetOptimizedDestinationIndex(
IRoute currRoute,
IRoute pBRoute,
IRoute lBRoute,
PsoAttributes psoAttribs)
{
//update all the velocities using the appropriate PSO constants
double currV = routeManager.UpdateVelocity(currRoute, psoAttribs.W, 1);
double pBV = routeManager.UpdateVelocity(pBRoute, psoAttribs.C1, randomFactory.NextRandomDouble());
double lBV = routeManager.UpdateVelocity(lBRoute, psoAttribs.C2, randomFactory.NextRandomDouble());
double totalVelocity = currV + pBV + lBV;

//update the Segment size for each Route
currRoute.SegmentSize = routeManager.GetSectionSize(currRoute, currV, totalVelocity);
pBRoute.SegmentSize = routeManager.GetSectionSize(pBRoute, pBV, totalVelocity);
lBRoute.SegmentSize = routeManager.GetSectionSize(lBRoute, lBV, totalVelocity);
return routeManager.AddSections(new[] { lBRoute, pBRoute, currRoute });
}```

A `RouteManager` is responsible for joining the section of the `CurrentRoute`, `PersonalBestRoute` and `LocalBestRoute` to form the new `CurrentRoute`.

```//updates a particle's velocity. The shorter the total distance the greater the velocity
public double UpdateVelocity(IRoute particleItinery, double weighting, double randomDouble)
{
return (1 / particleItinery.TourDistance) * randomDouble * weighting;
}

//Selects a section of the route with a length  proportional to the particle's
// relative velocity.
public int GetSectionSize(IRoute particleItinery, double segmentVelocity, double totalVelocity)
{
int length = particleItinery.DestinationIndex.Length;
return Convert.ToInt32(Math.Floor((segmentVelocity / totalVelocity) * length));
}
```

Lastly, the `RouteManager` uses a `RouteUpdater` to handle the building of the updated route.

```//sets the selected BitArray mask so that
//only cities that have not been added already are available
//pointer is set to the start of the segment
public void SetSelectedMask(int pointer, IRoute section)
{
int p = pointer;
this.SelectedMask.SetAll(false);
//foreach city in the section set the appropriate bit
// in the selected mask
for (int i = 0; i < section.SegmentSize; i++)
{
//set bit to signify that city is to be added if not already used
this.SelectedMask[section.DestinationIndex[p]] = true;

p++;
//p is a circular pointer in that it moves from the end of the route
// to the start
if (p == section.DestinationIndex.Length)
{
p = 0;
}
}
//in the AvailabilityMask, true=available, false= already used
//remove cities from the SelectedMask  that have already been added
this.SelectedMask.And(this.AvailabilityMask);
}

//Updates the  new route by adding cities,sequentially from the route section
//providing the cities are not already present
public void SetDestinationIndex(int startPosition, IRoute section)
{

int p = startPosition;
for (int i = 0; i < section.SegmentSize; i++)
{
if (this.SelectedMask[section.DestinationIndex[p]])
{
this.destinationIndex[this.destinationIndexPointer] = section.DestinationIndex[p];
this.destinationIndexPointer++;
}
p++;
if (p == section.DestinationIndex.Length)
{
p = 0;
}
}
//update the City AvailabilityMask
//sets bits that represent cities that have been included to false
this.AvailabilityMask.Xor(this.SelectedMask);
}
```

## Test Results

A test of 100 swarm optimizations was carried out using the following parameters,
Test File Pr76DataSet.xml, 76 Cities, Correct Solution is at 108,159
Swarm Size (number of particles ) =80
Number of Epochs per swarm optimization =30,000
Number of Informers in a group = 8
Number of Static Epochs before regrouping the informers= 250
Weightings W=0.7 C1=1.4 C2 =1.4
Results
Correct Solutions Found = 7
Highest Error= 6%
Average Error = 2%
Time for 1 Swarm Optimization = 1 minute 30 seconds.

## Conclusion.

A Particle swarm optimizer can be used to solve highly complicated problems by multiple repetitions of a simple algorithm.

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## About the Author

 Student Wales
No Biography provided

 Pro

## Comments and Discussions

 First Prev Next
 A quick comparison with other approaches would be nice too rtybase23-Oct-17 1:27 rtybase 23-Oct-17 1:27
 Re: A quick comparison with other approaches would be nice too George Swan1-Nov-17 21:29 George Swan 1-Nov-17 21:29
 Pictures would help Andrew Kirillov9-Sep-17 3:35 Andrew Kirillov 9-Sep-17 3:35
 Re: Pictures would help George Swan9-Sep-17 7:56 George Swan 9-Sep-17 7:56
 Re: Pictures would help KarstenK11-Sep-17 23:47 KarstenK 11-Sep-17 23:47
 Last Visit: 19-Feb-19 0:55     Last Update: 19-Feb-19 0:55 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web05 | 2.8.190214.1 | Last Updated 2 Aug 2017
Article Copyright 2017 by George Swan
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid