求解0/1背包問題的自適應(yīng)元胞粒子群算法

李枝勇,馬 良,張惠珍

(上海理工大學(xué)管理學(xué)院,上海200093)

求解0/1背包問題的自適應(yīng)元胞粒子群算法

李枝勇,馬 良,張惠珍

(上海理工大學(xué)管理學(xué)院,上海200093)

對(duì)0/1背包問題進(jìn)行研究,提出一種自適應(yīng)元胞粒子群算法。在算法設(shè)計(jì)過程中,重新定義粒子位置和速度的更新方程,引入自適應(yīng)因子,為有效粒子的主動(dòng)進(jìn)化和無效粒子的主動(dòng)退化提供依據(jù),新的編碼方式使得新產(chǎn)生的粒子能夠以更大的概率和更快的速度成為有效粒子,將元胞及其鄰居引入到算法中保持種群的多樣性,利用元胞的演化規(guī)則進(jìn)行局部?jī)?yōu)化,避免算法陷入局部極值。對(duì)多組不同規(guī)模的背包問題進(jìn)行仿真實(shí)驗(yàn),結(jié)果表明,該算法不僅可以有效求解0/1背包問題,而且能夠以較快的速度搜索到精度較高的次優(yōu)解甚至全局最優(yōu)解,具有較好的穩(wěn)定性。

粒子群優(yōu)化;0/1背包問題;自適應(yīng)因子;元胞自動(dòng)機(jī);組合約束優(yōu)化;NP難題

1 概述

0/1背包問題是運(yùn)籌學(xué)中的一個(gè)典型優(yōu)化難題[1],已被應(yīng)用于諸多領(lǐng)域,如預(yù)算控制、項(xiàng)目選擇、裝載問題、材料切割和投資問題等,并且還經(jīng)常作為其他問題的子問題加以研究。

就計(jì)算復(fù)雜性而言,背包問題屬于NP難題,隨著問題規(guī)模的增大,求解時(shí)間隨指數(shù)增長,在最壞的情況下,時(shí)間復(fù)雜度為O(2n)。因此,設(shè)計(jì)新的高效算法來求解背包問題具有重要的理論和實(shí)際意義[2-3]。從已有的研究成果來看,求解背包問題的方法主要有精確算法和啟發(fā)式算法兩大類。其中,精確算法包括分支界定法、動(dòng)態(tài)規(guī)劃法、遞歸法和回溯法等。啟發(fā)式算法主要包括貪心算法、遺傳算法、蟻群算法、蜂群算法、模擬退火算法、禁忌搜索算法、粒子群算法及以上幾種算法的改進(jìn)算法等。精確算法雖然可以得到精確解,但是當(dāng)物品數(shù)目較大時(shí),精確算法并沒有可行性。啟發(fā)式算法雖然不一定得到精確解,但可以得到次優(yōu)解,時(shí)間復(fù)雜度也比較低。

粒子群優(yōu)化[4](Particle Swarm Optimization, PSO)算法源于對(duì)鳥類捕食的行為研究,是Kennedy和Eberhart于1995年提出的仿生智能計(jì)算方法,具有概念簡(jiǎn)單、控制參數(shù)少、容易實(shí)現(xiàn)等優(yōu)點(diǎn)。目前,粒子群算法的研究成果大多是在對(duì)各類連續(xù)空間優(yōu)化問題的研究上所取得的,對(duì)離散優(yōu)化問題的研究相對(duì)較少,因此,開拓離散的PSO算法的應(yīng)用研究是一項(xiàng)很有價(jià)值的工作。有部分學(xué)者已經(jīng)將PSO算法用來解決背包問題,并取得了很好的效果[5-8],如文獻(xiàn)[5]定義了等值交換、異值變換以及變換序列等概念,并針對(duì)性地設(shè)計(jì)了一種適合求解0/1背包問題的特殊微粒群算法,具有一定的可行性,但是該算法用概率來引導(dǎo)變換序列的變換這一過程具有較強(qiáng)的隨機(jī)性,雖然可以增加算法的多樣性,但是可能會(huì)降低算法的收斂速度。本文在對(duì)粒子位置和速度更新公式進(jìn)行重新定義的基礎(chǔ)上,利用決策分析的相關(guān)知識(shí)定義了每個(gè)物品被選擇的機(jī)率,并結(jié)合元胞自動(dòng)機(jī)理論,豐富種群的多樣性,提出一種自適應(yīng)元胞粒子群算法(Adaptive Cellular Particle Swarm Optimization,ACPSO)來解決0/1背包問題。

