基于遺傳算法和最速下降法的函數(shù)優(yōu)化混合數(shù)值算法_百度文庫

1、基于遺傳算法和最速下降法的函數(shù)優(yōu)化混合數(shù)值算法趙明旺(武漢冶金科技大學自動化系, 430081 摘要在遺傳算法中嵌入一個最速下降算子, 并定義適當?shù)倪m應度函數(shù)和子代個體的選擇算子, 從而可結合遺傳算法和最速下降法兩者的長處, 得到既有較快收斂性, 又能以較大概率得到全局極值的新的用于連續(xù)函數(shù)全局優(yōu)化的混合數(shù)值算法。數(shù)值計算結果表明了本文方法顯著優(yōu)于求解函數(shù)優(yōu)化的遺傳算法和最速下降法。關鍵詞遺傳算法最速下降法函數(shù)優(yōu)化適應度A H yb rid N um erical A lgo rithm fo r Functi onOp ti m izati on Based on Genetic A lgo

2、 rithmand Steepest D ecen t A lgo rithmZhao M ingw ang(D ep t . of A u tom ati on , W uhan Yejin U n iversity of Science &T echno logy , 430081Abstract In th is paper , th rough a steepest decen t operato r is em bedded in to the genet 2ic algo rithm and a p roper fitness functi on and a selecting o

3、perato r fo r son generati on aredefined , a hyb rid algo rithm fo r global op ti m izati on of con tinuou s functi on , com b ined theadvances of bo th of genetic algo rithm and steepest decen t algo rithm , is go t w ith fastconvergence and great p robab ility fo r global op ti m izati on . T he n

4、um erical compu ting re 2su lts show n that the m ethod is distinctly superi o r to the genetic algo rithm and steepestdecen t algo rithm .Keywords genetic algo rithm ; steepest decen t algo rithm ; functi on op ti m izati on ; fit 2ness1引言對連續(xù)可微函數(shù)的優(yōu)化問題, 傳統(tǒng)數(shù)值優(yōu)化方法(如最速下降法、N ew ton 法和共軛梯度法等 有相對較快的收斂速度,

5、計算精度高, 在實際函數(shù)優(yōu)化問題求解中得到廣泛應用6。但傳統(tǒng)數(shù)值優(yōu)化方法求得的是局部最優(yōu)解。對全局優(yōu)化問題, 目前存在確定性和非確定性兩類方法。前者方法以B rian in 的下降軌線法1、L evy 的隧道法2和R 1Ge 的填充函數(shù)法3為代表。該類方法雖然有收斂快, 較高計算效率, 但算法復雜, 求得全局極值的概率不大。非確定性方法以M on te 2Garlo 隨機試驗法, H artm an 的多始點方法4, So lis 和W ets 的結合梯度信息的搜索方法5, 模擬退火方法6等為代表。該類方法對目標函數(shù)要求低、容易實現(xiàn)、穩(wěn)定性好, 但收斂較慢、效率低、求得全局極值的概率較低。近年

6、來, 模擬生物進化中“物競天擇”原則的計算智能(compu tati onal in telligen t 方法遺傳算法吸引了眾多科學領域中的研究人員, 并在函數(shù)優(yōu)化、模式識別、圖像處理、人工智能得到廣泛應用711。在不可微函數(shù)甚至不連續(xù)函數(shù)的函數(shù)優(yōu)化問題中, 遺傳算法以其能以較大概率求得全局最優(yōu)解、計算時間相對1997年7月系統(tǒng)工程理論與實踐第7期本文于1996年1月23日收到本文工作得到武漢市科委“晨光計劃”和冶金工業(yè)部理論研究基金資助較少、具有較強魯棒性等特點得到廣泛重視。但對于可微連續(xù)函數(shù)的優(yōu)化問題, 遺傳算法由于受到收斂性相對較慢、編碼長度對精度影響大、求解全局最優(yōu)解需群體(popu

7、 lati on 規(guī)模相對大等因素的影響, 與運籌學中的常用數(shù)值優(yōu)化方法相比, 并不具有優(yōu)勢。本文利用遺傳算法中雜交(cro ssover 算子、變異(m u tati on 算子和選擇算子在全變量空間, 以較大概率搜索全局極值的特點, 以及函數(shù)數(shù)值優(yōu)化中最速下降法收斂快、計算數(shù)值精度高的特點, 給出了一個適用于函數(shù)數(shù)值優(yōu)化的混合優(yōu)化算法。該混合算法具有雜交算子、變異算子和最速下降算子三種基本運算方式, 并定義了適合于連續(xù)函數(shù)全局優(yōu)化問題的用于子代群體的適應度函數(shù)和選擇算子。數(shù)值計算結果表明了本文方法既有較快的收斂性, 又能以較大概率求得全局最優(yōu)解, 顯著優(yōu)于求解函數(shù)優(yōu)化的遺傳算法和最速下降法

8、。2問題描述考慮如下有限空間的連續(xù)可微函數(shù)的全局優(yōu)化問題m in a i x b ii =1, n f (x (1其中a i 和b i 為優(yōu)化問題中變量x i 的上下限, n 為變量向量x 的維數(shù)。對(1 式所示的有限空間連續(xù)可微函數(shù)的全局優(yōu)化問題, 下面先引出目前的數(shù)值優(yōu)化方法和遺傳算法。211最速下降法最速下降法是數(shù)值優(yōu)化方法中最早的算法。該方法直觀、簡單、不需要求解函數(shù)的二階導數(shù)矩陣(H es 2sian 矩陣 。許多更有效的數(shù)值優(yōu)化方法都是在最速下降法的啟發(fā)下獲得的。最速下降法求解式(1 所示的連續(xù)函數(shù)優(yōu)化問題的計算過程如下12:最速下降法選定初始迭代點R epeat作線性搜索x k

9、+1=linear 2search (x k , - f (x k 計算f (x k +1 , f (x k +1U n til (結束迭代邏輯條件滿足最速下降法雖然實現(xiàn)簡單, 有一階收斂速度, 但其求得的是局部最優(yōu)解, 而不能保證是全局最優(yōu)解。對于有限空間的連續(xù)可微函數(shù)的全局優(yōu)化問題, 目前還沒有簡便且有效的求解方法, 實際應用中只能通過在多個初始迭代點上多次使用傳統(tǒng)數(shù)值優(yōu)化方法來盡可能地求取全局最優(yōu)解, 但該種處理方法求得全局極值的概率不高、可靠性低。建立以盡大可能(概率 求解連續(xù)函數(shù)的全局最優(yōu)解的算法仍是一個重要的問題。212遺傳算法如引言中所述, 遺傳算法對于有限空間的連續(xù)可微函數(shù)的全

10、局優(yōu)化問題, 與數(shù)值優(yōu)化方法相比并不具有優(yōu)勢。即便如此, 遺傳算法的雜交算子、變異算子和子代群體選擇算子在求取全局最優(yōu)解中的效能對有限空間的連續(xù)可微函數(shù)的全局優(yōu)化問題還是具有指導作用的。遺傳算法求解式(1 所示的連續(xù)函數(shù)優(yōu)化問題的計算過程如下:8,10:遺傳算法隨機產生初始父代群體并計算其適應度對初始父代群體的每個個體進行編碼R epeat 選擇群體中兩個(或多個 個體以概率P c 進行雜交運算選擇群體中個體以概率P m 進行變異運算06系統(tǒng)工程理論與實踐1997年7月對每個個體進行解碼并計算其適應度選擇子代群體(適者繁殖, 不適者被淘汰U n til (結束迭代邏輯條件滿足遺傳算法應用于式(

11、1 所示的連續(xù)可微函數(shù)的全局優(yōu)化問題的困難之處在于:1 雜交運算概率P c 和變異運算概率P m 的選擇。2 群體規(guī)模的確定。3 編碼方法和編碼長度。4 如何控制群體向某個或某幾個個體集中的速度。若該速度快, 則求得全局極值的概率將變小; 若過慢, 則遺傳算法將退化為M on te 2Carlo 完全隨機試驗算法。5 適應度函數(shù)的確定。3基于遺傳算法和最速下降法的函數(shù)優(yōu)化混合數(shù)值算法針對上述最速下降法和遺傳算法在連續(xù)可微函數(shù)的全局優(yōu)化上的不足, 綜合兩種方法各自的優(yōu)勢, 本文提出如下混合算法。混合算法隨機產生初始父代群體并計算其適應度R epeat選擇群體中兩個個體以概率P c 進行編碼、雜交

12、、解碼運算, 將父代和子代都加入新的子代群體對新的子代群體中每個個體以概率P m 進行編碼、變異、解碼運算, 將父代和子代都加入新的子代群體對新的子代群體中每個個體以概率P s 計算f (x k , f (x k , 并進行線性搜索x k +1=linear 2search(x k , - f (x k , 將子代取代父代加入新的子代群體對每個個體計算適應度以既定的群體規(guī)模, 選擇下一次繁殖的子代群體(適者繁值, 不適者被淘汰U n til (結束迭代邏輯條件滿足對上述混合算法, 說明如下:311適應度函數(shù)定義由于待優(yōu)化的函數(shù)f (x 的值可正可負, 而適應度函數(shù)需恒為正, 再者進行雜交運算和

13、子代選擇時所需的概率與適應度是成正比的。因此, 適應度函數(shù)的定義將對整個遺傳算法和本文的混合算法有全局性的影響, 是算法成功求得全局極值的關鍵之一。本文的上述混合算法的適應度函數(shù)g (x 定義為g (x =f m ax -f (x +k 1(f m ax -f m in (2其中f m ax 和f m in 分別為當前群體中的最大函數(shù)值和最小函數(shù)值; k 1為控制當前群體中最大適應度與最小適應度之比的參數(shù)。由上式可知, 在每次繁殖的群體中最大適應度與最小適應度之比為(1+k 1 k 1。若k 1過大, 該比值趨近于1, 即當前群體中最大函數(shù)值的個體和最小函數(shù)值的個體有較接近的適應度和選擇概率,

14、 則雜交算子和變異算子的作用將退化至接近于完全的隨機搜索。若k 1過小, 該比值趨近于, 將使得當前群體中函數(shù)值較大的個體的適應度和選擇概率過小, 失去繁殖的機會, 從而導致群體快速向某個個體或某幾個個體集中, 使得求得全局極值的概率下降。一般情況下, k 1的取值在0. 010. 1之間較適宜, 相應的同代群體中個體間的最大適應度和最小適應度之比為11101之間。由于算法中每代的f m ax 和f m in 隨群體不同而變化, 使得本文的混合算法在確定適應度和選擇概率上具有自適應性和魯棒性。312群體的數(shù)據(jù)結構和編碼方法遺傳算法的主要數(shù)據(jù)結構是數(shù)字位串, 一般常用的是二進制。當遺傳算法應用于

15、連續(xù)函數(shù)的優(yōu)化計算16第7期基于遺傳算法和最速下降法的函數(shù)優(yōu)化混合數(shù)值算法時, 位串長度和編碼方法對計算精度和群體中個體之間的距離具有決定性影響, 并直接影響全局極值的求解。本文的混合算法的數(shù)據(jù)結構采用混合式數(shù)據(jù)結構, 在群體中每個個體采用實型數(shù)的數(shù)據(jù)結構, 只有在個體被確定進行雜交運算和變異運算時才進行編碼, 運算結束后產生子代的要進行解碼才能入新的子代群體。采用混合數(shù)據(jù)結構的優(yōu)點是可以避免編碼的有限字長對精度的影響, 充分發(fā)揮最速下降算子精度高以及能局部細致地搜索極值的特性。本文的混合方法在雜交運算和變異運算中個體的編碼方法采用遺傳算法中常用的二進制位串編碼方法。個體的各變量x i (i

16、=1, 2, , n 的二進制位串以順序排列, 其中變量x i 的二進制位串x i 的編碼算法為x i =int b i -a i (2N -1 (3其中N 為二進制位串的長度, 函數(shù)in t (為取整函數(shù)。313線性搜索算子為了加速遺傳算法在連續(xù)可微函數(shù)全局優(yōu)化問題上的收斂性, 發(fā)揮傳統(tǒng)數(shù)值優(yōu)化算法在計算速度與計算精度上的優(yōu)勢, 本文的混合算法中嵌入了一個最速下降算子。該最速下降算子主要進行的是傳統(tǒng)最速下降法中的線性搜索運算。在每次繁殖中產生的新的子代, 都要以概率P s 判斷是否需要進行線性搜索運算。由于最速下降法的線性搜索運算是一種能保證迭代產生的點序列是函數(shù)單調下降的良好的局部極值數(shù)值

17、優(yōu)化算法, 因此經(jīng)最速下降算子的線性搜索運算產生的新的個體繼承了其父代的優(yōu)良品質, 故可將子代取代父代進入代候選群體以待選擇新的子代, 而不需要父代和子代都進入子代候選群體。本文的最速下降算子所進行的具體運算為:最速下降算子過程R epeat對群體中第i 個體產生0, 1間隨機數(shù)。若該隨機數(shù)大于既定最速下降算子概率P s 則進行下述運算計算f (x k , f (x k 用黃金分割法進行線性搜索x k +1=linear 2search (x k , - f (x k 將產生的子代取代父代加入新的子代群體U n til (搜索完整個群體可以這么說, 本文混合算法中的遺傳算子雜交算子、變異算子和

18、選擇算子的作用是宏觀搜索, 處理的是大范圍搜索問題, 而最速下降算子中的線性搜索過程的作用是極值局部搜索, 即微觀搜索, 處理的是小范圍搜索問題和搜索加速問題。最速下降算子概率P s 的大小應能保證在繁殖(迭代 過程中, 對群體中的每個個體都有機會得到一定次數(shù)的進行最速下降算子的線性搜索運算。因此, 確定最速下降算子概率P s 的大小需考慮的因素為:1 所優(yōu)化的函數(shù)的線性搜索迭代的收斂性。若其線性搜索迭代收斂較快, 則相應的P s 可取小一些。否則, 則取大一些。2 預定的繁殖代數(shù)(迭代次數(shù) ; 若預定的繁殖代數(shù)較大, 則相應的P s 可取小一些。否則, 則取大一些。314選擇算子、選擇概率和

19、控制個體間的距離遺傳算法與傳統(tǒng)優(yōu)化算法比較, 其之所以其以較大概率求得全局極值, 是因為其算法思想中體現(xiàn)了兩個基本原則:一為適者生存, 二為選擇的相對隨機性。而選擇算子、選擇概率和控制個體間的距離是體現(xiàn)這些原則的最重要的手段。本文的混合算法對選擇算子、選擇概率和控制個體間的距離等的主要考慮是:1 雜交運算和變異運算后, 子代和父代都同時都進入子代候選群體, 而由于最速下降運算的子代較好地繼承了其父代的特性故只有子代進入候選群體。2 在選擇下次繁殖的子代群體時, 每次以候選群體中個體的概率隨機地選擇兩個體, 其中適應度大26系統(tǒng)工程理論與實踐1997年7月的個體進入子代群體, 直至產生完所有繁殖

20、所需的下代群體為止。這樣既可保證有相對和適直生存, 又使選擇具有一定的隨機性。3 為避免在繁殖中群體向某個個體或有限幾個個體快速集中, 降低求得全局極值的概率, 在選擇算子運算中還必須計算群體中各個體間的距離(常用的有2-范數(shù), -范數(shù), H amm ing 距離等 , 相鄰較近的兩個個體必須剔出其一。由于本文的混合算法中的最速下降算子能局部地、細致地進行優(yōu)化搜索, 故在控制群體中個體間的距離時, 可考慮讓群體中個體之間的相對距離較大(一般相對誤差可在10以上 , 使能在更大的空間范圍內, 以較大概率搜索全局極值。4數(shù)值計算和結束語本節(jié)考慮如下連續(xù)可微函數(shù)的有限區(qū)間的全局極值問題f (x =x

21、 21+2x 22-10sin (2x 1 sin (x 3 +0. 5co s (x 1+2x 2+x 21x 23-5sin (2x 1-x 2+3x 3 -10x i 10i =1, 2, 3(4 由上式可知, 該函數(shù)f (x 在其變量空間中存在多極值點, 傳統(tǒng)數(shù)值優(yōu)化方法不易求得全局極值。該函數(shù)的全局極值發(fā)生在(-0. 676256, -0. 381582, -1. 282868 , 其全局極值為-12. 765473。本文利用混合算法進行了大量計算機數(shù)值模擬計算, 計算過程和結果如下所述:1 先隨機產生-10, 10間的900組3維隨機向量, 每30組作為初始繁殖群體, 共進行30次

22、計算。計算結果如表1所示。表1計算結果情況1情況2情況3情況4情況5情況6參數(shù)(P c , P m , P s 0. 9, 0. 1, 0. 50. 9, 0. 1, 0. 10. 9, 0. 1, 0. 010. 9, 0. 1, 0. 00. 0, 1. 0, 0. 00. 0, 0. 0, 1. 0計算次數(shù)303030303030繁殖代數(shù)500極值的次數(shù)3030221011搜索到全局極值的概率1. 01. 00. 7330. 0330. 00. 367說明:1 情況4中P s =0. 0, 則混合算法退化為一般的遺傳算法。2 情況5中P c =P s =0. 0, P m =1. 0,

23、則混合算法則相當于完全隨機的M onte 2Carlo 方法。3 由于情況4和情況5收斂較慢, 故數(shù)值模擬時, 每次繁殖1500代。4 情況6中P c =P m =0. 0, P s =1. 0, 則混合算法則相當于在30個初始迭代點同時進行搜索的最速下降算法。2 同1 的-10, 10間的900組3維隨機向量, 對不同的線性搜索概率P s 進行計算, 觀察P s 對求得全局極值的概率和迭代收斂性的影響。表2在P c =0. 9, P m =0. 1時, 在30次計算中不同的P s 得到的全局極值的計算結果, 圖1是表2數(shù)據(jù)中求得全局次數(shù)與P s 關系曲線。圖2是在同一次計算中不同的P s 的

24、迭代計算收斂過程。由上述數(shù)值計算結果可知, 本文的基于遺傳算法和最速下降法的函數(shù)優(yōu)化混合數(shù)值算法在連續(xù)可微函數(shù)的全局優(yōu)化問題運用中, 其求得全局極值的概率顯著地大于M on te 2Carlo 完全隨機實驗法、最速下降法和遺傳算法, 而且具有較好的收斂性, 是一種可行的求解連續(xù)可微函數(shù)全局優(yōu)化問題的數(shù)值算法。36第7期基于遺傳算法和最速下降法的函數(shù)優(yōu)化混合數(shù)值算法64 系統(tǒng)工程理論與實踐 表 2計算結果 (P c = 0. 9, P m = 0. 1 參數(shù) P s 計算次數(shù) 繁殖代數(shù) 搜索到全局 極值的次數(shù) 搜索到全局 極值的概率 0. 0 30 1500 1 0. 005 0. 01 0.

25、015 0. 02 0. 035 0. 05 30 500 15 30 500 22 30 500 23 30 500 25 30 500 29 30 500 30 0. 08 30 500 30 0. 1 30 500 30 0. 2 30 500 30 1997 年 7 月 0. 5 30 500 30 0. 033 0. 50 0. 733 0. 767 0. 833 0. 967 1. 0 1. 0 1. 0 1. 0 1. 0 圖 1求得全局次數(shù)與 P s 的關系曲線 參考文獻 圖 2不同的 P s 的迭代收斂過程 1 B ra in F H. So lu tion of non l

26、inea r DC netw o rk p rob lem via d ifferen tia l equa tion s . In t. IEEE Conf. on sys2 tem s netw o rk s & com p u ters, O ax tep ex,M ex ico, 1971. 2 L evy A V. T he tunelling a lgo rithm fo r the g loba l m in i m iza tion of function. T he D undee Conf. on N u 2 m erica l ana lysis, D undee, Sc

27、o tland, 1971. 3 Ge. R A filled function m ethod fo r find ing a g loba l m in i . T he m izer of a function of severa l va riab les D undee B ienn ia l Conf. on N um erica l ana lysis, D undee, Sco tland, 1983. 4 H a rtnan J K. Som e exp eri m en t in g loba l op ti m iza tion. N ava l Po stg radua te Schoo l, M on terey, Ca lifo rn ia N p sssHH 73041A , 197