文化遺傳算法的研究及其在函數(shù)優(yōu)化中的應(yīng)用

1、Computer Engineering and Applications 計算機(jī)工程與應(yīng)用2009，45（18）1引言遺傳算法（Genetic Algorithm ，GA）是1975年由Holland 教授首先提出的一種基于自然選擇和基因遺傳學(xué)原理的隨機(jī)并行搜索算法1，與傳統(tǒng)的算法相比，它具有全局尋優(yōu)和收斂速度快等優(yōu)點(diǎn)，但是遺傳算法本身在理論和應(yīng)用方法上仍有許多亟待完善之處。研究發(fā)現(xiàn)，GA 能用極快的速度達(dá)到最優(yōu)解的90%左右，但要達(dá)到真正的最優(yōu)解則要花費(fèi)很長的時間2。為了提高遺傳算法的性能，研究人員提出了許多相應(yīng)的改進(jìn)遺傳算法，如采用二元變異算子（變異操作需要兩個個體）替代傳統(tǒng)的變異算子3

2、、將病毒機(jī)制引入遺傳算法4、將局部搜索算法與遺傳算法結(jié)合5等。這些方法都在一定程度上提高了遺傳算法的性能。遺傳算法一個顯著的缺點(diǎn)就是隨著算法的進(jìn)行其種群多樣性逐漸消失，很容易于陷入早熟收斂。引入隨機(jī)種群可以改善種群的多樣性問題，但是又影響到算法的效率。然而，利用遺傳算法求解問題的根本目標(biāo)是在盡可能短的時間內(nèi)找到問題的全局最優(yōu)解，算法結(jié)束時往往最關(guān)心的是種群中最優(yōu)個體的性能，從概率上來說，種群中優(yōu)秀個體和全局最優(yōu)解的親和度6要大于其他個體和全局最優(yōu)解之間的親和度。所以，優(yōu)秀個體所包含的信息能否被充分利用也是決定該算法優(yōu)化能力的一個重要因素。本文從收斂速度和收斂效率兩方面來提高遺傳算法的性能，將遺

3、傳算法納入文化算法框架，在群體空間的代進(jìn)化過程中引入隨機(jī)種群來保持種群多樣性增強(qiáng)算法的勘探能力，并將優(yōu)秀個體傳遞到信念空間進(jìn)行信息提取更新來充分開采優(yōu)秀個體所包含信息的能力；在信念空間采用基于耗散結(jié)構(gòu)理論的遺傳算法來更新最優(yōu)個體，并將更新后的最優(yōu)個體返回到群體空間中指導(dǎo)較差個體來提高算法的速度和效率。2文化算法框架文化算法7是源于對人類社會多層面進(jìn)化的模擬，它為進(jìn)文化遺傳算法的研究及其在函數(shù)優(yōu)化中的應(yīng)用張敏，鄧新秀，葛斌ZHANG Min ，DENG Xin-xiu ，GE Bin大連大學(xué)信息工程學(xué)院，遼寧大連116622School of Information Engineering ，D

4、alian University ，Dalian ，Liaoning 116622，ChinaE-mail ：kingfisher1014ZHANG Min ，DENG Xin-xiu ，GE Bin.Research on cultural genetic algorithm and its application in function optimization.Computer Engineering and Applications ，2009，45（18）：56-58. Abstract ：In order to improve the performance of genetic

5、algorithm ，an improved genetic algorithm based on cultural algorithmframework is developed to be applied to the function optimization.The improved genetic algorithms are embedded into cultural al gorithm framework and compose population space and belief space.In population space ，it introduces a ran

6、dom population to ex tend search area and parts of the worst individuals are organized to crossover with part of best individuals that the belief space provides in probability.A dissipative system theory is used in genetic algorithm so as to tapping the high guidance of the whole population and regu

7、lation potential of self-organizing to enhance accuracy and efficiency.The performance of the proposed im proved generic algorithm is evaluated by a number of test functions.Experimental results show that the algorithm can be efficient ly applied to the function optimization. Key words ：cultural fra

8、mework ；genetic algorithm ；dissipative structure文章編號：10028331（2009）18-0056-03文獻(xiàn)標(biāo)識碼：A中圖分類號：TP301基金項目：國家自然科學(xué)基金（the National Natural Science Foundation of China under Grant No.60573072）；遼寧省教育廳高等學(xué)校研究項目（No.2023901017）。作者簡介：張敏（1966-），女，博士，副教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘、智能算法；鄧新秀（1979-），女，碩士研究生，主要研究領(lǐng)域?yàn)槿斯ぶ悄埽桓鸨螅?958-），男，博士，

