第一篇：基于遺傳算法的優(yōu)化設計論文

1數(shù)學模型的建立

影響抄板落料特性的主要因素有:抄板的幾何尺寸a和b、圓筒半徑Ｒ、圓筒的轉速n、抄板安裝角β以及折彎抄板間的夾角θ等［4，9］。在不同的參數(shù)a、β、θ下，抄板的安裝會出現(xiàn)如圖1所示的情況。圖1描述了不同參數(shù)組合下抄板的落料特性橫截面示意圖。其中，圖1(a)與圖1(b)、圖1(c)、圖1(d)的區(qū)別在于其安裝角為鈍角。當安裝角不為鈍角且OB與OC的夾角σ不小于OD與OC夾角ψ時(即σ≥ψ)，會出現(xiàn)圖1(b)所示的安裝情況;當σ＜ψ時，又會出現(xiàn)圖1(c)與圖1(d)所示的情況，而兩者區(qū)別在于，η+θ是否超過180°，若不超過，則為圖1(c)情況，反之則為圖1(d)情況。其中，點A為抄板上物料表面與筒壁的接觸點或為物料表面與抄板橫向長度b邊的交點;點B為抄板的頂點;點C為抄板折彎點;點D為抄板邊與筒壁的交點;點E為OB連線與圓筒內壁面的交點;點F為OC連線與圓筒內壁面的交點。

1．1動力學休止角(γ)［4，10］抄板上的物料表面在初始狀態(tài)時保持穩(wěn)定，直到物料表面與水平面的夾角大于物料的休止角(最大穩(wěn)定角)時才發(fā)生落料情況。隨著轉筒的轉動，抄板上物料的坡度會一直發(fā)生改變。當物料的坡度大于最大穩(wěn)定角時，物料開始掉落。此時，由于物料的下落，物料表面重新達到最大穩(wěn)定角開始停止掉落。然而，抄板一直隨著轉筒轉動，使得抄板內物料的坡度一直發(fā)生改變，物料坡度又超過最大休止角。這個過程一直持續(xù)到抄板轉動到一定位置(即抄板位置處于最大落料角δL時)，此時抄板內的物料落空。通常，在計算抄板持有量時，會采用動力學休止角來作為物料發(fā)生掉落的依據，即抄板內的物料坡度超過γ時，物料開始掉落。該角主要與抄板在滾筒中的位置δ、動摩擦因數(shù)μ和弗勞德數(shù)Fr等有關。

1．2抄板持有量的計算

隨著抄板的轉動，一般可以將落料過程劃分為3部分(Ｒ－1，Ｒ－2，Ｒ－3)，如圖1(a)所示。在轉動過程中，當抄板轉角δ超過動力學休止角γ時，落料過程從Ｒ－1區(qū)域轉變到Ｒ－2區(qū)域，在這兩個區(qū)域內，物料不僅受到抄板的作用還受到滾筒壁面的作用。當物料表面上的A點與D點重合時，從Ｒ－2區(qū)域轉變到Ｒ－3區(qū)域，在該區(qū)域內，物料僅受抄板作用［4］。然而，抄板情況為圖1(c)、圖1(d)時只會經歷Ｒ－1、Ｒ－3區(qū)域。因為在運轉過程中，抄板上物料的A點與D點重合時抄板的轉角不會超過動力學休止角γ，所以不會經歷Ｒ－2區(qū)域;但是，當物料的休止角足夠小時，由于物料表面只會與抄板接觸(即A點不會超出D點)，圖1(c)、圖1(d)的抄板落料過程只會經歷Ｒ－3區(qū)域。以下根據不同的區(qū)域建立了不同組合下抄板持料量的數(shù)學模型。

2研究結果與分析

2．1最大落料角結果分析

通過MatLab編制以上推導公式的計算程序，模擬計算了120種不同組合(β、θ、a不同)下抄板的最大落料角。其中，物料動摩擦因數(shù)為0．53［8］，轉筒干燥機半徑為300mm，且其抄板安裝角為10°、30°、50°、70°、90°、110°，抄板間夾角為90°、110°、130°、150°，抄板縱向長度a為30、45、60、75、90mm，橫向長度b為60mm。并且，根據Kelly和O＇Donnell通過驗證得出的公式(1)只適用于Fr小于0．4的情況［4］，此次模擬的轉筒干燥機角速度為0．84rad/s。表1給出了模擬結果中較為典型的數(shù)據。從模擬結果中可以得出，當a、θ不變時，δL隨著安裝角β的增大而增大;當a、β不變時，δL隨著θ的增大而減小。當抄板情況如圖1(a)、(b)、(c)時，且β、θ不變時，抄板最大落料角隨著長度a的增大而增大;而圖1(d)情況則反之，并且會出現(xiàn)最大落料角小于0°的情況，這是由于抄板無法抄起物料所導致的結果。另外，在圖1(d)情況下，抄板的最大落料角非常小，這會使得干燥器的效率很低。因此，在探討抄板優(yōu)化問題上，不考慮圖1(d)這種情況下的抄板。

2．2優(yōu)化目標與結果分析

水平直徑上均勻撒料雖好，但是物料應與熱氣均勻接觸，如果在路徑長的地方撒料多些，就可以使熱效率高些。又因為圓筒中心熱氣量比邊緣多以及在圓筒下半部分超出干燥圓的區(qū)域存在物料，所以落料均勻度考慮為物料在干燥圓橫截面積上撒料均勻。評判干燥圓橫截面積上落料均勻的具體方法如下:把干燥圓橫截面積劃分20個等分，以水平直徑為X軸，鉛垂直徑為Y軸，圓心O為原點，采用定積分方法求解每個劃分點的x坐標，每個劃分點的鉛垂線與干燥圓壁面(上半部分)有一個交點，連接圓心與每個點，可以得出每條連線與X軸的夾角δi(i=1～21，步長為1，δ1為0°)，如圖2所示。在合理的設計下，不僅希望落料過程中抄板在干燥圓面積上撒料越均勻越好，δL也應越接近180°越好。因此，優(yōu)化函數(shù)為最大落料角和抄板在干燥圓而積上落料的均方差。并且，根據國內外實際情況，抄板的安裝角一般為90°并且抄板間夾角一般不為銳角，由于機構的限制和不考慮圖1(d)的情況，在研究抄板優(yōu)化問題時只探討安裝角在70°～110°、抄板夾角在90°～130°以及抄板縱向長度在30～90mm之間的情況。其余參數(shù)同上。采用了線性加權和法來求解此多目標優(yōu)化結果。其中，f1為1/δL的最優(yōu)化值，f2為q的最優(yōu)化值;均方差q=(1n∑ni=1(qi－qa)2)12，每相鄰角度落料面積差qi=A(δi)－A(δi+1)，qa為面積差的平均值。當δL≤δi+1－δi2，n=i;反之則n=i+1，且δi+1=δL。s1、s2為權重系數(shù)，由于干燥器的效率主要與抄板的撒料均勻有關，但是如果落料角很小、撒料很均勻，干燥器效率也不高，綜合考慮下，取s1、s2分別為0．4、0．6。通過編寫MatLab程序，確定優(yōu)化函數(shù)，然后采用MatLab遺傳算法工具箱進行計算，設置相關參數(shù):最大代數(shù)為51，種群規(guī)模為20，交叉概率為0．2，選擇概率為0．5。運行算法并顯示結果，β、θ、a較優(yōu)結果分別為:1．844rad、1．571rad、51．609mm。

3結論

考慮到安裝角、抄板夾角以及抄板縱向長度的不同組合情況對抄板落料均勻度以及最大落料角的影響，建立了轉筒干燥器中任意參數(shù)組合下單個抄板持料量的數(shù)學模型。通過對不同組合下的抄板最大落料角進行計算從而得出結論:當抄板縱向長度、抄板夾角不變時，最大落料角隨著安裝角的增大而增大;當抄板縱向長度、安裝角不變時，最大落料角隨著抄板夾角的增大而減小。最后，根據優(yōu)化設計方法，以抄板最大落料角和抄板在干燥圓面積上落料的均方差為目標函數(shù)，采用遺傳算法得出了較優(yōu)的抄板參數(shù):安裝角為1．844rad、夾角為1．571rad、縱向長度為51．609mm。

