L HS抽樣遺傳算法

任 哲,陳明華

（1.合肥學院數(shù)理系,安徽合肥230022;2.皖西學院數(shù)理系,安徽六安 237012）

L HS抽樣遺傳算法

任 哲1,陳明華2

（1.合肥學院數(shù)理系,安徽合肥230022;2.皖西學院數(shù)理系,安徽六安 237012）

文獻[1]研究了遺傳算法的運行機理及特點,即遺傳算法是一個具有定向制導(dǎo)的隨機搜索技術(shù),其定向制導(dǎo)的原則是:導(dǎo)向以高適應(yīng)度模式為祖先的“家族”方向。以此結(jié)論為基礎(chǔ),利用拉丁超立方體抽樣（LHS）的理論和方法,對遺傳算法中的交叉操作進行了重新設(shè)計,給出了一個新的GA算法,稱之為LHS遺傳算法。將L HS遺傳算法應(yīng)用于求解優(yōu)化問題,并與簡單遺傳算法和文獻[2]中的佳點集遺傳算法進行比較,通過模擬比較,可以看出新的算法不但提高了算法的收斂速度和精度,而且避免了其它方法常有的早期收斂的現(xiàn)象。

遺傳算法（GA）;拉丁超立方體抽樣（LHS）;LHS遺傳算法（LHSGA）

1 引言

文獻[1]指出了GA算法的本質(zhì)是:遺傳算法是一個具有定向制導(dǎo)的隨機搜索技術(shù),其定向制導(dǎo)的原則是:導(dǎo)向以高適應(yīng)度模式為祖先的“家族”方向。文獻[2]根據(jù)此機理,利用數(shù)論中的佳點集理論和方法[3]設(shè)計了一個新的交叉算法,提高了GA算法的效率。簡單介紹文獻[2]中給出的佳點集遺傳算法。

1.1 佳點集GA算法

設(shè)在傳統(tǒng)的GA算法基礎(chǔ)上,在進行過復(fù)制后,對池中的元素按賭輪法選擇兩個元素A1,A2進行佳點集交叉操作。

不妨設(shè)A1,A2的前t個分量不同,后l-t個分量相同,令模式

由A1,A2進行交叉（不管是單點交叉或是多點交叉）其子孫必屬于H,于是要在“高適應(yīng)度模式為祖先的家族方向”上搜索出更好的樣本,就是要在H中搜索出更好的樣本。佳點集GA算法就是在H上利用佳點集方法找出好樣本來,其方法是[2]:

將H的前t個分量看成一個t維的立方體（仍記為H）然后在H上求佳點集。

在t維空間中取佳點的方法如下:

在t維空間H中作含n個點的佳點集（當H是二進制立方體時）

其中rk=2cos（2πk/p）,1≤k≤t,p是滿足p≥2t+3的最小素數(shù),或rk=ek,1≤k≤t,{a}表示a的小數(shù)部分。令交叉后產(chǎn)生的n個后代中第k個染色體

〈a〉表示,若a的小數(shù)部分小于0.5,則〈a〉=0;否則〈a〉=1。

這樣在其“家族”中,產(chǎn)生n個后代,取其中適應(yīng)度值最大者（或最大的幾個）,作為交叉后的后代。上述交叉操作,稱為佳點集交叉操作。

1.2 拉丁超立方體抽樣（L HS）

設(shè)在一個d—維單位立方體Cd=[0,1]d中要選n個點,先將每一維坐標區(qū)間[0,1]都分成n等分,并用標號i記小區(qū)間第j維坐標的n個標號（1,2,…,n）的一個隨機排列。又設(shè)這d個隨機排列相互獨立,則得到一個n×d階的隨機矩陣π=（πij）,然后令

為一個Latin Hypercube樣本。我們稱這樣的抽樣方法為L HS。所得到的樣本稱為L HS的樣本。

在某種意義下,L HS是一種分層抽樣,就某種均勻性來說要優(yōu)于i.i.d.抽樣（常指Monte Carlo抽樣）。而且文獻[5]、[6]都說明L HS具有良好的散布均勻性和代表性,加之它是隨機的,搜索能力更強,故比佳點集有更好的表現(xiàn)。

