改進(jìn)的克隆選擇算法求解高維背包問(wèn)題*

錢淑渠，武慧虹

1.南京航空航天大學(xué) 自動(dòng)化學(xué)院，南京 210016

2.安順學(xué)院 數(shù)理學(xué)院，貴州 安順 561000

改進(jìn)的克隆選擇算法求解高維背包問(wèn)題*

錢淑渠1,2+，武慧虹2

1.南京航空航天大學(xué) 自動(dòng)化學(xué)院，南京 210016

2.安順學(xué)院 數(shù)理學(xué)院，貴州 安順 561000

QIAN Shuqu,WU Huihong.Improved clonal selection algorithm for solving high-dimensional knapsack problem. Journal of Frontiers of Computer Science and Technology,2016,10(12)：1711-1719.

高維背包問(wèn)題；克隆選擇算法（CSA）；受體編輯機(jī)制；修補(bǔ)策略

1 引言

背包問(wèn)題（knapsack problem，KP）屬一類NP難組合優(yōu)化問(wèn)題，具有較高的理論和實(shí)際應(yīng)用價(jià)值[1]，其可描述為許多實(shí)際問(wèn)題，如貨物裝載、投資組合、資源分配等。近來(lái)，基于群智能的算法求解KP受到眾多學(xué)者的關(guān)注[2]，相繼出現(xiàn)了差分算法[3]、粒子群算法[4]、蟻群算法[5]和量子進(jìn)化算法[6]。這些算法在求解KP時(shí)已取得了較好的效果，但多數(shù)使用低維的KP作為測(cè)試實(shí)例，研究求解高維的KP算法更具有實(shí)際價(jià)值[1]。眾所周知，作為一類新興的智能算法，克隆選擇算法（clonal selection algorithm，CSA）已在連續(xù)函數(shù)優(yōu)化領(lǐng)域得到了廣泛的應(yīng)用[7]，其獨(dú)特的抗體學(xué)習(xí)抗原機(jī)制使得該算法能快速尋優(yōu)，并且抗體多樣性功能使得進(jìn)化群能保持較好的解多樣性，但其對(duì)KP的研究成果較少。主要原因是CSA多數(shù)用于求解無(wú)約束連續(xù)函數(shù)問(wèn)題，沒(méi)有特定的約束處理策略，故其直接解決約束問(wèn)題時(shí)僅靠簡(jiǎn)單的親和突變算子開(kāi)采可行域，而且當(dāng)求解高維KP時(shí)，在進(jìn)化過(guò)程中所獲可行抗體的比率非常低（相對(duì)于搜索群），開(kāi)采能力弱，甚至不能獲得可行的抗體，導(dǎo)致算法易于陷入局部搜索。因此，克服CSA易于陷入局部搜索的不足，發(fā)揮其抗體多樣性功能，設(shè)計(jì)適合求解高維KP的改進(jìn)CSA具有一定的研究?jī)r(jià)值。

為此，本文以CSA為基本框架，充分挖掘免疫系統(tǒng)的內(nèi)部機(jī)理，提煉出一種受體編輯機(jī)制（receptor editing，RE），以該機(jī)制代替CSA中的0/1二進(jìn)制變異，并設(shè)計(jì)一種二次修補(bǔ)策略（repair），提出了基于RE和修補(bǔ)的改進(jìn)克隆選擇算法（clonal selection algorithm with receptor editing and repair，CSA-ER）。其中RE機(jī)制增大抗體的突變程度，提高算法的開(kāi)采能力，而修補(bǔ)策略增加種群中抗體的可行比率，加快算法收斂速度。數(shù)值實(shí)驗(yàn)將CSA-ER與CSA的一系列變體（CSA-M，基于0/1二進(jìn)制突變的CSA；CSA-E，CSA中二進(jìn)制突變由本文提出的RE機(jī)制替換后的CSA；CSA-MR，采用二進(jìn)制突變并增加二次修補(bǔ)策略的CSA）應(yīng)用于100和200維KP進(jìn)行了仿真分析，比較了CSA-ER與其他兩類算法的性能。比較結(jié)果充分表明了本文提出的RE機(jī)制和二次修補(bǔ)策略能有效地提高CSA求解高維KP的能力。

2 背包問(wèn)題

背包問(wèn)題（KP）的數(shù)學(xué)模型可描述為：

式中，pi和wi分別表示第i物品的利潤(rùn)和重量；n為物品數(shù)；xi取1表示第i物品被裝入背包，否則表示不被裝入；C稱為背包的最大容量，本文取。求解KP的目標(biāo)是確定最佳組合x(chóng)，使總利潤(rùn) f(x)盡可能的大。

3 改進(jìn)的克隆選擇算法

基本CSA[7]的步驟可簡(jiǎn)述為：

輸入：種群規(guī)模N；最大迭代數(shù)G；免疫選擇率α；突變率pm；募集率μ。

