智能技術(shù)課程課件

遺傳算法（GeneticAlgorithm）

NaturalComputing1、算法起源2、基本術(shù)語和遺傳算子3、模式定理4、遺傳算法的應(yīng)用11/17/2022智能技術(shù)課程－－葉東毅遺傳算法（GeneticAlgorithm）

Natura1算法起源遺傳算法（簡稱GA）的基本思想起源于生物體的遺傳進化。生物的進化是發(fā)生在作為生物體結(jié)構(gòu)編碼的染色體上，染色體主要是由DNA和蛋白質(zhì)組成，其中DNA又是最主要的遺傳物質(zhì)，它儲存著遺傳信息，可以準(zhǔn)確地復(fù)制，也能夠發(fā)生突變，并可通過控制蛋白質(zhì)的合成而控制生物的性狀。生物的遺傳特性，使生物界的物種能夠保持相對的穩(wěn)定；生物的變異特性，使生物個體產(chǎn)生新的性狀，以至于形成了新的物種，推動了生物的進化和發(fā)展。遺傳算法正是模擬這一過程，通過向自然學(xué)習(xí)來求解問題。11/17/2022智能技術(shù)課程－－葉東毅算法起源遺傳算法（簡稱GA）的基本思想起源于生物體的遺傳進化2算法起源1975年，美國Michigan大學(xué)的Holland教授出版了系統(tǒng)論述遺傳算法的第一本專著，標(biāo)志著遺傳算法的誕生。80年代，遺傳算法得到了廣泛應(yīng)用與研究。1989年，D.J.Goldberg出版了他的著作，對遺傳算法作了系統(tǒng)的闡述，確立了現(xiàn)代遺傳算法的基礎(chǔ)。

11/17/2022智能技術(shù)課程－－葉東毅算法起源1975年，美國Michigan大學(xué)的Holland3基本遺傳算法是一種概率搜索算法，利用編碼技術(shù)作用于稱為染色體（chromosome）的二進制數(shù)串，模擬由這些串組成的群體的進化過程。類似于自然進化，遺傳算法通過作用于染色體上的基因，尋找好的染色體來求解問題。遺傳算法通過有組織的然而是隨機的信息交換來重新結(jié)合那些適應(yīng)性好的串。雖是一類隨機算法，但又不是簡單的隨機走動，它可以有效利用已有的信息來搜尋那些有希望改善解質(zhì)量的串。與自然界相似，遺傳算法對求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行評價，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體比適應(yīng)性差的染色體有更多的繁殖機會。11/17/2022智能技術(shù)課程－－葉東毅基本遺傳算法是一種概率搜索算法，利用編碼技術(shù)作用于稱為染色體4基本術(shù)語和遺傳算子定義1

將待解決問題的解變量用某種編碼技術(shù)編制成特定形式的數(shù)字串，稱這個數(shù)字串為染色體（chromosome）；數(shù)字串的每位數(shù)字碼稱為基因（gene）（基本GA中，采用二進制編碼串），串的長度即為染色體的長度定義2

由一定數(shù)目的同等長度染色體組成的集合稱為一個種群（population）；相應(yīng)的染色體稱為種群的一個個體（individual）定義3

根據(jù)擬定的函數(shù)對個體性質(zhì)評價的一種度量，稱為個體的適應(yīng)值或適應(yīng)度（fitness）11/17/2022智能技術(shù)課程－－葉東毅基本術(shù)語和遺傳算子定義1將待解決問題的解變量用某種編碼技術(shù)5基本術(shù)語和遺傳算子定義4

對兩個個體進行部分基因互換，產(chǎn)生兩個新個體的操作，稱為交叉或雜交運算（crossover）定義5

對個體的某些基因進行改變，產(chǎn)生新個體的操作，稱作變異運算（mutation）定義6

