求解加权圆集布局问题启发式演化算法的研究.doc

Research on Evolutionary Algorithm with Heuristic Strategy for Weighted Circles Layout Problem  Candidate Supervisor College Program Specialization Degree University Date  Xie Yanfang Li Ziqiang(professor) School of information and engineering Technology of Computer Application Intelligent Computing Master of engineering Xiangtan University May20th,2012 湘潭大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。  作者签名：  日期：  年  月  日  学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权湘潭大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 涉密论文按学校规定处理。  作者签名： 导师签名：  日期： 日期：  年 年  月 月  日 日 摘  要  带性能约束布局问题有着较为广泛的应用背景 。如钢铁企业的板材切割 (最大成材 率约束)，印刷电路板(PCB)的布局设计(最小权距积之和约束)，航天器舱的布局方案 设计(最小不平衡量约束)及工厂机床设备布置(最小货运花费约束)问题等。目前，加权 布局问题与带平衡约束的布局问题是我们课题组主要讨论的两类 2 维带性能约束布局 问题。本文研究前者，由于加权圆集布局问题属于 NP-hard 组合优化问题，在多项式 时间内求解是十分困难的。因此，学者们进行了深入研究，并提出诸如启发式和演化 算法等有效算法。但计算精度和计算效率都有待提高 ,尤其是大规模布局问题。为此， 本文在湖南省自然科学基金和湖南省教育厅基金项目的资助工下，对加权布局问题展 开研究，提出一种求解加权圆集布局问题的有效机理和算法。主要工作如下： 1. 本文针对加权圆集布局问题，提出一种新的启发式算法。它是根据问题本身的 已知信息，获得其布局知识，用于建立启发式定序和定位规则：圆半径和权矩阵的行 向量范数作为轮盘赌选择的概率因子，对圆集的放置顺序进行定序；定位采用外围逆 时针排列定位规则。该启发式算法能快速构造出外包络矩形面积较小的布局方案，且 计算复杂度低。 2. 本文针对加权圆集布局问题提高一种蚁群布局优化算法。它是将提出的启发式 策略和蚁群算法相结合。实验结果表明：提高的算法比已有算法提高了计算精度。 3. 本文针对加权圆集布局问题提高一种带拟人策略的粒子群优化算法。该算法是 将拟人策略与粒子群局部优化算法相结合，对通过启发式构造得到的较优解作进一步 优化，获得最优解。数值试验验证表明：与已经存在的算法相比，本文算法的计算效 率和计算精度都得到了明显的提高。 本文以印刷电路板布局和车间机器摆放为背景，充分利用布局问题本身的已知信 息研究了加权圆集的布局问题的优化求解算法。先给出一种启发式算法，进而探索出 启发式蚁群算法和拟人粒子群算法，较好地解决了二维加权圆集布局问题。最后，希 望本文算法能推广应用于其他同类布局问题。 关键词：加权圆集布局问题；启发式；拟人粒子群；粒子群算法 I Abstract Layout problem with performance constraints (PCLP problem) has widespread application background, for example, cutting plates of iron and steel plate enterprise (the maximum product rate constraint), the layout design of printed circuit board (PCB) (the minimal the sum of weighted distance product constraint), the layout scheme design of spacecr