模擬退火和模擬退火思想在0-1背包問題中的應用

模擬退火和模擬退火思想在0-1背包問題中的應用

1基于模擬退火的遺傳算法遺傳算法和模型退火算法是近年來優(yōu)化問題的兩種智力方法。遺傳理論采用生物進化的概念，并通過自然選擇和適應性策略來解決優(yōu)化問題。遺傳算法具有良好的整體搜索效率，但實際應用中容易發(fā)現(xiàn)早期收斂問題，在進化后期搜索效率較低。模型退火算法是模擬力學中物理火的學習規(guī)則。該算法不僅可以優(yōu)化目標函數(shù)，而且可以以一定的概率接受目標函數(shù)的不均勻分解，從而避免陷入局部優(yōu)勢，確保獲得全球最佳解決方案的可靠性，但其收取速度緩慢。本文在提出模糊回歸理論的基礎上，有效緩解了遺產(chǎn)繼承算法的選擇壓力，并根據(jù)0-1包絡合物的實際情況設計了交叉和變異算子，這不僅提高了遺傳計算的全球收集性，而且在后期的泛在化中具有強大的爬山性能，加速了泛在化的收斂速度。2物品明確規(guī)劃模型背包問題(knapsackproblem)的一般提法是:已知n個物品的重量(weight)及其價值(或收益profit)分別為Wi>0和Pi>0,背包的容量(contain)為C>0,選擇哪些物品裝入背包可以使得在背包的容量約束限制之內(nèi)所裝物品的價值最大呢?該問題的模型可以表示為下述0/1整數(shù)規(guī)劃模型.目標函數(shù):maxf(x1,x2,?,xn)=n∑i=1piximaxf(x1,x2,?,xn)=∑i=1npixi約束條件:{n∑i=1wixi≤Cxi∈{0,1}(i=1,2,?,n)???????∑i=1nwixi≤Cxi∈{0,1}(i=1,2,?,n)式中,Xi為0-1決策變量,Xi=1時表示將物品i裝入背包中,Xi=0時則表示不將其裝入背包中.3最佳算法及終止程序模擬退火算法是一種有效的全局優(yōu)化算法,在模擬退火算法中,適當?shù)乜刂茰囟鹊南陆颠^程實現(xiàn)模擬退火,從而得到全局的最優(yōu)解.模擬退火算法來源于固體退火原理,將固體加溫至充分高,再讓其徐徐冷卻,加溫時,固體內(nèi)部粒子隨溫度升高變?yōu)闊o序狀,內(nèi)能增大,而徐徐冷卻時粒子漸趨有序,在每個溫度都達到平衡態(tài),最后在常溫時達到基態(tài),內(nèi)能減為最小.基本流程如下:(1)初始化:初始溫度T(充分大),初始解狀態(tài)S(是算法迭代的起點),每個T值的迭代次數(shù)L;(2)對k=1,…,L做(3)～(6)步;(3)產(chǎn)生新解S′;(4)計算增量Δt′=C(S′)-C(S),其中C(S)為評價函數(shù);(5)若Δt′<0則接受S′作為新的當前解,否則以概率exp(-Δt′/T)接受S′作為新的當前解;(6)如果滿足終止條件則輸出當前解作為最優(yōu)解,結束程序.終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法;(7)T逐漸減少,且T→N(N一般取足夠小的常量),然后轉(zhuǎn)(2).4遺傳算法的一般描述遺傳算法是將問題的每一個可能性解看作是群體中的一個個體(染色體),并將每一個染色體編碼成串的形式,再根據(jù)預定的目標函數(shù)對每個個體進行評價,給出一個適應值.算法將根據(jù)適應度值進行尋優(yōu)過程,遺傳算法的尋優(yōu)過程是通過選擇、雜交和變異三個遺傳操作來具體實現(xiàn)的.搜索能力由選擇算子和雜交算子決定,變異算子則保證了算法能夠搜索到問題空間的盡可能多的點,從而使其具有搜索全局最優(yōu)的能力.在遺傳算法中,定義長度較短、低階且適應值超過平均適應值的模式在群體中數(shù)目的期望值按指數(shù)遞增,這個結論稱為遺傳算法的基本定理.遺傳算法是通過定義長度短、確定位數(shù)少、適應度值高的模式的反復抽樣、組合來尋找最佳點,稱這些使遺傳算法有效工作的模式為積木塊,是遺傳算法構造答案的基本材料.但歸根到底,要使遺傳算法有效工作必須按照遺傳算法的模式定理(或積木塊假設)根據(jù)具體問題設計合理編碼方案.在運行遺傳算法程序時,需要對一些參數(shù)作事先選擇,它們包括種群的大小、染色體長、雜交率、變異率、最大進化代數(shù)等,這些參數(shù)對GA的性能都有很重要的影響.5包容量和物品個數(shù)基于背包問題的模型,我們設計了相對應的染色體編碼方法:將待求解的各量X表示成長為n(n為待裝入背包的物品數(shù))的二進制字符串X[i](i=1,2,…,n).X[i]=0表示物品i不放入背包內(nèi),X[i]=1表示物品i放入背包內(nèi).例如:101010100…00101代表一個解,它表示將第1,3,5,7,…,n-2,n號物體放入背包中,其他的物體則不放入.本算法定義背包容量和物品個數(shù)分別為:contain=1000,lchrom=50.5.1項目設計在這個過程中,本文設計了不同的編碼方式(操作算子)來驗證算法的性能。(1)染色體結構數(shù)據(jù)從knapin.txt中讀取背包問題的相關信息并將解空間的數(shù)據(jù)進行二進制編碼,轉(zhuǎn)換為遺傳空間的基因型串(即染色體)結構數(shù)據(jù),如本算法以50個物品為例:oldpop[i].chrom[j]=rand()%2,則解空間內(nèi)一個基因串長度為50的二進制串;定義整數(shù)lchrom作為染色體的長度,并且隨機產(chǎn)生popsize個染色體作為初始種群,在產(chǎn)生這popsize個染色體時,本文選取的是weight小于背包容量的個體作為種群的成員;(2)實驗設計與程序評價函數(shù)對種群中的每個染色體(chrom)求得其個體適應度,以基因被選擇與否,計算pop[i].fitness=cal_fit(pop[i].chrom),按照下列公式計算種群中個體權重與適應度(收益):weight=lchrom-1∑i=0weight[i]*chromweight=∑i=0lchrom?1weight[i]*chrom[i]fitness=lchrom-1∑i=0profit[i]*chromfitness=∑i=0lchrom?1profit[i]*chrom[i]設置適應度的懲罰函數(shù):pen*(contain-weight),降低適應度最小個體的適應度,以減少它被選出的概率,其中參數(shù)pen=1.5(pen的確定需經(jīng)過實驗測試得到),minpop為種群中適應度最小個體的索引;(3)代次的種規(guī)則精英選擇,保留父代和子代的最優(yōu)個體.選擇把當前群體中適應度較高的個體按某種規(guī)則或者模型遺傳到下一代種群中,這里所用的規(guī)則是:①(輪盤賭選擇)染色體在種群中被選擇的可能性與其個體的適應度的大小成正比;②(競標賽選擇)隨機從原始種群中選擇10個個體(染色體),比較其適應度,從中選擇適應度最大個體;(4)自適應雜交概率采用雙親單子法,定義參數(shù)pc作為雜交操作的概率(這里使用了兩種:①固定雜交概率pc;②自適應雜交概率pc),由(3)選擇得到的兩個個體以概率pc交換各自的部分染色體(這里使用了單點雜交和多點雜交),得到新的兩個個體.其中自適應雜交概率的計算以如下公式進行:pc={kf′＜favgk*f′-favgfbest-favgf′＞favgpc=???kk*f′?favgfbest?favgf′＜favgf′＞favg式中,f′為所得兩個父個體的平均適應度,favg為種群平均適應度,fbest為種群個體最大適應度,k=0.9;采用自適應雜交概率在算法前期作用不大,但是在后期,當種群適應度普遍較高時,有利于保持算法的穩(wěn)定性(當兩個父體適應度較高時,相應的雜交概率自適應的變小,從而有利于保留優(yōu)勢個體);(5)概率pm法定義參數(shù)Pm=0.05作為變異操作的概率,由(4)得到每個個體中的每個基因值都以概率Pm進行變異,這里未采用自適應的變異(由于問題規(guī)模不大,這樣可能適得其反);(6)下一次退火迭代—退火過程:在一個種群進化周期內(nèi)(退火周期),設定初始退火溫度T和每個T值的迭代次數(shù)(相當于種群演化次數(shù))L;在每一個退火周期內(nèi),令T=k*T,進行退火,其中k為退火系數(shù),控制著降溫的速率,對算法結果的好壞有決定性作用.依據(jù)遺傳操作得到新種群,然后比較新老種群中各自最大適應度個體,如果maxfitness≥oldmax(其中maxfitness為新種群中個體最大適應度,oldmax為老種群中個體最大適應度),則接受新種群作為下一次退火迭代的初始種群,并令新種群的最好個體為當前最好解;如果maxfitness<oldmax,則以概率expmaxfitness-olemaxΤexpmaxfitness?olemaxT接受新種群為下一次退火迭代的初始種群,若不能接受,則先以原始種群的最大適應度個體替換新種群的最小適應度個體,然后以新組成的種群作為下一次退火迭代的初始種群.這樣做能夠很好的保持種群多樣性,以克服遺傳算法容易陷入局部最優(yōu)的缺陷.退火過程直到溫度下降到一個預定小的值或者達到既定的退火周期為止.5.2遺傳操作和退火(1)讀入背包問題信息,以二進制編碼初始化種群,評估種群中個體的適應度;(2)初始化退火(進化)周期C=1,進入一次退火過程中:①設置退火初始溫度T=3000;②初始化退火迭代次數(shù)L=100,對初始化的種群進行遺傳操作,按5.1節(jié)中的(3)和(4)對種群進行選擇和雜交操作,然后對新產(chǎn)生種群的每個染色體按5.1節(jié)中的(5)進行變異操作;③評估種群的適應度,然后按5.1節(jié)中的(6)進行模擬退火操作;④每次退火操作后,都保存到目前為止適應度最佳個體的相關信息,避免退火過程中產(chǎn)生的全局最優(yōu)個體被遺傳退火操作“干掉”;同時令L=L-1,若L>0,開始下一次迭代,直到L=0時轉(zhuǎn)到⑤;⑤令T=k*T,T>10轉(zhuǎn)到②,開始新一個T值的退火循環(huán);否則向下執(zhí)行;(3)保存一個退火周期里的最佳個體信息,令C=C+1,轉(zhuǎn)①;(4)全部退火周期結束后,保留并輸出最佳個體.6溫度、退火溫度和模式2.2優(yōu)化算法為了能夠驗證混合算法的有效性和穩(wěn)定性,本文通過數(shù)據(jù)實驗對改進的混合算法與傳統(tǒng)的GA和SA算法進行對比.其中實驗數(shù)據(jù)一部分來源常見的遺傳算法文獻,另一部分則通過隨機產(chǎn)生.試驗環(huán)境:CPU—Intel(R)Core(TM)2Duo2.0GHz內(nèi)存—1GB;操作系統(tǒng)—WindowsXp;開發(fā)程序—VC++6.0.參數(shù)設置:種群規(guī)模popsize=200;染色體長度lchrom=50;初始溫度:T=3000;降溫系數(shù):d=0.8;退火終止溫度:10;每個溫度內(nèi)的迭代次數(shù):num=100.計算分析過程:分別用遺傳算法、模擬退火算法以及本文提出的改進算法對每個數(shù)據(jù)集都計算10次,保存計算結果.然后針對每個數(shù)據(jù)集,分析三種算法得到的最優(yōu)值、最差值、平均值、偏差和改進比例.①偏差=(最優(yōu)值-平均值)/最優(yōu)值;②改進比例=(改進算法的最優(yōu)值-GA/SA的最優(yōu)值)/(GA/SA的最優(yōu)值).實驗結果見表1.附:Data3數(shù)據(jù)Weight={80,82,85,70,72,70,82,75,78,45,49,76,45,35,94,49,76,79,84,74,76,63,35,26,52,12,56,78,16,52,16,42,18,46,39,80,41,41,16,35,70,72,70,66,50,55,25,50,55,40}Profit={200,208,198,192,180,180,168,176,182,168,187,138,184,154,168,175,198,184,158,148,174,135,126,156,123,145,164,145,134,164,134,174,102,149,134,156,172,164,101,154,192,180,180,165,162,160,158,155,130,125}Contain=10007遺傳算子實驗本文算法測試不同規(guī)模的數(shù)據(jù)集都取得了很好的結果.相比GA和SA而言,本算法在這些數(shù)據(jù)集上都有較大的改進.理論上,當所謂的退火三原則(初始溫度足夠高,降溫速度足夠慢,終止溫度足夠低)滿足時,模擬退火算法以概率1達到全局最優(yōu)解.但是初始溫度及降溫函數(shù)的選取會讓算法的性能差異很大,就像使用遺傳算法時使用不同的選擇算子和雜交算子對算法的性能影響很大一樣.本文用了不同的遺傳算子進行實驗,最終確定退火參數(shù).每一個退火周期相當于一個種群的進化周期,在進化過程中同時進行遺傳操作和退火操作,控制參數(shù)T的下降幅度可能導致算法進程迭代次數(shù)的增加,