본문 바로가기
KERD
논문KCI 등재

TSP 경로탐색을 위한 S-MINE 알고리즘

S-MINE Algorithm for the TSP

이창훈|고성범|원일용|황숙희
한국정보처리학회|2011.04|정보처리학회 논문지 (The Transactions of the Korea Information Processing Society)|제18권 제2호|pp. 73-82

0

조회

0

다운로드

1

인용

0

참고문헌

키워드

Traveling Salesman Problem탐색 알고리즘Search Algorithm메타 휴리스틱 알고리즘순회판매원문제Meta Heuristic Algorithm
주제분류컴퓨터학

초록

메타 휴리스틱 알고리즘을 이용해 TSP (Traveling Salesman Problem) 문제를 풀고자 하는 많은 시도가 이루어지고 있다. TSP 문제는 대표적인 NP_Hard 문제로 탐색 알고리즘이나 최적화 알고리즘을 실험하는데 많이 사용되고 있으며, 복잡한 사회의 많은 문제들의 표준 모델로제시되고 있다. 본 논문에서는 2009년 제안된 MINE 알고리즘을 TSP 에 적용시켜 메타 휴리스틱 알고리즘으로서의 탐색성능을 알아보고자 하였다. 이에 S-MINE (Search – MINE) 알고리즘을 제안하였으며, TSP 에 적용하여 그 결과를 고찰하였다.

Abstract

There are a lot of people trying to solve the Traveling Salesman Problem (TSP) by using the Meta Heuristic Algorithms. TSP is an NP-Hard problem, and is used in testing search algorithms and optimization algorithms. Also TSP is one of the models of social problems. Many methods are proposed like Hybrid methods and Custom-built methods in Meta Heuristic. In this paper, we propose the S-MINE Algorithm to use the MINE Algorithm introduced in 2009 on the TSP.

참고문헌 (24)

  1. S. Lin, "An Effective Heuristic Algorithm for the Traveling Salesman Problem" (1971), Murray Hill
  2. M.R. Garey, "A Guide to the Theory of NP-Completeness" (1979), Freeman
  3. B. Freisleben, "Genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems", Proceedings of IEEE International Conference of Evolutionary Computation, IEEE-EC96, pp.616~621 (1996), IEEE Press
  4. Zhong Yiwen, "A Discrete Particle Swarm Optimization Algorithm for Solving Traveling alesman Problem", System Engineering and Theory Practice, pp.88~94 (2006)
  5. L.M Gambardella, "Ant Colony System: A cooperative Learning Approach to the Traveling Salesman Problem", IEEE Transactions on Evolutionary Computation, 1(1) (1997)
  6. Christian Blum, "Metaheuristics in combinatorial optimization: overview and Conceptual comparison", ACM Computing Surveys, 35, pp.268~308 (2003)
  7. L. Bianchi, "A survey on metaheuristics for Stochastic combinatorial optimization", Natural Computing, 8, pp.239~287 (2008)
  8. Sarayut Nonsiri an Siriporn Supratid, "Modifying Ant Colony Optimization", IEEE conference on soft computing in industrial applications (2008)
  9. X. Hu, "Swarm Intelligence for permutation Optimization: a case study of n-queens problem", proceedings of the IEEE Swarm Intelligence Symposium, pp.243~246 (2003)
  10. 고성범, "Mine 알고리즘:인간의 행동을 모방한 메타휴리스틱", 정보처리학회논문지. 소프트웨어 및 데이터 공학, 16(5), pp.411~426 (2009), 한국정보처리학회
  11. Solis, F.J, "Minimization by random search techniques", Mathematics of operations research, 6(1), pp.19~30 (1981)
  12. Moscato,P, "Memetic algorithms: A short introduction in New Ideas in Optimization", pp.219~234 (1999), McGraw Hill
  13. Puchinger, J, "Modules and Algorithms for Three-stage two-dimensional bin Packing", European Journal of Operational Research (2006)
  14. "A Traveling Salesman Problem Library"[URL]
  15. D.E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning" (1989), Addison-Wesley
  16. Z. Michalewicz, "Genetic Algorithms + Data structure = Evolution Program" (1992), Springer-Verlag
  17. Dorigo M, "The Ant System: Optimization by a Colony of Cooperating Agents", IEEE trans. Syst. Man Cybern B, 26, pp.29~41 (1996)
  18. Dorigo M, "Ant Colony System: A Cooperative Learning Approach", IEEE Trans. Evol. Comp, 1, pp.53~66 (1997)
  19. Raed Abu Zitar, "Optimizating the parameters of Ant colony Algorithm Using the Genetics", Enformatika Transaction on Engineering, Computing and Technology VI, VI, pp.228~231 (2004)
  20. J. Kennedy, "Particle Swarm Optimization", IEEE conference of Neural Network, 통권 : IV, pp.1942~1948 (1995)
  21. J. Kennedy, "The Particle Swarm: Social adaptation of knowledge", IEEE conference of Evolutionary Computing, pp.303~308 (1997)
  22. X.H. Shi, "An improved GA and novel PSO-GA-based hybrid algorithm", Information Processing Letters (1993)
  23. 고성범, "인터넷기반 의사결정 공간의 설계" (2010), GS 인터비젼
  24. J. De Vicente, "Placement by Thermodynamic Simulated Annealing", Physics Letters A, 317(5), pp.415~423 (2003)

관련 논문AI추천

순회 판매원 문제 해결을 위한 개미집단 최적화 알고리즘 개선김민제, 이종환, 장주영한국산업경영시스템학회 · 한국산업경영시스템학회지2019 · 제42권 제3호Mine 알고리즘:인간의 행동을 모방한 메타휴리스틱고성범한국정보처리학회 · 정보처리학회 논문지2009 · 제16권 제5호TSP를 위한 개미알고리즘: 보다 좋은 α와 β 값 발견조상엽, 황수철한국지식정보기술학회 · 한국지식정보기술학회 논문지2010 · 제5권 제5호순회 왼판원 문제를 위한 지역 탐색의 그리디 기반 이웃해 생성 방법김용호, 황준하한국컴퓨터정보학회 · 한국컴퓨터정보학회논문지2022 · 제27권 제9호방문판매원 문제에 적용한 개선된 개미 군락 시스템김인겸, 윤민영한국정보처리학회 · 정보처리학회 논문지2005 · 제12권 제7호이종 확률적 외판원 문제를 위한 최소 평균거리 삽입 및 집단적 지역 탐색 알고리듬김승모, 최기석한국산업경영시스템학회 · 한국산업경영시스템학회지2010 · 제33권 제3호

이 간행물의 다른 논문 (6건)

x-색도 공간에서 ROI의 전방향 프로젝션과 백색패치의 평행이동에 의한 본질 영상 획득이우람, 전병민, 김달현, 황동국pp. 51-56K-평균 클러스터링과 그래프 탐색을 통한 심장 자기공명영상의 좌심실 자동분할 알고리즘이해연, 조현우pp. 57-66엔트로피 거리와 SVM를 이용한 SNP 군집분석과 천식 유형 예측신기섭, 위규범, 이중섭pp. 67-72모바일 퍼스널 어시스턴트의 지능 행위 구현을 위한 스마트 스크립트 시스템김인철, 오휘경pp. 83-86한국어 자모 Viable Prefix를 이용한 외래어 표기 교정 기법권순호, 권혁철pp. 87-92
원문 보기