步驟1初始種群：隨機(jī)產(chǎn)生規(guī)模為N的初始種群A。設(shè)置初始代數(shù)t=0。

步驟2停止準(zhǔn)則：判斷t＜G？若是，執(zhí)行步驟3；否則，輸出結(jié)果。

步驟3抗體評(píng)價(jià)：計(jì)算A中各抗體親和力aff(x)，并按親和力由大到小排序。

步驟4免疫克?。哼x取A中親和力較大的┌αN ┐個(gè)抗體構(gòu)成群體B，對(duì)B中的抗體按親和力比例克隆，獲克隆群C。每個(gè)抗體x∈B的克隆數(shù)目為：

克隆群C的規(guī)模為N?！芶ff(B)表示群體B中所有抗體親和力的和。

步驟5親和突變：對(duì)C執(zhí)行親和突變，獲群體D。

步驟6免疫選擇：從D中選擇親和力較大的N個(gè)抗體構(gòu)成群體E。

改進(jìn)的CSA主要圍繞抗體評(píng)價(jià)、約束處理和免疫系統(tǒng)抗體多樣性機(jī)理而相應(yīng)地提出改進(jìn)的親和力設(shè)計(jì)方法、二次修補(bǔ)的約束處理策略和受體編輯機(jī)制。具體設(shè)計(jì)如下。

3.1 親和力設(shè)計(jì)

KP為一類約束優(yōu)化問(wèn)題，常用罰函數(shù)法[8]設(shè)計(jì)抗體的親和力，以降低非可行抗體進(jìn)化機(jī)會(huì)：

這里，κ稱為罰因子，一般需根據(jù)經(jīng)驗(yàn)選擇一個(gè)較為合適的數(shù)值；g(x)為約束。該方法不適合CSA，因?yàn)槿暨x定的κ較大，將會(huì)使得非可行抗體的親和力aff(x)＜0（根據(jù)式（2））。此時(shí)，若當(dāng)前群中非可行抗體又占主導(dǎo)地位，則會(huì)出現(xiàn)∑aff(B)＜0。此情況下，在免疫克隆階段，非可行抗體的克隆比例aff(x)∑aff(B)＞0，而可行抗體的克隆比例卻 aff(x)∑aff(B)＜0（因?yàn)榭尚锌贵w必有aff(x)＞0），這必將誤導(dǎo)算法的搜索行為。

為了克服上述問(wèn)題，本文親和力設(shè)計(jì)為：

此設(shè)計(jì)足以保證非可行抗體的親和力aff(x)∈(0,1)，并且違背度越大，其親和力aff(x)越小。

3.2 約束處理機(jī)制

在優(yōu)化領(lǐng)域，約束的處理策略主要是罰函數(shù)法。對(duì)于KP模型，直接使用罰函數(shù)法很難獲得高質(zhì)量的解。為此，學(xué)者們提出了很多價(jià)值密度修補(bǔ)策略[9-12]。本文在這些策略的基礎(chǔ)上，提出一種二次修補(bǔ)策略，對(duì)克隆突變的抗體進(jìn)行修復(fù)，具體過(guò)程如下：

對(duì)抗體x=(x1,x2,…,xn)∈{0,1}n。若x為非可行抗體，執(zhí)行步驟1～步驟7；否則，執(zhí)行步驟4～步驟7。

步驟1確定抗體x中編碼為1的序數(shù)集Ι={i|xi= 1,i=1,2,…,n}。假設(shè)集合I的勢(shì) |I|=u，計(jì)算序數(shù)集I中元素對(duì)應(yīng)物品的價(jià)值密度：

步驟2序數(shù)集I中的元素按價(jià)值密度ρi由小到大排列，獲得新的序數(shù)集，其中 ρi≤ρijk(1≤j＜k≤u)。

步驟4計(jì)算背包的剩余容量ΔW=g(x)。

步驟5確定經(jīng)修復(fù)的抗體x中編碼為0的序數(shù)集O={i|xi=0,i=1,2,…,n}，假定所獲O的勢(shì)|O|=η，計(jì)算序數(shù)集O中元素對(duì)應(yīng)物品的價(jià)值密度：

步驟6對(duì)序數(shù)集O中的元素按價(jià)值密度σi由大到小排列，得到新的序數(shù)集。

評(píng)注 步驟1～步驟3是對(duì)非可行抗體進(jìn)行修補(bǔ)，使其為可行抗體；步驟4～步驟7對(duì)可行抗體或修復(fù)后的抗體采用二次再裝策略，使背包盡可能最大限度地載滿，以加速算法的收斂速度。

3.3 受體編輯機(jī)制