2 基本粒子群算法

在PSO系統(tǒng)中,每個(gè)備選解被看作一個(gè)“粒子”,每個(gè)粒子根據(jù)自身的最佳“經(jīng)驗(yàn)”和種群的最佳“經(jīng)驗(yàn)”,在問題空間中向更好的位置飛行,這樣反復(fù)搜索,直到發(fā)現(xiàn)最優(yōu)解。PSO算法的數(shù)學(xué)表示如下:

設(shè)種群粒子數(shù)為 n,搜索的空間維數(shù)為 d。第i個(gè)粒子位置表示為向量Xi=(xi1,xi2,…,xid),速度為向量Vi=(vi1,vi2,…,vid),第i個(gè)粒子目前搜索到的最優(yōu)位置為向量Pi=(Pi1,Pi2,…,Pid),整個(gè)種群目前搜索到的最優(yōu)位置為向量 Pj=(Pj1,Pj2,…, Pjd),每個(gè)粒子的速度和位置分別按式(1)和式(2)進(jìn)行迭代更新:

其中,c1和c2為正常數(shù),稱為加速因子;R1和R2為均勻分布在[0,1]之間的隨機(jī)數(shù);w稱為慣性因子,較大時(shí)適于對(duì)解空間進(jìn)行較大范圍探查,反之亦然; t表示某一次迭代。粒子群初始速度和位置隨機(jī)產(chǎn)生,然后按式(1)和式(2)進(jìn)行迭代,直到算法滿足迭代終止條件。

3 自適應(yīng)元胞粒子群算法

3.1 速度和位置更新公式的重新定義

0/1背包問題可被描述為:給定n個(gè)物品和一個(gè)背包,物品i的價(jià)值為pi、重量為wi,(i=1,2,…,n)背包能容納的最大物品重量為C,現(xiàn)要求從這n個(gè)物品中選出若干件放入背包,使得放入物品的總重量不超過C,且總價(jià)值達(dá)到最大:

根據(jù)背包問題可行解的性質(zhì),解是由0和1組成的集合向量,所以第i個(gè)粒子的初始位置可以表示為向量Xi=round(rand(i,d))。同理,第i個(gè)粒子的初始速度可以表示為向量 Vi=round(rand(i, d))。至此,在求解之前必須給出各個(gè)粒子的速度和位置的更新公式的重新定義,定義如下:

Pi-Xi(t)和Pj-Xi(t)運(yùn)算操作定義為:

這樣定義了粒子群速度和位置更新公式的相關(guān)操作規(guī)則。通過這種定義可以將粒子群擴(kuò)展到背包問題的求解上。ACPSO實(shí)現(xiàn)只要將式(5)～式(9)帶入式(1)和式(2)即可。

3.2 自適應(yīng)因子

定義1 如果某個(gè)粒子所對(duì)應(yīng)的解滿足式(4),則稱該粒子為有效粒子,否則稱為無效粒子。

為了引導(dǎo)每個(gè)粒子能夠主動(dòng)地適應(yīng)環(huán)境,本文引入自適應(yīng)因子來推動(dòng)有效粒子的主動(dòng)進(jìn)化和無效粒子的主動(dòng)退化。針對(duì)0/1背包問題,自適應(yīng)因子是由d個(gè)0～1之間的小數(shù)組成的數(shù)字串(m1,m2,…,m3),mi表示物品i被選中放入背包的機(jī)率。這個(gè)機(jī)率由下面2個(gè)因素決定:

(1)物品i的單位重量?jī)r(jià)值avi,令avi=pi/wi;

(2)物品i的重量和背包容量的比率關(guān)系wci,令wci=C/wi;

不難發(fā)現(xiàn),avi和wci越大越好,可由下式得到自適應(yīng)因子:

由以上可以看出,mi和物品i放入背包的機(jī)率呈正比關(guān)系。

根據(jù)自適應(yīng)因子,可以對(duì)當(dāng)前每個(gè)有效粒子進(jìn)行主動(dòng)進(jìn)化:首先將m的各個(gè)元素由大到小進(jìn)行排序,然后按照該順序?qū)γ總€(gè)粒子進(jìn)行如下操作,當(dāng)該粒子位置的某個(gè)分量所對(duì)應(yīng)物品被選擇的概率mi＞rand()或者該分量為0,則將該分量設(shè)置為1,從而產(chǎn)生一個(gè)備選粒子,如果此時(shí)該備選粒子為有效粒子,就將該物品放進(jìn)背包里面,否則扔掉。

如果一個(gè)粒子為無效粒子,則對(duì)該粒子進(jìn)行退化處理:如果該粒子的某個(gè)分量所對(duì)應(yīng)的物品被選擇的機(jī)率mi＜rand()且該分量取值為1,則將該分量退化成0。然后,再次判斷該粒子是否為有效粒子,如果不是,則繼續(xù)重復(fù)前面的操作,直到滿足為止。

3.3 編碼方式

很多文獻(xiàn)在產(chǎn)生粒子的初始位置時(shí)都簡(jiǎn)單地定義當(dāng)產(chǎn)生的隨機(jī)數(shù)小于0.5時(shí)便取0,否則取1。然而,在經(jīng)過大量的實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證后發(fā)現(xiàn):用MATLAB中函數(shù)rand()產(chǎn)生的隨機(jī)數(shù),超過半數(shù)的均要大于0.5。這說明當(dāng)某個(gè)背包問題的最優(yōu)解中1較少,則會(huì)以很大的概率出現(xiàn)初始種群全部是無效粒子的情況,又因?yàn)楸疚乃岢龅乃惴ㄒ髤⑴c評(píng)價(jià)的粒子必須全都是有效粒子,為了避免算法在進(jìn)入循環(huán)迭代之前的初始化過程中出現(xiàn)由于無效粒子的存在,使得算法一直處在將無效粒子退化成有效粒子的循環(huán)往復(fù)的過程而使算法停滯不前的情況,這里給出一種新的有關(guān)粒子初始化的編碼方式,方法如下:如果rand()＜r,則x=1,否則,x=0。其中, r為一個(gè)常數(shù),這里稱作為被選率。

3.4 背包問題的元胞粒子群算法

元胞自動(dòng)機(jī)是一個(gè)時(shí)間離散化、狀態(tài)離散化的網(wǎng)格動(dòng)力模型,已成為以離散性為特點(diǎn)描述復(fù)雜行為的具有廣闊發(fā)展前景的方法。元胞在元胞空間里,按照演化規(guī)則有很多種變化,有助于保持種群的多樣性。

定義2 設(shè)物品選擇的集合 C=(c1,c2,…, ci,…,cn),其中,ci∈{0,1},ci=1表示選中物品i, ci=1表示未選中物品i。C中ci任意取值的排列組合的集合為元胞空間,可表示為L={CellX=(c1, c2,…,ci,…cn)},每個(gè)組合CellX為元胞。

定義3 moore鄰居類型:

其中,diff(CellY-CellX)≤γ為2個(gè)組合排序的差異,如無差異為0,有差異時(shí),最小為1;γ為差異度,這里γ取1。

定義4 擴(kuò)展moore鄰居類型:

