第11章進化算法

11.1標準遺傳算法

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

遺傳算法有以下的基本特點

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

遺傳算法是一種對群體的操作，該操作是以群體中的所有個體為對象。1）選擇（復制）操作實現選擇操作的方式很多，其類型主要有以下幾種：（1）直接基于適應度的比例選擇機制

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

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

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

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

在應用遺傳算法求解具體問題時，主要考慮以下幾個問題：

1）參數編碼對尋優參數編碼。確定尋優參數和各參數的變化范圍，將各尋優參數用無符號的二進制數表示。設某尋優參數a則b可由下式求得：

的變化范圍是，若用m位二進制數b來表示，再將所有尋優參數的二進制數串聯成一個二進制的字符串s，又稱為樣本。若有r個尋優參數，每個參數都用m位二位。

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

3）求各樣本的適配值

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

4）選擇（Seletion)

求出各樣本的適配度：

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

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

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

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

在每個子女樣本的字符串中隨機的選擇一位，將其數值求反（即1變為0，0變為1）。變異概率0.001~0.01。7）循環

將新產生的子女樣本加入原樣本中，或可以直接加入前面被選出的優秀的父輩樣本中，組成新種群。到此，一輪遺傳操作完成。新種群返回到3），再用每個樣本對應的一組尋優參數計算其適配值，并按從優到劣的次序排列，并進行下一次迭代計算，直至達到滿意的性能指標（或適配值）。11.1.4遺傳算法的實質

從模式的角度看，遺傳算法的搜索過程其本質是對隱含在可行解編碼串內的“模式”的抽樣過程。關于遺傳算法的收斂性，標準遺傳算法在變異概率為0時，必然收斂于一個吸收狀態，但不能確保收斂于全局最優解；標準遺傳算法在變異概率不為零時，是不收斂的。11.2進化算法的分析

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

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

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

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