錢淑渠，武慧虹

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

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

改進的克隆選擇算法求解高維背包問題*

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

1.南京航空航天大學(xué) 自動化學(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.

高維背包問題；克隆選擇算法（CSA）；受體編輯機制；修補策略

1 引言

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

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

2 背包問題

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

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

3 改進的克隆選擇算法

基本CSA[7]的步驟可簡述為：

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

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

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

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

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

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

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

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

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

3.1 親和力設(shè)計

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

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

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

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

3.2 約束處理機制

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

對抗體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的勢 |I|=u，計算序數(shù)集I中元素對應(yīng)物品的價值密度：

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

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

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

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

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

3.3 受體編輯機制

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

3.3.1 基因庫產(chǎn)生

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

步驟1給定基準基因段長度σ。

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

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

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

3.3.2 受體編輯

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

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

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

RE步驟如下：

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

步驟2隨機選定一個基因庫并在其中隨機產(chǎn)生一個長度為l的基因段y。

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

3.4 改進的算法

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

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

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

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

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

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

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

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

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

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

4 數(shù)值實驗

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

（1）CSA-M：二進制0/1突變的CSA；

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

（3）CSA-MR：采用二進制突變和二次修補策略的CSA；

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

（5）MBPSO：改進的二進制粒子群算法[4]。

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

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

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

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

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

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

圖2和圖3分別為各算法對KP-100獨立執(zhí)行30次所獲的平均目標和群體平均多樣性搜索曲線。由圖2可知，在初始大約100代內(nèi)，MBPSO和BDEPM的搜索速度快于CSA-ER，但隨后CSA-ER的搜索速度超過所有其他算法，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雖然起始收斂速度快，但隨后陷入局部搜索。此也說明了RE機制能提高算法的開采能力，其不足是收斂速度稍慢。由CSA-ER、CSA-MR與CSA-E、CSA-M的比較可知，在最大代數(shù)內(nèi)，CSA-ER、CSA-MR的收斂能力均優(yōu)越于CSA-E、CSA-M，這說明約束處理策略加快了算法的收斂速度。由圖3的比較可知，MBPSO在進化過程中保持較高的種群多樣性，而其他算法均有較明顯的下降，其中BDEPM在進化過程中一直下降，而其他算法初始階段迅速下降，隨后保持一定的水平。這是因為MBPSO中改進的粒子位置更新策略保持了種群的多樣性，而BDEPM中的無參數(shù)變異策略加速種群向最優(yōu)解位置移動，隨算法的收斂，必將降低其種群的多樣性。進一步比較CSA系列算法可知，CSA-ER優(yōu)越于CAS-MR，CSA-E相似于CSAM，這說明RE機制提高了群體的多樣性。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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

[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.

附中文參考文獻：

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

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

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

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

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

[12]武慧虹,錢淑渠,徐志丹.克隆選擇免疫遺傳算法對高維0/1背包問題應(yīng)用[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—），男，安徽樅陽人，2007年于貴州大學(xué)獲得碩士學(xué)位，現(xiàn)為安順學(xué)院副教授，南京航空航天大學(xué)自動化學(xué)院博士研究生，主要研究領(lǐng)域為智能計算，復(fù)雜系統(tǒng)建模與控制等。發(fā)表學(xué)術(shù)論文20余篇，主持國家自然科學(xué)基金1項、貴州省科技計劃基金2項、貴州省教育廳自然科學(xué)基金1項。

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ōu)化，群與圖等。發(fā)表論文10余篇，主持貴州省科技計劃基金1項，省教育廳優(yōu)秀人才創(chuàng)新基金1項。

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(國家自然科學(xué)基金);the Science and Technology Foundation of Guizhou Province under Grant No.20152002(貴州省科技計劃基金);the Science and Technology Reward Program for Excellent Creative Talents of Guizhou Province under Grant No.2014255(貴州省教育廳優(yōu)秀創(chuàng)新人才支持計劃基金).

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

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