其中,diff(CellY-CellX)≤λ為2個(gè)組合排序的差異,如無差異為0,有差異時(shí),最小為2。λ為差異度,這里λ取2。

定義5 元胞演化規(guī)則

根據(jù)元胞鄰居的定義計(jì)算其鄰居的目標(biāo)解,比較元胞和其鄰居的差異,選擇最好的目標(biāo)解。

背包問題的自適應(yīng)元胞粒子群算法的基本步驟如下:

Step 1 初始化粒子群中粒子的位置和速度,相關(guān)參數(shù)的設(shè)置以及自適應(yīng)因子的計(jì)算;

Step 2 設(shè)粒子自身最佳位置pbest為當(dāng)前位置,設(shè)初始群體最佳粒子的位置為gbest;

Step 3 判斷算法是否滿足結(jié)束條件,如果滿足,轉(zhuǎn)Step8,否則執(zhí)行Step4;

Step 4 根據(jù)式(1)和式(2)來更新粒子的位置和速度;

Step 5 粒子主動(dòng)進(jìn)化,更新gbest和pbest,如果粒子的gbest和pbest相等,則將該粒子的位置重新初始化,其他參數(shù)不變;

Step 6 按元胞鄰居的定義,在鄰居范圍內(nèi)演化,記錄最好的解,再次更新gbest和pbest;

Step 7 迭代次數(shù)加1,轉(zhuǎn)Step3;

Step 8 輸出結(jié)果,算法結(jié)束。

在算法運(yùn)行的過程中,粒子初始化、粒子位置更新和粒子的主動(dòng)進(jìn)化過程中都伴隨有對(duì)該粒子所對(duì)應(yīng)解是否符合約束規(guī)則的判斷以及當(dāng)粒子不符合約束規(guī)則時(shí)對(duì)該粒子進(jìn)行主動(dòng)退化的過程。

這里,定義去掉Step6這一過程后的算法為自適應(yīng)粒子群算法,方便起見,記作算法1;在Step6進(jìn)行moore鄰居類型演化的算法為自適應(yīng)元胞粒子群算法,方便起見,記作算法2;在Step6進(jìn)行moore擴(kuò)展鄰居類型演化的算法為自適應(yīng)擴(kuò)展元胞粒子群算法,方便起見,記作算法3。

4 仿真實(shí)驗(yàn)

為了比較上述3種算法解決實(shí)際問題的能力,從中找出一種較好的算法作為本文提出的算法,本文選用各種文獻(xiàn)中普遍使用的9組測(cè)試算例,其中涉及到不同規(guī)模的0/1背包問題。實(shí)驗(yàn)所用硬件為Core(TM)2 Duo CPU為 2.93 GHz,內(nèi)存為1.93 GB,軟件為Windows XP和Matlab。

4.1 測(cè)試算例

測(cè)試用到的9組算例如下:

算例1 物件個(gè)數(shù)d=10,最大重量限制C= 269,各個(gè)物件重量w=[95,4,60,32,23,72,80,62, 65,46],各個(gè)物件價(jià)值p=[55,10,47,5,4,50,8,61, 85,87],最優(yōu)值為295[9]。

算例2 物件個(gè)數(shù)d=20,最大重量限制=878,各個(gè)物件重量w=[92,4,43,83,84,68,92,82,6, 44,32,18,56,83,25,96,70,48,14,58],各個(gè)物件價(jià)值p=[44,46,90,72,91,40,75,35,8,54,78,40,77, 15,61,17,75,29,75,63],最優(yōu)值1 024[9]。

算例3 物件個(gè)數(shù)d=20,最大重量限制C= 878,各個(gè)物件重w=[44,46,90,72,91,40,75,35, 8,54,78,40,77,15,61,17,75,29,75,63],各個(gè)物件值p=[92,4,43,83,84,68,92,82,6,44,32,18,56, 83,25,96,70,48,14,58],最優(yōu)值1 042。不難發(fā)現(xiàn),算例3是將算例2的物件重量矩陣和物件價(jià)值矩陣對(duì)調(diào)了一下,但是有些文獻(xiàn)卻沒有發(fā)現(xiàn)這一不同[10]。