研究表明免疫系統(tǒng)的B細(xì)胞成熟過(guò)程不僅經(jīng)歷克隆選擇和親和突變過(guò)程，而且B細(xì)胞偶爾會(huì)發(fā)生RE過(guò)程[13-15]。RE過(guò)程即通過(guò)V(D)J區(qū)基因段重組[16]刪去親和力較低的受體基因段，并從基因庫(kù)中產(chǎn)生新的抗體受體。RE機(jī)制能極大地提高算法的全局搜索能力[17]。受該機(jī)制啟發(fā)，本文提出受體編輯操作，主要包括基因庫(kù)產(chǎn)生和編輯過(guò)程。

3.3.1 基因庫(kù)產(chǎn)生

基因庫(kù)即是由若干個(gè)基因片段組成的基因段池，每個(gè)基因段具有一定的長(zhǎng)度。對(duì)于免疫系統(tǒng)，其基因庫(kù)數(shù)量和庫(kù)內(nèi)基因段的長(zhǎng)度一般為固定值，而且這些基因段是由染色體分解而成。本文為了提高算法適應(yīng)不同維問(wèn)題，基因庫(kù)的數(shù)量和基因段的長(zhǎng)度根據(jù)被優(yōu)化問(wèn)題的維數(shù)n確定，具體為：

步驟1給定基準(zhǔn)基因段長(zhǎng)度σ。

步驟2確定基因庫(kù)數(shù)量m和各庫(kù)的基因段長(zhǎng)度l。如果mod(n,σ)=0，則m=n σ，此時(shí)每個(gè)庫(kù)內(nèi)的基因段長(zhǎng)度l=σ；若mod(n,σ)≠0，則，此時(shí)前面m-1個(gè)基因庫(kù)內(nèi)的基因段長(zhǎng)度l=σ，而最后基因庫(kù)內(nèi)的基因段長(zhǎng)度l=n-(m-1)σ。其中mod(n,σ)表示σ除n的余數(shù)。

步驟3根據(jù)獲得的l隨機(jī)產(chǎn)生各基因庫(kù)的基因段。

評(píng)注 該設(shè)計(jì)確保不同基因庫(kù)內(nèi)的基因段長(zhǎng)度之和恰為染色體的長(zhǎng)度，體現(xiàn)基因段來(lái)自染色體自身的生物機(jī)理；另外，在基準(zhǔn)基因段長(zhǎng)度給定下，不同維問(wèn)題基因庫(kù)的數(shù)目不同，維數(shù)越高其基因庫(kù)數(shù)目相對(duì)多，基因段的多樣性高，以提高算法適應(yīng)問(wèn)題的能力。

3.3.2 受體編輯

受體編輯（RE）即從基因庫(kù)中選定一個(gè)基因段替換被編輯的抗體相應(yīng)長(zhǎng)度的基因段而獲得新的抗體[7,17]。如圖1所示。

需要說(shuō)明的是在算法實(shí)現(xiàn)中不分基因庫(kù)的類別，而且基因庫(kù)的類型不只是圖1中的3種類型，而是假設(shè)有多個(gè)基因庫(kù)（參見(jiàn)基因庫(kù)產(chǎn)生部分）。

Fig.1 Receptor editing process in immune system圖1 免疫系統(tǒng)中受體編輯過(guò)程

RE步驟如下：

步驟1對(duì)于待編輯的抗體x，若rand≤Tr，則隨機(jī)產(chǎn)生一個(gè)編輯起始點(diǎn)q，執(zhí)行步驟2；否則，返回步驟1，對(duì)下一個(gè)抗體執(zhí)行編輯操作。其中Tr稱為編輯率，rand為[0,1]的隨機(jī)數(shù)。

步驟2隨機(jī)選定一個(gè)基因庫(kù)并在其中隨機(jī)產(chǎn)生一個(gè)長(zhǎng)度為l的基因段y。

步驟3若q+l≤n，則y按圖1方式替換；若q+l＞n，此時(shí)替換完q點(diǎn)之后的所有基因，y仍有剩余，則y的剩余部分將依次替換x的起始位基因。此方法以保證被編輯后的抗體基因長(zhǎng)度保持為n。

3.4 改進(jìn)的算法

根據(jù)CSA基本框架，結(jié)合上述RE和修補(bǔ)機(jī)制，改進(jìn)的CSA步驟描述如下。

輸入：種群規(guī)模N；最大迭代數(shù)G；基準(zhǔn)基因段長(zhǎng)度σ；克隆選擇率α；編輯率Tr。

步驟1初始種群：隨機(jī)產(chǎn)生規(guī)模為N的初始種群A；根據(jù)變量維數(shù)n，按基因庫(kù)產(chǎn)生方式確定基因庫(kù)數(shù)量并產(chǎn)生各庫(kù)的基因段。設(shè)置初始代數(shù)t=0。

步驟2停止準(zhǔn)則：判斷t＜G？若是，執(zhí)行步驟3；否則，輸出結(jié)果。

步驟3抗體評(píng)價(jià)：依式（3）計(jì)算A中各抗體親和力aff(x)，并按親和力由大到小排列各抗體。

