【正文】 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]。將種群規(guī)模設置為 50，最大迭代次數(shù)為 500，交叉概率為 ，變異概率為 。從圖中可 以看出最優(yōu)值仿真曲線和平均值的仿真曲線波動不大，表明遺傳算法的尋優(yōu)能力比較好。 表 22 不同種群規(guī)模求解算例 1 的結果 種群規(guī)模 總價值 總體積 100 3094 996 200 3095 996 400 3103 1000 500 3103 1000 從上表可以看出，隨著種群規(guī)模的增大總價值和總體積也隨之增大，并且在種群 設計（論文）專用紙 23 規(guī)模為 400 的時候已命中最優(yōu)解 3103，同時在種群規(guī)模為 500 時也命中最優(yōu)解，說明種群規(guī)模增大時遺傳算法在求解背包問題的時候選擇范圍更廣，更易命中最優(yōu)解。 （ 3） 最大迭代次數(shù)對算法性能的影響 設置變異概率為 、交叉概率為 、染色體長度為 50、迭代次數(shù)分別為 100、200、 300、 500、 對算例 1運行 20 次，所得結果如表 24所示 表 24 不同迭代次數(shù)求解算例 1的結果 最大迭代次數(shù) 總價值 總體積 100 3068 999 200 3084 1000 300 3091 1000 500 3103 1000 設計（論文）專用紙 24 從表 24 可以看出隨著迭代次數(shù)的增加總價值和總體積也隨之增加并且在迭代500 次時命中最優(yōu)解。 Pi 與 C 的數(shù)值由以下公式得出。 表 26 算例 2循環(huán) 20的次結果 種群規(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
。 當物品數(shù)量為 50 時，循環(huán) 20 次的結果如表 25和仿真圖分別如圖 24,圖 25,圖 26 所示。 綜上所述種群規(guī)模 、交叉概率以及迭代次數(shù)的設置對于遺傳算法在求解 01背包問題時對于命中最優(yōu)解的影響是 非常明 的，通過以上實驗的探究我可以看到當交叉 概率為 ，迭代次數(shù)為 500 時都命中了最優(yōu)解 3103，那么我可以利用這兩個參數(shù)對算例 2進行測試。 表 23 不同交叉概率求解算例 1的結果 交叉概率 總價值 總體積 3091 998 3095 1000 3103 1000 3103 1000 3103 1000 3103 1000 3103 1000 從表 23 可以看出當交叉概率增大時與之對應的總值和 總體積 也隨之增加并在交叉概率為 時命中最優(yōu)解，隨著交叉概率增加大依然保持命中最優(yōu)解。 B 不同參數(shù)對算法性能的影響 （ 1） 種群規(guī)模對算法性能影響 設置交叉概率為 ，變異概率為 ，最大迭代次數(shù)為 500，染色體長度為 50。 表 21 算例 1求解結果 循環(huán)次數(shù) 迭代次數(shù) 最優(yōu)值 最差值 平均值 命中最優(yōu)解概率 20 500 3103 1429 45% 從表 21可以看出在程序運行 20次中命中了 9次最優(yōu)解 3103，平均值為 ，最優(yōu)值與最差值的差值為 1674，說明遺傳算法求解背包問題不易陷入局部最優(yōu)。 C=1000 其中， value 表示背包中物品的價值， weight 表示相應物品的重量， C 表示 背包的最大容量。對各個染色體計算其適應度值，淘汰適應度值最低的，復制適應度值最高的，用最高的代替最低的，這樣完成選擇；再隨機產生交叉點及相互交叉的染色體進行交叉，計算交叉后的染色體是否符合要求，即裝入背包的物品的總體積小于背包容量，若不符合則交叉失敗，重新交叉，達到交叉最多次數(shù)未交叉成功則退出；交叉完成后就進行變異，根據(jù)變異概率隨機選擇變異的染色體，隨機產生變異點進行變異，變異后也需要計算染色體是否符合要求，若不符合則變異失敗，重新變異，達到變異最多次數(shù)未變異成功則退出。 temp=samp_arr(max_index, :)。 %變異操作，直接針對整個樣本集操作 muta_arr=( rand(POP_NUM, LEN) P_MUTA )。位點變異比較簡單，針對本問題來說，就是把染色體的變異位 1變?yōu)?0， 0變?yōu)?1就可以了，其它位都保持不變。 %交叉點位置 ,[1, POP_NUM1] temp_cross=samp_arr(cross_index(i), cross_pos:end)。 cross_index(temp_pos)=cross_index(i)。 % 交叉操作 cross_index=1:POP_NUM。 end winner_index(i)=index。 %輪盤， rotary table %生成輪盤，類似于概率分布 For i=2:POP_NUM rtable(i)=rtable(i1)+rtable(i)。 end end end end 設計（論文）專用紙 18 (4)選擇操作：根據(jù)選擇概率選擇染色體，將上述的個體作為第 1 代，這里采用以正比于適應度的賭輪隨機選 擇方式，每個體適應度值為 fi，則 i 被選中的概率 psi為：1/nsi i iip f f?? ?；；對于初始化后的種群，先計算出每條染色體的適應度值，再計算出其被選擇的概率，將它們進行比較，把選擇概率最小的一條染色體淘汰掉，并把選擇概率最大的一條染色體進行復制，用這條復制的來替代淘汰的染色體位置。)。 rate=val./vol。這個問題解的總組合數(shù)有 2 個，其數(shù)學模型表示為：1niii XW C? ??時，使得1niii XP??大， Xi=1 或 0（ i=1， 2，?， n)。如果 M= N=IO，那么初始化后的種群可以看作一個 5 行 10 列的矩陣。每產生一個染色體，就對它進行一次檢驗，如果不滿足約束條件，則拒絕接受。例如 x={0，1， 0， 1， 0， 0， 1)表示第 7 這三個物品被選入背包中。運用簡單遺傳算法求解背包問題時，若問題的規(guī)模不大時能夠得到最優(yōu)解或近似最優(yōu)解。 (5)全局最優(yōu)收斂 (Convergence to the global opt imum)當最優(yōu)個體的適應度達到給定的閥值，或者最優(yōu)個體的適應度和群體適應度不再上升時，則算法的迭代過程收斂，算法結束。 單靠變異不能在求解中得到好處。在變異時，對執(zhí)行變異的串的對應位求反，即把 1變?yōu)?0，把 0變?yōu)?1。這個過程反映了隨機信息交換；目的在于產生新的基因組合，也即產生新的個體。 這樣，就產生了對環(huán)境適應能力較強的后代。給出目標函數(shù) f，則 f(bi)稱為個 體 bi的適應度。問題的最優(yōu)解將通過這些初始假設解進化而求出。概括地講，遺傳算法求解組合優(yōu)化問題的具體步驟可描述如下： (1)初始化：選擇一個群體，即選擇一個串或個體的集合 bi， i=l， 2，? n。每個個體具有其自的特征，我們根據(jù)這些個體的不同的特征來確定其存活到下一代的可能性高低，按照優(yōu)勝劣汰的法則，我們由父代來產生子代，如此來繁衍。 遺傳算法的原理可以簡要給出如下：選擇初始值，確定合適的值，完成選擇；進行交叉，變異；重復直到得到最優(yōu)解這里所指的某種結束準則一般是指個體的適應度達到給定的閥值；或者個體的適應度的變化率為零。由于在選擇用于繁殖下一代的個體時，是根據(jù)個體對環(huán)境的適應度而決定其繁殖量的，故而有時也稱為非均勻再生 (differential reproduction)。在每個串中，每個二進制位就是個體染色體的基因。我們無法據(jù)此推斷算法的收斂性； c) 模式定理沒有解決算法設計中控制參數(shù)選取等問題。 滿足這個假設的條件比較簡單，包括兩方面： a) 表現(xiàn)型相近的個體，其基因型相近； b) 遺傳因子間相關性低。模式定理可以用數(shù)學形式表示為： ( , 1 ) ( , ) ( ( ) / ) [ 1 ( ( ) / ( 1 ) ) ( ) ]cmm H t m H t f H f P H l o H P?? ? ? ? ? ? ? ? ? 式中， m（ H,t+1）辨識在 t+1 代種群中存在模式 H 的個數(shù) f(H)表示在 t代種群包含模式 H的個體平均適應度 ｌ表示個體長度 Pc 表示交叉概率 Pm 表示變異概率 δ (H) 表示模式 H的定義距； o（ H）表示模式 H的階。 設計（論文）專用紙 11 定義 定義距 (defining length)模式 H 中的第一個確定位置和最后一個確定位置之間的距離稱為該模式的定義距，記作δ (H)。因此模式也可解釋為相同的構形。遺傳算法的 執(zhí)行過程包括了大量的隨機性操作，因此有必要對其數(shù)學機理進行分析。 d) 運行參數(shù)：群體大小 M；遺傳運算的終止 進化代數(shù) T 乃一般取為 100500；交叉概率 Pc，一般取為 ；變異概率 Pm，一般取為 。這個群體不斷的經(jīng)過遺傳和進化操作，并 且每次都按照優(yōu)勝劣汰的規(guī)則將適應度較高的個體更多的遺傳到下一代，這樣最終在種群中將會得到一個優(yōu)良的個體 X，它所對應的的表現(xiàn)型 X 將達到或接近問題的最優(yōu)解 X*。在一系列研究工作基礎上。 d. 在 matlab 環(huán)境中進行 GUI 界面設計， 運行界面中遺傳算法主要的參數(shù)可通過手動輸入自行修改，同時通過 GUI 界面可以直接觀察到仿真曲線的變化情況。 本文主要工作 a. 介紹了 01 背包問題的概念，接著論述求解該問題的各種傳統(tǒng)算法，并對 01背包問題進行數(shù)學描述。例如：利用 GA的機器學習來調整人工神經(jīng)網(wǎng)絡的權值等；利用 GA學習模糊控制的奴隸度函數(shù)以改進模糊控制系統(tǒng)的性能。 。學者構造了各種復雜的測試函數(shù)，既有連續(xù)函數(shù)也有離散函數(shù)，有高維的也有低維的，有凹的也有凸的，有多峰的也有單峰的，遺傳算法較其他優(yōu)化方法便于得到較好的結果。隨著組合優(yōu)化問題規(guī)模的增加，其搜索空間也急劇增加，在計算機上用窮舉法不可能求出其最優(yōu)解，而遺傳算法可以在此類問題上尋求問題的滿意解。 可以對群體按一定的方式進行分組，分組后各組的個體遺傳進化過程可以在不同的處理機上相互獨立地進行，在適當?shù)臅r候，各處理機之間相互交換信息。 。 個體適應度的評價 或計算在遺傳算法的運行過程中所占用的運行時間比較長。由于遺傳算法與傳統(tǒng)優(yōu)化方法的互補性，混合遺傳算法通常比單一算法優(yōu)越。 設計（論文）專用紙 6 遺傳算法分類 （ 1） 混合遺傳算法 單用簡單的遺傳算法在許多情況下不是十分有效，容易產生早熟現(xiàn)象以及局部尋優(yōu)能力較差等問題，于是提出了多種混 合算法。這就是一個強烈的過濾過程，并且是一個并行濾波機制。遺產算法只需自適應值和串編碼等通用信息，故幾乎可以處理任何問題。傳統(tǒng)優(yōu)化算法是從單個初值迭代求最優(yōu)解的，容易誤入局部最優(yōu)解。 工科數(shù)學教育也應有所調整 ,以適應高新技術發(fā)展的需要 。 理論研究與實際應用不夠緊密 ,阻礙了我國高新技術的迅速發(fā)展 ,幾乎已經(jīng)成為頑癥 。 這一思想在 90 年代初逐步形成 ,而由模糊集論的創(chuàng)始人 ,美國 Zadeh LA在 1993 年于漢城召開的國際模糊系統(tǒng)協(xié)會 ( IFSA )第五屆世界會議首先明確提出隨后在許多有關的國際學 術會議上得到充分體現(xiàn)。 自然 ,不論從理論還是應用的角度看 ,最緊迫的應是關于算法收斂性問題的研究 ,特別是過早收斂的防止 。 今 后幾年 ,可以預期 ,拓廣更加多樣的應用領域 ,其中包括各種 遺傳算法 程序設計環(huán)境的 開發(fā)仍將是遺傳算法發(fā)展的主流 。在國內，武漢大學成立了一個軟件工程國家重點實驗室。在此之后世界范圍內掀起了關于遺傳算法研究與 設計（論文）專用紙 4 應用的高潮。 基于 生物進化理論，從 20 世紀 60年代起科學家們就嘗試用計算的方法模擬生物遺傳和選擇進化過程。 遺傳算法的研究現(xiàn)狀與發(fā)展趨勢 查克斯其本質是一種高效、并行、全局搜索的方法，它 能在搜索過程中自動獲取和積累有關搜索空間的知識，并自適應地控制搜索過程以求得最優(yōu)的方法。 本文將對遺傳算法做進一步研究并結合應用于背包問題的求解，并通過實驗證明遺傳算法對求解背包問題是比較有效的。與以上幾種算法相比遺傳算法具有一定的優(yōu)勢。首先，很多算法的計算量都很大，迭代的時間很長。上世紀九十年代以后，隨著生物仿生技術和網(wǎng)絡技術的飛速發(fā)展 ，各種模擬生物物理規(guī)律的并行近似算法不斷涌現(xiàn)，例如：遺傳算法已經(jīng)在 01背包問題上得到了較好的應用，螞蟻算法等仿生算法也很好的應用 設計（論文）