混合式遺傳演算法求解大型零壹多限制式背包問題

A hybrid genetic algorithm for the large-scale 0-1 multidimensional knapsack problem

黃弘景(Hung-Ching Huang)

指導教授 ： 陳茂生

國立清華大學/工學院/工業工程與工程管理學系/碩士(2006年)

摘要

此研究所探討的問題為零壹多限制式背包問題(0-1 multidimensional knapsack problem)，其為一基於多限制式下找尋價值最高之物件組合的最佳化問題。此問題為NP-hard，隨著問題維度增加，以最佳解演算法(Exact algorithm)求解的所需時間將急速上升。然而，現實生活中時常出現大型零壹多限制式背包問題，因此發展一個具效率且能獲得近似最佳解的演算法是有其必要性的。
此研究中，我們利用一混合式遺傳演算法求解大型零壹多限制式背包問題。在求解前，我們固定問題中部分的變數使其為零或壹。接著我們設計一遺傳演算法求解縮減後的問題，此遺傳演算法由多個混合式運算子所構成，其可使得搜尋更加有智慧與有彈性。
為驗證所提出演算法的有效性，我們首先在兩個著名的問題集上進行計算研究。接著我們基於文獻上所建議的方法產生數組大型零壹多限制式背包問題進行測試。計算結果顯示：（1）本研究所提出之演算法優於過去求解零壹多限制式背包問題的遺傳演算法。（2）本研究所提出之變數縮減程序有助於Chu與Raidl的遺傳演算法獲得較佳的解品質。（3）本研究所提出之演算法亦優於已使用變數縮減程序之Chu與Raidl的遺傳演算法。

關鍵字

零壹多限制式背包問題 ； 遺傳演算法

並列摘要

The 0-1 multidimensional knapsack problem (0-1 MKP) is the problem of finding a subset of items that yields maximum profit under several knapsack constraints. It belongs to the class of NP-hard problems. When the dimension increases, the computing time needed for exact methods increase rapidly. However, problems of high dimensionality often arise in the modeling of real-world applications, so we need to develop computationally efficient methods for approaching the optimums of them. Genetic algorithms (GAs) are intelligent and probabilistic search algorithm established upon the principles of natural evolution. They have been shown to be able to find good and fast solutions for hard optimization problems.
In this study, we propose a hybrid GA for the large-scale 0-1 MKP. Unlike the past GAs for the 0-1 MKP, we fix a large portion of variables to be 0 or 1 before applying GAs. Then we design a GA for solving the reduced 0-1 MKP (with less variables). The proposed GA is made up of several hybrid operators which are used to make the search more flexible and intelligent.
Computational study is conducted on the medium-scale problem sets taken from literature. We also test the proposed GA on several sets of randomly generated large-scale problems (with up to 10000 variables and 1000 constraints). Computational results show that: (1) The proposed GA is superior to all the GAs so-far designed for the 0-1 MKP. (2) The GAs proposed by Chu and Raidl respectively can also be improved significantly in solution quality and computing time if the proposed variable reduction procedure is incorporated into their algorithms. (3) The proposed GA also outperforms Chu and Raidl GAs in which the proposed variable reduction procedure is incorporated.

並列關鍵字

0-1 Multidimensional Knapsack Problem ； Genetic Algorithms

參考文獻

[Balas 1980] Balas, E. and C.H. Martin. (1980). “Pivot and complement－a heuristic for 0-1 programming,” Management Sciences 26, 86–96.

[Chu 1998] Chu, P. and J. Beasley. (1998). “A genetic algorithm for the multidimensional knapsack problem,” Journal of Heuristics 4, 63–86.

[Drexe 1988] Drexel, A. (1988). “A simulated annealing approach to the multiconstraint zero-one knapsack problem,” Computing 40, 1-8.

[Eilon 1971] Eilon, S., C.G. Watson, and N. Christofides. (1971). Distribution management: mathematical modeling and practical analysis, Hafner, New York.

[Frevi 2004] Freville, A. (2004). “The multidimensional 0-1 knapsack problem: An overview,” European Journal of Operational Research 155, 1-21.