Zhang Shufan, Mao Jianlin, Wang Niya, Li Dayan, Ju Chengan
Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China.
Entropy (Basel). 2022 Dec 31;25(1):87. doi: 10.3390/e25010087.
The quadratic minimum spanning tree problem (QMSTP) is a spanning tree optimization problem that considers the interaction cost between pairs of edges arising from a number of practical scenarios. This problem is NP-hard, and therefore there is not a known polynomial time approach to solve it. To find a close-to-optimal solution to the problem in a reasonable time, we present for the first time a clustering-enhanced memetic algorithm (CMA) that combines four components, i.e., (i) population initialization with clustering mechanism, (ii) a tabu-based nearby exploration phase to search nearby local optima in a restricted area, (iii) a three-parent combination operator to generate promising offspring solutions, and (iv) a mutation operator using Lévy distribution to prevent the population from premature. Computational experiments are carried on 36 benchmark instances from 3 standard sets, and the results show that the proposed algorithm is competitive with the state-of-the-art approaches. In particular, it reports improved upper bounds for the 25 most challenging instances with unproven optimal solutions, while matching the best-known results for all but 2 of the remaining instances. Additional analysis highlights the contribution of the clustering mechanism and combination operator to the performance of the algorithm.
二次最小生成树问题（QMSTP）是一个生成树优化问题，它考虑了许多实际场景中边对之间的交互成本。这个问题是NP难问题，因此不存在已知的多项式时间方法来解决它。为了在合理的时间内找到接近最优的解决方案，我们首次提出了一种聚类增强的混合算法（CMA），它结合了四个组件，即：（i）具有聚类机制的种群初始化，（ii）基于禁忌的附近探索阶段，在受限区域内搜索附近的局部最优解，（iii）一个三亲组合算子，用于生成有前途的后代解，以及（iv）一个使用 Lévy 分布的变异算子，以防止种群早熟。对来自3个标准集的36个基准实例进行了计算实验，结果表明，所提出的算法与现有最先进的方法具有竞争力。特别是，它报告了25个最具挑战性的未经验证最优解实例的改进上界，而对于其余实例中除2个之外的所有实例，它都与已知的最佳结果相匹配。进一步的分析突出了聚类机制和组合算子对算法性能的贡献。
