【作者】 杨林；

【导师】 黎自强；

【作者基本信息】 湘潭大学 ， 计算机应用技术， 2010， 硕士

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

【Abstract】 Complex layout optimization problems, such as the layout scheme design of printed circuit board(PCB) and satellite module and factory machine equipment layout problem etc, belong to NP-hard problem. It is surprisingly difficult to solve. When solving these problems, they require satisfying performance constraints of imbalance, stability, vibration, connectivity and adjacent, in addition to requirements of maximum space utilization and non-interference between object and object, between object and container. Therefore, it called as the layout optimization problem with performance constraints. Many scholars have done a lot of research and proposed some algorithms, such as heuristic algorithm, evolutionary algorithm, human computer interactive algorithm, graph theory method and so on, but satisfactory solution is only obtained by all of them. With the development of high technology of industry, traffic, national defense and so on, many layout optimization problems with performance constraints, such as VLSI layout design problem, are required to improve computational quality and efficiency of solving problem. Therefor, this paper studies: (a) obtaining the layout knowledge from the known information of the layout problem; (b) the heuristic strategy constructed the layout scheme using the above layout knowledge; (c) hybrid algorithm combined the heuristic algorithm with the ant colony optimization(ACO). The paper applies the hybrid algorithm to solve the 2-D layout problem of weighted circles and the layout problem with equilibrium constraints, and to improve the solving efficiency and precision of latout problem. The main contents in the paper are as follows.Firstly, a heuristic ant colony approach(HACA) is presented for circle layout problems. the layout knowledge obtained from weighted matrix, is used to define the circles’selection probability. Afterward, the paper proposes a selection probability-based ordering mechanism and a improved locating rule. The idea of the rule is that information of tangent circles screening form packed circles is stored to fastly determined candidate positions of next packing circle. The heuristic strategy of HACA consists of ordering mechanism and a improved locating rule and is used in constructing layout schemes of the superior ant individuals. When solving the layout problem of weighted circles, the HACA is designed by combining the ACO with the heuristic strategy; when solving the layout problem with equilibrium constraints, the HACA is designed by combining the ACO with the improved location rule. The experimental results show that the HACA can improve the solution efficiency and precision compared with existing algorithms.Secondly, a improved heuristic ant colony approach(IHACA) based on structing of non-isomorphic layout pattern is put forward for circles layout problem. The approach is on the basis of HACA. After partly constructing ant colony individuals for next generation population of HACA through its heuristic strategy, the other part of ant colony individuals is obtained by constructing non-isomorphic layout pattern solutions of generated ant colony individuals in the process of iteration, The results of examples show when solving the layout problem of weighted circles our approach can improve obviously the solution efficiency and precision; and when solving the layout problem with equilibrium constraints it can improve the solution efficiency and solution precision doesn’t decrease, compared with existing algorithms.The paper studies the circles layout problem with performance constraints based on the layout design of satellite module and PCB as the study background. By combining heuristic strategy and non-isomorphic layout pattern with ant colony optimization(ACO), we develop evolutionary layout approaches to better solve the 2-D circles layout optimization problem with performance constraints than other algorithms. Finally, author hope the above approachs will be spread and applied to some other layout problem.更多还原