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

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

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

3、傳算法納入文化算法框架，在群體空間的代進化過程中引入隨機種群來保持種群多樣性增強算法的勘探能力，并將優(yōu)秀個體傳遞到信念空間進行信息提取更新來充分開采優(yōu)秀個體所包含信息的能力；在信念空間采用基于耗散結構理論的遺傳算法來更新最優(yōu)個體，并將更新后的最優(yōu)個體返回到群體空間中指導較差個體來提高算法的速度和效率。2文化算法框架文化算法7是源于對人類社會多層面進化的模擬，它為進文化遺傳算法的研究及其在函數(shù)優(yōu)化中的應用張敏，鄧新秀，葛斌ZHANG Min ，DENG Xin-xiu ，GE Bin大連大學信息工程學院，遼寧大連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文獻標識碼：A中圖分類號：TP301基金項目：國家自然科學基金（the National Natural Science Foundation of China under Grant No.60573072）；遼寧省教育廳高等學校研究項目（No.2023901017）。作者簡介：張敏（1966-），女，博士，副教授，主要研究領域為數(shù)據挖掘、智能算法；鄧新秀（1979-），女，碩士研究生，主要研究領域為人工智能；葛斌（1958-），男，博士，

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

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

11、的父輩；obj （）函數(shù)用來評價個體適應度；generate（）函數(shù)根據個體行為準則生成下一代個體。3算法的基本知識與思想描述3.1相關定義定義1（海明距離）兩個個體編碼對應基因位取值不同的個數(shù)稱為這兩個個體的海明距離。定義兩個個體X 1、X 2的關系R （X 1，X 2）=mi =1|X i1-X i2|，其中，X ij 表示個體j 的第i 個基因，則R （X 1，X 2）為兩個個體之間的海明距離。定義2（成功交叉次數(shù)）根據交叉概率和海明距離整個種群成功交叉的次數(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 開始可取一個稍大一點的值，避免陷入局部最優(yōu)，隨著進化的進行，逐步減小，以便在最優(yōu)解附近微調。3.2相關概念耗散結構理論耗散結構是指一個遠離平衡狀態(tài)的開放系統(tǒng)，由于不斷和外環(huán)境交換物質和能量可能從原來的無序狀態(tài)變?yōu)橐环N時間、空間或功能有序的狀態(tài)，在這種非平衡狀態(tài)下的非線性區(qū)形成的有序結構就稱為耗散結構9。遺傳算法的耗散結構在遺傳算法中，交叉和變異是兩個主要操作，交叉使種群向適應度高的方向發(fā)展，變異為這種發(fā)展提供了隨機擾動，這兩種操作造就了種群向前發(fā)展，這就是一種耗散結構。但是隨著進化的不斷進行，種群的多樣性漸趨于零，適

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

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

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

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

17、三角網格體積計算的網格局部特征信息提取、網格模型的快速檢索等展開研究。參考文獻：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陳學工，潘懋. 空間散亂點集Delaunay 四面體剖分切割算法J.計算機輔助設計與圖形學學報，2002（1）.7龐明勇，戴文俊. 基于體積分布特征匹配的三維實體網格模型檢索J.系統(tǒng)仿真學報，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周儒榮，張麗艷，蘇旭，等. 海量散亂點的曲面重建算法研究J.軟件學報，2001，12（2）：249-

21、255.10尹習雙，周宜紅. 基于虛擬現(xiàn)實的水電工程施工動態(tài)可視化仿真研究J.系統(tǒng)仿真學報，2005（7）.圖5不同規(guī)模三角網格模型的體積計算時間測試結果三角網格模型面片數(shù)量/萬3025201510500.5151050100計算時間適應度函數(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。本文采用二進制編碼，實驗中的參數(shù)設置為：群體空間種群大?。?0；最大進化代數(shù)：1000；信念空間種群大小：25；交叉概率：0.85；個體長度：40；本文算法與基本遺傳算法比較結果如表1所示。從表1可以看出，在給定解的精度要求下，算法的收斂速度（平均迭代代數(shù)

23、）得到成倍的提高，算法的優(yōu)化效率優(yōu)于基本遺傳算法。在求解過程中，算法達到的最大適應度遠遠優(yōu)于基本遺傳算法的最大適應度，算法的精確度得到了大幅度的提高。因此，不論是優(yōu)化效率還是優(yōu)化效果，該算法均優(yōu)于基本遺傳算法。5結論針對遺傳算法的不足之處，將遺傳算法進行適當改進后融合到文化算法框架中作為群體空間和信念空間用于函數(shù)優(yōu)化，算法性能由函數(shù)測試并進行了比較分析。實驗結果表明，新算法能夠提高效率和精確度，有一定的實用價值。參考文獻：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