印桂生，崔曉暉，董宇欣，楊雪

（哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001）

面向離散優(yōu)化問(wèn)題的改進(jìn)二元粒子群算法

印桂生，崔曉暉，董宇欣，楊雪

（哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001）

二元粒子群算法被廣泛用于求解離散組合優(yōu)化問(wèn)題。在求解離散優(yōu)化問(wèn)題時(shí)，二元粒子群算法會(huì)出現(xiàn)解空間利用率低，速度和狀態(tài)趨同以及退化和波動(dòng)等演化問(wèn)題。針對(duì)這些問(wèn)題，提出一種改進(jìn)的二元粒子群算法。算法使用Gray碼演化基編碼，混沌初始化過(guò)程，改進(jìn)速度和狀態(tài)調(diào)整方法以及子代處理方法用于提高種群利用率和種群多樣性。在不同類(lèi)型的檢驗(yàn)函數(shù)以及多選擇背包問(wèn)題上，和現(xiàn)有優(yōu)化算法及其他二元粒子群算法相比，改進(jìn)算法能夠獲得較高的收斂精度以及較快的收斂速度，體現(xiàn)出多離散優(yōu)化問(wèn)題的實(shí)際效用。

二元粒子群；Gray碼；混沌；子代處理；離散優(yōu)化

粒子群優(yōu)化（particle swarm optimization，PSO）用于求解連續(xù)解空間的優(yōu)化問(wèn)題［1］。在實(shí)際中，存在這大量離散優(yōu)化問(wèn)題［2?4］，為解決這類(lèi)問(wèn)題，學(xué)者們提出了用于離散問(wèn)題的二元PSO［5?10］。

隨問(wèn)題維度的上升，現(xiàn)有二元PSO通常增大種群規(guī)?；蛟黾拥螖?shù)來(lái)提高求解精度，導(dǎo)致算法的時(shí)間復(fù)雜度以及空間復(fù)雜度隨之升高，喪失了優(yōu)化算法在處理離散問(wèn)題上的實(shí)際效用。為此，本文提出一種面向離散問(wèn)題的改進(jìn)二元PSO算法。該算法采用的Gray碼演化基編碼方式，混沌初始化過(guò)程，改進(jìn)的速度和狀態(tài)調(diào)整過(guò)程以及子代處理過(guò)程，旨在問(wèn)題維度上升的情況下，仍能夠高效且穩(wěn)定的收斂到高精度的演化狀態(tài)，提高算法對(duì)離散問(wèn)題的實(shí)際效用。

1 經(jīng)典二元粒子群算法及其問(wèn)題

Kennedy借鑒經(jīng)典連續(xù)PSO的速度調(diào)整和狀態(tài)調(diào)整思路，設(shè)計(jì)了用于離散問(wèn)題的二元粒子群算法BPSO（binary particle swarm optimization）［5］，其速度和狀態(tài)調(diào)整過(guò)程表示為

式中：ωvi，j（t）為第t代的第i個(gè)粒子在第j維的速度，t）∈｛0，1｝分別表示第i個(gè)粒子的個(gè)體最優(yōu)位置和種群最優(yōu)位置。U（0，φ1）和U（0，φ2）生成（0，1）間的隨機(jī)數(shù)。vmax表示速度的上限。

式中：sig（x）為sigmoid函數(shù)，用于將速度變量轉(zhuǎn)換成（0，1）內(nèi)的概率。

BPSO以及基于BPSO的改進(jìn)算法［5?6，8?10］主要存在以下問(wèn)題：解空間的利用率較差。由于缺乏有效的演化基初始化策略，導(dǎo)致算法無(wú)法充分利用有限的種群規(guī)模。速度趨同現(xiàn)象。迭代后期，BPSO隨著各個(gè)維速度的不斷累加，演化基上各維狀態(tài)只能無(wú)限趨近于1，從而出現(xiàn)趨同現(xiàn)象［8］。狀態(tài)遺忘特征。BPSO現(xiàn)有狀態(tài)完全依賴(lài)于速度轉(zhuǎn)換后的概率，導(dǎo)致?tīng)顟B(tài)調(diào)整過(guò)程呈現(xiàn)遺忘特征。演化波動(dòng)以及退化現(xiàn)象。BPSO的收斂精度曲線(xiàn)隨迭代次數(shù)增加而不斷波動(dòng)且出現(xiàn)退化的現(xiàn)象。

