Improving Local Search Algorithms via Probabilistic Configuration Checking

• Main Authors: Luo, Weilin, Ye, Rongzhen, Wan, Hai, Cai, Shaowei, Fang, Biqing, Zhang, Delong
• Format: Conference Proceeding
• Language: English
• ISSN: 2159-5399; 2374-3468
• DOI: 10.1609/aaai.v36i9.21269

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.