趙小康， 盧厚清

（1.陸軍工程大學(xué)， 江蘇 南京 210014； 2. 31151 部隊(duì)， 江蘇 南京 210016）

0 引言

裝載問題屬于離散組合優(yōu)化問題， 有多個(gè)不同類型的民船（背包）、多種需要裝載的貨物（物品）和多重約束條件，目標(biāo)函數(shù)不唯一，且解空間是離散點(diǎn)的集合，可以將其歸為多約束背包問題（MKP，Multi-constrained Knapsack Problem）。

MKP 問題是一個(gè)NP-Hard 問題， 對(duì)于此類問題，國內(nèi)外很多專家都進(jìn)行了研究， 目前的解決方法主要分為兩類：一類是精確的求解方法，如枚舉法、動(dòng)態(tài)規(guī)劃方法、回溯法和分支定界法等；另一類是用啟發(fā)式算法來求解，如貪婪算法、遺傳算法、蟻群優(yōu)化算法、模擬退火算法、粒子群優(yōu)化算法等；近年來隨著智能優(yōu)化算法的不斷發(fā)展，布谷鳥搜索算法、雞群優(yōu)化算法、哈里斯鷹優(yōu)化算法等新的優(yōu)化算法也被用于解決背包問題。

采用精確的求解方法雖然原理簡(jiǎn)單、容易理解、使用方便，在較小規(guī)模的問題上該方法可以得到精確解，取得不錯(cuò)的計(jì)算效果； 但計(jì)算時(shí)間和計(jì)算復(fù)雜度會(huì)隨著物品數(shù)量增加呈指數(shù)增長(zhǎng)，隨著背包變大和物品數(shù)量的增多，用來求解背包問題會(huì)浪費(fèi)大量時(shí)間，占用大量存儲(chǔ)空間。使用智能優(yōu)化算法求解此類問題， 面對(duì)不斷復(fù)雜化和規(guī)模變大的問題， 可以在保持快速收斂計(jì)算的同時(shí)尋找到一個(gè)比較精確的解，在實(shí)際應(yīng)用取得較好的計(jì)算效果，對(duì)于生產(chǎn)生活具有重要意義。

通過查閱書籍和閱讀文獻(xiàn)可以知道， 使用粒子群優(yōu)化算法來解決類似0-1 背包類的離散優(yōu)化問題， 通過向上或向下取整的方式將實(shí)數(shù)的符號(hào)和小數(shù)部分去掉，直接轉(zhuǎn)化為正整數(shù)是可行的， 且用該方式求解的速度和解的質(zhì)量要優(yōu)于大多數(shù)其他智能優(yōu)化算法[1]，本文我們借助此思想，將布谷鳥搜索算法和粒子群算法結(jié)合起來，對(duì)算法進(jìn)行混合改進(jìn)來求解此問題。

1 粒子群優(yōu)化算法

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法，又稱為微粒群優(yōu)化算法， 是1995 年美國心理學(xué)家Kennedy 和電氣工程師Eberhart 通過觀察鳥群覓食行為，發(fā)現(xiàn)其有一定的規(guī)律， 進(jìn)而總結(jié)此類行為規(guī)律提出的群體智能優(yōu)化方法[2]。由于算法概念簡(jiǎn)明、易于實(shí)現(xiàn)，在解決優(yōu)化問題領(lǐng)域具有優(yōu)越性， 出現(xiàn)后迅速得到了各國研究者的認(rèn)可，目前已被用于多個(gè)領(lǐng)域。

1.1 算法原理

該算法主要將將鳥群的棲息地鳥巢抽象的看作空間中的解，每只鳥相當(dāng)于抽象空間中的一個(gè)粒子，每個(gè)粒子的運(yùn)動(dòng)軌跡都是在本身歷史最好位置和所有粒子當(dāng)前最優(yōu)位置的影響下，不斷尋找全局最優(yōu)解的過程[3]。 在該算法模型中，每個(gè)粒子都是可行解空間中的一個(gè)可行解，都有一個(gè)被優(yōu)化函數(shù)目標(biāo)所決定的適應(yīng)值， 每個(gè)粒子的運(yùn)動(dòng)狀態(tài)都使用一組速度和位置向量來進(jìn)行描述。 在初始化粒子種群中，各個(gè)粒子在空間中進(jìn)行不規(guī)則的運(yùn)動(dòng)，運(yùn)動(dòng)過程中，每個(gè)粒子都會(huì)去尋找本身的最優(yōu)位置，而整個(gè)粒子種群會(huì)尋找整個(gè)種群的最優(yōu)位置， 每個(gè)粒子的運(yùn)動(dòng)都會(huì)受到當(dāng)前自身最優(yōu)位置和整個(gè)種群當(dāng)前最優(yōu)位置的影響，經(jīng)過不斷的迭代后，找到問題的最優(yōu)解[4]。

