Font Size: a A A

Research On Swarm Intelligence Optimization Algorithm For Several Combinatorial Optimization Problems

Posted on:2022-05-12Degree:MasterType:Thesis
Country:ChinaCandidate:S S GuoFull Text:PDF
GTID:2518306350994689Subject:Control Science and Engineering
Abstract/Summary:PDF Full Text Request
Combinatorial optimization is an important branch of computer science and operations research,which mainly studies mathematical methods to find the optimal grouping,arrangement,screening or ordering of discrete events.With the development of computer technology,some heuristic algorithms were proposed and widely used in combinatorial optimization problems.In view of the shortcomings of heuristic algorithms in solving combinatorial optimization problems,such as low precision and slow convergence speed,this article studies the application of swarm intelligence optimization algorithms in some classical combinatorial optimization problems.The specific work of this article mainly includes the following aspects:(1)A binary particle swarm optimization(BPSO)algorithm based on a new Z-shaped probability transfer function was proposed to solve the 0-1 knapsack problem.The discrete binary particle swarm optimization(BPSO)algorithm maps the continuous search space to a binary space with a new transfer function,and the update process is designed to switch the position of particles between 0 and 1 in the binary search space.In this article,a new Z-shaped probability function is proposed on the basis of the existing S-shaped and V-shaped probability functions,aiming at the disadvantage that the original BPSO algorithm is easy to fall into local optimal.The improved algorithm is tested on a large number of CEC test functions and standard0-1 knapsack examples,and the results show that the proposed probability transfer function improves the convergence speed and optimization accuracy of the algorithm.(2)A discrete Mole optimization algorithm(DNMR)was proposed to solve the TSP.Naked Mole rat algorithm a swarm intelligence optimization algorithm based on the paired breeding behavior of naked mole rat.In this article,a DNMR based on multiple local dynamic search strategies is proposed to solve the single-traveler problem and the multi-traveler problem.The DNMR for SOLVING TSP problem adopts sequential coding and proposes individual renewal strategies for worker stage and reproduction stage.In order to avoid the algorithm falling into the local optimal solution path,we added 2-opt,3-opt and double-bridge local search operators on the basis of DNMR.The algorithm is tested by using the benchmark problem selected in TSPLIB,and the results show that the improved naked Mole rat algorithm proposed in this article can reach the results close to the theoretical optimal value in a reasonable time and has strong robustness in solving the problems of single and multiple travel agents.(3)A hybrid grasshopper optimization algorithm(HGOA)was proposed to solve the economic load dispatch and economic discharge joint dispatch problem.First of all,in view of the shortcomings of poor GOA development ability and low convergence accuracy,the gravity search operator is introduced into the optimization process of GOA,which improves the grasshopper's global optimization ability and avoids falling into local optima in advance.At the same time,the pigeon search operator-landmark operator is introduced to improve and balance the exploration and development capabilities of the algorithm.In addition,according to the characteristics of economic load dispatching and economic emission combined dispatching,six penalty functions are proposed on the basis of fixed value penalty strategy,which transforms the fixed value penalty strategy into dynamic penalty strategy.In order to verify the performance of HGOA and the dynamic penalty strategy,by testing the economic dispatch problem of the quadratic criterion and the economic dispatch problem of the third criterion,the simulation experiment results show that HGOA is superior to other meta-heuristic algorithms in terms of solution quality,and improved dynamics The penalty factor is improved to different degrees in terms of convergence speed and solution quality compared with the fixed value penalty strategy.
Keywords/Search Tags:Backpack Problem, Traveling Salesman Problem, Economic Scheduling Problem, Swarm Intelligence Optimization Algorithm, Particle Swarm Optimization Algorithm, Naked Mole Algorithm, Grasshopper Optimization Algorithm
PDF Full Text Request
Related items