混合遺傳算法在有色裝箱問題中的應(yīng)用

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

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

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

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

5、 打開的箱子里(把已經(jīng)裝過物品的箱子稱為 已打開的箱子 (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 ,其中物品 的 顏 色 數(shù) 目 為 (, K K N K 是常數(shù) ,21, , B B L為一個由單位容積的箱子組成的無限序列。要求:每一

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

7、 ,對于jI 內(nèi)的任意兩個元素 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 類箱子中, 從而保證相同顏色的物品不會 出現(xiàn)在同一類箱子中,然后在任何一類箱子 類

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

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

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

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

12、箱順序輸出,并輸出 所用箱子數(shù) ( M F X (同時可以輸出裝 箱方案 。4. 算例及與其它算法的比較4.1 算例設(shè)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 表示三種 不同的顏色,應(yīng)用本文的算法,設(shè)置 5T =,10M =, 0.5c p =, 0.02m p =,計(jì)算結(jié)果為:10m =,為最優(yōu)解。應(yīng)用 JCBP 算法和 SCPF-A 算法,

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

14、試驗(yàn)數(shù)據(jù)可以看出,用混合遺傳算法求 解色裝箱問題所得到的結(jié)果要比用近似算法 得到的結(jié)果好。但當(dāng)物品數(shù)量比較大時,問 題變的比較復(fù)雜,不好驗(yàn)證本文算法所求得 的解是否為最優(yōu)解,并且用混合遺傳算法求 解的時間開銷有點(diǎn)大,這兩點(diǎn)有待于做進(jìn)一 步的研究。 .參考文獻(xiàn)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. 計(jì) 算 機(jī) 研 究 與 發(fā) 展 .2002, 39(3:335-340.5 劉春霞,于洪霞 . 有色裝箱問題的一種新的近似 算法 J. 佳木斯大學(xué)學(xué)報(bào) .2005, 23(4:606-609.6 董一鴻,趙杰 . 帶約束的一維裝箱問題近似算法 的研究 J.計(jì)算機(jī)工程與應(yīng)用 .2003, 18:41-44.7 雷英杰,張善文,李續(xù)武,周創(chuàng)明 MATLAB 遺 傳算法工具箱及應(yīng)用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