论文标题
进化算法和多因素进化算法的最短路径问题
Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on Clustered Shortest-Path Tree problem
论文作者
论文摘要
在文献中，聚类的最短路径树问题（群体）是一个NP困难的问题。先前的研究经常在相对较大的空间中寻找最佳解决方案。为了提高搜索过程的性能，提出了两种方法：第一种方法寻求解决方案作为一组边缘。从原始图中，我们生成了一个新图，其顶点集的基数远小于原始图。因此，提出了一种有效的进化算法（EA）来解决群集。第二种方法寻找基于顶点的解决方案。群体的搜索空间被转换为2个嵌套搜索空间（NSS）。在高级优化中的每个候选人中，较低级别的搜索引擎将找到一个与之结合的候选者，以创建最佳解决方案。因此，引入了嵌套的本地搜索EA（N-LSEA）以搜索NSS上的最佳解决方案。当通过N-LSEA以较低级别求解此模型时，会处理各种类似的任务。因此，应用多因素进化算法，以增强这些优化的隐式遗传转移。提出的算法是在一系列数据集上进行的，与以前的科学工作相比，获得的结果表明效率较高。
In literature, Clustered Shortest-Path Tree Problem (CluSPT) is an NP-hard problem. Previous studies often search for an optimal solution in relatively large space. To enhance the performance of the search process, two approaches are proposed: the first approach seeks for solutions as a set of edges. From the original graph, we generate a new graph whose vertex set's cardinality is much smaller than that of the original one. Consequently, an effective Evolutionary Algorithm (EA) is proposed for solving CluSPT. The second approach looks for vertex-based solutions. The search space of the CluSPT is transformed into 2 nested search spaces (NSS). With every candidate in the high-level optimization, the search engine in the lower level will find a corresponding candidate to combine with it to create the best solution for CluSPT. Accordingly, Nested Local Search EA (N-LSEA) is introduced to search for the optimal solution on the NSS. When solving this model in lower level by N-LSEA, variety of similar tasks are handled. Thus, Multifactorial Evolutionary Algorithm applied in order to enhance the implicit genetic transfer across these optimizations. Proposed algorithms are conducted on a series of datasets and the obtained results demonstrate superior efficiency in comparison to previous scientific works.
