國科大中科院算法遺傳算法1210

啟發(fā)式算法

三、遺傳算法生物進(jìn)化

生命自從在地球上誕生以來，就開始了漫長的生物演化歷程，低級、簡單的生物類型逐漸發(fā)展為高級、復(fù)雜的生物類型。這一過程已經(jīng)由古生物學(xué)、胚胎學(xué)和比較解剖學(xué)等方面的研究工作所證實。生物進(jìn)化的原因自古至今有著各種不同的解釋，其中被人們廣泛接受的是達(dá)爾文的自然選擇學(xué)說。

1825年至1828年在愛丁大學(xué)學(xué)醫(yī)，后進(jìn)入劍橋大學(xué)學(xué)習(xí)神學(xué)。1831年從劍橋大學(xué)畢業(yè)后，以博物學(xué)家的身份乘海軍勘探船“貝格爾號（Beagle）”作歷時5年（1831－1836）的環(huán)球旅行，觀察和搜集了動物、植物和地質(zhì)等方面的大量材料，經(jīng)過歸納整理和綜合分析，形成了生物進(jìn)化的概念。

1859年出版《物種起源（On

theOriginofSpecies）》，全面提出以自然選擇（TheoryofNaturalSelection）為基礎(chǔ)的進(jìn)化學(xué)說。該書出版震動當(dāng)時的學(xué)術(shù)界，成為生物學(xué)史上的一個轉(zhuǎn)折點。自然選擇的進(jìn)化學(xué)說對各種唯心的神造論、目的論和物種不變論提出根本性的挑戰(zhàn)。使當(dāng)時生物學(xué)各領(lǐng)域已經(jīng)形成的概念和觀念發(fā)生根本性的改變。

達(dá)爾文（CharlesRobertDarwin，1809－1882）英國博物學(xué)家，進(jìn)化論的奠基人。1809年2月12日，出生于英國醫(yī)生家庭。物競天擇，適者生存

自然選擇學(xué)說認(rèn)為，生物要生存下去，就必須進(jìn)行生存斗爭。生存斗爭包括種內(nèi)斗爭、種間斗爭以及生物與無機(jī)環(huán)境之間的斗爭三個方面。在生存斗爭中，具有有利變異(mutation)的個體容易存活下來，并且有更多的機(jī)會將有利變異傳給后代，具有不利變異的個體容易被淘汰，產(chǎn)生后代的機(jī)會也少得多。因此，凡是在生存斗爭中獲勝的個體都是對環(huán)境適應(yīng)性比較強(qiáng)的。達(dá)爾文把這種在生存斗爭中適者生存、不適者淘汰的過程叫做自然選擇。達(dá)爾文的自然選擇學(xué)說表明，遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。遺傳算法（GeneticAlgorithm）遺傳算法借鑒生物界自然選擇原理和自然遺傳機(jī)制而形成的一種迭代式自適應(yīng)概率性全局優(yōu)化搜索算法。模擬達(dá)爾文“優(yōu)勝劣汰、適者生存”的原理激勵好的結(jié)構(gòu)模擬孟德爾遺傳變異理論在迭代過程中保持已有結(jié)構(gòu)，同時尋找更好的結(jié)構(gòu)