1.2 數(shù)學(xué)模型

該算法的數(shù)學(xué)模型描述如下：規(guī)模為M 的粒子群在一個(gè)N 維的搜索空間中以一定的初速度進(jìn)行不規(guī)則運(yùn)動(dòng)，xi=（xi1，xi2， …，xim） 表示第i 個(gè)粒子的位置；vi=（vi1，xi2，…，vin）表示第i 個(gè)粒子的速度；pi=（pi1，pi2，…，pin）表示第i個(gè)粒子經(jīng)過n 次迭代后所經(jīng)過的最佳位置， 也稱為個(gè)體最優(yōu)（pbest，personal best）；g=（g1，g2，…，gn）表示所有粒子經(jīng)過n 次迭代后所搜尋到的最佳位置， 也稱為全局最優(yōu)（gbest，global best）。

在粒子群優(yōu)化算法中粒子位置和速度的更新公式如下：

關(guān)于該公式中：i∈[1，M]，d∈[1，N]；vid表示粒子的速度，xid表示粒子的位置；w 表示慣性權(quán)重因子（inertia weight）；c1、c2為加速常數(shù)（acceleration constants），也稱為學(xué)習(xí)因子；r1、r2為在[0，1] 之間均勻分布的隨機(jī)數(shù)；pbest表示個(gè)體最優(yōu)解，gbest 表示整個(gè)種群的全局最優(yōu)解。

式（3）中，對(duì)粒子的速度vi進(jìn)行了有關(guān)約束，將速度限制在[-vmax，vmax]這一區(qū)間；如果vmax過大，粒子就會(huì)速度過快，進(jìn)而飛越最優(yōu)解；如果vmax太小，粒子就會(huì)在很小的范圍內(nèi)運(yùn)動(dòng)，難以進(jìn)行整體搜索找到全局最優(yōu)解。

從式（1）可以看出，粒子群優(yōu)化算法的速度更新公式由三個(gè)部分共同構(gòu)成[5-6]。 第一部分表示粒子的歷史速度對(duì)當(dāng)前速度的影響， 該部分起到了平衡全局和局部搜索的作用， 參數(shù)w 是為了平衡粒子的局部搜索能力和擴(kuò)大對(duì)全局的搜索能力而引入的慣性系數(shù)。 第二部分反映粒子本身認(rèn)知模式（cognition modal）影響，表示粒子自身的歷史最優(yōu)位置對(duì)個(gè)體速度更新的影響， 使粒子可以在更大范圍內(nèi)搜索求解，以免只取得局部最優(yōu)解。第三部分反映社會(huì)模式（social modal）對(duì)粒子的影響，表示種群中各個(gè)粒子受整體中最好位置的影響，并向其靠攏，體現(xiàn)粒子之間進(jìn)行信息共享、互相學(xué)習(xí)、互相影響。 在三部分共同作用之下，粒子群基于信息共享，根據(jù)歷史經(jīng)驗(yàn)，在當(dāng)前個(gè)體最優(yōu)位置的基礎(chǔ)上不斷變化調(diào)整， 以此來尋找整個(gè)問題的最優(yōu)解。

1.3 算法步驟和流程

粒子群優(yōu)化算法的基本步驟為：

Step1：設(shè)置算法有關(guān)參數(shù)，生成初始種群，生成粒子初始的速度和位置；

Step2：計(jì)算各個(gè)微粒的適應(yīng)度函數(shù)值；

Step3：計(jì)算并更新每個(gè)微粒的最好位置，找出每個(gè)粒子自身的最優(yōu)位置pbest 和整個(gè)種群的最優(yōu)位置gbest；

Step4：按照公式（1）更新各個(gè)微粒的速度，按照公式（2）更新各個(gè)微粒的位置；

Step5： 比較種群中每個(gè)微粒當(dāng)前目標(biāo)值與其pbest 的目標(biāo)值， 如果當(dāng)前目標(biāo)值更優(yōu)，則用微粒的當(dāng)前位置和目標(biāo)更新其pbest；

Step6： 比較當(dāng)前所有pbest 和gbest 的 值， 更 新gbest；

