图的Steiner最小树问题是经典的组合优化问题,在通信网络和电路设计等领域有广泛应用。该问题是一个NP难题,虽然有一些精确算法,但是随着网络规模的增大,这些算法的运行时间呈指数增长。为了能够在多项式时间内得到最优解或者近似最优解,寻找有效的启发式算法就显得尤为重要。本文对遗传算法和传统的启发式算法进行了改进,主要工作如下:1.针对基本遗传算法采用自适应规则,引入模拟退火思想,提出了一种解决Steiner最小树问题的混合遗传算法并进行仿真实验。实验结果表明:与基本遗传算法相比,改进的混合遗传算法能够加快收敛速度,减少迭代次数,使得到的解更稳定。2.分析已有典型启发式算法,提出了一种基于加权节点的Steiner树启发式算法。该算法根据正则点对间的最短路径、节点的度数、与正则点连接的次数等计算出节点的权值,然后根据权值对最短路径的费用进行修正,通过修正费用最短路径将正则点添加到多播树中,从而实现更多链路的共享,降低整棵树的费用。3.为了模拟真实的通信网络来测试算法的性能,本文对Waxman算法进行改进,设计了一种逼近现实网络特性的随机网络生成算法。用该算法生成不同规模的仿真网络,然后用启发式算法对仿真网络进行求解,结果表明基于加权节点的启发式算法是一个性能较好的算法。