從當(dāng)前種群中選出優(yōu)良的個體，使之有機會作為父代繁殖下一代的操作，稱作選擇運算（selection），或復(fù)制運算（reproduction）11/17/2022智能技術(shù)課程－－葉東毅基本術(shù)語和遺傳算子定義4對兩個個體進行部分基因互換，產(chǎn)6基本遺傳算子：以二進制編碼為例單點交叉:(隨機投點）X=100110100;X’=010110100;Y=010111011；Y’=100111011；兩點交叉：X=100110100;X’=010110011;Y=010111011；Y’=100111100；

或者X”=100111100;Y”=010110011；11/17/2022智能技術(shù)課程－－葉東毅基本遺傳算子：以二進制編碼為例單點交叉:(隨機投點）11/7基本遺傳算子：以二進制編碼為例單點變異:(隨機投點）X=100110100;X’=101110100;Y=010111011；Y’=110111011；多點變異：X=100110100;X’=110100101;Y=010111011；Y’=100111111；

11/17/2022智能技術(shù)課程－－葉東毅基本遺傳算子：以二進制編碼為例單點變異:(隨機投點）11/8基本遺傳算子：以二進制編碼為例個體選擇復(fù)制:(賭輪原則）設(shè)種群規(guī)模為4個體fitness概率選擇選擇X111/12X2X1X221/6X3X3X331/4X4X3X461/2X4X4X4X3X2X1RouletteWheelSelection11/17/2022智能技術(shù)課程－－葉東毅基本遺傳算子：以二進制編碼為例個體選擇復(fù)制:(賭輪原則）個9標(biāo)準(zhǔn)遺傳算法（SGA）

考慮全局優(yōu)化問題（P）max{f(x)：x∈DRn→R1}遺傳算法基于以下兩條基本策略求解問題（P）：（a）對于給定的目標(biāo)函數(shù)f，它使用f的任一適應(yīng)值函數(shù)（換言之，一個值域非負(fù)、與f有相同極點的函數(shù)）；（b）它不直接作用于實向量x，而是作用于x的某種編碼（最常見的為定長二進制數(shù)串編碼）。所以，對于取定f的任一適應(yīng)值函數(shù)F和固定長度為L的二進制數(shù)串編碼，遺傳算法實質(zhì)上是通過求解組合優(yōu)化問題

（P’）max{F(x)：x∈S}來求解問題（P）的，這里S={0，1}L為D的編碼空間（即D中所有實變量的長度為L的二進制數(shù)串編碼全體）。11/17/2022智能技術(shù)課程－－葉東毅標(biāo)準(zhǔn)遺傳算法（SGA）11/10/2022智能技術(shù)課程－－葉10Step1

初始化：1.1指定種群規(guī)模N，雜交概率Pc

，變異概率Pm及終止進化準(zhǔn)則；1.2隨機生成初始種群X(0)=(X1(0)，X2(0)，…，XN(0))∈SN，置k=0。Step2種群進化：2.1（選擇）依據(jù)Xi(k)的適應(yīng)值，隨機、獨立、重復(fù)地從X(k)中選取N個個體為母體；2.2（交叉）依概率Pc獨立地對所選N個母體執(zhí)行雜交，以產(chǎn)生新的N個中間個體；2.3（變異）依概率Pm獨立地對交叉生成的N個中間個體執(zhí)行變異，從而生成新一代種群X(k+1)=(X1(k+1)，X2(k+1)，…，XN(k+1))11/17/2022智能技術(shù)課程－－葉東毅Step1初始化：11/10/2022智能技術(shù)課程－－葉11Step3

終止檢驗：如果X（k+1）已滿足預(yù)設(shè)的進化終止原則，則停止；否則，置k=k+1，轉(zhuǎn)Step2。常見的終止條件有：1、,其中δ為給定的常數(shù)，與具體問題的求解精度有關(guān)；2、整個群體僅由某個個體生成；3、進化次數(shù)超過預(yù)定的值。

11/17/2022智能技術(shù)課程－－葉東毅Step3終止檢驗：11/10/2022智能技術(shù)課程－－12常見的選擇機制1.

賭輪選擇（roulettewheelselection）；2.最佳保留（elitistmodel）；3．期望值模型（expectedvaluemodel）選擇機制;

在該模型選擇機制中，先按期望值Q的整數(shù)部分安排個體被選中的次數(shù)，而對期望值Q的小數(shù)部分可按下述幾種方式進行處理：（1）

確定方式;（2）

賭輪方式;（3）

貝努利試驗（BernoulliTrials）方式11/17/2022智能技術(shù)課程－－葉東毅常見的選擇機制1.賭輪選擇（roulettewheel13遺傳算法的改進——精英策略采用精英策略(優(yōu)、劣解同時保留)的遺傳算法是保持當(dāng)前一個最好解和最差解；最好解(thefittest)不參與交叉和變異操作；最差解不參加交叉操作，但參加變異操作；11/17/2022智能技術(shù)課程－－葉東毅遺傳算法的改進——精英策略采用精英策略(優(yōu)、劣解同時保留)的14Step1初始化：隨機產(chǎn)生一個規(guī)模為N的初始種群，其中每個個體為二進制位串的形式。Step2

計算適應(yīng)值并按序排列：計算種群中每個個體的適應(yīng)值，并把個體按適應(yīng)值從小到大排列。Step3

選擇：把適應(yīng)值最大、最小的個體按1:1選擇，另外的N-2個個體根據(jù)每個個體的相對適應(yīng)值，計算每個個體被選擇的概率，進行選擇操作。Step4

交叉：從上述選擇后的種群中，除了最優(yōu)、最差兩個個體外，隨機選擇兩個染色體，按一定的交叉概率Pc進行基因變換，交換的位置隨機選取。Step5

變異：從種群中，除了最優(yōu)、最差兩個個體外，隨機選擇一個染色體，按一定的變異概率Pm進行基因變異；對最差的個體按增大后的變異概率kPm(k取10-20)進行基因變異。Step6

若達(dá)到預(yù)設(shè)的進化代數(shù)，則算法停止，否則，轉(zhuǎn)Step2.11/17/2022智能技術(shù)課程－－葉東毅Step1初始化：隨機產(chǎn)生一個規(guī)模為N的初始種群，其中每個15模式定理定義：

基于三值字符集{0，1，*}所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似性的0、1字符串集的字符串稱作模式。模式是二值符號串的一種擴展，其中基因的取值可為0，1或*。符號“*”稱作“無關(guān)符”，表示一種隨意的情況，也就是說基因的取值可以是1也可以是0。例如（*01*00）、（******）和（100101）都是長為6位的二值符號串的模式。11/17/2022智能技術(shù)課程－－葉東毅模式定理定義：基于三值字符集{0，1，*}所產(chǎn)生的能描述16包含個體與隱含模式如果一個個體X符合模式H，就稱X屬于H，或H包含X。如：H=10*0**;包含：101011,100001,…,給定一個個體X,如果X屬于模式H，也稱H為X隱含的模式。如：X=101011,它隱含的模式有H1=1*****,H2=*01**1,H3=10**11,…,11/17/2022智能技術(shù)課程－－葉東毅包含個體與隱含模式如果一個個體X符合模式H，就稱X屬于H，或17定義：

模式H中確定位置的個數(shù)稱作該模式的模式階，記作O(H)。比如模式011*0*的階是4，而模式0*****為1。顯然一個模式的階數(shù)越高，其包含的樣本數(shù)就越少，因而確定性也就越高。定義：

模式H中第一個確定位置和最后一個確定位置之間的距離稱作該模式的定義距，記作δ(H)。比如模式011*1*的定義距是4，而模式0*****的定義距為0。11/17/2022智能技術(shù)課程－－葉東毅定義：模式H中確定位置的個數(shù)稱作該模式的模式階，記作O(H18模式階和定義距描述了模式的基本性質(zhì)。下面討論模式在遺傳操作下的變化。令A(yù)(t)表示第t代中串的群體，以Aj(j=1,2,···,n)表示一代中第j個個體串。1、選擇操作對模式的作用假設(shè)在t代，群體A(t)中模式H所包含的個體數(shù)為m(H，t)。在選擇運算中，一個串是根據(jù)其適應(yīng)度進行復(fù)制的。即以概率Pi=fi/(∑fj）進行選擇的，其中fi是個體Ai(t)適應(yīng)度。則模式H在第t+1代中包含的個體數(shù)為（從概率角度）其中，f(H),f(t)分別是模式H（在A(t)中）和群體A(t)的適應(yīng)度平均值。11/17/2022智能技術(shù)課程－－葉東毅模式階和定義距描述了模式的基本性質(zhì)。下面討論模式在遺傳操作19可見，模式的增長（減少）依賴于模式的平均適應(yīng)度與群體平均適應(yīng)度之比：那些平均適應(yīng)度高于群體平均適應(yīng)度的模式將在下一代中增長；而那些平均適應(yīng)度低于群體平均適應(yīng)度的模式將在下一代中減少。現(xiàn)在，假定模式H的平均適應(yīng)度一直高于群體平均適應(yīng)度(設(shè)至少為1+c倍），c為正的常數(shù)，則有即，在選擇算子作用下，平均適應(yīng)度高于群體平均適應(yīng)度的模式將呈指數(shù)級增長；而低于群體平均適應(yīng)度的模式將呈指數(shù)級減少。11/17/2022智能技術(shù)課程－－葉東毅可見，模式的增長（減少）依賴于模式的平均適應(yīng)度與群體平均適應(yīng)202．模式在交叉算子作用下的變化考慮一個長度為6的串以及隱含其中的兩個模式：A=010110

H1=*1***0H2

=***11*

假定A被選中進行交叉，不妨設(shè)交叉點為3，即A=010110H1=*1***0H2=***11*11/17/2022智能技術(shù)課程－－葉東毅2．模式在交叉算子作用下的變化11/10/2022智能技術(shù)課21模式在交叉算子作用下的變化A=010110B=101001A’=101110B’=010001H1=*1***0

H2=***11*顯然，H1被破壞，而H2依然存在11/17/2022智能技術(shù)課程－－葉東毅模式在交叉算子作用下的變化11/10/2022智能技術(shù)課程－22模式H1的定義距為4，那么交叉點在l

－1=5個位置上隨機產(chǎn)生時，H1遭到破壞的概率是Pd=δ(H1)/(l－1)=4/5，換句話說，其生存概率為1/5；模式H2的定義距是1，則H2遭破壞的概率是

Pd=δ(H2

)/(l－1)=1/5，即生存概率是4/5。一般地講，當(dāng)交叉點落在定義距之外時，模式H才能生存。在簡單交叉（單點交叉）下的H的生存概率Ps=1－δ(H)/(l－1)11/17/2022智能技術(shù)課程－－葉東毅模式H1的定義距為4，那么交叉點在l－1=5個位置上隨機產(chǎn)23由于交叉本身也是以一定的概率Pc發(fā)生的，所以模式H的生存概率為如果與A進行交叉的串在位置2，6上有一位與A相同，則H1將被保留。因此，以上公式只是生存概率的一個下界，即有：這個公式描述了模式在交叉算子作用下的生存概率。如果考慮模式H在選擇和交叉算子的共同作用下的變化。則有11/17/2022智能技術(shù)課程－－葉東毅由于交叉本身也是以一定的概率Pc發(fā)生的，所以模式H的生存概率243．模式在變異算子作用下的變化

考慮變異操作。串的某一位置發(fā)生改變的概率為Pm，故該位置不變的概率為1－Pm，而模式H在變異運算作用下若要不受破壞，則其中所有的確定位置必須保持不變。因此模式H保持不變的概率為其中O(H)為模式H的階數(shù)。當(dāng)Pm<<1時，模式H在變異算子作用下的生存概率為11/17/2022智能技術(shù)課程－－葉東毅3．模式在變異算子作用下的變化11/10/2022智能技術(shù)課25綜合三種算子對模式H的影響，有如下的生存概率估計：模式定理在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將得以(指數(shù)級)增長。

結(jié)論：在一定前提下，遺傳算法以概率為1收斂到全局最優(yōu)解！11/17/2022智能技術(shù)課程－－葉東毅綜合三種算子對模式H的影響，有如下的生存概率估計：模式定理126遺傳算法的應(yīng)用染色體編碼：視具體問題而定，可以整數(shù)序列串，也可以實數(shù)序列。適應(yīng)值函數(shù)的定義，如何評估？交叉算子的本質(zhì)：保持父代基因段或信息；變異算子的本質(zhì)：新解的實質(zhì)多樣性；如何定義這2個演化算子，使之保持解的可行性？（特別是約束情況下？）參數(shù)設(shè)定問題。11/17/2022智能技術(shù)課程－－葉東毅遺傳算法的應(yīng)用染色體編碼：視具體問題而定，可以整數(shù)序列串，也27SAT問題（無約束）F(x)：布爾變量x=(x1,…,xn)的合取范式.問題：找到x=(x1,…,xn)的一個真值指派，使得F(x)=TRUE(or1).例如：F(x)=（x1x3）（x2x5x6）（

x4x5）取x=(1,0,0,0,0,1)，則F(x)=0；取x=(1,0,0,0,0,0)，則F(x)=1；求得一個解！11/17/2022智能技術(shù)課程－－葉東毅SAT問題（無約束）F(x)：布爾變量x=(x1,…28編碼和適應(yīng)值函數(shù)二進制編碼：直接用原問題的變量編碼；適應(yīng)值：直接采用問題的目標(biāo)函數(shù)F(x)?要么F(x)=1，找到解；要么F(x)=0，此時，如何區(qū)別不同個體的質(zhì)量呢？如何引導(dǎo)選擇過程呢？適應(yīng)值函數(shù)的合理確定問題！！F(x)=

f1(x)

f2(x)…fp(x);fi(x)為析取項;適應(yīng)值函數(shù)：Q(x)=Boolean(fi(x))；0Q(x)p如果Q(x)=p,則x為一個解；可以有其他（可能更好）的方式定義適應(yīng)值函數(shù)。11/17/2022智能技術(shù)課程－－葉東毅編碼和適應(yīng)值函數(shù)二進制編碼：直接用原問題的變量編碼；F(x)29對稱全通路TSP問題（含約束）城市編號（頂點）序列為染色體（整數(shù)編碼）：X=123…n的某一個排列，這樣最自然！如何定義交叉、變異呢？簡單交換或變異導(dǎo)致不可行的解：12435+23154=12154+23435

適應(yīng)值函數(shù)：距離總和。采用二進制編碼？按照邊，但是需要判斷頂點集合的重疊性。同時，邊數(shù)遠(yuǎn)遠(yuǎn)多于頂點數(shù)。另外，面臨演化算子的設(shè)計問題。不合適！11/17/2022智能技術(shù)課程－－葉東毅對稱全通路TSP問題（含約束）城市編號（頂點）序列為染色體（30X=123456789;Y=324695781X’=123456798

Y’=324691

7581、基于次序的交叉：在父代隨機選取一組位置，強加到另一個上2、基于位置的交叉：X=123456789;Y=324695781X’=312495687；Y’17/2022智能技術(shù)課程－－葉東毅X=123456789;Y=31X=123456789;4：7，5：9，6：8Y=324798651X’=123798465Y’=3274568913、部分映射交叉：在父代隨機選取一組位置，段內(nèi)元對應(yīng)對交換變異算子：1、隨機選2個元素，將第二元置于第一元之前；X=123456789，X’=1245367892、隨機選2個元素，交換位置；X=123456789，X’=12645378911/17/2022智能技術(shù)課程－－葉東毅X=123456789;432圖著色問題（混合算法）

---貪心+遺傳給定每個頂點具有加權(quán)的圖和n種顏色,圖著色問題：從n種顏色的集合中選擇一種顏色到任一個頂點上，但要滿足任何一條邊關(guān)聯(lián)的一對頂點不具有相同的顏色。未著色的頂點為無色的。著色頂點的加權(quán)總和為著色方案的分?jǐn)?shù)。求具有最高分?jǐn)?shù)的著色方案。這是NP-完全問題。11/17/2022智能技術(shù)課程－－葉東毅圖著色問題（混合算法）

---貪心+遺33貪心策略按照加權(quán)大小順序?qū)旤c排序；按照該順序取每個頂點，并為其指定它能夠具有的第一個合法顏色。該算法速度快，有時可以獲得最優(yōu)解。11/17/2022智能技術(shù)課程－－葉東毅貪心策略按照加權(quán)大小順序?qū)旤c排序；11/10/2022智能347-362-83-144-131-126-105-911/17/2022智能技術(shù)課程－－葉東毅7-362-83-144-131-126-105-911/1357-362-83-144-131-126-105-9n

=1,Score=36;Bestsolution!Greedyideawins!11/17/2022智能技術(shù)課程－－葉東毅7-362-83-144-131-126-105-9n=1367-152-83-144-131-126-105-911/17/2022智能技術(shù)課程－－葉東毅7-152-83-144-131-126-105-911/1377-152-83-144-131-126-105-9n

=1,Score=15;Notbest!Greedyideafails!11/17/2022智能技術(shù)課程－－葉東毅7-152-83-144-131-126-105-9n=1387-152-83-144-131-126-105-9n

=1,Score=35;Best!11/17/2022智能技術(shù)課程－－葉東毅7-152-83-144-131-126-105-9n=1397-152-83-144-131-126-105-9n

=2,Score=66;Best!11/17/2022智能技術(shù)課程－－葉東毅7-152-83-144-131-126-105-9n=2407-152-83-144-131-126-105-9n

=3,Score=81;Best!Again,greedyideawins!11/17/2022智能技術(shù)課程－－葉東毅7-152-83-144-131-126-105-9n=341混合遺傳算法編碼：有序頂點序列（整數(shù)串）適應(yīng)值函數(shù)：依照貪心策略，對給定的頂點序列進行著色，求出相應(yīng)的分?jǐn)?shù)作為適應(yīng)值；應(yīng)用遺傳算法進行演化，每得到新的一代，都按照貪心策略產(chǎn)生相應(yīng)的著色方案，直至找到一個滿意的著色方案。雜交算子和變異算子可以類似TSP問題那樣設(shè)計。11/17/2022智能技術(shù)課程－－葉東毅混合遺傳算法編碼：有序頂點序列（整數(shù)串）11/10/20224211/17/2022智能技術(shù)課程－－葉東毅11/10/2022智能技術(shù)課程－－葉東毅43遺傳算法（GeneticAlgorithm）

NaturalComputing1、算法起源2、基本術(shù)語和遺傳算子3、模式定理4、遺傳算法的應(yīng)用11/17/2022智能技術(shù)課程－－葉東毅遺傳算法（GeneticAlgorithm）

Natura44算法起源遺傳算法（簡稱GA）的基本思想起源于生物體的遺傳進化。生物的進化是發(fā)生在作為生物體結(jié)構(gòu)編碼的染色體上，染色體主要是由DNA和蛋白質(zhì)組成，其中DNA又是最主要的遺傳物質(zhì)，它儲存著遺傳信息，可以準(zhǔn)確地復(fù)制，也能夠發(fā)生突變，并可通過控制蛋白質(zhì)的合成而控制生物的性狀。生物的遺傳特性，使生物界的物種能夠保持相對的穩(wěn)定；生物的變異特性，使生物個體產(chǎn)生新的性狀，以至于形成了新的物種，推動了生物的進化和發(fā)展。遺傳算法正是模擬這一過程，通過向自然學(xué)習(xí)來求解問題。11/17/2022智能技術(shù)課程－－葉東毅算法起源遺傳算法（簡稱GA）的基本思想起源于生物體的遺傳進化45算法起源1975年，美國Michigan大學(xué)的Holland教授出版了系統(tǒng)論述遺傳算法的第一本專著，標(biāo)志著遺傳算法的誕生。80年代，遺傳算法得到了廣泛應(yīng)用與研究。1989年，D.J.Goldberg出版了他的著作，對遺傳算法作了系統(tǒng)的闡述，確立了現(xiàn)代遺傳算法的基礎(chǔ)。

11/17/2022智能技術(shù)課程－－葉東毅算法起源1975年，美國Michigan大學(xué)的Holland46基本遺傳算法是一種概率搜索算法，利用編碼技術(shù)作用于稱為染色體（chromosome）的二進制數(shù)串，模擬由這些串組成的群體的進化過程。類似于自然進化，遺傳算法通過作用于染色體上的基因，尋找好的染色體來求解問題。遺傳算法通過有組織的然而是隨機的信息交換來重新結(jié)合那些適應(yīng)性好的串。雖是一類隨機算法，但又不是簡單的隨機走動，它可以有效利用已有的信息來搜尋那些有希望改善解質(zhì)量的串。與自然界相似，遺傳算法對求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行評價，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體比適應(yīng)性差的染色體有更多的繁殖機會。11/17/2022智能技術(shù)課程－－葉東毅基本遺傳算法是一種概率搜索算法，利用編碼技術(shù)作用于稱為染色體47基本術(shù)語和遺傳算子定義1

將待解決問題的解變量用某種編碼技術(shù)編制成特定形式的數(shù)字串，稱這個數(shù)字串為染色體（chromosome）；數(shù)字串的每位數(shù)字碼稱為基因（gene）（基本GA中，采用二進制編碼串），串的長度即為染色體的長度定義2

由一定數(shù)目的同等長度染色體組成的集合稱為一個種群（population）；相應(yīng)的染色體稱為種群的一個個體（individual）定義3

根據(jù)擬定的函數(shù)對個體性質(zhì)評價的一種度量，稱為個體的適應(yīng)值或適應(yīng)度（fitness）11/17/2022智能技術(shù)課程－－葉東毅基本術(shù)語和遺傳算子定義1將待解決問題的解變量用某種編碼技術(shù)48基本術(shù)語和遺傳算子定義4

對兩個個體進行部分基因互換，產(chǎn)生兩個新個體的操作，稱為交叉或雜交運算（crossover）定義5

對個體的某些基因進行改變，產(chǎn)生新個體的操作，稱作變異運算（mutation）定義6

從當(dāng)前種群中選出優(yōu)良的個體，使之有機會作為父代繁殖下一代的操作，稱作選擇運算（selection），或復(fù)制運算（reproduction）11/17/2022智能技術(shù)課程－－葉東毅基本術(shù)語和遺傳算子定義4對兩個個體進行部分基因互換，產(chǎn)49基本遺傳算子：以二進制編碼為例單點交叉:(隨機投點）X=100110100;X’=010110100;Y=010111011；Y’=100111011；兩點交叉：X=100110100;X’=010110011;Y=010111011；Y’=100111100；

或者X”=100111100;Y”=010110011；11/17/2022智能技術(shù)課程－－葉東毅基本遺傳算子：以二進制編碼為例單點交叉:(隨機投點）11/50基本遺傳算子：以二進制編碼為例單點變異:(隨機投點）X=100110100;X’=101110100;Y=010111011；Y’=110111011；多點變異：X=100110100;X’=110100101;Y=010111011；Y’=100111111；

11/17/2022智能技術(shù)課程－－葉東毅基本遺傳算子：以二進制編碼為例單點變異:(隨機投點）11/51基本遺傳算子：以二進制編碼為例個體選擇復(fù)制:(賭輪原則）設(shè)種群規(guī)模為4個體fitness概率選擇選擇X111/12X2X1X221/6X3X3X331/4X4X3X461/2X4X4X4X3X2X1RouletteWheelSelection11/17/2022智能技術(shù)課程－－葉東毅基本遺傳算子：以二進制編碼為例個體選擇復(fù)制:(賭輪原則）個52標(biāo)準(zhǔn)遺傳算法（SGA）

考慮全局優(yōu)化問題（P）max{f(x)：x∈DRn→R1}遺傳算法基于以下兩條基本策略求解問題（P）：（a）對于給定的目標(biāo)函數(shù)f，它使用f的任一適應(yīng)值函數(shù)（換言之，一個值域非負(fù)、與f有相同極點的函數(shù)）；（b）它不直接作用于實向量x，而是作用于x的某種編碼（最常見的為定長二進制數(shù)串編碼）。所以，對于取定f的任一適應(yīng)值函數(shù)F和固定長度為L的二進制數(shù)串編碼，遺傳算法實質(zhì)上是通過求解組合優(yōu)化問題

（P’）max{F(x)：x∈S}來求解問題（P）的，這里S={0，1}L為D的編碼空間（即D中所有實變量的長度為L的二進制數(shù)串編碼全體）。11/17/2022智能技術(shù)課程－－葉東毅標(biāo)準(zhǔn)遺傳算法（SGA）11/10/2022智能技術(shù)課程－－葉53Step1

初始化：1.1指定種群規(guī)模N，雜交概率Pc

，變異概率Pm及終止進化準(zhǔn)則；1.2隨機生成初始種群X(0)=(X1(0)，X2(0)，…，XN(0))∈SN，置k=0。Step2種群進化：2.1（選擇）依據(jù)Xi(k)的適應(yīng)值，隨機、獨立、重復(fù)地從X(k)中選取N個個體為母體；2.2（交叉）依概率Pc獨立地對所選N個母體執(zhí)行雜交，以產(chǎn)生新的N個中間個體；2.3（變異）依概率Pm獨立地對交叉生成的N個中間個體執(zhí)行變異，從而生成新一代種群X(k+1)=(X1(k+1)，X2(k+1)，…，XN(k+1))11/17/2022智能技術(shù)課程－－葉東毅Step1初始化：11/10/2022智能技術(shù)課程－－葉54Step3

終止檢驗：如果X（k+1）已滿足預(yù)設(shè)的進化終止原則，則停止；否則，置k=k+1，轉(zhuǎn)Step2。常見的終止條件有：1、,其中δ為給定的常數(shù)，與具體問題的求解精度有關(guān)；2、整個群體僅由某個個體生成；3、進化次數(shù)超過預(yù)定的值。

11/17/2022智能技術(shù)課程－－葉東毅Step3終止檢驗：11/10/2022智能技術(shù)課程－－55常見的選擇機制1.

賭輪選擇（roulettewheelselection）；2.最佳保留（elitistmodel）；3．期望值模型（expectedvaluemodel）選擇機制;

在該模型選擇機制中，先按期望值Q的整數(shù)部分安排個體被選中的次數(shù)，而對期望值Q的小數(shù)部分可按下述幾種方式進行處理：（1）

確定方式;（2）

賭輪方式;（3）

貝努利試驗（BernoulliTrials）方式11/17/2022智能技術(shù)課程－－葉東毅常見的選擇機制1.賭輪選擇（roulettewheel56遺傳算法的改進——精英策略采用精英策略(優(yōu)、劣解同時保留)的遺傳算法是保持當(dāng)前一個最好解和最差解；最好解(thefittest)不參與交叉和變異操作；最差解不參加交叉操作，但參加變異操作；11/17/2022智能技術(shù)課程－－葉東毅遺傳算法的改進——精英策略采用精英策略(優(yōu)、劣解同時保留)的57Step1初始化：隨機產(chǎn)生一個規(guī)模為N的初始種群，其中每個個體為二進制位串的形式。Step2

計算適應(yīng)值并按序排列：計算種群中每個個體的適應(yīng)值，并把個體按適應(yīng)值從小到大排列。Step3

選擇：把適應(yīng)值最大、最小的個體按1:1選擇，另外的N-2個個體根據(jù)每個個體的相對適應(yīng)值，計算每個個體被選擇的概率，進行選擇操作。Step4

交叉：從上述選擇后的種群中，除了最優(yōu)、最差兩個個體外，隨機選擇兩個染色體，按一定的交叉概率Pc進行基因變換，交換的位置隨機選取。Step5

變異：從種群中，除了最優(yōu)、最差兩個個體外，隨機選擇一個染色體，按一定的變異概率Pm進行基因變異；對最差的個體按增大后的變異概率kPm(k取10-20)進行基因變異。Step6

若達(dá)到預(yù)設(shè)的進化代數(shù)，則算法停止，否則，轉(zhuǎn)Step2.11/17/2022智能技術(shù)課程－－葉東毅Step1初始化：隨機產(chǎn)生一個規(guī)模為N的初始種群，其中每個58模式定理定義：

基于三值字符集{0，1，*}所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似性的0、1字符串集的字符串稱作模式。模式是二值符號串的一種擴展，其中基因的取值可為0，1或*。符號“*”稱作“無關(guān)符”，表示一種隨意的情況，也就是說基因的取值可以是1也可以是0。例如（*01*00）、（******）和（100101）都是長為6位的二值符號串的模式。11/17/2022智能技術(shù)課程－－葉東毅模式定理定義：基于三值字符集{0，1，*}所產(chǎn)生的能描述59包含個體與隱含模式如果一個個體X符合模式H，就稱X屬于H，或H包含X。如：H=10*0**;包含：101011,100001,…,給定一個個體X,如果X屬于模式H，也稱H為X隱含的模式。如：X=101011,它隱含的模式有H1=1*****,H2=*01**1,H3=10**11,…,11/17/2022智能技術(shù)課程－－葉東毅包含個體與隱含模式如果一個個體X符合模式H，就稱X屬于H，或60定義：

模式H中確定位置的個數(shù)稱作該模式的模式階，記作O(H)。比如模式011*0*的階是4，而模式0*****為1。顯然一個模式的階數(shù)越高，其包含的樣本數(shù)就越少，因而確定性也就越高。定義：

模式H中第一個確定位置和最后一個確定位置之間的距離稱作該模式的定義距，記作δ(H)。比如模式011*1*的定義距是4，而模式0*****的定義距為0。11/17/2022智能技術(shù)課程－－葉東毅定義：模式H中確定位置的個數(shù)稱作該模式的模式階，記作O(H61模式階和定義距描述了模式的基本性質(zhì)。下面討論模式在遺傳操作下的變化。令A(yù)(t)表示第t代中串的群體，以Aj(j=1,2,···,n)表示一代中第j個個體串。1、選擇操作對模式的作用假設(shè)在t代，群體A(t)中模式H所包含的個體數(shù)為m(H，t)。在選擇運算中，一個串是根據(jù)其適應(yīng)度進行復(fù)制的。即以概率Pi=fi/(∑fj）進行選擇的，其中fi是個體Ai(t)適應(yīng)度。則模式H在第t+1代中包含的個體數(shù)為（從概率角度）其中，f(H),f(t)分別是模式H（在A(t)中）和群體A(t)的適應(yīng)度平均值。11/17/2022智能技術(shù)課程－－葉東毅模式階和定義距描述了模式的基本性質(zhì)。下面討論模式在遺傳操作62可見，模式的增長（減少）依賴于模式的平均適應(yīng)度與群體平均適應(yīng)度之比：那些平均適應(yīng)度高于群體平均適應(yīng)度的模式將在下一代中增長；而那些平均適應(yīng)度低于群體平均適應(yīng)度的模式將在下一代中減少?，F(xiàn)在，假定模式H的平均適應(yīng)度一直高于群體平均適應(yīng)度(設(shè)至少為1+c倍），c為正的常數(shù)，則有即，在選擇算子作用下，平均適應(yīng)度高于群體平均適應(yīng)度的模式將呈指數(shù)級增長；而低于群體平均適應(yīng)度的模式將呈指數(shù)級減少。11/17/2022智能技術(shù)課程－－葉東毅可見，模式的增長（減少）依賴于模式的平均適應(yīng)度與群體平均適應(yīng)632．模式在交叉算子作用下的變化考慮一個長度為6的串以及隱含其中的兩個模式：A=010110

H1=*1***0H2

=***11*

假定A被選中進行交叉，不妨設(shè)交叉點為3，即A=010110H1=*1***0H2=***11*11/17/2022智能技術(shù)課程－－葉東毅2．模式在交叉算子作用下的變化11/10/2022智能技術(shù)課64模式在交叉算子作用下的變化A=010110B=101001A’=101110B’=010001H1=*1***0

H2=***11*顯然，H1被破壞，而H2依然存在11/17/2022智能技術(shù)課程－－葉東毅模式在交叉算子作用下的變化11/10/2022智能技術(shù)課程－65模式H1的定義距為4，那么交叉點在l

－1=5個位置上隨機產(chǎn)生時，H1遭到破壞的概率是Pd=δ(H1)/(l－1)=4/5，換句話說，其生存概率為1/5；模式H2的定義距是1，則H2遭破壞的概率是

Pd=δ(H2

)/(l－1)=1/5，即生存概率是4/5。一般地講，當(dāng)交叉點落在定義距之外時，模式H才能生存。在簡單交叉（單點交叉）下的H的生存概率Ps=1－δ(H)/(l－1)11/17/2022智能技術(shù)課程－－葉東毅模式H1的定義距為4，那么交叉點在l－1=5個位置上隨機產(chǎn)66由于交叉本身也是以一定的概率Pc發(fā)生的，所以模式H的生存概率為如果與A進行交叉的串在位置2，6上有一位與A相同，則H1將被保留。因此，以上公式只是生存概率的一個下界，即有：這個公式描述了模式在交叉算子作用下的生存概率。如果考慮模式H在選擇和交叉算子的共同作用下的變化。則有11/17/2022智能技術(shù)課程－－葉東毅由于交叉本身也是以一定的概率Pc發(fā)生的，所以模式H的生存概率673．模式在變異算子作用下的變化

考慮變異操作。串的某一位置發(fā)生改變的概率為Pm，故該位置不變的概率為1－Pm，而模式H在變異運算作用下若要不受破壞，則其中所有的確定位置必須保持不變。因此模式H保持不變的概率為其中O(H)為模式H的階數(shù)。當(dāng)Pm<<1時，模式H在變異算子作用下的生存概率為11/17/2022智能技術(shù)課程－－葉東毅3．模式在變異算子作用下的變化11/10/2022智能技術(shù)課68綜合三種算子對模式H的影響，有如下的生存概率估計：模式定理在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將得以(指數(shù)級)增長。

結(jié)論：在一定前提下，遺傳算法以概率為1收斂到全局最優(yōu)解！11/17/2022智能技術(shù)課程－－葉東毅綜合三種算子對模式H的影響，有如下的生存概率估計：模式定理169遺傳算法的應(yīng)用染色體編碼：視具體問題而定，可以整數(shù)序列串，也可以實數(shù)序列。適應(yīng)值函數(shù)的定義，如何評估？交叉算子的本質(zhì)：保持父代基因段或信息；變異算子的本質(zhì)：新解的實質(zhì)多樣性；如何定義這2個演化算子，使之保持解的可行性？（特別是約束情況下？）參數(shù)設(shè)定問題。11/17/2022智能技術(shù)課程－－葉東毅遺傳算法的應(yīng)用染色體編碼：視具體問題而定，可以整數(shù)序列串，也70SAT問題（無約束）F(x)：布爾變量x=(x1,…,xn)的合取范式.問題：找到x=(x1,…,xn)的一個真值指派，使得F(x)=TRUE(or1).例如：F(x)=（x1x3）（x2x5x6）（

x4x5）取x=(1,0,0,0,0,1)，則F(x)=0；取x=(1,0,0,0,0,0)，則F(x)=1；求得一個解！11/17/2022智能技術(shù)課程－－葉東毅SAT問題（無約束）F(x)：布爾變量x=(x1,…71編碼和適應(yīng)值函數(shù)二進制編碼：直接用原問題的變量編碼；適應(yīng)值：直接采用問題的目標(biāo)函數(shù)F(x)?要么F(x)=1，找到解；要么F(x)=0，此時，如何區(qū)別不同個體的質(zhì)量呢？如何引導(dǎo)選擇過程呢？適應(yīng)值函數(shù)的合理確定問題?。(x)=

f1(x)

f2(x)…fp(x);fi(x)為析取項;適應(yīng)值函數(shù)：Q(x)=Boolean(fi(x))；0Q(x)p如果Q(x)=p,則x為一個解；可以有其他（可能更好）的方式定義適應(yīng)值函數(shù)。11/17/2022智能技術(shù)課程－－葉東毅編碼和適應(yīng)值函數(shù)二進制編碼：直接用原問題的變量編碼；F(x)72對稱全通路TSP問題（含約束）城市編號（頂點）序列為染色體（整數(shù)編碼）：X=123…n的某一個排列，這樣最自然！如何定義交叉、變異呢？簡單交換或變異導(dǎo)致不可行的解：12435+23154=12154+23435

適應(yīng)值函數(shù)：距離總和。采用二進制編碼？按照邊，但是需要判斷頂點集合的重疊性。同時，邊數(shù)遠(yuǎn)遠(yuǎn)多于頂點數(shù)。另外，面臨演化