Step7： 若未達(dá)到終止條件，轉(zhuǎn)Step4；若達(dá)到終止條件， 則輸出gbest 及其目標(biāo)值并停止算法。根據(jù)基本步驟，繪制流程圖見圖1。

圖1 粒子群優(yōu)化算法基本流程圖

2 布谷鳥搜索算法

布谷鳥搜索（Cuckoo Search，CS）算法，又稱杜鵑搜索， 于2009 年由劍橋大學(xué)Xin-She Yang 教授和S. Deb在研究杜鵑孕育雛鳥行為的基礎(chǔ)上， 結(jié)合部分鳥類和昆蟲在飛行過程中具有Lévy 飛行特點(diǎn)提出的一種智能優(yōu)化優(yōu)化算法[7]。 該算法提出后，由于其簡(jiǎn)單的結(jié)構(gòu)和高效的性能迅速成為研究的熱點(diǎn)，被廣泛應(yīng)用到諸多領(lǐng)域。

2.1 算法原理

布谷鳥是一種神奇的鳥類，其雌鳥不會(huì)自己孵蛋，而是使用侵略性手段占據(jù)別的鳥類的巢穴讓其他鳥類幫助其孵蛋，并且鳥巢內(nèi)一般還會(huì)有其他鳥類產(chǎn)下的蛋。有時(shí)候布谷鳥會(huì)將自己產(chǎn)下的鳥蛋讓其他鳥類一起孵化；有時(shí)候布谷鳥為了提高自己產(chǎn)生蛋的孵化概率會(huì)將鳥巢內(nèi)原有的鳥蛋推出巢內(nèi)；當(dāng)然，布谷鳥產(chǎn)下的蛋也會(huì)被鳥巢主人發(fā)現(xiàn)而毀壞或者放棄原有鳥巢重新搭筑巢穴。 在該算法模型中， 布谷鳥產(chǎn)蛋的每個(gè)鳥巢相當(dāng)于解空間的一個(gè)可行解，有一個(gè)被優(yōu)化函數(shù)目標(biāo)所決定的適應(yīng)值，可以用解空間的一個(gè)位置來描述，而該位置以符合Lévy 飛行的方式進(jìn)行變化。

2.2 數(shù)學(xué)模型

考慮建立算法數(shù)學(xué)模型的可行性， 布谷鳥的繁殖行為可以理想化概括為以下幾點(diǎn)：

（1） 每只布谷鳥每次隨機(jī)選擇一個(gè)宿主鳥巢產(chǎn)下一枚蛋，選擇的鳥巢為一個(gè)可行解。

（2）在任意選擇的所有鳥巢中，能夠被保留下來，并順利進(jìn)入下一代的被認(rèn)為是最好的。

（3）能夠被選擇產(chǎn)蛋的鳥巢的總數(shù)量是確定的，鳥巢原主人發(fā)現(xiàn)布谷鳥蛋的概率為pα，其中pα∈[0，1]，若被發(fā)現(xiàn)，則該鳥巢被淘汰。

（4）布谷鳥按照Lévy 飛行的方式尋找下一個(gè)鳥巢并產(chǎn)蛋，代替被淘汰的鳥巢。

布谷鳥搜索算法的具體求解過程如下： 在確定空間里隨機(jī)產(chǎn)生一定規(guī)模數(shù)量的鳥巢并產(chǎn)蛋， 選擇當(dāng)前最好的鳥巢并存儲(chǔ)，通過步長(zhǎng)公式變換鳥巢新位置并產(chǎn)蛋；如果布谷鳥蛋被其他鳥類發(fā)現(xiàn)，則代表該鳥巢被淘汰，需更新鳥巢位置，尋找新的鳥巢；尋找最好的鳥巢位置是一個(gè)不斷循環(huán)迭代的過程， 每次迭代都要計(jì)算當(dāng)前所有剩余鳥巢的位置；不斷重復(fù)上面的求解過程，就可以找到鳥巢的最好位置，也就是問題的最優(yōu)解。

2.3 算法步驟和流程

布谷鳥搜索算法的基本步驟為：

Step1：種群初始化，隨機(jī)選擇n 個(gè)鳥巢產(chǎn)蛋，生成初始解集；

Step2：計(jì)算每個(gè)鳥巢的目標(biāo)函數(shù)值，獲得初始全局最優(yōu)解；

Step3：通過Lévy 飛行更新鳥巢位置，獲得新解；

Step4：由于布谷鳥蛋可能被發(fā)現(xiàn)，根據(jù)淘汰機(jī)制和概率淘汰部分解；

