1、混合遺傳算法在有色裝箱問題中的應用邱玉良,劉志忠河海大學應用數學 (系 ,南京 (210098E-mail :摘 要 :有色裝箱問題是經典裝箱問題的推廣,它在多處理器實時計算機系統的任務調度等 實際問題中有著很強的應用背景。為了更好的解決這個問題,本文將 C-BF (有色最佳適應算 法 與改進的遺傳算法相結合, 給出了一種新的混合遺傳算法, 用隨機產生實例的方法對本文 的算法和文獻中的近似算法做了比較,結果表明用本文的算法求解有色裝箱問題效果比較好。 關鍵詞 :裝箱問題;有色裝箱;混合遺傳算法;有色最佳適應算法1. 引言經典裝箱問題是把一定數量的物品放入容積 相同的一些箱子中,要求每個箱子中物

2、品體 積之和不超過箱子的容積并且所用的箱子數 目最少。有色裝箱問題是經典裝箱問題的推 廣,它最初是在支持容錯的多處理器實時計 算機系統的任務調度中被提出來的 1,在計 算機科學和工業領域中,有著廣泛的應用背 景,包括多處理器任務調度、內存管理、資 源分配、運輸計劃等,因此對其求解具有廣 泛的應用價值。從計算復雜性來講,裝箱問題是一個經典的 NP 完全問題 2,很難精確求解,由于目前 NP 完全問題不存在有效時間內求得精確解 的算法,因此就出現了各種求解裝箱問題的 近似算法如:下次適應 (NF、首次適應 (FF、 降序適應 (FD、 降序下次適應 (NFD、 最佳適 應 (BF等 3, 文獻 4

3、5已經表明有色裝箱問 題也是 NP 完全問題,與經典裝箱問題一樣, 出現了一些求解此問題的近似算法。這些近 似算法比較容易實現,運算速度快,各自有 其自身的優點與不足,但它們都不具有通用 性,并且在某些情況下的結果也不理想。為 了更好地求解有色裝箱問題筆者提出了一種 啟發式混合遺傳算法。遺傳算法 (GA(其詳 述參見 7作為一種有效的全局并行搜索工 具,具有簡單、通用、魯棒性強的特點,且 無需過多的專業知識。近年來其在求解最優 化問題中得到了越來越廣泛的應用,它的基 本思想是將某種編碼技術作用于被稱為個體 的二進制串 (也可以采用其它方式 , 然后模 擬有這些串組成的群體的進化過程,對這些 群

4、體進行選擇操作、交叉操作、變異操作, 通過尋求群體進化中的最優個體,得到所求 問題的最優解。它的主要特點是擅長全局搜 索, 而局部搜索不足, 且容易出現早熟現象, 研究表明, GA 可以用極快的速度達到最優解 的 90%, 但要達到真正的最優解要花費相當 長的時間,解決這一問題的方法可考慮對簡 單 GA 進行適當的改進,目前最為活躍的研 究領域是考慮 GA 與其它方法集成,即混合 遺傳算法。在這里, 筆者將 GA 與 C-BF 算法相結合, 構 成一種啟發式混合遺傳算法(G-CBF 對有 色裝箱問題進行了求解。C-BF 算法(有色最佳適應算法 :在對有色 物品進行裝箱時,把待裝物品裝入這樣的已

5、 打開的箱子里(把已經裝過物品的箱子稱為 已打開的箱子 (1待裝物品的顏色與箱子中 所有物品的顏色都不相同; (2箱子所剩容積 大于物品體積,且與物品體積最接近;如果 沒有這樣的已打開的箱子則把待裝物品裝入 一個新箱子;直到所有物品都被裝入箱子為 止。2. 有色裝箱問題及其算法2.1 問題描述有色裝箱問題:給定 n 個物品的一個序列 12, , , n nL a a a=L,物品(1 ia i n 的大小( (0,1i v a ,顏色 (1 i C i k ,其中物品 的 顏 色 數 目 為 (, K K N K 是常數 ,21, , B B L為一個由單位容積的箱子組成的無限序列。要求:每一

6、物品只能裝入到唯一的箱子中, 每一個箱子中物品大小之和不能超過 1,同 一個箱子中物品的顏色互不相同,如何使用 最少的單位容積的箱子,裝下所有的物品?2.2 數學模型令12, , , n n L a a a =L 為任意給定的 n個物品的一個序列, 物品 (1 i a i n 的大小( (0,1i v a ,顏色 (1 i C i k ,其中物品的顏色數目不超過 (, K K N K 是常數 , 若 設所用的箱子數為 m , 將這 m 個箱子按被用 的 先 后 順 序 分 別 記 為12, , , m B B B L , 記(1, 2, , j B j m =L 號箱子中所裝物品的下標集為jI

7、 ,對于jI 內的任意兩個元素 p 、 q , 必須滿足p q C C ;令(j f B 表示裝入箱子jB 中的所有物品的體積之和。因此有:min m121211( 1, , , 1, 2, , . ( (, 1,2, , ( ( jj k j k k k I j k k I m nj i j i v a k k I C C j m s t f B v a j m f B v a =K K 、2.3 已有的算法KC-A 算法 4:首先把箱子分成 K 類, 物品 序列中第 i 個具有這種顏色的物品只能裝在 第 i 類箱子中, 從而保證相同顏色的物品不會 出現在同一類箱子中,然后在任何一類箱子 類

8、內部,物品的放置采用近似策略 A ,我們稱這樣的算法為以 A 為基礎的 K - 分類算 法,記為 KC -A 算法,相應的,當算法采 用 FF 算法時,則得到 KC -FF 算法。 JCBP 算法 5:首先把待裝物品以大小為標準 降序排列,從左端把第一個物品裝入第一個 箱子 , 然后從右往左依次查看物品, 如果所 查看的物品滿足:物品顏色與當前箱(把正在往里面裝物品的 箱子稱為當前箱內所裝物品的顏色都不相 同;物品的體積不大于當前箱的剩余容積; 則把這個物品裝入當前箱,并檢查下一個物 品,直到沒有可以裝箱的物品為止,然后打 開一個新箱子,把左端的第一個物品裝入, 再從右端開始查找滿足條件 (1

9、(2物品并裝 箱;如此操作直到所有物品都被裝箱為止。 SCPF-A 算法 6:首先把物品按顏色種類分 類,將相同顏色的物品分成一類,放置時按 照相同顏色的物品首先放置的原則,即把具 有顏色1C 的所有物品先分別放在不同的箱子里,然后再處理具有顏色2C 的所有物品,直到把所有顏色的物品都放置完畢,在放置的過程中,相同顏色的物品不能放在相同的 箱子中,每個箱子中物品體積之和不能超過箱子的體積。如果每類物品都采用經典裝箱 問題的近似算法 A 放置,則記為 SCPF -A;例如:當算法 A 選取的是 FF 算法時,則得 到 SCPF -FF 算法。3. 基于混合遺傳算法求解 3.1 混合遺傳算法的實現

10、本文用每條染色體所用的箱子數 m 作為 目標函數,即 ( f X m =。適應度函數設為( ( F X M f X =,其中 ( M f X >。遺傳算法中的交叉操作有多種方式,比 如:單點交叉、兩點交叉、多點交叉、部分 匹配交叉等。本文采用兩點交叉算子,具體 操作如下:一對染色體 A 、 B 進行交配,交 配后,把 A 的交配區域加到 B 的前面得到' B , 把 B 的交配區域加到 A 的前面得到 ' A ;然后在 ' A 中自交配區域后依次刪除與交配 區域中的基因相同的基因,得到新的染色體1A ,對 ' B 采用同樣的處理方法得到新的染色體 1B ,

11、 這樣就得到了兩條新的染色體 1A 、1B 。本文應用了兩點對換變異算子,其操作過程是:以較小的概率 m p 產生變異基因 g ,然后Step1 初 始 化 設 置 進 化 代 數 計 數 器0t =, 設置最大進化代數 T ,設置群體規模 M , 隨機生成 M 個從 1到 n 的全排列作為第一代染色體 (0p ,設置交叉概率 c p ,設置變異概率m p 。Step6 群體 ( p t 經過選擇、 交叉、 變異操 作后得到下一代群體 (1 p t +,終止條件判 斷,若 t T ,則 1t t =+,轉到 Step2;若t T >, 則以進化過程中所得到的具有最大適應度的個體作為最優裝

12、箱順序輸出,并輸出 所用箱子數 ( M F X (同時可以輸出裝 箱方案 。4. 算例及與其它算法的比較4.1 算例設L = 0.3(A,0.3(C,0.8(B,0.4(C,0.2(A, 0.5(C,0.7(C,0.3(B,0.7(B,0.9(A,0.5(B, 0.6(B,0.8(B,0.6(A,0.4(C,0.7(A,0.3(C, 0.1(A,0.1(B,0.2(B為給定的物品序列,其中 A , B , C 表示三種 不同的顏色,應用本文的算法,設置 5T =,10M =, 0.5c p =, 0.02m p =,計算結果為:10m =,為最優解。應用 JCBP 算法和 SCPF-A 算法,

13、分別得 12m =和 11m =。4.2 與其它算法的比較筆者應用隨機產生實例的方法對本文的算法 和 JCBP算法、 SCPF-A 算法進行了比較, 實驗證明本文的算法比起它算法具有更好的 裝箱效果,它們的比較結果如表 1所示:表 1 混合遺傳算法與其它近似算法的比較物 品 個 數 N 顏色數KSCPF-FFD(箱子數JCBP(箱子數G-CBF (箱 子 數 12 19 51 49 124 156 246 298 405 401 479 473附注:由于文獻 56已經驗證了 JCBP 算法、 SCPF-A 算法比 KC-A 算法裝箱效果好,所 以本文沒與 KC-A 算法進行比較。5. 結論通過

14、試驗數據可以看出,用混合遺傳算法求 解色裝箱問題所得到的結果要比用近似算法 得到的結果好。但當物品數量比較大時,問 題變的比較復雜,不好驗證本文算法所求得 的解是否為最優解,并且用混合遺傳算法求 解的時間開銷有點大,這兩點有待于做進一 步的研究。 .參考文獻1 C L Liu, J Layland. Scheduling algorithms for multi programming in a hard real-timeenvioronmentJ. Journal ofACM.1973,10(1:174-189.2 M R Garey, D S Johnson. Computers and

15、 Intractability: Aguild to the Theory of NP-CompletenessM. New York: W H Freeman and Company ,1978.3 Coffman E G,Garey M R,Johnson D S. Approximation algorithms for bin packing: A surveyA. Hochnaum Ded. Approximation Algorithms for NP-Hard ProblemsC. Boston :PWS Publishing, 1996.46-93.4 顧曉東, 許胤龍, 陳國

16、良, 顧鈞 . 有色裝箱問題的 在 線 近 似 算 法 J. 計 算 機 研 究 與 發 展 .2002, 39(3:335-340.5 劉春霞,于洪霞 . 有色裝箱問題的一種新的近似 算法 J. 佳木斯大學學報 .2005, 23(4:606-609.6 董一鴻,趙杰 . 帶約束的一維裝箱問題近似算法 的研究 J.計算機工程與應用 .2003, 18:41-44.7 雷英杰,張善文,李續武,周創明 MATLAB 遺 傳算法工具箱及應用A Hybrid Genetic Algorithm for Coloring Bin-packing ProblemQiu Yuliang, Liu Zhiz

17、hong2. Dept. of Science, Hohai University, Nanjing (210098AbstractAs one of the constrained bin packing problem(BPP,coloring BPP has many important applications such as multi-processor real-time scheduling, ect. In order to solve this problem better, the paper proposes a new hybrid genetic algorithm, which is combined with C-BF(Coloring-Best Fitand improved genetic algorithm. The results of coloring BPP problems which are randomly produced w