다차원 다선택 배낭문제를 위한 새로운 보간알고리즘을 이용한 혼합형 유전 알고리즘

Abstract

혼합형 유전 알고리즘은 유전 알고리즘의 공간탐색 능력과 지역최적화 알고리즘의 끌개를 능력을 조합한 효율적인 공간탐색 알고리즘이다.이 논문은 혼합형 유전 알고리즘을 이용하여MMKP문제를 위한 해를 찾는 제안한다. 다중선택 다중차원 배낭문제(multiple-choice multidimensional knapsack problem, MMKP)는배낭문제(Knapsack Problem, KP)를 변형시킨 문제로 매우 복잡한 문제로 알려져 있다. 이 논문은 MMKP문제 중에서 제약사항을 강력하게 바꾸어 해의 밀도가 매우 낮을때 해를 찾기위해 경향함수를 제안한다. 경향함수는 문제 공간에서하나의 해가 다른해로 변화될때 앞으로의 엔트로피를 가장 낮출 수 있는변화함수이다. 이러한 경향함수는 해밀도가 매우 낮은 MMKP문제를 푸는데 보간함수의 역할을 하며 효과적인 지역최적화 알고리즘과 결합되어 혼합형 유전알고리즘을 이룬다. 기존연구들과 비교하여 이러한 혼합형 유전 알고리즘이 더 낮은 해밀도에서 더 좋은 해를 찾음을 보인다.