文献类型：期刊文献

英文题名：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]; Wang, Zhe[1]; Lai, Xiangjing[6]

机构：[1] School of Information Science and Engineering, East China University of Science and Technology, 130 Meilong Road, Shanghai, 200237, China; [2] Key Laboratory of Advanced Control and Optimization for Chemical Processes, Ministry of Education; [3] Department of Computer Science, LERIA, Université d'Angers, 2 Boulevard Lavoisier, Angers, 49045, France; [4] Institut Universitaire de France, 1 rue Descartes, Paris, 75231, France; [5] Robotics Laboratory for Logistics Service, Institute of Robotics and Intelligent Manufacturing, Chinese University of Hong Kong, Shenzhen Institute of Artificial Intelligence and Robotics for Society, Shenzhen, 518172, China; [6] Institute of Advanced Technology, Nanjing University of Posts and Telecommunications, Nanjing, 210023, China

年份：2019

外文期刊名：arXiv

收录：EI(收录号：20200232836)

语种：英文

外文关键词：Benchmarking

摘要：Population-based memetic algorithms have been successfully applied to solve many difficult combinatorial problems. Often, a population of fixed size was 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 variable population memetic search (VPMS), where a strategic population sizing mechanism is used to dynamically adjust the population size during the memetic 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 (called diversified late acceptance search) 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 13 instances out of the 42 popular benchmark instances, while matching 23 previous best-known upper bounds. Copyright ? 2019, The Authors. All rights reserved.