第二篇：基于改進遺傳算法的配送路徑優(yōu)化方案

基于改進遺傳算法的配送路徑優(yōu)化方案

摘要:為了很好地解決物流車輛的線路優(yōu)化問題（簡稱VRP），借鑒DNA算法局部尋優(yōu)能力強的優(yōu)點，提出新編碼方法，以及車輛的行使路線的新的測序方式，很好地解決遺傳算法的早熟、局部尋優(yōu)能力差的問題。通過測試，發(fā)現(xiàn)交替使用遺傳算法和DNA算法進行全局尋優(yōu)和局部尋優(yōu)可以相對較準確、快速的實現(xiàn)車輛線路的尋優(yōu)。

關鍵詞:遺傳算法；DNA算法；VRP

一、引言

物流被譽為經濟活動中的“未開發(fā)的黑大陸”、企業(yè)的“第三利潤源泉”。物流的目標在于以最小的費用滿足消費者的最大需求，而運輸?shù)馁M用占整個企業(yè)物流的40％左右。在運輸過程中，配送是其中一個重要的直接與消費者相連接的環(huán)節(jié)，物流配送車輛的線路優(yōu)化問題，更是物流配送優(yōu)化中的關鍵環(huán)節(jié)，正確合理的安排車輛的配送線路，可以有效的減少車輛的空駛率，實現(xiàn)合理線路運輸，從而降低運輸成本，節(jié)約運輸時間，提高經濟效益，達到物流科學化管理。

二、遺傳算法與DNA算法

遺傳算法是一種基于自然選擇和自然遺傳機制的自適應的隨機搜索算法，它是一種有效的解決最優(yōu)化問題的方法。

遺傳算法求解工程實際最優(yōu)化問題的基本步驟是：首先對可行域中的個體進行編碼；然后在可行域中隨機挑選指定群體大小的一些個體組成作為進化起點的第一代群體，并計算每個個體的目標函數(shù)值，即該個體的適應度。利用選擇機制從群體中隨機挑選個體作為繁殖過程前的個體樣本。選擇機制保證適應度較高的個體能夠保留較多的樣本；而適應度較低的個體則保留較少的樣本，甚至被淘汰。在繁殖過程中，遺傳算法提供了交叉和變異兩種算法對挑選后的樣本進行交換和基因突變。交叉算法交換隨機挑選的兩個個體的某些位，變異算子則直接對一個個體中的隨機挑選的某一位進行突變。這樣通過選擇和繁殖就產生了下一代群體。重復上述選擇和繁殖過程，直到結束條件得到滿足為止。進化過程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問題所得到的最終結果。

遺傳算法是一種自適應隨機搜索方法,具有極強的并行機制，在解決整體的搜索問題時，具有很強的魯棒性和全局尋優(yōu)能力。但遺傳算法忽視了個體潛力的開發(fā)而只重視群體整體性能的提高。也就是說，遺傳算法能夠以較大的概率找到最優(yōu)區(qū)域而不是最優(yōu)點。因此遺傳算法在應用中也有一些不盡人意的地方，主要表現(xiàn)在算法收斂慢、效率低、容易早熟、局部尋優(yōu)能力差等。

三、基于DNA算法對VRP的局部尋優(yōu)

為追求DNA計算局部尋優(yōu)解的質量，我們在算法中加入基于啟發(fā)式知識的方向搜索策略。在網絡拓撲圖中，求解某幾個節(jié)點的最短回路，不需要對整個網絡進行問題求解，可以只提取出與節(jié)點緊密相關的節(jié)點與弧段構成子網絡，在子網絡中進行問題求解，降低問題規(guī)模，提高算法效率。即基于方向策略的限制搜索區(qū)域方法[7]，比如搜索從北京到沈陽的最短路徑，完全可以把南京、重慶等節(jié)點排除在搜索空間以外。該方法是一種有損局部尋優(yōu)算法，即排除了概率極小的子網絡外最優(yōu)路徑的可能。

在單條路徑尋優(yōu)中，以該點集作最小凸包，并以該凸包區(qū)域作適當擴充的緩沖區(qū)，落在緩沖區(qū)內的節(jié)點與弧段構成子網絡進行搜索計算。DNA計算模型即構建在該子網絡上進行，在保證有效搜索的基礎上多余的邊(輔助邊)盡量少。

我們這里的VRP可描述為：已知n 個代售點之間的相互費用大小(在編碼時用DNA片段的長度來表示)，現(xiàn)有一輛配送車必須訪遍n個代售點 ,最后又必須返回起始送貨點。如何安排車對這些代售點的有向行使路線，可使其行駛路線的總費用最少？以圖論術語來說，假設有一個圖G =(V,E,W)，其中，V是頂點集，E是邊集，W是頂點和邊的權值集，設D=(dij)是由頂點i和頂點j之間的距離所組成的距離矩陣，VRP就是求出一條通過所有頂點完成配送任務并且總費用最少的有向路徑。

（一）算法思想

依據上述思想，為了便于利用DNA計算，我們設計如下的求解該VRP的基本算法：

步驟1 ：搜索出所有閉合路徑。

步驟2 ：找出那些開始于0、結束也是0的固定頂點的閉路經，也就是說，保留那些經過0的固定頂點的閉路經。

步驟3：找出那些經過所有節(jié)點至少一次的閉合路徑，也就是說，保留0的所有廣義Euler閉跡。

步驟4：找出最短的廣義Euler閉跡，這就是我們所需的解。

步驟5：確定出配送車路線。

（二）VRP的DNA計算編碼以及實施

1、構建VRP的DNA計算編碼

先選取節(jié)點和弧段的基本寡聚核苷酸片斷，通常是根據相應權值的大小先同等放大為正整數(shù)，再分別求出節(jié)點和弧段的最小公倍數(shù)作為基本寡聚核苷酸長度的制定標準。

由于DNA編碼片斷的數(shù)目隨著路徑條數(shù)的增加呈指數(shù)增長，如此復雜的編碼也將成為DNA計算的技術瓶頸。本文采用基本寡聚核苷酸（K個）連接組合（單獨長為4的一條就能形成K4/2種組合，因此所需的寡聚核苷酸的種類大大減少）從很大程度上簡化這個過程，盡量減少DNA生物操作而更多地通過合理的編碼進行處理，從而大大減少了誤差的來源，這也是DNA計算研究的難以解決的問題之一。

2、VRP的DNA計算實施改進

步驟1：將以上各節(jié)點和弧段編碼好的核苷酸放在不同的試管中加入底物（具有各自相同同位素標記的DNA分子）、適量的引物（固定點所對應的寡聚核苷酸片斷的補鏈）、DNA聚合酶及緩沖液進行PCR擴增，這樣在聚合酶的作用下可以使得DNA鏈成指數(shù)增加，各自產生大量的寡聚核苷酸。

步驟2：將第一步中合成的各節(jié)點所對應的寡聚核苷酸片斷和邊所對應的寡聚核苷酸片斷混合在一起，加入緩沖液、DNA連接酶使之進行連接反應，這樣可以生成所有閉路徑，保留這些那些以0點開始和結束DNA鏈。

步驟３：將第2步的產物進行純化，然后對于純化后的產物進行分離。在分離過程中我們首先以表示邊權的寡聚核苷酸片斷的補鏈為模板構造探針，然后利用構造的探針對純化后的產物進行分離。與該探針雜交的DNA鏈中一定含有該寡聚核苷酸片斷，再將之加熱變性后保留這些DNA鏈。這些被保留的DNA鏈一定包含所有邊，也就是說我們找到了所有廣義Euler閉跡。

步驟４：對第３步的產物進行瓊脂糖漿凝膠電泳，跑在最前面的就是最優(yōu)的DNA鏈。

步驟５：將上述步驟的標記產物直接由相關儀器進行讀取，從而確定所求VRP的配送路線。

四、總結和展望

