Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem
From MaRDI portal
Publication:2123564
Abstract: 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.
Recommendations
- A novel genetic algorithm for solving the clustered shortest-path tree problem
- Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
- Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem
- A two-level solution approach for solving the generalized minimum spanning tree problem
- Evolutionary Multi-Criterion Optimization
Cites work
- An improved particle swarm optimization for solving bilevel multiobjective programming problem
- An improved simulated annealing algorithm for bilevel multiobjective programming problems with application
- Bilevel programming in traffic planning: Models, methods and challenge
- Generalized spanning trees
- Genetic algorithm based approach to bi-level linear programming
- GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem
- GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem
- Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
- Introduction to evolutionary computing
- New Branch-and-Bound Rules for Linear Bilevel Programming
- On the clustered Steiner tree problem
- On the generalized minimum spanning tree problem
- On the minimum routing cost clustered tree problem
Cited in
(3)- A novel genetic algorithm for solving the clustered shortest-path tree problem
- Global optimization on non-convex two-way interaction truncated linear multivariate adaptive regression splines using mixed integer quadratic programming
- Competition between Dandelion and Prüfer encoded genetic algorithms for solving the clustered minimum routing tree problem
This page was built for publication: Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2123564)
