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

1、第23卷第2期計算機應(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è)計及優(yōu)化算法研究。一種遺傳算法適應(yīng)度函數(shù)的改進方法張思才張方曉(中國工程物理研究院結(jié)構(gòu)力學研究所四川綿陽621900摘要針對簡單遺傳算法中線性適應(yīng)度函數(shù)隨進化過程恒定不變的缺點, 數(shù)。以典型的遺傳算法測試函數(shù)為算例, 分別以Goldberg 1。計算結(jié)果關(guān)鍵詞遺傳算法適應(yīng)度函數(shù)優(yōu)化計算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, 簡稱G A 是模擬生物進化過程中, “適者生存, 優(yōu)勝劣汰”規(guī)律而無需函數(shù)梯度信息的自適應(yīng)全局搜索算法1。遺傳算法倍受各行設(shè)計者青睞之原因在于:這類隨機算法能夠同時處理N 個設(shè)計變量, 有利于實現(xiàn)并行操作, 提高多變量優(yōu)化問題的計算效率; 能夠跳出局部最優(yōu)解而做到全局搜索。遺傳算法依靠選擇操作模擬自然界中的“適者生存, 優(yōu)勝劣汰”這一過程, 即選擇操作來引導算法的搜索方向, 而選擇操作是以個體的適應(yīng)度作為確定性指標, 從當前群體中選擇適應(yīng)值高的個體以生成交配池。如此必然造成群體中基因

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

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

8、使得群體多樣性降低, 遺傳算法提前收斂到某個局部最優(yōu)解。因此, 適應(yīng)度函數(shù)的選取應(yīng)盡量地避免早熟現(xiàn)象, 即降低適應(yīng)度較高的個體與其它個體適應(yīng)度之間的差異, 限制其復(fù)制數(shù)量以維護群體多樣性。其次是運行后期階段, 群體越來越集中, 個體之間的差異減小, 相互之間的競爭力也隨即減弱。這必然造成個體被選擇到下一代中的概率接近, 使進化過程失去競爭力, 退化為隨機選擇過程。因此, 適應(yīng)度函數(shù)的選取也應(yīng)該克服這種退化現(xiàn)象, 使算法在運行后期階段能夠擴大最佳個體適應(yīng)度與其它個體適應(yīng)度之間的差異, 提高個體之間的競爭性。第2期張思才等:一種遺傳算法適應(yīng)度函數(shù)的改進方法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)過線性拉伸得到的適應(yīng)度函數(shù); F (X 為目標函數(shù)通過線性變換得到的適應(yīng)度函數(shù), 且與常數(shù)的選取密切相關(guān)1; F avg 為當前群體個體平均適應(yīng)度; F max 為當前群體中最佳個體的適應(yīng)度; c 為常數(shù), 建議取12。顯然, 適應(yīng)度函數(shù)的好壞直接取決于常數(shù)c 的選取。對于求極小值問題, 針對上述問題, 本文構(gòu)造具有隨進化代數(shù)動態(tài)調(diào)整的非線性適應(yīng)度函數(shù)為:F 3(X mG (X (2 式中, F 3(X 為非線性適應(yīng)度函數(shù); G (X 得到的目標

10、函數(shù); QQ m ln N , N ; 進化代數(shù)。文獻6100500代。由(2 式可知, 應(yīng)度。另外, 文獻7研究表明進化代數(shù)與個體位串長度有關(guān)?？紤]個體位串長度及算法運行耗費, 最大進化代數(shù)N 設(shè)定為200。3算例 下面以典型的遺傳算法測試函數(shù)驗證文中構(gòu)造的適應(yīng)度函數(shù)之有效性、可行性, 比較采用不同適應(yīng)度函數(shù)的遺傳算法得到的尋優(yōu)結(jié)果。311Schaffer 函數(shù)F 6Schaffer 函數(shù)F 6的具體形式為(3 式, 其局部最優(yōu)點很多,最優(yōu)點是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è)計變量以15位二進制數(shù)表示, 分別以不同c 值的線性拉伸遺傳算法(LG A 與改進遺傳算法(MG A 計算, 其收斂過程分別如圖1所示, 得到的近似最優(yōu)值均為119×10-5。圖2給出了簡單遺傳算法(SG A 、LG A 及M G A 的進化情況, 從圖2中可以 看出采用非線性適應(yīng)度函數(shù)的遺傳算法收斂, 且運行效率明顯提高。表1給出了不同c 值的LG A 收斂到函數(shù)最優(yōu)或近似最優(yōu)點對應(yīng)的起始收斂代數(shù)。表1線性拉伸適應(yīng)度序號cF 2F 6最優(yōu)值起始收斂代數(shù)最優(yōu)值起始收斂代數(shù)1110501000003151010000191652112

12、010000021040100001918631140100000118701000019146411550100000112601000019171511701000003880100001916362100100000012301000019192本文010000011301000019129312D e Jong 函數(shù)F2De Jong 函數(shù)F 2是一個二維函數(shù), 其函數(shù)具體形式為(4不同常數(shù)c 對應(yīng)的優(yōu)化結(jié)果圖2非線性適應(yīng)度函數(shù)對應(yīng)的收斂情況圖3不同常數(shù)c 對應(yīng)的優(yōu)化結(jié)果圖4三種不同適應(yīng)度函數(shù)對應(yīng)的優(yōu)化情況式, 唯一的全局最優(yōu)點為(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è)計變量以10位二進制數(shù)表示, 分別以不同c 值的LG A 與M G A 計算, 其代斂情況分別如圖3所示。M G A 優(yōu)化得到的近似最優(yōu)值為10-6, 表1給出了不同c 值的LG A 得到的函數(shù)最110計算機應(yīng)用與軟件2006年優(yōu)或近似最優(yōu)點及對應(yīng)的起始收斂代數(shù)。比較兩種適應(yīng)度函數(shù)改進方法得到的結(jié)果, 表明MG A 在最接近函數(shù)最優(yōu)點的情況下可以明顯提高運行效率。圖4給出了采用不同適應(yīng)度函數(shù)的遺傳算法的進化情況, 從圖4中可以看出采用非線性適應(yīng)度函數(shù)的遺傳算法收斂, 且運行效率明顯提高。313討論

14、圖1圖4表明文中提出的改進適應(yīng)度函數(shù)方法使得遺傳算法較SG A 、LG A 在運算效率上有明顯的提高, 同時圖1與圖3及表1表明LG A 的收斂情況與常數(shù)c 密切相關(guān)。從表1可以看出F 2函數(shù)以LG A (c =210 經(jīng)過123代開始收斂到函數(shù)最優(yōu)點, 表明函數(shù)最優(yōu)值的獲得直接與設(shè)計者的決策密切相關(guān)。 4結(jié)論, 作為考題, , 同時也表。文中提出的非線性適應(yīng)度函數(shù)可供改善遺傳算法尋優(yōu)性能參考。參考文獻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彌麗娜、陳治飛、孫昌志, “一種隨機并行算法A l opex 算法的改進”, 沈陽工業(yè)大學學報, 2000, 22(4 :296299.3馬鈞水、劉貴忠、賈玉蘭, “改進遺傳算法搜索性能的大變異操作”,控制理論與應(yīng)用, 1998, 15(3 :40440814李大衛(wèi)、王夢光, “一種改進的混合遺傳算法”, 信息與控制,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)用與軟件實現(xiàn)M, 西安:西安交通大學出版社, 200217張思才、張方曉, “遺傳算法在離散變量結(jié)構(gòu)優(yōu)化設(shè)計中的應(yīng)用”,西南交通大學學報, 2003(2 :146150.(上接第9頁柄HANDLE_B。當協(xié)作方A 要求繼續(xù)對這條直線進行修正時, 協(xié)作方B 是無法根據(jù)HANDLE_A找到HANDLE_B并對其進行修改的。(一種替代的方法是協(xié)作方B 根據(jù)消息中的其它

17、參數(shù)在整個數(shù)據(jù)庫中查找匹配的對象, 這樣存在著如下問題:(1 搜索費時, 減低了實時性。(2 可能有不止一個對象參數(shù)相同 。因此, 我們需要為整個協(xié)同網(wǎng)絡(luò)設(shè)計一個消息映射網(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é)同為例來說明整個協(xié)同過程:(1 協(xié)作方A 創(chuàng)建一條直線后, 通過ARX 獲得直線句柄HANDLE_A,按照通信協(xié)議組織成消息發(fā)送給協(xié)作方B 和C 。(2 協(xié)作方B 、C 接收到服務(wù)器轉(zhuǎn)發(fā)過來的消息, 在本地創(chuàng)建完一條與協(xié)作方A 一樣的直線后, 獲得這條直線在本地數(shù)據(jù)庫的句柄, 分別是HANDLE_B和。然后為本方建立一個雙向映射表。B 、C 3所示。圖3映射表

19、當協(xié)作方B 修改這條直線時, 可通過ARX 獲得這條直線的句柄HANDLE _B,然后搜索本地的映射表(LOCAL ->G LOBAL , 通過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,然后修改句柄相對應(yīng)的直線。4結(jié)論按照操作語義構(gòu)建消息的協(xié)同辦法, 為在異構(gòu)CAD 系統(tǒng)中進行協(xié)同提供了重要思路。在我們的設(shè)計中,

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