VRP是一種NP難題，本文結合遺傳算法和DNA算法的各自優(yōu)勢，交替進行全局尋優(yōu)和局部尋優(yōu)，從而具有良好的全局性和局部性，在通過對算法本身經過創(chuàng)新改進后對解決VRP等NP難題將有不錯的成效。

本文提出采用以基本單位的寡聚核苷酸相連接從而形成不同長度的片斷對節(jié)點和弧段進行編碼，從而避免在融合的過程當中形成發(fā)夾結構從而產偽解，而且也減少了生物操作（變性、退火等），使得到所需的DNA寡聚核苷酸源片斷變得更加容易。其次，本文提出新的測序方式，即事先就各自進行帶標記的核苷酸基片進行PCR復制，從而在檢測目標時只需通過強度檢驗就可以知道寡聚核苷酸片斷的連接順序，映射得到車輛的行使路線，減少了測序操作。

參考文獻：

[1] 丁立言,張鐸.物流管理[M].北京:清華大學出版社,1999:15-16

[2] 周康,同小軍,許進.路徑排序問題基于表面的DNA算法[J]華中科技大學學報:自然科學版,2005,33(8),100-103

第三篇：遺傳算法學習心得體會

遺傳算法

概念

遺傳算法是模仿自然界生物進化機制發(fā)展起來的隨機全局搜索和優(yōu)化方法，它借鑒了達爾文的進化論和孟德爾的遺傳學說。其本質是一種高效、并行、全局搜索的方法，它既能在搜索中自動獲取和積累有關空間知識，并自適應地控制搜索過程以求得最優(yōu)解遺傳算法操作使用適者生存的原則，在潛在的解決方案種群中逐次產生一個近視最優(yōu)方案。在遺傳算法的每一代中，根據個體在問題域中的適應度值和從自然遺傳學中借鑒來的再造方法進行個體選擇，產生一個新的近視解。這個過程導致種群中個體的進化，得到的新個體比原個體更適應環(huán)境，就像自然界中的改造一樣。

應用

遺傳算法在人工智能的眾多領域具有廣泛應用。例如，機器學習、聚類、控制（如煤氣管道控制）、規(guī)劃（如生產任務規(guī)劃）、設計（如通信網絡設計、布局設計）、調度（如作業(yè)車間調度、機器調度、運輸問題）、配置（機器配置、分配問題）、組合優(yōu)化（如tsp、背包問題）、函數(shù)的最大值以及圖像處理和信號處理等等。遺傳算法多用應與復雜函數(shù)的優(yōu)化問題中。原理

遺傳算法模擬了自然選擇和遺傳中發(fā)生的復制、交叉、和變異等現(xiàn)象，從任一初始種群出發(fā)，通過隨機選擇、交叉、變異操作，產生一群更適合環(huán)境的個體，使群體進行到搜索空間中越來越好的區(qū)域，這樣一代一代地不斷繁衍進化，最后收斂到一群最適合環(huán)境的個體求得問題的最優(yōu)解。

算法流程 1.編碼：解空間中的解數(shù)據x，作為作為遺傳算法的表現(xiàn)型形式。從表現(xiàn)

型到基本型的映射稱為編碼。遺傳算法在進行搜索之前先將解空間的解數(shù)據表示成遺傳空間的基本型串結構數(shù)據，這些串結構數(shù)據的不同的組合就構成了不同的點。2.初始種群的形成：隨機產生n個初始串數(shù)據，每個串數(shù)據稱為一個個體，n個串數(shù)據構成了一個群體。遺傳算法以這n個串結構作為初始點開始迭代。設置進化代數(shù)計數(shù)器t 0;設置最大進行代數(shù)t；隨機生成m個個體作為初始群體p(0)。3.適應度檢測：適應度就是借鑒生物個體對環(huán)境的適應程度,適應度函數(shù) 就是對問題中的個體對象所設計的表征其優(yōu)劣的一種測度。根據具體問題計算p(t)的適應度。

4.選擇：將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到

下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。

5.交叉：將交叉算子作用于群體。所謂交叉是指把兩個父代個體的部分結

構加以替換重組而生成新個體的操作。遺傳算法中起核心作用的就是交叉算子。6.變異：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。

群體p(t)經過選擇、交叉、變異運算之后得到下一代群體p(t+1)。7.終止條件判斷:若t<=t,則t=t+1，轉到第3步，否則以進化過程中所得

到的具有最大適應度個體作為最優(yōu)解輸出，終止計算。

遺傳算法流程圖如下圖所示： 遺傳算法

下幾種：適應度比例方法、隨機遍歷抽樣法、局部選擇法。

其中輪盤賭選擇法是最簡單也是最常用的選擇方法。在該方法中，各個個體的選擇概率和其適應度值成比例。設群體大小為n，其中個體i的適應度為，則i 被選擇的概率，為遺傳算法

2、交叉：在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。

交叉算子根據交叉率將種群中的兩個個體隨機地交換某些基因，能夠產生新的基因組合，期望將有益基因組合在一起。根據編碼表示方法的不同，可以有以下的算法： b)二進制交叉（binary valued crossover）1)單點交叉（single-point crossover）2)多點交叉（multiple-point crossover）3)均勻交叉（uniform crossover）4)洗牌交叉（shuffle crossover）5)縮小代理交叉（crossover with reduced surrogate）。

3、變異

變異算子的基本內容是對群體中的個體串的某些基因座上的基因值作變動。依據個體編碼表示方法的不同，可以有以下的算法： a)實值變異 b)二進制變異。

一般來說，變異算子操作的基本步驟如下： a)對群中所有個體以事先設定的編譯概率判斷是否進行變異 b)對進行變異的個體隨機選擇變異位進行變異。

例：簡單一元函數(shù)優(yōu)化

求下面函數(shù)的最大值：

f(x)=xsin(10*pi*x)+2.0,-1<=x<=2;程序： figure(1);fplot(variable.*sin(10*pi*variable)+2.0,[-1,2]);%畫出函數(shù)曲線 %定義遺傳算法參數(shù)

nind=40;%個體數(shù)目(number of individuals)maxgen=25;%最大遺傳代數(shù)(maximum number of generations)preci=20;%變量的二進制位數(shù)(precision of variables)ggap=0.9;%代溝(generation gap)trace=zeros(2, maxgen);%尋優(yōu)結果的初始值 fieldd=[20;-1;2;1;0;1;1];%區(qū)域描述器(build field descriptor)chrom=crtbp(nind, preci);%初始種群 gen=0;%代計數(shù)器 variable=bs2rv(chrom, fieldd);

%計算初始種群的十進制轉換

objv=variable.*sin(10*pi*variable)+2.0;%計算目標函數(shù)值 while gen

基本概念

遺傳算法(genetic algorithms, ga)是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。

它模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。ga的組成:（1）編碼（產生初始種群）

（2）適應度函數(shù)

（3）遺傳算子（選擇、交叉、變異）

（4）運行參數(shù)

編碼

基因在一定能夠意義上包含了它所代表的問題的解?；虻木幋a方式有很多，這也取決于要解決的問題本身。常見的編碼方式有：

（1）二進制編碼，基因用0或1表示（常用于解決01背包問題）如：基因a：00100011010(代表一個個體的染色體)（2）互換編碼（用于解決排序問題，如旅行商問題和調度問題）

如旅行商問題中，一串基因編碼用來表示遍歷的城市順序，如：234517986，表示九個城市中，先經過城市2，再經過城市3，依此類推。

（3）樹形編碼（用于遺傳規(guī)劃中的演化編程或者表示）

如,問題：給定了很多組輸入和輸出。請你為這些輸入輸出選擇一個函數(shù)，使得這個函數(shù)把每個輸入盡可能近地映射為輸出。

編碼方法：基因就是樹形結構中的一些函數(shù)。

（4）值編碼（二進制編碼不好用時，解決復雜的數(shù)值問題）

在值編碼中，每個基因就是一串取值。這些取值可以是與問題有關任何值：整數(shù)，實數(shù)，字符或者其他一些更復雜的東西。

