遺傳算法

1、計算智能,計算智能是信息科學(xué)和生命科學(xué)相互交叉的前沿領(lǐng)域,是現(xiàn)代科學(xué)技術(shù)發(fā)展的一個重要體現(xiàn)。計算智能涉及神經(jīng)網(wǎng)絡(luò)、模糊邏輯、進化計算和人工生命等領(lǐng)域，它的研究和發(fā)展反映了當(dāng)代科學(xué)技術(shù)多學(xué)科交叉與集成的重要發(fā)展趨勢。,貝茲德克于1994年提出了一種A，B，C智能模型，從而表示ABC與神經(jīng)網(wǎng)絡(luò)、模式識別和智能之間的關(guān)系：A：Artificial ,表示人工的、符號的（非生物的）B：Biological ,表示生物的C：Comput

2、ational,表示計算的計算智能是一種智力方式的底層認知，它與人工智能的區(qū)別是認知層次從中層下降到底層而已。中層系統(tǒng)含有知識，底層系統(tǒng)沒有知識。,關(guān)于A，B，C智能,計算智能與人工智能的區(qū)別與聯(lián)系,NN Neural Network 神經(jīng)網(wǎng)絡(luò)PR Pattern Recognition 模式識別,計算智能系統(tǒng)與人工智能系統(tǒng),當(dāng)一個系統(tǒng)只涉及數(shù)值（底層）數(shù)據(jù)，含有模式識別部分，不應(yīng)用于人工智能意義上的知識，而且系統(tǒng)能夠呈現(xiàn)出：（

3、1）計算適應(yīng)性（2）計算容錯性（3）接近人的計算速度（4）計算誤差率與人接近則該系統(tǒng)就是計算智能系統(tǒng)。當(dāng)一個智能計算系統(tǒng)以非數(shù)值方式并加上知識，即為人工智能系統(tǒng)。,神經(jīng)計算（Neural Computation）,神經(jīng)計算研究的進展1943年麥卡洛奇和皮茨提出神經(jīng)網(wǎng)絡(luò)模型的概念（稱為MP模型）20世紀60年代威德羅和霍夫提出了自適應(yīng)線性元件。60年代末到80年代初初與研究的低潮期80年代后又大發(fā)展,遺傳算法,遺傳算法

4、簡稱GA（Genetic Algorithms）是1975年由美國Michigan(密歇根州)大學(xué)的J.Holland教授提出的模擬自然界生物遺傳學(xué)（孟德爾）和生物進化論（達爾文）通過人工方式所構(gòu)造的一類并行隨機搜索最優(yōu)化方法，是對生物進化過程進行的一種數(shù)學(xué)仿真，是進化計算的重要形式。,1、遺傳算法,在生物系統(tǒng)中，進化被認為是一種成功的自適應(yīng)方法，具有很好的健壯性。其主要特點是 (1)直接對結(jié)構(gòu)對象進行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限

5、定；(2)具有內(nèi)在的隱含并行性和更好的全局尋優(yōu)能力；(3)采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。 遺傳算法已被廣泛地應(yīng)用于組合優(yōu)化、機器學(xué)習(xí)、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)計算智能中的關(guān)鍵技術(shù)之一。 遺傳算法是以達爾文的自然選擇學(xué)說為基礎(chǔ)發(fā)展起來的。自然選擇學(xué)說包括以下三個方面：,1、遺傳算法,（1）遺傳：這是生物的普遍特征，親代把生物信息交給子

6、代，子代總是和親代具有相同或相似的性狀。生物有了這個特征，物種才能穩(wěn)定存在。（2）變異：親代和子代之間以及子代的不同個體之間的差異，稱為變異。變異是隨機發(fā)生的，變異的選擇和積累是生命多樣性的根源。（3）生存斗爭和適者生存：具有適應(yīng)性變異的個體被保留下來，不具有適應(yīng)性變異的個體被淘汰，通過一代代的生存環(huán)境的選擇作用，性狀逐漸逐漸與祖先有所不同，演變?yōu)樾碌奈锓N。,遺傳算法將“優(yōu)勝劣汰，適者生存”的生物進化原理引入優(yōu)化參數(shù)形成的編碼串群體

7、中，按所選擇的適應(yīng)度函數(shù)并通過遺傳中的復(fù)制、交叉及變異對個體進行篩選，適應(yīng)度高的個體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個體適應(yīng)度不斷提高，直到滿足一定的條件。遺傳算法的算法簡單，可并行處理，并能到全局最優(yōu)解。如：愛斯基摩人，,非洲原始部落,2、遺傳算法的基本操作為：（1）復(fù)制（Reproduction Operator） 復(fù)制是從一個舊種群中選擇生命力強的個體位串產(chǎn)生新種群

