最小生成树问题是一类经典的网络优化问题。大量研究表明，最小生成树结构是通信网络设计的最优拓扑。生成树在大多数网络设计和分析问题中扮演着重要角色，然而，实际的网络优化问题通常需要满足附加的约束，形成约束最小生成树问题。二次最小生成树(q-MST)问题是在最小生成树问题中附加了边的交互费用的一类约束最小生成树问题，是一类典型的NP完全问题。在实际生活中的很多组合优化问题，例如，通信网络设计、超大规模集成电路的设计等优化问题，都可以转化为二次最小生成树问题，所以对二次最小生成树问题的研究具有较大的理论意义和实用价值。　　 Probabilistic Memetic Algorithm(PMA)是在memetic算法的基础上，通过管理每个个体的学习强度来平衡进化和个体学习。本文通过对q-MST问题和PMA进行分析、研究，采用基于一种新的进化算法PMA对二次最小生成树问题进行求解，将PMA首次应用到q-MST问题中。本文首先对采用进化算法求解二次最小生成树问题的现有文献进行学习和分析，发现算法中的编码、进化算子等关键技术还可以通过改进得到更好的解；然后根据二次最小生成树问题设计出局部搜索算子，并借鉴Jaccard系数推导出在非欧几里得空间下个体间距离的计算方法，进而设计出基于PMA的二次最小生成树问题的步骤和求解过程；最后设计局部加速算子和全局优化算子，对本文设计的PMA进行优化。　　 本文参照有关文献给出的按随机方式生成二次最小生成树问题的方法，通过设计随机生成器来产生若干个二次最小生成树问题的测试用例。使用本文所设计的算法对上述用例分别进行10次随机测试，并和遗传算法的数据进行比较。实验结果表明：PMA中得到的解明显要优于遗传算法得到的解，并验证了本文设计的距离计算方法、局部搜索算子、局部加速算子和全局优化算子在算法中的有效性。