適應度函數(shù)

遺傳算法對一個個體（解）的好壞用適應度函數(shù)值來評價，適應度函數(shù)值越大，解的質量越好。適應度函數(shù)是遺傳算法進化過程的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。

如tsp問題，遍歷各城市路徑之和越小越好，這樣可以用可能的最大路徑長度減去實際經過的路徑長度，作為該問題的適應度函數(shù)。

遺傳算子——選擇

遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。sga（基本遺傳算法）中采用輪盤賭選擇方法。

輪盤賭選擇又稱比例選擇算子，基本思想：各個個體被選中的概率與其適應度函數(shù)值大小成正比。設群體大小為n，個體i 的適應度為 fi，則個體i 被選中遺傳到下一代群體的概率為：

遺傳算子——交叉

所謂交叉運算，是指對兩個相互配對的染色體依據交叉概率按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算在ga中起關鍵作用，是產生新個體的主要方法。1.單交叉點法（用于二進制編碼）

選擇一個交叉點,子代在交叉點前面的基因從一個父代基因那里得到,后面的部分從另外一個父代基因那里得到。

如：交叉前：

00000|***00 11100|***01 交叉后：

00000|***01 11100|***00 2.雙交叉點法（用于二進制編碼）

選擇兩個交叉點,子代基因在兩個交叉點間部分來自一個父代基因,其余部分來自于另外一個父代基因.如：交叉前： 01 |0010| 11 11 |0111| 01 交叉后： 11 |0010| 01 01 |0111| 11 3.基于“ 與/或 ”交叉法（用于二進制編碼）對父代按位與”邏輯運算產生一子代a;按位”或”邏輯運算產生另一子代b。該交叉策略在解背包問題中效果較好.如：交叉前： 01001011 11011101 交叉后： 01001001 11011111 4.單交叉點法（用于互換編碼）

選擇一個交叉點，子代的從初始位置出發(fā)的部分從一個基因復制，然后在另一個基因中掃描，如果某個位點在子代中沒有，就把它添加進去。如：交叉前： 87213 | 09546 98356 | 71420 交叉后：

87213 | 95640 98356 | 72104 5.部分匹配交叉（pmx）法（用于互換編碼）先隨機產生兩個交叉點，定義這兩點間的區(qū)域為匹配區(qū)域，并用交換兩個父代的匹配區(qū)域。

父代a：872 | 130 | 9546 父代b：983 | 567 | 1420 變?yōu)椋? temp a: 872 | 567 | 9546 temp b: 983 | 130 | 1420 對于 temp a、temp ｂ中匹配區(qū)域以外出現(xiàn)的數(shù)碼重復，要依據匹配區(qū)域內的位置逐一進行替換。匹配關系：1<——>５ ３<——>６ ７<——>０ 子代ａ：802 | 567 | 9143 子代ｂ：986 | 130 | 5427 6.順序交叉法(ox)（用于互換編碼）

從父代ａ隨機選一個編碼子串，放到子代ａ的對應位置；子代ａ空余的位置從父代ｂ中按ｂ的順序選?。ㄅc己有編碼不重復）。同理可得子代ｂ。父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：

子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904 7.循環(huán)交叉（cx）法（用于互換編碼）cx同ox交叉都是從一個親代中取一些城市，而其它城市來自另外一個親代，但是二者不同之處在于：ox中來自第一個親代的編碼子串是隨機產生的，而cx卻不是，它是根據兩個雙親相應位置的編碼而確定的。

父代ａ：1 2 3 4 5 6 7 8 9 | | | | | 父代ａ：5 4 6 9 2 3 7 8 1 可得循環(huán)基因：1->5->2->4->9->1 用循環(huán)的基因構成子代ａ，順序與父代ａ一樣 1 2 4 5 9 用父代ｂ剩余的基因填滿子代ａ： 1 2 6 4 5 3 7 8 9 子代ｂ的編碼同理。（循環(huán)基因 5->1->9->4->2->5）

遺傳算子——變異 變異是指依據變異概率將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。ga中的變異運算是產生新個體的輔助方法，它決定了ga的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。

注：變異概率pm不能太小，這樣降低全局搜索能力；也不能太大，pm > 0.5，這時ga退化為隨機搜索。篇三：計算智能學習心得體會

計算智能學習心得體會

本學期我們水利水電專業(yè)開了“計算智能概論”這門課，有我們學院的金菊良教授給我們授課，據說這門課相當難理解，我們課下做了充分的準備，借了計算智能和人工智能相關方面的書籍，并提前了解了一點相關知識，我感覺看著有點先進，給我們以往學的課程有很大區(qū)別，是一種全新的概念和理論，里面的遺傳算法、模糊集理論、神經網絡更是聞所未聞，由于課前讀了一些書籍，我以為課堂上應該能容易理解一點，想不到課堂上聽著還是相當玄奧，遺傳算法還好一點，因為高中學過生物遺傳，遺傳算法還能理解一點。像模糊集理論神經網絡便不知所云了。雖然金老師講課生動形象，幽默風趣，而且舉了好多實際的例子，但有一些理論有點偏難。

多關于ci的解釋。

雖然有好多計算智能理論還不太清楚，但是我對新知識還是相當渴望的，因為我本身比較愛學習，且喜歡讀書。我感覺學到了許多知識：計算智能是一門經驗科學，它研究自然的或人工的智能行為形成之原理以“推理即計算”為基本假設，開發(fā)某種理論、說明某項智能可以算法化，從而可以用機器模擬和實現(xiàn)；尋求和接受自然智能之啟迪，但不企圖完全仿制人類智能，其中心工程目標是研究設計和建立智能計算系統(tǒng)的方法。

由于我們只有16課時，所以我們學的面并不廣，金老師主要教了一些計算智能方面的經典理論，我們所學的計算智能所涉及的領域主要包括以下三方面：遺傳算法、人工神經網絡方法和模糊集理論。

遺傳算法最早由美國michigan大學john h.holland教授提出，按照生物進化過程中的自然選擇（selection）、父代雜交（crossover）和子代變異（mutation）的自然進化（natural evolution）方式，編制的計算機程序，能夠解決許多復雜的優(yōu)化問題，這類新的優(yōu)化方法稱之為遺傳算法（genetic algorithm，ga）[7]。ga模擬生物進化過程中的主要特征有：（1）生物個體的染色體（chromosomes）的結構特征，即基因碼序列（series of genetic code）決定了該個體對其生存環(huán)境的適應能力。（2）自然選擇在生物群體（population）進化過程中起著主導作用，它決定了群體中那些適應能力（adaptability）強的個體能夠生存下來并傳宗接代，體現(xiàn)了“優(yōu)勝劣汰”的進化規(guī)律。（3）個體繁殖（雜交）是通過父代個體間交換基因材料來實現(xiàn)的，生成的子代個體的染色體特征可能與父代的相似，也可能與父代的有顯著差異，從而有可能改變個體適應環(huán)境的能力。

（4）變異使子代個體的染色體有別于其父代個體的染色體，從而也改變了子代個體對其環(huán)境的適應能力。（5）生物的進化過程，從微觀上看是生物個體的染色體特征不斷改善的過程，從宏觀上看則是生物個體的適應能力不斷提高的過程。作為利用自然選擇和群體遺傳機制進行高維非線性空間尋優(yōu)的一類通用方法，遺傳算法（ga）不一定能尋得最優(yōu)（optimal）點，但是它可以找到更優(yōu)（superior）點，這種思路與人類行為中成功的標志是相似的。例如不必要求某個圍棋高手是最優(yōu)的，要戰(zhàn)勝對手只需他（她）比其對手更強即可。因此，ga可能會暫時停留在某些非最優(yōu)點上，直到變異發(fā)生使它遷移到另一更優(yōu)點上。遺傳算法隨編碼

