呂學(xué)勤，陳樹果，林 靜

(1.上海電力學(xué)院電力與自動化工程學(xué)院，上海 200090;2.信陽市供電局財務(wù)資產(chǎn)部，河南 信陽 464000)

0 引言

0/1背包問題(zero-one knapsack problem，ZKP)是運籌學(xué)中一個典型的NP(non-deterministic polynomia)完全問題［1-2］。背包問題在20世紀(jì)50年代末期由Dntzig提出之后，經(jīng)歷幾十年的發(fā)展，已成功應(yīng)用于管理科學(xué)、計算機科學(xué)、分子物理學(xué)以及超大規(guī)模集成電路設(shè)計、代碼設(shè)計、圖像處理、電子工程等領(lǐng)域。目前，解決0/1背包的常規(guī)方法包括窮舉法、動態(tài)規(guī)劃法和遞歸回溯法等［3］，但只能處理小規(guī)模背包問題。啟發(fā)式算法是模擬自然界和生物行為的新型算法，具有模型靈活，求解速度快、解的質(zhì)量高等一系列優(yōu)點，因而被獲得廣泛應(yīng)用。但遺傳算法、蟻群算法、差分進化算法等優(yōu)化算法收斂速度慢、全局收斂性差，而模擬退火算法(simulated annealing algorithm，SA)能改善陷入局部最優(yōu)解的缺陷，使得算法快速地收斂于全局最優(yōu)解［4-5］。因此，本文提出了自適應(yīng)遺傳退火算法(adaptive genetic annealing algorithm，AGAA)求解大規(guī)模背包問題，通過4個背包問題對算法進行性能對比，結(jié)果表明本文提出的算法具有較快的搜索性能和較強的實用價值。

1 背包問題

給定一個可裝重量為M的背包及n件物品，物品i的重量和價值分別為wi和ci，i=1，…，n。要選若干件物品裝入背包，使其價值之和最大，背包問題的目標(biāo)函數(shù)為

2 遺傳算法及其改進

2.1 遺傳算法

遺傳算法(genetic algorithm，GA)抽象于生物體的進化過程，是一種基于自然選擇和群體遺傳機理的搜索算法，其本質(zhì)是一種高效、并行、全局搜索的優(yōu)化方法。

2.2 遺傳算法的改進

GA的改進方案大致有2種:一種是算法本身的編碼方式、遺傳操作的改進，另一種是GA與其他優(yōu)化算法構(gòu)成混合算法。為此，本文把GA與SA相結(jié)合構(gòu)成混合算法，并改進GA交叉、變異方式，使得改進后的算法既保持了GA的高速并行性，又保持了SA跳出局部最優(yōu)值的能力。

1)編碼策略。

針對0/1背包問題，采用二進制編碼方案，問題的解可以表示為

(3)式中:fi表示在某一次迭代解空間里的某一個染色體串經(jīng)適應(yīng)度評價得到的解;P是由解空間里n個染色體串所得到的解的集合，比如:染色體1為(0，0，1，…，1)，f1=C1× 0+ … +Cn× 1 。

2)選擇策略。

為了避免由交叉、變異操作導(dǎo)致破壞最優(yōu)解或近似最優(yōu)解的情況，采用輪盤賭和最優(yōu)保存策略相結(jié)合的選擇機制，以保留當(dāng)前最優(yōu)染色體，即從當(dāng)前種群中保留2個最佳染色體直接復(fù)制到下一代種群中，余下的種群通過輪盤賭方法選擇進入下一代種群中，以提高算法的收斂性。

3)交叉、變異策略。

整個遺傳進程中，影響遺傳算法性能的主要指標(biāo)為交叉、變異概率，為了維持種群的多樣性，交叉概率Pc越大，產(chǎn)生新個體越多，但種群中好的模式被破壞的可能性就越大，即適應(yīng)度高的個體所占的比重就越少;交叉概率過小時，好的模式保留的可能性越大，種群的多樣性難以保證;若變異概率Pm越小，種群中就不易產(chǎn)生新的模式，Pm越大，遺傳算法就不滿足定向搜索算法的原則，因此，對于實際問題，需多次實驗確定交叉、變異概率的取值，而且很難找到適應(yīng)每個問題的最優(yōu)解。在自適應(yīng)遺傳算法(a daptive genetic algorithm，AGA)中，Pc和 Pm按(4)式和(5)式進行自適應(yīng)調(diào)整。

