遺傳算法上課講義

人工智能張曉偉x.w.zhang@126.com15.3進(jìn)化計(jì)算進(jìn)化計(jì)算（EvolutionaryComputation,EC）是在達(dá)爾文（Darwin）的進(jìn)化論和孟德爾（Mendel）的遺傳變異理論的基礎(chǔ)上產(chǎn)生的一種在基因和種群層次上模擬自然界生物進(jìn)化過程與機(jī)制的問題求解技術(shù)。它主要包括遺傳算法（GeneticAlgorithm，GA）進(jìn)化策略（EvolutionaryStrategy,ES）進(jìn)化規(guī)劃（EvolutionaryProgramming,EP）遺傳規(guī)劃（GeneticProgramming,GP）

四大分支。

其中，第一個分支是進(jìn)化計(jì)算中最初形成的一種具有普遍影響的模擬進(jìn)化優(yōu)化算法。因此我們主要討論遺傳算法。2進(jìn)化計(jì)算的生物學(xué)基礎(chǔ)

自然界生物進(jìn)化過程是進(jìn)化計(jì)算的生物學(xué)基礎(chǔ)，它主要包括遺傳(Heredity)、變異(Mutation)和進(jìn)化(Evolution)理論。進(jìn)化論

進(jìn)化是指在生物延續(xù)生存過程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良的這種生命現(xiàn)象。遺傳和變異是生物進(jìn)化的兩種基本現(xiàn)象，優(yōu)勝劣汰、適者生存是生物進(jìn)化的基本規(guī)律。長頸鹿的祖先當(dāng)中，脖子有長有短。脖子短的無法和脖子長的競爭食物，漸漸被淘汰了。幾代之后，所有的長頸鹿都是長頸的。4

達(dá)爾文的自然選擇學(xué)說認(rèn)為：在生物進(jìn)化中，一種基因有可能發(fā)生變異而產(chǎn)生出另一種新的生物基因。這種新基因?qū)⒁罁?jù)其與生存環(huán)境的適應(yīng)性而決定其增殖能力。一般情況下，適應(yīng)性強(qiáng)的基因會不斷增多，而適應(yīng)性差的基因則會逐漸減少。通過這種自然選擇，物種將逐漸向適應(yīng)于生存環(huán)境的方向進(jìn)化，甚至?xí)葑兂蔀榱硪粋€新的物種，而那些不適應(yīng)于環(huán)境的物種將會逐漸被淘汰。達(dá)爾文，進(jìn)化論之父5遺傳理論

遺傳是指父代（或親代）利用遺傳基因?qū)⒆陨淼幕蛐畔鬟f給下一代（或子代)，使子代能夠繼承其父代的特征或性狀的這種生命現(xiàn)象。正是由于遺傳的作用，自然界才能有穩(wěn)定的物種?！胺N瓜得瓜，種豆得豆”“龍生龍，鳳生鳳，老鼠生兒打地洞”孟德爾（1822—1884），奧地利人，遺傳學(xué)的奠基人。6在自然界，構(gòu)成生物基本結(jié)構(gòu)與功能的單位是細(xì)胞（Cell）。細(xì)胞中含有一種包含著所有遺傳信息的復(fù)雜而又微小的絲狀化合物，人們稱其為染色體（Chromosome）。在染色體中，遺傳信息由基因（Gene）所組成，基因決定著生物的性狀，是遺傳的基本單位。染色體的形狀是一種雙螺旋結(jié)構(gòu)，構(gòu)成染色體的主要物質(zhì)叫做脫氧核糖核酸(DNA)，每個基因都在DNA長鏈中占有一定的位置。一個細(xì)胞中的所有染色體所攜帶的遺傳信息的全體稱為一個基因組(Genome)。細(xì)胞在分裂過程中，其遺傳物質(zhì)DNA通過復(fù)制轉(zhuǎn)移到新生細(xì)胞中，從而實(shí)現(xiàn)了生物的遺傳功能。7變異理論