方式、遺傳操作算子的不同而表現(xiàn)為不同形式，因此難以象傳統(tǒng)的共軛梯度法那樣從形式上給以明確定義，它的識別標志在于它是否具有模擬生物的自然選擇和群體遺傳機理這一內在特征。目前國內外普遍應用的實施方案是標準遺傳算法（simple genetic algorithm，sga）。bp神經網絡 bp神經網絡是用反向傳播學習算法（back-propagation algorithm，bp算法）訓練的一種多層前饋型非線性映射網絡，網絡中各神經元接受前一級的輸入，并輸出到下一級，網絡中沒有反饋聯(lián)接。bp神經網絡通?？梢苑譃椴煌膶樱墸?，第j層的輸入僅與第j–1層的輸出聯(lián)接。由于輸入層節(jié)點和輸出層節(jié)點可與外界相連，直接接受環(huán)境的影響，所以稱為可見層，而其它中間層則稱為隱層（hidden layer）。決定一個bp神經網絡性質的要素有三個：網絡結構、神經元作用函數(shù)和學習算法，對這三個要素的研究構成了豐富多彩的內容，尤其是后者被研究得最多。bp算法是目前應用最為廣泛且較成功的一種算法，它解決了多層前饋網絡的學習問題，從而使該網絡在各方面獲得了廣泛應用。它利用梯度搜索技術（gradient search technique）使代價函數(shù)（cost function）最小化。bp算法把一組樣本的輸入輸出問題歸納為一非線性優(yōu)化問題，它使用了最優(yōu)化方法中最常用的負梯度下降算法。用迭代運算求解網絡權重和閾值對應于網絡的學習記憶過程，加入隱層節(jié)點使得優(yōu)化問題的可調參數(shù)增加，從而可得到更精確的解。

模糊集理論

模糊集理論（又稱模糊數(shù)學，fuzzy mathematics）就是應用模糊集這一模擬人腦模糊思維的數(shù)學工具，來描述、分析、識別、分類、判斷、推理、決策和控制各種模糊事物所形成的一門現(xiàn)代應用數(shù)學分支學科。經典數(shù)學僅考慮現(xiàn)實世界的數(shù)量而拋棄現(xiàn)實世界的質量，而模糊集理論則反映了現(xiàn)實世界數(shù)量與質量的統(tǒng)一性，是對經典數(shù)學的一種補充和完善。定義模糊集、模糊關系的不同運算（目前主要是代數(shù)運算），就可得到相應的不同模糊數(shù)學方法。目前已研究成熟并廣為應用的模糊數(shù)學方法主要有模糊模式識別、模糊聚類分析、模糊綜合評價、模糊推理、模糊控制等方法。在現(xiàn)代科學技術體系中定性因素和主觀因素定量化處理的方法至今仍很少，而模糊數(shù)學方法正是其中的典型代表，目前已在各科學和工程領域得到了廣泛的成功應用，其主要原因在于它異于其它方法的一些顯著特點：（1）模糊集的引入改善了二值邏輯中硬性的分類方法，是普通集合的推廣，使模糊數(shù)學方法更加接近于廣泛存在模糊性和不精確性的現(xiàn)實世界，也更加接近于人類思維方式。這些真實性使得模糊數(shù)學方法能很好地平衡系統(tǒng)的復雜性與描述系統(tǒng)的精確性，也有助于模糊數(shù)學方法充分提取各種專家經驗信息和其它人類語言信息。（2）當系統(tǒng)為多輸入多輸出、強非線性、定性信息與定量信息混雜的動態(tài)系統(tǒng)時，系統(tǒng)的數(shù)學模型非常復雜或根本就不存在確定性數(shù)學模型，常規(guī)方法難以或不能有效處理這樣的復雜系統(tǒng)，而模糊數(shù)學方法可以用建立在語言型經驗之上的模糊集及其運算就可以簡便有效地處理，有時甚至不需要輔以確定的數(shù)學模型。（3）模糊數(shù)學方法可以直接利用人類語言型概念及其運算，篇四：遺傳算法總結

遺傳算法總結

遺傳算法是借鑒生物的自然選擇和遺傳進化機制而開發(fā)出的一種全局自適應概率搜索算法。

一、遺傳算法流程圖

圖1 遺傳算法流程圖

二、遺傳算法的原理和方法 1）染色體編碼

把一個問題的可行解從其解空間轉換到遺傳算法所能處理的搜索空間的轉換方法就稱為編碼。de jong曾提出了兩條操作性較強的實用編碼原則：編碼原則一：應使用能易于產生與所求問題相關的且具有低階、短定義長度模式的編碼方案；編碼原則二：應使用能使問題得到自然表示或描述的具有最小編碼字符集的編碼方案。

編碼方法主要有以下幾種：二進制編碼方法、格雷碼編碼方法、浮點數(shù)編碼方法、符號編碼方法、參數(shù)級聯(lián)編碼方法、多參數(shù)交叉編碼方法。2）適應值計算

由解空間中某一點的目標函數(shù)值f(x)到搜索空間中對應個體的適應度函數(shù)值 fit(f(x))的轉換方法基本上有一下三種： a． 直接以待解的目標函數(shù)值f(x)轉化為適應度函數(shù)值fit(f(x))，令 ?f(x)目標函數(shù)為最大化函數(shù) fit(fx())= ? ??f(x)目標函數(shù)為最小化函數(shù) ?cmax?f(x)f(x)?cmax b． 對于最小值的問題，做下列轉化fit(f(x))??，其中cmax是 0 其他? f(x)的最大輸入值。

c． 若目標函數(shù)為最小值問題，fit(f(x))? 1 , c?0, c?f(x)?0 1?c?f(x)1 , c?0, c?f(x)?0 1?c?f(x)若目標函數(shù)為最大值問題，fit(f(x))?3）選擇、交叉、變異

遺傳算法使用選擇算子來對群體中的個體進行優(yōu)勝劣汰操作：根據每個個體的適應度值大小選擇。適應度較高的個體被遺傳到下一代群體中的概率較大；適應度較低的個體的被遺傳到下一代群體中的概率較小。其中選擇的方法有：輪盤賭選擇、隨機競爭選擇、最佳保留選擇、無回放隨機選擇、確定式選擇等。

遺傳算法中的所謂交叉運算，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉操作主要有單點交叉、兩點交叉與多點交叉、均勻交叉和算數(shù)交叉四種。

遺傳算法中的變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他基因來替換，從而形成一個新的個體。主要有基本位變異、均勻變異、邊界變異等幾種變異操作方法。4）控制參數(shù)選擇

交叉概率pcpm

三、算例

min f(x1,x2)?(x1?3)2?(x2?2)2 2 ?g1(x1,x2)?x12?x2?5? s.t.?h1(x1,x2)?x1?2x2?4?0?x,x?10，x?n 121?(1)1）三種不同的遺傳方法

方法一：原模型中x1、x2均為決策變量，操作如下。a.采用混合整數(shù)編碼，對x1進行十進制編碼，x2進行二進制編碼； b.適應度函數(shù)值采用fit(f(x1,x2))? 1 計算，其中 c?f(x1,x2)c???max{0,g1(x1,x2)?5}???max{0,|h1(x1,x2)?4|}，?=?=10000； c.采用賭輪盤選擇、單點交叉和基本位變異； d.pc=0.8，pm=0.1，遺傳代數(shù)為200，種群中個體數(shù)100； e.終止條件為連續(xù)十次最優(yōu)個體保持不變或遺傳代數(shù)到達200。方法二：已知等式約束h1(x1,x2)，可得x2?(4?x1)/2，則原問題可化為 min f(x1)?(x1?3)2?((4?x1)?2)22（2）4?x12?2 g(x)?x?()?5111? 2?s..t?0?x1?10，x1?n?4?x1?0??10 2? x min f(x1)?(x1?3)2?(1)2 2 即等式約束簡化后的模型為 4?x12?2 g(x)?x?()?5?1 s..t?112??0?x1?4，x1?n 其中a~b的操作如下，而c~e的操作同方法一。a.對x1進行十進制編碼； b.適應度函數(shù)值采用fit(f(x1,x2))?（3）1 計算，其中 c?f(x1,x2)c???max{0,g1(x1,x2)?5}，?=10000 方法三：在方法二的基礎上，改變x1的編碼方法，對x1進行二進制編碼。由于0?x1?4，且為自然數(shù)，則二進制編碼至少為3位，但3位的二進制可以表示0~7的整數(shù)，所以存在冗余編碼。則通過懲罰來排除冗余編碼，即適應度函數(shù)值采用 fit(f(x1,x2))? 1 計算。c?f(x1,x2)其中c???max{0,g1(x1,x2)?5}???max{0,x1(i)?4}，?=10000。x1(i)表示個體解碼后的x1。

