A new heuristic algorithm, PROBE_BA, which is based on the recently introduced metaheuristic paradigm population- reinforced optimization-based exploration (PROBE), is proposed for solving the Graph Partitioning Problem. The "exploration" part of PROBE_BA is implemented by using the differential-greedy algorithm of Battiti and Bertossi and a modification of the Kernighan-Lin algorithm at the heart of Bui and Moon's genetic algorithm BFS _GBA. Experiments are used to investigate properties of PROBE and show that PROBE_BA compares favorably with other solution methods based on genetic algorithms, randomized reactive tabu search, or more specialized multilevel partitioning techniques. In addition, PROBE_BA finds new best cut values for 10 of the 34 instances in Walshaw's graph partitioning archive.
No takes yet. Share an insight, caveat, or question.
Chardaire et al. (2007) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: