Swarm Intelligence Optimization And Applications To Capacitated Arc Routing Problems

There are a lot of optimization problems in scientific research and industrial production.These problems usually have poor properties,such as nondifferentiability and nonlinearity.It is difficult to solve these problems by traditional numerical optimization methods.Swarm intelligence algorithms perform well in solving these problems with poor properties.This paper discusses the properties and applications of swarm intelligence algorithms in continuous problems and combinatorial optimization problems.Firstly,the origin illusion is discovered by the fireworks algorithm,and the intelligent algorithm is understood and analyzed from the perspective of aggregation and guidance.Then a simple algorithm is proposed,which verifies the feasibility of designing algorithm by using aggregation and guidance.Then a gathering and dispersion optimization algorithm is proposed.Finally,the convergence and convergence speed of the population algorithm are analyzed from the perspective of aggregation and guidance.Swarm intelligence algorithms usually need to specify parameters,but the setting of these parameters are often empirical.In order to simplify the use of the algorithm,the adaptive parameters are set.At the same time,mixing different algorithms to get the mixing operator is a very effective method to improve the algorithm.Therefore,this paper proposes an adaptive harmony algorithm by differential evolution algorithm operator.In order to make full use of harmony memory to generate new solutions,a new adaptive harmony search algorithm is proposed,which adopts differential mutation,periodic learning and linear population reduction strategies for global optimization.The difference variation method is used to adjust the pitch,which provides a promising direction guidance for adjusting the bandwidth.In order to balance the diversity and convergence of harmony memory,a linear reduction strategy for harmony memory is proposed.At the same time,periodic learning method is used to modify pitch adjustment rate and scale factor adaptively to improve the adaptability of the algorithm.The effectiveness and synergism of the proposed strategy and key parameters are analyzed in detail.The experimental comparison with several most advanced evolutionary algorithms shows that the new algorithm has very competitive performance.Capacitated arc routing problem is one of the classical combinatorial optimization problems.The capacitated arc routing problem has attracted much attention because of its wide application.However,the existing research methods still have a certain potential in making full use of the characteristics of the capacitated arc routing problem.This paper aims at mining the essential characteristics of arc routing problems that node routing problems do not have.On the basis of observing the characteristics of arc routing instances,the smoothing condition is proposed,which can be used for dividing the links between two tasks into smooth links and nonsmooth links are constructed.The smooth degree is then defined to measure the effect of nonsmooth connections on the solution.The lower the smooth degree,the better the quality of the solution.The effect of smooth degree is verified by the comparison of several instance sets,which indicates that there is a positive correlation between the smooth degree and the total cost of solution.The nonsmooth penalty is used to drive the nonsmooth solution to become smooth by increase its total cost.Then two new construction algorithms are obtained by adding nonsmooth penalty into the path scanning.Using these construction algorithms as the alternative kernel method,a partial reconstruction method is designed.In order to further reduce the number of routes,a reinsert method is proposed.Combining these two methods with the traditional local search algorithm,based on the preliminary observation of the essential characteristics of the capacitated arc routing problems,a memetic algorithm with nonsmooth penalty is proposed.A large number of experiments of smoothness and penalty factor and comparison with the latest algorithm show that the proposed strategy is effective,and the proposed memetic algorithm with nonsmooth penalty is competitive.In the existing studies of capacitated arc routing problems,the problem sets used to test algorithm performance are usually in small scale.But problems in real life are often on a larger scale.Therefore,a series of coevolutionary algorithms for large scale are proposed.That is,in the process of searching,the large scale capacitated arc routing problem is decomposed into several small scale subproblems according to the current optimal solution in the population,and then partial solutions of the original problem are obtained by solving the subproblems separately with the existing methods,and finally all partial solutions are combined to obtain the original solution.However,the problem of computational waste in largescale problem is not fully understood.This paper explores the reasons why large scale problems are difficult and attempts to solve existing large scale problems directly by using local search.At the same time,the existing local search method is improved and an improved scheme is proposed.Experimental results show that the improved algorithm is competitive enough.