變異是指子代和父代之間，以及子代的各個不同個體之間產(chǎn)生差異的現(xiàn)象。變異是生物進(jìn)化過程中發(fā)生的一種隨機(jī)現(xiàn)象，是一種不可逆過程，在生物多樣性方面具有不可替代的作用。引起變異的主要原因有以下兩種：雜交

指有性生殖生物在繁殖下一代時兩個同源染色體之間的交配重組，即兩個染色體在某一相同處的DNA被切斷后再進(jìn)行交配重組，形成兩個新的染色體。復(fù)制差錯

指在細(xì)胞復(fù)制過程中因DNA上某些基因結(jié)構(gòu)的隨機(jī)改變而產(chǎn)生出新的染色體。龍生九子，九子九樣85.3.1進(jìn)化計(jì)算概述——產(chǎn)生與發(fā)展進(jìn)化計(jì)算自20世紀(jì)50年代以來，其發(fā)展過程大致可分為三個階段。萌芽階段（'50年代后期到'70年代中期）20世紀(jì)50年代后期，一些生物學(xué)家在研究如何用計(jì)算機(jī)模擬生物遺傳系統(tǒng)中，產(chǎn)生了遺傳算法的基本思想，并于1962年由美國密執(zhí)安（Michigan）大學(xué)霍蘭德（Holland）提出。1965年德國數(shù)學(xué)家雷切伯格（Rechenberg）等人提出了一種只有單個個體參與進(jìn)化，并且僅有變異這一種進(jìn)化操作的進(jìn)化策略。同年，美國學(xué)者弗格爾（Fogel）提出了一種具有多個個體和僅有變異一種進(jìn)化操作的進(jìn)化規(guī)劃。1969年美國密執(zhí)安（Michigan）大學(xué)的霍蘭德（Holland）提出了系統(tǒng)本身和外部環(huán)境相互協(xié)調(diào)的遺傳算法。至此，進(jìn)化計(jì)算的三大分支基本形成。9成長階段（'年代中期到'80年代后期）

