Particle Swarm Optimization .*;

Travelling Salesperson Problem Example 1

This is a rendition of the classic Traveling Salesman Problem, where the shortest tour needs to be found among all cites without visiting the same one twice.  The algorithm works out the minimum Cartesian distance through eight cities named 0, 1, 2, 3, 4, 5, 6 and 7.  There are 88 (or, 16,777,216) possible combinations, but this algorithm can find them in less than 83, and sometimes less than 82!

The cities' locations are (30, 5), (40, 10), (40, 20), (29, 25), (19, 25), (9, 19), (9, 9), (20, 5).  This is roughly a circle; something easy to see on a graph and check the algorithm's solutions with. All manner of combinations using eight digit strings of 0 through 7 are explored to find the one that represents the shortest distance (i.e.; 01234567).  By hand, I've found the solution to be about 86.6299, which is the target value of the algorithm.

To simplify this example, there is no starting or ending point, and it doesn't matter which direction the tour travels in (i.e.; forward or backward).  For instance, a solution that looks like 34567012 is valid because it travels forward from 3 and around to 2.  The solution 76543210 is equally valid, it just goes backward from 7 to 0.

I decided to take a slightly different take on the PSO algorithm with this one. I added the global worst to the global variables. The velocity score is calculated using the global worst, defining velocity as the measure of how bad each particle is doing (as opposed to how good).

Modifying data is done by swapping digits within each particles own data set. The amount of swapping depend on how bad it's doing (i.e.; velocity).

Particles are slowly pushed towards the global best by copying pieces of the next best particle's data (single-sighted topology).

Swapping and copying are done to all particles except the global best.

In this example, only three variables can be experimented with:

  • PARTICLE_COUNT - number of particles employed in the test.
  • V_MAX - maximum velocity change allowed.
  • MAX_EPOCHS - number of iterations for the algorithm.

 

Example Results 1

PARTICLE_COUNT = 10, V_MAX = 4, MAX_EPOCHS = 10000.

Route: 2, 3, 4, 6, 5, 7, 0, 1, Distance: 99.93584193997158
Route: 2, 7, 3, 4, 6, 5, 0, 1, Distance: 132.21887327932137
Route: 6, 4, 7, 3, 5, 0, 1, 2, Distance: 161.01823909844032
Route: 4, 7, 0, 5, 2, 6, 1, 3, Distance: 178.79093664436735
Route: 3, 6, 1, 5, 0, 4, 7, 2, Distance: 194.08096028878091
Route: 4, 6, 0, 7, 2, 1, 5, 3, Distance: 148.4061583915042
Route: 7, 0, 1, 2, 3, 4, 5, 6, Distance: 86.62998956150375
Route: 5, 2, 3, 6, 7, 0, 1, 4, Distance: 139.06558715090466
Route: 7, 2, 3, 6, 0, 4, 5, 1, Distance: 171.45598237170142
Route: 2, 3, 0, 4, 6, 1, 5, 7, Distance: 179.90206048967966
Changes for particle 1: 2
Changes for particle 2: 2
Changes for particle 3: 2
Changes for particle 4: 3
Changes for particle 5: 3
Changes for particle 6: 3
Changes for particle 7: 3
Changes for particle 8: 3
Changes for particle 9: 4
epoch number: 85
Target reached.
Shortest Route: 7, 0, 1, 2, 3, 4, 5, 6, Distance: 86.62998956150375

 

Example Results 2

PARTICLE_COUNT = 4, V_MAX = 4, MAX_EPOCHS = 10000. Fewer workers usually means longer to finish.

Route: 2, 0, 7, 6, 5, 4, 3, 1, Distance: 99.99543531546844
Route: 6, 0, 7, 1, 2, 3, 4, 5, Distance: 105.73803621780542
Route: 0, 1, 2, 3, 4, 5, 6, 7, Distance: 86.62998956150375
Route: 7, 0, 3, 4, 5, 6, 1, 2, Distance: 127.70301302273303
Changes for particle 1: 3
Changes for particle 2: 3
Changes for particle 3: 4
epoch number: 801
Target reached.
Shortest Route: 0, 1, 2, 3, 4, 5, 6, 7, Distance: 86.62998956150375

 

Example Results 2

PARTICLE_COUNT = 10, V_MAX = 8, MAX_EPOCHS = 10000. Increasing the velocity using the implementation in this code has little effect.

Route: 0, 7, 5, 6, 4, 3, 2, 1, Distance: 99.93584193997157
Route: 1, 0, 7, 6, 5, 4, 3, 2, Distance: 86.62998956150375
Route: 6, 4, 1, 5, 2, 3, 0, 7, Distance: 161.78381796573566
Route: 5, 2, 3, 0, 4, 1, 6, 7, Distance: 172.28187399281768
Route: 1, 6, 4, 0, 2, 3, 5, 7, Distance: 162.1209488352703
Route: 0, 1, 3, 2, 7, 5, 6, 4, Distance: 136.36234159873652
Route: 0, 3, 6, 5, 1, 2, 7, 4, Distance: 165.76791494289756
Route: 6, 5, 4, 7, 0, 3, 1, 2, Distance: 133.2067162232275
Route: 7, 3, 1, 2, 4, 6, 5, 0, Distance: 136.2266417744836
Route: 6, 5, 7, 3, 1, 4, 2, 0, Distance: 155.1366049017671
Changes for particle 1: 4
Changes for particle 2: 6
Changes for particle 3: 6
Changes for particle 4: 6
Changes for particle 5: 7
Changes for particle 6: 7
Changes for particle 7: 7
Changes for particle 8: 7
Changes for particle 9: 8
epoch number: 221
Target reached.
Shortest Route: 1, 0, 7, 6, 5, 4, 3, 2, Distance: 86.62998956150375

 

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}