본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

그래프 착색 문제에 적용된 효과적인 Ant Colony Algorithm에 관한 연구
A Effective Ant Colony Algorithm applied to the Graph Coloring Problem

안상혁   (경희대학교 대학원 컴퓨터공학과UU0001575  ); 이승관   (경희대학교 대학원 전자계산공학과UU0001575  ); 정태충   (경희대학교 컴퓨터공학과UU0001575  );
  • 초록

    개미 집단 시스템(Ant Colony System ACS) 알고리즘은 조합 최적화 문제를 해결하기 위한 새로운 메타 휴리스틱 방법이다. 이것은 그리디 탐색뿐만 아니라 긍정적 피드백에 의한 탐색을 이용한 모집단에 근거한 접근법으로 조합 최적화 문제를 해결하기 위해 제안되었다. 최근까지 인접한 노드( $v_i, v_j$ )가 같은 색을 갖지 않도록 그래프 G의 노드 V에 색을 배정하는 문제인 그래프 착색 문제의 최적 해를 구하기 위하여 다양한 접근 방식들과 해법들이 제안되고 있다. 본 논문에서는 기존의 그래프 착색 문제의 해법으로 잘 알려진 그리디 알고리즘, 시뮬레이티드어넬링, 타부 탐색 등이 아닌 개미 집단 시스템 알고리즘으로 해법을 구하는 방법인 ANTCOL 알고리즘을 소개하고, ANTCOL을 해결하기 위해 제안된 기존의 생성 함수들(ANT_Random ANT_LF, ANT_SL, ANT_DSATUR, ANT_RLF)과, 본 논문에서 새롭게 제안된 방법으로 RLF에 무작위 기법을 적용한 XRLF를 생성 함수로 사용한 ANT_XRLF 방법과 ANT_XRLF에 재검색을 추가한 방법(ANT_XRLF_R)의 그래프 착색 결과 및 실행 시간을 비교, 분석하여 제안된 방법이 더 빠르게 수렴할 수 있음을 실험을 통해 알 수 있었다.


    Ant Colony System(ACS) Algorithm is new meta-heuristic for hard combinational optimization problem. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. Recently, various methods and solutions are proposed to solve optimal solution of graph coloring problem that assign to color for adjacency node( $v_i, v_j$ ) that they has not same color. In this paper introducing ANTCOL Algorithm that is method to solve solution by Ant Colony System algorithm that is not method that it is known well as solution of existent graph coloring problem. After introducing ACS algorithm and Assignment Type Problem, show the wav how to apply ACS to solve ATP And compare graph coloring result and execution time when use existent generating functions(ANT_Random, ANT_LF, ANT_SL, ANT_DSATUR, ANT_RLF method) with ANT_XRLF method that use XRLF that apply Randomize to RLF to solve ANTCOL. Also compare graph coloring result and execution time when use method to add re-search to ANT_XRLF(ANT_XRLF_R) with existent generating functions.


  • 주제어

    개미 집단 시스템 .   자원 배정형 문제 .   그래프 착색 문제 .   생성 함수.  

  • 참고문헌 (12)

    1. Johnson D. S., Aragon C. A, 'Optimization by Simulated Annealing : An Experimental Evaluation-Part2(Graph Coloring and Number partitioning),' Operations Research, Vol.31, pp.378-406, 1991 
    2. Leighton F, 'A graph coloring algorithm for large scheduling problems,' J. National Bureau of Standards, Vol.84, pp.489-505, 1979 
    3. Bralaz D, 'New methods to color vertices of a graph,' Communications of the ACM, Vol.22, pp.251-256, 1979 
    4. Ferland J, A, Hertz A and Lavoie A, 'An object orientedmethodology for solving assignment type problem with neighborhood search techniques,' Opns Res , Vol.44, pp.347-359, 1996 
    5. D. Costa and Hertz A, 'Ant can colour graphs,' J. Op. Res. Society, pp.295-305, 1997 
    6. Welsh D. J. A. and M. B. Powell, 'An Upper Bound for Chromatic Number of a Graph and its Application to Timetabling Problems,' Comput. J., Vol.10, pp.85-86, 1967 
    7. Matula, D. W, G. Marble and J. D. Issacson 'Graph Coloring Algorithms,' on Graph Theory and Computing, R. C. Read, Academic Press, New York, pp.104-122, 1972 
    8. Colorni A. Dorigo M, 'Ant System for job shop scheduling,' Belgian J Opns Res, Stat and Comp Sci, Vol.34, pp.39-53, 1994 
    9. Dorigo M, Maniezzo V, Colorni A, 'The ant system: optimization by a colony of cooperation agents,' IEEE Transactions of Systems, Man and Cybernetics-Part B, Vol.26, No.2, pp.29-41, 1996 
    10. Colorni A. Dorigo M. Maniezzo V, 'An investigation of some properties of an ant algorithm,' Proceeding of the Second Conference on Parall Problem Solving from Nature, Brussels, North-Holland, Amsterdam, pp.509-520, 1992 
    11. Maniezzo V, Colorni A. Dorigo M, 'The ant system applied to the quadratic assignment problem,' Technical Report 94/28, IRIDIA, Universite Libre de Bruxelles, Belgium, 1994 
    12. Colomi A, Dorigo M, Maniezzo V 'Distributed optimization by ant colonies' Proceeding of the first European conference on Artificial Life, Paris. MIT Press Bradford Books, Cambridge, pp.134-142, 1991 

 저자의 다른 논문

  • An, Sang-Hyeok (1)

    1. 2012 "Univector Field Method based Multi-Agent Navigation for Pursuit Problem" International journal of fuzzy logic and intelligent systems : IJFIS 12 (1): 86~93    
  • Lee, Seung-Gwan (18)

  • 정태충 (45)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기