(4)—(5)式中:f為當(dāng)前個體的適應(yīng)度;f1為當(dāng)代種群兩個個體的較大適應(yīng)度;favg為當(dāng)代各個體的平均適應(yīng)度;fmax為各個體的最大適應(yīng)度。根據(jù)前人經(jīng)驗，(4)—(5)式中 Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.001。

從(4)—(5)式看出，種群中各個體的適應(yīng)度值接近于局部最優(yōu)時，Pc，Pm相應(yīng)增加;種群中各個體的適應(yīng)度值趨于分散時，Pc，Pm相應(yīng)地減少。同時，當(dāng)適應(yīng)度值高于種群的平均適應(yīng)度值的個體，對應(yīng)較低的Pc，Pm，使得適應(yīng)度高的個體進入下一代種群中;而適應(yīng)度值低的個體，Pc，Pm會相應(yīng)地增加，致使該個體被破壞。因此，Pc，Pm的自適應(yīng)調(diào)整能提供個體最適合的Pc，Pm。

4)退火策略。

對于本文算法而言，以遺傳算法為主，用模擬退火算法來改進遺傳算法的局部搜索能力，使得待求問題能快速搜索到最優(yōu)解。遺傳算法執(zhí)行完遺傳操作后，得到子代種群，而子代種群由于退火策略的引入不能以全概率進入新一代的種群中，為此，以狀態(tài)i和新狀態(tài)j為連續(xù)的兩種狀態(tài)為例說明，當(dāng)新狀態(tài)j的適應(yīng)度值f(j)小于或等于f(i)時，則直接進入新種群中;當(dāng)f(j)大于f(i)時，需按照Metropolis準(zhǔn)則來確定是否進入新種群中，(6)式給出了新狀態(tài)j的接受概率

(6)式中:a為退溫系數(shù);tk為退火溫度。

2.3 算法效率定性分析

雖然理論上SA算法和帶最優(yōu)保存策略的AGA算法能以1的概率搜索到全局最優(yōu)值，但實際上兩者難以實現(xiàn)理論的收斂條件，因此，2種算法的效率和優(yōu)化性能均不太理想，也導(dǎo)致算法的參數(shù)選取困難。綜合2種算法的優(yōu)點，構(gòu)成自適應(yīng)遺傳退火算法，具有以下優(yōu)勢:1)SA算法在各狀態(tài)賦予優(yōu)化過程可變的概率突跳性，高溫時，算法具有較高的突跳性，溫度漸緩時，Metropolis抽樣過程使得SA算法變?yōu)閹缀跏歉怕蕿?的帶優(yōu)變異操作，實現(xiàn)了很強的趨化性局部搜索;2)AGA算法采用群體并行搜索機制，而SA算法采用串行搜索，把這兩種算法相結(jié)合，能夠使得SA成為并行搜索算法，以提高算法的優(yōu)化性能;3)AGA和SA算法對參數(shù)的選取要求很苛刻，不合適的參數(shù)會嚴(yán)重影響算法的性能。AGA算法的參數(shù)選取沒有明確的理論指導(dǎo)，多半要靠大量的實驗和經(jīng)驗來確定，而AGA和SA相混合，使算法的性能有所提高，因此，對算法參數(shù)的選取不必太嚴(yán)格。

3 求解0/1背包問題的自適應(yīng)遺傳退火算法的具體實現(xiàn)

根據(jù)以上介紹的算法的各種策略，制定了求解基于0/1背包的自適應(yīng)遺傳退火算法如下。

步驟1 給定算法參數(shù)，包括種群規(guī)模popsize，染色體長度chromlong，自適應(yīng)交叉概率Pc1，Pc2，自適應(yīng)變異概率Pm1，Pm2，退火溫度tk，退溫系數(shù)a等;

步驟2 隨機產(chǎn)生初始群體pop(k)，其中k賦初始值0，作為初始迭代;

步驟3 根據(jù)適應(yīng)函數(shù)對群體中每一個個體的適應(yīng)度值作出評價，并判斷其是否符合優(yōu)化準(zhǔn)則，若符合，輸出最佳個體及其代表的最優(yōu)解，并結(jié)束計算;否則執(zhí)行以下步驟;

步驟4 按照輪盤賭和最佳保存策略相結(jié)合的方式執(zhí)行選擇操作，并按照自適應(yīng)交叉、變異概率公式執(zhí)行基因重組和基因突變操作，產(chǎn)生SA算法的初始群體SA_pop(k);

步驟5 從群體SA_pop(k)中的每一染色體i∈SA_pop(k)的領(lǐng)域中隨機選取一個狀態(tài)j∈N(i)，按照Metropolis抽樣準(zhǔn)則接受或拒絕j，該階段需要進行popsize次迭代產(chǎn)生下一代群體pop(k+1);

