Font Size: a A A

Research On Multi-objective Optimal Path Based On Hybrid Particle Swarm Optimization

Posted on:2019-05-23Degree:MasterType:Thesis
Country:ChinaCandidate:H LiFull Text:PDF
GTID:2348330545985781Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
The shortest path algorithm has always been one of the hot topics in the field of optimization.It has been widely used in many fields and has important practical value.The traditional shortest path problem often needs to be solved by a single goal optimization such as time and distance.However,most problems in reality cannot be solved with a single goal optimization.In many practical applications,it is often found that a single goal optimization is insufficient to adequately express the problem.Therefore,the need of reality makes it necessary to study the multi-objective shortest path problem.This article first discusses how to encode the shortest path problem,which makes it possible to use evolutionary algorithms and particle swarm algorithms to deal with this problem,and designs a decoding algorithm based on the coding method.Then a multi-objective hybrid evolutionary algorithm is designed to solve the problem.The target shortest path problem is the hybrid evolutionary algorithm because the a lgorithm combines two sampling strategies,namely the combination of the Vector Evaluation Genetic Algorithm(VEGA)sampling strategy and a new fitness evaluation function.The sampling strategy of VEGA is more inclined to search for the Pareto frontier edge area,and the new fitness evaluation function is more inclined to pick out individuals in the central area of the Pareto frontier area.The complementarity between the two makes the algorithm uniform towards the Pa reto frontier.Evolution,and finally compared with the traditional NSGA-II and SPEA2 experi ments.The experimental data used road network data from Washington,USA,and the results show that both the convergence and the distribution of the algorithm are superior to the traditional algorithms.In the end,this paper introduces a multi-objective hybrid particle swarm optimization algorithm to solve the multi-objective shortest path problem.Because the particle swarm optimization algorithm has better global search capability and faster computation speed than the traditional evolutionary algorithm,it is more suitable for searching in multi-target environments.Therefore,it uses it to combine with the above-mentioned hybrid sampling strategy,and then makes an experimental comparison with the general multi-objective particle swarm algorithm and the multi-objective hybrid evolution algorithm designed in this paper.The res ults show that both the convergence and the distribution of the algorithm are superior to the two compared algorithms,a nd further prove that the algorithm has achieved good results.In this dissertation,two algorithms are designed for multi-objective optimal path problem.One is based on traditional evolut ionary algorithm and the other is based on particle swarm algorithm.The particle swarm is classified.On the basis of classification,according to each type of particle,different global optimal positions and historical optimal positions are selected for updati ng.The a bove two algorithms are compar ed with traditional classic multi-objective evolutionary algorithms.The results show that improved algorithm has achieved good results.
Keywords/Search Tags:shortest path problem, hybrid evolu tionary algorithm, hybrid particle swarm optimization, multi-objective shortest path, encoding and decoding
PDF Full Text Request
Related items