NSGAII With Local Search Based Heavy Perturbation for Bi-Objective Weighted Clique Problem

Abstract

This paper focuses on the clique problem of a weighted graph where weights of vertices can be either positive or negative (WG-PN). Two objectives, the size and the total weight of a clique, are considered. In particular, the larger size in terms of set inclusion and the higher total weight a clique is, the better it is. This problem is termed BiOWCP which is a multi-objective combinatorial optimization problem that contains conflict objectives. We show that BiOWCP cannot be translated into the clique problem of a weighted graph with positive vertex weights (WG-P) via a straight forward transformation, which highlights the difficulty of BiOWCP. We propose a heavy perturbation (HP)-based NSGAII (nondominated sorting genetic algorithm II) algorithm HP-NSGAII for the problem, where the perturbation is done by either improving a selected elitist with a local search procedure or swapping its left and right parts. Benchmarks for BiOWCP were adapted from the DIMACS set. Extensive experiments were carried out for different ratios of the heavy perturbation effort to the total search effort. Computational results show that HP-NSGAII is superior to NSGAII on many problems with respect to the hyper volume indicator and the set coverage indicator.

Keywords

• Clique problem
• evolutionary algorithm
• multi-objective combinatorial optimization
• negative vertex weight
• weighted graph