论文部分内容阅读
提出了一种解决平面点集最小权三角划分的新方法——最小权三角划分进化算法。针对平面点集最小权三角划分问题的特点，提出了新的交叉算子和变异算子，即多边形交叉算子与三角形变异算子。从而保证了经交叉与变异操作后得到的后代仍为合理的三角划分，加快了算法的收敛速度。研究了进化算法的几个主要参数（如：解群规模、交叉概率、变异概率及自适应系数）对算法性能及收敛性的影响，并给出了影响曲线。计算结果表明，新算法能得到比贪心算法更优的结果。
A new method to solve the least weighted triangulation of plane point set - the least weighted triangulation evolutionary algorithm is proposed. Aiming at the characteristics of the least weighted trigonometric partition of plane points set, a new crossover operator and mutation operator are proposed, that is, polygon crossover operator and triangle mutation operator. Thus ensuring that the offspring obtained after the crossover and mutation operation is still a reasonable triangular partition and accelerating the convergence speed of the algorithm. The influence of several main parameters of evolutionary algorithm (such as solution group size, crossover probability, mutation probability and adaptive coefficient) on the performance and convergence of the algorithm is studied and the influence curve is given. The results show that the new algorithm can get better results than the greedy algorithm.