1975年，霍蘭德出版專著《自然和人工系統(tǒng)的適應(yīng)性（AdaptationinNaturalandArtificialSystem）》，全面介紹了遺傳算法。同年，德國學(xué)者施韋費(fèi)爾（Schwefel）在其博士論文中提出了一種由多個個體組成的群體參與進(jìn)化的，并且包括了變異和重組這兩種進(jìn)化操作的進(jìn)化策略。1989年，霍蘭德的學(xué)生戈?duì)柕虏瘢℅oldberg）博士出版專著《遺傳算法——搜索、優(yōu)化及機(jī)器學(xué)習(xí)（GeneticAlgorithm——inSearchOptimizationandMachineLearning）》，使遺傳算法得到了普及與推廣。Prof.Holland電氣工程、計(jì)算機(jī)科學(xué)領(lǐng)域?qū)＜疫z傳算法提出者10發(fā)展階段（'90年代至今）1989年，美國斯坦福（Stanford）大學(xué)的科扎（Koza）提出了遺傳規(guī)劃的新概念，并于1992年出版了專著《遺傳規(guī)劃----應(yīng)用自然選擇法則的計(jì)算機(jī)程序設(shè)計(jì)（GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection）》該書全面介紹了遺傳規(guī)劃的基本原理及應(yīng)用實(shí)例，標(biāo)志著遺傳規(guī)劃作為計(jì)算智能的一個分支已基本形成。進(jìn)入20世紀(jì)90年代以來，進(jìn)化計(jì)算得到了眾多研究機(jī)構(gòu)和學(xué)者的高度重視，新的研究成果不斷出現(xiàn)、應(yīng)用領(lǐng)域不斷擴(kuò)大。目前，進(jìn)化計(jì)算已成為人工智能領(lǐng)域的又一個新的研究熱點(diǎn)。115.3.2遺傳算法——研究內(nèi)容性能分析。遺傳算法的性能分析一直都是遺傳算法研究領(lǐng)域中最重要的主題之一。在遺傳算法中，群體規(guī)模、雜交和變異算子的概率等控制參數(shù)的選取是非常困難的，同時它們又是必不可少的實(shí)驗(yàn)參數(shù)。遺傳算法還存在一個過早收斂問題，也就是說遺傳算法的最后結(jié)果并不總是達(dá)到最優(yōu)解，怎樣阻止過早收斂問題是人們感興趣的問題之一。另外，為了拓廣遺傳算法的應(yīng)用范圍，人們在不斷研究新的遺傳染色體表示法和新的遺傳算子。并行遺傳算法。遺摶算法在操作上具有高度的并行性，只要通過保持多個群體和恰當(dāng)?shù)乜刂迫后w間的相互作用來模擬并行執(zhí)行過程，即使不使用并行計(jì)算機(jī)，我們也能提高算法的執(zhí)行效率。分類系統(tǒng)。分類系統(tǒng)屬于基于遺傳算法的機(jī)器學(xué)習(xí)中的一類型，它包括一個簡單的基于串規(guī)則的并行生成子系統(tǒng)、規(guī)則評價子系統(tǒng)和遺傳算法子系統(tǒng)。目前，分類系統(tǒng)是遺傳算法研究中的一個非?；钴S的領(lǐng)域125.3.2遺傳算法——基本概念遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個體，并通過雜交、變異來產(chǎn)生新一代種群，如此逐代進(jìn)化，直到滿足目標(biāo)為止。遺傳算法所涉及到的基本概念主要有以下幾個：種群（Population）：種群是指用遺傳算法求解問題時，初始給定的多個解的集合。遺傳算法的求解過程是從這個子集開始的。個體（Individual）：個體是指種群中的單個元素，它通常由一個用于描述其基本遺傳結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)來表示。例如，可以用0、1組成的長度為l的串來表示個體。染色體（Chromos）：染色體是指對個體進(jìn)行編碼后所得到的編碼串。染色體中的每1位稱為基因，染色體上由若干個基因構(gòu)成的一個有效信息段稱為基因組。適應(yīng)度（Fitness）函數(shù)：適應(yīng)度函數(shù)是一種用來對種群中各個個體的環(huán)境適應(yīng)性進(jìn)行度量的函數(shù)。其函數(shù)值是遺傳算法實(shí)現(xiàn)優(yōu)勝劣汰的主要依據(jù)遺傳操作（GeneticOperator）：遺傳操作是指作用于種群而產(chǎn)生新的種群的操作。標(biāo)準(zhǔn)的遺傳操作包括以下三種基本形式：選擇（Selection）交叉（Crosssover）變異（Mutation）

13遺傳算法與自然進(jìn)化的比較自然界染色體基因等位基因(allele)染色體位置(locus)基因型(genotype)表型(phenotype)遺傳算法字符串字符，特征特征值字符串位置結(jié)構(gòu)參數(shù)集譯碼結(jié)構(gòu)145.3.2遺傳算法——基本結(jié)構(gòu)遺傳算法主要由染色體編碼、初始種群設(shè)定、適應(yīng)度函數(shù)設(shè)定、遺傳操作設(shè)計(jì)等幾大部分所組成，其算法主要內(nèi)容和基本步驟可描述如下：