針對(duì)上述問(wèn)題，提出一種面向離散優(yōu)化問(wèn)題的改進(jìn)二元粒子群算法（improved binary particle swarm opti?mization，IBPSO），采用混沌初始化種群，引入二維速度變量并設(shè)計(jì)子代處理過(guò)程。

2 高效離散粒子群算法

2.1 IBPSO的編碼方式

IBPSO的演化基編碼形式包括：用于適應(yīng)度計(jì)算以及滿(mǎn)足約束判斷的整數(shù)演化基形式I；用于中間狀態(tài)的二進(jìn)制BCD碼形式B；用于演化過(guò)程的Gray碼形式。各形式的表示以及轉(zhuǎn)換方法如下：

針對(duì)種群規(guī)模為s和問(wèn)題規(guī)模為n的離散問(wèn)題，種群中某一整數(shù)演化基Ik表示為

假設(shè)Ik中每一維ikl的取值約束為［al，bl］，則可通過(guò)ikl-al將ikl轉(zhuǎn)換為無(wú)符號(hào)的正整數(shù)i'kl進(jìn)而轉(zhuǎn)換為無(wú)符號(hào)的二進(jìn)制BCD碼Bkl，即

為便于IBPSO在約束范圍內(nèi)有效演化，通過(guò)左補(bǔ)0的方式使Bkl的寬度等于「lb（bl-al）。

式（4）的BCD編碼雖然是整數(shù)演化基的直觀(guān)二元表示，但存在Hamming懸崖問(wèn)題［9］，因此，IBPSO采用式（6）將BCD編碼的演化基轉(zhuǎn)換為對(duì)應(yīng)的Gray碼Gkl＝（gkl，1，gkl，2，…，gkl，d），并使用Gkl作為種群中速度和狀態(tài)調(diào)整的操作對(duì)象。

2.2 算法改進(jìn)思路

2.2.1 混沌初始化方法

可利用混沌過(guò)程產(chǎn)生初始種群，充分利用解空間，形成分布均勻的初始種群。IBPSO的混沌初始化的步驟為：

1）產(chǎn)生與問(wèn)題規(guī)模n一致的（0，1）隨機(jī)種子集合｛Z0l｝（l＝1，2，…，n）。

2）將Z0l作為輸入，通過(guò)式（6）所示的混沌發(fā)生器，產(chǎn)生2倍種群規(guī)模的｛Zkl｝（k＝1，2，…，2s）。

3）將具有同樣下標(biāo)k的ikl構(gòu)成候選初始整數(shù)演化基Ik＝（ik1，ik2，…，ikn）。根據(jù)適應(yīng)度，對(duì)2s個(gè)候選初始整數(shù)演化基進(jìn)行排序，選擇適應(yīng)度較優(yōu)的前s個(gè)不同個(gè)體作為初始種群。

4）根據(jù)l維的約束條件［al，bl］，通過(guò)式（7），將Zkl映射為相應(yīng)的整數(shù)變量ikl。

5）利用2.1節(jié)中的介紹的方法，將整數(shù)演化基轉(zhuǎn)換為Gray碼演化基，并初始化速度變量Vk。對(duì)于Vkl（l＝1，2，…，n）的每一維變量vkl，o，初始化為［vkl，o（t，0），vkl，o（t，1）］（o∈［1，2，…，d］），其中，vkl，o（t，0）為第t代第k個(gè)Gray碼演化基的第l維上所對(duì)應(yīng)二進(jìn)制的第o個(gè)分量趨近于0的程度，vkl，o（t，1）為趨近1的程度。vkl，o的初值為vkl，o（0，0）＝vkl，o（0，1）＝vmax／2。

2.2.2 改進(jìn)的速度調(diào)整過(guò)程

以二維速度向量為基礎(chǔ)，改進(jìn)BPSO的速度調(diào)整過(guò)程，采用式（8）調(diào)整演化基中每一分量gkl，o（o∈［1，2，…，d］）的速度。

式中：vkl，o（t-1，s）表示在t-1代演化基接近s的程度，pkl，o（t-1）表示在t-1代，個(gè)體k的最優(yōu)演化基在該維的取值，gkl，o（t-1）表示在t-1代，種群最優(yōu)演化基在該維的取值。ω為非慣性權(quán)重。當(dāng)s取0或1時(shí)，IBPSO依據(jù)vkl，o（t-1，s），pkl，o（t-1）和gkl，o（t-1）的取值情況，同時(shí)調(diào)整vkl，o（t，0）和vkl，o（t，1），如式（9）。