8、的過程。具有高適應(yīng)度的位串更有可能在下一代中產(chǎn)生一個或多個子孫。 復(fù)制操作可以通過隨機方法來實現(xiàn)。首先產(chǎn)生0~1之間均勻分布的隨機數(shù)，若某串的復(fù)制概率為40%，則當(dāng)產(chǎn)生的隨機數(shù)在0.40~1.0之間時，該串被復(fù)制，否則被淘汰。,（2）交叉（Crossover Operator） 復(fù)制操作能從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體。而交叉模擬了生物進化過程中的繁殖現(xiàn)象，通過兩個染色體的交換組合，來產(chǎn)生新的優(yōu)良品種。 交

9、叉的過程為：在匹配池中任選兩個染色體，隨機選擇一點或多點交換點位置；交換雙親染色體交換點右邊的部分，即可得到兩個新的染色體數(shù)字串。,交叉體現(xiàn)了自然界中信息交換的思想。交叉有單點交叉、兩點交叉、還有一致交叉、順序交叉和周期交叉。單點交叉是最基本的方法，應(yīng)用較廣。它是指染色體切斷點有一處，例：,（3）變異(Mutation Operator) 變異運算用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機地改

10、變遺傳基因（表示染色體的符號串的某一位）的值。在染色體以二進制編碼的系統(tǒng)中，它隨機地將染色體的某一個基因由1變?yōu)?，或由0變?yōu)?。,若只有選擇和交叉，而沒有變異，則無法在初始基因組合以外的空間進行搜索，使進化過程在早期就陷入局部解而進入終止過程，從而影響解的質(zhì)量。為了在盡可能大的空間中獲得質(zhì)量較高的優(yōu)化解，必須采用變異操作。,17,設(shè)自變量 x 介于0～31，求其二次函數(shù)的最大值，即： max f(x) = x2,

11、 x∈ [0, 31],3、遺傳算法示例-- f(x) = x2 極大值問題,當(dāng)然，利用簡單的代數(shù)運算，很容易求出該問題的解?，F(xiàn)在改用遺傳算法求解，遺傳算法通常包括下述內(nèi)容：,18,（1）編碼 遺傳算法首先要對實際問題進行編碼，用字符串表達問題。這種字符串相當(dāng)于遺傳學(xué)中的染色體。每一代所產(chǎn)生的字符串個體總和稱為群體。為了實現(xiàn)的方便，通常字符串長度固定，字符選0或1。 本例中，利用5位二進制數(shù)表示x值，采用隨機產(chǎn)生的方

12、法，假設(shè)得出擁有四個個體的初始群體，即：01101，11000，01000，10011。x值相應(yīng)為13，24，8，19。,19,（2）計算適應(yīng)度 衡量字符串（染色體）好壞的指標是適應(yīng)度，它也就是遺傳算法的目標函數(shù)。 本例中適應(yīng)度比較簡單，用x2計算。,表中還列出了當(dāng)前適應(yīng)度的總和∑f(xi)及平均值f，即： ∑f(xi) = f(x1) + f(x2) + f(x3) + f(x

13、4) = 1170 f = ∑f(xi) /4 = 292.5(293) f(x1)/f=169/293=0.57679...,20,（2）計算適應(yīng)度 表中第6列的 f(xi)/f 表示每個個體的相對適應(yīng)度，它反映了個體之間的相對優(yōu)劣性。如2號個體的 f(xi)/f 值最高（1.97），為優(yōu)良個體，3號個體最低（0.22），為不良個體。,21,（3）

14、復(fù)制 為了將已有的群體變?yōu)橄乱淮后w，遺傳算法仿效進化論中“自然選擇、適者生存”的原則，從舊群體中選擇優(yōu)良個體進行復(fù)制。選擇的依據(jù)是個體適應(yīng)度的大小，適應(yīng)度大的個體接受復(fù)制，使之繁殖；適應(yīng)度小的個體則刪除掉，遭到淘汰。,22,（3）復(fù)制 在本例中，根據(jù)相對適應(yīng)度的大小對個體進行取舍，2號個體性能最優(yōu)，予以復(fù)制繁殖。3號個體性能最差，將它刪除，使之死亡，表中的M表示傳遞給下一代的個體數(shù)目，其中2號個體占

