.png){kind=icon}
返回
An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s11704-022-2023-7.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
evolutionary algorithm
combinatorial optimization
minimum independent dominating set
local search
master apprentice
path breaking
期刊
IF:
4.6
论文数:
1.6K
被引数:
2.8K
机构
引用论文
Reduced white matter microstructural integrity correlates with cognitive deficits in minimal hepatic encephalopathy轻度肝性脑病中白质微结构完整性降低与认知缺陷相关.png)
Gut
GutIF0
PREAI
分享收藏
分享收藏Preparations and Polymerizations ofp-Substituted Phenyl Vinyl Sulfides. Vinyl Polymerization 168
PREAI
分享收藏
查看更多内容