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

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (2): 86-86.

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

张冬梅,姜鹏飞,何兴恒,杨捷

中国地质大学（武汉）计算机学院

收稿日期:2006-01-19 修回日期:1900-01-01 出版日期:2007-01-11 发布日期:2007-01-11
通讯作者: 张冬梅 cugzdm cugzdm

Minimum Weight Triangulation Based on the Parallel Genetic Algorithm

,,,

中国地质大学（武汉）计算机学院

Received:2006-01-19 Revised:1900-01-01 Online:2007-01-11 Published:2007-01-11

摘要/Abstract

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

关键词: 最小权三角划分, PVM, 并行遗传算法

Abstract: The triangulation of a set of points in the Euclidean plane has a wide range of applications in Computer Graphics, 3-D Visualization and so on. In most cases, the optimum triangulation is required. However, this kind of problem is conjectured to be a NP complete problem. In this paper, we try to obtain the approximate global optimum triangulation with Parallel Genetic Algorithm based on PVM. Large-scale experiments have been done to systematically test the effect of some important parallel control parameters, which include the migration generations and the average load for each processor, on the performance of the algorithm. And the experimental results show that the parallel genetic algorithm is simple and stable, and is efficient of finding an optimum solution with a high possibility.

Key words: MWT (Minimum Weight Triangulation), PVM, Parallel Genetic Algorithm

张冬梅,姜鹏飞,何兴恒,杨捷. 基于PVM的最小权三角划分并行遗传算法研究[J]. 计算机工程与应用, 2007, 43(2): 86-86.

,,,. Minimum Weight Triangulation Based on the Parallel Genetic Algorithm[J]. Computer Engineering and Applications, 2007, 43(2): 86-86.

[1]	沈焕学1，2，郑凯1，2，刘垚1，2，王肃1，2，刘艳1，2，赵瑞祥1，2，周谦豪3. 申威众核处理器的并行NSGA-II算法[J]. 计算机工程与应用, 2018, 54(17): 35-40.
[2]	冯志强1，许国军2，邓磊2，夏晓燕2，贾振红1，覃锡忠1. 基于改进并行遗传算法的蜂窝网络信道分配[J]. 计算机工程与应用, 2014, 50(3): 89-92.
[3]	张学华，李尧. 模拟跨导滤波器多目标并行进化的设计[J]. 计算机工程与应用, 2013, 49(18): 204-207.
[4]	李飞¹，刘成¹，赵辉². 不确定信息下QoS多播路由问题研究[J]. 计算机工程与应用, 2009, 45(26): 104-106.
[5]	冯国壁,赵庆祯. 并行遗传算法下的农业业务外包伙伴选择[J]. 计算机工程与应用, 2009, 45(1): 217-219.
[6]	何桂霞¹,高家全¹,王雨顺². 特殊工艺约束并行多机双目标调度问题的研究[J]. 计算机工程与应用, 2008, 44(32): 197-199.
[7]	殷新春^1,2,仇亮¹. 基于主从式并行遗传算法的S盒优化算法[J]. 计算机工程与应用, 2008, 44(24): 112-114.
[8]	高家全¹,赵端阳¹,何桂霞¹,王雨顺². 解特殊工艺约束拖后调度问题的并行遗传算法[J]. 计算机工程与应用, 2007, 43(27): 184-186.
[9]	高家全,王雨顺,何桂霞. 解不同交货期并行机调度问题的并行遗传算法[J]. 计算机工程与应用, 2007, 43(2): 15-15.
[10]	高家全,王雨顺. 解并行多机提前/拖后调度问题的并行遗传算法 [J]. 计算机工程与应用, 2006, 42(20): 10-.