15、2個，3號個體為0，1號、4號個體保持為1個。,這樣，就產(chǎn)生了下一代群體。,23,（3）復(fù)制,從表中的第4列可以看出，復(fù)制后產(chǎn)生的新一代群體的平均適應(yīng)度明顯增加，由原來的293增加到421。造成平均適應(yīng)度增加的原因有二： 1）淘汰原來最差的個體。使最小適應(yīng)度由原來的64增加到169。 2）增加了優(yōu)良個體（2號）的個數(shù)，使適應(yīng)度累計值增加。,24,（4）交換,通過復(fù)制產(chǎn)生的新群體，其性能得到改善，然而它不能產(chǎn)生

16、新的個體。為了產(chǎn)生新的個體，遺傳算法仿照生物學(xué)中雜交的方法，對染色體（字符串）的某些部分進行交叉換位。被交換的母體都選自經(jīng)過復(fù)制產(chǎn)生的新一代個體（優(yōu)勝者）。,25,（4）交換,本例中，利用隨機配對的方法，決定1號和2號個體、3號和4號個體分別交換，如表中第5列。再利用隨機定位的方法，確定這兩對母體交叉換位的位置分別從字符長度的第4位及第3位開始。如：3號、4號個體從字符長度第3位開始交換。交換開始的位置稱交換點。,26,（4）交換,從表

17、中可以看出，交換后出現(xiàn)優(yōu)異個體3號，其適應(yīng)度高達729，大大高于交換前的最大值（576）。與此同時，平均適應(yīng)度也從原來的421提高到439，說明交換后的群體正朝優(yōu)良方向發(fā)展。,27,（5）突變,遺傳算法模仿生物學(xué)中基因突變的方法，將個體字符串某位符號進行逆變，即由1變?yōu)?或由0變?yōu)?。例如，下式左側(cè)的個體于第3位突變，得到新個體如右側(cè)所示。,上述（2）～（5）反復(fù)執(zhí)行，直至得出滿意的最優(yōu)解。,由上可知，遺傳算法參考生物中有關(guān)進化與遺傳的

18、過程，利用復(fù)制、交換、突變等操作，不斷循環(huán)執(zhí)行，逐漸逼近全局最優(yōu)解。,遺傳算法中，個體是否進行突變以及在哪個部位突變，都由事先給定的概率決定。通常，突變概率很小，約為0.008，本例的第一代中就沒有發(fā)生突變。,28,從數(shù)學(xué)角度看，遺傳算法實質(zhì)上是一種搜索尋優(yōu)技術(shù)。它從某一初始群體出發(fā)，遵照一定的操作規(guī)則，不斷迭代計算，逐步逼近最優(yōu)解。這種搜索技術(shù)，有如下特點：,4、遺傳算法的基本特征,從上述簡單例子可以看出，遺傳算法仿照生物進化和遺傳的

19、規(guī)律，利用復(fù)制、交換、突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代一代地重復(fù)同樣的操作，最終找出最優(yōu)解。,29,（1）智能式搜索 遺傳算法的搜索策略，既不是盲目式的亂搜索，也不是窮舉式的全面搜索，它是有指導(dǎo)的搜索。指導(dǎo)遺傳算法執(zhí)行搜索的依據(jù)是適應(yīng)度，也就是它的目標函數(shù)。利用適應(yīng)度，使遺傳算法逐步逼近目標值。（2）漸進式優(yōu)化 遺傳算法利用復(fù)制、交換、突變等操作，使新一代的結(jié)果優(yōu)越于舊一代，通過不斷迭代，

20、逐漸得出最優(yōu)的結(jié)果，它是一種反復(fù)迭代的過程。,4、遺傳算法的基本特征,30,（3）全局最優(yōu)解 遺傳算法由于采用交換、突變等操作，產(chǎn)生新的個體，擴大了搜索范圍，使得搜索得到的優(yōu)化結(jié)果是全局最優(yōu)解而不是局部最優(yōu)解。（4）黑箱式結(jié)構(gòu) 遺傳算法根據(jù)所解決問題的特性，進行編碼和選擇適應(yīng)度。一旦完成字符串和適應(yīng)度的表達，其余的復(fù)制、交換、突變等操作都可按常規(guī)手續(xù)執(zhí)行。個體的編碼如同輸入，適應(yīng)度如同輸出。因此遺傳算