由于pkl，o（t-1），gkl，o（t-1）∈｛0，1｝，式（9）還可繼續(xù)轉(zhuǎn)換為4種形式，以其中pkl，o（t-1）＝1和gkl，o（t-1）＝1為例。

當(dāng)pkl，o（t-1）＝1時(shí)，說(shuō)明個(gè)體k的最優(yōu)演化基在該維的狀態(tài)為1，此時(shí)，為促進(jìn)個(gè)體k的快速收斂到最優(yōu)狀態(tài)，應(yīng)增強(qiáng)趨近于1的程度，同時(shí)，減弱趨近于0的程度。當(dāng)gkl，o（t-1）＝1時(shí)，說(shuō)明種群中最優(yōu)演化基在該維的狀態(tài)為1，為促進(jìn)個(gè)體k向全局狀態(tài)收斂，應(yīng)增強(qiáng)趨近于1的程度，同時(shí)，減弱趨近于0的程度。根據(jù)上述思路，粒子在解空間中可自由移動(dòng)，避免速度趨同現(xiàn)象。

2.2.3 改進(jìn)的狀態(tài)調(diào)整過(guò)程

IBPSO采用式（10）調(diào)整Gray碼演化基中每一分量gkl，o（o∈［1，2，…，d］）的狀態(tài)。

式中：U（0，1）為（0，1）的隨機(jī)數(shù)，sgn（x）為符號(hào)函數(shù)。當(dāng)x＞0時(shí)，sgn（x）＝1；否則，sgn（x）＝0，sig（x）為sig?moid函數(shù)。

以gkl，o（t-1）＝0為例，考察gkl，o（t-1）的相反取值gkl，o（t-1）所對(duì)應(yīng)的速度vkl，o（t-1，1）和隨機(jī)產(chǎn)生數(shù)值U（0，1）的大小關(guān)系，確定符號(hào)函數(shù)sgn的取值。當(dāng)sgn＝0時(shí)，說(shuō)明gkl，o（t-1）的取值更趨近于1，則利用式（10）將gkl，o（t-1）取反，當(dāng)sgn＝1時(shí)，說(shuō)明gkl，o（t-1）的取值更趨近于0，保持gkl，o（t-1）不改變。在gkl，o（t-1）＝1，式（10）的狀態(tài)調(diào)整思路同gkl，o（t-1）＝0。上述過(guò)程中IBPSO的狀態(tài)調(diào)整參考前一代的狀態(tài)，緩解了迭代過(guò)程中的狀態(tài)趨同問(wèn)題。

2.2.4 子代處理過(guò)程

將演化基上不滿(mǎn)足約束的維度調(diào)整到約束范圍內(nèi)，如式（11）所示：

篩選并形成子代的過(guò)程：將調(diào)整后的候選演化基I'（t）和父代演化基I（t-1）構(gòu)成數(shù)量為2s的集合IS＝｛I'（t），I（t-1）｝，按適應(yīng)度排序，將排序中適應(yīng)度較大且不同的前s個(gè)演化基形成子代I（t）。

2.3 IBPSO的主要步驟

1）執(zhí)行混沌初始化操作。生成初始Gray碼演化基G、速度變量V、種群和個(gè)體最優(yōu)位置。

2）速度以及狀態(tài)調(diào)整。更新速度變量，生成候選子代G'（t）。

3）按約束調(diào)整演化基。將不滿(mǎn)足約束的整數(shù)演化基調(diào)整為有效演化基。

4）篩選并形成子代。依據(jù)子代篩選過(guò)程，從IS中生成子代I（t）。

5）更新操作。更新演化基每一維的最優(yōu)位置以及種群最優(yōu)位置。

6）結(jié)束判斷。

2.4 IBPSO的時(shí)間復(fù)雜度

IBPSO的時(shí)間復(fù)雜度包括初始化、速度調(diào)整、狀態(tài)調(diào)整及子代處理等過(guò)程。初始化的時(shí)間復(fù)雜度為

O（n（2+2s）+2sz（n）+2slb2s+

速度和狀態(tài)調(diào)整過(guò)程時(shí)間復(fù)雜度為

子代處理的時(shí)間復(fù)雜度為

如果假設(shè)IBPSO設(shè)定的結(jié)束代數(shù)為tmax，則IBPSO時(shí)間復(fù)雜度為

2.5 IBPSO的收斂性分析

