文化遗传算法的研究及其在函数优化中的应用

1、Computer Engineering and Applications 计算机工程与应用2009，45（18）1引言遗传算法（Genetic Algorithm ，GA）是1975年由Holland 教授首先提出的一种基于自然选择和基因遗传学原理的随机并行搜索算法1，与传统的算法相比，它具有全局寻优和收敛速度快等优点，但是遗传算法本身在理论和应用方法上仍有许多亟待完善之处。研究发现，GA 能用极快的速度达到最优解的90%左右，但要达到真正的最优解则要花费很长的时间2。为了提高遗传算法的性能，研究人员提出了许多相应的改进遗传算法，如采用二元变异算子（变异操作需要两个个体）替代传统的变异算子3

2、、将病毒机制引入遗传算法4、将局部搜索算法与遗传算法结合5等。这些方法都在一定程度上提高了遗传算法的性能。遗传算法一个显著的缺点就是随着算法的进行其种群多样性逐渐消失，很容易于陷入早熟收敛。引入随机种群可以改善种群的多样性问题，但是又影响到算法的效率。然而，利用遗传算法求解问题的根本目标是在尽可能短的时间内找到问题的全局最优解，算法结束时往往最关心的是种群中最优个体的性能，从概率上来说，种群中优秀个体和全局最优解的亲和度6要大于其他个体和全局最优解之间的亲和度。所以，优秀个体所包含的信息能否被充分利用也是决定该算法优化能力的一个重要因素。本文从收敛速度和收敛效率两方面来提高遗传算法的性能，将遗

3、传算法纳入文化算法框架，在群体空间的代进化过程中引入随机种群来保持种群多样性增强算法的勘探能力，并将优秀个体传递到信念空间进行信息提取更新来充分开采优秀个体所包含信息的能力；在信念空间采用基于耗散结构理论的遗传算法来更新最优个体，并将更新后的最优个体返回到群体空间中指导较差个体来提高算法的速度和效率。2文化算法框架文化算法7是源于对人类社会多层面进化的模拟，它为进文化遗传算法的研究及其在函数优化中的应用张敏，邓新秀，葛斌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-），女，博士，副教授，主要研究领域为数据挖掘、智能算法；邓新秀（1979-），女，硕士研究生，主要研究领域为人工智能；葛斌（1958-），男，博士，

9、教授，主要研究领域为智能控制。收稿日期：2008-04-16修回日期：2008-07-11562009，45（18）update （）信念空间群体空间accept（）influence（）obj（）generate（）select（）图1文化算法框架初始化群体空间群体空间计算个体适应度并排序传一半优秀个体到信念空间结束引入随机种群改进的GA最优个体传递到群体空间基于耗散结构的GA满足终止条件？接收群体空间个体与原来个体比较，保留最好的一半个体信念空间是否图2算法的执行过程化算法提供了一个新的计算框架，与其他进化算法相比，文化算法概念清晰，更能精确的反应进化过程。文化算法框架（Culture a

10、lgorithm framework ）是由群体空间和信念空间组成的8。群体空间是从微观角度模拟个体根据一定的行为准则进化的过程，而信念空间是从宏观角度模拟文化的形成、传递和比较等进化过程。基本框架如图1所示。群体空间和信念空间相对独立进化，群体空间个体在进化过程中形成个体经验，通过accept （）函数传递到信念空间；信念空间接收到个体经验与现有的经验进行比较优化，通过up date（）函数更新群体经验；群体经验形成以后，通过influence （）函数来影响群体空间中个体的行为，使群体空间中的个体得到更高的进化效率；群体空间中的select （）函数是从新生个体中选择一部分个体作为下代个体

11、的父辈；obj （）函数用来评价个体适应度；generate（）函数根据个体行为准则生成下一代个体。3算法的基本知识与思想描述3.1相关定义定义1（海明距离）两个个体编码对应基因位取值不同的个数称为这两个个体的海明距离。定义两个个体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（成功交叉次数）根据交叉概率和海明距离整个种群成功交叉的次数。定义=Ncn =1（R （X in ，X jn ）P r ）为成功交叉次数，其中，（R （X in ，X jn ）P r ）=1

12、，成功交叉0，未成功交叉，Nc 为以交叉概率确定交叉的个体数目的一半；P r 开始可取一个稍大一点的值，避免陷入局部最优，随着进化的进行，逐步减小，以便在最优解附近微调。3.2相关概念耗散结构理论耗散结构是指一个远离平衡状态的开放系统，由于不断和外环境交换物质和能量可能从原来的无序状态变为一种时间、空间或功能有序的状态，在这种非平衡状态下的非线性区形成的有序结构就称为耗散结构9。遗传算法的耗散结构在遗传算法中，交叉和变异是两个主要操作，交叉使种群向适应度高的方向发展，变异为这种发展提供了随机扰动，这两种操作造就了种群向前发展，这就是一种耗散结构。但是随着进化的不断进行，种群的多样性渐趋于零，适

