求解带性能约束圆集布局问题的启发式蚁群算法研究

摘要

带性能约束复杂布局问题,如印刷电路板(PCB)和航天器舱的布局方案设计及工厂机床设备布置问题等,属于NP-Complete问题,求解困难。在求解这些问题时,除了要求满足待布物间不干涉,尽量提高空间利用率之外,还要考虑各种性能约束,如不平衡性、稳定性、振动、连通性和相邻性等。因此,这类问题被称为带性能约束的布局问题。许多学者进行了大量的研究,提出的已有算法,如启发式算法、演化算法、人机交互算法、图论法等,都只能求出其工程满意解。随着近几十年来工业、交通、国防等方面高技术的发展,一些亟待解决的带复杂性能约束的布局优化(如大规模集成电路的布局设计)问题希望具有更高的求解精度和效率。为此,本文研究:(1)从布局问题的已知信息获取布局知识;(2)将获取的布局知识用于构造布局方案的启发式策略;(3)将启发式策略和蚁群算法相结合的混合布局算法。本文将提出的演化布局算法用于求解2-D带性能的加权圆集布局问题和带平衡约束的圆形布局问题,以提高其求解精度和效率。本文主要工作如下:
　　1.本文提出求解圆集布局问题的启发式蚁群算法(Heuristic Ant colony Approach,HACA)。从加权矩阵信息获取布局知识,用于定义待布圆的选择概率,是该算法构造布局方案的定序机理。通过筛选已布的相切圆位置作为下一个待布圆的侯选位置,以减少确定其最优位置的计算量,是该算法构造布局方案的定位规则思想。本文算法的启发式策略是由定序机理和定位规则构成,用于构造较优的蚁群个体的布局方案。在求解加权圆集布局问题时,本文的启发式蚁群算法是通过将定序机理和定位规则组成的启发式策略和蚁群算法相结合;在求解平衡约束布局问题时,则是将改进的定位规则和蚁群算法相结合。数值实验表明:与已有的算法相比,该算法能得到较好的求解效率和精度。
　　2.本文在启发式蚁群算法基础上,提出一种基于非同构布局模式的改进启发式蚁群圆集布局算法(A Improved Heuristic Ant Colony Approach,IHACA)。该算法在每次迭代过程中先由启发式策略构造下一代的部分蚁群个体的布局方案,再通过构造已生成蚁群个体布局方案的非同构布局模式,快速产生另一部分蚁群个体的布局方案,这两部分个体合在一起构成蚁群算法的种群。数值实验验证表明:文中算法求解加权圆集布局问题提高了求解效率和精度,求解带平衡约束布局问题时提高了求解效率且求解精度不降低。
　　本文以卫星舱和电子线路布局问题为背景,研究了带约束的圆集布局问题。利用布局问题中的布局知识和非同构布局模式,探索出启发式策略与蚁群算法相结合的圆集布局演化算法,较好的解决了2-D带性能约束的圆集布局问题。最后,希望上述算法能推广应用于其他同类布局问题。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 课题的背景

1.2 圆集布局问题

1.3 课题研究内容和意义

1.4 研究的基础

1.5 论文的组织

第二章 启发式算法

2.1 启发式算法

2.2 packing圆集问题启发式策略

2.3 小结

第三章 圆集Packing蚁群布局算法

3.1 基本蚁群算法的原理和演化机制

3.2 圆集Packing蚁群布局算法

3.3 小结

第四章 求解圆集布局问题的启发式蚁群算法

4.1 圆集布局问题的研究现状

4.2 求解加权圆集布局问题的启发式蚁群算法4.2.1 相关定义

4.3 求解带平衡约束圆形布局问题的启发式蚁群算法4.3.1 问题描述

4.4 小结

第五章 一种改进的启发式蚁群圆集布局算法

5.1 相关知识

5.2 求解加权圆集布局问题的改进启发式蚁群算法

5.3 求解平衡约束圆形布局问题的改进启发式蚁群算法

5.4 小结

总结与展望

参考文献

致谢

附录A：攻读硕士学位期间发表论文和参与的研究项目