國(guó)科大中科院算法遺傳算法1210

啟發(fā)式算法

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

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

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

1859年出版《物種起源（On

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

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

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

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

基因型：1000110001表現(xiàn)型：0.548編碼解碼個(gè)體（染色體）基因隨機(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ù)，可以對(duì)初始種群進(jìn)行評(píng)估。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)選擇首先按下式計(jì)算其相對(duì)適應(yīng)值：其中fi是群體中第i個(gè)個(gè)體的適應(yīng)值，N是群體的規(guī)模。每個(gè)個(gè)體的繁殖量為：Ni=round(reli·N)其中round(x)表示與x距離最小的整數(shù)。將每個(gè)個(gè)體復(fù)制Ni個(gè)生成一個(gè)臨時(shí)群體，即繁殖池。輪盤賭選擇方法

輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n，個(gè)體i的適應(yīng)度為Fi，則個(gè)體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è)計(jì)a.雜交單點(diǎn)雜交：雜交概率pc=0.75，6個(gè)個(gè)體參加雜交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個(gè)基因位進(jìn)行變異s6(0)=<0111011000>s’6=<0111011100>f(s’6)=0.704s3(0)=<0011001101>s’3=<0010001101>f(s’2)=0.880新群體：所有子代和父代中最好的8個(gè)個(gè)體(5)確定算法的終止準(zhǔn)則a.遺傳運(yùn)算的終止進(jìn)化代數(shù)T，一般取為100~500b.最好個(gè)體在若干代內(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)制串的長(zhǎng)度種群規(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é)束計(jì)算個(gè)體適應(yīng)度值比例選擇運(yùn)算單點(diǎn)交叉運(yùn)算基本位變異運(yùn)算否產(chǎn)生新一代群體SGA的理論基礎(chǔ)（1）

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

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

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

模式定理（SchemaTheorem）（

Holland

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

）：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長(zhǎng)。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長(zhǎng)，確認(rèn)了結(jié)構(gòu)重組遺傳操作對(duì)于獲得隱并行性的重要性，從理論上保證了遺傳算法是一個(gè)可以尋求最優(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代時(shí)的群體，f：I

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

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

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

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

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

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

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

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

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

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

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

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

格雷編碼（GrayEncoding）

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

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