A Particle Swarm Optimisation Approach to Graph Permutations

Particle swarm optimisers (PSO) can be used for graph permutation and optimal combinatorial problems. Graphs are a powerful mathematical tool that can be used to represent multi-agent systems such as multi-robotic systems and distributed networks. The arrangement of nodes in a graph can sometimes be required to satisfy an optimality criterion for the distributed network. The search for globally optimal graph permutations is an NP-complete problem. Although exhaustive search techniques can yield the global optimum, they are often computationally expensive. PSO is a relatively new heuristic search algorithm that can be modified to accommodate for the nature of optimal combinatorial and permutation problems. In this paper, a modified discrete particle swarm optimiser is presented that can be used to find optimal graph permutations efficiently for large population sets. An energy deviation function was used to describe the associated morph between two graph configurations and preserve permutation invariant shape abstractions. The PSO algorithm demonstrated exceptional performance to exhaustive search techniques and is a promising search algorithm for the graph reconfiguration problem.