Zhou Yangming, Hao Jin-Kao, Glover Fred
IEEE Trans Cybern. 2019 Oct;49(10):3699-3712. doi: 10.1109/TCYB.2018.2848116. Epub 2018 Jul 4.
Critical node problems (CNPs) involve finding a set of critical nodes from a graph whose removal results in optimizing a predefined measure over the residual graph. As useful models for a variety of practical applications, these problems are computationally challenging. In this paper, we study the classic CNP and introduce an effective memetic algorithm for solving CNP. The proposed algorithm combines a double backbone-based crossover operator (to generate promising offspring solutions), a component-based neighborhood search procedure (to find high-quality local optima), and a rank-based pool updating strategy (to guarantee a healthy population). Extensive evaluations on 42 synthetic and real-world benchmark instances show that the proposed algorithm discovers 24 new upper bounds and matches 15 previous best-known bounds. We also demonstrate the relevance of our algorithm for effectively solving a variant of the classic CNP, called the cardinality-constrained CNP. Finally, we investigate the usefulness of each key algorithmic component.
关键节点问题（CNP）涉及从一个图中找到一组关键节点，移除这些节点会使剩余图上的预定义度量得到优化。作为适用于各种实际应用的有用模型，这些问题在计算上具有挑战性。在本文中，我们研究经典的关键节点问题，并引入一种有效的混合算法来求解关键节点问题。所提出的算法结合了基于双骨干的交叉算子（用于生成有前景的后代解）、基于组件的邻域搜索过程（用于找到高质量的局部最优解）以及基于排名的种群更新策略（用于保证种群的健康）。对42个合成和真实世界基准实例的广泛评估表明，所提出的算法发现了24个新的上界，并与15个先前已知的最佳界相匹配。我们还证明了我们的算法对于有效求解经典关键节点问题的一个变体——基数约束关键节点问题的相关性。最后，我们研究了每个关键算法组件的有用性。
