智能控制系統(tǒng)chapter

第11章進(jìn)化算法

11.1標(biāo)準(zhǔn)遺傳算法

11.2進(jìn)化算法的分析11.3進(jìn)化算法的性能分析19世紀(jì)50年代，英國生物學(xué)家達(dá)爾文（C.R.Darwin，1809~1882)根據(jù)他對世界各地生活的考察資料和人工選擇的實(shí)驗(yàn)，提出了生物進(jìn)化論。根據(jù)達(dá)爾文的進(jìn)化論，生物發(fā)展進(jìn)化主要有三個(gè)原因，就是遺傳、變異和選擇。遺傳就使子代總是和父代相似，遺傳性是一切事物所共有的特性，遺傳是生物進(jìn)化的基礎(chǔ)。變異是指子代是父代有某些不相似的現(xiàn)象，即子代永遠(yuǎn)不會(huì)和父代完全一樣。生物的變異性為生物的進(jìn)化和發(fā)展創(chuàng)造了條件。選擇決定生物進(jìn)化的方向，所謂選擇是指保留和淘汰的意思。選擇分為人工選擇和自然選擇選擇就是優(yōu)生劣汰生物就是在遺傳、變異與選擇三種因素的綜合作用過程中，不斷的向前發(fā)展和進(jìn)化。選擇是通過遺傳和變異起作用變異為選擇提供資料，遺傳鞏固與積累選擇的資料選擇則能控制變異和遺傳的方向，使變異和遺傳向著適應(yīng)環(huán)境方向發(fā)展。遺傳算法（GeneticAlgorithm，簡稱GA）是建立在自然選擇和自然遺傳學(xué)機(jī)理基礎(chǔ)上的迭代自適應(yīng)概率性搜索算法。該算法最早是由美國的J.H.Holland教授1975年提出的一種模仿生物進(jìn)化過程的最優(yōu)化方法它模擬了自然選擇和自然遺傳過程中發(fā)生的繁殖，交換、變異現(xiàn)象，根據(jù)適者生存、優(yōu)勝劣汰的自然法則利用遺傳算子：選擇、交叉、變異逐代產(chǎn)生、優(yōu)選個(gè)體，最終搜索到較優(yōu)的個(gè)體。遺傳算法具有不需要求梯度、能得到全局最優(yōu)解、算法簡單、可并行處理等優(yōu)點(diǎn)遺傳算法已成功應(yīng)用與各種復(fù)雜問題的優(yōu)化中，在許多傳統(tǒng)優(yōu)化技術(shù)難以解決的場合更顯示出其優(yōu)越性。遺傳算法術(shù)語遺傳學(xué)遺傳算法染色體(chromosome)字符串（或樣本）個(gè)體(individul)基因(gene)每個(gè)字符串代(generation)種群繁殖（reproduction）再生選擇、復(fù)制交配(crossover)交叉、交換變異(mutation)變異11.1.1遺傳算法的基本特點(diǎn)

遺傳算法有以下的基本特點(diǎn)

1）遺傳算法通過編碼將優(yōu)化問題的自然參數(shù)編碼成有限長度數(shù)字串位，故遺傳算法基本上不受函數(shù)約束條件（如連續(xù)、可導(dǎo)、單調(diào)等）特性的限制，能在極其廣泛的問題求解過程中發(fā)揮作用。2）傳統(tǒng)搜索法基本上是點(diǎn)到點(diǎn)的搜索方法，遺傳算法是全局優(yōu)化方法3）遺傳算法在選擇過程中，依據(jù)一定概率隨機(jī)地選擇個(gè)體是為了摹仿自然界進(jìn)化過程中的“適者生存”、“優(yōu)勝劣汰”的競爭規(guī)則。11.1.2遺傳算法的基本操作

遺傳算法是一種對群體的操作，該操作是以群體中的所有個(gè)體為對象。1）選擇（復(fù)制）操作實(shí)現(xiàn)選擇操作的方式很多，其類型主要有以下幾種：（1）直接基于適應(yīng)度的比例選擇機(jī)制

a）賭輪(Roulettewheelselection)選擇方式；b）期望值模型(Expectedvaluemodel)選擇方式；c）隨機(jī)競爭(Stochastictournament)選擇方式

（2）間接基于適應(yīng)度的非線性選擇機(jī)制a）線性標(biāo)定(Scaling)：b）冪函數(shù)標(biāo)定：c）指數(shù)標(biāo)定：（3）基于代溝(Generation)方式的種群選擇機(jī)制（4）基于小生境技術(shù)的種群選擇機(jī)制a）基于預(yù)選擇(preselection)機(jī)制的小生境技術(shù)b）基于種群(Crowding)機(jī)制的小生境技術(shù)c）基于共享(sharing)機(jī)制的小生境技術(shù)

2）交叉（交換）操作在設(shè)計(jì)交叉算子時(shí)，需要兼顧如下兩個(gè)基本要求：（1）交叉操作要有利于父串關(guān)鍵特征（模式）以及有利于變異的遺傳和繼承；（2）交叉操作要有利于的遺傳變異庫的更新和豐富。

簡單的交叉可分兩步進(jìn)行：首先對種群中的個(gè)體某一個(gè)概率值進(jìn)行隨機(jī)配對；其次在配對個(gè)體中隨機(jī)設(shè)定交叉處，被配對個(gè)體彼此交換部分信息。交叉操作類型一般有一點(diǎn)交叉(one-pointcrossover)；二點(diǎn)交叉(two-pointcrossover)；多點(diǎn)交叉(multi-pointcrossover)和一致交叉(uniformcrossover)幾種。3）變異操作11.1.3遺傳算法的設(shè)計(jì)步驟

在應(yīng)用遺傳算法求解具體問題時(shí)，主要考慮以下幾個(gè)問題：

1）參數(shù)編碼對尋優(yōu)參數(shù)編碼。確定尋優(yōu)參數(shù)和各參數(shù)的變化范圍，將各尋優(yōu)參數(shù)用無符號(hào)的二進(jìn)制數(shù)表示。設(shè)某尋優(yōu)參數(shù)a則b可由下式求得：

的變化范圍是，若用m位二進(jìn)制數(shù)b來表示，再將所有尋優(yōu)參數(shù)的二進(jìn)制數(shù)串聯(lián)成一個(gè)二進(jìn)制的字符串s，又稱為樣本。若有r個(gè)尋優(yōu)參數(shù)，每個(gè)參數(shù)都用m位二位。

進(jìn)制數(shù)表示，則字符串s共有2）種群初始化確定遺傳算法所使用的各參數(shù)的取值，如群體規(guī)模n，交叉、變異等發(fā)生的概率。若無先驗(yàn)知識(shí)，可隨機(jī)產(chǎn)生n個(gè)字符串（樣本），組成一個(gè)種群(Population)。

3）求各樣本的適配值

根據(jù)編碼方法以及問題的要求，設(shè)計(jì)一個(gè)適配度函數(shù)f，用以測量和評價(jià)各解的性能。這個(gè)適配度函數(shù)實(shí)際上對應(yīng)于最優(yōu)化的指標(biāo)函數(shù)。用每個(gè)樣本對應(yīng)的一組尋優(yōu)參數(shù)計(jì)算其適配值(FitnessValue)，并按從優(yōu)到劣的次序排列。

4）選擇（Seletion)

求出各樣本的適配度：

，i=1,2,...,n

對種群中各樣本以優(yōu)于作為父母樣本，并隨機(jī)的兩兩配對，用交叉和變異的方法繁殖后代。

值的原則選擇出來5）交叉（Crossover)

在父母樣本A、B的字符串中隨機(jī)的產(chǎn)生一個(gè)分段點(diǎn)，將分段點(diǎn)之后的子串互換，生成兩個(gè)子女樣本，如下列：A=1101/011 A’=1101/110B=0010/110 B’=0010/011交換概率可定為0.6~1.06）變異(mutation)

在每個(gè)子女樣本的字符串中隨機(jī)的選擇一位，將其數(shù)值求反（即1變?yōu)?，0變?yōu)?）。變異概率0.001~0.01。7）循環(huán)

將新產(chǎn)生的子女樣本加入原樣本中，或可以直接加入前面被選出的優(yōu)秀的父輩樣本中，組成新種群。到此，一輪遺傳操作完成。新種群返回到3），再用每個(gè)樣本對應(yīng)的一組尋優(yōu)參數(shù)計(jì)算其適配值，并按從優(yōu)到劣的次序排列，并進(jìn)行下一次迭代計(jì)算，直至達(dá)到滿意的性能指標(biāo)（或適配值）。11.1.4遺傳算法的實(shí)質(zhì)

從模式的角度看，遺傳算法的搜索過程其本質(zhì)是對隱含在可行解編碼串內(nèi)的“模式”的抽樣過程。關(guān)于遺傳算法的收斂性，標(biāo)準(zhǔn)遺傳算法在變異概率為0時(shí)，必然收斂于一個(gè)吸收狀態(tài)，但不能確保收斂于全局最優(yōu)解；標(biāo)準(zhǔn)遺傳算法在變異概率不為零時(shí)，是不收斂的。11.2進(jìn)化算法的分析

根據(jù)效仿生物進(jìn)化過程中側(cè)重點(diǎn)不同，可將進(jìn)化算法分為1）遺傳算法2）進(jìn)化規(guī)劃3）進(jìn)化策略4）遺傳編程遺傳算法遺傳算法的選擇是對“適者生存，優(yōu)勝劣汰”的簡單模擬基本遺傳算法設(shè)計(jì)以下5大要素：參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作的設(shè)計(jì)和控制參數(shù)的設(shè)定遺傳算法是用字符串作為染色體去表達(dá)所要解決的問題，而且字符串的長度一般是固定的。然而現(xiàn)實(shí)中的問題往往是很復(fù)雜的，有時(shí)不能用簡單的字符串表達(dá)問題的所有性質(zhì)，于是就產(chǎn)生了遺傳編程（GP）。遺傳編程及其特點(diǎn)遺傳編程用廣義的計(jì)算機(jī)程序形式表達(dá)問題，它的結(jié)構(gòu)和大小都是可以變化的，從而可以更靈活地表達(dá)復(fù)雜的事物結(jié)構(gòu)。遺傳編程與遺傳算法的工作過程基本類似，都經(jīng)歷初始群體的生成、個(gè)體適應(yīng)度的計(jì)算、選擇、交叉、變異、反復(fù)迭代過程。它們的差別主要體現(xiàn)在問題的表達(dá)上：遺傳規(guī)劃是用廣義的層狀（樹狀）結(jié)構(gòu)的計(jì)算機(jī)程序表達(dá)問題，在遺傳進(jìn)化過程中個(gè)體不斷動(dòng)態(tài)變更結(jié)構(gòu)及大小。遺傳編程的主要步驟（1）個(gè)體的描述。遺傳編程中的個(gè)體用廣義層次的計(jì)算機(jī)程序表達(dá)，它由函數(shù)集F和終止符集T組成。函數(shù)集F內(nèi)的函數(shù)可以是+、-、*、/等算術(shù)運(yùn)算或sin、cos、log、exp等標(biāo)準(zhǔn)數(shù)學(xué)函數(shù)。終止符集T內(nèi)的終止符可以是x、y、z等變量或a、b、等常量。將函數(shù)和終止符隨機(jī)的組合就可以可到不同的個(gè)體表達(dá)式。（2）初始群體的形成。初始群體中染色體（樹）用隨機(jī)方法產(chǎn)生的，即從函數(shù)集F及終止符集T中隨機(jī)選取函數(shù)和終止符組成各種復(fù)雜的數(shù)學(xué)函數(shù)（表達(dá)式）。（3）適應(yīng)度的計(jì)算。遺傳編程中常用的適應(yīng)度有原始適應(yīng)度或經(jīng)過標(biāo)度變換的調(diào)整適應(yīng)度。最常用的原始適應(yīng)度的定義是以誤差形式出現(xiàn)的，即用該表達(dá)式所計(jì)算實(shí)例的值與該實(shí)例實(shí)際值的誤差之和作為個(gè)體的適應(yīng)度。（4）遺傳操作。遺傳編程一般使用選擇和交叉來產(chǎn)生新個(gè)體。進(jìn)化策略

進(jìn)化策略用傳統(tǒng)的實(shí)數(shù)型去表達(dá)所要解決的問題，其表達(dá)形式為：公式中含有服從正態(tài)分布的、均值為零，有標(biāo)準(zhǔn)差的隨機(jī)數(shù)。進(jìn)化策略中個(gè)體的進(jìn)化主要采用突變。在進(jìn)化策略中，經(jīng)過突變，來產(chǎn)生新個(gè)體的重組（遺傳算法中的交叉操作）進(jìn)化策略也是一個(gè)反復(fù)迭代的過程。它從隨機(jī)產(chǎn)生的初始群體出發(fā)，經(jīng)過突變，重組，選擇等遺傳操作，改進(jìn)群體的質(zhì)量，逐漸得到最優(yōu)解。進(jìn)化規(guī)劃進(jìn)化規(guī)劃的進(jìn)化也是主要依賴突變：參照個(gè)體的適應(yīng)度添加一個(gè)隨機(jī)數(shù)來進(jìn)行突變，產(chǎn)生下一代新個(gè)體為了增加進(jìn)化過程中的自適應(yīng)調(diào)整功能，人們在突變中添加了方差的概念，產(chǎn)生了元進(jìn)化規(guī)劃，個(gè)體表達(dá)式為：新個(gè)體而是在舊個(gè)體的基礎(chǔ)上添加一個(gè)隨機(jī)數(shù)，該添加量的大小取決于個(gè)體的方差，而方差在每次進(jìn)化中又有自適應(yīng)的調(diào)整。進(jìn)化規(guī)劃的工作流程類似于其他進(jìn)化算法，同樣經(jīng)歷產(chǎn)生初始群體→突變產(chǎn)生新個(gè)體→計(jì)算個(gè)體適應(yīng)度→選擇→組成新群體，然后反復(fù)迭代，一代代地進(jìn)化直至達(dá)到最優(yōu)解。11.3進(jìn)化算法的性能分析4種進(jìn)化算法在總體的思路上是大體相同的，都經(jīng)歷了編碼—產(chǎn)生初始群體—通過遺傳操作產(chǎn)生子代個(gè)體—選擇—組成新群體，然后反復(fù)迭代，尋找最優(yōu)解的這樣一個(gè)工作流程。但在具體的操作上每種算法又有著各自的特點(diǎn)。編碼策略標(biāo)準(zhǔn)的遺傳算法采用二進(jìn)制0/1字符編碼，即染色體是固定長度的二進(jìn)制編碼位串。這種二進(jìn)制編碼不受函數(shù)約束條件（如連續(xù)，可導(dǎo)，單調(diào)）特性的限制，通用性好，遺傳操作簡單，能在極其廣泛的問題求解中發(fā)揮作用。但當(dāng)變量眾多，取值范圍大或無法給定范圍時(shí)，二進(jìn)制編碼使GA收斂速度降低，同時(shí)在變量的編碼與解碼過程中，會(huì)導(dǎo)致有用信息的喪失，且存在計(jì)算量大的缺點(diǎn)。遺傳規(guī)劃是用廣義的層狀（樹狀）結(jié)構(gòu)的計(jì)算機(jī)程序來表示染色體結(jié)構(gòu)。在GP中構(gòu)成染色體的主要元素是函數(shù)集和變/常量集合。函數(shù)可以是四則運(yùn)算和簡單的數(shù)學(xué)函數(shù)，如三角函數(shù)，對數(shù)函數(shù)，指數(shù)函數(shù)，以及代數(shù)操作，布爾操作，條件運(yùn)算，及面向問題的函數(shù)等。進(jìn)化策略和進(jìn)化規(guī)劃都采用十進(jìn)制實(shí)數(shù)編碼的形式消除了因編碼精度不夠使搜索空間中具有較優(yōu)適應(yīng)度的解無法表示的隱患。實(shí)數(shù)編碼具備了利用連續(xù)變量函數(shù)具有的漸變性的能力。更多的應(yīng)用在連續(xù)參數(shù)優(yōu)化問題中遺傳算法和遺傳編程是將原問題的解空間映射到位串空間，然后再實(shí)施遺傳操作，它強(qiáng)調(diào)個(gè)體基因結(jié)構(gòu)的變化對其適應(yīng)度的影響；進(jìn)化策略和進(jìn)化規(guī)劃是直接在解空間進(jìn)行操作，它強(qiáng)調(diào)進(jìn)化過程中從父代到子代行為的自適應(yīng)性和多樣性。選擇方法遺傳算法，遺傳編程和進(jìn)化規(guī)劃都強(qiáng)調(diào)基于概率的選擇機(jī)制。遺傳算法中選擇方式有很多，例如，賭輪選擇，聯(lián)賽選擇，排序選擇，競技選擇的等。遺傳編程的選擇操作方法與GA是相同的，只是其操作的對象不是二進(jìn)制的字符串，而是由函數(shù)和變/常量組成的表達(dá)式，這也是由其編碼方式?jīng)Q定的。

進(jìn)化規(guī)劃的選擇采用隨機(jī)性的q競爭選擇法。遺傳算法中的競技選擇就是來源于進(jìn)化規(guī)劃。進(jìn)化策略中的選擇是確定性的選擇，它嚴(yán)格根據(jù)適應(yīng)度的大小，將劣質(zhì)個(gè)體完全淘汰。進(jìn)化策略的確定性選擇明確地將某些個(gè)體排除在被選擇和復(fù)制之外，被成為滅絕選擇機(jī)制。理論上講，滅絕選擇機(jī)制破壞了種群的多樣性，容易使算法陷入早熟收斂，但進(jìn)化策略中的變異操作又彌補(bǔ)了這種多樣性的丟失。保留選擇機(jī)制維持了種群的多樣性，但由于一些“壞”個(gè)體的存在，使得算法的收斂性降低。遺傳算子

遺傳算法和遺傳編程都是將交叉(重組)作為主要的進(jìn)化算子，是產(chǎn)生子代新個(gè)體的主要方式，而突變只是一種輔助算子，突變的概率一般很低。進(jìn)化策略