HEA-D: A Hybrid Evolutionary Algorithm for Diversified Top-k Weight Clique Search Problem

HEA-D: A Hybrid Evolutionary Algorithm for Diversified Top-k Weight Clique Search Problem

Jun Wu, Chu-Min Li, Yupeng Zhou, Minghao Yin, Xin Xu, Dangdang Niu

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 4821-4827. https://doi.org/10.24963/ijcai.2022/668

The diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique (DTKC) search problem with extensive applications, which extends the DTKC search problem by taking into account the weight of vertices. In this paper, we formulate DTKWC search problem using mixed integer linear program constraints and propose an efficient hybrid evolutionary algorithm (HEA-D) that combines a clique-based crossover operator and an effective simulated annealing-based local optimization procedure to find high-quality local optima. The experimental results show that HEA-D performs much better than the existing methods on two representative real-world benchmarks.
Keywords:
Search: Heuristic Search
Search: Combinatorial Search and Optimisation
Search: Evolutionary Computation
Search: Local search