An Intelligent Evolutionary Computation Approach for Solving the Shortest Path Problem
Behzad Moradi
A new non-Darwinian-type evolutionary computation approach based on learnable evolution model is proposed for solving the shortest path problem in this article. Learnable evolution model includes a machine learning method, such as the decision trees, that can detect the right directions of the evolution and results in large improvements in the fitness of the individuals. A modified priority-based path encoding method with a repairing procedure is proposed to represent the individuals in the problem which leads to reducing the possibility of the loop formation in the path construction process. Several novel heuristics are employed in the instantiating process in order to avoid the incomplete path formation. The proposed approach is tested on networks of varying topologies and different sizes in order to verify its performance. Computer simulations justify that the proposed approach exhibits a much better quality of solution and a much higher convergence speed in comparison with other similar approaches. The proposed approach retains its robustness against changing network topologies regarding both the quality of solution and the convergence speed.
Keywords: Graph theory; combinatorial optimization; shortest path; learnable evolution model; evolutionary computation; path encoding.