首页 | 供应信息 | 求购信息  | 下载系统 | 技术资讯 | 企业信息 | 产品信息 | 论文信息 | 展会信息 | 在线工具
作者: 发布时间:2013-08-21 来源: 繁体版
摘 要: Gilbert算法是求解最接近点对问题的一种算法,广泛应用于碰撞检测、数据分类、运动规划等领域。但是,Gilbert算法的最大缺点是在很多情况下,当它接近最优解时,收敛速度非常慢。在Gilbert算法的基础上提出

摘  要: Gilbert算法是求解最接近点对问题的一种算法,广泛应用于碰撞检测、数据分类、运动规划等领域。但是,Gilbert算法的最大缺点是在很多情况下,当它接近最优解时,收敛速度非常慢。在Gilbert算法的基础上提出一个新的迭代策略,可以减少算法的迭代次数,加快收敛速度。实验结果证明,改进后的算法求解速度和收敛速度快。aCS自动化在线网
关键词: Gilbert算法;NPA算法;碰撞检测;数据分类aCS自动化在线网

    Gilbert算法[1]是一种求解最接近点对算法,即求解凸包外指定点到一群点集组成的凸包的距离,广泛应用于机器人领域。Gilbert算法是一种迭代算法,属于梯度下降算法,具有很好的全局收敛性,易被计算机实现,而且适用几何的观点来分析。但是,Gilbert算法的缺点也很明显,特别是接近最优解时收敛过慢。aCS自动化在线网
    针对Gilbert算法的改进算法有MDM算法[2]、NPA算法[3]以及CHANG L[4]等人提出的改进算法。MDM算法利用具有消极影响的训练样本点改进更新策略,在迭代过程中,一旦发现迭代点的组合中具有消极影响的训练样本点,就直接在迭代点的线性组合中删除或是降低该点对目标函数的影响,并同时使得目标函数边缘下降。MDM算法解决了Gilbert算法接近最优解时收敛过慢的问题,但仍需要多次迭代完成计算。NPA算法结合了Gilbert算法和MDM算法的特点,选取三角形区域作为迭代点的搜索范围,扩大了迭代点的搜索范围,实验结果显示,它比MDM算法收敛更快,但NPA算法仍存在计算量很大的不足。参考文献[4]的研究证明了最接近点对问题的最优解一定出现在凸包顶点中两点组成的边上或者几点确定的面上,根据此结论,最优解一定落在凸包边界上。CHANG L等人据此提出了一种改进的Gilbert算法(下文简称CQW),当算法迭代到一定次数时,如果发现算法重复选取几个凸包顶点作为算法迭代选取的顶点,就直接计算凸包外指定点到这几点组成的平面或两点组成的线段的距离,它加快了Gilbert的收敛,但需要人工设置迭代次数,迭代次数的选取是一个难点。aCS自动化在线网
    针对上述算法计算量大的问题,本文分析了Gilbert收敛慢的原因,当新的迭代点越来越趋近于最优解时,它一直在最优解附近徘徊,不能快速到达凸包边界。本文通过实验发现,在迭代的过程中,一旦迭代点出现在凸包的边界上,Gilbert算法会快速收敛。据此,本文在Gilbert算法的基础上提出一种新的迭代策略,迭代过程中将Gilbert算法原有的梯度方向上的候选点与凸包边界上的候选点进行比对,选取离凸包外指定点更近的候选点作为新的迭代点,这样的迭代机制一有机会即将迭代点拉到凸包的边界上,有效避免了在凸包内部最优解附近不停徘徊迭代的情况发生,减少迭代次数,加快收敛速度。实验结果表明,本文改进后的算法与NPA算法相比,计算量小,问题的求解速度更快,与CQW算法相比,不需要人工设置迭代次数,更容易求出最优解。aCS自动化在线网
aCS自动化在线网
aCS自动化在线网
    aCS自动化在线网

 aCS自动化在线网


Gilbert算法研究及其改进
评论】【加入收藏夹】【 】【关闭
※ 相关信息
无相关信息
※ 其他信息
访问数: | 共有条评论
发表评论
用户名:
密码:
验证码: 看不清楚,点击刷新
匿名发表

 搜索新闻
[提交投稿]  [管理投稿]
 最新新闻
 热点新闻
数据加载中..

网站地图
Autooo.Net 版权所有
Copyright © 2007--2014 All rights reserved