Step5：對(duì)現(xiàn)有鳥巢和上一代剩余鳥巢進(jìn)行對(duì)比，將較好的位置保留下來，更新全局最優(yōu)解；

Step6：判斷迭代條件，若未達(dá)到終止條件，轉(zhuǎn)Step3；

Step7：輸出全局最優(yōu)解。

根據(jù)基本步驟，繪制流程圖見圖2。

圖2 布谷鳥搜索算法基本流程圖

3 R-CS-PSO 混合算法

每種智能算法都有優(yōu)點(diǎn)和缺點(diǎn)，沒有一種智能算法能完美的解決所有問題，于是人們?cè)趯?shí)際使用過程中會(huì)考慮對(duì)已有的智能算法進(jìn)行優(yōu)化改進(jìn)，在保持算法本身優(yōu)點(diǎn)的同時(shí)根據(jù)需要克服不足，以達(dá)到更好解決問題的效果。 目前，研究領(lǐng)域?qū)τ诹Ｗ尤核惴ǜ倪M(jìn)和布谷鳥搜索算法改進(jìn)都研究的比較多， 也取得了很好的應(yīng)用效果，解決了很多實(shí)際領(lǐng)域的問題，本文在查閱大量文獻(xiàn)基礎(chǔ)上，分析兩種算法的優(yōu)缺點(diǎn)，將兩種算法混合起來，并引入隨機(jī)變化的慣性系數(shù)，進(jìn)一步增進(jìn)算法的活躍度，以達(dá)到取長(zhǎng)補(bǔ)短的效果。

3.1 改進(jìn)思想

粒子群優(yōu)化算法具有搜索速度快、 尋優(yōu)效率高的特點(diǎn)， 且粒子可以根據(jù)歷史經(jīng)驗(yàn)并利用信息共享機(jī)制進(jìn)行位置更新， 但在計(jì)算后期大多數(shù)粒子容易集中于一個(gè)最優(yōu)解附近，出現(xiàn)早熟和局部最優(yōu)。布谷鳥搜索算法中鳥巢采用Lévy 飛行隨機(jī)游走的方式進(jìn)行更新，可以在豐富種群多樣性的同時(shí)讓搜索范圍擴(kuò)大， 該算法中使用的鳥巢淘汰機(jī)制，也可以使算法跳出局部最優(yōu)，進(jìn)而在全局內(nèi)進(jìn)行較好的搜索。 R-CS-PSO 算法針對(duì)兩種算法的不同特點(diǎn)，將兩種算法的優(yōu)點(diǎn)結(jié)合在一起，有效克服其不足，將布谷鳥搜索算法中鳥巢采用Lévy 飛行進(jìn)行變化的機(jī)制引入粒子群優(yōu)化算法， 同時(shí)也將淘汰機(jī)制的理念也引入粒子群優(yōu)化算法， 不僅有助于粒子在局部范圍進(jìn)行精細(xì)搜索，找到更優(yōu)的解；而且增加了粒子的活力，讓粒子跳出局部進(jìn)行更大范圍搜索，進(jìn)而搜索得到全局最優(yōu)解。

在算法改進(jìn)的過程中， 考慮粒子群優(yōu)化算法中是為了平衡全局和局部搜索能力而引入的慣性系數(shù)， 在搜索早期要求有較大速度，也就是較大的，便于在全局內(nèi)進(jìn)行快速搜索；在搜索的后期要求速度減緩，也就是較小的，算法可以快速收斂找到更精確的解； 因此提出一種分段隨機(jī)的調(diào)整策略，使在逐漸縮小的同時(shí)又隨機(jī)變化，進(jìn)一步增加粒子的活力，豐富種群的多樣性。

式中：t 表示當(dāng)前迭代次數(shù)；Ndt為設(shè)置的最大迭代次數(shù)；r0為介于[0，1]之間均勻分布的隨機(jī)數(shù)；wmax為通過經(jīng)驗(yàn)和仿真實(shí)驗(yàn)設(shè)置的最大慣性權(quán)重系數(shù)；wmin為通過經(jīng)驗(yàn)和仿真實(shí)驗(yàn)設(shè)置的最小慣性權(quán)重系數(shù)。

3.2 算法步驟

根據(jù)改進(jìn)思想，設(shè)計(jì)隨機(jī)布谷鳥粒子群（R-CS-PSO）混合算法的基本運(yùn)行步驟如下：