步驟5受體編輯：對(duì)群C中每個(gè)抗體，執(zhí)行RE操作，獲群體D。

步驟6約束處理：群體D經(jīng)由約束處理機(jī)制，獲群體E。

步驟7免疫選擇：群體E按親和力由大到小排序，并選取親和力較大的N個(gè)抗體構(gòu)成群體P。置t←t+1，A←P，轉(zhuǎn)入步驟2。

3.5 復(fù)雜度對(duì)比分析

對(duì)比CSA-ER與CSA-M可知，CSA-ER中RE代替了CSA-M的親和突變，增加了約束處理策略，但減少了募集新成員算子。兩算法不同部分的復(fù)雜度量化比較如下：對(duì)于CSA-ER，RE最壞時(shí)間復(fù)雜度為O(N)；約束處理策略模塊復(fù)雜度主要由步驟2和步驟6決定，其最壞時(shí)間復(fù)雜度均為O(Nnlgn)。故兩模塊最壞時(shí)間復(fù)雜度為O(N)+O(Nnlgn)=O(Nnlgn)。對(duì)于CSA-M，親和突變的最壞時(shí)間復(fù)雜度為O(Nn)。因?yàn)镺(Nnlgn)＞O(Nn)，所以CSA-ER的時(shí)間復(fù)雜度大于CSA-M。這里的N為免疫選擇后的種群規(guī)模，n為抗體編碼長(zhǎng)度。

4 數(shù)值實(shí)驗(yàn)

為了分析CSA-ER的優(yōu)化能力，采用CSA-ER求解兩類高維KP（100維[9]和200維[12]，為方便表述分別記為KP-100和KP-200），并將其與CSA的一系列變體以及兩種其他類群智能算法（BDEPM[3]、MBPSO[4]進(jìn)行比較，各算法的親和力函數(shù)均采用本文設(shè)計(jì)的式（3）：

（1）CSA-M：二進(jìn)制0/1突變的CSA；

（2）CSA-E：RE策略替換CSA中的二進(jìn)制突變；

（3）CSA-MR：采用二進(jìn)制突變和二次修補(bǔ)策略的CSA；

（4）BDEPM：改進(jìn)的無(wú)參數(shù)變異二進(jìn)制差分進(jìn)化算法[3]；

（5）MBPSO：改進(jìn)的二進(jìn)制粒子群算法[4]。

各算法參數(shù)設(shè)置為：群體規(guī)模N=100，最大迭代數(shù)G=1 000；克隆選擇率α=0.4；CSA中的突變率pm=1 n，募集率μ=0.1；CSA-ER的編輯率Tr=0.9，基因段基準(zhǔn)長(zhǎng)度σ=4；BDEPM中CR=0.9；MBPSO中c1=c2=2，r1、r2在[0,1]間均勻地隨機(jī)產(chǎn)生。

評(píng)價(jià)準(zhǔn)則為各算法對(duì)每測(cè)試問(wèn)題獨(dú)立執(zhí)行30次，統(tǒng)計(jì)30次中各算法所獲的最好值（最大目標(biāo)值）、最差值（最小目標(biāo)值）和平均值（30次所獲最好目標(biāo)值和的平均值），以及平均目標(biāo)值搜索曲線和群體平均多樣性搜索曲線。群體的多樣性計(jì)算公式[18]為：

式中，HD(?,?)為兩抗體間的海明距離；n為染色體長(zhǎng)度；N為抗體數(shù)。群體平均多樣性是30次執(zhí)行所獲的D(P)的平均值。

表1和表2分別為各算法對(duì)KP-100和KP-200在30次執(zhí)行中所獲的最好值、最差值、平均值及方差（粗體為6個(gè)算法中最好的）。由表1可知，CSA-ER所得各項(xiàng)統(tǒng)計(jì)值均比其他算法相應(yīng)的統(tǒng)計(jì)值優(yōu)越，其次為BDEPM，例如CSA-ER的平均目標(biāo)值為5 341.167，BDEPM為5 335.833。比較CSA-M和CSA-E可知，除方差外，CSA-E所獲統(tǒng)計(jì)值均優(yōu)于CSA-M，這表明基于RE機(jī)制的CSA強(qiáng)于基于0/1二進(jìn)制突變策略的CSA，其原因是RE機(jī)制增強(qiáng)了算法的開(kāi)采和探索能力。比較CSA-MR和CSA-M，CSA-ER和CSA-E可知，CSA-MR優(yōu)于CSA-M，CSA-ER優(yōu)于CSA-E，這表明本文提出的約束處理策略能提高算法對(duì)KP的優(yōu)化性能，原因是修補(bǔ)策略增強(qiáng)了可行抗體的數(shù)目，加快了算法的收斂性。對(duì)于KP-200（表2）同樣有CSAER所獲的各項(xiàng)統(tǒng)計(jì)值優(yōu)于其他算法。對(duì)于被比較的其他類群智能算法BDEPM和MBPSO，由表1和表2可知，BDEPM求解KP的能力強(qiáng)于MBPSO，但均差于CSA-ER。特別對(duì)于KP-200，BDEPM和MBPSO甚至差于CSA-E和CSA-MR（觀察表2可知）。由各表的方差統(tǒng)計(jì)值比較可知，CSA-ER所獲的方差均小于其他算法所獲的方差，這表明CSA-ER多次獨(dú)立執(zhí)行得到的結(jié)果穩(wěn)定性較其他算法好。

Table 1 Comparison of statistical values of each algorithm on KP-100表1 KP-100各算法統(tǒng)計(jì)值比較

Table 2 Comparison of statistical values of each algorithm on KP-200表2 KP-200各算法統(tǒng)計(jì)值比較

圖2和圖3分別為各算法對(duì)KP-100獨(dú)立執(zhí)行30次所獲的平均目標(biāo)和群體平均多樣性搜索曲線。由圖2可知，在初始大約100代內(nèi)，MBPSO和BDEPM的搜索速度快于CSA-ER，但隨后CSA-ER的搜索速度超過(guò)所有其他算法，MBPSO陷入局部搜索，BDEPM一直向最優(yōu)解搜索，并逐漸靠近CSA-ER。這表明BDEPM具有一定的發(fā)展?jié)摿?，但其收斂速度比較慢。比較CSA-E與CSA-M和CSA-MR可知，CSA-E起始收斂速度差于CSA-M和CSA-MR，但其一直向最優(yōu)解搜索，而CSA-M和CSA-MR雖然起始收斂速度快，但隨后陷入局部搜索。此也說(shuō)明了RE機(jī)制能提高算法的開(kāi)采能力，其不足是收斂速度稍慢。由CSA-ER、CSA-MR與CSA-E、CSA-M的比較可知，在最大代數(shù)內(nèi)，CSA-ER、CSA-MR的收斂能力均優(yōu)越于CSA-E、CSA-M，這說(shuō)明約束處理策略加快了算法的收斂速度。由圖3的比較可知，MBPSO在進(jìn)化過(guò)程中保持較高的種群多樣性，而其他算法均有較明顯的下降，其中BDEPM在進(jìn)化過(guò)程中一直下降，而其他算法初始階段迅速下降，隨后保持一定的水平。這是因?yàn)镸BPSO中改進(jìn)的粒子位置更新策略保持了種群的多樣性，而B(niǎo)DEPM中的無(wú)參數(shù)變異策略加速種群向最優(yōu)解位置移動(dòng)，隨算法的收斂，必將降低其種群的多樣性。進(jìn)一步比較CSA系列算法可知，CSA-ER優(yōu)越于CAS-MR，CSA-E相似于CSAM，這說(shuō)明RE機(jī)制提高了群體的多樣性。

Fig.2 Comparison of average objective values with generations of each algorithm on KP-100圖2 針對(duì)KP-100各算法的平均目標(biāo)搜索曲線

Fig.3 Comparison of average diversity with generations of each algorithm on KP-100圖3 針對(duì)KP-100各算法的平均多樣性搜索曲線

圖4和圖5分別為各算法對(duì)KP-200獨(dú)立執(zhí)行30次所獲的平均目標(biāo)和群體平均多樣性搜索曲線。觀察圖4可知，CSA-ER與CSA-MR的初始階段具有相當(dāng)?shù)氖諗克俣?，但最終CSA-ER獲得更好的收斂效果，而MBPSO相對(duì)于其他算法有較差的收斂能力，BDEPM收斂能力與KP-100相似，一直向最優(yōu)解搜索。對(duì)于多樣性（圖5）的比較可知，同圖3類似，MBPSO和BDEPM保持較好的多樣性（但BDEPM一直下降），CSA-ER僅優(yōu)于CSA-MR，而劣于其他算法。這是因?yàn)镃SA-ER保持較好的收斂能力，必以降低種群多樣性為代價(jià)。

Fig.4 Comparison of average objective values with generations of each algorithm on KP-200圖4 針對(duì)KP-200各算法的平均目標(biāo)搜索曲線

Fig.5 Comparison of average diversity with generations of each algorithm on KP-200圖5 針對(duì)KP-200各算法的平均多樣性搜索曲線

表3給出了各算法對(duì)每個(gè)問(wèn)題執(zhí)行30次所獲的每代所需的平均時(shí)間。由表3可知，CSA-E算法所需的時(shí)間最短，也即基于RE機(jī)制的算法執(zhí)行時(shí)間低于基于0/1二進(jìn)制突變策略的算法。這是因?yàn)?/1二進(jìn)制突變策略對(duì)被突變抗體的每個(gè)基因均按一定的概率進(jìn)行突變操作，最壞情況下每個(gè)抗體要進(jìn)行n次突變操作，而RE機(jī)制僅對(duì)被編輯抗體執(zhí)行一次基因段替換，最壞情況下每個(gè)抗體最多執(zhí)行一次編輯操作。

Table 3 Comparison of average running time表3 平均執(zhí)行時(shí)間統(tǒng)計(jì)值 s

5 參數(shù)敏感性分析

CSA-ER涉及到的參數(shù)主要有克隆選擇率α、基因段基準(zhǔn)長(zhǎng)度σ和受體編輯率Tr，分別對(duì)這3個(gè)參數(shù)進(jìn)行敏感性分析。對(duì)KP-100和KP-200在不同的參數(shù)設(shè)置下各算法獨(dú)立執(zhí)行30次，圖6～圖8為KP-100在不同參數(shù)下所獲的平均目標(biāo)搜索曲線。

圖6為克隆選擇率α由0.1變化到1.0的平均目標(biāo)值變化曲線。由圖可知，選擇率α較小或較大時(shí)均降低算法的搜索能力，如α為0.1，0.2，0.7，0.8，0.9，1.0，特別是α為0.7～1.0區(qū)間時(shí)算法陷入局部搜索，完全失去開(kāi)采能力。當(dāng)α為0.3，0.4，0.5，0.6時(shí)獲得較好的搜索性能，其中α為0.5時(shí)達(dá)到最好。

Fig.6 Curves of average objective values with clonal selection rate α from 0.1 to 1.0圖6 克隆選擇率α由0.1變化到1.0平均目標(biāo)搜索曲線

圖7描繪了基因段基準(zhǔn)長(zhǎng)度σ在1到10之間的平均目標(biāo)搜索曲線。觀察圖7易知，σ為1時(shí)算法搜索能力最差，起始代就陷入局部搜索。σ由2到4算法的搜索能力逐漸提高，在σ為4時(shí)達(dá)到最佳性能。σ為8和9時(shí)起始搜索速度慢，在較大代（如1 000代）時(shí)達(dá)到比較好的性能。其他情況優(yōu)化能力較弱。總體比較σ為4時(shí)搜索速度較快。

圖8給出了受體編輯率Tr取不同值時(shí)所獲的平均目標(biāo)搜索曲線。由圖8可知，Tr為0.9時(shí)表現(xiàn)最佳的搜索行為，Tr在0.7～0.8時(shí)也表現(xiàn)較好的搜索能力，但其他值稍差，由此可知編輯率Tr不宜過(guò)小。

Fig.7 Curves of average objective values with gene segment length σ from 1 to 10圖7 基因段長(zhǎng)度σ由1變化到10平均目標(biāo)搜索曲線

Fig.8 Curves of average objective values with receptor editing rate Tr from 0.1 to 1.0圖8 受體編輯率Tr由0.1變化到1.0平均目標(biāo)搜索曲線

對(duì)于KP-200，克隆選擇率α和受體編輯率Tr對(duì)目標(biāo)值的敏感性與KP-100所獲結(jié)果非常類似，而基因段基準(zhǔn)長(zhǎng)度σ對(duì)目標(biāo)值的敏感性有所不同，在σ= 6時(shí)達(dá)到最好的收斂效果（對(duì)于KP-100，在σ=4時(shí)達(dá)到最好收斂效果）。其原因是由于KP-200與KP-100的主要不同是個(gè)體編碼長(zhǎng)度，KP-200編碼長(zhǎng)度增長(zhǎng)了，而在相同的受體編輯率下，要想達(dá)到種群的最佳收斂效果，必將要求個(gè)體突變程度增強(qiáng)，故σ的最適合值增大。

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

本文基于免疫系統(tǒng)的受體編輯機(jī)制及二次修補(bǔ)策略提出了改進(jìn)的CSA處理高維KP。設(shè)計(jì)二次修補(bǔ)策略能提高算法的約束處理能力，提出受體編輯算子提高抗體的多樣性。數(shù)值實(shí)驗(yàn)將被提出的算法用于兩種高維的KP，并與CSA的一系列變體進(jìn)行了仿真比較，結(jié)果表明了被提出的算法解決高維KP的優(yōu)越性，收斂速度比其他算法快。最后對(duì)被提出算法的3個(gè)重要參數(shù)進(jìn)行了敏感性分析。

需要指出的是本文重點(diǎn)分析受體編輯機(jī)制和二次修補(bǔ)策略對(duì)CSA性能的影響。因此，未研究其與更多其他類算法的比較，該內(nèi)容將是后續(xù)工作。另外，本文提出的受體編輯及修補(bǔ)策略也可結(jié)合其他類算法，以及用于其他類組合問(wèn)題的求解，如TSP、投資組合等，這也將是后期的研究工作。經(jīng)數(shù)值實(shí)驗(yàn)可知，所提出的相關(guān)機(jī)制能提高算法的優(yōu)化性能，但算法時(shí)間開(kāi)銷有所增大，這在實(shí)驗(yàn)比較部分均有分析，如何克服這些缺點(diǎn)有待進(jìn)一步討論。

