| 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. |
PDF Full Text Request