9、教授，主要研究領(lǐng)域?yàn)橹悄芸刂?。收稿日期?008-04-16修回日期：2008-07-11562009，45（18）update （）信念空間群體空間accept（）influence（）obj（）generate（）select（）圖1文化算法框架初始化群體空間群體空間計算個體適應(yīng)度并排序傳一半優(yōu)秀個體到信念空間結(jié)束引入隨機(jī)種群改進(jìn)的GA最優(yōu)個體傳遞到群體空間基于耗散結(jié)構(gòu)的GA滿足終止條件？接收群體空間個體與原來個體比較，保留最好的一半個體信念空間是否圖2算法的執(zhí)行過程化算法提供了一個新的計算框架，與其他進(jìn)化算法相比，文化算法概念清晰，更能精確的反應(yīng)進(jìn)化過程。文化算法框架（Culture a

10、lgorithm framework ）是由群體空間和信念空間組成的8。群體空間是從微觀角度模擬個體根據(jù)一定的行為準(zhǔn)則進(jìn)化的過程，而信念空間是從宏觀角度模擬文化的形成、傳遞和比較等進(jìn)化過程?；究蚣苋鐖D1所示。群體空間和信念空間相對獨(dú)立進(jìn)化，群體空間個體在進(jìn)化過程中形成個體經(jīng)驗(yàn)，通過accept （）函數(shù)傳遞到信念空間；信念空間接收到個體經(jīng)驗(yàn)與現(xiàn)有的經(jīng)驗(yàn)進(jìn)行比較優(yōu)化，通過up date（）函數(shù)更新群體經(jīng)驗(yàn)；群體經(jīng)驗(yàn)形成以后，通過influence （）函數(shù)來影響群體空間中個體的行為，使群體空間中的個體得到更高的進(jìn)化效率；群體空間中的select （）函數(shù)是從新生個體中選擇一部分個體作為下代個體

11、的父輩；obj （）函數(shù)用來評價個體適應(yīng)度；generate（）函數(shù)根據(jù)個體行為準(zhǔn)則生成下一代個體。3算法的基本知識與思想描述3.1相關(guān)定義定義1（海明距離）兩個個體編碼對應(yīng)基因位取值不同的個數(shù)稱為這兩個個體的海明距離。定義兩個個體X 1、X 2的關(guān)系R （X 1，X 2）=mi =1|X i1-X i2|，其中，X ij 表示個體j 的第i 個基因，則R （X 1，X 2）為兩個個體之間的海明距離。定義2（成功交叉次數(shù)）根據(jù)交叉概率和海明距離整個種群成功交叉的次數(shù)。定義=Ncn =1（R （X in ，X jn ）P r ）為成功交叉次數(shù)，其中，（R （X in ，X jn ）P r ）=1

12、，成功交叉0，未成功交叉，Nc 為以交叉概率確定交叉的個體數(shù)目的一半；P r 開始可取一個稍大一點(diǎn)的值，避免陷入局部最優(yōu)，隨著進(jìn)化的進(jìn)行，逐步減小，以便在最優(yōu)解附近微調(diào)。3.2相關(guān)概念耗散結(jié)構(gòu)理論耗散結(jié)構(gòu)是指一個遠(yuǎn)離平衡狀態(tài)的開放系統(tǒng)，由于不斷和外環(huán)境交換物質(zhì)和能量可能從原來的無序狀態(tài)變?yōu)橐环N時間、空間或功能有序的狀態(tài)，在這種非平衡狀態(tài)下的非線性區(qū)形成的有序結(jié)構(gòu)就稱為耗散結(jié)構(gòu)9。遺傳算法的耗散結(jié)構(gòu)在遺傳算法中，交叉和變異是兩個主要操作，交叉使種群向適應(yīng)度高的方向發(fā)展，變異為這種發(fā)展提供了隨機(jī)擾動，這兩種操作造就了種群向前發(fā)展，這就是一種耗散結(jié)構(gòu)。但是隨著進(jìn)化的不斷進(jìn)行，種群的多樣性漸趨于零，適

