For a route represented as an ordering of cities, a particle cannot move by adding a numerical displacement. In permutation-based particle swarm optimization (PSO), its velocity is an ordered sequence of swaps. Applying those swaps changes the particle’s position—its candidate route—while keeping it a permutation. section 9.4
To use velocity in a PSO update, reinterpret three familiar operations:
- Subtract two positions to obtain a sequence of swaps that transforms one permutation into the other. section 9.4
- Multiply a velocity by a constant to change its length: zero removes all swaps, a value below one truncates the sequence, and a value above one augments it by repeating swaps from its start. section 9.4
- Add a velocity to a position by performing its swaps in order; the result is the particle’s new candidate solution. section 9.4
One move in an eight-city route
Start with the route [2, 4, 6, 1, 5, 3, 8, 7]. If the velocity contains a swap of positions 1 and 4, applying it gives [1, 4, 6, 2, 5, 3, 8, 7]. A longer velocity would perform further swaps in sequence. This is a route change, not a change to the cities themselves. section 9.4
Figure 9.9 Redefined subtraction operation for permutation-based PSO
Trace how subtracting two route permutations produces the swaps used as velocity. section 9.4
The meaning of velocity depends on the search space. Continuous PSO updates a numerical velocity before changing position; binary PSO uses a sigmoid to turn velocity values into probabilities for bit updates. For permutation problems, work with swap sequences instead of applying either interpretation directly. section 9.2.1 section 9.3 section 9.4
