An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem  

作　　者：Shiwei PAN Yiming MA Yiyuan WANG Zhiguo ZHOU Jinchao JI Minghao YIN Shuli HU 

机构地区：[1]School of Computer Science and Information Technology,Northeast Normal University,Changchun 130117,China [2]Key Laboratory of Applied Statistics of MOE,Northeast Normal University,Changchun 130117,China

出　　处：《Frontiers of Computer Science》2023年第4期1-14,共14页中国计算机科学前沿（英文版）

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.61806050,61972063,61976050);the Fundamental Research Funds for the Central Universities(2412020FZ030,2412019ZD013,2412019FZ051);Jilin Science and Technology Association(QT202005).

摘　　要：The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB.The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting.It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps.We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications.The results show that the MAE-PB algorithm achieves high performance.In particular,for the classical benchmarks,the MAE-PB algorithm obtains the best-known results for seven instances,whereas for several massive graphs,it improves the best-known results for 62 instances.We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.

关 键 词：evolutionary algorithm combinatorial optimization minimum independent dominating set local search master apprentice path breaking 

分 类 号：O15[理学—数学]