模擬退火和模擬退火思想在0-1背包問題中的應(yīng)用

模擬退火和模擬退火思想在0-1背包問題中的應(yīng)用

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