Paper Info
Title
Immune clonal algorithm based on directed evolution for multi-objective capacitated arc routing problem.
Abstract
Display OmittedThe non-dominant solutions obtained by three algorithms on some small and large-scale instances.In the above figure, the former two lines of figures are small-scale instances, in which DE-ICA shows the best convergence on 2 instances compared with other two algorithms. Besides, on other 4 instances of small-scale instances, DE-ICA is not worse than D-MAENS and ID-MAENS. In general, DE-ICA shows a slightly advantage on small scale instances. The reason is that small scale instances have a smaller solution space and they are easier to solve. Consequently, other two compared algorithms have enough capacity to deal with it and get a similar performance with DE-ICA.In the latter two lines of figures, DE-ICA gets the best convergence on 5 instances (e4a, s1a, s4a, G1-A, G2-E). On these instances, DE-ICA can reach areas with both low total cost and the low makespan. As a result, the non-dominant solutions obtained by DE-ICA almost completely dominate the non-dominant solutions obtained by D-MAENS and ID-MAENS. On the remaining instances, DE-ICA is also not worse than the other two algorithms in convergence. In conclusion, DE-ICA demonstrates an obvious advantage in convergence on these large scale instances. The results above show that the DE-ICA is more suitable for the large-scale problems. This paper proposes and Immune Clonal Algorithm Based on Directed Evolution for Multi-Objective Capacitated Arc Routing Problem.The proposed algorithm expands the scale of the initial population to increase the diversity.It helps the antibody populations to share the neighborhood information in time.It applies a brand-new kind of comparison operator.It can evolve in the direction of the better population. The capacitated arc routing problem is playing an increasingly important role in our society, engendering increasing attention from the research community. Among the various models, multi-objective capacitated arc routing problem comes much closer to real-world problems. Therefore, this paper proposes an immune clonal algorithm based on directed evolution to solve this problem. Firstly, the proposed algorithm adopts the framework of the immune clonal algorithm and expands the scale of the initial antibody population in the initialization process to increase the diversity of the antibodies. Secondly, the proposed algorithm is combined with a decomposition strategy in the operations of the immune gene. Antibodies are classified to perform the immune genetic operations, which helps the antibody populations to share the neighborhood information in a timely manner. Thirdly, the proposed algorithm applies a novel kind of comparison operator to build the total population, which helps it to evolve in the direction of a better population and improves the quality of the antibodies. Experimental results suggest that the proposed algorithm can generate better non-dominant solutions than several compared state-of-the-art algorithms, especially for large-scale sets.
Year
DOI
Venue
2016
10.1016/j.asoc.2016.09.005
Appl. Soft Comput.
Keywords
Field
DocType
Immune clone,Decomposition algorithm,Comparison operator,MO-CARP
Convergence (routing),Arc routing,Population,Mathematical optimization,Job shop scheduling,Algorithm,Artificial intelligence,Operator (computer programming),Initialization,Total cost,Mathematics,Machine learning
Journal
Volume
Issue
ISSN
49
C
1568-4946
Citations 
PageRank 
References 
3
0.40
0
Authors
6
Name
Order
Citations
PageRank
Ronghua Shang155633.57
Bingqi Du250.75
Hongna Ma330.40
Licheng Jiao45698475.84
Yu Xue5663.74
Rustam Stolkin652739.74