遺傳算法（GeneticAlgorithm）

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

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

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

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

根據擬定的函數(shù)對個體性質評價的一種度量，稱為個體的適應值或適應度（fitness）1/12/2023智能技術課程－－葉東毅基本術語和遺傳算子定義4

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

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

從當前種群中選出優(yōu)良的個體，使之有機會作為父代繁殖下一代的操作，稱作選擇運算（selection），或復制運算（reproduction）1/12/2023智能技術課程－－葉東毅基本遺傳算子：以二進制編碼為例單點交叉:(隨機投點）X=100110100;X’=010110100;Y=010111011；Y’=100111011；兩點交叉：X=100110100;X’=010110011;Y=010111011；Y’=100111100；

或者

X”=100111100;Y”=010110011；1/12/2023智能技術課程－－葉東毅基本遺傳算子：以二進制編碼為例單點變異:(隨機投點）X=100110100;X’=101110100;Y=010111011；Y’=110111011；多點變異：X=100110100;X’=110100101;Y=010111011；Y’=100111111；

1/12/2023智能技術課程－－葉東毅基本遺傳算子：以二進制編碼為例個體選擇復制:(賭輪原則）設種群規(guī)模為4個體fitness概率選擇選擇X11

1/12X2X1X22

1/6X3X3X33

1/4X4X3X46

1/2X4X4X4X3X2X1RouletteWheelSelection1/12/2023智能技術課程－－葉東毅標準遺傳算法（SGA）

考慮全局優(yōu)化問題（P）

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

（P’）

max{F(x)：x∈S}來求解問題（P）的，這里S={0，1}L為D的編碼空間（即D中所有實變量的長度為L的二進制數(shù)串編碼全體）。1/12/2023智能技術課程－－葉東毅Step1

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

，變異概率Pm及終止進化準則；1.2隨機生成初始種群X(0)=(X1(0)，X2(0)，…，XN(0))∈SN，

置k=0。Step2種群進化：2.1（選擇）依據Xi(k)的適應值，隨機、獨立、重復地從X(k)中選取N個個體為母體；2.2（交叉）依概率Pc獨立地對所選N個母體執(zhí)行雜交，以產生新的N個中間個體；2.3（變異）依概率Pm獨立地對交叉生成的N個中間個體執(zhí)行變異，從而生成新一代種群X(k+1)=(X1(k+1)，X2(k+1)，…，XN(k+1))1/12/2023智能技術課程－－葉東毅Step3

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

1/12/2023智能技術課程－－葉東毅常見的選擇機制1.

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

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

確定方式;（2）

賭輪方式;（3）

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

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

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

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

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

若達到預設的進化代數(shù)，則算法停止，否則，轉Step2.1/12/2023智能技術課程－－葉東毅模式定理定義：

基于三值字符集{0，1，*}所產生的能描述具有某些結構相似性的0、1字符串集的字符串稱作模式。模式是二值符號串的一種擴展，其中基因的取值可為0，1或*。符號“*”稱作“無關符”，表示一種隨意的情況，也就是說基因的取值可以是1也可以是0。例如（*01*00）、（******）和（100101）都是長為6位的二值符號串的模式。1/12/2023智能技術課程－－葉東毅包含個體與隱含模式如果一個個體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,…,1/12/2023智能技術課程－－葉東毅定義：

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

模式H中第一個確定位置和最后一個確定位置之間的距離稱作該模式的定義距，記作δ(H)。比如模式011*1*的定義距是4，而模式0*****的定義距為0。1/12/2023智能技術課程－－葉東毅模式階和定義距描述了模式的基本性質。下面討論模式在遺傳操作下的變化。令A(t)表示第t代中串的群體，以Aj(j=1,2,···,n)表示一代中第j個個體串。1、選擇操作對模式的作用假設在t代，群體A(t)中模式H所包含的個體數(shù)為m(H，t)。在選擇運算中，一個串是根據其適應度進行復制的。即以概率Pi=fi

/(∑fj）進行選擇的，其中fi是個體Ai(t)適應度。則模式H在第t+1代中包含的個體數(shù)為（從概率角度）其中，f(H),f(t)

分別是模式H（在A(t)中）和群體A(t)的適應度平均值。1/12/2023智能技術課程－－葉東毅可見，模式的增長（減少）依賴于模式的平均適應度與群體平均適應度之比：那些平均適應度高于群體平均適應度的模式將在下一代中增長；而那些平均適應度低于群體平均適應度的模式將在下一代中減少。現(xiàn)在，假定模式H的平均適應度一直高于群體平均適應度(設至少為1+c倍），c為正的常數(shù)，則有即，在選擇算子作用下，平均適應度高于群體平均適應度的模式將呈指數(shù)級增長；而低于群體平均適應度的模式將呈指數(shù)級減少。1/12/2023智能技術課程－－葉東毅2．模式在交叉算子作用下的變化考慮一個長度為6的串以及隱含其中的兩個模式：

A=010110

H1=*1***0H2

=***11*

假定A被選中進行交叉，不妨設交叉點為3，即

A=010110H1=*1***0H2=***11*1/12/2023智能技術課程－－葉東毅模式在交叉算子作用下的變化

A=010110

B=101001A’=

101110B’=010001H1=*1***0

H2=***11*顯然，H1被破壞，而H2依然存在1/12/2023智能技術課程－－葉東毅模式H1的定義距為4，那么交叉點在l

－1=5個位置上隨機產生時，H1遭到破壞的概率是

Pd=δ(H1)/(l－1)=4/5，換句話說，其生存概率為1/5；模式H2的定義距是1，則H2遭破壞的概率是

Pd=δ(H2

)/(l－1)=1/5，即生存概率是4/5。一般地講，當交叉點落在定義距之外時，模式H才能生存。在簡單交叉（單點交叉）下的H的生存概率

Ps=1－δ(H)/(l－1)1/12/2023智能技術課程－－葉東毅由于交叉本身也是以一定的概率Pc發(fā)生的，所以模式H的生存概率為如果與A進行交叉的串在位置2，6上有一位與A相同，則H1將被保留。因此，以上公式只是生存概率的一個下界，即有：這個公式描述了模式在交叉算子作用下的生存概率。如果考慮模式H在選擇和交叉算子的共同作用下的變化。則有1/12/2023智能技術課程－－葉東毅3．模式在變異算子作用下的變化

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

結論：在一定前提下，遺傳算法以概率為1收斂到全局最優(yōu)解！1/12/2023智能技術課程－－葉東毅遺傳算法的應用染色體編碼：視具體問題而定，可以整數(shù)序列串，也可以實數(shù)序列。適應值函數(shù)的定義，如何評估？交叉算子的本質：保持父代基因段或信息；變異算子的本質：新解的實質多樣性；如何定義這2個演化算子，使之保持解的可行性？（特別是約束情況下？）參數(shù)設定問題。1/12/2023智能技術課程－－葉東毅SAT問題（無約束）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；求得一個解！1/12/2023智能技術課程－－葉東毅編碼和適應值函數(shù)二進制編碼：直接用原問題的變量編碼；適應值：直接采用問題的目標函數(shù)F(x)?要么F(x)=1，找到解；要么F(x)=0，此時，如何區(qū)別不同個體的質量呢？如何引導選擇過程呢？適應值函數(shù)的合理確定問題！！F(x)=

f1(x)

f2(x)…fp(x);

fi(x)為析取項;適應值函數(shù)：Q(x)=Boolean(fi(x))；0Q(x)p如果Q(x)=p,

則x為一個解；可以有其他（可能更好）的方式定義適應值函數(shù)。1/12/2023智能技術課程－－葉東毅對稱全通路TSP問題（含約束）城市編號（頂點）序列為染色體（整數(shù)編碼）：

X=123…n的某一個排列，這樣最自然！如何定義交叉、變異呢？簡單交換或變異導致不可行的解：12435+23154=12154+23435

適應值函數(shù)：距離總和。采用二進制編碼？按照邊，但是需要判斷頂點集合的重疊性。同時，邊數(shù)遠遠多于頂點數(shù)。另外，面臨演化算子的設計問題。不合適！1/12/2023智能技術課程－－葉東毅X=123456789;Y=324695781X’=123456798

Y’=324691

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

---貪心+遺傳給定每個頂點具有加權的圖和n種顏色,圖著色問題：從n種顏色的集合中選擇一種顏色到任一個頂點上，但要滿足任