목차

I. 서론 . . . . . . . . . . . . . . . . . . . . . . . 1
II. 관련연구 . . . . . . . . . . . . . . . . . . . . 4
2.1 유전알고리즘 . . . . . . . . . . . . . . . . . .. 4
2.2 유전알고리즘의구조 . . . . . . . . . . . . . . . .4
2.3 유전알고리즘의구성요소 . . . . . . . . . . . . .. 5
2.4 혼합형유전 알고리즘 . . . . . . . . . . . . . . . 8
2.5 다차원다선택 배낭문제 . . . . . . . . . . . . . . 9
2.5.1 건설적절차 . . . . . . . . . . . . . . . . . .. 9
2.5.2 MPGA . . . . . . . . . . . . . . . . . . . . .. 10
III. Tendency . . . . . . . . . . . . . . . . . . . . 13
3.1 MMKP의공간 . . . . . . . . . . . . . . . . . . .. 13
3.2 Tendency Approach . . . . . . . . . . . . . . . . 13
3.3 Tendency for MMKP . . . . . . . . . . . . . . . . 15
3.4 Tendency function . . . . . . . . . . . . . . . . 16
3.5 경향함수를위한유전알고리즘의Genetic Framework . . 16
3.5.1 유전자표현 . . . . . . . . . . . . . . . . . . 16
3.5.2 적합도함수 . . . . . . . . . . . . . . . . . . 17
3.5.3 교차와변이 . . . . . . . . . . . . . . . . . . 17
3.5.4 선택 . . . . . . . . . . . . . . . . . . . . . 17
3.5.5 대치 . . . . . . . . . . . . . . . . . . . . . 17
IV. Hybrid GA for MMKP . . . . . . . . . . . . . . . 22
4.1 Genetic Framework . . . . . . . . . . . . . . . . 22
4.1.1 유전자 표현 . . . . . . . . . . . . . . . . . . 22
4.1.2 적합도 함수 . . . . . . . . . . . . . . . . . . 23
4.1.3 교차와 변이 . . . . . . . . . . . . . . . . . . 23
4.1.4 선택 . . . . . . . . . . . . . . . . . . . . . 23
4.1.5 대치 . . . . . . . . . . . . . . . . . . . . . 23
4.1.6 보간알고리즘 . . . . . . . . . . . . . . . . . 24
4.1.7 지역최적화 알고리즘 . . . . . . . . . . . . . . 24
V. 실험결과 . . . . . . . . . . . . . . . . . . . . . 26
5.1 실험준비 . . . . . . . . . . . . . . . . . . . . 26
5.2 경향함수의 성능 . . . . . . . . . . . . . . . . . 27
5.3 MMKP문제의해결 . . . . . . . . . . . . . . . . . 29
VI. 결론 . . . . . . . . . . . . . . . . . . . . . . 34
참고 문헌 . . . . . . . . . . . . . . . . . . . . . . 35
Abstract . . . . . . . . . . . . . . . . . . . . . . 37