70年代初期由美國Michigan大學(xué)的Holland教授發(fā)展起來的。以1975年Holland的專著《AdaptationinnaturalandArtificialsystems》出版為標(biāo)志。遺傳算法基本思想：從一組解的初值開始進(jìn)行搜索，這組解稱為一個種群，種群由一定數(shù)量、通過基因編碼的個體組成，其中每一個個體稱為染色體。不同個體通過染色體的復(fù)制、交叉和變異又生成新的個體，依照適者生存的規(guī)則，個體也在一代一代進(jìn)化，通過若干代的進(jìn)化最終得出條件最優(yōu)的個體。遺傳算法（GA）個體（Individual）就是模擬生物個體而對問題中的候選解的一種稱呼，一個個體也就是搜索空間中的一個點。種群（population）：是模擬生物種群而由若干個體組成的群體,它一般是整個搜索空間的一個很小的子集。種群中含有的個體的數(shù)量叫做種群的規(guī)模(populationsize)。人工智能范疇符號智能的特點是以知識為基礎(chǔ)，偏重于邏輯推理計算智能則是以數(shù)據(jù)為基礎(chǔ)，偏重于數(shù)值計算。遺傳算法∈演化計算∈計算智能考慮如下優(yōu)化問題：這里f是X上的一個正值函數(shù)，即對任意x∈X，f(x)>0。X是問題的解空間，即問題的所有可能解全體。它可以是一個有限集合(如組合優(yōu)化問題)，也可以是實空間Rn的一個子集(如連續(xù)優(yōu)化問題)等。對以上問題，我們通常用兩類方法來求解之，一類是解析法，通過一定的手段直接計算出問題的解，另一類是迭代法，給出問題的一個初始猜測，然后從此初始點出發(fā)，逐步迭代，直至達(dá)到停機(jī)條件。遺傳算法也是一種迭代法，但它有別于傳統(tǒng)的迭代法。設(shè)計一個遺傳算法要涉及到以下步驟：確定編碼方案確定適應(yīng)值函數(shù)選擇策略的確定遺傳算子的設(shè)計確定算法的終止準(zhǔn)則控制參數(shù)的選取例編碼方案變量是演化算法的表現(xiàn)型形式。編碼是將優(yōu)化問題解空間中可行解（個體），即設(shè)計變量映射到GA中的基因型數(shù)據(jù)結(jié)構(gòu)。我們這里采用二進(jìn)制編碼，將某個變量值代表的個體表示為一個{0,1}二進(jìn)制串。串長取決于求解的精度。如果確定求解精度到3位小數(shù)，由于區(qū)間長度為1，編碼的二進(jìn)制串長至少需要10位。二進(jìn)制串轉(zhuǎn)化為十進(jìn)制：如：s=<1000110001>x’=561x=0.548<0000000000>與<1111111111>表示區(qū)間端點0和1。

基因型：1000110001表現(xiàn)型：0.548編碼解碼個體（染色體）基因隨機(jī)生成初始種群：S1=<1110001110>,x1=0.890S2=<0101000111>,x2=0.320S3=<0011001101>,x3=0.200S4=<1011110011>,x4=0.738S5=<1001101101>,x5=0.607S6=<0111011000>,x6=0.461S7=<1111001100>,x7=0.950S8=<0000100101>,x8=0.036構(gòu)造適應(yīng)值函數(shù)

直接將目標(biāo)函數(shù)作為適應(yīng)值函數(shù):f(x)=sinx+2e-x-1有了適應(yīng)值函數(shù)，可以對初始種群進(jìn)行評估。S1(0)=<1110001110>,f(x1)=0.598S2(0)

=<0101000111>,f(x2)=0.767S3(0)

=<0011001101>,f(x3)=0.836S4(0)

=<1011110011>,f(x4)=0.629S5(0)

=<1001101101>,f(x5)=0.660S6(0)

=<0111011000>,f(x6)=0.706S7(0)

=<1111001100>,f(x7)=0.578S8(0)

=<0000100101>,f(x8)=0.965選擇策略基于適應(yīng)值比例的選擇：繁殖池(breedingpool)選擇首先按下式計算其相對適應(yīng)值：其中fi是群體中第i個個體的適應(yīng)值，N是群體的規(guī)模。每個個體的繁殖量為：Ni=round(reli·N)其中round(x)表示與x距離最小的整數(shù)。將每個個體復(fù)制Ni個生成一個臨時群體，即繁殖池。輪盤賭選擇方法

輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n，個體i的適應(yīng)度為Fi，則個體i被選中遺傳到下一代群體的概率為：

A

B

C

D

E

rel2=0.134,N2=1rel3=0.146,N3=1rel4=0.110,N4=1rel5=0.115,N5=1rel6=0.123,N6=1rel7=0.101,N7=1rel8=0.168,N8=1繁殖池：s1(0),s2(0),s3(0),s4(0),s5(0),s6

(0),s7(0),

s8(0)