13、應(yīng)度值不能得到改善，耗散結(jié)構(gòu)逐漸消失，已無法滿足有序的要求，為了避免這種情況，本文將變異概率和交叉成功次數(shù)聯(lián)系起來。交叉成功次數(shù)越多，變異次數(shù)減少，變異可以理解為系統(tǒng)與環(huán)境進(jìn)行能量交換的方式，這樣便構(gòu)成了耗散結(jié)構(gòu)，使種群的進(jìn)化能夠充分利用交叉和變異的優(yōu)點(diǎn)，取得較為理想的效果。3.3群體空間的進(jìn)化（1）生成規(guī)模大小為N 的初始種群。（2）通過obj （）函數(shù)計算種群中個體的適應(yīng)度值，并按從大到小排序。（3）將一半優(yōu)秀個體通過accept （）函數(shù)傳遞到信念空間。（4）通過influence （）函數(shù)接收信念空間中的最優(yōu)個體，判斷是否滿足終止條件，若滿足，程序結(jié)束，否則，執(zhí)行下一步。（5）產(chǎn)生空間

14、大小30%的隨機(jī)種群。（6）最優(yōu)個體與最差個體的40%進(jìn)行交叉操作，其余進(jìn)行普通交叉操作。（7）進(jìn)行變異操作，產(chǎn)生下一代種群。（8）轉(zhuǎn)到（2）。3.4信念空間的進(jìn)化信念空間接收群體空間的一半優(yōu)秀個體后執(zhí)行以下操作：（1）信念空間把通過accept （）函數(shù)接收到的優(yōu)秀個體與原來的比較，保留迄今為止最好的一部分個體。（2）選擇信念空間一部分個體進(jìn)行耗散結(jié)構(gòu)的遺傳算法操作，并按一定規(guī)則逐步增大搜索空間，從而能充分利用優(yōu)秀個體，使好的個體多次獲得繁殖機(jī)會。（3）若搜索空間達(dá)到了信念空間大小，執(zhí)行（4）；否則，執(zhí)行（2）。（4）把最優(yōu)個體通過influence （）函數(shù)傳遞到群體空間。3.5基于文化框

15、架的遺傳算法群體空間引入隨機(jī)種群來維持種群的多樣性，可防止早熟收斂現(xiàn)象的發(fā)生，但是，不能保證算法的速度和效率；為了能快速找到最優(yōu)個體，在信念空間中減小種群大小為群體空間的一半，充分開采至今為止優(yōu)秀個體所包含的信息。由于優(yōu)秀個體的相似性，采用耗散結(jié)構(gòu)避免找到局部最優(yōu)解，使交叉和變異這兩個主要操作相互交換信息來達(dá)到一種有序狀態(tài)，促進(jìn)種群向前發(fā)展。更新優(yōu)秀個體后再反饋到群體空間與大部分較差個體進(jìn)行交叉操作來更新較差個體，提高算法的效率。在這種傳遞、比較、更新和反饋中快速找到最優(yōu)解。算法的執(zhí)行過程如圖2所示。4實(shí)驗(yàn)結(jié)果及分析為了驗(yàn)證算法的有效性，本文選擇了5個典型函數(shù)進(jìn)行測張敏，鄧新秀，葛斌：文化遺傳

16、算法的研究及其在函數(shù)優(yōu)化中的應(yīng)用57Computer Engineering and Applications 計算機(jī)工程與應(yīng)用2009，45（18）（上接34頁）為了測試本文設(shè)計的體積計算方法的在不同復(fù)雜程度的三角網(wǎng)格模型下的性能，采取了具有不同數(shù)量級三角面片的三角網(wǎng)格模型進(jìn)行了測試，測試結(jié)果如圖5所示。測試結(jié)果表明本文設(shè)計的體積計算方法針對不同規(guī)模的三角網(wǎng)格模型均具有良好的性能。 5結(jié)論三角網(wǎng)格是最常用的網(wǎng)格模型，提出了一種直接在三角網(wǎng)格面片集合上進(jìn)行模型體積計算的方法，并通過在水電工程施工三維模型的施工單元方量計算中的應(yīng)用證實(shí)了該方法的快速有效性。進(jìn)一步的研究將在本文工作的基礎(chǔ)上，對基于