2）三種方法的計算結果

方法一可得到三個不同的解：

解1：x1?2,x2?1, fit(f(x1,x2))?0.4646, f(x)?2.0000，適應度趨勢圖如下： 圖2 方法一解1的適應度趨勢圖

解2：x1?0,x2?2, fit(f(x1,x2))?0.1075, f(x)?9.0000，適應度趨勢圖如下： 篇五：遺傳算法學習作業(yè)

遺傳算法學習總結 1.1 概述 遺傳算法是一類借鑒生物界的進化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機制）演化而來的自適應概率性隨機化迭代搜索算法。1962年霍蘭德(holland)教授首次提出了ga算法的思想，它的基本思想是基于darwin進化論和mendel的遺傳演說。darwin進化論最重要的是適者生存的原理，它認為每一代種群總是向著前進方向發(fā)展，越來越適應環(huán)境。每一個個體都有繼承前代的特性，但不是完全繼承，會產生一些新特性。最終只有適應環(huán)境的特征才能被保留下來。mendel遺傳學說最重要的是基因遺傳原理，它認為遺傳以密碼方式存在細胞中，并以基因形式包含在染色體內。一條染色體中存在很多基因，每個基因有自己的位置并控制著外部特征；基因的產生和變異直接影響到個體的特性是否能適應環(huán)境。經過存優(yōu)去劣的自然淘汰，適應性高的基因結構得以保存下來。

遺傳算法正是借用了仿真生物遺傳學和自然選擇機理，通過自然選擇、遺傳、變異等作用機制，實現(xiàn)各個個體的適應性的提高。

與自然界相似，遺傳算法對求解問題的本身一無所知，從代表問題可能潛在解集的一個種群(population)開始，每一個種群則由經過基因(gene)編碼(coding)的一定數(shù)目的個體(individual)構成。每個個體實際上是染色體(chromosome)帶有特征的實體。把問題的解表示成染色體，并基于適應值來選擇染色體，遺傳算法所需要的僅是對算法所產生的每個染色體進行評價，使適應性好的染色體有更多的繁殖機會。在算法中也就是以二進制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群染色體，也就是假設解。然后，把這些假設解置于問題的“環(huán)境”中，也即在一個適應度函數(shù)中來評價。并按適者生存的原則，從中選擇出較適應環(huán)境的染色體進行復制，淘汰低適應度的個體，再通過交叉，變異過程產生更適應環(huán)境的新一代染色體群。對這個新種群進行下一輪進化，直到最適合環(huán)境的值。1.2遺傳算法的基本原理和特點 1.2.1 算法原理

在遺傳算法中，通過隨機方式產生若干個所求解問題的數(shù)字編碼，即染色體，形成初始種群；通過適應度函數(shù)給每個個體一個數(shù)值評價，淘汰低適應度的個體，選擇高適應度的個體參加遺傳操作，經過遺傳操作后的個體集合形成下一代新的種群，再對這個新種群進行下一輪進化，這就是遺傳算法的基本原理。

遺傳算法的主要步驟如下： 1)隨機產生一個由確定長度的特征串組成的初始群體； 2)對串群體迭代地執(zhí)行步驟(1)和(2)，直到滿足停止準則：(1)計算群體中每個個體的適應值。(2)應用復制、雜交和變異算子產生下一代群體。3)把在任一代中出現(xiàn)的最好的個體串指定為遺傳算法的執(zhí)行結果。這個結果可以表示問題的一個解(或近似解)?；具z傳算法的流程圖如圖 1-1，其中gen是當前代數(shù)，m為每代種群中最大個體數(shù)。

圖1-1 基本遺傳算法的流程圖 1.2.2 算法特點

遺傳算法的特點如下： 1)遺傳算法中不包含待解決問題所持有的形態(tài)。它是從改變基因的配置來實現(xiàn)問題的整體優(yōu)化的，因而屬于自下而上的優(yōu)化方法； 2)類似于生物的進化過程，遺傳算法處理的是變量集合的編碼而非變量本身。它直接 對結構對象進行操作，不存在求導和函數(shù)連續(xù)性的限定； 3)遺傳算法具有內在的隱并行性和更好的全局尋優(yōu)能力； 4)遺傳算法采用概率化的尋優(yōu)方法，能自動獲取和指導優(yōu)化的搜索空間，自適應地調整搜索方向，不需要確定的規(guī)則。

遺傳算法的這些特點已被人們廣泛地應用于組合優(yōu)化、機器學習、信號處理、自適應控制和人工生命等領域。它是現(xiàn)代有關智能計算中的關鍵技術之一。1.3 基本遺傳算法的步驟

1.3.1 染色體編碼（chromosome coding）與解碼(decode)基本遺傳算法使用固定長度的二進制符號串來表示群體中的個體，其等位基因由二值{0，1}所組成。初始群體中各個個體的基因可用均勻分布的隨機數(shù)來生成。例如：x=***101就可表示一個個體，該個體的染色體長度是n=18。（1）編碼：變量x作為實數(shù)，可以視為遺傳算法的表現(xiàn)型形式。從表現(xiàn)型到基因型的映射稱為編碼。設某一參數(shù)的取值范圍為[u1，u2]，我們用長度為k的二進制編碼符號來表示該參數(shù)，則它總共產生2k種不同的編碼，可使參數(shù)編碼時的對應關系為：

000000?0000=0→u1 000000?0001=1→u1+? 000000?0010=2→u1+2? ? 111111?1111=2k-1→u2 u?u其中，?=2 k1。2?1（2）解碼：假設某一個體的編碼為bkbk-1bk-2?b2b1,則對應的解碼公式為 x?u1?(?bi?2i?1)? i?1ku2?u1 ① k2?1 例如：設有參數(shù)x∈[2，4]，現(xiàn)用5位二進制編碼對x進行編碼，得25=32個二進制串（染色體）：

00000,00001,00010,00011,00100,00101,00110,00111 01000,01001,01010,01011,01100,01101,01110,01111 10000,10001,10010,10011,10100,10101,10110,10111 11000,11001,11010,11011,11100,11101,11110,11111 對于任一個二進制串，只要代入公式①，就可得到相應的解碼，如x22=10101,它對應的十進制為?bi?2i?1=1+0*2+1*22+0*23+1*24=21,則對應參數(shù) i?15 x的值為2+21*(4-2)/(25-1)=3.3548。1.3.2 個體適應度的檢測評估

基本遺傳算法按與個體適應度成正比的概率來決定當前群體中各個個體遺傳到下一代群體中的機會多少。為了正確估計這個概率，要求所有個體的適應度

必須為非負數(shù)。所以，根據不同種類的問題，需要預先確定好由目標函數(shù)值到個體適應度之間的轉換規(guī)律，特別是要預先確定好當目標函數(shù)值為負數(shù)時的處理方法。例如，可選取一個適當大的正數(shù)c，使個體的適應度為目標函數(shù)值加上正數(shù)c。1.3.3 遺傳算子

基本遺傳算法使用下列三種遺傳算子：

（1）選擇運算使用比例選擇算子。比例選擇因子是利用比例于各個個體適應度的概率決定其子孫的遺傳可能性。若設種群數(shù)為m，個體i的適應度為fi,則個體i被選取的概率為 pi?fi/?fk k?1m 當個體選擇的概率給定后，產生[0，1]之間的均勻隨機數(shù)來決定哪個個體參加交配。若個體的選擇概率大，則能被多次選中，它的遺傳基因就會在種群中擴大；若個體的選擇概率小，則被淘汰。

