进化算法在诸多领域内有着广泛的应用.尤其在计算科学中,一些难解的优化问题,例如NP-完全问题和多目标决策问题,采用传统优化方法往往不能有效求解.首先,该文提出一种求解带度约束最小生成树问题的进化算法.该问题是NP-完全问题.算法采用PRüfer编码表示问题的解,为了增强算法的搜索能力,长年累月加紧设计了两个新的遗传算子参与进化,算子避免了产生不可行解.此外,设计了两个局部搜索算子和算法相结合来进一步提高解的质量.因此,算法表现出较强的搜索能力.数值实验表明算法适用于求解该问题,理论分析表明算法以概率1收敛到全局最优解;其次,研究了多目标决策的最小生成树问题.算法仍然采用PRüfer编码表示问题的解,设计了两个不必考虑度约束的遗传算子.数值实验表明算法非常有效,理论分析表明算法以概率1收敛到全局最优解.