Improving Local Search Algorithms via Probabilistic Configuration Checking

Configuration checking (CC) has been confirmed to alleviate the cycling problem in local search for combinatorial optimization problems (COPs). When using CC heuristics in local search for graph problems, a critical concept is the configuration of the vertices. All existing CC variants employ either 1- or 2-level neighborhoods of a vertex as its configuration. Inspired by the idea that neighborhoods with different levels should have different contributions to solving COPs, we propose the probabilistic configuration (PC), which introduces probabilities for neighborhoods at different levels to consider the impact of neighborhoods of different levels on the CC strategy. Based on the concept of PC, we first propose probabilistic configuration checking (PCC), which can be developed in an automated and lightweight favor. We then apply PCC to two classic COPs which have been shown to achieve good results by using CC, and our preliminary results confirm that PCC improves the existing algorithms because PCC alleviates the cycling problem.

Authors

• Weilin Luo School of Computer Science and Engineering, Sun Yat-sen University
• Rongzhen Ye School of Computer Science and Engineering, Sun Yat-sen University
• Hai Wan Tsinghua University
• Shaowei Cai Institute of Software, Chinese Academy of Sciences
• Biqing Fang
• Delong Zhang

Keywords

No keywords are indexed for this paper.