论文部分内容阅读
概率最小生成树问题是对传统最小生成树问题中树的顶点附加一定的存在概率，从而形成的一类重要的约束最小生成树问题，它是一个典型的NP完全问题，同时，对它的求解是一个NP--hard问题。实际生活中的很多组合优化问题，例如，网络设计、超大规模集成电路的设计等等优化问题，都可以抽象为概率最小生成树问题，通过对概率最小生成树问题及其求解方法的研究，提出有效求解概率最小生成树问题的方法，可以很好地解决实际生活中的以上组合优化问题，所以对概率最小生成树问题的研究具有较大的理论意义和实用价值。
本文通过对概率最小生成树问题进行分析，采用基于行列式因子分解编码的遗传算法和并行遗传算法对它进行求解。研究工作如下：1)对基于行列式因子分解编码的遗传算法和并行遗传算法中涉及的问题进行了分析；2)在用基于行列式因子分解编码的遗传算法求解问题的过程中，给出了算法的行列式因子分解编码的有效性判断依据，并对非可行个体进行修正，从而保证算法更高效地求解问题；3)对以上遗传算法进行并行化，通过和消息传递并行编程模型MPI相结合，设计了一种粗粒度并行遗传算法对具体的概率最小生成树问题进行求解。
参照有关文献给出的按随机方式生成概率最小生成树问题的方法，通过设计随机生成器来产生若干个概率最小生成树问题，用本文所提的算法对上述问题进行测试，并将测试数据与现有文献中求解概率最小生成树问题的相关实验数据进行了比较，实验结果表明，相对已有文献给出的测试数据，由本文算法得到的测试数据，无论是最好解的精度，还是算法的多项性能指标，均有一定的优势。