我們經常采用的是輪盤賭的原理，個體的選擇概率是基于它們的性能進行的一些計算。實值范圍——總和是所有個體期望的選擇概率的總和或當前種群中所有個體原始適應度值的總和。個體采用一對一方式

映像到范圍[0，sum]的一連續(xù)區(qū)間，每一個體區(qū)間的 大小與對應個體的適應度值相匹配。如圖1所示，輪

盤賭輪的周長是6個個體適應度值的總和，個體5 是最大適應度個體，它占有最大的區(qū)間。選擇一個個

體，用在[0，sum]間產生隨機數(shù)，看此隨機數(shù)在哪個

個體的區(qū)間上，則此個體被選中。重復此過程，直到

所需數(shù)量個體被選中為止。

（2）交叉運算使用單點交叉算子。只有一個交叉點位置，任意挑選經過選擇操作后種群中兩個個體作為交叉對象，隨機產生一個交叉點位置，兩個個體在交叉點位置互換部分基因碼，形成兩個子個體，如圖2所示。

父個體1 父個體2 110 11 011 00 單點交叉 子個體1 子個體2 圖2 單點交叉示意圖

（3）變異運算使用基本位變異算子或均勻變異算子。為了避免問題 過早收斂，對于二進制的基因碼組成的個體種群，實現(xiàn)基因碼的小概率翻轉，即0變?yōu)?，而1變?yōu)?，如圖3所示。

變異

圖3 變異操作示意圖 1.3.4 基本遺傳算法的運行參數(shù) 基本遺傳算法有下列4個運行參數(shù)需要預先設定，即m,t,pc,pm。m為群體大小，即群體中所含個體的數(shù)量，一般取為20~100； t為遺傳算法的終止進化代數(shù)，一般取為100~500； pc為交叉概率，一般取為0.4~0.99;pm為變異概率，一般取為0.0001~0.1。1.4遺傳算法的應用 進入90年代后，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳算法的應用研究顯得格外活躍，不但它的應用領域擴大，而且利用遺傳進行優(yōu)化和規(guī)則學習的能力也顯著提高，同時產業(yè)應用方面的研究也在摸索之中。

遺傳算法提供了一種求解復雜系統(tǒng)問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。如工程結構優(yōu)化、計算數(shù)學、制造系統(tǒng)、航空航天、交通、計算機科學、通信、電子學、材料科學等。1)ga在數(shù)值優(yōu)化上的應用

最優(yōu)化問題是遺傳算法經典應用領域，但采用常規(guī)方法對于大規(guī)模、多峰態(tài)函數(shù)、含離散變量等問題的有效解決往往存在許多障礙。對全局變化問題，目前存在確定性和非確定性兩類方法。前者以brianin的下降軌線法、levy的隧道法和r.ge的填充函數(shù)為代表。該類方法雖然收斂快、計算效率高，但算法復雜，求得全局極值的概率不大。遺傳算法作為現(xiàn)代最優(yōu)化的手段，實踐證明，它應用于大規(guī)模、多峰多態(tài)函數(shù)、含離散變量等情況下的全局優(yōu)化問題是合適的，在求解速度和質量上遠遠超過常規(guī)方法。2)ga 在組合優(yōu)化中的應用

3)遺傳算法在機器學習中的應用

機器學習系統(tǒng)實際上是對人的學習機制的一種抽象和模擬，是一種理想的學習模型?；诜枌W習的機器學習系統(tǒng)如監(jiān)督型學習系統(tǒng)、條件反射學習系統(tǒng)、類比式學習系統(tǒng)、推理學習系統(tǒng)等，只具備一些較初級的學習能力。近年來，由于遺傳算法的發(fā)展，基于進化機制遺傳學習成為一種新的機器學習方法，它將知識表達為另一種符號形式—遺傳基因型，通過模擬生物的進化過程，實現(xiàn)專門領域知識的合理增長型學習。4)遺傳算法在并行處理中的應用 遺傳算法固有的并行性和大規(guī)模并行機的快速發(fā)展，促使許多研究者開始研究遺傳算法的并行化問題，研究數(shù)量更加接近自然界的軟件群體將成為可能。遺傳算法與并行計算的結合，能把并行機的高速性和遺傳算法固有的并行性兩者的長處彼此結合起來，從而也促進了并行遺傳算法的研究與發(fā)展。

第四篇：基于遺傳算法的排課系統(tǒng)設計 開題報告

基于遺傳算法的排課系統(tǒng)設計開題報告 課題的意義

每個新學期開始，對于學校教務科來說首要而急需完成的任務是：如何合理而高效的排課。其本質是將課程、教師和學生在合適的時間段內分配到合適的教室中。但由于涉及到的問題較多，同時學校擴招，學生和課程數(shù)量比以往大大增加，教室資源明顯不足，在這種情況下排課很難在同時兼顧多重條件限制的情況下用人工方式排出令教師和學生都滿意的課表。

雖然排課問題很早以前就成為眾多科研人員和軟件公司的研究課題，但是真正投入使用的排課軟件卻很少。原因是多方面的，其中算法的選擇是最關鍵的一個問題，S.Even等人在1975年的研究中證明了排課問題是一個NP-Complete問題，即若是用“窮舉法”之外的算法找出最佳解是不可能的。然而由于窮舉法成本太高，時間太長，根本無法在計算機上實現(xiàn)。如果假設一個星期有n個時段可排課，有m位教師需要參與排課，平均每位教師一個星期上k節(jié)課，在不考慮其他限制情況下，能夠推出的可能組合就有nm*k種，如此高的復雜度是目前計算機所無法承受的。而遺傳算法的出現(xiàn)正好解決了排課在算法上的問題，可以很有效的求出最優(yōu)解。輕松而快速的解決了困擾教務科的一大難題，能在短時間內排出符合各項條件的課程表。國內外研究現(xiàn)狀

計算機排課問題是一個多目標，有限資源，帶有模糊約束條件的組合規(guī)劃問題，是計算機應用領域一個具有代表性的問題。20世紀60年代末，Gotlieb.C.C教授就對課程表問題進行了形式化描述。隨后，此類研究發(fā)展起來。70年代中期，S.Even等人就論證了課表問題是NP完全類問題，將該問題理論化，同時也說明課表問題有其自身的理論化模型，即課表問題存在解。并且能找到解。但是根據計算和難解性理論，目前還沒有解決NP完全類問題的多項式算法。到1979年，Schmit 和Strohein在文獻中就列出了 300多篇已發(fā)表的文獻。近年來研究這一問題的人員不斷增多，國外的運籌學雜志幾乎每年都有相關內容的文章那個發(fā)表，此外它還廣泛的出現(xiàn)在計算機，應用數(shù)學，教育管理等雜志上。80年代初，我國的很多大學也開始研究排課系統(tǒng)軟件。大體上說這些排課系統(tǒng)軟件可以分為兩大類：第一類以所謂班——教員模型為主，它是在Gotlieb.C.C工作的基礎上發(fā)展起來的。主要討論此模型的定義擴充，解的特性及分析，不斷提出新的猜測和推論?；灸Ｐ妥兓淮?，并且這類模型適合課程長度一致，無合班教室的情況，并不適合一般院校的實際情況。第二類事所謂的課程調度問題，多于圖的節(jié)點的著色問題有關，模型一旦產生，它的變量往往太多，規(guī)模太大，此外根據具體的校情對模型提出的各式各樣要求對模型影響較大，有的甚至沒有具體的模型可尋。通過對資料的查閱發(fā)現(xiàn)以往對課程問題的研究多側重于自動生成，難度較大實現(xiàn)不易，往往是理論研究上的工作多，而實際應用方面的工作很少。有一些實際的例子，也往往是特定條件下對實際情況簡化得到的，至今還沒有自動生成可課表系統(tǒng)的軟件應用于實際。對計算機而言，不像人工編排那樣可以對任何情況進行合理的取舍，因此不存在完全沖突的課表很難排出來。