21、法從某種意義上講是一種只考慮輸入與輸出關(guān)系的黑箱問題。,4、遺傳算法的基本特征,31,（5）通用性強 傳統(tǒng)的優(yōu)化算法，需要將所解決的問題用數(shù)學(xué)式子表示，常常要求解該數(shù)學(xué)函數(shù)的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)。采用遺傳算法，只用編碼及適應(yīng)度表示問題，并不要求明確的數(shù)學(xué)方程及導(dǎo)數(shù)表達式。因此，遺傳算法通用性強，可應(yīng)用于離散問題及函數(shù)關(guān)系不明確的復(fù)雜問題，有人稱遺傳算法是一種框架型算法，它只有一些簡單的原則要求，在實施過程中可以賦予更多的含

22、義。（6）并行式算法 遺傳算法是從初始群體出發(fā)，經(jīng)過復(fù)制、交換、突變等操作，產(chǎn)生一組新的群體。每次迭代計算，都是針對一組個體同時進行，而不是針對某個個體進行。因此，盡管遺傳算法是一種搜索算法，但是由于采用這種并行機理，搜索速度很高。這種并行式計算是遺傳算法的一個重要特征。,4、遺傳算法的基本特征,32,遺傳算法受生物進化與遺傳的啟發(fā)，形成一種獨特的優(yōu)化方式，因此，遺傳算法的運算原則常常與生物進化及遺傳學(xué)說吻合，而且其術(shù)

23、語也常常仿效生物學(xué)的術(shù)語。 遺傳算法的運算基礎(chǔ)是字符串，它就相當(dāng)于生物學(xué)中的染色體。 字符串由一系列字符組成，每個字符都有特定的含義，反應(yīng)所解決問題的某個特征，這就相當(dāng)于基因，即染色體DNA的片段。 在進行交換、突變操作時，遺傳算法只涉及到字符串某些片段，這就類似于遺傳過程只涉及某些基因而不是整個染色體。,5、遺傳算法的生物學(xué)含義,33,遺傳學(xué)很注重等位基因，它是反映生物某一形態(tài)所對應(yīng)的