[1]Wu Congcong,He Yichao,Chen Yiying,et al.Binary bat algorithm for solving 0-1 knapsack problem[J].Computer Engineering andApplications,2015,51(19):71-74.

[2]Changdar C,Mahapatra G S,Pal R K.An ant colony optimization approach for binary knapsack problem under fuzziness[J].Applied Mathematics and Computation,2013,223 (9):243-253.

[3]Kong Xiangyong,Gao Liqun,Ouyang Haibin,et al.Binary differential evolution algorithm based on parameterless mutation strategy[J].Journal of Northeastern University,2014, 35(4):484-488.

[4]Bansal J C,Deep K.A modified binary particle swarm optimization for knapsack problems[J].Applied Mathematics &Computation,2012,218(22):11042-11061.

[5]Kong Min,Tian Peng,Kao Yucheng.A new ant colony optimization algorithm for the multidimensional knapsack problem[J].Computers&Operations Research,2008,35(8): 2672-2683.

[6]Chang Xingong,Liu Wenjuan.Self-adaptive quantum-inspired evolutionary algorithm combining the strategy of keeping away from the worst[J].Journal of Frontiers of Computer Science and Technology,2014,8(11):1373-1380.

[7]Castro L N D,Zuben F J V.Learning and optimization using the clonal selection principle[J].IEEE Transactions on Evolutionary Computation,2002,6(3):239-251.

[8]Basu S K,Bhatia A K.A naive genetic approach for nonstationary constrained problems[J].Soft Computing,2006, 10(2):152-162.

[9]He Yichao,Wang Xizhao,Kou Yingzhan.A binary differential evolution algorithm with hybrid encoding[J].Journal of Computer Research and Development,2007,44(9):1476-1484.

[10]Zeng Zhi,Yang Xiaofan,Chen Jing,et al.An improved genetic algorithm for the multidimensional 0-1 knapsack problem[J].Journal of Computer Sciences,2006,7(7):220-223. [11]Tuo Shouheng,Yong Longquan,Deng Fang'an.A novel harmony search algorithm based on teaching-learning strategies for 0-1 knapsack problems[J].The Scientific World Journal,2014.doi:10.1155/2014/637412.

[12]Wu Huihong,Qian Shuqu,Xu Zhidan.Immune genetic algorithm based on clonal selection and its application to 0/1 knapsack problem[J].Journal of Computer Application, 2013,33(3):845-848.

[13]Berek C,Ziegner M.The maturation of the immune response[J].Immunology Today,1993,14(8):400-404.

[14]Nussenzweig M C.Immune receptor editing:revise and select[J].Cell,1998,95(7):875-878.

[15]George A J,Gray D.Receptor editing during affinity maturation[J].Immunology Today,1999,20(4):196.

[16]Matthyssens G,Hozumi N,Tonegawa S.Somatic generation of antibody diversity[J].Nature,1983,302(5909):575-581.

[17]Castro L,Zuben F.Artificial immune system,Part 1 basic theory and applications[J].International Journal of Electrical Power&Energy Systems,1999,33(1):131-136.

[18]Sim?es A,Costa E.Improving the genetic algorithm's performance when using transformation[J].Artificial Neural Nets&GeneticAlgorithms,2003,20(2):175-181.

附中文參考文獻(xiàn)：

[1]吳聰聰,賀毅朝,陳嶷瑛,等.求解0-1背包問(wèn)題的二進(jìn)制蝙蝠算法[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(19):71-74.

[3]孔祥勇,高立群,歐陽(yáng)海濱,等.無(wú)參數(shù)變異的二進(jìn)制差分進(jìn)化算法[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,2014,35(4):484-488.

[6]常新功,劉文娟.結(jié)合遠(yuǎn)離最差策略的自適應(yīng)量子進(jìn)化算法[J].計(jì)算機(jī)科學(xué)與探索,2014,8(11):1373-1380.

[9]賀毅朝,王熙照,寇應(yīng)展.一種具有混合編碼的二進(jìn)制差分演化算法[J].計(jì)算機(jī)研究與發(fā)展,2007,44(9):1476-1484.

[10]曾智,楊小帆,陳靜,等.求解多維0-1背包問(wèn)題的一種改進(jìn)的遺傳算法[J].計(jì)算機(jī)科學(xué),2006,7(7):220-223.

[12]武慧虹,錢淑渠,徐志丹.克隆選擇免疫遺傳算法對(duì)高維0/1背包問(wèn)題應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2013,33(3):845-848.

QIAN Shuqu was born in 1978.He received the M.S.degree in operations research and control theory from Guizhou University in 2007.Now he is an associate professor at Anshun University and is pursuing the Ph.D.degree at College of Automatic Engineering,Nanjing University of Aeronautics and Astronautics.His research interests include computer intelligence,complex system modeling and control,etc.He has published more than 20 papers, presided 4 scientific research projects,including the National Natural Science Foundation and the Science and Technology Foundation of Guizhou Province.

錢淑渠（1978—），男，安徽樅陽(yáng)人，2007年于貴州大學(xué)獲得碩士學(xué)位，現(xiàn)為安順學(xué)院副教授，南京航空航天大學(xué)自動(dòng)化學(xué)院博士研究生，主要研究領(lǐng)域?yàn)橹悄苡?jì)算，復(fù)雜系統(tǒng)建模與控制等。發(fā)表學(xué)術(shù)論文20余篇，主持國(guó)家自然科學(xué)基金1項(xiàng)、貴州省科技計(jì)劃基金2項(xiàng)、貴州省教育廳自然科學(xué)基金1項(xiàng)。

