大多数组合优化问题都是NP完全问题，这类问题很难找到多项式时间的最优化算法，也就是说其算法的时间花费通常随着问题规模的增大呈指数增长。然而进化算法在求解组合最优化问题时，尽管它不能保证在多项式时间内找到NP完全问题的最优解，但是常常能找到组合最优化问题很好的次优解，数值实验结果表明进化算法在解的质量和执行效果上都优于传统的启发式算法。所以进化算法以及其他智能算法对组合最优化问题的解决具有十分重要的意义。 首先，提出了一种新的求解多目标最小生成树问题的进化算法。该算法采用边集合编码表示生成树，给出了一种新的随机(服从均匀分布)生成树算法，并用来产生初始种群；同时设计了一种新的交叉算子和变异算子。第二，针对度约束的最小生成树问题给出了一种改进的进化算法，该算法也采用边集合编码表示生成树，给出了一种新颖的初始种群生成算法和一种改进的交叉算子。数值实验结果表明上述的两种进化算法是有效的。第三，对带约束的最小生成树问题给出了一种有效的枚举算法。最后，介绍了实现并行进化算法的两种基本策略，然后基于多线程技术提出了一种并行进化算法框架，在英特尔的双核处理器的机器上进行数值实验，基于多线程的并行进化算法的加速比达到2，而且还获得比单线程进化算法更好的结果。