24、基因。在遺傳算法的字符串中，每個字符都反映問題的某一特性，這也就相當(dāng)于等位基因，至于等位基因的位置，也就相當(dāng)于該字符在字符串中的位置。 在遺傳學(xué)中，雜交產(chǎn)生的子代里顯現(xiàn)出親本的性狀，稱作顯性性狀，未顯現(xiàn)出來的親本性狀叫作隱性性狀。控制顯性性狀的基因是顯性基因，用大寫英文字母表示?？刂齐[性性狀的基因是隱性基因，用小寫英文字母表示。在遺傳算法中，模仿這種大、小字母表達方式，對顯性基因和隱性基因采取不同的操作。,5、遺傳算法的生物學(xué)含

25、義,34,生物學(xué)術(shù)語在遺傳算法中的對應(yīng)意義如下表。,5、遺傳算法的生物學(xué)含義,35,根據(jù)前面所講的示例，可以看出遺傳算法的實施過程中包括編碼、產(chǎn)生群體、計算適應(yīng)度、復(fù)制、交換、突變等操作。 遺傳算法的詳細流程如下圖。,6、遺傳算法的工作步驟,36,Gen：遺傳（迭代）的代次。表明遺傳算法反復(fù)執(zhí)行的次數(shù)，即已產(chǎn)生群體的代次數(shù)目。M：群體中擁有的個體數(shù)目。i：已處理個體的累計數(shù)，當(dāng)i等于M，表明這一代的個體已全部處

26、理完畢，需要轉(zhuǎn)入下一代群體。交叉率 Pc 就是參加交叉運算的染色體個數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.4～0.99。變異率 Pm 是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.0001～0.1。復(fù)制概率 Pt 用于控制復(fù)制與淘汰的個體數(shù)目。,37,概括地講，遺傳算法主要執(zhí)行以下四步：（1）隨機地建立由字符串組成的初始群體；（2）計算各個體的適應(yīng)度；（3）根據(jù)遺傳概率

27、，利用下述操作產(chǎn)生新群體： 1）復(fù)制。將已有的優(yōu)良個體復(fù)制后添入新群體中，刪除劣 質(zhì)個體； 2）交換。將選出的兩個個體進行交換，所產(chǎn)生的新個體添 入新群體中。 3）突變。隨機地改變某一個體的某個字符后添入新群體中。（4）反復(fù)執(zhí)行（2）、（3）后，一旦達到終止條件， 選擇最佳個體作為遺傳算法的結(jié)果

28、。,38,遺傳算法的工作對象是字符串，因此對字符串的編碼有兩點要求：一是字符串要反映所研究問題的性質(zhì)；二是字符串的表達要便于計算處理。,遺傳算法關(guān)鍵問題（1）編碼,遺傳算法常常用二進制的0/1字符編碼。當(dāng)問題比較簡單，例如只描述高/低、大/小等布爾型性質(zhì)時，每一位0/1變量就代表一個性質(zhì)。 例如，某事物只涉及到貴/賤、大/小及好/壞時，我們可用三位0/1字符表示，并規(guī)定第1位字符代表貴/賤，第2位字符代表大/小，第3位

29、字符代表好/壞。如111代表貴-大-好，而100代表貴-小-好。,39,當(dāng)問題的性質(zhì)要用數(shù)值描述時，則編碼變成用二進制數(shù)表示十進制數(shù)。例如，用4位0/1字符串表示1 ～ 16。,根據(jù)排列計算，長度（位數(shù)）為L的0/1字符串，可以表達2*2*2‥ ‥2 = 2L 種情況。如果所描述性質(zhì)的最小值不是0時，即性質(zhì)介于Umin～Umax之間，為了減小字符串長度，可以采用映射的方法，用2L個二進制數(shù)表示 [ Umin，Umax ]。這時，令L個0

30、表示Umin ，L個1 表示Umax ，其中L大小取決于（ Umax — Umin ），其余的數(shù)則用線性插值決定。例如，對于[ 16，31 ]的十進制數(shù)，我們可以用4位二進制0/1字符在[ 0000，1111 ]范圍內(nèi)表示。,（1）編碼,Umin 0…0…Umax 1…1,40,對于兼有多種性質(zhì)的問題，可以采用長字符串順序分別表示。例如，可選25位0/1字符串表示物體的體積、重量及顏色，其中前10位數(shù)表示體積

31、量，中間10位數(shù)表示重量，后5位數(shù)表示顏色。 在遺傳算法中，字符串的長度常常是固定的，以便按統(tǒng)一的方式執(zhí)行操作。個別研究者采用不等長的字符串，這時就需要跟蹤記錄，經(jīng)常調(diào)整操作方式，比較煩瑣。,從生物學(xué)角度看，編碼就相當(dāng)于選擇遺傳物質(zhì)，它是研究遺傳的基礎(chǔ)。同樣，在遺傳算法中編碼也是一項基礎(chǔ)性工作。,（1）編碼,41,在遺傳算法中，衡量個體優(yōu)劣的尺度是適應(yīng)度。根據(jù)適應(yīng)度的大小，決定某些個體是繁殖或是消亡。因此，適應(yīng)度是驅(qū)動遺

32、傳算法的動力。從生物學(xué)角度講，適應(yīng)度相當(dāng)于“生存競爭，適者生存”的生物生存能力，在遺傳過程中具有重要意義。,通常，適應(yīng)度是費用、贏利、方差等目標的表達式。在運用過程中可以借鑒以下經(jīng)驗。,（2）適應(yīng)度,42,統(tǒng)一表達形式 在實際問題中，有時希望適應(yīng)度越大越好（如贏利、勞動生產(chǎn)率），有時要求適應(yīng)度越小越好（費用、方差）。為了使遺傳算法有通用性，這種最大、最小值問題宜統(tǒng)一表達。通常都統(tǒng)一按最大值問題處理，而且不

33、允許適應(yīng)度小于0。,對于最小值問題，其適應(yīng)度按下式轉(zhuǎn)換：,f(x)：轉(zhuǎn)換后的適應(yīng)度。g(x)：最小值問題下的適應(yīng)度。Cmax ：足夠大的常數(shù)，可取g(x)的最大值。,（2）適應(yīng)度,43,統(tǒng)一表達形式 為了保證適應(yīng)度不出現(xiàn)負值，對于有可能產(chǎn)生負值的最大值問題，可以采用下式進行變換：,f(x)： 變換后的適應(yīng)度。U(x)：最大值問題下的適應(yīng)度。Cmin ：足夠大的常數(shù)。,（2）適應(yīng)度

34、,44,適應(yīng)度縮放 在執(zhí)行遺傳算法的初始階段，各個個體的適應(yīng)度比較離散，某些個體的適應(yīng)度會很高或很低。對于個別適應(yīng)度很高的個體，會連續(xù)多次被復(fù)制；對于適應(yīng)度很低的個體，會過早被舍棄。這種不正常的取舍，對于個體數(shù)目不多的群體尤為嚴重，會把遺傳算法的搜索引向誤區(qū)，過早地收斂于局部最優(yōu)解。為了克服這種缺陷，需要采用適應(yīng)度縮放技術(shù)，將適應(yīng)度按下式變換：,f ' ： 縮放后的適應(yīng)度。f：原來的適應(yīng)度。a、b ：系數(shù)

35、。,f '= a*f + b,利用這種縮放技術(shù)，縮?。ǚ糯螅┰瓉碜畲螅ㄗ钚。┑倪m應(yīng)度，從而可以減弱離散現(xiàn)象。,（2）適應(yīng)度,45,復(fù)制是遺傳算法的基本算子，它將優(yōu)良個體在下一代新群體中繁殖，體現(xiàn)了“適者生存”的自然選擇原則。 個體是否被復(fù)制的依據(jù)是其適應(yīng)度的大小，適應(yīng)度大者被復(fù)制，小者被淘汰，使新群體中的個體總數(shù)與原來群體相同。 在遺傳算法中，常常采用J.Holland教授提出的輪盤賭方式選擇復(fù)制

36、對象。,（3）復(fù)制,46,表中第一行說明有10個個體參與選擇，第二行表示各個體的適應(yīng)度，第三行標記適應(yīng)度的累計值，總值為76。然后，在[ 0，76 ]區(qū)間內(nèi)產(chǎn)生均勻分布的隨機數(shù)，如第四行所示。依次序?qū)⒌谌械睦塾嬤m應(yīng)度與隨機數(shù)相比較，其值大于或等于隨機數(shù)的第一個個體列為入選的復(fù)制對象。例如，第一個隨機數(shù)是23，除了1號、2號個體外，其余個體的累計適應(yīng)度均大于23，然而3號個體累計值為27，是第一個大于23的個體，所以它入選。,輪盤選擇示