13、应度值不能得到改善，耗散结构逐渐消失，已无法满足有序的要求，为了避免这种情况，本文将变异概率和交叉成功次数联系起来。交叉成功次数越多，变异次数减少，变异可以理解为系统与环境进行能量交换的方式，这样便构成了耗散结构，使种群的进化能够充分利用交叉和变异的优点，取得较为理想的效果。3.3群体空间的进化（1）生成规模大小为N 的初始种群。（2）通过obj （）函数计算种群中个体的适应度值，并按从大到小排序。（3）将一半优秀个体通过accept （）函数传递到信念空间。（4）通过influence （）函数接收信念空间中的最优个体，判断是否满足终止条件，若满足，程序结束，否则，执行下一步。（5）产生空间

14、大小30%的随机种群。（6）最优个体与最差个体的40%进行交叉操作，其余进行普通交叉操作。（7）进行变异操作，产生下一代种群。（8）转到（2）。3.4信念空间的进化信念空间接收群体空间的一半优秀个体后执行以下操作：（1）信念空间把通过accept （）函数接收到的优秀个体与原来的比较，保留迄今为止最好的一部分个体。（2）选择信念空间一部分个体进行耗散结构的遗传算法操作，并按一定规则逐步增大搜索空间，从而能充分利用优秀个体，使好的个体多次获得繁殖机会。（3）若搜索空间达到了信念空间大小，执行（4）；否则，执行（2）。（4）把最优个体通过influence （）函数传递到群体空间。3.5基于文化框

15、架的遗传算法群体空间引入随机种群来维持种群的多样性，可防止早熟收敛现象的发生，但是，不能保证算法的速度和效率；为了能快速找到最优个体，在信念空间中减小种群大小为群体空间的一半，充分开采至今为止优秀个体所包含的信息。由于优秀个体的相似性，采用耗散结构避免找到局部最优解，使交叉和变异这两个主要操作相互交换信息来达到一种有序状态，促进种群向前发展。更新优秀个体后再反馈到群体空间与大部分较差个体进行交叉操作来更新较差个体，提高算法的效率。在这种传递、比较、更新和反馈中快速找到最优解。算法的执行过程如图2所示。4实验结果及分析为了验证算法的有效性，本文选择了5个典型函数进行测张敏，邓新秀，葛斌：文化遗传

16、算法的研究及其在函数优化中的应用57Computer Engineering and Applications 计算机工程与应用2009，45（18）（上接34页）为了测试本文设计的体积计算方法的在不同复杂程度的三角网格模型下的性能，采取了具有不同数量级三角面片的三角网格模型进行了测试，测试结果如图5所示。测试结果表明本文设计的体积计算方法针对不同规模的三角网格模型均具有良好的性能。 5结论三角网格是最常用的网格模型，提出了一种直接在三角网格面片集合上进行模型体积计算的方法，并通过在水电工程施工三维模型的施工单元方量计算中的应用证实了该方法的快速有效性。进一步的研究将在本文工作的基础上，对基于

17、三角网格体积计算的网格局部特征信息提取、网格模型的快速检索等展开研究。参考文献：1Gotsman C ，Gumhold S ，Kobbelt L.Simplification and compressionof 3D meshesC/IskeA ，Quak E ，Floater 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.系统仿真学报，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尹习双，周宜红. 基于虚拟现实的水电工程施工动态可视化仿真研究J.系统仿真学报，2005（7）.图5不同规模三角网格模型的体积计算时间测试结果三角网格模型面片数量/万3025201510500.5151050100计算时间适应度函数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。本文采用二进制编码，实验中的参数设置为：群体空间种群大小：50；最大进化代数：1000；信念空间种群大小：25；交叉概率：0.85；个体长度：40；本文算法与基本遗传算法比较结果如表1所示。从表1可以看出，在给定解的精度要求下，算法的收敛速度（平均迭代代数

23、）得到成倍的提高，算法的优化效率优于基本遗传算法。在求解过程中，算法达到的最大适应度远远优于基本遗传算法的最大适应度，算法的精确度得到了大幅度的提高。因此，不论是优化效率还是优化效果，该算法均优于基本遗传算法。5结论针对遗传算法的不足之处，将遗传算法进行适当改进后融合到文化算法框架中作为群体空间和信念空间用于函数优化，算法性能由函数测试并进行了比较分析。实验结果表明，新算法能够提高效率和精确度，有一定的实用价值。参考文献：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