在任意代t，種群中每個(gè)的粒子，通過(guò)式（8）和（10）確定Ik轉(zhuǎn)換的Gray碼表示Gk上的每一維轉(zhuǎn)移概率pkl，o（t）。由于pkl，o（t）∈（0，1），因此，粒子的每一步轉(zhuǎn)移概率為（k）＞0，轉(zhuǎn)移過(guò)程構(gòu)成Markov鏈，即任意解間依概率可達(dá)。同時(shí)，IBPSO鄰代種群序列是單調(diào)的。由上述理論分析，IBPSO滿(mǎn)足依概率1收斂到全局最優(yōu)解的充要條件。

3 仿真分析

以檢驗(yàn)函數(shù)以及背包問(wèn)題為基礎(chǔ)，分析算法在經(jīng)典離散問(wèn)題和實(shí)際離散問(wèn)題上的尋優(yōu)效果。參數(shù)設(shè)置如表1所示。限定s＝10以及tmax＝100。

表1 PSO相關(guān)參數(shù)設(shè)定情況Table1 Experimental parameters setting of PSO

3.1 檢驗(yàn)函數(shù)的實(shí)驗(yàn)及結(jié)果分析

3.1.1 實(shí)驗(yàn)設(shè)計(jì)

本文選擇具有單峰、多峰等典型特征的檢驗(yàn)函數(shù)［11］構(gòu)成測(cè)試環(huán)境，如表2所示。

表2 檢驗(yàn)函數(shù)列表Table2 List of test functions

將BPSO［5］，NBPSO［7］和EBPSO?作為第1組對(duì)比算法，分析IBPSO的改進(jìn)效果。NBPSO：采用與IBPSO類(lèi)似的速度及狀態(tài)調(diào)整，但未采用混沌初始化以及子代處理過(guò)程。EBPSO?：采用混沌初始化但未采用子代處理過(guò)程。

將SPSO［13］、EnBPSO［14］以及MBPSO［15］作為第2組對(duì)比算法，分析IBPSO與其他改進(jìn)的二元粒子的求解差異。SPSO：與經(jīng)典BPSO的狀態(tài)調(diào)整方法相同，僅在速度調(diào)整過(guò)程中，速度變量偏向全局最優(yōu)的比例隨迭代次數(shù)的增加而增大。EnBPSO：在SPSO基礎(chǔ)上，引入非線(xiàn)性慣性權(quán)重。MBPSO：使用線(xiàn)性函數(shù)而非sig?moid函數(shù)。

3.1.2 結(jié)果分析

在檢驗(yàn)函數(shù)f1～f5上，分別取維度n＝｛10，30，50｝，計(jì)算IBPSO以及各算法執(zhí)行100次的實(shí)驗(yàn)結(jié)果，如表3所示。AVG為平均演化精度。ENUM為計(jì)算代價(jià)，z（n）為適應(yīng)度函數(shù)執(zhí)行一次計(jì)算的單位時(shí)間。

對(duì)于AVG指標(biāo)，BPSO無(wú)論在單峰檢驗(yàn)函數(shù)還是多峰檢驗(yàn)函數(shù)下，都無(wú)法收斂到全局最優(yōu)。NBPSO僅在高維檢驗(yàn)函數(shù)上，陷入局部最優(yōu)解。EBPSO?一定程度的緩解NBPSO陷入局部最優(yōu)解的問(wèn)題，但仍然無(wú)法收斂到全局最優(yōu)解。SPSO在低維度問(wèn)題中能夠收斂到全局最優(yōu)解，但在高維度問(wèn)題上難以收斂到全局最優(yōu)解。和SPSO相比，MBPSO對(duì)單峰問(wèn)題具有較好求解能力，但對(duì)多峰問(wèn)題較差。IBPSO無(wú)論是單峰還是多峰函數(shù)，均可有效收斂。

在衡量指標(biāo)ENUM上，SPSO、EnBPSO和MBPSO與BPSO的算法結(jié)構(gòu)類(lèi)似，因此，它們的ENUM與BP?SO相同。由于IBPSO和EBPSO?采用的混沌初始化過(guò)程，因此IBPSO和EBPSO?的ENUM數(shù)量增加了10個(gè)單位的z（n）。雖然增加了較少的計(jì)算代價(jià)，但I(xiàn)BP?SO和EBPSO?的收斂精度AVG普遍優(yōu)于BPSO和NB?PSO。

表3 各二元PSO算法在檢驗(yàn)函數(shù)上的實(shí)驗(yàn)結(jié)果Table3 Experimental results of the different binary PSO algorithms on the test functions

以多峰函數(shù)f3為例分析各算法在處理50維問(wèn)題時(shí)的收斂情況，如圖1所示。