國內高校排課系統(tǒng)中，大連理工大學是從事此類軟件開發(fā)較早單位。1987年該校開發(fā)了《教學組織管理及課程調度系統(tǒng)》1.00版本，之后在此基礎上又推出了《教學組織管理及課程調度系統(tǒng)》2.00版本，1902年又推出了《教學組織管理及課程調度系統(tǒng)》2.01版本和安排考試補考的《考試調度系統(tǒng)》。1994年又推出了《教學調度系統(tǒng)》2.20版本。1998年 年推出的在Windows下運行的3.00版，現(xiàn)在在各大高校使用比較多，反映較好的有大連理工大學開發(fā)的系統(tǒng)和清華大學開發(fā)的《綜合教務排課系統(tǒng)》，以及北京大學開發(fā)上的一套比較新的排課管理系統(tǒng)。

3畢業(yè)設計論文的主要內容

1.遺傳算法的形成及基本應用，遺傳算法的基本實現(xiàn)技術和特點。

2.排課中所要考慮的約束條件，課表編排的基本規(guī)則和課表編排中存在的矛盾和問題 3.將遺傳算法應用于排課系統(tǒng)；

4.所采用的方法、手段以及步驟等

1.詳細了解課表編排中存在的矛盾和課表編排的規(guī)則，將其逐條列舉出來，選取必須兼顧的重要的約束條件，2.分析學生，教師，課程，教室之間的關系建立概念模型和邏輯模型 3.產生初試種群

4沖突檢測和消除：對各種沖突進行檢測，如有沖突則消除它 5計算適應度函數(shù) 期望值

6遺傳操作包括選擇 交叉 變異 7可行課表的生成

5.階段進度計劃

第一周——第三周：查閱資料，學習遺傳算法的基本理論，查閱相關文獻完成 開題報告

第四周——第五周：詳細學習遺產算法，并對所做課題進行詳細構思

第六周——第七周： 完成英文資料的翻譯

第八周——第九周 ：分析調查排課問題所面臨的具體問題和矛盾以及縮影可考慮的因素，分析找出座位乖蹇的約束條件

第七周——第九周：對各個模塊進行設計 第十周——第十一周：對各個部分進行分析完善 第十二周——第十三周：撰寫論文

第十四周：完成PowerPoint制作的論文答辯電子稿

第十五周——第十六周：論文答辯 6參考文獻

周明 孫樹棟《遺傳算法原理及應用》國防工業(yè)出版社 1996.6 徐艷斌 基于遺傳算法的高校排課系統(tǒng)設計與分析(碩士生論文)

第五篇：機械振動交互式遺傳算法粗糙集汽車行駛平順性論文

基于隱式性能指標的機械振動優(yōu)化設計

【摘要】近些年,優(yōu)化算法已經成為研究與應用領域一種非常重要的工具,利用遺傳算法的優(yōu)化原理,普通遺傳算法在解決機械振動優(yōu)化設計方面的問題具有很大的優(yōu)勢。遺傳算法已經廣泛的應用于機械振動優(yōu)化設計中,雖然解決了一部分機械設計中遇到的問題,但是這種算法往往只能解決性能指標用顯示函數(shù)表達的優(yōu)化問題。而在實際的工程中,很多系統(tǒng)優(yōu)化問題的性能指標并不能用顯示的函數(shù)表達出來,這方面屬于隱式性能指標的優(yōu)化問題,采用傳統(tǒng)的遺傳算法不能解決此類問題。本文主要提出了一種交互式遺傳算法優(yōu)化算法,通過用戶給出適應度值參與進化過程,突破傳統(tǒng)遺傳算法的主要缺陷來優(yōu)化解決機械振動方面的實際問題,這種優(yōu)化方法能啟發(fā)式的搜索到全局最優(yōu)解的較小區(qū)域,而且不會陷入局部最優(yōu)解,解決了部分隱式性能指標下的機械振動優(yōu)化問題。對于交互式遺傳算法人的疲勞問題,本文采用粗糙集理論的分類約簡功能解決,從而解決了隱式性能指標下的機械振動優(yōu)化設計。本文根據交互式遺傳算法,開發(fā)了一套機械振動優(yōu)化設計測試系統(tǒng)。該系統(tǒng)是在Visual C++ 6.0的環(huán)境下利用MFC開發(fā)工具完成的。程序采用文檔/視圖結構,將后臺的數(shù)據管理和前臺的用戶交互分離開來,極大的方便...更多還原

【Abstract】 In recent years, optimization has become an important tool for research and application.Experts have given in detail about the principle of genetic algorithm optimization and the general application of genetic algorithms applied to optimal design of the advantages of mechanical vibrations.Some articles have been using genetic algorithm to solve the plight of mechanical vibration, but traditional genetic algorithm can only solve the system optimization problem with a clear(explicit)expression....更多還原

【關鍵詞】 機械振動； 交互式遺傳算法； 粗糙集； 汽車行駛平順性；

【Key words】 Mechanical vibration； interactive genetic algorithm； rough set； vehicle ride comfort； 摘要 4-5 Abstract 5-6 第1章 緒論 10-15

1.1 課題來源和研究意義 10-11

1.2 國內外研究現(xiàn)狀 11-12

1.3 論文的創(chuàng)新點及主要研究內容 12-13

1.4 論文的內容組織形式 13-15

第2章 隱式性能指標機械振動優(yōu)化方法 15-24

2.1 交互式遺傳算法的概念 15-18

2.1.1 交互式遺傳算法與傳統(tǒng)遺傳算法的區(qū)別 15-17

2.1.2 交互式遺傳算法的特點 17-18

2.2 交互式遺傳算法的核心問題 18-20

2.2.1 個體適應值估計 19

2.2.2 加速進化收斂 19-20

2.3 交互式遺傳算法的環(huán)境 20-22

2.3.1 交互式遺傳算法的環(huán)境 20-21

2.3.2 交互式遺傳算法環(huán)境的波動性和不一致性 21-22

2.4 開發(fā)工具及環(huán)境 22-23

2.5 本章小結 23-24

第3章 屬性相對約簡啟發(fā)式遺傳算法 24-32

3.1 基于遺傳算法的粗糙集知識抽取方法 24-26

3.2 粗糙集最小屬性集選擇 26-27

3.3 屬性集選擇的貪心算法 27

3.4 基于交互式遺傳算法的屬性相對約簡 27-31

3.5 本章小結 31-32

第4章 基于隱式性能指標的機械振動優(yōu)化設計實例 32-43

4.1 汽車行駛平順性的主要指標 32-39

4.1.1平順性評價指標 33-36

4.1.2 1/3 倍頻帶分別評價法 36-38

4.1.3 總加權值評價法 38-39

4.2 汽車行駛平順性的輔助評價指標 39

4.3 汽車振動模型 39-42

4.3.1 系統(tǒng)的力學和數(shù)學模型 39-40

4.3.2 系統(tǒng)的頻率響應特性 40-41

4.3.3 系統(tǒng)的振動響應量的幅頻特性 41

4.3.4 系統(tǒng)響應量的功率譜密度 41-42

4.4 基于交互式遺傳算法的汽車平順性的優(yōu)化 42

4.4.1 設計變量的確定 42

4.4.2 目標函數(shù)的建立 42

4.5 本章小結 42-43

第5章 交互式遺傳算法軟件開發(fā)與功能實現(xiàn) 43-62

5.1 MFC 開來發(fā)工具概述 43-44

5.2 MFC 文檔/視圖結構分析 44-46

5.3 軟件實現(xiàn)的總體流程 46-48

5.4 算法程序的設計與實現(xiàn) 48-59

5.4.1 根據實際問題進行編碼 49-50

5.4.2 設定遺傳操作的各參數(shù) 50-51

5.4.3 產生初始種群 51-52

5.4.4 遺傳操作程序設計 52-55

5.4.5 人機交互操作程序 55-56

5.4.6 進化終止條件判斷程序 56

5.4.7 世代進化過程的實現(xiàn) 56-57

5.4.8 在窗口中輸出每一代的結果 57-59

5.5 交互式遺傳算法的優(yōu)化結果 59-61

5.6 本章小結 61-62 第6章 全文總結與展望 62-64

6.1 總結 62-63

6.2 展望 63-64 參考文獻