(1)選擇編碼策略，將問題搜索空間中每個可能的點(diǎn)用相應(yīng)的編碼策略表示出來，即形成染色體；(2)定義遺傳策略，包括種群規(guī)模N，交叉、變異方法，以及選擇概率Pr、交叉概率Pc、變異概率Pm等遺傳參數(shù)；(3)令t=0，隨機(jī)選擇N個染色體初始化種群P(0)；(4)定義適應(yīng)度函數(shù)f（f>0）；(5)計(jì)算P(t)中每個染色體的適應(yīng)值；(6)t=t+1；(7)運(yùn)用選擇算子，從P(t-1)中得到P(t)；(8)對P(t)中的每個染色體，按概率Pc參與交叉；(9)對染色體中的基因，以概率Pm參與變異運(yùn)算；(10)判斷群體性能是否滿足預(yù)先設(shè)定的終止標(biāo)準(zhǔn)，若不滿足則返回(5)。15計(jì)算種群中個體的適應(yīng)度并進(jìn)行評價滿足終止條件嗎？終止選擇交叉變異Y基本遺傳算法的算法流程圖編碼和生成初始種群N選擇165.3.2遺傳算法——遺傳編碼常用的遺傳編碼算法有二進(jìn)制碼、格雷碼（GrayCode）、實(shí)數(shù)編碼和字符編碼等。二進(jìn)制編碼（Binaryencoding）二進(jìn)制編碼是將原問題的結(jié)構(gòu)變換為染色體的位串結(jié)構(gòu)。在二進(jìn)制編碼中，首先要確定二進(jìn)制字符串的長度l，該長度與變量的定義域和所求問題的計(jì)算精度有關(guān)。例假設(shè)變量x的定義域?yàn)閇5，10]，要求的計(jì)算精度為10E-5，則需要將[5，10]至少分為600000個等長小區(qū)間，每個小區(qū)間用一個二進(jìn)制串表示。于是，串長至少等于20，原因是：524288=219<600000<220=1048576這樣，對應(yīng)于區(qū)間[5，10]內(nèi)滿足精度要求的每個值x，都可用一個20位編碼的二進(jìn)制串<b19,b18,…,b0>來表示。二進(jìn)制編碼存在的主要缺點(diǎn)是漢明（Hamming）懸崖。例如，7和8的二進(jìn)制數(shù)分別為0111和1000，當(dāng)算法從7改進(jìn)到8時，就必須改變所有的位。

17格雷編碼（Grayencoding）格雷編碼是對二進(jìn)制編碼進(jìn)行變換后所得到的一種編碼方法。這種編碼方法要求兩個連續(xù)整數(shù)的編碼之間只能有一個碼位不同，其余碼位都是完全相同的。它有效地解決了漢明懸崖問題，其基本原理如下：設(shè)有二進(jìn)制串b1,b2,…,bn，對應(yīng)的格雷串為a1,a2,…,an，則從二進(jìn)制編碼到格雷編碼的變換為：其中，⊕表示模2加法。而從一個格雷串到二進(jìn)制串的變換為：例十進(jìn)制數(shù)7和8的二進(jìn)制編碼分別為0111和1000，而其格雷編碼分別為0100和1100。18實(shí)數(shù)編碼（Realencoding）實(shí)數(shù)編碼是將每個個體的染色體都用某一范圍的一個實(shí)數(shù)（浮點(diǎn)數(shù)）來表示，其編碼長度等于該問題變量的個數(shù)。這種編碼方法是將問題的解空間映射到實(shí)數(shù)空間上，然后在實(shí)數(shù)空間上進(jìn)行遺傳操作。由于實(shí)數(shù)編碼使用的是變量的真實(shí)值，因此這種編碼方法也叫做真值編碼方法。實(shí)數(shù)編碼適應(yīng)于那種多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題。195.3.2遺傳算法——適應(yīng)度函數(shù)適應(yīng)度函數(shù)是一個用于對個體的適應(yīng)性進(jìn)行度量的函數(shù)。通常，一個個體的適應(yīng)度值越大，它被遺傳到下一代種群中的概率也就越大。常用的適應(yīng)度函數(shù)在遺傳算法中，有許多計(jì)算適應(yīng)度的方法，其中最常用的適應(yīng)度函數(shù)有以下兩種：原始適應(yīng)度函數(shù)它是直接將待求解問題的目標(biāo)函數(shù)f(x)定義為遺傳算法的適應(yīng)度函數(shù)。例如，在求解極值問題

時，f(x)即為x的原始適應(yīng)度函數(shù)。采用原始適應(yīng)度函數(shù)的優(yōu)點(diǎn)是能夠直接反映出待求解問題的最初求解目標(biāo)，其缺點(diǎn)是有可能出現(xiàn)適應(yīng)度值為負(fù)的情況。

20標(biāo)準(zhǔn)適應(yīng)度函數(shù)在遺傳算法中，一般要求適應(yīng)度函數(shù)非負(fù)，并其適應(yīng)度值越大越好。這就往往需要對原始適應(yīng)函數(shù)進(jìn)行某種變換，將其轉(zhuǎn)換為標(biāo)準(zhǔn)的度量方式，以滿足進(jìn)化操作的要求，這樣所得到的適應(yīng)度函數(shù)被稱為標(biāo)準(zhǔn)適應(yīng)度函數(shù)fNormal(x)。極小化問題對極小化問題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為其中，fmax