圖1 各算法求解50維f3時(shí)的收斂情況Fig.1 Convergence of each algorithm on f2with 50 di?mensions

圖1 中，BPSO與IBPSO在收斂速度方面的差異較單峰函數(shù)f1更加明顯，在100代演化結(jié)束時(shí)，IBPSO能夠獲取f3的全局最優(yōu)值，但BPSO仍未收斂。SPSO和EnBPSO的收斂情況類(lèi)似，雖然波動(dòng)較低，但仍無(wú)法避免退化問(wèn)題。

上述分析表明：和其他算法相比，IBPSO能夠在有限迭代次數(shù)內(nèi)，收斂到理想狀態(tài)。

3.2 多選擇背包問(wèn)題實(shí)驗(yàn)及結(jié)果分析

多維多選擇背包問(wèn)題（multi?dimensional multi?choice knapsack problem，MMKP）是經(jīng)典0?1背包問(wèn)題的擴(kuò)展，其約束包括：物品分為M類(lèi)，指定第m個(gè)類(lèi)中最多有Nm個(gè)物品，第i類(lèi)中第j個(gè)物品的重量和價(jià)值分別為wij和vij，背包總?cè)萘繛镃，背包中對(duì)于一類(lèi)物品至多有一個(gè)，其目標(biāo)是最大化背包內(nèi)組合物品數(shù)量的收益。

實(shí)驗(yàn)數(shù)據(jù)來(lái)源自Brunel University提供的測(cè)試集［12］，選取該數(shù)據(jù)集中13個(gè)測(cè)試用例，每個(gè)測(cè)試用例中物品分類(lèi)數(shù)量從5個(gè)到400個(gè)不等，且各類(lèi)數(shù)量中物品數(shù)量相同。記錄運(yùn)行結(jié)果的平均值A(chǔ)VG以及適應(yīng)度最大值MAX，如表4所示，其中，M為物品類(lèi)別數(shù)，N為物品總個(gè)數(shù)，R為每類(lèi)物品數(shù)。

根據(jù)表4，在低維度多選擇背包問(wèn)題上，貪心算法能夠獲得較優(yōu)的收益平均值，但隨著物品種類(lèi)數(shù)量以及每類(lèi)物品數(shù)量的上升（M＞15和R＞10），GA，PSO，IB?PSO和EnBPSO和MPSO表現(xiàn)出較高的平均收益和最大收益。在智能優(yōu)化算法中，二元粒子群系列改進(jìn)算法（IBPSO，EnBPSO和MBPSO）所獲得的收益高于經(jīng)典優(yōu)化算法（GA和PSO）。

表4 各二元PSO算法在背包問(wèn)題上的實(shí)驗(yàn)結(jié)果Table4Experimental results of the different binary PSO algorithms on knapsack problem

綜合背包問(wèn)題的實(shí)驗(yàn)分析結(jié)果，在多選擇背包問(wèn)題維度上升時(shí)，適合采用IBPSO算法進(jìn)行求解。

4 結(jié)束語(yǔ)

針對(duì)現(xiàn)有二元PSO求解離散優(yōu)化問(wèn)題時(shí)存在的問(wèn)題，提出一種改進(jìn)的二元PSO算法（IBPSO）。實(shí)驗(yàn)結(jié)果表明，在經(jīng)典檢驗(yàn)函數(shù)以及實(shí)際背包問(wèn)題中，IBPSO較相同參數(shù)設(shè)定下其他優(yōu)化算法具有更高的收斂精度以及更有效的收斂過(guò)程，體現(xiàn)了對(duì)離散問(wèn)題的求解優(yōu)勢(shì)。

在今后的研究中，將IBPSO與其他離散問(wèn)題相結(jié)合，研究與問(wèn)題相關(guān)的特定啟發(fā)式過(guò)程，指導(dǎo)IBPSO求解相關(guān)領(lǐng)域的離散問(wèn)題。同時(shí)，基于策略融合是提高優(yōu)化算法的有效手段，可將IBPSO與其他離散演化策略相互融合，借鑒其他演化策略的收斂?jī)?yōu)勢(shì)，設(shè)計(jì)混合策略的離散優(yōu)化算法。

［1］ZHU Hanhong，WANG Yi，WANG Kesheng，et al.Particle swarm optimization（PSO）for the constrained portfolio opti?mization problem［J］.Expert Systems with Applications，2011，38（8）：10161?10169.