遺傳算子的設(shè)計a.雜交單點雜交：雜交概率pc=0.75，6個個體參加雜交s2(0)和s6(0),s1(0)和s5(0),s3(0)和s4(0)s2(0)=<0101|000111>s’2=<0101|011000>,f(s’2)=0.644s6(0)=<0111|011000>s’6=<0111|000111>,f(s’6)=0.712s1(0)=<111|0001110>s’1=<111|1101101>,f(s’1)=0.580s5(0)=<100|1101101>s’5=<100|0001110>,f(s’5)=0.687s3(0)=<00110011|01>s’3=<00110011|11>,f(s’3)=0.834s4(0)=<10111100|11>s’4=<10111100|01>,f(s’4)=0.629b.變異變異概率pm=0.02，10*8*0.02=1.6，隨機(jī)選取2個基因位進(jìn)行變異s6(0)=<0111011000>s’6=<0111011100>f(s’6)=0.704s3(0)=<0011001101>s’3=<0010001101>f(s’2)=0.880新群體：所有子代和父代中最好的8個個體(5)確定算法的終止準(zhǔn)則a.遺傳運(yùn)算的終止進(jìn)化代數(shù)T，一般取為100~500b.最好個體在若干代內(nèi)無改變(6)控制參數(shù)的選取a.種群規(guī)模N，一般取為20~100b.雜交概率pc，一般取為0.4~0.9c.變異概率pm,

一般取為0.001~0.1SGA的形式化描述

GA＝(P(0),N,l,s,g,p,f,t)初始種群：P(0)＝(a1(0),a2(0),…,aN(0))∈IN位串空間：I={0,1}l

，l表示二進(jìn)制串的長度種群規(guī)模：N選擇策略：s:IN→IN遺傳算子g：通常包括繁殖算子Or:I→I、雜交算子Oc:I×I→I×I和變異算子Om:I→I遺傳算子的操作概率p：包括繁殖概率pr、雜交概率pc和變異概率pm；f:I→R+是適應(yīng)函數(shù)；t:IN→{0,1}是終止準(zhǔn)則。SGA的流程圖產(chǎn)生初始群體是否滿足停止準(zhǔn)則是輸出結(jié)果并結(jié)束計算個體適應(yīng)度值比例選擇運(yùn)算單點交叉運(yùn)算基本位變異運(yùn)算否產(chǎn)生新一代群體SGA的理論基礎(chǔ)（1）

模式是指種群個體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結(jié)構(gòu)。在二進(jìn)制編碼中，模式是基于三個字符集(0,1,*)的字符串，符號*代表任意字符，即0或者1，如101**1。模式H中確定位置的個數(shù)稱為模式H的階，記作O(H)。例如O(10**1)=3。模式H中第一個確定位置和最后一個確定位置之間的距離稱為模式H的定義距，記作δ(H)。例如(10**1)=4。

SGA的理論基礎(chǔ)（2）

模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。SGA的理論基礎(chǔ)（3）

模式定理（SchemaTheorem）（

Holland

1975，《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性》

）：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性，從理論上保證了遺傳算法是一個可以尋求最優(yōu)可行解的優(yōu)化過程，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)，被認(rèn)為是遺傳算法的基本定理。

SGA的理論基礎(chǔ)（4）

設(shè)X=IN=({0,1}l)N為SGA群體狀態(tài)的空間，是任一模式，表示SGA在第t代時的群體，f：I

R1為適應(yīng)函數(shù)模式H的平均適應(yīng)值：P(t)的平均適應(yīng)值：

SGA的理論基礎(chǔ)（5）

設(shè)SGA的雜交概率和變異概率分別為pc和pm，模式H的定義長度為、階為，第t+1代群體P(t+1)含有H中元素個數(shù)的期望值記為則：

SGA的理論基礎(chǔ)（6）

積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。遺傳算法的收斂性(1)種群太小則不能提供足夠的采樣點，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。遺傳算法的收斂性(2)交叉操作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破壞掉；概率太小時，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。變異操作是對種群模式的擾動，有利于增加種群的多樣性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機(jī)搜索算法。遺傳算法的本質(zhì)

遺傳算法本質(zhì)上是對染色體模式所進(jìn)行的一系列運(yùn)算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。遺傳算法的特點（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。遺傳算法的改進(jìn)

遺傳欺騙問題：在遺傳算法進(jìn)化過程中，有時會產(chǎn)生一些超常的個體，這些個體因競爭力太突出而控制了選擇運(yùn)算過程，從而影響算法的全局優(yōu)化性能，導(dǎo)致算法獲得某個局部最優(yōu)解。