算例4 物件個(gè)數(shù)d=50,最大重量限制C= 959,各個(gè)物件重量w=[95,39,69,63,49,104,56, 58,47,23,17,129,91,28,77,125,73,5,103,63,76, 23,47,79,119,125,26,119,79,56,50,75,12,26,31, 43,41,38,29,21,14,9,3,17,8,8,9,7,4,5],各個(gè)物件價(jià)值p=[293,291,290,280,278,274,269,265, 248,247,245,245,241,234,229,228,222,216,214, 191,191,187,171,170,164,152,142,132,131,126, 122,116,112,111,110,106,77,76,74,73,69,67,42, 41,35,33,30,29,28,26],最優(yōu)值為4 882[11]。

算例5 物件個(gè)數(shù)d=100,最大重量限制C=3 820,各個(gè)物件重量w=[54,95,36,18,4,71,83,16, 27,84,88,45,94,64,14,80,4,23,75,36,90,20,77, 32,58,6,14,86,84,59,71,21,30,22,96,49,81,48, 37,28,6,84,19,55,88,38,51,52,79,55,70,53,64, 99,61,86,1,64,32,60,42,45,34,22,49,37,33,1, 78,43,85,24,96,32,99,57,23,8,10,74,59,89,95, 40,46,65,6,89,84,83,6,19,45,59,26,13,8,26,5, 9],各個(gè)物件價(jià)值p=[297,295,293,292,291,289, 284,284,283,283,281,280,279,277,276,275,273, 264,260,257,250,236,236,235,235,233,232,232, 228,218,217,214,211,208,205,204,203,201,196, 194,193,193,192,191,190,187,187,184,184,184, 181,179,176,173,172,171,160,128,123,114,113, 107,105,101,100,100,99,98,97,94,94,93,91,80, 74,73,72,63,63,62,61,60,56,53,52,50,48,46,40, 40,35,28,22,22,18,15,12,11,6,5],最優(yōu)值為15 170[11]。

算例6 物件個(gè)數(shù)d=100,最大重量限制C= 6 718,各個(gè)物件重量w=[54,183,106,82,30,58, 71,166,117,190,90,191,205,128,110,89,63,6, 140,86,30,91,156,31,70,199,142,98,178,16,140, 31,24,197,101,73,169,73,92,159,71,102,144, 151,27,131,209,164,177,177,129,146,17,53,164, 146,43,170,180,171,130,183,5,113,207,57,13, 163,20,63,12,24,9,42,6,109,170,108,46,69,43, 175,81,5,34,146,148,114,160,174,156,82,47, 126,102,83,58,34,21,14],各個(gè)物件價(jià)值p=[597, 596,593,586,581,568,567,560,549,548,547,529, 529,527,520,491,482,478,475,475,466,462,459, 458,454,451,449,443,442,421,410,409,395,394, 390,377,375,366,361,347,334,322,315,313,311, 309,296,295,294,289,285,279,277,276,272,248, 246,245,238,237,232,231,230,225,192,184,183, 176,174,171,169,165,165,154,153,150,149,147, 143,140,138,134,132,127,124,123,114,111,104, 89,74,63,62,58,55,48,27,22,12,6],當(dāng)前最優(yōu)值為26 559[12]。

