基于PVM的最小权三角划分并行遗传算法研究

摘要

平面点集的三角划分在计算机图形学,三维可视化等领域具有广泛地应用,在许多应用中需要提供形状最优的三角划分.但该类问题推测属于NP完全问题.为了快速有效地求解最小权三角划分(MWT)问题,提出了一种基于PVM的并行遗传算法来近似获取全局最优解,并系统地测试算法中一些重要的并行控制参数,包括迁移代数和节点平均负载对算法性能的影响.实验结果表明,该方法简单,可靠,大大缩短了优化过程的时间,提高获取全局最优解的概率.