(x)是原始適應(yīng)函數(shù)f(x)的一個上界。如果fmax

(x)未知，則可用當(dāng)前代或到目前為止各演化代中的f(x)的最大值來代替?？梢?，fmax

(x)是會隨著進(jìn)化代數(shù)的增加而不斷變化的。

21極大化問題對極大化問題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為其中，fmin(x)是原始適應(yīng)函數(shù)f(x)的一個下界。如果fmin(x)未知，則可用當(dāng)前代或到目前為止各演化代中的f(x)的最小值來代替。

22適應(yīng)度函數(shù)的加速變換在某些情況下，適應(yīng)度函數(shù)在極值附近的變化可能會非常小，以至于不同個體的適應(yīng)值非常接近，使得難以區(qū)分出哪個染色體更占優(yōu)勢。對此，最好能定義新的適應(yīng)度函數(shù)，使該適應(yīng)度函數(shù)既與問題的目標(biāo)函數(shù)具有相同的變化趨勢，又有更快的變化速度。適應(yīng)度函數(shù)的加速變換有兩種基本方法線性加速適應(yīng)度函數(shù)的定義如下：其中，

是加速轉(zhuǎn)換前的適應(yīng)度函數(shù)；是加速轉(zhuǎn)換后的適應(yīng)度函數(shù)；α和β是轉(zhuǎn)換系數(shù)。非線性加速冪函數(shù)變換方法指數(shù)變換方法23對于的選擇應(yīng)滿足如下條件：保證夫代中那些適應(yīng)度接近于平均適應(yīng)度個體，能夠保證有相當(dāng)數(shù)量的個體被遺傳到下一代中M是指將當(dāng)前的最大適應(yīng)度放大為其平均值的M倍，這樣通過選擇適當(dāng)?shù)腗值可以拉開不同染色體間的適應(yīng)度值的差距245.3.2基本遺傳操作——選擇遺傳算法中的基本遺傳操作包括選擇、交叉和變異3種，而每種操作又包括多種不同的方法，下面分別對它們進(jìn)行介紹。選擇操作選擇（Selection）操作是指根據(jù)選擇概率按某種策略從當(dāng)前種群中挑選出一定數(shù)目的個體，使它們能夠有更多的機(jī)會被遺傳到下一代中。常用的選擇策略可分為比例選擇、排序選擇和競技選擇三種類型。比例選擇比例選擇方法（ProportionalModel）的基本思想是：各個個體被選中的概率與其適應(yīng)度大小成正比。常用的比例選擇策略包括：輪盤賭選擇、繁殖池選擇25輪盤賭選擇輪盤賭選擇法又被稱為轉(zhuǎn)盤賭選擇法或輪盤選擇法。在這種方法中，個體被選中的概率取決于該個體的相對適應(yīng)度。而相對適應(yīng)度的定義為其中，P(xi)是個體xi的相對適應(yīng)度，即個體xi被選中的概率；f(xi)是個體xi的原始適應(yīng)度；是種群的累加適應(yīng)度。輪盤賭選擇算法的基本思想是：根據(jù)每個個體的選擇概率P(xi)將一個圓盤分成N個扇區(qū)，其中第i個扇區(qū)的中心角為：26并再設(shè)立一個固定指針。當(dāng)進(jìn)行選擇時，可以假想轉(zhuǎn)動圓盤，若圓盤靜止時指針指向第i個扇區(qū)，則選擇個體i。從統(tǒng)計(jì)角度看，個體的適應(yīng)度值越大，其對應(yīng)的扇區(qū)的面積越大，被選中的可能性也越大。這種方法有點(diǎn)類似于發(fā)放獎品使用的輪盤，并帶有某種賭博的意思，因此亦被稱為輪盤賭選擇。P(x1)P(x2)P(xN)P(xi)輪盤賭選擇……275.3.2基本遺傳操作——交叉交叉操作交叉（Crossover）操作是指按照某種方式對選擇的父代個體的染色體的部分基因進(jìn)行交配重組，從而形成新的個體。交配重組是自然界中生物遺傳進(jìn)化的一個主要環(huán)節(jié)，也是遺傳算法中產(chǎn)生新的個體的最主要方法。根據(jù)個體編碼方法的不同，遺傳算法中的交叉操作可分為二進(jìn)制交叉和實(shí)值交叉兩種類型。二進(jìn)制交叉二進(jìn)制交叉（BinaryValuedCrossover）是指二進(jìn)制編碼情況下所采用的交叉操作，它主要包括單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉和均勻交叉等方法。28單點(diǎn)交叉單點(diǎn)交叉也稱簡單交叉，它是先在兩個父代個體的編碼串中隨機(jī)設(shè)定一個交叉點(diǎn)，然后對這兩個父代個體交叉點(diǎn)前面或后面部分的基因進(jìn)行交換，并生成子代中的兩個新的個體。假設(shè)兩個父代的個體串分別是：X=x1x2…xkxk+1…xnY=y1y2…ykyk+1…yn隨機(jī)選擇第k位為交叉點(diǎn)，若采用對交叉點(diǎn)后面的基因進(jìn)行交換的方法，但點(diǎn)交叉是將X中的xk+1到xn部分與Y中的yk+1到y(tǒng)n部分進(jìn)行交叉，交叉后生成的兩個新的個體是：X’=x1x2…xk