WU Huihong was born in 1980.She received the M.S.degree in application mathematics from Yunnan University in 2009.Now she is an associate professor at Anshun University.Her research interests include intelligence optimization,group and graph,etc.She has published more than 10 papers,presided 2 scientific research projects,including the Science and Technology Foundation of Guizhou Province.

武慧虹（1980—），女，山西太原人，2009年于云南大學(xué)獲得碩士學(xué)位，現(xiàn)為安順學(xué)院副教授，主要研究領(lǐng)域?yàn)橹悄軆?yōu)化，群與圖等。發(fā)表論文10余篇，主持貴州省科技計(jì)劃基金1項(xiàng)，省教育廳優(yōu)秀人才創(chuàng)新基金1項(xiàng)。

Improved Clonal Selection Algorithm for Solving High-Dimensional Knapsack Problem*

QIAN Shuqu1,2+,WU Huihong2
1.College ofAutomation Engineering,Nanjing University ofAeronautics andAstronautics,Nanjing 210016,China
2.School of Sciences,Anshun University,Anshun,Guizhou 561000,China
+Corresponding author:E-mail:shuquqian@163.com

Since clonal selection algorithm(CSA)on high-dimensional knapsack problems(KPs)can only obtain a low feasible rate,and falls easily into local search,this paper proposes an improved clonal selection algorithm(CSAER)to solve high-dimensional KPs.In CSA-ER,a receptor editing mechanism is developed based on antibodies diversity function in immune system.Also,a repeat repair strategy is introduced to enhance the ability of handling constraints.CSA-ER is compared with several variants of CSA(CSA-M,CSA-E,CSA-MR)and two other intelligent algorithms on KPs in simulation experiments.The results show that CSA-ER has strong exploitation and convergence capability.Meanwhile,the sensitivities of three parameters(selection rate α,editing rate Tr,and basic gene segment length σ)in CSA-ER are also analyzed,and the appropriate parameter settings are obtained in the last.

high-dimensional knapsack problem;clonal selection algorithm(CSA);receptor editing mechanism;repair strategy

10.3778/j.issn.1673-9418.1511066

A

TP306.03

*The National Natural Science Foundation of China under Grant No.61304146(國(guó)家自然科學(xué)基金);the Science and Technology Foundation of Guizhou Province under Grant No.20152002(貴州省科技計(jì)劃基金);the Science and Technology Reward Program for Excellent Creative Talents of Guizhou Province under Grant No.2014255(貴州省教育廳優(yōu)秀創(chuàng)新人才支持計(jì)劃基金).

Received 2015-11,Accepted 2016-03.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-03-07,http://www.cnki.net/kcms/detail/11.5602.TP.20160307.1710.006.html

摘 要：針對(duì)克隆選擇算法（clonal selection algorithm，CSA）求解高維背包問(wèn)題（knapsack problem，KP）時(shí)可行抗體比率低且易于陷入局部搜索的問(wèn)題，充分挖掘免疫系統(tǒng)的抗體多樣性機(jī)理，提出了受體編輯機(jī)制，并設(shè)計(jì)了二次修補(bǔ)策略增強(qiáng)約束處理能力，獲得了改進(jìn)的克隆選擇算法CSA-ER（clonal selection algorithm with receptor editing and repair）。數(shù)值實(shí)驗(yàn)將CSA-ER與CSA的一系列變體（CSA-M、CSA-E、CSA-MR）及兩類其他群智能算法應(yīng)用于兩類KP進(jìn)行了仿真比較，結(jié)果表明CSA-ER具有較強(qiáng)的開(kāi)采和收斂能力。同時(shí)對(duì)CSA-ER的3個(gè)參數(shù)（克隆選擇率α、編輯率Tr及基因段基準(zhǔn)長(zhǎng)度σ）進(jìn)行了敏感性分析，獲得了合適的參數(shù)選擇策略。