TY - GEN
T1 - Multi-objective Techniques for Single-Objective Local Search
T2 - 10th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2019
AU - Shi, Jialong
AU - Sun, Jianyong
AU - Zhang, Qingfu
PY - 2019/3
Y1 - 2019/3
N2 - In this paper, we show that the techniques widely used in multi-objective optimization can help a single-objective local search procedure escape from local optima and find better solutions. The Traveling Salesman Problem (TSP) is selected as a case study. Firstly the original TSP ƒ0 is decomposed into two TSPs ƒ1 and ƒ2 such that ƒ0 = ƒ1 + ƒ2 . Then we propose the Non-Dominance Search (NDS) method which applies the non-domination concept on (ƒ1 , ƒ2 to guide a local search out of the local optima of ƒ0 . In the experimental study, NDS is combined with Iterated Local Search (ILS), a well-known metaheuristic for the TSP. Experimental results on some selected TSPLIB instances show that the proposed NDS can significantly improve the performance of ILS.
AB - In this paper, we show that the techniques widely used in multi-objective optimization can help a single-objective local search procedure escape from local optima and find better solutions. The Traveling Salesman Problem (TSP) is selected as a case study. Firstly the original TSP ƒ0 is decomposed into two TSPs ƒ1 and ƒ2 such that ƒ0 = ƒ1 + ƒ2 . Then we propose the Non-Dominance Search (NDS) method which applies the non-domination concept on (ƒ1 , ƒ2 to guide a local search out of the local optima of ƒ0 . In the experimental study, NDS is combined with Iterated Local Search (ILS), a well-known metaheuristic for the TSP. Experimental results on some selected TSPLIB instances show that the proposed NDS can significantly improve the performance of ILS.
KW - Multi-objective optimization
KW - Traveling Salesman Problem
KW - Local search
KW - Metaheuristic
KW - Iterated Local Search
UR - https://www.scopus.com/pages/publications/85063067646
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85063067646&origin=recordpage
U2 - 10.1007/978-3-030-12598-1_10
DO - 10.1007/978-3-030-12598-1_10
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783030125974
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 114
EP - 125
BT - Evolutionary Multi-Criterion Optimization
A2 - Deb, Kalyanmoy
A2 - Goodman, Erik
A2 - Coello Coello, Carlos A.
A2 - Klamroth, Kathrin
A2 - Miettinen, Kaisa
A2 - Mostaghim, Sanaz
A2 - Reed, Patrick
PB - Springer Nature Switzerland AG
Y2 - 10 March 2019 through 13 March 2019
ER -