yk+1…yn

Y’=y1y2…yk

xk+1…xn

例

設(shè)有兩個父代的個體串A=0011

01

和B=1100

10

，若隨機(jī)交叉點(diǎn)為4，則交叉后生成的兩個新的個體是：A’=0011

10

B’=1100

01

29兩點(diǎn)交叉兩點(diǎn)交叉是指先在兩個父代個體的編碼串中隨機(jī)設(shè)定兩個交叉點(diǎn)，然后再按這兩個交叉點(diǎn)進(jìn)行部分基因交換，生成子代中的兩個新的個體。假設(shè)兩個父代的個體串分別是：X=x1x2…xi…xj…xnY=y1y2…yi…yj…,yn隨機(jī)設(shè)定第i、j位為兩個交叉點(diǎn)（其中i<j<n），兩點(diǎn)交叉是將X中的xi+1到xj部分與Y中的yi+1到y(tǒng)j部分進(jìn)行交換，交叉后生成的兩個新的個體是：X’=x1x2…xiyi+1…yjxj+1…xn

Y’=y1y2…yixi+1…xjyj+1…yn例

設(shè)有兩個父代的個體串A=001101和B=110010，若隨機(jī)交叉點(diǎn)為3和5，則交叉后的兩個新的個體是：A’=001011B’=11010030多點(diǎn)交叉多點(diǎn)交是指先隨機(jī)生成多個交叉點(diǎn)，然后再按這些交叉點(diǎn)分段地進(jìn)行部分基因交換，生成子代中的兩個新的個體。假設(shè)交叉點(diǎn)個數(shù)為m，則可將個體串劃分為m+1個分段，其劃分方法是：當(dāng)m為偶數(shù)時，對全部交叉點(diǎn)依次進(jìn)行兩兩配對，構(gòu)成m/2個交叉段。當(dāng)m為奇數(shù)時，對前(m-1)個交叉點(diǎn)依次進(jìn)行兩兩配對，構(gòu)成(m-1)/2個交叉段，而第m個交叉點(diǎn)則按單點(diǎn)交叉方法構(gòu)成一個交叉段。下面以m=3為例進(jìn)行討論。假設(shè)兩個父代的個體串分別是X=x1x2…xi…xj…xk…xn和Y=y1y2…yi…yj…yk…yn，隨機(jī)設(shè)定第i、j、k位為三個交叉點(diǎn)（其中i<j<k<n），則將構(gòu)成兩個交叉段。交叉后生成的兩個新的個體是：X’=x1x2…xiyi+1…yjxj+1…xkyk+1…

yn

Y’=y1y2…yixi+1…xjyj+1…ykxk+1…xn例