Step1： 程序初始化， 設(shè)置R-CS-PSO 算法的相關(guān)參數(shù)。 主要包括：粒子個(gè)數(shù)M，最大迭代次數(shù)Ndt，學(xué)習(xí)因子c1、c2，慣性權(quán)重wmax和wmin，步長(zhǎng)控制因子α，發(fā)現(xiàn)概率為pα，搜索上界Ub和搜索下界Lb；

Step7：判斷是否滿足終止條件，若不滿足，轉(zhuǎn)Step4；

Step8：輸出粒子最優(yōu)位置和目標(biāo)函數(shù)最優(yōu)解，終止算法。

3.3 算法流程

根據(jù)基本步驟， 繪制流程圖見圖3。

圖3 R-CS-PSO 算法基本流程圖

4 算法性能測(cè)試

4.1 使用典型函數(shù)測(cè)試性能

為了檢驗(yàn)所提出的RCS-PSO 算法的性能，我們使用Python 語言進(jìn)行了編程，使用Sphere 函數(shù)、Step 函數(shù)、Schwefe1_2.22 函 數(shù)、Rosenbrock 函 數(shù)、Griewank 函 數(shù)、Ackley 函 數(shù)、Alpine 函 數(shù) 和Rastrigin 函數(shù)等[8-9]標(biāo)準(zhǔn)的測(cè)試函數(shù)， 將R-CS-PSO 算法與PSO 算法、CS 算法進(jìn)行求解速度、收斂性、魯棒性等算法性能比較，通過比較發(fā)現(xiàn)，改進(jìn)的算法相比于之前的算法搜索范圍廣、收斂速度快、能在較短的時(shí)間內(nèi)取得較好的解。

4.2 使用標(biāo)準(zhǔn)背包測(cè)試性能

為了進(jìn)一步檢驗(yàn)所提出的R-CS-PSO 算法求解背包問題的性能，我們同樣使用Python 語言進(jìn)行編程，將RCS-PSO 算法與PSO 算法、CS 算法通過經(jīng)典背包問題進(jìn)行算法性能測(cè)試對(duì)比。 選擇以下3 個(gè)大、中、小背包[10]，見表1。

表1 2 個(gè)經(jīng)典的測(cè)試背包

為了減少隨機(jī)性對(duì)實(shí)驗(yàn)的影響， 每個(gè)測(cè)試的結(jié)果都是程序獨(dú)立運(yùn)行20 次的平均值，各背包種群規(guī)模等于背包大小，最大迭代次數(shù)為500 次。 我們分別通過最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差、成功率和迭代次數(shù)等指標(biāo)來分析。其中成功率為每種算法尋優(yōu)到理論最優(yōu)值的成功率，迭代次數(shù)為每種算法尋優(yōu)到單次實(shí)驗(yàn)最優(yōu)值的平均迭代次數(shù)。 結(jié)果見表2。

分析表2 可以看出， 對(duì)于KP-1 背包，R-CS-PSO 算法可以很快找到理論最優(yōu)解，CS 算法也可以找到理論最優(yōu)解， 但迭代次數(shù)遠(yuǎn)大于R-CS-PSO 算法的迭代次數(shù)，PSO 算法容易陷入局部最優(yōu)解；對(duì)于KP-2、KP-3，隨著背包的不斷變大，R-CS-PSO 算法可以以一定的成功率找到理論最優(yōu)解，CS 算法和PSO 算法已不能找到理論最優(yōu)解，而且從平均值、標(biāo)準(zhǔn)差、迭代次數(shù)等也可以看出，RCS-PSO 算法較CS 算法和PSO 算法在解決背包問題中的求解精度、速度和穩(wěn)定性都更好。

表2 經(jīng)典測(cè)試背包對(duì)3 中算法性能測(cè)試結(jié)果對(duì)比

5 結(jié)束語

本文在研究粒子群優(yōu)化（PSO）算法和布谷鳥搜索（CS）算法的基礎(chǔ)上，針對(duì)兩種算法的不同特點(diǎn)，改進(jìn)的提出了分階段隨機(jī)布谷鳥粒子群優(yōu)化算法（R-CS-PSO），通過選擇多個(gè)典型函數(shù)測(cè)試該算法具有較快的計(jì)算速度、 較好的收斂性和較強(qiáng)的魯棒性， 通過標(biāo)準(zhǔn)0-1 背包測(cè)試該算法在求解多約束背包問題中具有較好性能， 進(jìn)而在求解民船裝載問題中進(jìn)行推廣應(yīng)用。