2 L HS遺傳算法

2.1 L HS交叉操作

設(shè)在傳統(tǒng)的GA算法基礎(chǔ)上,在進行過復(fù)制后,對池中的元素按賭輪法選擇兩個元素A1,A2進行L HS抽樣交叉操作。

不妨設(shè)A1,A2的前t個分量不同,后l-t個分量相同,令模式

由A1,A2進行交叉（不管是單點交叉或是多點交叉）其子孫必屬于H,于是要在“高適應(yīng)度模式為祖先的家族方向”上搜索出更好的樣本,就是要在H中搜索出更好的樣本,L HS遺傳算法就是要在H上利用L HS方法來找出好樣本,其具體方法是[4]:

將H的前t個分量看成一個t維的立方體（仍記為H）然后在H上進行L HS抽樣或?qū)的每d個分量分成一組（不妨設(shè)共分成s組）,每組表示一個實數(shù)。于是s個組就表示s個實數(shù)。這樣就將H變換成一個s維的實空間,可將其歸一化變換成一個s維的單位立方體。然后在其上進行L HS抽樣。

如（1,1,0,0,1,0,1,0,1,1,0,1）是12維二進制單位立方體中的一點,我們可以將它化成三維的實值空間的點（每4個分量合成一個實數(shù)）（1100,1010,1101）=（12,10,13）;再將它歸一化,得點（12/16,10/16,13/16）=（3/4,5/8,13/16）,即為實3維單位立方體中的一點。

在t維空間中進行L HS的具體做法如下:

〈a〉表示:若a的小數(shù)部分小于0.5,則〈a〉=0;否則〈a〉=1。

這樣在其“家族”中,產(chǎn)生n個后代,取其中適應(yīng)度值最大者（或最大的幾個）,作為交叉后的后代。

上述交叉操作,稱為L HS交叉操作。

變異:取染色體A,隨機整數(shù)i,A=（a1,a2,…, al）變異成新的染色體B,

2.2 L HS遺傳算法

給定交叉概率pc和變異概率pm,L HS遺傳算法如下:

（1）每次進行遺傳操作,以概率fi/∑fi復(fù)制A i,其中fi是A i的適應(yīng)度值。

（2）以賭輪法隨機取兩個染色體,以概率pc對其進行L HS交叉操作（產(chǎn)生n個后代,n為待定參數(shù)）。

（3）以概率pm進行變異遺傳操作。

（4）把經(jīng)過遺傳操作后得到的染色體都放到染色體池中,對新得到的染色體,計算其適應(yīng)度值。若假定染色體的容量一定,當染色體的個體超過容量時,就將適應(yīng)度小的染色體從池中刪去（或按a%進行刪除）。

（5）進行上述的遺傳算法至第T代后（T是預(yù)先給定的常數(shù)）,在第T代的染色體中取適應(yīng)度最大的染色體,即為所求的染色體。

3 L HS遺傳算法的測試比較和實驗分析

在P4 3.0G PC機器上,在Matlab7.0計算平臺上,利用遺傳算法工具箱中“簡單遺傳算法”、文獻[2]中的“佳點集遺傳算法”和這里的“L HS遺傳算法”對文獻[2]中提供的5個函數(shù)進行了計算比較;計算中遺傳算法參數(shù)為:種群規(guī)模為100,最大迭代代數(shù)為150,交叉概率為0.85,變異概率取0.05,每個執(zhí)行100次。

實驗結(jié)果:

表中:GA:簡單遺傳算法;GGA:佳點集遺傳算法;L HSGA:拉丁超立方抽樣遺傳算法。

從上面結(jié)果可見,不管在求解精度上,還是在求解速度上,基于L HS的遺傳算法比傳統(tǒng)簡單遺傳算法和佳點集遺傳算法的性能都要好得多,并能成功地避免“早熟”現(xiàn)象。

4 結(jié)論