設(shè)有兩個父代的個體串A=001101和B=110010，若隨機(jī)交叉點(diǎn)為1、3和5，則交叉后的兩個新的個體是：A’=010100B’=10101131均勻交叉均勻交叉（UniformCrossover）是先隨機(jī)生成一個與父串具有相同長度，并被稱為交叉模版（或交叉掩碼）的二進(jìn)制串，然后再利用該模版對兩個父串進(jìn)行交叉，即將模版中1對應(yīng)的位進(jìn)行交換，而0對應(yīng)的位不交換，依此生成子代中的兩個新的個體。事實(shí)上，這種方法對父串中的每一位都是以相同的概率隨機(jī)進(jìn)行交叉的。例

設(shè)有兩個父代的個體串:A=001101和B=110010，

若隨機(jī)生成的模版T=010011，則交叉后的兩個新的個體是A’=011010和B’=100101。即A：001101B：110010T：010011A’：01111

0

B’：10000

132實(shí)值交叉實(shí)值交叉是在實(shí)數(shù)編碼情況下所采用的交叉操作，主要包括離散交叉和算術(shù)交叉，下面主要討論離散交叉（部分離散交叉和整體離散交叉）。部分離散交叉是先在兩個父代個體的編碼向量中隨機(jī)選擇一部分分量，然后對這部分分量進(jìn)行交換，生成子代中的兩個新的個體。整體交叉則是對兩個父代個體的編碼向量中的所有分量，都以1/2的概率進(jìn)行交換，從而生成子代中的兩個新的個體。以部分離散交叉為例，假設(shè)兩個父代個體的n維實(shí)向量分別是X=x1x2…xi…xk…xn和Y=y1y2…yi…yk…yn，若隨機(jī)選擇對第k個分量以后的所有分量進(jìn)行交換，則生成的兩個新的個體向量是：X’=x1x2…xk

yk+1…ynY’=y1y2…yk

xk+1…xn例

設(shè)有兩個父代個體向量A=201619321826和B=362538122130，若隨機(jī)選擇對第3個分量以后的所有分量進(jìn)行交叉，則交叉后兩個新的個體向量是：A’=201619

12

21

30B’=362538

32

18

26335.3.2基本遺傳操作——變異變異操作變異（Mutation）是指對選中個體的染色體中的某些基因進(jìn)行變動，以形成新的個體。變異也是生物遺傳和自然進(jìn)化中的一種基本現(xiàn)象，它可增強(qiáng)種群的多樣性。遺傳算法中的變異操作增加了算法的局部隨機(jī)搜索能力，從而可以維持種群的多樣性。根據(jù)個體編碼方式的不同，變異操作可分為二進(jìn)制變異和實(shí)值變異兩種類型。二進(jìn)制變異當(dāng)個體的染色體采用二進(jìn)制編碼表示時，其變異操作應(yīng)采用二進(jìn)制變異方法。該變異方法是先隨機(jī)地產(chǎn)生一個變異位，然后將該變異位置上的基因值由“0”變?yōu)椤?”，或由“1”變?yōu)椤?”，產(chǎn)生一個新的個體。例

設(shè)變異前的個體為A=001101，若隨機(jī)產(chǎn)生的變異位置是2，則該個體的第2位由“0”變?yōu)椤?”。變異后的新的個體是A’=011101。34實(shí)值變異當(dāng)個體的染色體采用實(shí)數(shù)編碼表示時，其變異操作應(yīng)采用實(shí)值變異方法。該方法是用另外一個在規(guī)定范圍內(nèi)的隨機(jī)實(shí)數(shù)去替換原變異位置上的基因值，產(chǎn)生一個新的個體。最常用的實(shí)值變異操作有:基于位置的變異方法該方法是先隨機(jī)地產(chǎn)生兩個變異位置，然后將第二個變異位置上的基因移動到第一個變異位置的前面。例

設(shè)選中的個體向量C=201619122130，若隨機(jī)產(chǎn)生的兩個變異位置分別時2和4，則變異后的新的個體向量是：C’=201216192130

