Sub swarm and crossbreed strategy particle swarm optimization for the travelling salesman problem

Particle swarm optimization (PSO) a novel simulated evolutionary algorithm, which is based on observations of real seagull swarm behaviors, provides a new method for complicated combinatorial optimization problems. This paper presents a novel algorithm, combining PSO structure and trip building method of ACS named the swarm and crossbreed strategy PSO (SCPSO). It is an attempt to expand PSO to TSP problems. By adding sub-swarm division and crossbreed strategy, our algorithm simulates real life-form crossbreed behaviors. And in this paper, two crossbreed operators and select mechanism of crossbreed particles are designed in order to improve algorithm performance. Experiment results show that our algorithm is efficient. With optimization information spread within sub-swarms, diversity of particles is improved and the whole particle swarm converges faster with greater accuracy. When approaching TSP problems, sub-swarm and crossbreed- PSO(SCPSO) works much better than single swarm PSO and some other algorithms. The final results have reached the optimal solutions recorded in TSPLIB.