Ant colony optimization is a metaheuristic developed for solving many difficult combinatorial optimization problems. In this thesis, the ant colony optimization method is modified for solving the maximum independent set problem. We propose a new approach combining linear programming with the ant colony optimization method to define the local information. The experiments on instances from the discrete mathematics and computer science benchmark set show that the suggested method is comparable with the previous ant colony optimization algorithms. For the maximum weighted independent set problem, we compare the results solved by CPLEX with those solved by our method.
개미 군집 최적화 기법(ant colony optimization)은 여러가지 어려운 조합 최적화 문제들을 해결하기 위하여 개발된 메타휴리스틱이다. 본 논문에서는 최대 독립 마디 문제(maximum independent set problem)를 해결하기 위해 개미 군집 최적화 기법이 활용되었다. 선형계획법을 활용한 개미 군집 최적화 기법을 사용하여 지역 정보(local information)를 정의하였다. DIMACS(discrete mathematics and computer science)의 benchmark set을 이용한 실험에서는 본 논문에서 제안하는 방법이 이전의 개미 군집 최적화 기법들과 비슷한 성능을 보여주었다. 최대 가중 독립 마디 문제(maximum weighted independent set problem)에 대해서는 CPLEX와 그 성능을 비교하였다.