算例7 物件個(gè)數(shù)d=100,最大重量限制C= 999.60,各個(gè)物件重量w=[94,81,8,62,21,83,85, 45,48,81,4,64,59,97,96,14,21,59,34,68,36,2,3, 65,26,48,25,17,11,97,43,23,24,48,56,73,54,15, 98,99,47,93,78,68,24,52,8,89,100,7,9,46,8,40, 77,46,76,78,7,32,92,11,93,75,6,60,64,15,99, 30,99,61,17,3,31,34,76,68,79,91,95,25,73,43, 89,9,12,31,71,24,19,70,76,14,50,85,40,78,12, 6],各個(gè)物件價(jià)值p=[94,60,88,18,39,57,4,74, 86,77,59,45,74,99,46,68,99,83,23,85,80,41,58, 11,35,73,100,2,79,58,70,40,6,9,26,2,7,92,40, 45,65,50,80,53,37,84,14,14,72,41,46,76,13,78, 77,77,49,29,63,61,32,2,6,47,31,46,35,85,39, 64,52,24,25,26,50,81,89,61,44,95,40,27,83,81, 85,32,60,91,44,54,31,48,50,94,32,83,24,40,43, 11],當(dāng)前最優(yōu)值為2 656,本文最優(yōu)值為2 660[13]。

算例8 算例8和算例7的區(qū)別僅僅在于最大重量限制和當(dāng)前最優(yōu)值不一樣,算例8的最大重量限制C=2 499,當(dāng)前最優(yōu)值為4 142,其他相關(guān)數(shù)據(jù)均一樣。本文最優(yōu)值為4 143[13]。

算例9 算例9和算例7的區(qū)別僅僅在于最大重量限制和當(dāng)前最優(yōu)值不一樣,算例9的最大重量限制C=3 998.4,當(dāng)前最優(yōu)值為4 985,其他相關(guān)數(shù)據(jù)均一樣。本文最優(yōu)值為4 986[13]。

4.2 參數(shù)設(shè)置

慣性權(quán)重因子w=0.8,學(xué)習(xí)因子c1=c2=2,種群規(guī)模50,最大迭代次數(shù)500,被選率為0.5(算例7除外,為0.009)。

4.3 測(cè)試結(jié)果及分析

3個(gè)算法各自獨(dú)立運(yùn)行30輪,尋優(yōu)目標(biāo)均為當(dāng)前最新文獻(xiàn)給出的最好值(算例7、算例8和算例9除外,這3個(gè)算例的尋優(yōu)目標(biāo)分別為2 660,4 143和4 986,均優(yōu)于當(dāng)前文獻(xiàn)給出的最好值),各個(gè)算法在每輪尋優(yōu)的過程中算法停止的條件有 2個(gè),具體如下:一旦找到當(dāng)前最好值,該輪算法程序運(yùn)行結(jié)束,隨即轉(zhuǎn)入下一輪程序的運(yùn)行;當(dāng)算法程序運(yùn)行過程中,如果一直沒有找到當(dāng)前最好值,則達(dá)到最大迭代次數(shù)時(shí),該輪算法程序運(yùn)行結(jié)束.該實(shí)驗(yàn)統(tǒng)計(jì)的指標(biāo)有: 30輪獨(dú)立實(shí)驗(yàn)中的實(shí)驗(yàn)最好值、實(shí)驗(yàn)平均值和實(shí)驗(yàn)最差值;30輪獨(dú)立實(shí)驗(yàn)消耗總時(shí)間(單位: s);30輪獨(dú)立實(shí)驗(yàn)中尋找當(dāng)前最好值的成功次數(shù);30輪獨(dú)立實(shí)驗(yàn)中尋找當(dāng)前最好值的成功迭代次數(shù)中的最小迭代次數(shù)、平均迭代次數(shù)和最大迭代次數(shù)。實(shí)驗(yàn)結(jié)果見表1。其中“-”表示由于30次獨(dú)立實(shí)驗(yàn)中沒有找到當(dāng)前最好值,指標(biāo)無法統(tǒng)計(jì)。另外需要指出的是在統(tǒng)計(jì)指標(biāo)為“最小迭代”中有數(shù)據(jù)為0,指得是在沒有進(jìn)入循環(huán)前的初始化中已經(jīng)找到當(dāng)前最好值。

表1 實(shí)驗(yàn)結(jié)果比較

