基于小生境改进粒子群算法的几何约束求解  

Geometric constraint solving based on niche improved particle swarm optimization

作　　者：曹春红[1,2,3] 王利民[4] 赵大哲[3] 张斌[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110819 [2]占林大学符号计算与知识工程教育部重点实验室,长春130012 [3]东北大学医学影像计算教育部重点实验室,沈阳110819 [4]吉林大学计算机科学与技术学院,长春130012

出　　处：《仪器仪表学报》2012年第9期2125-2129,共5页Chinese Journal of Scientific Instrument

摘　　要：几何约束问题可以等价为求解非线性方程组问题。几何约束问题先被转化为一个优化问题。采用基于小生境改进粒子群优化算法来求解该优化问题。由于经典粒子群优化算法容易陷入局部最优,出现早熟现象。为此,基于小生境原理,提出一种小生境改进粒子群优化算法(niche improved particle swarm optimization,NIPSO)。该算法在进行速度和位置更新后,根据小生境数确定个体历史最好位置中的孤立点。然后对所有个体历史最好值差于孤立点值的粒子使用交叉和选择算子进行更新。实验表明,该方法可以提高几何约束求解的效率和收敛性。Geometric constraint problem can be equivalent to the problem of solving a set of nonlinear equations substantially. The constraint problem will be transformed into an optimization problem firstly. We can solve the problem with niche improved particle swarm optimization（NIPSO） algorithm. Classical particle swarm optimization algorithm is likely to be trapped into local minima as well as premature. A niche improved particle swarm optimization based on niche theory is developed. After the update of the particle velocity and position, the algorithm will determine the isolated points in the best location of the individual history according to the number of niche. Then all the best values of the individual history that are worse than the isolated point particles are updated using crossover and selection operators. Experiments show that this method can improve the efficiency and convergence of geometric constraint solving.

关 键 词：几何约束求解 粒子群优化算法 小生境 孤立点 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]