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.

العنوان

Journal of Mathematical and Computational Science

الناشر

SCIK Publishing Corporation

بلد الناشر

المملكة المتحدة

Indexing

Scopus

معامل التأثير

None

نوع المنشور

إلكتروني فقط

المجلد

11

السنة

2021

الصفحات

2058-2074