一種遺傳算法適應(yīng)度函數(shù)的改進(jìn)方法

1、第23卷第2期計(jì)算機(jī)應(yīng)用與軟件Vol 123, No . 22006年2月Computer App licati ons and Soft w are Feb . 2006收稿日期:2004-02-05。張思才, 碩士, 主研領(lǐng)域:結(jié)構(gòu)設(shè)計(jì)及優(yōu)化算法研究。一種遺傳算法適應(yīng)度函數(shù)的改進(jìn)方法張思才張方曉(中國(guó)工程物理研究院結(jié)構(gòu)力學(xué)研究所四川綿陽(yáng)621900摘要針對(duì)簡(jiǎn)單遺傳算法中線性適應(yīng)度函數(shù)隨進(jìn)化過(guò)程恒定不變的缺點(diǎn), 數(shù)。以典型的遺傳算法測(cè)試函數(shù)為算例, 分別以Goldberg 1。計(jì)算結(jié)果關(guān)鍵詞遺傳算法適應(yīng)度函數(shù)優(yōu)化計(jì)算A MOD F FUNCT I O N O F GENET I C AL G

2、O R I TH M SZhang Sicai Zhang Fangxiao(Institute of S tructural M echanics, China A cade m y of Engineering physics, M ianyang S ichuan 621900, China Abstract A i m ing at the shortcom ing of the si m p le genetic algorith m (G A with the linear fitness functi on unfit f or evoluti onary p r ocess,

3、a modified genetic algorith m with the nonlinear fitness functi on, which can adap t t o evoluti onary p r ocess of algorith m is p resented in this disserta 2ti on . G A with linear scaling method p r oposed by Goldberg1and modified G A in this paper, res pectively, calculates the genetic algorith

4、m s tes 2ting functi ons . The comparis on bet w een the results obtained by above 2menti oned algorith m s indicates that the nonlinear adap tive fitness func 2ti on is effective f or i m p r oving the si m p le genetic algorith m s perf or mance . Keywords Genetic algorith m Fitness functi on Op t

5、i m izati on computati on0引言遺傳算法(genetic alg orith m s, 簡(jiǎn)稱G A 是模擬生物進(jìn)化過(guò)程中, “適者生存, 優(yōu)勝劣汰”規(guī)律而無(wú)需函數(shù)梯度信息的自適應(yīng)全局搜索算法1。遺傳算法倍受各行設(shè)計(jì)者青睞之原因在于:這類隨機(jī)算法能夠同時(shí)處理N 個(gè)設(shè)計(jì)變量, 有利于實(shí)現(xiàn)并行操作, 提高多變量?jī)?yōu)化問(wèn)題的計(jì)算效率; 能夠跳出局部最優(yōu)解而做到全局搜索。遺傳算法依靠選擇操作模擬自然界中的“適者生存, 優(yōu)勝劣汰”這一過(guò)程, 即選擇操作來(lái)引導(dǎo)算法的搜索方向, 而選擇操作是以個(gè)體的適應(yīng)度作為確定性指標(biāo), 從當(dāng)前群體中選擇適應(yīng)值高的個(gè)體以生成交配池。如此必然造成群體中基因

6、信息的丟失, 使群體中個(gè)體平均相似度增加, 最終造成遺傳算法早熟。文獻(xiàn)2研究表明優(yōu)化參數(shù)配置不當(dāng), 遺傳算法可能會(huì)出現(xiàn)不收斂的情況。為使遺傳算法運(yùn)用于工程結(jié)構(gòu)優(yōu)化領(lǐng)域, 諸多學(xué)者對(duì)遺傳算法做出不少改進(jìn)35。大多數(shù)改進(jìn)思想都是對(duì)遺傳算法中的適應(yīng)度函數(shù)、交叉概率和變異概率等方面進(jìn)行改進(jìn), 尤其以文獻(xiàn)5中提出的自適應(yīng)遺傳算法為代表, 其思想就是建立在個(gè)體適應(yīng)度基礎(chǔ)之上。此外, 遺傳算法本身是以激勵(lì)機(jī)制適應(yīng)度函數(shù)為基礎(chǔ), 故對(duì)適應(yīng)度函數(shù)的改進(jìn)應(yīng)該是最基本的、最有效的改進(jìn)方式。Goldberg 在簡(jiǎn)單遺傳算法的基礎(chǔ)上提出線性拉伸方法以擴(kuò)大個(gè)體之間的差異, 但是涉及到常數(shù)的選取問(wèn)題。本文將對(duì)常數(shù)的選取進(jìn)行

7、討論, 為避免人為因素對(duì)算法的影響, 本文提出一種非線性的動(dòng)態(tài)適應(yīng)度函數(shù), 以典型的遺傳算法測(cè)試函數(shù)為考題驗(yàn)證本文提出的適應(yīng)度函數(shù)的有效性與可行性。1遺傳算法遺傳算法尋優(yōu)的本質(zhì)是以群體中各個(gè)體的適應(yīng)度為依據(jù), 通過(guò)選擇、交叉等操作反復(fù)迭代, 不斷尋求出適應(yīng)度較好的個(gè)體, 最終得到問(wèn)題的最優(yōu)解。適應(yīng)度函數(shù)是評(píng)價(jià)群體中個(gè)體好壞的標(biāo)準(zhǔn), 是模擬自然選擇的唯一依據(jù)。從而適應(yīng)度函數(shù)選取的優(yōu)劣直接影響遺傳算法的收斂速度及能否找到最優(yōu)解。2適應(yīng)度函數(shù)的選取首先是遺傳算法運(yùn)行初期階段, 群體中或許會(huì)出現(xiàn)少數(shù)適應(yīng)度極好的個(gè)體, 最終這些個(gè)體可能會(huì)充斥整個(gè)群體, 使用于產(chǎn)生新個(gè)體作用較大的交叉操作失去作用, 從而

8、使得群體多樣性降低, 遺傳算法提前收斂到某個(gè)局部最優(yōu)解。因此, 適應(yīng)度函數(shù)的選取應(yīng)盡量地避免早熟現(xiàn)象, 即降低適應(yīng)度較高的個(gè)體與其它個(gè)體適應(yīng)度之間的差異, 限制其復(fù)制數(shù)量以維護(hù)群體多樣性。其次是運(yùn)行后期階段, 群體越來(lái)越集中, 個(gè)體之間的差異減小, 相互之間的競(jìng)爭(zhēng)力也隨即減弱。這必然造成個(gè)體被選擇到下一代中的概率接近, 使進(jìn)化過(guò)程失去競(jìng)爭(zhēng)力, 退化為隨機(jī)選擇過(guò)程。因此, 適應(yīng)度函數(shù)的選取也應(yīng)該克服這種退化現(xiàn)象, 使算法在運(yùn)行后期階段能夠擴(kuò)大最佳個(gè)體適應(yīng)度與其它個(gè)體適應(yīng)度之間的差異, 提高個(gè)體之間的競(jìng)爭(zhēng)性。第2期張思才等:一種遺傳算法適應(yīng)度函數(shù)的改進(jìn)方法109Goldberg 的線性拉伸適應(yīng)度函

9、數(shù)為1:F 3 (X =(c -1 F F max -F avgF (X +F -cF F max -F avgF avg(1式中, F 3(X 為經(jīng)過(guò)線性拉伸得到的適應(yīng)度函數(shù); F (X 為目標(biāo)函數(shù)通過(guò)線性變換得到的適應(yīng)度函數(shù), 且與常數(shù)的選取密切相關(guān)1; F avg 為當(dāng)前群體個(gè)體平均適應(yīng)度; F max 為當(dāng)前群體中最佳個(gè)體的適應(yīng)度; c 為常數(shù), 建議取12。顯然, 適應(yīng)度函數(shù)的好壞直接取決于常數(shù)c 的選取。對(duì)于求極小值問(wèn)題, 針對(duì)上述問(wèn)題, 本文構(gòu)造具有隨進(jìn)化代數(shù)動(dòng)態(tài)調(diào)整的非線性適應(yīng)度函數(shù)為:F 3(X mG (X (2 式中, F 3(X 為非線性適應(yīng)度函數(shù); G (X 得到的目標(biāo)

10、函數(shù); QQ m ln N , N ; 進(jìn)化代數(shù)。文獻(xiàn)6100500代。由(2 式可知, 應(yīng)度。另外, 文獻(xiàn)7研究表明進(jìn)化代數(shù)與個(gè)體位串長(zhǎng)度有關(guān)。考慮個(gè)體位串長(zhǎng)度及算法運(yùn)行耗費(fèi), 最大進(jìn)化代數(shù)N 設(shè)定為200。3算例 下面以典型的遺傳算法測(cè)試函數(shù)驗(yàn)證文中構(gòu)造的適應(yīng)度函數(shù)之有效性、可行性, 比較采用不同適應(yīng)度函數(shù)的遺傳算法得到的尋優(yōu)結(jié)果。311Schaffer 函數(shù)F 6Schaffer 函數(shù)F 6的具體形式為(3 式, 其局部最優(yōu)點(diǎn)很多,最優(yōu)點(diǎn)是f 6(0, 0 =0。m in f 6(x 1, x 2 =015sin2x 21+x 22-0151+01001×(x 21+x 22

11、2x i -100, 100(i =1, 2(3 設(shè)計(jì)變量以15位二進(jìn)制數(shù)表示, 分別以不同c 值的線性拉伸遺傳算法(LG A 與改進(jìn)遺傳算法(MG A 計(jì)算, 其收斂過(guò)程分別如圖1所示, 得到的近似最優(yōu)值均為119×10-5。圖2給出了簡(jiǎn)單遺傳算法(SG A 、LG A 及M G A 的進(jìn)化情況, 從圖2中可以 看出采用非線性適應(yīng)度函數(shù)的遺傳算法收斂, 且運(yùn)行效率明顯提高。表1給出了不同c 值的LG A 收斂到函數(shù)最優(yōu)或近似最優(yōu)點(diǎn)對(duì)應(yīng)的起始收斂代數(shù)。表1線性拉伸適應(yīng)度序號(hào)cF 2F 6最優(yōu)值起始收斂代數(shù)最優(yōu)值起始收斂代數(shù)1110501000003151010000191652112

12、010000021040100001918631140100000118701000019146411550100000112601000019171511701000003880100001916362100100000012301000019192本文010000011301000019129312D e Jong 函數(shù)F2De Jong 函數(shù)F 2是一個(gè)二維函數(shù), 其函數(shù)具體形式為(4不同常數(shù)c 對(duì)應(yīng)的優(yōu)化結(jié)果圖2非線性適應(yīng)度函數(shù)對(duì)應(yīng)的收斂情況圖3不同常數(shù)c 對(duì)應(yīng)的優(yōu)化結(jié)果圖4三種不同適應(yīng)度函數(shù)對(duì)應(yīng)的優(yōu)化情況式, 唯一的全局最優(yōu)點(diǎn)為(1, 1 。m in f 2(x 1, x 2 =10

13、0(x 21-x 2 2+(1-x 12x i -21048, 21048(i =1, 2(4 設(shè)計(jì)變量以10位二進(jìn)制數(shù)表示, 分別以不同c 值的LG A 與M G A 計(jì)算, 其代斂情況分別如圖3所示。M G A 優(yōu)化得到的近似最優(yōu)值為10-6, 表1給出了不同c 值的LG A 得到的函數(shù)最110計(jì)算機(jī)應(yīng)用與軟件2006年優(yōu)或近似最優(yōu)點(diǎn)及對(duì)應(yīng)的起始收斂代數(shù)。比較兩種適應(yīng)度函數(shù)改進(jìn)方法得到的結(jié)果, 表明MG A 在最接近函數(shù)最優(yōu)點(diǎn)的情況下可以明顯提高運(yùn)行效率。圖4給出了采用不同適應(yīng)度函數(shù)的遺傳算法的進(jìn)化情況, 從圖4中可以看出采用非線性適應(yīng)度函數(shù)的遺傳算法收斂, 且運(yùn)行效率明顯提高。313討論

14、圖1圖4表明文中提出的改進(jìn)適應(yīng)度函數(shù)方法使得遺傳算法較SG A 、LG A 在運(yùn)算效率上有明顯的提高, 同時(shí)圖1與圖3及表1表明LG A 的收斂情況與常數(shù)c 密切相關(guān)。從表1可以看出F 2函數(shù)以LG A (c =210 經(jīng)過(guò)123代開(kāi)始收斂到函數(shù)最優(yōu)點(diǎn), 表明函數(shù)最優(yōu)值的獲得直接與設(shè)計(jì)者的決策密切相關(guān)。 4結(jié)論, 作為考題, , 同時(shí)也表。文中提出的非線性適應(yīng)度函數(shù)可供改善遺傳算法尋優(yōu)性能參考。參考文獻(xiàn)1Goldberg D. E . Genetic algorithm s in search, op ti m izati on and machinelearning, Addis on W

15、esley Publishing Reading,Mass . , 1989.2彌麗娜、陳治飛、孫昌志, “一種隨機(jī)并行算法A l opex 算法的改進(jìn)”, 沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào), 2000, 22(4 :296299.3馬鈞水、劉貴忠、賈玉蘭, “改進(jìn)遺傳算法搜索性能的大變異操作”,控制理論與應(yīng)用, 1998, 15(3 :40440814李大衛(wèi)、王夢(mèng)光, “一種改進(jìn)的混合遺傳算法”, 信息與控制,1997, 26(6 :449454.5SrinivasM. , Patnaik L. M. , Adap tive Pr obabilities of Cr oss over and Mu 2tat

16、i on in Genetic A lgorithm s, I EEE Transacti on Syste m,Man and Cyber 2netics . 1994, 24(4 :656667.6王小平、曹立明, 遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn)M, 西安:西安交通大學(xué)出版社, 200217張思才、張方曉, “遺傳算法在離散變量結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用”,西南交通大學(xué)學(xué)報(bào), 2003(2 :146150.(上接第9頁(yè)柄HANDLE_B。當(dāng)協(xié)作方A 要求繼續(xù)對(duì)這條直線進(jìn)行修正時(shí), 協(xié)作方B 是無(wú)法根據(jù)HANDLE_A找到HANDLE_B并對(duì)其進(jìn)行修改的。(一種替代的方法是協(xié)作方B 根據(jù)消息中的其它

17、參數(shù)在整個(gè)數(shù)據(jù)庫(kù)中查找匹配的對(duì)象, 這樣存在著如下問(wèn)題:(1 搜索費(fèi)時(shí), 減低了實(shí)時(shí)性。(2 可能有不止一個(gè)對(duì)象參數(shù)相同 。因此, 我們需要為整個(gè)協(xié)同網(wǎng)絡(luò)設(shè)計(jì)一個(gè)消息映射網(wǎng), 以防止這種情況的發(fā)生。消息映射網(wǎng)算法描述:Receive Message (提取Operati on Type, Handleif (Operati on Type =Create /3創(chuàng)建3/Create L ine (Local Handle =Get Handle (Create D icti onary (Handle, Local Handle /3雙向映射表3/else/3修改或刪除3/Local Handl

18、e =SearchD ict (Handle I f (! Local Handle Local Handle =HandleModify (Local Handle or Erase (Local Handle 以A 、B 、C 三方協(xié)同為例來(lái)說(shuō)明整個(gè)協(xié)同過(guò)程:(1 協(xié)作方A 創(chuàng)建一條直線后, 通過(guò)ARX 獲得直線句柄HANDLE_A,按照通信協(xié)議組織成消息發(fā)送給協(xié)作方B 和C 。(2 協(xié)作方B 、C 接收到服務(wù)器轉(zhuǎn)發(fā)過(guò)來(lái)的消息, 在本地創(chuàng)建完一條與協(xié)作方A 一樣的直線后, 獲得這條直線在本地?cái)?shù)據(jù)庫(kù)的句柄, 分別是HANDLE_B和。然后為本方建立一個(gè)雙向映射表。B 、C 3所示。圖3映射表

19、當(dāng)協(xié)作方B 修改這條直線時(shí), 可通過(guò)ARX 獲得這條直線的句柄HANDLE _B,然后搜索本地的映射表(LOCAL ->G LOBAL , 通過(guò)HANDLE_B找到HANDLE_A,并把HANDLE_A填入消息格式中的HANDLE 字段, 由服務(wù)器轉(zhuǎn)發(fā)給協(xié)作方A 和C, A 和C 接收到消息后, 取出HANDLE 字段, 然后分別搜索本地的映射表(G LOBAL ->LOCAL , 根據(jù)上面的映射算法, 找到本地的句柄HANDLE_A和HANDLE_C,然后修改句柄相對(duì)應(yīng)的直線。4結(jié)論按照操作語(yǔ)義構(gòu)建消息的協(xié)同辦法, 為在異構(gòu)CAD 系統(tǒng)中進(jìn)行協(xié)同提供了重要思路。在我們的設(shè)計(jì)中,

20、就成功實(shí)現(xiàn)了Aut oCADR14與Aut oC AD2000之間的基本協(xié)同。憑借這種協(xié)同方法, 可以把更多的設(shè)計(jì)細(xì)節(jié)屏蔽在動(dòng)態(tài)庫(kù)中, 從而極大地減輕了協(xié)同設(shè)計(jì)客戶端與服務(wù)器的工作。但是這種協(xié)同方法需要對(duì)CAD 的每個(gè)操作細(xì)節(jié)比較熟悉, 以保證在各個(gè)協(xié)同方都能夠完整無(wú)誤的把操作重現(xiàn)出來(lái)。而且建立一個(gè)所有操作的狀態(tài)轉(zhuǎn)換表也是一個(gè)比較繁瑣的過(guò)程。此外, 由于動(dòng)態(tài)鏈接庫(kù)是利用C AD 的二次開(kāi)發(fā)工具來(lái)實(shí)現(xiàn)的, 因而采用這種方法進(jìn)行協(xié)同的CAD 必須具備較完善的二次開(kāi)發(fā)接口。參考文獻(xiàn)1Kvan T . Collaborative design:what is it? J AUTOMATI O N I N CON 2STRACTI O N, 2000, Vol . 9, No . 4:409415.2史美林、向勇、楊光信, 計(jì)算機(jī)支持的協(xié)同工作理論與應(yīng)用M, 北京:電子工業(yè)出版社, 2