［2］ZHANG Zike，ZHOU Tao，ZHANG Yicheng.Personalized recommendation via integrated diffusion on user?item?tag tri?partite graphs［J］.Physica A：Statistical Mechanics and its Applications，2010，389（1）：179?186.

［3］WU Changjun，KALYANARAMAN A.An efficient parallel approach for identifying protein families in large?scale met?agenomic data sets［C］／／Proceedings of the 2008 ACM／IEEE Conference on Supercomputing［S.l.］，2008：1?10.

［4］CAVUSLU M，KARAKUZU C，KARAKAYA F.Neural i?dentification of dynamic systems on FPGA with improved PSO learning［J］.Applied Soft Computing，2012，12（9）：2707?2718.

［5］KENNEDY J，EBERHART R C.A discrete binary version of the particle swarm algorithm［C］／／Proceedings of the Con?ference on Systems，Man，and Cybernetics.Piscataway，USA，1997：4104?4109.

［6］QIN Jin，LI Xin，YIN Yixin.An algorithmic framework of discrete particle swarm optimization［J］.Applied Soft Com?puting，2012，12：1125?1130.

［7］MOJTABA A K，TOOSI K N.A novel binary particle swarm op?timization［C］／／Proceedings of the 15th Mediterranean Confer?ence on Control and Automation.［S.l.］，2007：33?41.

［8］RATHI A，RATHI P，VIJAY R.Optimization of MSA with swift particle swarm optimization［J］.International Journal of Computer Allication，2010，12（8）：28?33.

［9］GANESH M，KRISHNA R，MANIKANTAN K，et al.Entro?py based binary particle swarm optimization and classification for ear detection original research article［J］.Engineering Applications of Artificial Intelligence，2014，27：115?128.

［10］BANSAL J，DEEP K.A modified binary praticle swarm op?timization for knapsack problems［J］.Applied Mathematics and Computation，2012，218（22）：11042?11069.［11］CHEN Enxiu，LI Jianqin，LIU Xiyu.In search of the essential binary discrete particle swarm［J］.Applied Soft Computing，2011，11：3260?3269.

［12］YANG Xiaohua，YANG Zhifeng，YIN Xinan，et al.Chaos gray?coded genetic algorithm and its application for pollu?tion source identifications in convection?diffusion equation［J］.Communications in Nonlinear Science and Numerical Simulation，2008，13（8）：1678?1688.

［13］AIHARA K.Chaos and its applications［J］.Procedia IU?TAM，2012，5：199?203.

［14］De JONG K A.An analysis of the behavior of a class of ge?netic adaptive systems［D］.Ann Arbor：University of Michi?gan，1975：196?249.

［15］KHAN S，LI K F，MANNING E G，et al，Solving the knapsack problem for adaptive miltimedia system［J］.Stu?dia Informatica：Special Issue on Cutting，Packing and Knapsacking Problems，2001，9：157?178.

An Improved binary particle swarm optimization for discrete optimization problems

YIN Guisheng，CUI Xiaohui，DONG Yuxin，YANG Xue
（College of Computer Science and Technology，Harbin Engineering University，Harbin 150001，China）

Binary particle swarm optimization（BPSO）is wildly used to solve discrete combinational optimization problems.With the low amount of population size and limit iterations，BPSO would have the evolutional problems such as low utilization of solution space，convergence of the speed and status of particles，as well as the degradation and volatility during the iterations.To solve these problems，an improved binary PSO（IBPSO）is designed，which uses the Gray code evolution based coding，chaos initialization process of population，improved modification of the speed and status of particles and the off?spring processing to increase the diversity and utilization of the population.According to the experimental results on the test functions with different types and multiple choice knapsack prob?lems，IBPSO outperforms the existing optimization algorithms and other binary algorithms with higher precision solu?tion and faster convergence speed，which shows the practicality of multiple discrete optimization problems.

binary particle swarm optimization；Gray code；chaos；off?spring processing；discrete optimization

10.3969／j.issn.1006?7043.201306024

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1006?7043.201306024.html

TP181

A

1006?7043（2015）02?0191?05

2013?06?05.網(wǎng)絡(luò)出版時(shí)間：2014?11?27.基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61272186，61100007）；黑龍

江省自然科學(xué)基金資助項(xiàng)目（F200937，F(xiàn)201110）；黑龍江省博士后基金資助項(xiàng)目（LBH?Z12068）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目（HEUCF100608）.

印桂生（1964?），男，教授，博士生導(dǎo)師；

崔曉暉（1984?），男，博士研究生.

印桂生，E?mail：yinguisheng＠hrbeu.edu.cn.