遺傳算法的改進(jìn)途徑（1）對編碼方式的改進(jìn)（2）對遺傳算子的改進(jìn)（3）對控制參數(shù)的改進(jìn)（4）對執(zhí)行策略的改進(jìn)編碼方式在設(shè)計遺傳算法時，編碼表示與遺傳算子尤其是雜交算子是同步考慮的，如果編碼處理不當(dāng)，在遺傳空間中因雜交而生成的個體映射到問題空間時，有可能成為無用解，我們稱形成無用解的染色體為致死因子。同時，即使逆映射到問題空間的是有用解，但也可能是和雙親完全無緣的解。編碼要避免在問題空間中形成這些不適當(dāng)?shù)膫€體。評估編碼策略常采用以下3個規(guī)范：1.完備性(completeness)：問題空間中的所有點(候選解)都能作為演化空間中的點(染色體)表現(xiàn)；2.健全性(soundness)：演化空間中的染色體能對應(yīng)所有問題空間中的候選解；

3.非冗余性(nonredundancy)：染色體和候選解一一對應(yīng)。

二進(jìn)制編碼（BinaryEncoding）將原問題的解空間映射到位串空間{0,1}l上，然后在位串空間上進(jìn)行演化操作。結(jié)果再通過解碼過程還原成其表現(xiàn)型以進(jìn)行適應(yīng)值的評估。很多數(shù)值與非數(shù)值問題都可以用二進(jìn)制編碼以應(yīng)用演化算法。二進(jìn)制編碼有如下優(yōu)點：二進(jìn)制編碼類似于生物染色體的組成，算法易于用生物遺傳理論來解釋并使得演化操作如雜交、變異很容易實現(xiàn)；采用二進(jìn)制編碼時，算法處理的模式數(shù)最多；這種編碼方式便于模式定理進(jìn)行分析，因為模式定理就是以二值編碼為基礎(chǔ)的。

二進(jìn)制編碼在求解連續(xù)數(shù)值優(yōu)化問題時的缺點：相鄰整數(shù)的二進(jìn)制編碼可能具有較大的Hamming距離，這種缺陷將降低演化算子的搜索效率，二進(jìn)制編碼的這一缺點有時稱為Hamming懸崖（HammingCliffs）；二進(jìn)制編碼時，所需解的精度確定后，串長也就確定了，當(dāng)需要改變精度時，很難在算法執(zhí)行過程中進(jìn)行調(diào)整，從而使算法缺乏微調(diào)的功能；當(dāng)應(yīng)用于高維、高精度數(shù)值問題時，產(chǎn)生的二進(jìn)制位串很長，搜索空間非常大，從而使算法的搜索效率很低。

格雷編碼（GrayEncoding）格雷編碼也稱為反射二進(jìn)制編碼，其目的是克服二進(jìn)制編碼的Hamming懸崖的缺點。格雷編碼使得兩個相鄰的整數(shù)的編碼只差一個二進(jìn)制位。二進(jìn)制串與格雷串的轉(zhuǎn)換關(guān)系如下：設(shè)二進(jìn)制串對應(yīng)的格雷串為，則它們之間有如下的變換關(guān)系：其中表示模2加法運(yùn)算。

格雷編碼（GrayEncoding）

BinaryCodeGrayCode000000001001010011011010100110101111110101111100引入了另一種形式的cliff!實數(shù)編碼為了克服二進(jìn)制編碼的缺點，對于問題的變量是實向量的情形，可以直接采用實進(jìn)制進(jìn)行編碼。這樣，便可直接在解的表現(xiàn)型上進(jìn)行遺傳操作。從而便于引入與問題領(lǐng)域相關(guān)的啟發(fā)式信息以增加遺傳算法的搜索能力?！霸谌斯みz傳和演化搜索方案中，實型編碼或浮點基因的使用已經(jīng)有很長的歷史了，盡管是有爭議的，但它們在以后的使用趨勢仍在上升。這種上升的使用趨勢多少有些使熟知基本遺傳算法(GA)理論的研究者感到驚訝，因為簡單的分析似乎建議通過使用低基數(shù)性的字母表可以增強(qiáng)模式的處理，而來自于實算的結(jié)論似乎直接反駁了這種觀點，實型編碼在許多實際問題里工作得較好。”（Goldberg）

對實數(shù)編碼的情形，從理論上講，二