從表1中可以看出,雖然算法1運(yùn)行的時(shí)間最短,而且尋找算例4和算例6的當(dāng)前最好值的成功次數(shù)要多于算法2和算法3,尋找算例7的當(dāng)前最好值的成功次數(shù)要多于算法3,但是在尋找算例2和算例3的當(dāng)前最好值的成功次數(shù)要明顯少于算法2和算法3;算法3的缺點(diǎn)很明顯,主要體現(xiàn)在2個(gè)方面:一方面是其運(yùn)行的時(shí)間要遠(yuǎn)遠(yuǎn)大于其他兩個(gè)算法;另一方面針對(duì)算例6,算法3的實(shí)驗(yàn)最好值要劣于其他2個(gè)算法。所以,綜合運(yùn)行時(shí)間和解決問題能力2個(gè)方面考慮,算法2是本文所要提出的用于求解0/1背包問題的自適應(yīng)元胞粒子群算法。

4.4 算法比較

為了進(jìn)一步驗(yàn)證本文提出的求解0/1背包問題的自適應(yīng)元胞粒子群算法的性能,將該算法與其他算法進(jìn)行比較。鑒于文章篇幅的原因,這里只給出算例7、算例8和算例9的比較結(jié)果,比較的算法是文獻(xiàn)[13]提出的算法及原文用來比較的其他算法。算法獨(dú)自運(yùn)行30次,統(tǒng)計(jì)比較其中的最好值和平均值,統(tǒng)計(jì)結(jié)果見表2。

表2 算例7～算例9的4種算法性能比較

從表2中可以很明顯地看出,從最優(yōu)值這個(gè)角度來看,ACPSO尋優(yōu)獲得的最優(yōu)值均好于ETGA、ISGA和 AIOA尋優(yōu)獲得的最優(yōu)值,從而說明ACPSO的全局尋優(yōu)能力要優(yōu)于其他3種算法;從平均值這個(gè)角度來看,ACPSO尋優(yōu)獲得的平均值均要好于ETGA、ISGA和AIOA尋優(yōu)獲得的平均值,特別是算例7和算例8,ACPSO的優(yōu)勢(shì)更加明顯,從而說明ACPSO在解決問題上比其他3種算法具有更好的穩(wěn)定性。綜上可以得出:ACPSO的尋優(yōu)性能更好,要遠(yuǎn)遠(yuǎn)優(yōu)于其他算法。

5 結(jié)束語

本文提出一種自適應(yīng)元胞粒子群算法,通過對(duì)算法仿真實(shí)驗(yàn)發(fā)現(xiàn):引入了自適應(yīng)因子和元胞鄰居理論的自適應(yīng)元胞粒子群算法能夠解決文中算例的大部分問題,與其他算法相比具有更好的性能。本文算法主要優(yōu)勢(shì)在于能夠快速找到全局最優(yōu)解,即使找不到全局最優(yōu)解,也會(huì)以很快的速度收斂到距離全局最優(yōu)解較近的次優(yōu)解,因此,該算法具有一定的普遍適應(yīng)性,可以用來解決0/1背包問題。

[1] 馬 良.高級(jí)運(yùn)籌學(xué)[M].北京:機(jī)械工業(yè)出版社,2008.

[2] Srinivasan V,Varghese G.Fast Address Lookups Using Controlled Prefix Expansion[J].ACM Transactions on Computer Systems,1999,17(1):1-40.

[3] Gupta P,LinS,McKeownN.RoutingLookupsin Hardware at Memory Access Speeds[C]//Proc.of IEEE INFOCOM’98.San Francisco,USA:IEEE Press, 1998:1240-1247.

[4] Kennedy J,Eberhart R C.Particle Swarm Optimization [C]//Proc.of IEEE International Conference on Neural Networks.Perth,Australia:IEEE Press,1995:1942-1948.