步驟6 執(zhí)行退溫操作tk+1=a×tk，并令k=k+1，返回步驟3;

在自適應(yīng)遺傳退火算法流程中，步驟5的群體選擇隨機搜索一個個體的領(lǐng)域空間，比單純遺傳算法的搜索空間更大，相當(dāng)于用N(i)取代了?SA_pop(k)，同時用Metropolis抽樣準(zhǔn)則由(6)式所確定的接受概率接收可行解，進一步增大了領(lǐng)域內(nèi)的局部搜索能力，而步驟4中最優(yōu)保存策略的引入，是為了避免當(dāng)代種群最優(yōu)解的流失，同時引入自適應(yīng)交叉、變異概率，保證了在交叉、變異時能自適應(yīng)地調(diào)整當(dāng)代種群最佳的Pc，Pm。

4 實例仿真

為了考察AGAA求解0－1背包問題的性能，下面用matlab語言編寫了AGAA算法的程序，同時編寫了GA，AGA兩種算法的程序，3種算法的程序在CPU為Intel cole T6570，內(nèi)存為2 GByte，操作系統(tǒng)為Window XP的計算機上對4個背包實例進行研究。

4.1 AGAA，AGA和GA的對照實驗及結(jié)果

實驗中，背包數(shù)目分別選10，20，50，100為測試實例，其中，實例1來源于文獻(xiàn)［6］，實例2和3來自文獻(xiàn)［7］，實例4來源于文獻(xiàn)［8］。參與對比的2種算法分別為AGA，GA。為了減少隨機性對算法性能的影響，各算法對每一測試算例獨立運行20次，以便分析它們的統(tǒng)計特征。實驗中，3種算法的適應(yīng)度公式均相同，AGAA，AGA，GA 3種算法的種群規(guī)模均選為100，交叉、變異率均設(shè)定為 Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.001，AGAA 算法中初始退火溫度均設(shè)定為800，衰減因子設(shè)定為K=0.95，3種算法均以最大迭代次數(shù)為停止準(zhǔn)則，即背包數(shù)目10，20，50，100 分別設(shè)定最大迭代次數(shù)為 50，80，250，300。

3種算法所獲得的統(tǒng)計值比較如表1所示。表1中，性能比較標(biāo)準(zhǔn)為算法在20次獨立運行中所獲得的最優(yōu)適應(yīng)度值Vmax，最差適應(yīng)度值Vmin，平均適應(yīng)度值Vavg，平均波動率δ，最小迭代次數(shù)Tmin，平均迭代次數(shù)Tavg以及所獲得可行最優(yōu)解的次數(shù)Z。表1中，N表示不同的背包數(shù)目;“—”表示文獻(xiàn)中未進行該數(shù)值結(jié)果的統(tǒng)計;Tmin，Tavg能夠衡量算法的收斂速度(時間復(fù)雜度);Vmax，Vmin，Vavg，Z 能夠衡量算法的尋優(yōu)能力;δ能夠衡量算法的穩(wěn)定程度。其中

(7)式中，Vopitimation為不同背包數(shù)目的理論最優(yōu)值。

表1 3種算法所獲得的統(tǒng)計值比較Tab.1 Statistical comparison by three algorithms

由表1可知，對于10個數(shù)目的背包而言，平均波動率均大于0，表明AGA，GA 2種算法在20次獨立運行中至少有一次獲得了近似最優(yōu)解;對于20個數(shù)目的背包而言，AGAA所獲得的最優(yōu)值數(shù)目均比其他2種算法多，且平均波動率為0.143%，明顯低于其他2種算法，表明AGAA算法的穩(wěn)定性更好;對于30個數(shù)目的背包，GA，AGA 2種算法均未獲得最優(yōu)值，而AGAA獲得了3次最優(yōu)解，可見，在問題規(guī)模逐步增大時，參與比較的2種算法搜索到最優(yōu)值相當(dāng)困難，且平均波動率也進一步增大，雖AGAA算法的平均波動率達(dá)到了0.370%，但仍小于其他2種算法，進而表明，AGAA的穩(wěn)定性是較好的;對于100個數(shù)目的背包而言，3種算法均未收斂到最優(yōu)值，只是在解的領(lǐng)域空間里獲得了近似最優(yōu)解，但AGAA所獲得的平均適應(yīng)度值最大，且高于文獻(xiàn)［8］，可見該算法的尋優(yōu)能力最好。從整體上看，對于不同數(shù)目的背包問題，AGAA算法的收斂代數(shù)明顯少于其他2種算法的收斂代數(shù)，平均波動率也好于其他2種算法，從而表明，AGAA算法在求解大規(guī)模背包問題時，其收斂速度、尋優(yōu)能力和穩(wěn)定性要比其他2種算法更滿意。

