A Particle Swarm Optimisation Approach to Graph Permutations

Abstract

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 optimalityc criterionforthe distributed network. Thesearchforglobally 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 deviationfunction 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.