遗传算法用于曲线的误差约束多边形近似

提出了一种求解曲线的误差约束多边形近似问题的遗传算法.其主要思想是:1)采用变长染色体编码机制,以减少存储空间和计算时间的消耗;2)针对问题的特点,提出了一种新的杂交算子——基因消去杂交,以尽可能地消去染色体上的冗余基因,从而提高算法的寻优能力;3)采用染色体修复策略处理遗传操作产生的不可行解,该策略通过迭代地向染色体追加有价值的候选基因来实现染色体的修复,并提出一种对染色体的候选基因进行评估的机制.通过实验评估并与其他遗传算法进行比较,结果表明,提出的算法性能更优越.

A Genetic Algorithm for Error-Bounded Polygonal Approximation of Curves

Polygonal approximation of digital curve is a hot topic in image processing and pattern recognition and has found wide applications. Genetic algorithms (GA) have been used to solve polygonal approximation problems recently. However, the existing GA-based methods have the following disadvantages which limit their performance. Firstly, the length of chromosome is very long because of adopting fixed-length chromosome encoding; secondly, the local search ability of the traditional genetic operator is poor; finally, the penalty function method is adopted to cope with infeasible solution, and however, an appropriate penalty function is very difficult to determine. To overcome these problems, a novel GA-based method is proposed for error-bounded polygonal approximation. Its main ideas are: 1) a variable-length chromosome encoding scheme is adopted to reduce the memory storage and computational time; 2) a novel genetic operator named gene-removing crossover is developed for removing the redundant genes; 3) a chromosome-repairing scheme is proposed to cope with the infeasible solutions by iteratively adding the valuable candidate genes to the chromosome and an gene evaluating scheme is developed for this task. The experimental results demonstrate that the proposed method outperforms the existing GA-based method. The proposed method is also applied to the polygonal approximation of the satellite image of lake and obtains a better approximation result.