演化算法及其在工程布局设计中的应用

摘要

本文研究演化算法及其在布局问题中的应用，其工程背景是返回式卫星回收舱布局设计和城市环境区域噪声测量布点优化问题。该课题在理论上，属带性能约束的具有NP难度的复杂问题，涉及机械工程、计算机科学、数学、自动化和系统工程、航天器设计、环境科学等学科，为交叉学科前沿课题的基础理论和应用基础研究，具有挑战性。在实践上，具有广泛的工程应用前景，如航天器舱、车辆船舶、高速列车、水下悬浮工程、海上钻井平台、组合机床多轴箱、机器人等的布局方案设计问题。研究的演化算法还可推广应用于求解多种复杂工程系统的优化问题之中。因此，无论从理论上还是工程实践上，该问题都是一个亟待较好解决的重要问题。 求解复杂工程布局问题的难点是存在计算复杂性的组合爆炸和工程实用化的复杂性。目前，针对复杂布局问题的主要求解方法有：数学规划和准则法、启发式算法、图论法、专家系统及演化算法等。数学规划和准则法有较为成熟的理论基础，但存在局部收敛性质，求解大规模问题较困难。启发式算法可得到较好的解，然而它只能解决一类限定的问题。图论法利用“相邻”、“距离”等关系，剪切了一些搜索分枝，却也带来了解空间不完备的问题。另外，它对空间的描述显得较复杂。专家系统对于求解复杂布局问题的局限性在于专家知识的获取和推理机制的设计较难。从算法的发展趋势和求解效果而言，通用、稳健、模拟自然法则的演化算法，如遗传算法等，具有一定的求解优势，它们尤其适合于求解大型复杂问题。本文以演化算法中的遗传算法为基础，对其缺陷加以改进，提出一种混合的智能并行演化算法，以便于更好地求解工程布局设计问题。论文的主要内容如下。 (1)给出本文研究课题的工程背景和意义，然后综述了布局问题的求解算法及其国内外有代表性的研究工作，并在其基础上明确了本文使用混合演化算法求解复杂布局设计问题的这一求解思路。 (2)对演化算法进行了较为深入的阐述，包括演化算法的理论基础，各种算法的基本内容和实现等。 (3)提出了混合粒子群免疫算法(HPSO-IA)。该算法以粗粒度并行遗传算法(PGA)为基础，针对其早熟和收敛速度慢等缺陷，给出一系列相应的改进措施，主要有：a.依据改进的自适应交叉、变异算子对子群体分类，实行多种群的并行演化；b.根据不同类型子群体的特点，引入不同模式的个体PSO更新算子，其主要目的是充分利用粒子群算法收敛快的特点；c.加入免疫的思想可起到双重效果，一方面基于提出的可调等差排序的免疫选择算子能有效防止早熟，另一方面模拟免疫记忆和接种过程的子群体信息交换策略可加快收敛速度；d.对于优秀个体的单纯形和混沌搜索能显著改善混合算法的局部搜索性能。HPSO-IA有连续型和0-1离散型两种版本，可同时用于解决上述两类问题，是一种通用的混合演化算法。文中的算例(包括典型函数优化问题和背包问题)表Ⅰ明了HPSO-IA是可行和有效的，确实优于传统的并行遗传算法。 (4)将提出的演化算法应用于工程布局设计问题，包括印刷电路板(PCB)设计为背景的加权圆集布局设计问题和圆容器装填布局问题。重点以返回式卫星回收舱的布局方案设计和城市环境区域噪声测量布点优化问题为实例，建立了其数学模型并用HPSO-IA求解，取得了令人满意的优化结果。这些工作促进了演化算法和工程布局设计问题的相关理论方法及应用的研究进展。 本课题得到了国家自然科学基金(No.50175009，No.50275019)和铁道部科技开发项目(No.2003J017)的资助。本文的研究具有理论意义和社会经济效益，可望推广应用于前述多种相关问题之中。

目录

文摘

英文文摘

第一章绪论

1.1课题的工程背景和研究意义

1.1.1课题的工程背景

1.1.2课题的研究意义

1.2布局问题的内涵和实例

1.2.1布局问题的内涵

1.2.2布局问题实例

1.3布局问题求解算法的国内外研究综述

1.3.1数学规划和准则法

1.3.2启发式算法

1.3.3图论法

1.3.4人工智能

1.3.5人机结合与协同设计

1.3.6演化算法

1.4本文的求解策略

1.5论文的主要内容和组织结构

第二章演化算法及其实现

2.1演化算法概要

2.1.1演化算法的含义

2.1.2演化算法的基本框架

2.1.3演化算法的基本特点

2.2几种演化算法及其实现

2.2.1遗传算法

2.2.2演化策略

2.2.3演化规划

2.2.4蚂蚁算法

2.2.5差异演化

2.2.6粒子群优化

第三章混合粒子群免疫算法

3.1改进的并行遗传算法

3.1.1改进的自适应交叉、变异算子和多种群并行演化

3.1.2可调等差排序选择

3.1.3局部搜索策略

3.2混合粒子群免疫算法

3.2.1免疫思想的引入

3.2.2个体PSO更新算子

3.2.3混合粒子群免疫算法的实现

3.2.4离散型的混合粒子群免疫算法

3.3数值试验

3.3.1函数优化问题

3.3.2背包问题

3.4小节

第四章工程布局设计问题的计算实例

4.1加权圆集的布局设计问题

4.2圆容器装填布局问题

4.3返回式卫星回收舱的布局方案设计

4.3.1问题概述

4.3.2数学模型

4.3.3实例

4.4城市环境区域噪声测点优化

4.4.1问题概述

4.4.2数学模型

4.4.3实例

4.5小节

第五章结论与展望

5.1论文的工作总结

5.2后续工作展望

参考文献

致谢

博士后期间发表的学术论文和承担课题

个人简历