A Very Fast Converge Method for Geometric Constraint Solving

摘要

This paper introduces a modified PSO, Gradient Particle Swarm Optimizer (GPSO), for geometric constraint solving. GPSO combines the merits of global search of the PSO and the sheer convergence capacity of gradient algorithm, the most prominent iterative method for linear equations. GPSO uses PSO to search the area where the best solution may exist in the whole space, and then performs fine searching. When the algorithm approaches to the best solution and the search speed is too slow, we can change to the effective search strategy - gradient algorithm in order to enhance the ability of the particle swarm optimization on fine searching. By using the gradient algorithm, GPSO has shown remarkable performance against the prematurely convergence situation. We apply this new algorithm into the geometric constraint solving. The detailed performance analysis of this new approach has been done as well in terms of program execution time, relative speed up and efficiency. Our result and comparison with PSO show that GPSO is highly competitive with conventional PSO.