期刊
ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE
卷 100, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.engappai.2021.104187
关键词
Multifactorial Evolutionary Algorithm; Clustered Shortest-Path Tree Problem; Evolutionary Algorithms; Multifactorial optimization
类别
资金
- Vingroup Joint Stock Company
- Domestic Master/PhD Scholarship Programme of Vingroup Innovation Foundation (VINIF) , Viet Nam
- Vingroup Big Data Institute (VINBIGDATA) , Viet Nam
- Ministry of Education and Training, Vietnam [B2021-TTB-01]
- U.S. Army Combat Capabilities Development Command (CCDC) Pacific, United States [W90GQZ-93290007]
- U.S. Army CCDC Army Research Laboratory (ARL) , United States [W90GQZ-93290007]
This paper presents an MFEA-based approach to address the CluSPT problem, utilizing Dijkstra's algorithm and evolutionary operators to construct spanning trees, balancing the advantages of exact and approximate algorithms. Experimental results demonstrate the effectiveness of the proposed algorithm over existing heuristic algorithms and suggests a potential influential factor for further study.
The Clustered Shortest-Path Tree Problem (CluSPT) plays an important role in various types of optimization problems in real-life. Recently, some Multifactorial Evolutionary Algorithms (MFEAs) have been introduced to deal with the CluSPT, but these researches still have some shortcomings, such as evolution operators only perform on complete graphs and huge resource consumption for finding the solution on large search spaces. To overcome these limitations, this paper describes an MFEA-based approach to solve the CluSPT. The proposed algorithm utilizes Dijkstra?s algorithm to construct the spanning trees in clusters while using evolutionary operators for building the spanning tree connecting clusters. This approach takes advantage of both exact and approximate algorithms, so it enables the algorithm to function efficiently on complete and sparse graphs alike. Furthermore, evolutionary operators such as individual encoding and decoding methods are also designed with great consideration regarding performance and memory usage. We have included proof of the repairing method?s efficacy in ensuring all solutions are valid. We have conducted tests on various types of Euclidean instances to assess the effectiveness of the proposed algorithm and methods. Experiment results point out the effectiveness of the proposed algorithm existing heuristic algorithms in most of the test cases. The impact of the proposed MFEA was analyzed, and a possible influential factor that may be useful for further study was also pointed out.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据