基于雁群启示的粒子群优化算法的几何约束求解

Geometric Constraint Solving Based on GeesePSO Optimization

几何约束是约束求解技术中最关键的问题之一.求解一个几何约束问题的最终目的是确定几何图形中每一个几何体的具体坐标位置.几何约束问题可以等价为求解非线性方程组问题.约束问题转化为一个优化问题.本文采用基于雁群启示的粒子群优化算法来求解该问题.该算法受雁群飞行特征启发,一方面将粒子排序,每个粒子跟随其前面那个较优粒子飞行,保持了多样性;另一方面使每个粒子利用更多其他粒子的有用信息,粒子之间的竞争被增强.两个方面的结合将平衡速度和精度之间的矛盾.实验表明,该方法可以提高几何约束求解的效率和收敛性.

Geometric constraint solving is a key issue in constraint solving technology. The ultimate goal of geometric constraint solving is to determine the geometry of the specific geometry of each coordinate position. Geometric constraint problem is equivalent to the problem of solving a set of nonlinear equations substantially. The constraint problem can be transformed to an optimization n problem. We can solve the problem with GeesePSO optimization. In this paper, an improved algorithm is proposed using the characteristics of the flight of geese for reference. The algorithm is inspired by the wild geese flying characteristics. The improved algorithm has superiority over PSO; for one thing, it keeps the population various by ordering all the particles and making each particle fly following its anterior particle; for another thing, it strengthens cooperation and competition between particles by making each particle share more useful information of the other particles. Combination of both to some extent, the algorithm searches balance the conflict between speed and accuracy. The experiment shows that it can improve the geometric constraint solving efficiency and possess better convergence property than the compared algorithms.