17、三角網(wǎng)格體積計算的網(wǎng)格局部特征信息提取、網(wǎng)格模型的快速檢索等展開研究。參考文獻(xiàn)：1Gotsman C ，Gumhold S ，Kobbelt L.Simplification and compressionof 3D meshesC/IskeA ，Quak E ，F(xiàn)loater M S.Proc of the Tutori als on Multiresolution in Geometric Modelling.New York ：Springer-Verlag ，2002：319-361.2Li L ，Schemenauer N ，Peng X ，et al.A reverse engin

18、eering systemfor rapid manufacturing of complex objectsJ.Roboticsand Comput er-Integrated Manufacturing ，2002，18（1）：53-67.3Ke Ying-lin ，Li An.Extruded surface extraction based on unorga nized point cloud in reverse engineeringJ.Journalof Computer-Aided Design &Computer Graphics ，2005，17（6）：1329-

19、1334. 4Zorin D N.Stationary subdivision and multiresolution surface repre sentationsD.CaliforniaInstitute of Technology ，Pasadena ，California ，1998.5Peng J L ，Kim C S ，Kuo C C J.Technologies for 3D mesh com pression ：A surveyJ.ELSEVIERJournal of Visual Communication and Image Representation ，2005，16

20、（6）：688-733.6陳學(xué)工，潘懋. 空間散亂點(diǎn)集Delaunay 四面體剖分切割算法J.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2002（1）.7龐明勇，戴文俊. 基于體積分布特征匹配的三維實(shí)體網(wǎng)格模型檢索J.系統(tǒng)仿真學(xué)報，2007（1）：30-34.8Loop C.Bounded curvature triangle mesh subdivision with the con vex hull propertyJ.TheVisual Computer ，2002，18（5/6）：316-325. 9周儒榮，張麗艷，蘇旭，等. 海量散亂點(diǎn)的曲面重建算法研究J.軟件學(xué)報，2001，12（2）：249-

21、255.10尹習(xí)雙，周宜紅. 基于虛擬現(xiàn)實(shí)的水電工程施工動態(tài)可視化仿真研究J.系統(tǒng)仿真學(xué)報，2005（7）.圖5不同規(guī)模三角網(wǎng)格模型的體積計算時間測試結(jié)果三角網(wǎng)格模型面片數(shù)量/萬3025201510500.5151050100計算時間適應(yīng)度函數(shù)f 1f 2f 3f 4f 5SGA本文算法表1算法性能比較試，并與基本遺傳算法做了比較。min f 1=100×（x 2-x 21）2+（1-x 1）2s.t. -5x 1，x 25min f 2=|（1-x ）×x ×sin （200x ）|s.t. 0x 1min f 3=-（x 2+2y 2-0.3cos （3x ）

22、-0.4cos （3y ）+4s.t. -1x ，y 1min f 4=0.5-sin2x+y -0.51+0.001×（x 2+y 2）2s.t. -100x ，y 100min f 5=x 21+x222-cos （2x 1）cos （2x 2）s.t. -10x 1，x 21011+f 1，f 2，f 3，f 412+f 5。本文采用二進(jìn)制編碼，實(shí)驗(yàn)中的參數(shù)設(shè)置為：群體空間種群大?。?0；最大進(jìn)化代數(shù)：1000；信念空間種群大?。?5；交叉概率：0.85；個體長度：40；本文算法與基本遺傳算法比較結(jié)果如表1所示。從表1可以看出，在給定解的精度要求下，算法的收斂速度（平均迭代代數(shù)

23、）得到成倍的提高，算法的優(yōu)化效率優(yōu)于基本遺傳算法。在求解過程中，算法達(dá)到的最大適應(yīng)度遠(yuǎn)遠(yuǎn)優(yōu)于基本遺傳算法的最大適應(yīng)度，算法的精確度得到了大幅度的提高。因此，不論是優(yōu)化效率還是優(yōu)化效果，該算法均優(yōu)于基本遺傳算法。5結(jié)論針對遺傳算法的不足之處，將遺傳算法進(jìn)行適當(dāng)改進(jìn)后融合到文化算法框架中作為群體空間和信念空間用于函數(shù)優(yōu)化，算法性能由函數(shù)測試并進(jìn)行了比較分析。實(shí)驗(yàn)結(jié)果表明，新算法能夠提高效率和精確度，有一定的實(shí)用價值。參考文獻(xiàn)：1Holland J H.Adaptation in natural and artificial systemsM.S.l.：MIT Press ，1975.2Kitano H.Empirical studies on the speed of convergence of theneural network