Browse

다차원 다선택 배낭문제를 위한 새로운 보간알고리즘을 이용한 혼합형 유전 알고리즘
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
서울대학교 대학원
Keywords
MMKPGA
Description
학위논문 (석사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2013. 2. 문병로.
Abstract
혼합형 유전 알고리즘은 유전 알고리즘의 공간탐색 능력과 지역최적화 알고리즘의 끌개를 능력을 조합한 효율적인 공간탐색 알고리즘이다.이 논문은 혼합형 유전 알고리즘을 이용하여MMKP문제를 위한 해를 찾는 제안한다. 다중선택 다중차원 배낭문제(multiple-choice multidimensional knapsack problem, MMKP)는배낭문제(Knapsack Problem, KP)를 변형시킨 문제로 매우 복잡한 문제로 알려져 있다. 이 논문은 MMKP문제 중에서 제약사항을 강력하게 바꾸어 해의 밀도가 매우 낮을때 해를 찾기위해 경향함수를 제안한다. 경향함수는 문제 공간에서하나의 해가 다른해로 변화될때 앞으로의 엔트로피를 가장 낮출 수 있는변화함수이다. 이러한 경향함수는 해밀도가 매우 낮은 MMKP문제를 푸는데 보간함수의 역할을 하며 효과적인 지역최적화 알고리즘과 결합되어 혼합형 유전알고리즘을 이룬다. 기존연구들과 비교하여 이러한 혼합형 유전 알고리즘이 더 낮은 해밀도에서 더 좋은 해를 찾음을 보인다.
Language
Korean
URI
https://hdl.handle.net/10371/122926
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Electrical and Computer Engineering (전기·정보공학부)Theses (Master's Degree_전기·정보공학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse