Click here to Skip to main content
13,252,065 members (57,119 online)
Click here to Skip to main content
Add your own
alternative version

Stats

4.8K views
109 downloads
8 bookmarked
Posted 1 Aug 2017

Solving the Travelling Salesman Problem With a Particle Swarm Optimizer

, 1 Aug 2017
Rate this:
Please Sign up or sign in to vote.
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)

Share

About the Author

George Swan
Student
Wales Wales
No Biography provided

You may also be interested in...

Pro

Comments and Discussions

 
QuestionA quick comparison with other approaches would be nice too Pin
rtybase23-Oct-17 1:27
memberrtybase23-Oct-17 1:27 
AnswerRe: A quick comparison with other approaches would be nice too Pin
George Swan1-Nov-17 21:29
memberGeorge Swan1-Nov-17 21:29 
QuestionPictures would help Pin
Andrew Kirillov9-Sep-17 3:35
memberAndrew Kirillov9-Sep-17 3:35 
AnswerRe: Pictures would help Pin
George Swan9-Sep-17 7:56
memberGeorge Swan9-Sep-17 7:56 
GeneralRe: Pictures would help Pin
KarstenK11-Sep-17 23:47
memberKarstenK11-Sep-17 23:47 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

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