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 Shiwei PAN;Yiming MA;Yiyuan WANG;Zhiguo ZHOU;Jinchao JI;Minghao YIN;Shuli HU

作者机构：School of Computer Science and Information TechnologyNortheast Normal UniversityChangchun 130117China Key Laboratory of Applied Statistics of MOENortheast Normal UniversityChangchun 130117China 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2023年第17卷第4期

页      面：1-14页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：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) 

主　　题：evolutionary algorithm combinatorial optimization minimum independent dominating set local search master apprentice path breaking 

摘      要：The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other *** this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called *** proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution *** 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 *** 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 *** results show that the MAE-PB algorithm achieves high *** 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 *** investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.