37、例：,（3）復(fù)制,47,（1）依次累計群體內(nèi)各個體的適應(yīng)度，得相應(yīng)的累計值Si，最后一個累計值為Sn；（2）在[ 0，Sn ]區(qū)間內(nèi)產(chǎn)生均勻分布的隨機數(shù)R；（3）依次用Si與R相比較，第一個出現(xiàn)Si大于或等于R的個體i被選為復(fù)制對象；（4）重復(fù)（2）、（3），直至滿足所需要的個體數(shù)目。,上述選擇過程，可描述如下：,（3）復(fù)制,48,因此，適應(yīng)度fi越大， △Si的距離越大，隨機數(shù)落在這個區(qū)間的可能性越大，第i個個體被選中的機會也越

38、多。如下圖所示。,表面上看，復(fù)制個體的選擇是隨機的。但是，選擇時是依據(jù)相鄰兩個適應(yīng)度累計值的差值△ Si ：,△Si = Si – Si-1 = fi,fi表示第i個個體的適應(yīng)度,（3）復(fù)制,49,輪盤（賭）選擇原理,圖中的指針固定不動，外圈的圓環(huán)可以任意轉(zhuǎn)動，圓環(huán)中每段對應(yīng)于適應(yīng)度的大小。從統(tǒng)計意義上講，適應(yīng)度大的個體被復(fù)制的機會越大。當(dāng)然，適應(yīng)度小的個體盡管被復(fù)制的概率小，但仍有可能被“破格”復(fù)制，這樣就增加個體的多樣性，便于執(zhí)行交

39、換及突變。所以，輪盤選擇方法既體現(xiàn)“適者生存”原則，又保持個體性態(tài)多種多樣。,（3）復(fù)制,50,選擇復(fù)制個體的隨機方法還有別的形式，不過輪盤選擇法是最常用的方法。,每代群體中，被復(fù)制的個體數(shù)目由復(fù)制概率Pt控制， Pt常取0.1～0.2，也就是說，群體中有10%個體被復(fù)制，相應(yīng)地有10%個體被淘汰，以保持群體大小。,（3）復(fù)制,51,下表是個體兩兩交換的示例，字符串內(nèi)的下橫線代表交換點的位置，交換點及其后面的字符串兩兩互換。,在遺傳算法

40、中，交換是產(chǎn)生新個體的主要手段。它仿照生物學(xué)中雜交的原理，將兩個個體（染色體）的部分字符（基因）互相交換。,（4）交換,52,執(zhí)行交換的個體是隨機選擇的。首先，要確定交換的概率Pc，大致為0.5～0.8左右。這就是說，約50%～80%的個體要執(zhí)行交換。然后，采用上述輪盤選擇的方法，按適應(yīng)度大小選擇被交換的個體，依次兩兩進行交換。 交換點的選擇也是隨機的。假設(shè)字符串長度為L，則在[ 0，L ]區(qū)間內(nèi)產(chǎn)生隨機整數(shù)，該整數(shù)便是

