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

- The present position of the particle.
- The best position found by the particle, known as personal best or pBest.
- 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;
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)
{
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;
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`

.

public double UpdateVelocity(IRoute particleItinery, double weighting, double randomDouble)
{
return (1 / particleItinery.TourDistance) * randomDouble * weighting;
}
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.

public void SetSelectedMask(int pointer, IRoute section)
{
int p = pointer;
this.SelectedMask.SetAll(false);
for (int i = 0; i < section.SegmentSize; i++)
{
this.SelectedMask[section.DestinationIndex[p]] = true;
p++;
if (p == section.DestinationIndex.Length)
{
p = 0;
}
}
this.SelectedMask.And(this.AvailabilityMask);
}
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;
}
}
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.