首頁 > 文章中心 > 正文

      不可微函數混合遺傳算法

      前言:本站為你精心整理了不可微函數混合遺傳算法范文,希望能為你的創作提供參考價值,我們的客服老師可以幫助你提供個性化的參考范文,歡迎咨詢。

      不可微函數混合遺傳算法

      摘要在浮點編碼遺傳算法中加入Powell方法,構成適于不可函數全局優化的混合遺傳算法。混合算法改善了遺傳算法的局部搜索能力,顯著提高了遺傳算法求得全局解的概率。由于只利用函數值信息,混合算法是一種求解可微和不可微函數全局優化問題的通用方法。

      關鍵詞全局最優;混合算法;遺傳算法;Powell方法

      1引言

      不可微非線性函數優化問題具有廣泛的工程和應用背景,如結構設計中使得結構內最大應力最小而歸結為極大極小優化(minmax)問題、數據魯棒性擬合中采取最小絕對值準則建立失擬函數等。其求解方法的研究越來越受到人們的重視,常用的算法有模式搜索法、單純形法、Powell方法等,但是這些方法都是局部優化方法,優化結果與初值有關。

      近年來,由Holland研究自然現象與人工系統的自適應行為時,借鑒“優勝劣汰”的生物進化與遺傳思想而首先提出的遺傳算法,是一種較為有效的求不可微非線性函數全局最優解的方法。以遺傳算法為代表的進化算法發展很快,在各種問題的求解與應用中展現了其特點和魅力,但是其理論基礎還不完善,在理論和應用上暴露出諸多不足和缺陷,如存在收斂速度慢且存在早熟收斂問題[1,2]。為克服這一問題,早在1989年Goldberg就提出混合方法的框架[2],把GA與傳統的、基于知識的啟發式搜索技術相結合,來改善基本遺傳算法的局部搜索能力,使遺傳算法離開早熟收斂狀態而繼續接近全局最優解。近來,文獻[3]和[4]在總結分析已有發展成果的基礎上,均指出充分利用遺傳算法的大范圍搜索性能,與快速收斂的局部優化方法結合構成新的全局優化方法,是目前有待集中研究的問題之一,這種混合策略可以從根本上提高遺傳算法計算性能。文獻[5]采用牛頓-萊佛森法和遺傳算法進行雜交求解旅行商問題,文獻[6]把最速下降法與遺傳算法相結合來求解連續可微函數優化問題,均取得良好的計算效果,但是不適于不可微函數優化問題。

      本文提出把Powell方法融入浮點編碼遺傳算法,把Powell方法作為與選擇、交叉、變異平行的一個算子,構成適于求解不可微函數優化問題的混合遺傳算法,該方法可以較好解決遺傳算法的早熟收斂問題。數值算例對混合方法的有效性進行了驗證。

      2混合遺傳算法

      編碼是遺傳算法應用中的首要問題,與二進制編碼比較,由于浮點編碼遺傳算法有精度高,便于大空間搜索的優點,浮點編碼越來越受到重視[7]。考慮非線性不可微函數優化問題(1),式中為變量個數,、分別是第個變量的下界和上界。把Powell方法嵌入到浮點編碼遺傳算法中,得到求解問題(1)如下混合遺傳算法:

      min(1)

      step1給遺傳算法參數賦值。這些參數包括種群規模m,變量個數n,交叉概率pc、變異概率pm,進行Powell搜索的概率pPowell和遺傳計算所允許的最大代數T。

      Step2隨機產生初始群體,并計算其適應值。首先第i個個體適應值取為fi’=fmax-fi,fi是第i個個體對應的目標函數值,fmax為當前種群成員的最大目標函數值,i=1,2,…,m。然后按Goldberg線性比例變換模型[2]式(2)進行拉伸。

      fi’=a×fi’+b(fi³0)(2)

      step3執行比例選擇算子進行選擇操作。

      step4按概率執行算術交叉算子進行交叉操作。即對于選擇的兩個母體和,算術交叉產生的兩個子代為和,是[0,1]上的隨機數,1,。

      step5按照概率執行非均勻變異算子[8]。若個體的元素被選擇變異,,則變異結果為,其中,

      (3)

      (4)

      返回區間[,]里的一個值,使靠近0的概率隨代數的增加而增加。這一性質使算子在初始階段均勻地搜索空間,而在后面階段非常局部化。是[,]之間的隨機數,為最大代數,為決定非均勻度的系統參數。

      step6對每個個體按照概率pPowell進行Powell搜索。若個體被選擇進行Powell搜索操作,則以作為初始點執行Powell方法得,若則把所得計算結果作為子代,否則,若取=;若取=,1。

      step7計算個體適應值,并執行最優個體保存策略。

      step8判斷是否終止計算條件,不滿足則轉向step3,滿足則輸出計算結果。

      作為求解無約束最優化問題的一種直接方法,Powell法的整個計算過程由若干輪迭代組成,在每一輪迭代中,先依次沿著已知的n個方向搜索,得一個最好點,然后沿本輪迭代的初始點與該最好點連線方向進行搜索,求得這一階段的最好點。再用最后的搜索方向取代前n個方向之一,開始下一階段的迭代。為了保持算法中n個搜索方向是線性無關的,保證算法的收斂性,對替換方向的規則進行改進,在混合法的計算步驟step6中采用文[9]中的改進Powell方法,其求解過程如下:

      (1)變量賦初值,n個線性無關的n個方向,,…,,和允許誤差ε>0,令k=1。

      (2)令,從出發,依次沿方向,,…,作一維搜索,得到點,,…,求指標m,使得-=max{-},令。若ε,則Powell方法計算結束,否則,執行(3)。

      (3)求使得=min,令==,若,則Powell方法計算結束,得點;否則,執行(4)。

      (4)若,令,否則令(),然后置,轉(2)。

      3算例

      T[-500,500]

      圖1函數f(x)特性示意圖

      函數f(x)有相當多的極小點,全局極小點是=-420.97,=1,2,…,,最優值為-837.97;次最優點為={(,,…,):=-420.97,,=302.52},=1,2,…,,次優值-719.53。變量個數n=2時函數f(x)特性如圖1示。程序編制和運行環境采用FortranPowerStation4.0,隨機數由內部隨機函數產生,在奔騰133微機上運行。

      采用改進的Powell方法計算100次,初值在區間[-500,500]內隨機產生,只有6次(即以概率0.06)搜索到全局最優,計算成功的概率極低。

      Holland建立的標準(或簡單)遺傳算法,其特點是二進制編碼、賭輪選擇方法、隨機配對、一點交叉、群體內允許有相同的個體存在。取種群規模m=30,交叉概率pc=0.95、變異概率pm=0.05,最大進化代數T=1000,每個變量用串長為L=16的二進制子串表示。二進制編碼比浮點編碼遺傳算法計算精度低,對于標準遺傳算法以目標函數小于-800為搜索成功,標準遺傳算法運行100次。當取最大進化代數為T=200時,40次(以概率0.40)搜索到全局最優,平均計算時間為0.51秒;當取T=500時,51次(以概率0.51)搜索到全局最優,平均計算時間為1.13秒。

      采用本文混合法計算,取m=30,pc=0.85、pm=0.2,T=100,進行Powell搜索的概率pPowell取不同值,混合法運行100次,計算結果見如表1。對于這個具有多極值的算例,多次計算表明pPowell=0.3時,混合法能以完全概率搜索到全局最優的準確值,但是此時混合法計算時間約為標準遺傳算法取T=500時計算時間的4/5。對應的浮點編碼遺傳算法,取m=30,pc=0.85、pm=0.2,T=100,運行100次,82次(以概率0.82)搜索到全局最優(如表1中PPowell=0所示),計算時間約為標準遺傳算法取T=500時計算時間的1/8,但是搜索到全局最優的概率卻遠遠高于標準遺傳算法。

      表1pPowell取不同值時混合法的計算結果

      PPowell

      0.0

      0.02

      0.05

      0.1

      0.2

      0.3

      求得最優解的次數

      82

      85

      89

      94

      98

      100

      求得最優解的概率

      0.82

      0.85

      0.89

      0.94

      0.98

      1.00

      平均計算時間/秒

      0.14

      0.20

      0.31

      0.47

      0.68

      0.87

      4結束語

      針對不可微函數的全局優化問題,本文提出一種把Powell方法與浮點編碼遺傳算法相結合的混合遺傳算法,該算法兼顧了遺傳算法全局優化方面的優勢和Powell方法局部搜索能力較強的特點,提高求得全局解的概率。計算結果表明混合法優于遺傳算法和Powell法,可以可靠地搜索到具有多個局部極值的函數優化問題的全局解。由于計算中只用到函數值信息,本文混合法不僅適用于不可微函數優化問題,也適合可微函數全局優化問題。

      參考文獻

      [1]周明,孫樹林.遺傳算法原理及應用[M].北京:國防工業出版社,1999.

      [2]GoldbergDE.Geneticalgorithmsinsearch,optimizationandmachinelearning[M].Reading,Ma:AddisonWesley,1989.

      [3]孟慶春,賈培發.關于Genetic算法的研究及應用現狀[J].清華大學出版社,1995,35(5):44-48.

      [4]戴曉暉,李敏強,寇紀松.遺傳算法理論研究綜述[J].控制與決策,2000,15(3):263-268.

      [5]LinW,Delgado-FriasJG.HybridNewton-Raphsongeneticalgorithmfortravelingsalesmanproblem[J].Cyberneticsandsystems,1995,26(5):387-412.

      [6]趙明旺.連續可微函數全局優化的混合遺傳算法[J].控制與決策,1997,12(5):589-592.

      [7]GoldbergDE.Real-CodeGeneticAlgorithm,VirtualAlphabetsandBlocking[J].ComplexSystems,1991,5:139-167.

      [8]MichalewiczZ.Amodifiedgeneticalgorithmforoptimalcontrolproblems[J].Computersmath.Application,1992,23(12):83-94.

      [9]陳寶林.最優化理論與算法[M].北京:清華大學出版社,1989.

      [10]俞紅梅.全過程系統能量綜合方法的研究[D].大連理工大學博士學位論文,1998.

      Hybridapproachforglobaloptimaofindifferentiablenonlinearfunction

      AbstractAhybridcomputationalintellectivealgorithmforlocatingtheglobaloptimaofindifferentiablenonlinearfunctionwasputforwardbysettingthePowellalgorithminreal-codegeneticalgorithm.Thehybridapproachimprovedthelocalsearchingabilityofthegeneticalgorithmandpromotedtheprobabilityfortheglobaloptimagreatly.Becauseonlytheobjectivevaluesareused,thehybridapproachisageneralizedgeneticalgorithmforglobaloptimaofdifferentiableandindifferentiablenonlinearfunctions.

      Keywordsglobaloptima;hybridapproach;geneticalgorithms;Powellalgorithm

      T-500:2:500(9)

      亚洲日产韩国一二三四区| 亚洲性日韩精品一区二区三区| 亚洲无人区午夜福利码高清完整版| 国产亚洲精品仙踪林在线播放| 亚洲AV电影天堂男人的天堂| 亚洲AV无码一区二区大桥未久| 亚洲爆乳无码专区www| 亚洲精品天堂在线观看| 日本亚洲色大成网站www久久 | 亚洲欧洲久久精品| 综合自拍亚洲综合图不卡区| 久久精品蜜芽亚洲国产AV| 久久亚洲私人国产精品vA| 亚洲毛片免费视频| 亚洲精品视频在线观看视频| 亚洲日本香蕉视频观看视频| 亚洲一卡2卡3卡4卡国产网站 | 亚洲精品国产成人中文| 亚洲永久中文字幕在线| avtt天堂网手机版亚洲| 伊人久久五月丁香综合中文亚洲| 亚洲欧洲精品成人久久曰| 妇女自拍偷自拍亚洲精品| 亚洲女同成人AⅤ人片在线观看| 久久久久久久亚洲精品| 亚洲人成色7777在线观看| 亚洲AV无码一区二区乱子伦| 亚洲天堂视频在线观看| 亚洲综合色一区二区三区小说| 亚洲天堂一区二区三区四区| 亚洲人精品亚洲人成在线| 亚洲成在人线aⅴ免费毛片 | 女bbbbxxxx另类亚洲| 2048亚洲精品国产| 久久亚洲精品视频| 亚洲精品91在线| 亚洲日韩精品A∨片无码加勒比| 无码欧精品亚洲日韩一区夜夜嗨 | 国产亚洲3p无码一区二区| 亚洲视频中文字幕| 亚洲中文无码线在线观看|