Hybridization of particle swarm optimization and simulated annealing for maximum partition problem

Abstract

The maximum partition problem (MPP) is to divide the set of nodes in directed weighted graph into two disjoint subsets such that the sum of weights of edges crossing from one subset of the partition to the other is maximized. The MPP is NP-hard. Hence, this paper presents a hybrid discrete particle swarm optimization (DPSO) simulated annealing (SA) algorithm to solve MPP. The proposed algorithm first applies DPSO to the problem until improvement in fitness slows down (stagnates). Then, the algorithm uses SA augmented with a heuristic method to improve the fitness of the solution obtained from DPSO. Experiments on randomly generated graphs of different size show that the proposed algorithm produces better partitions than conventional DPSO. Additionally, the proposed algorithm converges to near optimal solutions faster than conventional DPSO.