A bi-level encoding scheme for the clustered shortest-path tree problem in multifactorial optimization. (April 2021)

• Record Type: Journal Article
• Authors: Binh, Huynh Thi Thanh; Thang, Ta Bao; Thai, Nguyen Duc; Thanh, Pham Dinh
• Is Part Of: Engineering applications of artificial intelligence. Volume 100(2021)
• Publication Date: 2021-04
• Subjects: Multifactorial Evolutionary Algorithm -- Clustered Shortest-Path Tree Problem -- Evolutionary Algorithms -- Multifactorial optimization; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2021.104187
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: 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. Highlights: Devise a novel two-level scheme based on the Multifactorial Evolutionary Algorithm to solve the nested structure of the Clustered Shortest Path Tree Problem (CluSPT): tree containing sub-trees. Develop a new solution representation and an effective memory-based method to calculate the cost for the CluSPT, thus reducing resource consumption. Design a crossover operator that can work with multiple parents. Assessed the effectiveness of the proposed algorithm and existing methods on various types of instances. The proposed algorithm outperforms all existing algorithms in 98.6% test cases on both the solution quality and running time.