【正文】 子的作用，能夠互相拼接在一起，形成高階、長定義距、高平均適應(yīng)度的模式，最終接近全局最優(yōu)解。 目前大量的實(shí)踐支持積木塊假設(shè)，它在許多領(lǐng)域內(nèi)都取得了成功，例如平滑多峰 設(shè)計(jì)（論文）專用紙 12 問題、帶干擾多峰問題以及組合優(yōu)化問題等。 雖然模式定理在一定意義上解決了基本遺傳算法的有效性，但它仍有以下的缺點(diǎn)： a) 模式定理只對(duì)二進(jìn)制編碼適用，對(duì)其他編碼方案尚沒有相應(yīng)的結(jié)論成立； b) 模式定理只給出了在下世代包含模式 H 的個(gè)體數(shù)的下限。 遺傳算法基本原理 典型的遺傳算法 CGA[19] (Canonical Geic Algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問題：考慮對(duì)于一群長度為 L 的二進(jìn)制編碼 bi， i=1， 2，?， n；有bi{0， l}L 給定目標(biāo)函數(shù) f，有 f(bi)0 同時(shí) f(bi)≠ f(bi+1)，求滿足式 max{f(bi)｜bi{0， 1}L}的 bi；。 長度為 L的 n個(gè)二進(jìn)制串 bi(i=1， 2，?， n)組成了遺傳算 法的初解群，也稱為初始群體。根據(jù)進(jìn)化術(shù)語，對(duì)群體執(zhí)行的操作有三種： a) 選擇 (Selection)：這是從群體中選擇出較適應(yīng)環(huán)境的個(gè)體。故有時(shí)也稱這一操作為再生 (Reproduction)。 b) 交叉 (Crossover)：這是在選中用于繁殖下一代的個(gè)體中，對(duì)兩個(gè)不同的個(gè)體 設(shè)計(jì)（論文）專用紙 13 的相同位置的基 因進(jìn)行交換，從而產(chǎn)生新的個(gè)體。在串 bi中，如果某位基因?yàn)?l，產(chǎn)生變異時(shí)就是把它變成 0；反之亦然。 遺傳算法的實(shí)現(xiàn)過程 遺傳算法是模擬達(dá)爾文的生物自然選擇學(xué)說和自然界的生物進(jìn)化過程的一種自適應(yīng)全局概率搜索算法。種群由計(jì)算機(jī)生成 (一般是隨機(jī)生成 )的一定數(shù)目的個(gè)體組成，個(gè)體就是潛在解的計(jì)算機(jī)編碼，那么我們最后要求的解就由這些初始生成的個(gè)體進(jìn)化而來的。當(dāng)然在具體的進(jìn)化過程中為了保持種群多樣性防止過早收斂，還要在其中使個(gè)體以一定小概率發(fā)生變異。 遺傳算法的實(shí)現(xiàn)過程主要包 括編碼、產(chǎn)生群體、計(jì)算適應(yīng)度、復(fù)制、交換、變異等操作。這個(gè)初始的群體也就是問題假設(shè)解的集合。通常以隨機(jī)方法產(chǎn)生串或個(gè)體的集合 bi， i=1， 2，? n。 (2)選擇：根據(jù)適者生存原則選擇下一代的個(gè)體。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。以選中 bi為下一代個(gè)體的次數(shù)。 設(shè)計(jì)（論文）專用紙 14 b) 適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少；甚至被淘汰。對(duì)于問題求解角度來講，就是選擇出和最優(yōu)解較接近的中間解。在選中的位置實(shí)行交換。交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。 (4)變異：根據(jù)生物遺傳中基因變異的原理，以變異概率 Pm 對(duì)某些個(gè)體的某些位執(zhí)行變異。變異概率 Pm 與生物變異極小的情況一致，所以， Pm的取值較小，一般取 。對(duì)其的第 l、 4位置的基因進(jìn)行變異，則有 S1=001111。但是，它能保證算法過程不會(huì)產(chǎn)生無法進(jìn)化的單一群體。也就是說，變異增加了全局優(yōu)化的特質(zhì)。否則，用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到第 2 步即選擇操作處繼續(xù)循環(huán)執(zhí)行。 T 代種群用變量 P(t)表示，初始種群 P(o)是隨機(jī)設(shè)計(jì)的，簡單遺傳算法的偽代碼描述如下： Procedure GA begin t=0； initialize P(t)； evaluate P(t)； while not finished do begin t=t+l； select P(t) from P(t1)； reproduce pairs in P(t)； evaluate P(t)； end end 隨機(jī)選擇種群數(shù) 計(jì)算適應(yīng)度 變異 交叉 停止 滿足條件？ 是 否 設(shè)計(jì)（論文）專用紙 16 使用遺傳算法求解 01背包問題 遺傳算法己經(jīng)在背包問題的求解上取得了一定的成果。對(duì)于 01背包問題利用簡單遺傳算法求解的基本步驟如下： (1)群體的初始化：確定種群規(guī)模 M、交叉概率 Pc、變異概率 pm染色體長度 N及最大進(jìn)化代數(shù) maxgen。 (2)產(chǎn)生遺傳編碼：采用二進(jìn)制 n 維矢量解 X 作為解空間參數(shù)的遺傳編碼，串 T的長度等于 n， xi=1表示該物件裝 入背包， xi=0表示該物件沒有被裝入背包。而其他的沒有被選中。這個(gè)遺傳編碼也需要隨機(jī)地產(chǎn)生，隨機(jī)地產(chǎn)生數(shù)字 0或 l，就構(gòu)成一個(gè)染色體串，也就是一個(gè)遺傳編碼。重新產(chǎn)生一個(gè)新的染色體；如果產(chǎn)生的染色體滿足條件，則接受它作為種群的一名成員，經(jīng)過有限次抽樣后，得到 M個(gè)可行的染色體。所以，初始化后的種群應(yīng)該是一個(gè) M*N 的二維矩陣。比如，初始化后的種群可以是如下所示： 0 1 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 （ 3）適應(yīng)度函數(shù)構(gòu)造：適應(yīng)度函數(shù)的建立是解決背包問題的關(guān)鍵，首先背包問題的目標(biāo)函數(shù)和約束條件可表示為：目標(biāo)函數(shù)：1()niiiJ x X P???，約束條件：1niii XW C? ???？紤] n個(gè)物件的選擇與否，背包內(nèi)物件的總體積1niii XW??，物件總價(jià)值為1niii XP??，如何決定變量 Xi (i=l， 2，?，n)的值 (即確定一個(gè)物件組合 )使背包內(nèi)物件總價(jià)值為最大。 通過對(duì)這個(gè)問題的具體分析，它的適應(yīng)度函數(shù)應(yīng)該定義為每次裝入背包中的物品的之和，現(xiàn)在構(gòu)造它的適應(yīng)度函數(shù)如下：1niiiF XP???， Xi=1 或 0 （ i=1， 2，?， n)。 適應(yīng)度計(jì)算程序如下 ： temp_sum=vol*samp_arr39。 %計(jì)算每個(gè)物體單位體積的價(jià)值量，即價(jià)值密度 for i=1:POP_NUM j=0。ascend39。 while temp_sum(i) MAX_CAP j=j+1。 temp_sum(i)=temp_sum(i) vol(index(j))。這樣，就完成了對(duì)種群的選擇操作。 rtable=fit_arr./fit_sum。 end for i=1:POP_NUM p=rand(1)。 while p rtable(index) index=index+1。 end 以上程序是把所有個(gè)體的適應(yīng)度值求和，然后計(jì)算每個(gè)個(gè)體的適應(yīng)度值占總和中的比例，比例越大，該個(gè)體對(duì)應(yīng)的適應(yīng)度的范圍越大。這里嘗試用“與／或 交叉方法，這一交叉方法使子代繼承了雙親的同型基因，對(duì)于雙親的雜型基因，“與／或 交叉方法采取了兩種不同 的“支配 方式，“與”運(yùn)算是一種 0支配 l的方式，而“或 運(yùn)算是一種 1支配 0的方式，采用“與／或”交叉策略能使優(yōu)化過程更加迅速的達(dá)到全局最優(yōu)解，獲得全局最優(yōu)解的時(shí)間僅為“一點(diǎn)交叉 策略的 1／ 9到 1／ 3。 %參與交叉的樣本的索引 for i=1:POP_NUM temp=unidrnd(POP_NUMi+1)。 temp_val=cross_index(temp_pos)。 cross_index(i)=temp_val。 for i=1:2:POP_NUM %相鄰兩個(gè)進(jìn)行交叉 %隨機(jī)得到 一個(gè)數(shù)，小于交叉概率的話，進(jìn)行交叉 if rand(1) P_CROSS cross_pos=unidrnd(POP_NUM1 )。 samp_arr(cross_index(i), cross_pos:end)= ... samp_arr(cross_index(i+1), cross_pos:end)。 end end (6)變異操作：染色體變異采用位點(diǎn)變異的方式。 設(shè)計(jì)（論文）專用紙 20 變異前染色體為： 1 1 1 0 0 0 1 1 0 1 變異后染色體為： 0 0 0 1 1 1 0 0 1 0 變異概率為 Pm，變異的目的是使其變異后的適應(yīng)度大于或等于其原適應(yīng)度。對(duì)種群依次進(jìn)行選擇、交叉、變異后就檢驗(yàn)得到的新個(gè)體，當(dāng)某代得到的結(jié)果滿足要求或當(dāng)前代數(shù)等于結(jié)束代數(shù)時(shí)算法結(jié)束得到結(jié)果 ，否則重復(fù)選擇、交叉、變異操作，直到得到滿意的結(jié)果為止。 index=find(muta_arr)。 %找到最后一代中的最佳樣本 [max_val, max_index]= max(fit_arr)。 index=find(temp)。裝入背包的物品用 1 表示，未裝入的用 0表示，一種裝入方法用一個(gè)染色體表示，總共產(chǎn)生的染色體個(gè)數(shù)等于群體 規(guī)模。這樣遺傳算法的基本步驟完成，重復(fù)以上步驟，直到 設(shè)計(jì)的進(jìn)化次 設(shè)計(jì)（論文）專用紙 21 數(shù)才退出。 weight = [80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60, 30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30, 10,20,25,15,10,10,10,4,4,2,1 ]。 已知該算例的最優(yōu)解為 3103。 程序循環(huán)運(yùn)行 20次，結(jié)果如下表 21，仿真圖如22。 設(shè)計(jì)（論文）專用紙 22 0 2 4 6 8 10 12 14 16 18 201400160018002020220024002600280030003200 X : 1 0Y : 3 1 0 320 次循環(huán)結(jié)果最優(yōu)值最差值平均值 圖 22 算例 1運(yùn)行 20次結(jié)果仿真圖 通過圖 22，可以很清楚地看 到算法運(yùn)行 20次產(chǎn)生的最優(yōu)值、最差值以及平均值的仿真曲線。而最差值波動(dòng)相對(duì)較大一些，并且從仿真曲線圖中可看到最優(yōu)值與最差值之間的差距較大，說明種群具有一定的多樣性。當(dāng)種群規(guī)模分別為 100、 200、 400、 500 時(shí)，對(duì)算例 1 進(jìn)行求解，所得結(jié)果如表 22所示。 （ 2） 交叉概率對(duì)算法性能的影響 設(shè)置變異概率為 、最大迭代次數(shù)為 500、染色體長度為 50、交叉概率分別為、 、 、 、 、 、 時(shí)對(duì)算例 1 進(jìn)行求解，所得結(jié)果 如表 23。說明 交叉的頻率越高可以越快的收斂到最優(yōu)區(qū)域。 說明種群演化代數(shù)增加時(shí)，求得的解會(huì)更接近或者直接命中最優(yōu)解。 算例 2 設(shè)物品價(jià)值為 Pi，物品重量為 Wi，物品的 Wi 重量是（ 1,10）的隨機(jī)數(shù)，背包最大容量為 C。 5iipw?? （ 21） 112 n iicw?? ? （ 22） 設(shè)置 交叉概率 Pc=，迭代次數(shù)為 500，變異概率為 當(dāng)物品總數(shù)分別為50、 100、 150 時(shí) ，對(duì)算例 2 運(yùn)行 20 次，觀察種群規(guī)模分別為 50、 100、 200 時(shí)的 結(jié)果 。 表 25 不同種群規(guī)模求解算例的 2結(jié)果 種群規(guī)模 迭代次數(shù) 最大值 最小值 平均值 50 500 316 176 100 500 322 161 200 500 324 160 設(shè)計(jì)（論文）專用紙 25 0 2 4 6 8 10 12 14 16 18 20160180200220240260280300320X : 1 3Y : 3 1 6 20 次循環(huán)結(jié)果最大值最小值平均值 圖 24 種群規(guī)模為 50算例 2的仿真圖 0 2 4 6 8 10 12 14 16 18 20160180200220240260280300320340X : 1 6Y : 3 2 2 20 次循環(huán)結(jié)果最大值最小值平均值 圖 25 種群規(guī)模為 100算例 2的仿真圖 0 2 4 6 8 10 12 14 16 18 2016018020022024026028030032034020 次循環(huán)結(jié)果 X : 1 0Y : 3 2 4最大值最小值平均值 圖 26 種群 規(guī)模為 200算例 2的 仿真圖 設(shè)計(jì)（論文）專用紙 26 當(dāng)物品數(shù)為 100時(shí) 循環(huán) 20次算例 2的結(jié)果如表 26和仿真圖分別圖 2圖 2圖 29 所