【正文】 5iipw?? （ 21） 112 n iicw?? ? （ 22） 設(shè)置交叉概率 Pc=，迭代次數(shù)為 500，變異概率為 當(dāng)物品總數(shù)分別為50、 100、 150 時 ，對算例 2 運行 20 次，觀察種群規(guī)模分別為 50、 100、 200 時的 結(jié)果 。 說明種群演化代數(shù)增加時，求得的解會更接近或者直接命中最優(yōu)解。 （ 2） 交叉概率對算法性能的影響 設(shè)置變異概率為 、最大迭代次數(shù)為 500、染色體長度為 50、交叉概率分別為、 、 、 、 、 、 時對算例 1 進行求解，所得結(jié)果如表 23。而最差值波動相對較大一些，并且從仿真曲線圖中可看到最優(yōu)值與最差值之間的差距較大，說明種群具有一定的多樣性。程序循環(huán)運行 20次，結(jié)果如下表 21，仿真圖如22。 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 ]。裝入背包的物品用 1 表示，未裝入的用 0表示，一種裝入方法用一個染色體表示，總共產(chǎn)生的染色體個數(shù)等于群體規(guī)模。 %找到最后一代中的最佳樣本 [max_val, max_index]= max(fit_arr)。對種群依次進行選擇、交叉、變異后就檢驗得到的新個體，當(dāng)某代得到的結(jié)果滿足要求或 當(dāng)前代數(shù)等于結(jié)束代數(shù)時算法結(jié)束得到結(jié)果 ，否則重復(fù)選擇、交叉、變異操作，直到得到滿意的結(jié)果為止。 end end (6)變異操 作：染色體變異采用位點變異的方式。 for i=1:2:POP_NUM %相鄰兩個進行交叉 %隨機得到一個數(shù)，小于交叉概率的話，進行交叉 if rand(1) P_CROSS cross_pos=unidrnd(POP_NUM1 )。 temp_val=cross_index(temp_pos)。這里嘗試用“與／或 交叉方法，這一交叉方法使子代繼承了雙親的同型基因，對于雙親的雜型基因，“與／或 交叉方法采取了兩種不同的“支配 方式，“與”運算是一種 0支配 l的方式，而“或 運算是一種 1支配 0的方式，采用“與／或”交叉策略能使優(yōu)化過程更加迅速的達到全局最優(yōu)解，獲得全局最優(yōu)解的時間僅為“一點交叉 策略的 1／ 9到 1／ 3。 while p rtable(index) index=index+1。 rtable=fit_arr./fit_sum。 temp_sum(i)=temp_sum(i) vol(index(j))。ascend39。 適應(yīng)度計算程序如下： temp_sum=vol*samp_arr39?？紤] n個物件的選擇與否，背包內(nèi)物件的總體積1niii XW??，物件總價值為1niii XP??，如何決定變量 Xi (i=l， 2，?，n)的值 (即確定一個物件組合 )使背包內(nèi)物件總價值為最大。所以，初始化后的種群應(yīng)該是一個 M*N 的二維矩陣。這個遺傳編碼也需要隨機地產(chǎn)生，隨機地產(chǎn)生數(shù)字 0或 l，就構(gòu)成一個染色體串，也 就是一個遺傳編碼。 (2)產(chǎn)生遺傳編碼：采用二進制 n 維矢量解 X 作為解空間參數(shù)的遺傳編碼，串 T的長度等于 n， xi=1表示該物件裝入背包， xi=0表示該物件沒有被裝入背包。 T 代種群用變量 P(t)表示，初始種群 P(o)是隨機設(shè)計的，簡單遺傳算法的偽代碼描述如下： 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 隨機選擇種群數(shù) 計算適應(yīng)度 變異 交叉 停止 滿足條件？ 是 否 設(shè)計（論文）專用紙 16 使用遺傳算法求解 01背包問題 遺傳算法己經(jīng)在背包問題的求解上取得了一定的成果。也就是說，變異增加了全局優(yōu)化的特質(zhì)。對其的第 l、 4位置的基因進行變異，則有 S1=001111。 (4)變異：根據(jù)生物遺傳中基因變異的原理，以變異概率 Pm 對某些個體的某些位執(zhí)行變異。在選中的位置實行交換。 設(shè)計（論文）專用紙 14 b) 適應(yīng)度較小的個體，繁殖下一代的數(shù)目較少；甚至被淘汰。適應(yīng)度準則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。通常以隨機方法 產(chǎn)生串或個體的集合 bi， i=1， 2，? n。 遺傳算法的實現(xiàn)過程主要包括編碼、產(chǎn)生群體、計算適應(yīng)度、復(fù)制、交換、變異等操作。種群由計算機生成 (一般是隨機生成 )的一定數(shù)目的個體組成，個體就是潛在解的計算機編碼，那么我們最后要求的解就由這些初始生成的個體進化而來的。在串 bi中，如果某位基因為 l，產(chǎn)生變異時就是把它變成 0；反之亦然。故有時也稱這一操作為再生 (Reproduction)。 長度為 L的 n個二進制串 bi(i=1， 2，?， n)組成了遺傳算法的初解群，也稱為初始群體。 雖然模式定理在一定意義上解決了基本遺傳算法的有效性，但它仍有以下 的缺點： a) 模式定理只對二進制編碼適用，對其他編碼方案尚沒有相應(yīng)的結(jié)論成立； b) 模式定理只給出了在下世代包含模式 H 的個體數(shù)的下限。 積木塊假設(shè) (Building block hypothesis)[18]低階、短定義距、高平均適應(yīng)度的基因塊 通過選擇、交叉和變異等遺傳算子的作用，能夠互相拼接在一起，形成高階、長定義距、高平均適應(yīng)度的模式，最終接近全局最優(yōu)解。 模式定理在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。 模式階用來反映不同模式問確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本個數(shù)就越少。 定義 模式 (schema)是一個描述字符串集的模板，該字符串集中的串的某些位置上存在相似性。 遺傳算法的數(shù)學(xué)基礎(chǔ) 遺傳算法在機理方面具有搜索過程和優(yōu)化機制等屬性，數(shù)學(xué)方面的性質(zhì)可通過模式定理和積木塊假設(shè)等分析加以討論， Markov 鏈也是分析遺傳算法的一個有效工具。 c) 遺傳算子：使用比例選擇算子、單點交叉算子、基本位變異算子或均勻變異算子。與生物一代一代的自然進化過程相似，遺傳算法也是一個反復(fù)迭代的過程，第 t 代群體記作 P（ t）經(jīng)過一代遺傳和進化之后，得到第 t+1 代群體，它們是由多個個體組成的集合記作 P（ t+1）。 70 年代 Dc Jong 基于遺傳算法的思想在計算機上進行了大量純數(shù)值函數(shù)優(yōu)化計算實驗 [14]。 c. 應(yīng)用遺傳算法解決 01背包問題，通過設(shè)置不同參數(shù)探究遺傳算法求解背包問題的可行性并將算法在 Matlab 仿真平臺上進行實現(xiàn)。數(shù)據(jù)挖掘問題可以看做是搜索問題，把數(shù)據(jù)庫看作是搜索空間，而把挖掘算法看作搜索策略，這樣就可以使用遺傳算法對數(shù)據(jù)庫中的數(shù)據(jù)進行搜索，對于隨機產(chǎn)生的一組規(guī)則進行進化，直至數(shù)據(jù)庫能被該規(guī)則覆蓋，進而挖掘出大型數(shù)據(jù)庫中的隱含的規(guī)則。目前基于 GA 的機器學(xué)習(xí)在很多領(lǐng)域得到了應(yīng)用。目前 GA 進行系統(tǒng)辨識、模糊控制器設(shè)計、航空系統(tǒng)的優(yōu)化等方面取得了一定的成就。函數(shù)優(yōu)化是 GA的經(jīng)典應(yīng)用領(lǐng)域。 。 。即不同個體的適應(yīng)度計算可以在不同的處理機上同時進行。 。在混合遺傳算法中，運用啟發(fā)式方法作局部優(yōu)化，采用遺傳算法作全局最優(yōu)點的探索。 這說明遺傳算法是采用隨機 方法進行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串。 由于遺傳算法使用時應(yīng)值這一信息進行搜索，并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息。 這是遺傳算法與傳統(tǒng)算法的極大區(qū)別。 國家組建的工程研究中心應(yīng)該在這方面發(fā)揮更大的作用 。 就遺傳算法本身的研究而言 ,應(yīng)該說 ,我國起步較晚 ,近幾年才陸續(xù)看到一些介紹性的文章、不多于兩三部的專著以及初步的研究報告 ，與 國外工作比較 ,一個顯著區(qū)別是 ,國內(nèi)工作多只停留在論文這一層次 ,幾乎沒有看到具體實際應(yīng)用 ,與研究成果商品化的差距就更遠 。眾所周知 ,FL 有較強的知識表達能力 ,NN 的長處在于自學(xué)習(xí) ,它們與遺傳算法相結(jié)合形成新的集成化技術(shù) ,即所謂的 混合智能系統(tǒng) (Hybrid Intellectual System )。例如 : 控制參數(shù)的選擇 ； 交換和突變這兩類最重要的算子的確切作用 ； 并行遺傳算法和分布式遺傳算法的研究 ； 其 他類型生物機制的模仿 ,如免疫、 病毒、寄生等 ,以豐富遺傳算法的內(nèi)容 ,等等 。 認識到這一點 ,遺傳算法的奠基人之一 ,Goldsberg D 戲言 :“ 已不再需要水晶球 ” 。遺傳算法由于能有效解決 NP類型的組合優(yōu)化問題和多目標(biāo)函數(shù)優(yōu)化問題，得到很多學(xué)科的高度重視。 1989 年 Goldberg 博士出版本了專著《 Geic algorithm in search，optimization and machine learning 》 [6]，這是第一本關(guān)于遺傳算法的教科書，全面論述了遺傳算法的原理與應(yīng)用，并與實例結(jié)合給出了大量的可用的源程序，使技術(shù)專家可以借鑒參考并進行實際應(yīng)用。遺 傳和變異是決定生物進化的內(nèi)在因素，推動生物的進化和發(fā)展。這個過程導(dǎo)致種群中個體的進化，得到新的個體比原來的個體更能適應(yīng)環(huán)境，就像自然界中的改造一樣。 遺傳算法是模仿自然界生物進化機制發(fā)展起來的隨機全局搜索和優(yōu)化方法，它借鑒了達爾文的進化論和孟德爾的遺傳學(xué)說。 最后， 遺傳算法對于各種特殊問題可以提供極大的靈活性來混合構(gòu)造領(lǐng)域獨立的啟發(fā)式，從而保證算法的有效性。第三，蟻群算法可以得到近似最優(yōu)解 ,但是當(dāng)數(shù)據(jù)規(guī)模較大的時候收斂太慢；第四，新出現(xiàn)的知識進化算法和 DNA 計算等方法也可以有效的解決背包問題，但這些理論還不太完善，背包問題屬于組合最優(yōu)化問題，在嚴格意義上求取最優(yōu)解非常困難，所以研究高速近似的算法是一個重要的發(fā)展方向。 前人已經(jīng) 對背包問題做了一些深入的研究，得到了一些經(jīng)典的方法，有些方法對于解決背包問題雖然能得到不錯的結(jié)果，但是也存在著很多不足之處。隨后 balas 和 zemel 提出了背包問題的“核”思想使得背包問題的研究獲得了較大的發(fā)展。此外背包問題還常常作為其他復(fù)雜組合優(yōu)化問題的一個子問題出現(xiàn)，對于由簡單結(jié)構(gòu)組合而成的復(fù)雜結(jié)構(gòu)體而言，對簡單問題的深入探索往往可以使復(fù)雜的問題迎刃而解。物品的重量是已知的，所有可能的物品也是已知的，但是背包中的物品是保密的，此外還附加了背包的重量限制。接著通過設(shè)置不同的種群規(guī)模、交叉概率和迭代次數(shù)來探討這些算子對于遺傳算法求解背包問題性能的影響。它是由 美國 的 1975年首先提出，其主要特點是直接對結(jié)構(gòu)對象進行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。 Design a graphical user interface (GUI), realize the input parameters and the simulation results show Key Words： 01 knapsack problem； Geic algorithm； Popsize； Matlab； GUI 設(shè)計（論文）專用紙 第 III 頁 目錄 摘要 ............................................................................................................................................................................ I ABSTRACT ............................................................................................................................................................ II 目錄 ........................................................................................................................................................................