圖1—2是N分別為20，50時，3種算法獨立運行20次中某一次最佳適應(yīng)度值的收斂曲線圖，從圖1可以看出，3種算法均能尋優(yōu)到理想最優(yōu)值，而AGAA算法的收斂速度明顯大于參與比較的2種算法，從圖2可以看出，僅AGAA收斂到了理想最優(yōu)值，而且收斂速度較快。

圖1 N=20時，3種算法最佳適應(yīng)度值收斂圖Fig.1 Best fitness value convergence map of three algorithms when N=20

5 結(jié)束語

引入自適應(yīng)交叉、變異和退火策略的AGAA加劇了染色體之間的競爭，提高了收斂速度，同時加強了種群跳出局部最優(yōu)的能力，實驗結(jié)果表明，AGAA處理0/1背包問題具有明顯的優(yōu)越性，具有較好的搜索效率。

圖2 N=50時，3種算法最佳適應(yīng)度值收斂圖Fig.2 Best fitness value convergence map of three algorithms when N=20

在N=100個背包的實例中，AGAA算法未能搜索到理論最優(yōu)值，但平均適應(yīng)度值高于文獻(xiàn)［8］，至此，該算法如何在解決高維0/1背包問題中獲得更為理想的解，需進一步研究。

［1］何小鋒，馬良.求解0-1背包問題的量子蟻群算法［J］.計算機工程與應(yīng)用，2011，47(16):29-31.HE Xiaofeng，MA Liang.Quantumispired ant algorithm for solving 0-1 knapsack problem［J］.Computer Engineering and Application，2011，47(16):29-31.

［2］熊小華，寧愛兵，馬良.多目標(biāo)0-1背包問題的元胞競爭決策算法［J］.計算機應(yīng)用研究，2010，27(10):3680-3682.XIONG Xiaohua，NING Aibing，MA Liang.Cellular competitive decision algorithm for multi-objrctive 0-1 knapsack problem［J］.Application Research of Computers，2010，27(10):3680-3682.

［3］吳迪，姜永增，宋廣軍.基于蜂群遺傳算法的0-1背包問題［J］.計算機工程與科學(xué)，2011，33(5):102-105.WU Di，JIANG Yongzeng，SONG Guangjun.The 0-1 knapsack problem based on the bee-swarm genetic algorithm［J］.Engineering and Science，2011，33(5):102-105.

［4］黃凱，茅永興，周文晉.基于遺傳算法的測量船工況優(yōu)選方法［J］.電訊技術(shù)，2009，49(7):13-17.HUANG Kai，MAO Yongxing，ZHOU Wenjin.A new method of optimizing the tracking-ship operation condition design based on genetic algorithm［J］.Telecommunication Engineering，2009，49(7):13-17.

［5］李劍，景博.自適應(yīng)遺傳算法在多邊多議題協(xié)商中的應(yīng)用［J］.北京郵電大學(xué)學(xué)報，2008，31(6):67-69.LI Jiang，JING Bo.Adaptive genetic alg-orithm and its application in multi-lateral multi-issue negotiation［J］.Journal of Bei-jing University of Posts and Telecommu-nication，2008，31(6):67-69.

［6］馬良，王龍德.背包問題的螞蟻優(yōu)化算法［J］.計算機應(yīng)用，2001，21(8):4-5.MA Niang，WANG Longde.Ant optimization algorithm for knapsack problem［J］.Computer Application，2001，21(8):4-5.

［7］李康順，賈玉珍，張文生.一種基于模式替代的遺傳算法解0/1背包問題［J］.計算機應(yīng)用研究，2009，26(2):470-471.LI Kangshun，JIA Yuzhen，ZHANG Wensheng.Genetic algorithm with schema raplaced for solving 0/1 knapsack problem［J］.Application Research of Computers，2009，26(2):470-471.

［8］莊中文，錢淑渠.抗體修正免疫算法對高維0/1背包問題的應(yīng)用［J］.計算機應(yīng)用研究，2009，26(8):2921-2923.ZHUANG Zhongwen，QIAN Shuqu.Immune algorithm with antibody-repaired and its application for high-dimensional 0/1 knapsack problem［J］.Application Research of Computers，2009，26(8):2921-2923.