Discrete cuckoo search algorithm for the travelling salesman problem

[koptimizer]

:clipboard: 논문의 정보를 알려주세요.

• Discrete cuckoo search algorithm for the travelling salesman problem
• Aziz Ouaarab, Belaı ¨d Ahiod, Xin-She Yang
• 2012-11-24

:page_with_curl: Abstract(본문)

In this paper, we present an improved and discrete version of the Cuckoo Search (CS) algorithm to solve the famous traveling salesman problem (TSP), an NP-hard combinatorial optimisation problem. CS is a metaheuristic search algorithm which was recently developed by Xin-She Yang and Suash Deb in 2009, inspired by the breeding behaviour of cuckoos. This new algorithm has proved to be very effective in solving continuous optimisation problems. We now extend and improve CS by reconstructing its population and introducing a new category of cuckoos so that it can solve combinatorial problems as well as continuous problems. The performance of the proposed discrete cuckoo search (DCS) is tested against a set of benchmarks of symmetric TSP from the well-known TSPLIB library. The results of the tests show that DCS is superior to some other metaheuristics.

:mag_right: 어떤 논문인지 소개해주세요.

• 메타휴리스틱의 일종인 Cuckoo Search를 향상시켜 combinatorial problems(TSP)을 접근 할 수 있도록 개량한 DSC(Discrete Cuckoo Search)를 소개하고 다른 메타휴리스틱과 성능을 비교합니다.

:key: 핵심 키워드를 적어주세요.

• Improved Cuckoo Search(Pc)
• Le'vy flight
• Combinatorial optimisation

:paperclip: URL

https://link.springer.com/article/10.1007/s00521-013-1402-2

[koptimizer]

:bulb: 방법은 무엇입니까?

• population에 Pc라는 second control-level 파라미터를 부여해서 더 효율적인 탐색을 하게 하는 '지능적인 뻐꾸기'를 사용합니다.
  1. 하나의 둥지를 숙주로 Le'vy 분포에 의한 랜덤한 step을 결정합니다.
  2. step이 짧다면 숙주 둥지와 최대한 비슷한 알(Exploitation)인 2-Opt 최적화를 진행하고, 길다면 숙주의 알과 많이 다른 알(Exploration)인 Double Bridge 최적화를 사용하여 둥지를 만듭니다.
  3. 기존의 둥지와 비교(fitness comparing)하여 대체할지를 결정합니다.
  4. pa에 정해진 비율(host bird에게 들킬 확률)만큼 안좋은 둥지를 탈락시키고, 새 둥지를 만들어 population의 크기를 유지합니다.

:chart_with_upwards_trend: 실험과 그 결과는 어떻습니까?

• 실험
  • 공개 라이브러리인 TSPLIB의 일부 TSP 인스턴스(벤치마크)에 대해 테스트합니다.
  • 대부분의 인스턴스는 이미 해결되어 최적해를 알고 있기때문에 비교하기에 적절합니다.
  • n = 20 / pa = 0.2 / pc = 0.6 / maxGeneration = 500
• 결과
  • Basic DCS vs Improved DCS : Improved DCS가 수렴력, 탐색력 모두 좋음.
  • GSA-ACS-PSOT vs DCS : DCS가 수렴력, 탐색력 모두 좋음.
  • DPSO vs DCS : DCS가 수렴력, 탐색력 모두 좋음.

:open_file_folder: 차후 연구방향 및 보완점은 무엇입니까?

• 파라미터에 대한 민감도 연구가 필요해보입니다. 실제로 만들어보니 n의 크기가 커질수록 시간복잡도가 비약적으로 상승해서 시간비 성능이 굉장히 떨어집니다.
• 다른 Combinatorial probelm에 적용해보기 좋아보입니다. 예를들면 AutoML-zero...!

:thumbsup: novelty와 논문을 통해 배운 것은 무엇입니까?

• 기존 CS는 수렴력이 조금 약했지만, 제안된 Smart Cuckoo를 이용해서 수렴력을 상승시켰습니다.
• 원래 존재했던 최적화 알고리즘(2-opt, Double-Bridge)을 small step과 large step에 적절하게 부여한 것을 보고, 메타휴리스틱의 다양한 도메인 적용에 대한 방법을 얻어갈 수 있었습니다!

:loop: 궁금한 점이나 추가로 읽으면 좋은 레퍼런스가 있습니까?

Cuckoo search via Lévy flights - XS Yang