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.

Title

Journal of Mathematical and Computational Science

Publisher

SCIK Publishing Corporation

Publisher Country

United Kingdom

Indexing

Scopus

Impact Factor

None

Publication Type

Online only

Volume

11

Year

2021

Pages

2058-2074