淺談求解組合優化問題的幾種近似算法

摘要：現實生活中，為了最大限度地利用資源、節省開支，出現了許多最優化利用資源的問題，往往是要求求出最大值或最小值的。在優化問題中，比較常見的是組合優化問題。針對此類問題，也出現了不少求解的算法。該文對其中比較常用的幾種近似算法進行了總結，并通過一種典型的組合優化問題——裝箱問題的實例對各算法的優劣進行了比較。

關鍵詞：組合優化；近似算法；裝箱問題；NP問題；物流

中圖分類號：TP301.6文獻標識碼：A文章編號：1009-3044(2008)36-2819-02

Talking about Several Heuristic Algorithms Simply which Solve Optimizing Problem

MA Yu-ling

(School of Computer science， Shandong YingCai University， Jinan 250100， China)

Abstract: In real life， in order to maximize the use of resources， cost savings， many problems about the most optimal use of resources appear， they are often asked to derive the maximum or minimum value. In the optimization problem， the more common is combinatorial optimization problem. To such problems， there have been a lot of algorithms to solve them. In this paper， the author sum these heuristic algorithms which are commonly used ，and these algorithms are compared.through a typical combinatorial optimization problems - for example the problem of packing the pros and cons.

Key words: combinatorial optimization; heuristic algorithms; packing problems; NP problem; Logistics Industry

1 引言

所謂組合優化，是指在離散的、有限的數學結構上，尋找一個滿足給定條件，并使其目標函數值達到最大或最小的解。一般來說，組合優化問題通常帶有大量的局部極值點，往往是不可微的、不連續的、多維的、有約束條件的、高度非線性的NP完全問題。對于NP-hard問題，其求解是極為困難的。常見的啟發式算法有NF(Next Fit)近似算法，FF(First Fit)近似算法，FFD(First Fit Decreasing)近似算法，BF(best Fit)，BFD(Best Fit Deceasing)近似算法等。

裝箱問題作為一個經典的具有復雜約束條件的組合優化的問題，一直是學術界討論的熱點，它能否成功解決對現實生活和生產具有重要的指導意義。本文利用這幾種近似算法對裝箱問題分別進行求解，并通過分析求解結果，對這幾種算法進行比較。

2 問題描述

要將n個物品裝入許多箱子（最多n個箱子）。每個物品有重量（Wj>0），每個箱子有重量限制（Ci>0）。問題是尋找最好的將物品分配到箱子的方案，使得在每個箱子中物品的總重量不超過其限制，并且使用的箱子數量最少。

3 各算法的基本思想

下次適應算法(NF)：NF算法是最簡單也是最早研究的一個算法，它的處理方法是始終維持一個當前打開的箱子，對于每一個要裝入的物品，檢查該物品是否可以放入當前打開的箱子，如果無法裝入，則打開一個空箱子，裝入該物品，以該箱子作為當前的箱子。

首次適應算法(FF)：首次適應算法處理當前物品的時候，檢查所有非空箱子，找到第一個能夠放下當前物品的箱子并將該物品放入，否則開啟新的箱子。

最佳適應算法(BF)：與首次適應算法類似，唯一的區別是當物品裝箱時，不是直接裝在第一個可裝入的箱子中，而是裝入在最適合該物體的箱子中，如果沒有可裝入的箱子，則開啟空箱。

降序首次適應算法(FFD)：先對物品按降序排序，再按照首次適應算法進行裝箱。

降序最佳適應算法(BFD)：先對物品按降序排序，再按照最佳適應算法進行裝箱。

4 實例檢驗

筆者從省內某物流公司獲得一些數據，我們從中隨機抽取一份待裝物品清單對上述算法進行驗證。已知該公司采用的運輸車輛載重五噸，且待裝物品在裝車時不必考慮其體積。故這是經典的一維裝箱問題。下面分別上述幾種啟發式算法對其進行求解。

下面是各算法的求解結果，表中編號按對其對應物品的裝車順序進行排列，Ki(x，y)表示裝載車Ki在裝下x袋某編號物品后，剩余容量為y千克。

表2 下次適應算法求解結果表3 首次適應算法求解結果

表4 BF算法求解結果表5FFD算法求解結果

5 結果比較

綜合上述實例，我們得出如表7。

由此，可以很直觀地看出，對于本文提供的數據，首次適應（FF）算法和最佳適應（BF）算法取得了相同的結果，用車總數都是19輛；降序首次適應（FFD）算法和降序最佳適應（BFD）算法取得了相同的結果。不同算法之所以取得相同結果，是因為本實例中出現了多個相同大小的物品，比如編號為6的物品多達30件。從結果來看，下次適應算法是效率最低的，因為每個物品在裝入時，只有當前打開的箱子和空箱可以選擇，這必然造成裝箱的效率低下。而另外幾種算法都把所有的箱子分為兩大類，已裝物品的箱子和空箱子，當物品裝入時，優先在已裝物品的箱子中裝入，否則若找不到合適的箱子，則啟用空箱子，顯然，這樣可以充分的利用己開的箱子，盡量避免開啟新的箱子。其中降序首次適應和降序最佳適應取得的結果最佳，這是因為他們摒除了首次適應算法和最佳適應算法沒有事先對物品進行排序的缺點，所以得到比首次適應算法和最佳適應算法更優的求解方案。

6 結語

利用啟發式算法的思路可解決許多現實中的實際優化問題，比如：在金屬制造工業中，鋼片需要從大塊鋼片中切除，在建筑中經常需要從長度一定的棍子上切割不同長度的棒和管。電氣布線中的電線來自長度一定的線卷等等許多現實問題。從而優化利用資源，節省開支。

參考文獻：

[1] 邢文訓，謝金星. 現代優化計算方法[M].北京:清華大學出版社.

[2] 張立昂，譯.計算機和難解性-NP完全性理論導論[M].北京:科學出版社，1990.

[3] 韓禎祥，文福拴.模擬進化優化方法及其應用遺傳算法[J].計算機科學，1995，22(2):47-56.

[4] 鄧向陽，等.算法分析與設計[M].北京:冶金工業出版社，2006.

[5] Gehring H.A computer-based heuristic for packing pooled shipment containers[J].European Journal of Operational Research，1990，44(2):277-288.

[6] 趙素芬.幾何布局問題及其應用(一)[J].呼和浩特科技，1993(2):12-19.

[7] 武曉今，朱仲英.二維裝箱問題的一種實現方法[J].微型電腦應用，2003.

[8] 黃文奇，李慶華，余向東.求解空間Packing問題的擬物方法[J].應用數學學報，1968，9(4):443-453.

[9] 韓禎祥，文福拴.模擬進化優化方法及其應用遺傳算法[J].計算機科學，1995，22(2):47-56.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”