爾濱工程演化計算及布谷鳥算法性能改進

1、Harbin Engineering University 演化計算及布谷鳥算法性能改進劉延龍哈爾濱工程大學(xué)自動化學(xué)院Harbin Engineering University 生物進化優(yōu)化搜索解免疫系統(tǒng)Harbin Engineering University Harbin Engineering University 1859年出版Onthe Origin of Species一書，全面提出以自然選擇（Theory of Natural Selection）為基礎(chǔ)的進化學(xué)說。Charles Robert Darwin，18091882達爾文把在生存斗爭中適者生存、不適者淘汰的過程叫做自然選

2、擇。達爾文的自然選擇學(xué)說表明，遺傳和變異是決定生物進化的內(nèi)在因素。自然選擇學(xué)說Harbin Engineering University 生物進化演化算法適應(yīng)環(huán)境以求生存模擬進化最優(yōu)化解Harbin Engineering University 演化算法Harbin Engineering University 基本結(jié)構(gòu)如下：隨機初始化種群P(0)=x1, x2,xN , t:=0;計算P(0)中個體的適應(yīng)值;While(不滿足終止準(zhǔn)則)do由P(t)通過遺傳操作形成新的種群P(t+1);計算P(t+1)中個體的適應(yīng)值, t=t+1;演化算法基本結(jié)構(gòu)Harbin Engineering Uni

3、versity 設(shè)計演化算法需要詳細(xì)指明以下構(gòu)成成分:個體的編碼-能夠有效地執(zhí)行遺傳操作適應(yīng)函數(shù)-區(qū)別種群中個體好壞的唯一方法父體選擇策略；變化算子；存活選擇策略；參數(shù)設(shè)置；種群的初始化；遺傳算子的設(shè)計；終止準(zhǔn)則；編程上機運行；演化算法設(shè)計Harbin Engineering University 變化算子 重組算子:重組算子將兩個或多個父體的信息進行組合，得到一個或多個后代染色體，期望通過重組較好父體的信息得到更好的后代染色體。 變異算子:變異算子改變一個染色體的信息，得到一個新的染色體。其目的是通過引入新的染色體來增加種群的多樣性，擴大搜索空間，從而避免演化算法陷入局部最優(yōu)。在不同的演化算

4、法中，變化算子所起的作用有所不同在遺傳算法中，重組算子是一個主要的變化算子，變異算子起輔助性的作用。在演化策略中，變異算子是一種主要的遺傳算子，重組算子起輔助性的作用。在演化規(guī)劃中，只使用變異算子，根本不使用重組算子。Harbin Engineering University 參數(shù)設(shè)置 不同的演化算法有不同的參數(shù)。譬如說，遺傳算法的種群規(guī)模、雜交概率和變異概率；演化策略中的變異步長；遺傳程序設(shè)計中的樹的深度等。參數(shù)設(shè)置有以下兩種主要方法： (1) 參數(shù)調(diào)整：參數(shù)調(diào)整是算法設(shè)計中的一個典型方法，也是實際中用的最多的方法之一。 (2) 參數(shù)控制：參數(shù)控制是預(yù)先給定初始參數(shù)值，在算法的運行過程中，對

5、參數(shù)進行動態(tài)地變更。 Harbin Engineering University 例子：172394,5，86Harbin Engineering University 演化算法性能度量算法性能評估成功率有效性效率Harbin Engineering University 演化算法性能度量 對于學(xué)術(shù)研究來說，下面是一些常見的實驗?zāi)繕?biāo)： 對某個給定問題，演化算法可以得到一個好的解；證明演化算法可應(yīng)用于某個領(lǐng)域；證明具有某些新特征的演化算法比某些演化算法要好；證明對某些問題演化算法比某些傳統(tǒng)算法要好；觀察算法的性能與參數(shù)設(shè)置之間的關(guān)系。Harbin Engineering University 遺

6、傳算法(genetic algorithm，簡稱GA)遺傳程序設(shè)計(genetic programming，簡稱GP)演化規(guī)劃(evolutionary programming，簡稱EP)演化策略(evolution strategy，簡稱ES)四個分支組成。演化算法分支Harbin Engineering University 布谷鳥算法及其性能改進生物繁殖特點：巢寄生Harbin Engineering University 萊維飛行步長：正態(tài)分布：優(yōu)點：能擴大搜索范圍、增加種群多樣性, 更容易跳出局部最優(yōu)點。Harbin Engineering University 布谷鳥算法是模擬布谷

7、鳥尋窩產(chǎn)卵隨機飛行的過程位置更新公式：Harbin Engineering University 布谷鳥算法算法流程丟棄較差的解，始終保留最好的解目標(biāo)函數(shù)f(x)初始化具有N個鳥巢的種群終止條件萊維飛行得到一個布谷鳥ino利用函數(shù)評估判斷這個布谷鳥結(jié)束并且將結(jié)果可視化yesHarbin Engineering University 布谷鳥算法改進優(yōu)點：引入慣性權(quán)重，跳出局部最優(yōu)，加快后期收斂速度Harbin Engineering University 將改進的布谷鳥算法與罰函數(shù)法結(jié)合求解最優(yōu)化問題Harbin Engineering University 編程運行以及仿真測試Harbin Engineering University Harbin Engineering University Harbin Engineering University 演化算法的研究方向演化算法 + 程序結(jié)構(gòu) = 自動程序設(shè)計演化算法 + 可編程器件 = 演化硬件演化算法 + 數(shù)據(jù)結(jié)構(gòu) = Data Min