作　　者： ; ;

机构地区： 南京财经大学经济管理实验教学中心电子商务重点实验室

出　　处： 《电子学报》 2007年第8期1527-1532,共6页

摘　　要： 多边形近似是一种重要的曲线描述方法.研究用遗传算法求解平面数字曲线的多边形近似碰到的两个主要问题是不可行解难以处理和基本遗传算法局部搜索能力差.针对这两个问题,本文提出了一种组合拆分与合并技术的混合遗传算法(SMGA).它将两种经典算法—拆分技术与合并技术引入到对染色体的修复过程.采用这种方法,一个不可行解不仅能得到快速的修复,而且还能被推进到解空间中一个局部较优的位置.它的另外一个优点是:不同于已有的遗传算法,只能解决一类多边形近似问题,SMGA是一种能求解两类多边形近似问题的通用算法.实验结果表明:本文提出的算法比其他同类算法性能更优越. Polygonal approximation of digital curve is an important curve representation method. The main problems existing ingenetic algorithm based methods are the difficulty of coping with the infeasible solutions and the poor local search ability. In this paper, we propose a hybrid genetic algorithm combined with split and merge technique （SMGA） for polygonal approximation. Its main idea is that two classical methods-split and merge techniques are used to repair the infeasible solutions. In this method, an infeasible solution can not only be repaired rapidly, but also be pushed to a local optimal location in the solution space. Another advantage of SMGA is that it can solve two types of polygonal approximation problems. The experimental results demonstrate that SMGA is robust and outperforms the other genetic algorithm based methods.

关 键 词： 曲线描述 多边形近似 拆分与合并 遗传算法 染色体修复

领　　域： [自动化与计算机技术] [自动化与计算机技术]