Premium
Immune algorithm combined with estimation of distribution for traveling salesman problem
Author(s) -
Xu Zhe,
Wang Yirui,
Li Sheng,
Liu Yanting,
Todo Yuki,
Gao Shangce
Publication year - 2016
Publication title -
ieej transactions on electrical and electronic engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.254
H-Index - 30
eISSN - 1931-4981
pISSN - 1931-4973
DOI - 10.1002/tee.22247
Subject(s) - estimation of distribution algorithm , travelling salesman problem , benchmark (surveying) , local search (optimization) , computer science , mathematical optimization , algorithm , population , heuristic , permutation (music) , probabilistic logic , mathematics , artificial intelligence , physics , demography , geodesy , sociology , acoustics , geography
This paper describes an artificial immune algorithm (IA) combined with estimation of distribution algorithm (EDA), named IA‐EDA, for the traveling salesman problem (TSP). Two components are incorporated in IA‐EDA to further improve the performance of the conventional IA. First, aiming to strengthen the information exchange during different solutions, two kinds of EDAs involving univariate marginal distribution algorithm and population‐based incremental learning are altered based on the permutation representation of TSP. It is expected that new promising candidate solutions can be sampled from the constructed probabilistic model of EDA. Second, a heuristic refinement local search operator is proposed to repair the infeasible solutions sampled by EDA. Therefore, IA‐EDA can alleviate the deficiencies of the conventional IA and can find better solutions for TSP by well balancing the exploitation and exploration of the search. Experiments are conducted based on a number of benchmark instances with size up to 100 000 cities. Simulation results show that IA‐EDA is effective for improving the performance of the conventional IA and can produce better or competitive solutions than other hybrid algorithms. © 2016 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.