(A) linear programming based ant colony optimization method for the maximum independent set problem선형 계획법 기반의 개미 군집 최적화 기법을 활용한 최대 독립 마디 문제에 관한 해법
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.
- Advisors
- Park, Sung Sooresearcher; 박성수researcher
- Description
- 한국과학기술원 :산업및시스템공학과,
- Publisher
- 한국과학기술원
- Issue Date
- 2017
- Identifier
- 325007
- Language
- eng
- Description
학위논문(석사) - 한국과학기술원 : 산업및시스템공학과, 2017.2,[iii, 17 p. :]
- Keywords
Maximum independent set problem; Maximum weighted independent set problem; Ant colony optimization; Linear programming; Metaheuristic; 최대 독립 마디 문제; 최대 가중 독립 마디 문제; 개미 군집 최적화 기법; 선형계획법; 메타휴리스틱
- Appears in Collection
- IE-Theses_Master(석사논문)
- Files in This Item
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.