41、交換點的位置。需要注意的是，交換點不能選在第一個字符上。因此，長度為L的字符串，可供選擇的交換點為（L-1）個。 根據(jù)交換點數(shù)目的不同，可分為一點交換和多點交換，前者只選取一個交換點，該點之后的字符全部參加交換。后者選擇兩個或多個交換點，只有兩點間的字符才參加交換。當(dāng)字符串長度大時，常采用兩點交換。此外還有多點交換，即對長字符串實行多段交換。,（4）交換,53,通過交換，子代的字符串不同于親代。有時，這種差別很明顯，如表

42、中的第一組個體，被交換部分完全不一樣。有時，這種差別卻不大，如表中的第二組個體，被交換的三個字符中只有最后一個字符發(fā)生變化。后一種情況說明交換后產(chǎn)生的個體，其性態(tài)變化不大。盡管如此，交換仍然是遺傳算法產(chǎn)生新個體的主要手段。正是有了交換操作，群體的性態(tài)才多種多樣。,傳統(tǒng)的優(yōu)化算法，例如動態(tài)規(guī)劃法、個體性態(tài)不能增添，只能在原有的個體群體中擇優(yōu)，從而限制了搜索尋優(yōu)的范圍。因此，可以說，如果沒有交換，遺傳算法就失去了其優(yōu)越性。,（4）交換,54

43、,突變是遺傳算法中產(chǎn)生新個體的另一種方法，它是將某一個體的某一位字符進行補運算，使0變?yōu)?，或使1變?yōu)?。,突變個體的選擇以及突變位置的確定，都是采用隨機的方法產(chǎn)生。首先，確定突變概率Pm， Pm通常較小，約為0.001～0.01。也就是說，1000個字符中有1～10個發(fā)生突變。然后，針對每個字符在[ 0，1 ]之間產(chǎn)生三位有效數(shù)的均勻分布隨機數(shù)。若Pm = 0.008，凡是隨機數(shù)小于0.008所對應(yīng)的字符，將實現(xiàn)突變。示例如下：,（5

44、）突變,55,表中有三個字符長度為4的舊個體。對應(yīng)每個字符，依次產(chǎn)生[ 0，1 ]區(qū)間均勻分布的隨機數(shù)12個。表中只有2號個體的第3個字符以及3號個體的第4個字符需要發(fā)生突變，因為它們對應(yīng)的隨機數(shù)小于0.008。,（5）突變,56,隨機確定突變的位置后，執(zhí)行突變的方法有兩種。一種是直接產(chǎn)生突變，將表中的2號和3號舊個體分別改寫作1110及0011。另一種方法，按50%的概率隨機產(chǎn)生新字符0或1。表中2號個體產(chǎn)生的新字符為0，與需要突變

45、的第三行字符恰好一樣，因此新個體等同于舊個體。表中3號個體產(chǎn)生的新字符（1）不同于待突變的原來字符（0），因此新個體不同于舊個體。很明顯，后一種突變方法的突變概率僅為前一種方法的50%。通常建議采用后一種方法，增加突變的隨機性。,（5）突變,57,還有一種執(zhí)行突變的方法，是根據(jù)給定的概率Pm1。隨機選擇突變的個體。當(dāng)被突變的個體選中后，在字長范圍內(nèi)用均勻分布的隨機數(shù)選擇突變的字符，使該個體發(fā)生突變。然而，這時的概率Pm1 ，不同于突變概

46、率Pm，后者是針對字符而言，前者是針對個體。遺傳算法中討論的正是字符的突變概率Pm，兩者間的關(guān)系與字長L有關(guān)。 盡管突變和交換都能產(chǎn)生新個體，但是在遺傳算法中，交換的作用遠比突變重要。,（5）突變,58,遺傳算法是一種反復(fù)迭代的搜索方法，它通過多次進化逐漸逼近最優(yōu)解而不是恰好等于最優(yōu)解，因此需要確定終止條件。 其一, 最常用的終止方法是規(guī)定遺傳（迭代）的代次。剛開始時，迭代次數(shù)小一些，如規(guī)定100次。然后視

