Publications
Detailed Information
다차원 다선택 배낭문제를 위한 새로운 보간알고리즘을 이용한 혼합형 유전 알고리즘 : Hybrid Genetic Algorithm for the Multiple-Choice Multidimensional Problem with Novel Repair Algorithm
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Advisor
- 문병로
- Major
- 공과대학 전기·컴퓨터공학부
- Issue Date
- 2013-02
- Publisher
- 서울대학교 대학원
- Description
- 학위논문 (석사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2013. 2. 문병로.
- Abstract
- 혼합형 유전 알고리즘은 유전 알고리즘의 공간탐색 능력과 지역최적화 알고리즘의 끌개를 능력을 조합한 효율적인 공간탐색 알고리즘이다.이 논문은 혼합형 유전 알고리즘을 이용하여MMKP문제를 위한 해를 찾는 제안한다. 다중선택 다중차원 배낭문제(multiple-choice multidimensional knapsack problem, MMKP)는배낭문제(Knapsack Problem, KP)를 변형시킨 문제로 매우 복잡한 문제로 알려져 있다. 이 논문은 MMKP문제 중에서 제약사항을 강력하게 바꾸어 해의 밀도가 매우 낮을때 해를 찾기위해 경향함수를 제안한다. 경향함수는 문제 공간에서하나의 해가 다른해로 변화될때 앞으로의 엔트로피를 가장 낮출 수 있는변화함수이다. 이러한 경향함수는 해밀도가 매우 낮은 MMKP문제를 푸는데 보간함수의 역할을 하며 효과적인 지역최적화 알고리즘과 결합되어 혼합형 유전알고리즘을 이룬다. 기존연구들과 비교하여 이러한 혼합형 유전 알고리즘이 더 낮은 해밀도에서 더 좋은 해를 찾음을 보인다.
- Language
- Korean
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.