文献类型：期刊文献

英文题名：Variable Population Memetic Search: A Case Study on the Critical Node Problem

作者：Zhou, Yangming[1,2];Hao, Jin-Kao[3,4];Fu, Zhang-Hua[5,6];Wang, Zhe[1,2];Lai, Xiangjing[7]

机构：[1]East China Univ Sci & Technol, Key Lab Adv Control & Optimizat Chem Proc, Minist Educ, Shanghai 200237, Peoples R China;[2]East China Univ Sci & Technol, Sch Informat Sci & Engn, Shanghai 200237, Peoples R China;[3]Univ Angers, Dept Comp Sci, F-49045 Angers, France;[4]Inst Univ France, F-75231 Paris, France;[5]Chinese Univ Hong Kong, Shenzhen Inst Artificial Intelligence & Robot Soc, Shenzhen 518172, Peoples R China;[6]Chinese Univ Hong Kong, Inst Robot & Intelligent Mfg, Shenzhen 518172, Peoples R China;[7]Nanjing Univ Posts & Telecommun, Inst Adv Technol, Nanjing 210023, Peoples R China

年份：2021

卷号：25

期号：1

起止页码：187

外文期刊名：IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION

收录：;EI(收录号：20203309048754);WOS:【SCI-EXPANDED(收录号:WOS:000613552500014)】；

基金：This work was supported in part by the National Natural Science Foundation of China under Grant 61903144; in part by the Shanghai Sailing Program under Grant 19YF1412400; in part by the Key Project of Science and Technology Innovation 2030 Supported by the Ministry of Science and Technology of China under Grant 2018AAA0101302; in part by the Fundamental Research Funds for the Central Universities of China under Grant 222201817006; in part by the Shenzhen Science and Technology Innovation Commission under Grant JCYJ20180508162601910; in part by the Shenzhen Institute of Artificial Intelligence and Robotics for Society under Grant 2019-INT003; and in part by the Open Project of the Shenzhen Institute of Artificial Intelligence and Robotics for Society (Exploration Project 2020).

语种：英文

外文关键词：Critical node problem (CNP); local search; memetic search; population sizing

摘要：Population-based memetic algorithms have been successfully applied to solve many difficult combinatorial problems. Often, a population of fixed size is used in such algorithms to record some best solutions sampled during the search. However, given the particular features of the problem instance under consideration, a population of variable size would be more suitable to ensure the best search performance possible. In this work, we propose a variable population memetic search (VPMS), where a strategic population sizing mechanism is used to dynamically adjust the population size during the search process. Our VPMS approach starts its search from a small population of only two solutions to focus on exploitation and then adapts the population size according to the search status to continuously influence the balancing between exploitation and exploration. We illustrate an application of the VPMS approach to solve the challenging critical node problem (CNP). We show that the VPMS algorithm integrating a variable population, an effective local optimization procedure, and a backbone-based crossover operator performs very well compared to state-of-the-art CNP algorithms. The algorithm is able to discover new upper bounds for 12 instances out of the 42 popular benchmark instances while matching 23 previous best-known upper bounds.