本文改進了遺傳算法中的交叉操作,我們知道遺傳算法是一個具有定向制導(dǎo)的隨機搜索技術(shù),其定向制導(dǎo)的原則是:導(dǎo)向以高適應(yīng)度模式為祖先的“家族”方向,所以任何一種交叉操作都無非是在以其父代為“祖先”的“家族”中尋找一個適應(yīng)度值高的后代。現(xiàn)有的交叉算法:如單點交叉、多點交叉、樹交叉[8]等,都只能保證求到的后代落在上述的家族中,但其搜索適應(yīng)度值高的后代的能力不夠強;佳點集法利用求得的子集的均勻散布性,使它們能較好代表其“家族”性能的普遍性,所以佳點集遺傳算法構(gòu)造的交叉操作提高了搜索適應(yīng)度值高的后代的能力,但佳點集布點有方向性,并且當n取定后是確定的,不帶隨機性,更非統(tǒng)計意義下的抽樣,這導(dǎo)致了其整體搜索能力仍不夠強。L HS就克服了此不足,L HS所得的樣本具有很好的均勻散布性,并且每次取得的樣本集是隨機均勻散布的,這樣可以取到所有的格子點。所以L HS[4]遺傳算法具有極強的整體搜索能力。實驗證明不管在求解精度上還是在求解速度上,L HS遺傳算法不僅優(yōu)于GA算法,也優(yōu)于佳點集遺傳算法,并能較好地避免早熟現(xiàn)象,收斂到最優(yōu)解。

[1]張鈴,張鈸.遺傳算法機理的研究[J].軟件學報,2000,11 （7）:945-952.

[2]張鈴,張鈸.佳點集遺傳算法[J].計算機學報,2001,24 （9）:917-922.

[3]華羅庚,王元.數(shù)論在近似分析中的應(yīng)用[M].北京:科學出版社,1978.

[4]Mekay.M.D.,Beckman.R.J.and Conover.W.J.A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Out Put from A Computer Code[J].Technometrics,1979,21:239-245.

[5]Stein.M.Large Sample Properties of Simulations Using Latin Hypercube Sampling[J].Technometrics,1987,29: 143-151.

[6]Owen,A.B.A Central Limit Theorem for Latin Hhypercube Sampling[J].J.R.Statist.Soc.Ser.B,1992,54:541 -551.

[7]吳少巖,張青富,陳火旺.基于家族優(yōu)生學的進化算法[J].軟件學報,1997,8（2）:137-144.

[8]陳國良,王煦法,莊鎮(zhèn)泉,等.遺傳算法及其應(yīng)用[M].北京:人民郵電出版社,1996.

Genetic Algorithm Based on Latin Hypercube Sampling

REN Zhe1,CHEN Ming-hua2

（1.Dept.of Mathematics and Physics,Hefei University,Hefei230022,China;2.Dept.of Mathematics and Physics,West Anhui University,L u’an237012,China）

By analyzing the genetic algorithm（GA）based on it’s idea density model,the essence and characteristics of GA are given. It is shown that the GA is a guided random search and the guiding direction always aims at the family whose ancestors have schemata with high fitness.Based on the results,the crossover operation in GA is redesigned by using the principle of Latin Hypercube Sampling.Then a new GA called Genetic Algorithm based on Latin Hypercube Sampling is presented.The new GA is applied to optimization function.Compared to Simple Genetic Algorithm（SGA）and Good Point Genetic Algorithm（GGA）for solving this problem,the simulation results show that the new GA has superiority in speed,accuracy and overcoming premature.

genetic algorithm（GA）;Latin hypercube sampling（LHS）;genetic algorithm based on Latin hypercube sampling（LHSGA）

TP301

A

1009-9735（2010）02-0018-04

2010-03-31

任哲（1957-）,女,安徽淮南人,合肥學院數(shù)理系教授,研究方向:參數(shù)統(tǒng)計和大樣本理論、人工智能、遺傳算法。

陳明華（1954-）,男,浙江鄞縣人,皖西學院數(shù)理系教授,研究方向:參數(shù)統(tǒng)計和大樣本理論、人工智能、遺傳算法。