胡新,何海浪,郭瀟然
(長安大學(xué),陜西 西安 710064)
基于MATLAB的遺傳算法優(yōu)化軟件設(shè)計(jì)
胡新,何海浪,郭瀟然
(長安大學(xué),陜西 西安 710064)
優(yōu)化設(shè)計(jì)理論使工程設(shè)計(jì)方法發(fā)生了變革。其中,遺傳算法理論與傳統(tǒng)優(yōu)化算法相比,具有魯棒性、自適應(yīng)性、全局優(yōu)化性和隱含并行性的特點(diǎn)。本文基于Matlab語言編程實(shí)現(xiàn)了遺傳算法,并設(shè)計(jì)搭建了用戶界面。通過標(biāo)準(zhǔn)測試函數(shù)對所開發(fā)軟件優(yōu)化功能進(jìn)行了測試檢驗(yàn),優(yōu)化結(jié)果準(zhǔn)確,操作簡單方便,系統(tǒng)設(shè)計(jì)滿足預(yù)期要求。
遺傳算法;Matlab;優(yōu)化軟件;標(biāo)準(zhǔn)測試函數(shù)
CLC NO.:U462.1Document Code:AArticle ID:1671-7988(2014)08-32-03
優(yōu)化設(shè)計(jì)理論與方法在20世紀(jì)60年代后期開始應(yīng)用于工程設(shè)計(jì),而直到20世紀(jì)70年代中期我國才開始有關(guān)研究。工程設(shè)計(jì)方法在這30多年的研究中發(fā)生了根本性的變革,現(xiàn)在的工程設(shè)計(jì)方法具有科學(xué)性、理性化等特點(diǎn)。
遺傳算法(GA)是一種模擬自然進(jìn)化過程搜索最優(yōu)解的方法,以自然選擇和遺傳理論為基礎(chǔ),將生物進(jìn)化過程中適者生存規(guī)則與群體內(nèi)部染色體的隨機(jī)信息交換機(jī)制相結(jié)合,與傳統(tǒng)優(yōu)化算法相比,具有魯棒性、自適應(yīng)性、全局優(yōu)化性和隱含并行性的特點(diǎn)[2]。
Matlab配備有功能強(qiáng)大的數(shù)學(xué)函數(shù)支持庫,它不僅具有效率高、編程語句簡單、適用范圍廣等特點(diǎn),而且還便于使用以直觀、簡潔并符合人們思維習(xí)慣的代碼給用戶提供了一個非常友好的開發(fā)環(huán)境。利用Matlab處理矩陣運(yùn)算的強(qiáng)大功能來編寫遺傳算法程序有著巨大的優(yōu)勢[1]。
遺傳算法計(jì)算優(yōu)化的操作過程就如像生物學(xué)上生物遺傳進(jìn)化的過程一樣,主要有三個基本操作(或稱為算子):選擇(Selection)、交叉(Crossover)、變異(Mutation)[5]。
遺傳算法基本步驟主要是:先把問題的解表示成“染色體”,在算法中也就是以二進(jìn)制編碼的串,在執(zhí)行遺傳算法之前,給出一群“染色體”,也就是假設(shè)的可行解。然后,把這些假設(shè)的可行解置于問題的“環(huán)境”中,并按適者生存的原則,從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制,再通過交叉、變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。經(jīng)過這樣的一代一代地進(jìn)化,最后就會收斂到最適應(yīng)環(huán)境的一個“染色體”上,它就是問題的最優(yōu)解[4]。
遺傳算法的具體步驟(如圖1):
(1)選擇編碼策略,把參數(shù)集合(可行解集合)轉(zhuǎn)換染色體結(jié)構(gòu)空間;
(2)定義適應(yīng)函數(shù),便于計(jì)算適應(yīng)值;
(3)確定遺傳策略,包括選擇群體大小,選擇、交叉、變異方法以及確定交叉概率、變異概率等遺傳參數(shù);
(4)隨機(jī)產(chǎn)生初始化群體;
(5)計(jì)算群體中的個體或染色體解碼后的適應(yīng)值;
(6)按照遺傳策略,運(yùn)用選擇、交叉和變異算子作用于群體,形成下一代群體;
(7)判斷群體性能是否滿足某一指標(biāo)、或者是否已完成預(yù)定的迭代次數(shù),不滿足則返回第五步、或者修改遺傳策略再返回第六步。
2.1 編碼并產(chǎn)生初始種群
2.1.1 確定編碼策略
編碼就是表現(xiàn)型到基因型的映射,編碼時要注意以下三個原則:
①完備性:問題空間中所有點(diǎn)(潛在解)都能成為GA編碼空間中的點(diǎn)(染色體位串)的表現(xiàn)型;
②健全性:GA編碼空間中的染色體位串必須對應(yīng)問題空間中的某一潛在解;
③非冗余性:染色體和潛在解必須一一對應(yīng)。
基于上述三條原則,采用二進(jìn)制的形式來進(jìn)行編碼,將某個變量值代表的個體表示為一個{0,1}二進(jìn)制串。
2.1.2 要確定種群規(guī)模M
過大或過小的種群規(guī)模都會對進(jìn)化結(jié)果產(chǎn)生影響,一般種群設(shè)定為300~400個個體。
2.1.3 計(jì)算染色體長度
染色體的長度是根據(jù)所設(shè)定的求解精度計(jì)算而得的;假定求解精度為pre,則染色體的長度L由如下公式計(jì)算得出:
最后隨機(jī)生成M個長度為L的二進(jìn)制編碼串,構(gòu)成初始種群。實(shí)現(xiàn)過程如下:
2.2 雜交
雜交就是將一組染色體上對應(yīng)基因段的交換得到新的染色體,然后得到新的染色體組,組成新的群體[3]。雜交的實(shí)現(xiàn)過程如下:
2.3 變異
變異是通過一個小概率改變?nèi)旧w位串上的某個基因。變異的實(shí)現(xiàn)過程如下:
2.4 適應(yīng)度評價(jià)
適應(yīng)度評價(jià)的關(guān)鍵在于適應(yīng)度函數(shù)的選擇,由于本文是采用遺傳算法作函數(shù)優(yōu)化,則理想情況應(yīng)是直接將目標(biāo)函數(shù)作為適應(yīng)度函數(shù),這樣目標(biāo)函數(shù)值即為適應(yīng)度值,方便進(jìn)行后續(xù)的選擇和最優(yōu)解輸出[7]。
針對本文還要做出遺傳算法的優(yōu)化界面,適應(yīng)度函數(shù)也
是根據(jù)用戶的需要自行輸入的,這樣就會產(chǎn)生適應(yīng)度函數(shù)不確定的問題,為了解決這個問題,在Matlab編程時使用了eval函數(shù),將輸入的目標(biāo)函數(shù)字符串經(jīng)轉(zhuǎn)化識別后,根據(jù)優(yōu)化變量的取值范圍求其目標(biāo)函數(shù)值即適應(yīng)度值[6]。這樣適應(yīng)度評價(jià)的實(shí)現(xiàn)過程為:
2.5 選擇
優(yōu)勝劣汰的選擇機(jī)制使得適應(yīng)值大的個體有較大的存活機(jī)會,不同的選擇策略對算法性能有較大的影響。對函數(shù)優(yōu)化問題上,基于局部競爭的選擇對適應(yīng)度函數(shù)要求較小,同時能夠?qū)⑦m應(yīng)度值小的個體輕松選擇出來。因此,本文采用基于局部競爭的選擇方法[8]。選擇的實(shí)現(xiàn)過程如下:
2.6 GUI制作
首先對GUI進(jìn)行布局設(shè)計(jì),然后編寫實(shí)現(xiàn)GUI控件功能的回調(diào)函數(shù);同時到工作界面的美觀性,對圖形區(qū)添加了圖片背景,最終完成的工作界面如圖2所示:
標(biāo)準(zhǔn)測試函數(shù)Bohachevsky函數(shù)F(χ,χ)=χ2+2χ2-
1212 0.3cos(3πχ1)cos(4πχ2)+0.3(-50≤χi≤50)在(χ1,χ2)=(0,0)處有一全局極小值0。使用Bohachevsky函數(shù)對該軟件進(jìn)行功能驗(yàn)證結(jié)果如圖3所示:
由上述驗(yàn)證過程可知:得出最小值為0,此時優(yōu)化變量x1、x2的取值均為0,與之前介紹的Bohachevsky函數(shù)特性一致,因此,優(yōu)化結(jié)果正確,該軟件功能能正常實(shí)現(xiàn)。
但是,本軟件系統(tǒng)還存在一些不足:該系統(tǒng)僅是針對二元函數(shù)的優(yōu)化問題進(jìn)行的設(shè)計(jì),還未能拓展至多元函數(shù),二元函數(shù)和多元函數(shù)的優(yōu)化在程序?qū)崿F(xiàn)上的差異主要是在適應(yīng)度評價(jià)、個體和優(yōu)化變量取值范圍之間的轉(zhuǎn)化兩個方面,這也將是我在今后學(xué)習(xí)中需要解決的一個問題。
[1] 張志涌,楊祖櫻.Matlab教程(R2011a)[M].北京:航空航天大學(xué)出版社,2012.
[2] 雷英杰.MATLAB遺傳算法工具箱及應(yīng)用[M].西安:電子科技大學(xué)出版社,2005.
[3] 宋瑩,任金霞等.基于Matlab的GUI設(shè)計(jì)遺傳算法優(yōu)化軟件[J].計(jì)算機(jī)與現(xiàn)代化,2004.
[8] 羅述全.傳統(tǒng)優(yōu)化算法與遺傳算法的比較[J] .湖北工業(yè)大學(xué)學(xué)報(bào).2007.
[5] 章紅兵.基于MATLAB的遺傳算法優(yōu)化工具箱的應(yīng)用[C].中國科技文論在線.
[6] 陳國良,王煦法,莊鎮(zhèn)泉.遺傳算法及其應(yīng)用[M].北京:人民郵電出版社,1996.
[7] Bo-Ping Wang,Supervising Professor,Wen S.Chan.GENETIC ALGORITHMS IN DESIGN OPTIMIZATION[D].American,The Unveisity of Texas,2000.
[8] 劉國華,包宏,李文超.用Matlab實(shí)現(xiàn)遺傳算法程序[J].計(jì)算機(jī)應(yīng)用研究,2001.
Genetic algorithm optimization software design based on MATLAB
Huxin, He Hailang, Guo Xiaoran
(Chang'an University, Shaanxi Xi’an 710064)
The optimal design theory in engineering design has made the traditional engineering approach to a fundamental change .The theory of genetic algorithm in the optimization of the design are robust, adaptive, global optimization and implicit parallelism, which the traditional optimization algorithms donot have. This paper dsigns the genetic algorithm based on Matlab programming and build the user interface. Through the standard test function test the development software optimization function, the optimization results accurate, system friendly interface, easy to operate, the system design is expected to meet.
Genetic Algorithms; Matlab; Optimization software; Standard test functions
U462.1
A
1671-7988(2014)08-32-03
胡新,碩士研究生,就讀于長安大學(xué)汽車學(xué)院。