Neighborhood Search Algorithms for the Maximal Covering Problem

KJC Korea
Journal Central

Korean | English

pISSN : 1598-849X / eISSN : 2383-9945

http://journal.kci.go.kr/jksci

Home > Explore Content > All Issues > Article View

14 of 30

Neighborhood Search Algorithms for the Maximal Covering Problem

¹금오공과대학교

ABSTRACT
열림/닫힘 버튼

Various techniques have been applied to solve the maximal covering problem. Tabu search is also one of them. But, existing researches were lacking of the synthetic analysis and the effort for performance improvement about neighborhood search techniques such as hill-climbing search and simulated annealing including tabu search. In this paper, I introduce the way to improve performance of neighborhood search techniques through various experiments and analyses. Basically, all neighborhood search algorithms use the k-exchange neighborhood generation method. And I analyzed how the performance of each algorithm changes according to various parameter settings. Experimental results have shown that simple hill-climbing search and simulated annealing can produce better results than any other techniques. And I confirmed that simple hill-climbing search can produce similar results as simulated annealing unlike general case.
KEYWORDS
열림/닫힘 버튼

neighborhood search(이웃해 탐색), hill-climbing search(언덕오르기 탐색), simulated annealing(시뮬레이티드 어닐링), maximal covering problem(maximal covering 문제)

236 Viewed

21 Downloaded