Publications
Detailed Information
다차원 다선택 배낭문제를 위한 새로운 보간알고리즘을 이용한 혼합형 유전 알고리즘 : Hybrid Genetic Algorithm for the Multiple-Choice Multidimensional Problem with Novel Repair Algorithm
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.advisor | 문병로 | - |
| dc.contributor.author | 양재영 | - |
| dc.date.accessioned | 2017-07-14T02:48:59Z | - |
| dc.date.available | 2017-07-14T02:48:59Z | - |
| dc.date.issued | 2013-02 | - |
| dc.identifier.other | 000000008782 | - |
| dc.identifier.uri | https://hdl.handle.net/10371/122926 | - |
| dc.description | 학위논문 (석사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2013. 2. 문병로. | - |
| dc.description.abstract | 혼합형 유전 알고리즘은 유전 알고리즘의 공간탐색 능력과 지역최적화 알고리즘의 끌개를 능력을 조합한 효율적인 공간탐색 알고리즘이다.이 논문은 혼합형 유전 알고리즘을 이용하여MMKP문제를 위한 해를 찾는 제안한다. 다중선택 다중차원 배낭문제(multiple-choice multidimensional knapsack problem, MMKP)는배낭문제(Knapsack Problem, KP)를 변형시킨 문제로 매우 복잡한 문제로 알려져 있다. 이 논문은 MMKP문제 중에서 제약사항을 강력하게 바꾸어 해의 밀도가 매우 낮을때 해를 찾기위해 경향함수를 제안한다. 경향함수는 문제 공간에서하나의 해가 다른해로 변화될때 앞으로의 엔트로피를 가장 낮출 수 있는변화함수이다. 이러한 경향함수는 해밀도가 매우 낮은 MMKP문제를 푸는데 보간함수의 역할을 하며 효과적인 지역최적화 알고리즘과 결합되어 혼합형 유전알고리즘을 이룬다. 기존연구들과 비교하여 이러한 혼합형 유전 알고리즘이 더 낮은 해밀도에서 더 좋은 해를 찾음을 보인다. | - |
| dc.description.tableofcontents | 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 | - |
| dc.format | application/pdf | - |
| dc.format.extent | 1514232 bytes | - |
| dc.format.medium | application/pdf | - |
| dc.language.iso | ko | - |
| dc.publisher | 서울대학교 대학원 | - |
| dc.subject | MMKP | - |
| dc.subject | GA | - |
| dc.subject.ddc | 621 | - |
| dc.title | 다차원 다선택 배낭문제를 위한 새로운 보간알고리즘을 이용한 혼합형 유전 알고리즘 | - |
| dc.title.alternative | Hybrid Genetic Algorithm for the Multiple-Choice Multidimensional Problem with Novel Repair Algorithm | - |
| dc.type | Thesis | - |
| dc.contributor.AlternativeAuthor | Jaeyoung Yang | - |
| dc.description.degree | Master | - |
| dc.citation.pages | 37 | - |
| dc.contributor.affiliation | 공과대학 전기·컴퓨터공학부 | - |
| dc.date.awarded | 2013-02 | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.