论文部分内容阅读
对高效并行算法的研究是当前高性能计算领域中的一个重要课题。该文主要研究了粗粒度并行遗传算法和并行雅可比正交矩阵分解算法。
主要成果包括:
分析了粗粒度并行遗传算法的子群体连接拓扑对选择压力的影响。采用度和直径这两个参数来描述子群体的连接拓扑。利用当前最优个体在繁衍组中样本数的数学期望来衡量选择压力的大小。对单向环,双向环和带弦环这三种对称连接拓扑进行了详细的量化分析,得出了对称连接拓扑的度越大,则相应并行遗传算法的选择压力越大的结论。提出了一种自适应变拓扑并行遗传算法,有效的协调并行遗传算法的开拓与探索。算法将决定接受迁入个体数量的权力下放给各子群体,每个子群体都根据自身连续未发生正向跃变的进化代数量决定在当前进化代内是接受还是不接受迁入个体,以及接受迁入个体的数量。根据该文的自适应策略,在进化初期各子群体在选择压力较小的环境中,将以大的概率收敛到不同的“有希望的”区域,完成对搜索空间的充分探索。而在后期各子群体在选择压力较大的环境中,将对其占据的区域进行充分的开拓。在三个实际问题:计算机网络设备选型问题,无线网络基站定位问题和高斯信号的盲分离问题中的应用表明,自适应变拓扑并行遗传算法的性能优于固定拓扑的并行遗传算法。
分析了并行雅可比正交矩阵分解算法的两类主要排序策略:round-robin排序类策略和odd-even排序类策略。分析结果表明环排序能够使并行的雅可比正交矩阵分解算法在某些集群系统上发挥出最高的效率。设计了基于环排序的并行单边雅可比厄密矩阵特征值分解算法,复矩阵奇异值分解算法和复方阵Schur分解算法。这三种并行正交矩阵分解算法都采用基于环排序的任务划分及交互方式,并拥有相同的基本代数操作——复Givens旋转,它们的加速比和可扩展性都得到了详细的分析。在该文之前,方阵的并行单边雅可比Schur分解算法还未有文献报导。最后,用这三种并行单边雅可比正交矩阵分解算法完成了均匀线性阵列的波达方向角估计。大量算例验证了该文的理论分析结果以及并行算法的优势。