[5] 沈顯君,王偉武,鄭波盡,等.基于改進(jìn)的微粒群優(yōu)化算法的0-1背包問題求解[J].計(jì)算機(jī)工程,2006,32 (18):23-24.

[6] 柳寅,馬 良.0-1背包問題的模糊粒子群算法求解[J].計(jì)算機(jī)應(yīng)用研究,2011,28(11):4026-4028.

[7] 馬慧民,葉春明,張爽.二進(jìn)制改進(jìn)粒子群算法在背包問題的應(yīng)用[J].上海理工大學(xué)報(bào),2006,28(1): 31-34.

[8] 高 尚,楊靜宇.背包問題的混合粒子群算法[J].中國工程學(xué),2006,8(11):94-98.

[9] 馬 良.蟻群優(yōu)化算法[M].北京:科學(xué)出版社,2008.

[10] 趙新超,韓 宇,艾文寶.求解背包問題的一種改進(jìn)遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(24): 34-36.

[11] 劉建芹,賀毅朝,顧茜茜.基于離散微粒群算法求解背包問題研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(13): 3189-3191.

[12] 賀毅朝,劉坤起,張翠軍,等.求解背包問題的貪心遺傳算法及其應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28 (11):2655-2657.

[13] 莊中文,錢淑渠.抗體修正免疫算法對(duì)高維0/1背包問題的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究,2009,26(8): 2921-2923.

編輯 索書志

Adaptive Cellular Particle Swarm Algorithm for Solving 0/1 Knapsack Problem

LI Zhi-yong,MA Liang,ZHANG Hui-zhen
(School of Management,University of Shanghai for Science and Technology,Shanghai 200093,China)

0/1 knapsack problem is studied,and adaptive cellular particle swarm optimization algorithm is presented.In the design of the algorithm,the rules about updating the particle’s velocity and position are redefined,an adaptive factor is introduced to provide a basis for the active evolution of the valid particle and the active degradation of the invalid particle,a new coding mode is given to make new particles be valid with great probability and fast speed,cellular and its neighbor are introduced into the algorithm to maintain the swarm’s diversity and the algorithm uses evolutionary rule of cellular in local optimization to avoid local optima.Simulation experimental results of different scale 0/1 knapsack problem and comparisons with other algorithms show that the algorithm not only can solve the 0/1 knapsack problem effectively,but also can get the good second-best solution even for the global optimal solution with a faster rate,and has a certain degree of stability

Particle Swarm Optimization(PSO);0/1 knapsack problem;adaptive factor;cellular automata;

1000-3428(2014)10-0198-06

A

TP301.6

10.3969/j.issn.1000-3428.2014.10.037

高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研聯(lián)合基金資助項(xiàng)目(20123120120005);上海市一流學(xué)科建設(shè)基金資助項(xiàng)目(S1201YLXK);上海高校青年教師培養(yǎng)計(jì)劃基金資助項(xiàng)目(slg12010);上海市教育委員會(huì)科研創(chuàng)新基金資助項(xiàng)目(14YZ090);上海市研究生創(chuàng)新基金資助項(xiàng)目(JWCXSL1202);上海理工大學(xué)博士科研啟動(dòng)基金資助項(xiàng)目(1D-10-303-002)。

李枝勇(1986-),男,碩士研究生,主研方向:系統(tǒng)工程,智能優(yōu)化;馬 良,教授、博士、博士生導(dǎo)師;張惠珍,講師、博士。

2013-10-22

2013-12-13E-mail:lizhiyong.2180869@163.com

中文引用格式:李枝勇,馬 良,張惠珍.求解0/1背包問題的自適應(yīng)元胞粒子群算法[J].計(jì)算機(jī)工程,2014, 40(10):198-203.

英文引用格式:Li Zhiyong,Ma Liang,Zhang Huizhen.Adaptive Cellular Particle Swarm Algorithm for Solving 0/1 Knapsack Problem[J].Computer Engineering,2014,40(10):198-203.

combinatorial constrained optimization;NP hard problem