并行进化算法及其在组合优化中的应用

摘要

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

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景与意义

1.2进化计算的产生和发展

1.3进化计算的主要特点

1.4基于多线程的并行进化算法

1.5本文的组织

第二章进化计算的基本原理和方法

2.1进化计算的基本概念

2.1.1编码格式

2.1.2适应度度量

2.1.3选择算子

2.1.4繁殖算子

2.1.5进化算法的基本结构

2.2遗传算法

2.2.1遗传算法的基本结构

2.2.2基于精英保留与父子混合选择的遗传算法

2.3进化策略

2.4多目标进化算法

2.3.1多目标优化问题的数学模型

2.3.2非支配排序遗传算法(NSGA)

2.3.3带精英策略的非支配排序的遗传算法(NSGA-Ⅱ)

2.5本章小结

第三章进化算法在组合优化中的应用

3.1引言

3.1.1图的基本术语

3.1.2带约束的最小生成树问题

3.2多目标最小生成树问题

3.2.1多目标最小生成树问题的数学描述

3.2.2生成树的编码格式

3.2.3初始种群的生成算法

3.2.4繁殖算子

3.2.5进化算法基本框架

3.2.6算法结果分析

3.3度约束的最小生成树问题

3.3.1编码格式和生成初始种群算法

3.3.2繁殖算子

3.3.3进化算法框架

3.3.4算法结果分析

3.4带约束的最小生成树的枚举算法

3.5本章小结

第四章基于多线程的并行进化算法

4.1进化算法的并行化

4.1.1进化算法的并行性分析

4.1.2并行进化算法的硬件支持环境及性能评价

4.2基于种群分组的并行进化算法

4.3基于空间分解的并行进化算法

4.4并行进化算法在组合优化中的应用

4.4.1基于多线程技术的并行算法框架

4.4.2并行算法结果分析

4.5本章小结

第五章结束语

致谢

参考文献

在学期间撰写的论文及参加的科研工作