采用线段和圆弧作逼近基元是数字曲线拟合中的一个难点。文中给出一种基于改进遗传算法的拟合方法。通过对点列进行二进制编码,以拟合段数较少和拟合误差较小为优化目标,变异概率和交叉概率自适应生成,并根据相关知识控制分界点间隙,所得最优解中值为1的基因对应数字曲线的分界点,对线段与圆弧相交和相切以及具有噪声等多种情况进行检测,可同时提取尖点和切点,还可得到逼近基元及其之间关系。较好地解决了用线段和圆弧拟合曲线问题。
维普资讯 doc.guandang.net
2期
张习文等: f遗传算缓的线段和匿孤为基元的曲线拟台基体为问题的满意解 .
1j 4
拟台点列 .实现方法很多 . 分为两类:是先扯取基元 z町
间的分界,即分割优先的方法;二是先抽取轮廓卜的基无 即恢复优先的方法 .界点是人类认知彤状的重要春可舒用来描述、别和匹配形状经过多年研究,经提出多砷 i只已 分界橙测方法:
GA提高染色体适应度和产生全局最优解主要是通过 遗传操作来实现用遗传算子为:常 a选择 .从种群中按某一择概率尸选择染色体选 染色体 .选择的概率与其适成度成正比.被 b交 _.将按交叉概率 P选择的两个染色
体进行交义 叉生戚两个新的染色体 .交叉是 GA的主要搜索手段 .单有 、
lJ曲率计算 1 量较小,侣抗噪性差
根据曲率 (角 )夹米提取分界 .算许
【)小披变换 .基于小波变换检测有,干扰能力 2] 抗
两点和均匀等多种交叉方式 c变异.将被选中的染色体的各个基因按变异概率 P
强.但计算较为复杂. ()模糊推理 .根据人对局部图形特怔的认知用模 3糊推理来检删角点. (优化方法 .基于遗传算法衷拟台曲线,只是进 4但 行线性拟台 .
进行变异,成新的染色体 .异是 GA跳出局部域寻求全生变 局蛀优解的主要手段 .
4采用线段和圆弧为基元的拟合算法 本文采用线段和圆弧作为逼近基元 .线段与圆弧相连对
曲线拟台可采用线段、弧和椭匮弧等多种基元 .圆从
采用的基元亮看曲线拟台方法可分为_种:二 ()线段 .采用多边形逼近果需要得到圆孤的表 1如达.还需对线段进行圆弧拟合 ()线段和圆弧n .先自适应光顺曲线切线方向 .后 2:然对其求导,中取出峰值点,到曲线尖点;用动态聚焦拟从得再台技术粗略定位切点 .后要精确漏整 .最 f)线段和椭圆孤 9先用折线来粗略逼近曲线 .后 3 然
和相切等情况进行研究.先对骨架象素进行跟踪,得到点列 设井有十点,为 P= f 1 . .记 ( )… P0—1 . ()P 1, )声 , (+ ) …
.
P( ),声(+ 1是声() }称, ) 的后一个, P“一1是 P ) ()
的前一个点.问题求解就是在点列中选出分界电.遗传算强 的预备步骤如 F . ()表示方案 . 1 分为分界点和连续两种,用二进采制编码 .当点 i分界点时,色体基因为 1否则为 0在曲为染; .
作精确分割 .最后将一些线段拟合成椭圆孤.
线拟台中,连续和较近 (本文取 l 5个象索)的两个分界点是
3遗传算法 ( n t g rtmsGA) Ge ei Aloi c h, 简介 Holn l d在 l7 a 5年首次提出 GA .过多年研究和应 9 经用, A吸引了大批的研究者, G已经推广到优化、
索和机器搜
不存在的 .稀疏化.变异和交叉时 .行稀疏处理.要在进 ( )适应函数.对染色体的每段进行直线和圆拟台。, 2。’取两个拟合误差中较小的一个误差作为该段的拟台误差设
染色体中所有段的拟合误差之和为 E r . r ()设为线段和圆弧的段数,为调整系数, 调整拟合误差和段数的作用 . 则染色体 i的适应函数为 ,“L — J E …
学习等诸多方面 .奠定了坚实的理论基础 .具有良好的应用前景 G是一种崭新的全局优化算法 .用生物遗传学观 A借 点 .现自然界中“竞天择、者生存”进化过程 .过选体物适的通择、叉和变异等作用机制,问题的解在竞争中得以改选 .交使
1
r() r i XS ̄’— n'
其中=0 5可根据需要进行修改 . ., ( )算法的控制参数和变量: 3
实现各个染色体的适应性提高,以求得问题的满意解
G把适者生存与结构化和随机化的信息交换结合在 A 一
染色体长度 L .点的总个数 ( )Ⅳ . 种群规模 .点总个数的一半 (/ ) N 2. 选择概率尸 .设染色体 J的选择概率为其适应度占
起,形成一种崭新的求解算法,同基于微分、枚举和随机等
传统优化方法相比 .要有 4个方面的不同:主 ( )直接使用问题解集编码 .不是解集本身 . 1而 ()从解组成的种群中搜索最优解,不是单个解 . 2而 ( 1使用适应度函数指导搜索, 3而不考虑它的数学特性 ( 1概率地使用三种遗传操作,不用确定的状态转移 4而 规则.
种群适应度总和的百分比,染色体 J择概率定义为则选 ,、) J 一 . I 1一
L .
Fi( ) t i
交叉概率 P .根据选择的两个染色体之间的差距而
确定 .差距越大 . 大{之 . 小 . G n 和尸越反尸越设 e (,) G n J是被选择的两个染色体 i J上的基因 ( 1…, e (,)和 f,
G具有多种运行方式,本的实现过程可概括为: A基 ( )随机韧始化种群 (){,。… .} 1 0一 z . .
( )对种群造代执行遗传操作, 2直到满足运行结束条件为止.算当
前种群 ()计 中每个染色体 .适应度 F t的 i (..用下述操作产生新的种群 . )应
L .色体之间的距离为 Ds=>:Gn一G n_ ) . )染 i le(, ) e, 7 一
1
则染色体 i J的交叉概率为和 1
选择把现有染色体选择到新一代种群中. 交叉重组两个染色体,生两个新的染色体 .产
P( )■—= J l 十e 变异概率尸 .尸 随适应度自动改变一当种群染色”.
变异.改变染色体某个基因,产生一个新的染色体.
体适应度趋于一致时,增加;尸反之,减小.尸设染色体 i 的适应度为 F t )种群的最大适应度为 F i(, …平均适应度
( )当满足运行结束条件时 . 3后代中适应度最高的染色

基于遗传算法的以线段和圆弧为基元的曲线拟合_理学_高等教育_教育专区。曲线拟合资料第14 卷第 2 期 2002 年 2 月 计算机辅助设计与图形学学报 JOU RNAL O ...
基于遗传算法的相切圆弧逼近非圆曲线算法_专业资料。利用数控机床对非圆曲线进行加工时,采用直线段或相交圆弧对曲线进行拟合加工,在节点处存在尖点,影响轮廓的光滑...
基于Matlab遗传算法工具箱的曲线拟合_计算机软件及应用_IT/计算机_专业资料。...本文利用 Matlab 遗传算法工具箱有效地进行了曲 线的拟合,其精度也很高,它为...
基于遗传算法的扫描线划图稿的拟合算法研究_专业资料。研究智能款式设计过程中的重要环节之一扫描线划图稿部件信息的提取问题,提出采用给定误差基于遗传算法的扫描线...
本文根据遗传算法和模拟退火算法各自的优缺点,提出将遗传算法和模拟退火算法相结合的方法用在曲线拟合上,在B样条曲线拟合过程中设计了新的适应度函数和遗传算子,...
本文使用1种改进的遗传算法,改变遗传规划算法中初始群体的产生方法,改变变异策略,加快群体进化。用此方法构造B样条曲线,使得拟合满足精度要求。本文使用1种改进的...
第 1 期 郑峰松等: 基于 M essay 遗传算法 B 样条闭曲 线拟合 27 遗传算法有较好的鲁棒性 ( 与初始输入参数无关) , 因此本文算法适用于智能曲线拟合...
基于遗传算法和最速下降法的B_zier曲线拟合_理学_...线拟合的遗传算法和最速下降法相结合的混合算法;最后...( = 1,2,… ) ——Bernstein 基 2009,30 (1)...
提出一种B样条闭曲线拟合的新方法——基于Messay遗传算法,通过种群中每个染色体的基因和基因个数的不断变化,自适应地调整参数序列、节点向量和控制顶点数目.实验...
闭合数字曲线的多项式递归拟合_文学研究_人文社科_专业资料。闭合数字曲线的...( 李蔡 #$ 张习文,佐,士杰等 $ 基于遗传算法的以线段和圆弧为基元的曲 ...
热门文档