基于复合粒子群算法的几何约束求解技术研究

The Research Based on the Composite Particle Swarm Optimization Algorithm in the Geometric Constraint Solving

在将几何约束问题的约束方程组转化为优化模型的时候,需要找到一种方法来跳出局部最优解,进而找到全局最优解。为了兼顾算法的快速性和全局性,几何约束求解时,考虑使用复合粒子群算法。这种粒子群算法是一种基于群智能方法的演化计算技术,不仅在所有的进化算法中都包括控制其自身特性的启发式参数,而且这些参数通常是与特定的问题相关,并可由用户自己定义。虽然合适的参数选择需要用户丰富的经验和对研究问题所提供信息的正确判断,更重要的是,这些启发式参数会影响到算法的收敛特性,但是即便是很有经验的用户也可能选择不恰当的参数,从而使问题得不到有效地解决,这就越来越需要对这些参数进行研究。为此可将将粒子群算法中的控制参数的选取作为一个优化问题,以便用常规遗传算法来控制粒子群算法中的启发式参数,即形成了复合粒子群优化算法,通过把复合粒子群算法成功地应用到几何约束求解技术的实验表明,该方法可以在很短的时间内找到最优解。

When transferring a geometric constraint equation group into an optimization model, we need a method to jump out of the local beat solution so that we can find a best global solution. Considering the speed and global capability, we adopt a composite particle group optimization algorithm. Particle swarm optimization algorithm is a kind of evolution computation technology based on group intelligence. In all evolution computations heuristic function should be included to control its own characteristic. These parameters are usually correlated with a specific problem and are defined by the users. Suitable parameter choice needs user＇ s abundant experience and correct judgment on the information offered by the problem. More important thing is that these heuristic parameters will influence the convergence characteristic of the algorithm. Because of this even experienced users may choose an inappropriate parameter and make the problem unable to reach an effective solution. Some research on these parameters need to be carried on more and more. Here we choose the controlling parameters as an optimization solution to the particle swarm algorithm. Thus we can control the heuristic function in the PSO using the ordinal genetic algorithm and propose the composite particle swarm optimization algorithm. Finally we use this algorithm to solve the geometric constraint successfully. The experiment shows that the algorithm can find the best solution in a short time.