The Research On The Large-Scale Capacitated Arc Routing Problems Based On Memetic And Quantum Inspired Immune Clonal Algorithm

Capacitated Arc Routing Problem(CARP) is a classic NP-Hard combinatorial optimization problem, which has attracted considerable attention from researchers due to its broad potential for social applications. With increasing the size of the instances, its complexity is enhanced and it can not be solved exactly. Therefore, this paper builds on, and develops beyond, the cooperative coevolutionary(CC) algorithm based on route distance grouping(RDG-MAENS) proposed combining the feature of the search algorithms, the highly evolved features of the Quantum immune clone algorithm and the parallel evolution of the Coevolution to solve the CARP. The main work is as follows:1) There are some problems in the existing algorithms for solving CARP, like the stability of the solution is poor and easy to fall into local optimum. In this paper, we present a memetic algorithm based on Extension step and Statistical filtering for CARP(ESMAENS)which has improvements on both the global search strategy and the local search strategy.Firstly, ESMAENS adopts the Route Distance Grouping decomposition scheme(RDG) to decompose the large-scale CARP into the independent sub-problems. Then, the initial population evolves into a new group by using the Evolutionary Algorithm(EA). And ESMAENS introduces the extension step search strategy into the global search strategy to search the field of current solution. Finally, in the local search strategy, using the statistical filter to filter out the solution makes the algorithm to get the lower bound at a faster convergence speed and improves the stability of the algorithm. Compared with RDG-MAENS, experimental results on Beullen'C, D, E, F, egl and EGL-G test set show that ESMAENS has better convergence and the stability of solutions obtained is improved.Furthermore, ESMAENS achieves a global search for the solutions, which shows that ESMAENS is suitable for solving large-scale CARP.2) In this paper, we present a Quantum-Inspired Immune Clonal Algorithm for solving Large-Scale CARP(QICA-CARP) for the inadequate of the existing algorithms to solve the LSCARP. This algorithm combines the feature of artificial immune system and quantum computation ground on the qubit and the quantum superposition. In the proposed algorithm, an antibody of population is denoted by quantum bit encoding. For this encoding, using the information on the current optimal antibody to control population witha high probability evolution toward good schema by the action of the mutation strategy of quantum rotation gate to accelerate the convergence of the original clone operator.Meanwhile, quantum crossover operator enhances the exchange of information and increases the diversity of the population as well as prevents falling into local optimum. We also use the repair operator to amend the infeasible solutions to ensure the diversity of solutions, so that make it approximate to the optimal solution. The experimental results show that the algorithm has great competitive.3)We studied a more complex mathematical model of LSCARP-multi-objective LSCARP(MO-LSCARP). In 2014, the cooperative coevolutionary(CC) algorithm based on route distance grouping(RDG-MAENS), recently proposed by Mei et al. Although Mei's method has proved superior to previous algorithms, we discuss several remaining drawbacks and propose solutions to overcome them. Firstly, although route distance grouping(RDG) is used in searching for potential better solutions, the solution generated from the decomposed problem at each generation is not the best one, and the best solution found so far is not used for solving the current generation. Secondly, to determine which sub-population the individual belongs to simply according to distance can lead to an imbalance in the number of the individuals among different sub-populations and the allocation of resources. Thirdly, the method of Mei et al. was only used to solve single-objective CARP. To overcome the above issues, this paper proposes improving RDG-MAENS by updating the solutions immediately and applying them to solve the current solution through areas shared, and then according to the magnitude of the vector of the route direction, and a fast and simple allocation scheme is proposed to determine which decomposed problem the route belongs to. Finally, we combine the improved algorithm with an Improved Decomposition-based Memetic Algorithm to solve the multi-objective Large Scale CARP(LSCARP). Experimental results suggest that the proposed improved algorithm can achieve better results on both single-objective LSCARP and multi-objective LSCARP.