Solving the Travelling Salesman Problem with a Particle Swarm Optimizer

• Download demo - 116.2 KB

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