The ant colony optimization (ACO) is a probabilistic Meta-heuristic algorithm which has been developed in recent years. Originally ACO was used for solving the well-known Traveling Salesperson Problem. More recently, ACO has been used to solve many difficult problems. In this thesis, we develop an ant colony optimization method to solve the maximum independent set problems, which is known to be NP-hard. In this thesis, we suggest a new method for local information of ACO. Parameters of the ACO algorithm are tuned by evolutionary operations which have been used in forecasting and time series analysis. To show the performance of the ACO algorithm, the set of instances from discrete mathematics and computer science (DIMACS) benchmark graphs are tested, and computational results are compared with a previously developed ACO algorithm and other heuristic algorithms.
오랫동안 최대 독립 마디 문제는 많은 실생활에 관련된 문제에 대해 많은 적용이 되어왔다. 많은 현실 문제들이 최대 독립 마디 문제의 형태로 변환이 가능하기 때문이다. 예를 들어, 무선 통신망에서 개인과 개인을 연결하는 클러스터링 문제를 최대 독립 마디 문제로 변환이 가능하다. 하지만 최대 독립 마디 문제는 문제의 복잡도면에서 NP-hard로 분류되어 문제 크기가 커지면 쉽게 풀리지 않는다. 즉, 정확한 해를 도출하는 알고리즘은 최대 독립 마디 문제를 푸는데 있어서 수용 가능한 계산 시간을 보장하지 못한다. 이 문제에 관해 많은 연구가 이루어 졌고, 현재도 진행 중이지만 본 논문에서는 새로운 휴리스틱 알고리즘을 이용하여 최대 독립 마디 문제를 보다 효율적으로 좋은 해를 찾고자 한다. 개미 군집 최적화 기법은 최근에 개발된 확률적인 메타 휴리스틱 알고리즘이다. 초기에 개미 군집 최적화 기법은 비용을 최소화하는 hamiltonial cycle을 찾는 문제, 즉 Traveling Salesman Problem을 잘 풀면서 알려지게 되었다. 그리고 개미 군집 최적화 기법은 최근에 많은 어려운 문제를 푸는데 사용되고 있다. 먼저 개미 군집 최적화 알고리즘을 TSP 문제에 어떻게 적용하였는가에 대한 간략하게 설명하고, 알고리즘을 최대 독립 마디 문제에는 어떤 방향으로 적용하였는가에 대해 설명하였다. 개미 군집 최적화 알고리즘에는 크게 두 가지 정보를 이용하는데, 그것이 광역 정보(global information), 지역 정보(local information)이다. 본 논문에서는 지역 정보를 계산하는 새로운 방법을 제안하였고, 개미 군집 최적화 기법을 이용하는데 필요한 각 매개변수들의 값을 현명하게 구하기 위해 수요 예측에서 매개 변수 값을 구하는 방법으로 사용되는 진화적인 방법(evolutionary operation)을 사용하였다. 본 논문에서의 개미 군집 최적화 알고리즘의 성능을 보여주기 위해 최대 독립 마디 문제를 푼 다른 개미 군집 최적화 알고리즘과 결과를 비교하였고, 다른 휴리스틱 알고리즘과도 결과를 비교하였다. 최대 독립 마디 문제의 예는 DIMACS의 benchmark graphs를 이용하였다.
