遺傳算法

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

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

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

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

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

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

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

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

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

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

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

12、法，假設(shè)得出擁有四個(gè)個(gè)體的初始群體，即：01101，11000，01000，10011。x值相應(yīng)為13，24，8，19。,19,（2）計(jì)算適應(yīng)度 衡量字符串（染色體）好壞的指標(biāo)是適應(yīng)度，它也就是遺傳算法的目標(biāo)函數(shù)。 本例中適應(yīng)度比較簡(jiǎn)單，用x2計(jì)算。,表中還列出了當(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）計(jì)算適應(yīng)度 表中第6列的 f(xi)/f 表示每個(gè)個(gè)體的相對(duì)適應(yīng)度，它反映了個(gè)體之間的相對(duì)優(yōu)劣性。如2號(hào)個(gè)體的 f(xi)/f 值最高（1.97），為優(yōu)良個(gè)體，3號(hào)個(gè)體最低（0.22），為不良個(gè)體。,21,（3）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、,44,適應(yīng)度縮放 在執(zhí)行遺傳算法的初始階段，各個(gè)個(gè)體的適應(yīng)度比較離散，某些個(gè)體的適應(yīng)度會(huì)很高或很低。對(duì)于個(gè)別適應(yīng)度很高的個(gè)體，會(huì)連續(xù)多次被復(fù)制；對(duì)于適應(yīng)度很低的個(gè)體，會(huì)過早被舍棄。這種不正常的取舍，對(duì)于個(gè)體數(shù)目不多的群體尤為嚴(yán)重，會(huì)把遺傳算法的搜索引向誤區(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)良個(gè)體在下一代新群體中繁殖，體現(xiàn)了“適者生存”的自然選擇原則。 個(gè)體是否被復(fù)制的依據(jù)是其適應(yīng)度的大小，適應(yīng)度大者被復(fù)制，小者被淘汰，使新群體中的個(gè)體總數(shù)與原來群體相同。 在遺傳算法中，常常采用J.Holland教授提出的輪盤賭方式選擇復(fù)制

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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