An efficient strategy for using multifactorial optimization to solve the clustered shortest path tree problem

摘要

Arising from the need of all time for optimization of irrigation systems, distribution network and cable network, Clustered Shortest-Path Tree Problem (CluSPT) has been attracting a lot of attention and interest from the research community. On the other hand, the Multifactorial Evolutionary Algorithm (MFEA) is one of the most recently exploited realms of Evolutionary Algorithms (EAs) and its performance in solving optimization problems has been very promising. Considering these characteristics, this paper describes a new approach using the MFEA for solving the CluSPT. The MFEA has two tasks: the goal of the first task is to determine the best tree (w.r.t. cost minimization) which envelops all vertices of the CluSPT while the goal of the second task is to find the fittest solution possible for the problem. The purpose of the second task is to find good materials for implicit genetic transfer process in MFEA to improve the quality of CluSPT. To apply this new algorithm, a decoding scheme for deriving individual solutions from the unified representation in the MFEA is also introduced in this paper. Furthermore, evolutionary operators such as population initialization, crossover and mutation operators are also proposed. These operators are applicable for constructing valid solution from both sparse and complete graph. Although the proposed algorithm is slightly complicated for implementation, it can enhance ability to explore and exploit the Unified Search Space (USS). To prove this increment in performance i.e, to assess the effectiveness of the proposed algorithm and methods, the authors implemented them on both Euclidean and Non-Euclidean instances. Experiment results show that the proposed MFEA outperformed 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.