# 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 8^{8} (or, 16,777,216) possible combinations, but this algorithm can find them in less than 8^{3}, and sometimes less than 8^{2}!

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