求自由曲面间最短距离的对称调与遗传算法.pdfVIP

160 任红民等：求自由曲面间最短距离的对称调和遗传算法 求自由曲面间最短距离的对称调和遗传算法水 任红民1吴庆标2毕惟红2 (1杭州广播电视大学信息工程系，杭州310012；2浙江大学数学系科学与工程计算研究所，杭州310028) 摘要：如何快速有效地求取自由曲面间最短距离一直是CAD／CAM领域一个重要的研究课题。由于自由曲面的不 规则性，这也是一个难题。该文基于自由曲面的特性。提出了求自由曲面间最短距离的对称调和遗传算法。算法根 据遗传进程中各个个体适应值的变化情况来有选择性地投放对称调和个体，使种群的多样性得到了较好的保持，从 而有效地防止了早熟现象的出现。通过对双三次B6zier曲面间最短距离的模拟计算与分析，表明算法效果显著。 关键词：自由曲面；堆短距离；遗传算法；对称调和个体；全局优化 做可以有效地防止等位基因的缺损。该文基于自由 1引言 曲面的特性，提出了求自由曲面间最短距离的对称 如何快速有效地求取自由曲面间最短距离一直 调和遗传算法。算法根据遗传进程中各个个体适应 值的变化情况来有选择性地投放对称调和个体，使 是CAD／CAM和数控技术领域一个重要的研究课 题。由于自由曲面的不规则性，这也是一个难题。 种群的多样性得到了较好的保持，从而也可以有效 遗传算法由Holland等人创立以来，随着计算机技 术的迅猛发展，已被广泛用于优化、系统建模、自 间的模拟计算与分析，表明算法效果显著。 动程序设计、金融系统等许多领域，并己取得了许 2对称调和遗传算法 多非常有效、实用的结果“。6J。遗传算法因其具有独 有的特性，采用选择、交叉和变异等策略，获取的 解为全局最优解，而且无需计算函数的导数，是一 种只考虑输入与输出关系的黑箱方法，适用于处理 各种复杂问题[2-5l。遗传算法一般由编码机制、适应的距离为 值函数、遗传算子和控制参数等四部分组成，是求 ds爿‘‘“1，wlJ一吃忡2，w2)l 解自由曲面间最短距离十分有效的方法。文献【7】利 为了求得两曲面间的最短距离，需要求取上式 用两曲面间极值距离处两点法矢量共线这一特性来 定义的距离函数的最小值。该文研究利用遗传算法 求解最短距离，提出了一种有效的算法，但该算法 来求解这一问题。而在利用遗传算法求解问题时， 仅适合于两自由曲面之间的距离函数为单峰函数。 一般求目标函数的晟大值，因此需将上式做一个转 对于多峰函数，则得出的解可能是局部最优，而不 换，变为求解如下最大值问题 是全局最优。文献【8】提出了一种改进的遗传算法， Max d=CI。，一dJ 主要引入了两个特殊个体，计算效率和可靠性得到 其中C一为足够大的正数，以保证d为正。 了较大的改善。而对于自由曲面，特性点决定着自 为了求得最优解，首先对问题中的各参数编码。 由曲面的形状，如何利用其固有特性，并在遗传算 由上式可知，目标函数有％，w1，％。w，四个参数， 法中引入体现这些特性的特殊个体是值得考虑的论 该文采用二进制分别对各参数编码，每个参数的编 题。文献[9]基于自由曲面的特性，在遗传算法中引