基于次序的變異該方法是先隨機(jī)地產(chǎn)生兩個變異位置，然后交換這兩個變異位置上的基因。例

設(shè)選中的個體向量D=201216192130，若隨機(jī)產(chǎn)生的兩個變異位置分別時2和4，則變異后的新的個體向量是：D’=201916122130355.3.2遺傳算法應(yīng)用簡例用遺傳算法求函數(shù)的最大值，其中

為[0，31]間的整數(shù)。解這個問題本身比較簡單，其最大值很顯然是在=31處。但作為一個例子，它有著較好的示范性和可理解性。按照遺傳算法，其求解過程如下：(1)編碼由于

的定義域是區(qū)間[0，31]上的整數(shù)，由5位二進(jìn)制數(shù)即可全部表示。因此，可采用二進(jìn)制編碼方法，其編碼串的長度為5。例如，用二進(jìn)制串00000來表示=0,11111來表示=31等。其中的0和1為基因值。(2)生成初始種群若假設(shè)給定的種群規(guī)模

=4，則可用4個隨機(jī)生成的長度為5的二進(jìn)制串作為初始種群。再假設(shè)隨機(jī)生成的初始種群（即第0代種群）為：S01=01101S02=11001S03=01000S04=1001036(3)計(jì)算適應(yīng)度要計(jì)算個體的適應(yīng)度，首先應(yīng)該定義適應(yīng)度函數(shù)。由于本例是求

的最大值，因此可直接用

來作為適應(yīng)度函數(shù)。即：其中的二進(jìn)制串S對應(yīng)著變量的值。根據(jù)此函數(shù)，初始種群中各個個體的適應(yīng)值及其所占比例如表5-5所示。表1初始種群情況表可以看出，在4個個體中S03的適應(yīng)值最大，是當(dāng)前最佳個體。編號個體串（染色體）適應(yīng)值百分比%累計(jì)百分比%選中次數(shù)S01011011316914.4414.441S02110012562552.8867.182S03010008645.4172.590S04100101832427.41100137(4)選擇操作假設(shè)采用輪盤賭方式選擇個體，且依次生成的4個隨機(jī)數(shù)（相當(dāng)于輪盤上指針?biāo)傅臄?shù)）為0.85、0.32、0.12和0.46，經(jīng)選擇后得到的新的種群為：S01=10010S02=11001S03=01101S04=11001其中，染色體11001在種群中出現(xiàn)了2次，而原染色體01000則因適應(yīng)值太小而被淘汰。38(5)交叉假設(shè)交叉概率Pi為50%，則種群中只有1/2的染色體參與交叉。若規(guī)定種群中的染色體按順序兩兩配對交叉，且有S01與S02交叉，S03與S04不交叉，則交叉情況如表5-6所示。表2初始種群的交叉情況表可見，經(jīng)交叉后得到的新的種群為：S01=10001S02=11010S03=01101S04=11001編號個體串（染色體）交叉對象交叉位子代適應(yīng)值S0110010S02310001289S0211001S01311010676S0301101S04N01101169S0411001S03N1100162539(6)變異變異概率Pm一般都很小，假設(shè)本次循環(huán)中沒有發(fā)生變異，則變異前的種群即為進(jìn)化后所得到的第1代種群。即：S11=10001S12=11010S13=01101S14=11001然后，對第1代種群重復(fù)上述(4)-(6)的操作。40對第1代種群，同樣重復(fù)上述(4)-(6)的操作。其選擇情況如表5-7所示。表3第1代種群的選擇情況表其中若假設(shè)按輪盤賭選擇時依次生成的4個隨機(jī)數(shù)為0.14、0.51、0.24和0.82，經(jīng)選擇后得到的新的種群為：S11=10001S12=11010S13=11010S14=11001可以看出，染色體11010被選擇了2次，而原染色體01101則因適應(yīng)值太小而被淘汰。編號個體串（染色體）

適應(yīng)值百分比%累計(jì)百分比%選中次數(shù)S11100012728916.4316.4371S12110102667638.4354.862S1301101131699.6164.470S14110012562535.53100141對第1代種群，其交叉情況如表5-8所示。表5-8第1代種群的交叉情況