求解0/1背包問題的自適應(yīng)遺傳退火算法

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

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

0 引言

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

1 背包問題

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

2 遺傳算法及其改進(jìn)

2.1 遺傳算法

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

2.2 遺傳算法的改進(jìn)

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

1)編碼策略。

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

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

2)選擇策略。

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

3)交叉、變異策略。

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

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

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

4)退火策略。

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

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

2.3 算法效率定性分析

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

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

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

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

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

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

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

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

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

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

4 實(shí)例仿真

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

4.1 AGAA，AGA和GA的對(duì)照實(shí)驗(yàn)及結(jié)果

實(shí)驗(yàn)中，背包數(shù)目分別選10，20，50，100為測(cè)試實(shí)例，其中，實(shí)例1來源于文獻(xiàn)［6］，實(shí)例2和3來自文獻(xiàn)［7］，實(shí)例4來源于文獻(xiàn)［8］。參與對(duì)比的2種算法分別為AGA，GA。為了減少隨機(jī)性對(duì)算法性能的影響，各算法對(duì)每一測(cè)試算例獨(dú)立運(yùn)行20次，以便分析它們的統(tǒng)計(jì)特征。實(shí)驗(yàn)中，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)計(jì)值比較如表1所示。表1中，性能比較標(biāo)準(zhǔn)為算法在20次獨(dú)立運(yùn)行中所獲得的最優(yōu)適應(yīng)度值Vmax，最差適應(yīng)度值Vmin，平均適應(yīng)度值Vavg，平均波動(dòng)率δ，最小迭代次數(shù)Tmin，平均迭代次數(shù)Tavg以及所獲得可行最優(yōu)解的次數(shù)Z。表1中，N表示不同的背包數(shù)目;“—”表示文獻(xiàn)中未進(jìn)行該數(shù)值結(jié)果的統(tǒng)計(jì);Tmin，Tavg能夠衡量算法的收斂速度(時(shí)間復(fù)雜度);Vmax，Vmin，Vavg，Z 能夠衡量算法的尋優(yōu)能力;δ能夠衡量算法的穩(wěn)定程度。其中

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

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

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

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

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

5 結(jié)束語

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

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

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

［1］何小鋒，馬良.求解0-1背包問題的量子蟻群算法［J］.計(jì)算機(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ìng)爭(zhēng)決策算法［J］.計(jì)算機(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］.計(jì)算機(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］黃凱，茅永興，周文晉.基于遺傳算法的測(cè)量船工況優(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é)報(bào)，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］.計(jì)算機(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］.計(jì)算機(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］莊中文，錢淑渠.抗體修正免疫算法對(duì)高維0/1背包問題的應(yīng)用［J］.計(jì)算機(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.