47、情況逐漸增加次數(shù)，可達到上千次。,（6）終止條件,59,當(dāng)目標函數(shù)是方差這一類有最優(yōu)目標值的問題時，可采用控制偏差的方法實現(xiàn)終止。一旦遺傳算法得出的目標函數(shù)值（適應(yīng)度）與實際目標值之差小于允許值后，算法終止，即：,f(x) ： 遺傳算法得出的目標函數(shù)值。f * ：實際目標值?！?：足夠小的數(shù)。,| f(x) – f * | ≤△,（6）終止條件,60,第三種終止方法是檢查適應(yīng)度的變化。在遺傳算法后期，一旦最優(yōu)個體的適應(yīng)度沒有變化或變

48、化很小時，即令計算終止。,遺傳算法的另一個重要參數(shù)是每代群體中的個體數(shù)。很明顯，個體數(shù)目越多，搜索范圍越廣，容易獲取全局最優(yōu)解。然而個體數(shù)目太多，每次迭代時間也長。通常，個體數(shù)目可取100-1000之間。,（6）終止條件,7 遺傳算法的應(yīng)用領(lǐng)域（1）函數(shù)優(yōu)化。 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進行性能評價的常用算例。尤其是對非線性、多模型、多目標的函數(shù)優(yōu)化問題，采用其他優(yōu)化方法較難求解，而遺傳算法卻可以得到較好的

49、結(jié)果。,（2）組合優(yōu)化。 隨著問題的增大，組合優(yōu)化問題的搜索空間也急劇擴大，采用傳統(tǒng)的優(yōu)化方法很難得到最優(yōu)解。遺傳算法是尋求這種滿意解的最佳工具。例如，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用。,（3）生產(chǎn)調(diào)度問題 在很多情況下，采用建立數(shù)學(xué)模型的方法難以對生產(chǎn)調(diào)度問題進行精確求解。在現(xiàn)實生產(chǎn)中多采用一些經(jīng)驗進行調(diào)度。遺傳算法是解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)

50、車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。,（4）自動控制。 在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已經(jīng)在其中得到了初步的應(yīng)用。例如，利用遺傳算法進行控制器參數(shù)的優(yōu)化、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、基于遺傳算法的參數(shù)辨識、基于遺傳算法的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化和權(quán)值學(xué)習(xí)等。,（5）機器人 例如，遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和

51、應(yīng)用。（6）圖像處理 遺傳算法可用于圖像處理過程中的掃描、特征提取、圖像分割等的優(yōu)化計算。目前遺傳算法已經(jīng)在模式識別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。,利用遺傳算法求Rosenbrock函數(shù)的極大值,8 遺傳算法應(yīng)用--求函數(shù)極值,用長度為10位的二進制編碼串來分別表示兩個變量x1,x2。10位二進制編碼串可以表示從0到1023之間的1024個不同的數(shù)，故將x1,x2的定義域離散化為1023個均等的區(qū)域，包括兩個端

52、點在內(nèi)共有1024個不同的離散點。 從離散點-2.048到離散點2.048 ，分別對應(yīng)于從0000000000(0)到1111111111(1023)之間的二進制編碼。,編碼,將x1,x2分別表示的兩個10位長的二進制編碼串連接在一起，組成一個20位長的二進制編碼串，它就構(gòu)成了這個函數(shù)優(yōu)化問題的染色體編碼方法。使用這種編碼方法，解空間和遺傳算法的搜索空間就具有一一對應(yīng)的關(guān)系。例如：

53、 表示一個個體的基因型，其中前10位表示x1，后10位表示x2。,確定解碼方法：解碼時需要將20位長的二進制編碼串切斷為兩個10位長的二進制編碼串，然后分別將它們轉(zhuǎn)換為對應(yīng)的十進制整數(shù)代碼，分別記為y1和y2。 依據(jù)個體編碼方法和對定義域的離散化方法可知，將代碼y轉(zhuǎn)換為變量x的解碼公式為 例如，對個體,它由兩個代碼所組成 上述兩個代碼經(jīng)過

54、解碼后，可得到兩個實際的值確定個體評價方法：由于Rosenbrock函數(shù)的值域總是非負的，并且優(yōu)化目標是求函數(shù)的最大值，故可將個體的適應(yīng)度直接取為對應(yīng)的目標函數(shù)值，即,選個體適應(yīng)度的倒數(shù)作為目標函數(shù)設(shè)計遺傳算子：選擇運算使用比例選擇算子，交叉運算使用單點交叉算子，變異運算使用基本位變異算子。確定遺傳算法的運行參數(shù)：群體大小M=80，終止進化代數(shù)G=100，交叉概率Pc=0.60，變異概率Pm=0.10。,采用上述方法進行仿真