그래프 컬러링 문제를 위한 효과적인 유전 알고리즘

Abstract

그래프 컬러링 문제는 널리 알려진 유명한 문제의 하나로 다항시간안에 확정적으로 푸는 알고리즘이 존재하지 않는 NP완비군 문제로 알려져 있으며 그래프 컬러링 문제의 효율적인 해 공간 탐색을 위한 많은 알고리즘들이 제안되었다. 혼합형 유전 알고리즘은 유전알고리즘의 장점인 광범위한 공간 탐색과 지역 최적화를 결합하여 다항시간 안에 해결 불가능한 넓은 해 공간을 효율적으로 탐색하기 위한 메타 휴리스틱의 일종이다. 본 논문에서는 이전 연구를 활용하여 복잡도가 큰 그래프에서도 효율적으로 해 공간을 탐색 가능한 유전 알고리즘을 제안한다. 실험을 통해 본 논문에서 제시한 유전 알고리즘이 최적해가 알려지지 않은 그래프 컬러링 예시에 대해 이전에 제시된 알고리즘들 보다 더 좋은 해를 찾음을 보인다.