【正文】 表 26 算例 2循環(huán) 20的次結(jié)果 種群規(guī)模 迭代次數(shù) 最大優(yōu)值 最小值 平均值 50 500 616 396 100 500 618 378 200 500 629 377 0 2 4 6 8 10 12 14 16 18 20350
。 當(dāng)物品數(shù)量為 50 時(shí)，循環(huán) 20 次的結(jié)果如表 25和仿真圖分別如圖 24,圖 25,圖 26 所示。 Pi 與 C 的數(shù)值由以下公式得出。 綜上所述種群規(guī)模 、交叉概率以及迭代次數(shù)的設(shè)置對(duì)于遺傳算法在求解 01背包問(wèn)題時(shí)對(duì)于命中最優(yōu)解的影響是 非常明 的，通過(guò)以上實(shí)驗(yàn)的探究我可以看到當(dāng)交叉 概率為 ，迭代次數(shù)為 500 時(shí)都命中了最優(yōu)解 3103，那么我可以利用這兩個(gè)參數(shù)對(duì)算例 2進(jìn)行測(cè)試。 （ 3） 最大迭代次數(shù)對(duì)算法性能的影響 設(shè)置變異概率為 、交叉概率為 、染色體長(zhǎng)度為 50、迭代次數(shù)分別為 100、200、 300、 500、 對(duì)算例 1運(yùn)行 20 次，所得結(jié)果如表 24所示 表 24 不同迭代次數(shù)求解算例 1的結(jié)果 最大迭代次數(shù) 總價(jià)值 總體積 100 3068 999 200 3084 1000 300 3091 1000 500 3103 1000 設(shè)計(jì)（論文）專(zhuān)用紙 24 從表 24 可以看出隨著迭代次數(shù)的增加總價(jià)值和總體積也隨之增加并且在迭代500 次時(shí)命中最優(yōu)解。 表 23 不同交叉概率求解算例 1的結(jié)果 交叉概率 總價(jià)值 總體積 3091 998 3095 1000 3103 1000 3103 1000 3103 1000 3103 1000 3103 1000 從表 23 可以看出當(dāng)交叉概率增大時(shí)與之對(duì)應(yīng)的總值和 總體積 也隨之增加并在交叉概率為 時(shí)命中最優(yōu)解，隨著交叉概率增加大依然保持命中最優(yōu)解。 表 22 不同種群規(guī)模求解算例 1 的結(jié)果 種群規(guī)模 總價(jià)值 總體積 100 3094 996 200 3095 996 400 3103 1000 500 3103 1000 從上表可以看出，隨著種群規(guī)模的增大總價(jià)值和總體積也隨之增大，并且在種群 設(shè)計(jì)（論文）專(zhuān)用紙 23 規(guī)模為 400 的時(shí)候已命中最優(yōu)解 3103，同時(shí)在種群規(guī)模為 500 時(shí)也命中最優(yōu)解，說(shuō)明種群規(guī)模增大時(shí)遺傳算法在求解背包問(wèn)題的時(shí)候選擇范圍更廣，更易命中最優(yōu)解。 B 不同參數(shù)對(duì)算法性能的影響 （ 1） 種群規(guī)模對(duì)算法性能影響 設(shè)置交叉概率為 ，變異概率為 ，最大迭代次數(shù)為 500，染色體長(zhǎng)度為 50。從圖中可 以看出最優(yōu)值仿真曲線和平均值的仿真曲線波動(dòng)不大，表明遺傳算法的尋優(yōu)能力比較好。 表 21 算例 1求解結(jié)果 循環(huán)次數(shù) 迭代次數(shù) 最優(yōu)值 最差值 平均值 命中最優(yōu)解概率 20 500 3103 1429 45% 從表 21可以看出在程序運(yùn)行 20次中命中了 9次最優(yōu)解 3103，平均值為 ，最優(yōu)值與最差值的差值為 1674，說(shuō)明遺傳算法求解背包問(wèn)題不易陷入局部最優(yōu)。將種群規(guī)模設(shè)置為 50，最大迭代次數(shù)為 500，交叉概率為 ，變異概率為 。 C=1000 其中， value 表示背包中物品的價(jià)值， weight 表示相應(yīng)物品的重量， C 表示 背包的最大容量。 算例 1 A． 實(shí)驗(yàn)設(shè)置與仿真結(jié)果 value = [220,208,198,192,180,180,165,162,160,158,155,130,125,122, 120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73, 72， 70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1]。對(duì)各個(gè)染色體計(jì)算其適應(yīng)度值，淘汰適應(yīng)度值最低的，復(fù)制適應(yīng)度值最高的，用最高的代替最低的，這樣完成選擇；再隨機(jī)產(chǎn)生交叉點(diǎn)及相互交叉的染色體進(jìn)行交叉，計(jì)算交叉后的染色體是否符合要求，即裝入背包的物品的總體積小于背包容量，若不符合則交叉失敗，重新交叉，達(dá)到交叉最多次數(shù)未交叉成功則退出；交叉完成后就進(jìn)行變異，根據(jù)變異概率隨機(jī)選擇變異的染色體，隨機(jī)產(chǎn)生變異點(diǎn)進(jìn)行變異，變異后也需要計(jì)算染色體是否符合要求，若不符合則變異失敗，重新變異，達(dá)到變異最多次數(shù)未變異成功則退出。 %index記錄所取得物體編號(hào) 數(shù)值試驗(yàn)以及結(jié)果分析 程序思路分析如下 ： 采用二進(jìn)制 0I 編碼。 temp=samp_arr(max_index, :)。 samp_arr(index)=1samp_arr(index)。 %變異操作，直接針對(duì)整個(gè)樣本集操作 muta_arr=( rand(POP_NUM, LEN) P_MUTA )。先選擇一個(gè)變異位進(jìn)行變異，再計(jì)算它的適應(yīng)度，看它是否大于或等于其原來(lái)的適應(yīng)度，若不是的話就重新選擇變異位進(jìn)行變異。位點(diǎn)變異比較簡(jiǎn)單，針對(duì)本問(wèn)題來(lái)說(shuō)，就是把染色體的變異位 1變?yōu)?0， 0變?yōu)?1就可以了，其它位都保持不變。 samp_arr(cross_index(i+1), cross_pos:end)=temp_cross。 %交叉點(diǎn)位置 ,[1, POP_NUM1] temp_cross=samp_arr(cross_index(i), cross_pos:end)。 end 選擇個(gè)體中的兩個(gè)位置，把這兩個(gè)位置對(duì)應(yīng)的值進(jìn)行交換， 交叉操作 先對(duì)可能要經(jīng)行交叉的樣本進(jìn)行索引，隨機(jī)得到一個(gè)數(shù)若這個(gè)數(shù)小于交叉概率的話進(jìn)行相鄰交叉否則不交叉。 cross_index(temp_pos)=cross_index(i)。%在 1到 POP_NUMi+1之間取隨機(jī)數(shù) temp_pos=i+temp1。 % 交叉操作 cross_index=1:POP_NUM。 (5)交叉操作：判斷染色體是否為活的染色體，若為活的染色體，則將染色體進(jìn)行交叉，一般采用一點(diǎn)交叉方式，交叉概率為 Pc，具體操作是在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新 設(shè)計(jì)（論文）專(zhuān)用紙 19 個(gè)體。 end winner_index(i)=index。 index=1。 %輪盤(pán)， rotary table %生成輪盤(pán)，類(lèi)似于概率分布 For i=2:POP_NUM rtable(i)=rtable(i1)+rtable(i)。相應(yīng)程序如下： % 選擇操作（輪盤(pán)賭） fit_sum=sum(fit_arr)。 end end end end 設(shè)計(jì)（論文）專(zhuān)用紙 18 (4)選擇操作：根據(jù)選擇概率選擇染色體，將上述的個(gè)體作為第 1 代，這里采用以正比于適應(yīng)度的賭輪隨機(jī)選 擇方式，每個(gè)體適應(yīng)度值為 fi，則 i 被選中的概率 psi為：1/nsi i iip f f?? ?；；對(duì)于初始化后的種群，先計(jì)算出每條染色體的適應(yīng)度值，再計(jì)算出其被選擇的概率，將它們進(jìn)行比較，把選擇概率最小的一條染色體淘汰掉，并把選擇概率最大的一條染色體進(jìn)行復(fù)制，用這條復(fù)制的來(lái)替代淘汰的染色體位置。 if samp_arr(i,index(j))==1 samp_arr(i,index(j))=0。)。 if temp_sum(i) MAX_CAP [temp, index]=sort(rate, 39。 rate=val./vol。 把所有的物品都放到背包里，那么就可能就會(huì)大于背包容量，如果大于的話，根據(jù)價(jià)值密度的排序，把價(jià)值密度低對(duì)應(yīng)的背包去除，一直到滿(mǎn)足設(shè)定的背包容量為止。這個(gè)問(wèn)題解的總組合數(shù)有 2 個(gè)，其數(shù)學(xué)模型表示為：1niii XW C? ??時(shí)，使得1niii XP??大， Xi=1 或 0（ i=1， 2，?， n)。 設(shè)計(jì)（論文）專(zhuān)用紙 17 由于我們之前定義當(dāng)物件 i 被選入背包時(shí)， 設(shè)定變量 Xi=1，否則是 Xi=0。如果 M= N=IO，那么初始化后的種群可以看作一個(gè) 5 行 10 列的矩陣。 具體說(shuō)來(lái)，最終會(huì)產(chǎn)生 M 條染色體，而每條染 色體又有 N個(gè)基因，也就是每條染色長(zhǎng)度是 N。每產(chǎn)生一個(gè)染色體，就對(duì)它進(jìn)行一次檢驗(yàn)，如果不滿(mǎn)足約束條件，則拒絕接受。也就是說(shuō)，現(xiàn)在這個(gè)背包里只有 7 這三個(gè)物件。例如 x={0，1， 0， 1， 0， 0， 1)表示第 7 這三個(gè)物品被選入背包中。隨機(jī)初始化染色體，給出物品體積、物品價(jià)值和背包容量 C。運(yùn)用簡(jiǎn)單遺傳算法求解背包問(wèn)題時(shí)，若問(wèn)題的規(guī)模不大時(shí)能夠得到最優(yōu)解或近似最優(yōu)解。 遺傳算法流程圖如圖 21 所示： 設(shè)計(jì)（論文）專(zhuān)用紙 15 圖 21 遺傳算法流程圖 一個(gè)簡(jiǎn)單的遺傳算法被 Goldberg 用來(lái)進(jìn)行輪廓描述并用來(lái)舉例說(shuō)明遺傳算法的基本組成。 (5)全局最優(yōu)收斂 (Convergence to the global opt imum)當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，則算法的迭代過(guò)程收斂，算法結(jié)束。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無(wú)法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。 單靠變異不能在求解中得到好處。例如有個(gè)體 S=101011。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把 1變?yōu)?0，把 0變?yōu)?1。 例如有個(gè)體： S1=100101； S2=010111 選擇它們的左邊 3位進(jìn)行交叉操作，則有：S1=010101； S2=l00111 一般而言，交叉概率取值為 。這個(gè)過(guò)程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。 (3)交叉：對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率 pc。 這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。 a) 適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。給出目標(biāo)函數(shù) f，則 f(bi)稱(chēng)為個(gè) 體 bi的適應(yīng)度。在選擇時(shí)，以適應(yīng)度為選擇原則。問(wèn)題的最優(yōu)解將通過(guò)這些初始假設(shè)解進(jìn)化而求出。一般取 n=30概括地講，遺傳算法求解組合優(yōu)化問(wèn)題的具體步驟可描述如下： (1)初始化：選擇一個(gè)群體，即選擇一個(gè)串或個(gè)體的集合 bi， i=l， 2，? n。這樣在最后滿(mǎn)足收斂條件后的種群最優(yōu)個(gè)體就是問(wèn)題的近似最優(yōu)解。每個(gè)個(gè)體具有其自的特征，我們根據(jù)這些個(gè)體的不同的特征來(lái)確定其存活到下一代的可能性高低，按照優(yōu)勝劣汰的法則，我們由父代來(lái)產(chǎn)生子代，如此來(lái)繁衍。在解決具體問(wèn)題時(shí)先大致 確定問(wèn)題的潛在解的一個(gè)集合，這個(gè)集合就是算法的初始種群。 遺傳算法的原理可以簡(jiǎn)要給出如下：選擇初始值，確定合適的值，完成選擇；進(jìn)行交叉，變異；重復(fù)直到得到最優(yōu)解這里所指的某種結(jié)束準(zhǔn)則一般是指?jìng)€(gè)體的適應(yīng)度達(dá)到給定的閥值；或者個(gè)體的適應(yīng)度的變化率為零。 c) 變異 (Mutation)：這是在選中的個(gè)體中，對(duì)個(gè)體中的某些基因執(zhí)行異向轉(zhuǎn)化。由于在選擇用于繁殖下一代的個(gè)體時(shí)，是根據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度而決定其繁殖量的，故而有時(shí)也稱(chēng)為非均勻再生 (differential reproduction)。這些選中的個(gè)體用于繁殖下一代。在每個(gè)串中，每個(gè)二進(jìn)制位就是個(gè)體染色體的基因。很明顯，遺傳算法是一種最優(yōu)化方法，它通過(guò)進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個(gè)特定的串 bi 處，即求出最優(yōu)解。我們無(wú)法據(jù)此推斷算法的收斂性； c) 模式定理沒(méi)有解決算法設(shè)計(jì)中控制參數(shù)選取等問(wèn)題。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長(zhǎng)，從而滿(mǎn) 足求最優(yōu)解的必要條件，即遺傳算法存在找到全局最優(yōu)解的可能性；而積木塊假設(shè)指出，遺傳算法具備尋找全局最優(yōu)解的能力，即積木塊在遺傳算子的作用下，能生成低階、短距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。 滿(mǎn)足這個(gè)假設(shè)的條件比較簡(jiǎn)單，包括兩方面： a) 表現(xiàn)型相近的個(gè)體，其基因型相近； b) 遺傳因子間相關(guān)性低。 定義 積木塊 (building block)在模式定理中所指的具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng) 度的模式被定義為積木塊。模式定理可以用數(shù)學(xué)形式表示為： ( , 1 ) ( , ) ( ( ) / ) [ 1 ( ( ) / ( 1 ) ) ( ) ]cmm H t m H t f H f P H l o H P?? ? ? ? ? ? ? ? ? 式中， m（ H,t+1）辨識(shí)在 t+1 代種群中存在模式 H 的個(gè)數(shù) f(H)表示在 t代種群包含模式 H的個(gè)體平均適應(yīng)度 ｌ表示個(gè)體長(zhǎng)度 Pc 表示交叉概率 Pm 表示