Artificial Bee Colony Algorithm With Its Application And Research In Combinatorial Optimization Problems

Artificial bee colony algorithm is an efficient swarm intelligence optimization algorithm,which has the characteristics of few parameters,strong search ability and strong robustness as well as good performance in solving complex optimization problems,but it also has some shortcomings such as slow convergence speed and low search accuracy.Combinatorial optimization problem is an important branch of operational research in theory,and its subproblems have great application value in many fields such as economic management,engineering technology,transportation and so on.Therefore,on the basis of studying the principle of artificial bee colony algorithm,this thesis improves the algorithm from two aspects:neighborhood structure and search strategy.After the fusion and reconstruction of artificial bee colony algorithm,an effective improved algorithm is proposed,and its experiments on two sets of benchmark functions show that the algorithm can effectively improve the convergence speed and search accuracy.In addition,this thesis also studies the application of the improved artificial bee colony algorithm in two discrete combinatorial optimization problems which are vehicle routing problem with time window and order batching problem.The main research work of this thesis is summarized as follows:(1)Improvement of artificial bee colony algorithm.Based on the standard artificial bee colony algorithm,this thesis proposes a new neighborhood structure called dynamic kneighborhood structure,which reduces the randomness of employed bees to select neighborhood bees and improves the convergence speed of the algorithm.In particular,according to the characteristics of the three stages of artificial bee colony algorithm,this thesis introduces global optimal individual,elite individuals and reverse strategy into the search strategies in these three stages,which effectively improves the search accuracy of the algorithm.Finally,this thesis sets two benchmark functions to test the performance of the algorithm,analyzes the experimental results of improved artificial bee colony algorithm under different parameter settings and different strategies,and compares it with artificial bee colony algorithm and three artificial bee colony algorithm variants.The final results show that the performance of improved artificial bee colony algorithm has been significantly improved compared with standard artificial bee colony algorithm.(2)Improved artificial bee colony algorithm is applied to solve vehicle routing problem with time windows and order batching problem.Based on the existing research on these two discrete combinatorial optimization problems,this thesis establishes mathematical models respectively.Then on the basis of the corresponding models,the improved artificial bee colony algorithm is discretized,including coding and decoding,establishing objective function,population initialization,designing search strategy suitable for discretization algorithm and so on.Then the improved discrete artificial bee colony algorithm is simulated on a set of test data of these two combinatorial optimization problems,which proves the feasibility of the improved discrete artificial bee colony algorithm in solving vehicle routing problem with time window and order batching problem.In summary,based on the principle of artificial bee colony algorithm,this thesis researched its improvement strategy,proposed an improved algorithm,and analyzed its application in vehicle routing problem with time window and order batching problem.A large number of experiments proved that the improved algorithm is efficient in theory and feasible in the application of combinatorial optimization problem.