改进的遗传算法用于工业测量数据处理.doc

改进的遗传算法用于工业测量数据处理摘要：从遗传算法的两个缺陷入手，在几个方面对其进行改进，并且用MATLAB语言编程实现了改进后的算法。文章用一个工程实例，探讨了将改进后的遗传算法应用于工业测量和逆向工程领域的可行性，并且通过比较发现改进后的算法在全局收敛以及收敛速度方面都有了较大的改善，说明了文章所作的改进是有效的。文章提出的遗传算法的改进和应用的探讨具有较好的实用价值。关键词：遗传算法改进全局收敛性收敛速度工业测量数据处理马鞍面（双曲抛物面）ApplicationofImprovedGAinIndustrialSurveyingDataProcessingAbstract:Viewingfromtwodefectsoftraditionalsimplegeneticalgorithm,thispapermodifiesitfromseveralaspects,andrealizestheimprovedalgorithmusingMATLABlanguageprogramming.Usinganengineeringexample,thispaperdiscussesthefeasibilityofapplyingimprovedGAintoindustrialsurveyingandreverseengineering.Throughcomparison,thispaperfindsoutthattheimprovedGAhasgoodbettermentinglobalconvergenceandconvergencerate,whichreflectsthattheimprovementiseffective.TheimprovementofGAanditsapplicationhasgoodpracticability.Keywords:geneticalgorithm,improvement,globalconvergence,convergencerate,industrialsurveying,dataprocessing,hyperbolicparaboloid1引言在工业测量以及逆向工程中，由于实物的形状通常有严格的数学公式描述，通过采集其表面数据点的三维坐标，可以拟合出实物表面在空间三维坐标系中的几何方程，这对于发现实物的整体变形以及生成模型设计CAD图纸是至关重要的。对于平面拟合问题，已经得到很好的解决，但对于复杂曲面，即便是简单的二次曲面的最小二乘拟合的研究也相对较少，而且已有的拟合算法存在方程求解问难、有奇异值和算法不稳定等问题1，因此一种好的全局优化算法就显得极其必要。遗传算法(GeneticAlgorithm，简称GA)是由美国Michigan大学的JohnH.Holland教授于1975年在他的著作AdaptationinNaturalandArtificialSystems中根据C.R.Darwin的生物进化论和G.Mendel的遗传变异理论提出的一种基于种群搜索的优化算法。其思想是随机产生初始种群,通过选择(Reproduction)、交叉(Crossover)和变异(Mutation)等遗传算子的共同作用使种群不断进化,最终得到最优解2。与其他优化方法相比，遗传算法以单一字符串的形式描述所研究的问题，只需利用适应度函数进行优化计算,而不需要函数导数等其他信息，特别适合解决其他学科技术无法解决或难以解投稿日期：2008-01-12基金项目国家自然科学基金（40674010）；“十一五”科技支撑项目（2006BAC01B02-02-02,05）作者简介：潘国荣：教授、博士生导师，主要研究方向为精密工程测量、工业测量与测量数据处理。Email:pgr2163.com决的复杂和非线性问题，是继专家系统、人工神经网络之后又一受人青睐的人工智能学科，一直是研究的一个热点，被广泛地应用于组合优化、机器学习、自适应控制、规划设计、智能机器系统、智能制造系统、系统工程，人工智能、人工生命等领域，是21世纪智能计算中的关键技术之一3。习惯上将JohnH.Holland提出的遗传算法称为简单遗传算法(SimpleGeneticAlgorithm,简称SGA)。和其它优化方法一样，由于全局性的要求，简单遗传算法作为一种通用的自适应随机搜索算法，还存在着早熟收敛(过早收敛于局部最优值)和收敛速度慢这两个缺陷，而且比较难克服,这给遗传算法的应用带来了很大的不便。遗传算法的改进出现早熟往往是由于种群中出现了某些超级个体，随着模拟生物演化过程的进行，这些个体的基因物质很快占据种群的统治地位，导致种群中由于缺乏新鲜的基因物质而不能找到全局最优值；另一个主要原因是由于遗传算法中选择及杂交变异等算子的作用，使得一些优秀的基因片段过早丢失，从而限制了搜索范围，使得搜索只能在局部范围内找到最优值，而不能得到满意的全局最优值4。Whitley认为，遗传算法中最重要的两个因素就是“种群多样性”和“选择压力”，而选择压力过大是导致早熟收敛的一个重要原因。过大的选择压力虽然可以加快算法的收敛速度，却会使种群中适应度不利于问题的求解的个体迅速“死亡”，种群的多样性遭到破坏，使得算法搜索空间减小，进而导致算法错误地收敛到局部最优值。降低选择压力虽然可以增大算法搜索到全局最优值的概率，但却会降低搜索效率，使算法的收敛速度变慢。为了使算法具有良好的性能，必须在提高选择压力和保持种群多样性之间达到某种平衡5。为提高遗传算法的搜索效率并保证得到问题的最优解，从以下几个方面对简单遗传算法进行改进：2.1初始种群产生在遗传算法中，采用实数编码策略比二进制编码策略具有精度高、搜索范围大、表达自然直观等优点。如此，能克服二进制编码所存在的诸多缺点，如不易求解高精度问题、不便于反应所求问题的特定知识及无法借鉴一些经典优化算法的宝贵经验等。2.2个体适应度计算计算适应度，需先构造适应度函数。合理的适应度函数能引导搜索朝最优化方向前行。本文的适应度函数是基于顺序的基础，其特点是个体被选择的概率与目标函数的具体值无关，仅与顺序有关。构造方法是先将种群中所有个体按目标函数值的好坏进行排序，设参数(0,1)，定义基于顺序的适应度函数为：1)1()(iiXevali=1,2,m(1)式中，iX为种群个体按优劣排序后的第i个个体。一般在0.010.3之间取值。2.3选择与交叉放弃赌轮选择，避免早期的高适应度个体迅速占据种群和后期的种群中因个体的适应度相差不大而导致种群停止进化。此处采用基于种群的按个体适应度大小排序的选择算法代替赌轮选择方法，其过程伪码描述如下：fitsort()将种群中的个体按适应度大小进行排序；while(种群还没有扫描完)do排在最前面的个体复制两份；排在中间的个体复制一份；排在后面的个体不复制；在不破坏种群基因多样性的前提下加快算法的进化速度。交叉率Pc按照公式(2)进行自适应调整：aveaveaveffkffffffkPcmaxmax21(2)式中，fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f为要交叉的两个个体中较大的适应值。此处，只要设定k1，k2（在0，1取值）的值，Pc即可进行自适应调整。2.4个体子代的产生在选择出父本和母本后，按照交叉方法（单点、多点、一致交叉）进行n次交叉，产生2n个个体，再从这2n个个体中选出最优的两个个体加入到新的种群中。如此，既保留了父本和母本的基因，又在进化的过程中种群中个体的平均性能。2.5变异在遗传算法中，如采用固定的变异概率Pm，则当Pm取值很小时，变异算子对群体不会产生影响，不利于新的基因的引入；而当Pm取值很大时，有可能破坏群体中的优良基因，使得算法收敛速度变慢甚至不收敛。此处，本文采用动态确定变异概率的方法，该方法既可防止优良基因因为变异而遭破坏，又可在陷入局部最优解时引入新的基因，该方法的伪码描述如下：if个体的适应度>平均适应度thenPm取值很小或为0；elsePm取值相对很大；endif如此，使得种群中好的基因不被破坏，既有利于不良基因的去除，又有利于新的基因的引入，从而可以很大程度的提高遗传算法的性能。具体的自适应调整的公式为：aveaveaveffkffffffkPm43maxmax(3)式中，fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f为要变异个体的适应度值。此处，只要设定k3，k4（在0，1取值）的值，Pm即可进行自适应调整2.6种群的进化与进化终止条件将初始种群和产生的子代种群放在一起，形成新的种群，然后计算新的种群各个体的适应度，将适应度排在前面的m个个体保留，将适应度排在后面m个个体淘汰，这样种群便得到了进化。每进化一次计算一下各个个体的目标函数值，当相邻两次进化平均目标函数之差小于等于某一给定精度时，即满足如下条件：)()1(ttXFXF(4)式中，)1(tXF为第t+1次进化后种群的平均目标函数值，)(tXF为第t次进化后种群的平均目标函数值，此时，可终止进化。2.8遗传算法流程及编程实现遗传算法流程的伪码表示为：ProcedureGeneticAlgorithm；begink=0；初始化P(k)；计算P(k)的适应值；while(不满足停止准则)dobegink=k+1；从P(k-1)中选择P(k)；复制算子重组P(k)；杂交和变异算子计算P(k)的适应值；endendend作者采用MATLAB编程语言，实现了本文提出的改进遗传算法的程序包6。为了证明其有效性和探讨其用于工业测量和逆向工程领域求取复杂模型参数的有效性，采用了一个钢结构部件表面方程拟合的工程实例来说明问题。改进遗传算法用于工业测量数据处理某钢结构工业构件的表面为马鞍面（双曲抛物面），用工业测量的手段测得了其表面数十个点的坐标，标记为(Xi,Yi,Zi)。由于工业测量系统采用的是与该构件相一致的坐标系统，故无须进行旋转平移等操作。得到的测量点临近点相连接得到如图1所示的图形。图1采样点分布图Fig.1Distributionmapofsamplingpoints由空间立体几何的知识可知，马鞍面（双曲抛物面）的标准方程为：)0(222qpzqypx(5)运算采用的电脑配置为：Intel®CPU双核T25002.00GHz，1.00GB内存，80GBHITACHI硬盘，ATIMobilityRadeonX1400显卡，显存128M。分别采用本文的改进遗传算法(ImprovedGA)以及传统简单遗传算法(SGA)进行了多次运算。由于遗传算法的特性，每一次计算求得的参数值均在最后数位上略有差异，本文中采用计算得到的各项指标的平均值，对两种方法所得结果进行比较，并且将计算得到的曲面参数值同设计值（p0=1.3,q0=1.6）进行比较，将比较结果列举如表1所示。表1曲面拟合结果比较Tab.1Comparisonofsurfacefittingresults采用方法平均遗传代数平均计算时间(s)有无陷入局部极小参数估值变化比率（%）平均RMSE()pqp/pq/qSGA>50>40有1.32021.58361.6-1.0>8ImprovedGA<30<3无1.31741.58671.30.8<4同设计的钢结构构件表面几何参数p0、q0进行比较的结果可知，p和q都发生了一定的变化，超过了3的相对误差限值，分析认为该钢结构部件在长期的使用过程中发生了变形。采用改进遗传算法拟合得到的双曲抛物面图形如图2所示：图2拟合结果Fig.2Fittingresult结语本文针对遗传算法的两个缺陷从几个方面着手进行了改进，并且用一个钢结构工业构件表面检测的工程实例说明了改进算法的有效性和探索其应用于工业测量和逆向工程的可行性。通过文中的实例和比较结果发现，改进后的遗传算法在全局收敛性和收敛速度方面都有了很大的改善，并且快速准确有效地求得复杂结构物体数学描述方程的参数，由此可以得出结论，改进后的遗传算法具有很好的优势，并且完全可以应用于工业测量和逆向工程领域。参考文献:1顾步云，周来水，刘胜兰，陈涛.逆向工程中二次曲面拟合方法的研究J.南京：机械制造与研究，2004,33(1)：11-14.1GuBuyun,ZhouLaishui,LiuShenglan,ChenTao.StudyonalgorithmofquadricsurfacefittinginreverseengineeringJ.Nanjing:MachineBuilding&Automation,2004,33(1):11-14.2HollandJ.AdaptationinnaturalandartificialsystemsM.UniversityofMichganPress,1975.3王福林，王吉权，吴昌友，吴秋峰.实数遗传算法的改进研究J.鞍山：生物数学学报，2006，21（1）：153-158.3WangFulin,WangJiquan,WuChangyou,WuQiufeng.Theimprovedresearchonacturalnumbergeneticalgorithms.Anshan:JournalofBiomathematics,2006，21(1):153-158.4黄绪明.一类改进的遗传算法J.长沙：长沙大学学报，2005，19（5）:1-4.4HuangXuming.Akindofimprovedhereditaryalgorithm.Changsha,JournalofChangshaUniversity,2005,19(5):1-4.5WhitleyD.Thegeneticalgorithmandselectionpressure:whyrank-basedallocationreproductiontrialsisbestA.InSchafferJ,Proceedingofthe3rdinternationalconferenceongeneticalgorithmC.LosAltos:MorganKaufmannpublishers,1989.6雷英杰，张善文，李续武，周创明.MATLAB遗传算法工具箱及应用M.西安：西安电子科技大学出版社，2005.6LeiYingjie,ZhangShanwen,LiXuwu,ZhouChuangming.MATLABgeneticalgorithmtoolboxandapplicationM.Xian:XidianUnversityPress,2005.