求解带性能约束圆集布局问题的启发式蚁群算法研究
|
摘要
带性能约束复杂布局问题,如印刷电路板(PCB)和航天器舱的布局方案设计及工厂机床设备布置问题等,属于NP-Complete问题,求解困难。在求解这些问题时,除了要求满足待布物间不干涉,尽量提高空间利用率之外,还要考虑各种性能约束,如不平衡性、稳定性、振动、连通性和相邻性等。因此,这类问题被称为带性能约束的布局问题。许多学者进行了大量的研究,提出的已有算法,如启发式算法、演化算法、人机交互算法、图论法等,都只能求出其工程满意解。随着近几十年来工业、交通、国防等方面高技术的发展,一些亟待解决的带复杂性能约束的布局优化(如大规模集成电路的布局设计)问题希望具有更高的求解精度和效率。为此,本文研究:(1)从布局问题的已知信息获取布局知识;(2)将获取的布局知识用于构造布局方案的启发式策略;(3)将启发式策略和蚁群算法相结合的混合布局算法。本文将提出的演化布局算法用于求解2-D带性能的加权圆集布局问题和带平衡约束的圆形布局问题,以提高其求解精度和效率。本文主要工作如下:
1.本文提出求解圆集布局问题的启发式蚁群算法(Heuristic Ant colony Approach, HACA)。从加权矩阵信息获取布局知识,用于定义待布圆的选择概率,是该算法构造布局方案的定序机理。通过筛选已布的相切圆位置作为下一个待布圆的侯选位置,以减少确定其最优位置的计算量,是该算法构造布局方案的定位规则思想。本文算法的启发式策略是由定序机理和定位规则构成,用于构造较优的蚁群个体的布局方案。在求解加权圆集布局问题时,本文的启发式蚁群算法是通过将定序机理和定位规则组成的启发式策略和蚁群算法相结合;在求解平衡约束布局问题时,则是将改进的定位规则和蚁群算法相结合。数值实验表明:与已有的算法相比,该算法能得到较好的求解效率和精度。
2.本文在启发式蚁群算法基础上,提出一种基于非同构布局模式的改进启发式蚁群圆集布局算法(A Improved Heuristic Ant Colony Approach, IHACA)。该算法在每次迭代过程中先由启发式策略构造下一代的部分蚁群个体的布局方案,再通过构造已生成蚁群个体布局方案的非同构布局模式,快速产生另一部分蚁群个体的布局方案,这两部分个体合在一起构成蚁群算法的种群。数值实验验证表明:文中算法求解加权圆集布局问题提高了求解效率和精度,求解带平衡约束布局问题时提高了求解效率且求解精度不降低。
本文以卫星舱和电子线路布局问题为背景,研究了带约束的圆集布局问题。利用布局问题中的布局知识和非同构布局模式,探索出启发式策略与蚁群算法相结合的圆集布局演化算法,较好的解决了2-D带性能约束的圆集布局问题。最后,希望上述算法能推广应用于其他同类布局问题。
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.
1.本文提出求解圆集布局问题的启发式蚁群算法(Heuristic Ant colony Approach, HACA)。从加权矩阵信息获取布局知识,用于定义待布圆的选择概率,是该算法构造布局方案的定序机理。通过筛选已布的相切圆位置作为下一个待布圆的侯选位置,以减少确定其最优位置的计算量,是该算法构造布局方案的定位规则思想。本文算法的启发式策略是由定序机理和定位规则构成,用于构造较优的蚁群个体的布局方案。在求解加权圆集布局问题时,本文的启发式蚁群算法是通过将定序机理和定位规则组成的启发式策略和蚁群算法相结合;在求解平衡约束布局问题时,则是将改进的定位规则和蚁群算法相结合。数值实验表明:与已有的算法相比,该算法能得到较好的求解效率和精度。
2.本文在启发式蚁群算法基础上,提出一种基于非同构布局模式的改进启发式蚁群圆集布局算法(A Improved Heuristic Ant Colony Approach, IHACA)。该算法在每次迭代过程中先由启发式策略构造下一代的部分蚁群个体的布局方案,再通过构造已生成蚁群个体布局方案的非同构布局模式,快速产生另一部分蚁群个体的布局方案,这两部分个体合在一起构成蚁群算法的种群。数值实验验证表明:文中算法求解加权圆集布局问题提高了求解效率和精度,求解带平衡约束布局问题时提高了求解效率且求解精度不降低。
本文以卫星舱和电子线路布局问题为背景,研究了带约束的圆集布局问题。利用布局问题中的布局知识和非同构布局模式,探索出启发式策略与蚁群算法相结合的圆集布局演化算法,较好的解决了2-D带性能约束的圆集布局问题。最后,希望上述算法能推广应用于其他同类布局问题。
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.
引文
[1]钱志勤,滕弘飞.复杂布局问题的算法.中国机械工程[J].2002,13(8):696-698
[2]黄宜军,施德恒,许启赛.钣金CAD中一个较优的排料算法[J].计算机辅助设计与图形学学报, 2000, 12(5):380-383
[3]周泓一,金廷赞.二维不规则形状的最优布局问题[J].浙江大学学报,1988,22(2):92-99
[4] Ahmad A. R., Basir O., Hassanein K. Fuzzy interference in the Web page layout design[C]. In: Proceedings of the first Workshop on Web Service: Modeling, Architecture & Infrastructure, France, 2003, pp. 33-41
[5] Ahmad A. R., Basir O., Hassanein K. An intelligent decision support system for layout design. Working Paper, Systems Design Engineering, University of Waterloo, 2004. (网络链接: http://pami.uwaterloo.ca/pub/rahim/IL-DSS-APDSI-2004.PDF
[6]曹先彬,刘克胜,王煦法.基于免疫遗传算法的装箱问题求解[J].小型微型计算机系统, 2000, 21(4):361-363
[7]何大勇,鄂明成,查建中等.基于空间分解的集装箱布局启发式算法及布局空间利用率规律[J].计算机辅助设计与图形学学报, 2000, 12(5):367-370
[8] Guenther R.Raidl,The Multiple Container Packing Problem:A Genetic Algorithm Approach With Weighted Codings[J],ACM SIGAPP Applied Computing Review,1999,7(2):22-31
[9] Kamran D, Maziar A, Hossein S F.“FARAGAM”algorithm in satellite layout[C]. In: Proceedings of 6th Asia-Pacific Conference on Multilateral Cooperation in Space Technology and Application, Beijing, 2001, 120-127
[10] Pierre M. Grigon, Georges M. Fadel. A GA based configuration design optimization Method [J]. Journal of Mechanical Design,2004,126(1):6-14
[11] Zhang Bao, Teng Hong-fei, Shi Yan Jun. Layout optimization of satellite module suing soft computing techniques[J]. Applied Soft Computing, 2008,8(5):507-521
[12] Bugajska M D, Sehultz A C. Coevolution of form and function in the design of micro air vehieles[C]. In: Proeeedings of the 2002 NASA/DOD Conference on Evolvable Hardware (EH02). Alexandria, Virginia,USA,2002:154-163
[13] Cahlon B. G. A model for the convective cooling of electronic components with application to optimal placement[J]. Mathematics and Computer Modeling, 1991, 15(2): 59-75
[14]孔天明,洪先龙,乔长阁. VEAP:基于全局优化的有效VLSI布局算法[J].半导体学报, 1997, 8(9): 692-699
[15]王乃龙,戴宏宇,周润德.用模拟退火算法实现集成电路热布局优化[J].半导体学报, 2003, 24(4): 427-432
[16]晏敏,张昌期,刘育骐.平面布局的一个拓扑模型:方图[J].小型微型计算机系统, 1989,10(2): 23-32
[17]史彦军.复杂布局的协同差异演化方法与应用研究[D].大连:大连理工大学,2005
[18]谭悦,蔡世俊.集成电路布局规划技术[J].微电子学,1997,27(2):78-84
[19]孔天明,洪先龙,乔长阁.VEAP:基于全局优化的有效VLSI布局算法[J].半导体学报,1997,8(9):692-699
[20] Teng Hongfei, Sun Shoulin, Ge Wenhai. Layout optimization for the dishes installed on a rotating table[J]. Science In China(Series A),1994,37(10):1272-1280
[21] Hadjiconstantinou E, Christofides N. A exact algorithm for general orthogonal two- dimensional knapsack problems[J]. European Journal of Operational Research, 1995, 83(1): 39-56
[22] Botter R C, Brinnati M A. Stowage container planning: a model for getting an optimal solution[C]. ICCAS’92, North Holland, 1992
[23]王金敏,马丰宁,初楠等.基于构造的布局启发方法[J].天津大学学报, 1998,31(1):17-22
[24]李言照,滕弘飞,钟万勰等.旋转舱内长方体群的装填布局优化[J].宇航学报, 1993,14(1): 37-43
[25]李广强,滕弘飞.装填布局的同构和非同构模式[J].计算机学报, 2003,26(10): 1248-1254
[26]吴慧中,王英林,一种立体空间布局模型及布局算法[J].计算机学报, 1994,17(11):835- 841
[27] Feng En-min, Wang Xi-lu, Wang Xiu-mei, et al. An algorithm of global optimization for solving layout problems[J]. European Journal of Operational Research, 1999,114(2):430-436
[28] Zhi-Guo Sun, Hong-Fei Teng. An Ant Colony Optimization based layout Optimization Algorithm[C].Proceedings of IEEE TENCON, 2002:1-4
[29]徐义春,肖人彬.用蚁群算法求解带平衡约束的圆形布局问题[J].控制与决策,2008,23(1): 25-29
[30]霍军周,李广强,滕弘飞.人机结合蚁群、遗传算法及其在卫星舱布局设计中的应用[J].机械工程学报,2005,41(3):112-116
[31]钱学森,于景元,戴汝为.一个科学新领域-开放的复杂巨型系统及其方法论[J].自然杂志, 1990,13(1): 3-10
[32]戴汝为,王珏.巨型智能系统的探讨[J].自动化学报,1993,19(6):645-655
[33] Lenat D B, Feigenbaum E A. On the thresholds of knowledge[J]. Artificial Intelligence, 1991,47(1):185- 230
[34]钱志勤,滕弘飞,孙治国.人机交互的遗传算法及其在约束布局优化中的应用[J].计算机学报, 2001, 24(5):553-559
[35]刘峻,滕弘飞,屈福政.人机交互遗传算法的人机界面[J].大连理工学报,2005,45(1):58-63
[36] Sanja Petrovic, Yong Yang, Moshe Dror. Case-based selection of initialization heuristics for metaheuristic examination timetabling[J]. Expert System with Application ,2007,33(2):772- 785
[37] Bo Jin, Teng Hong-fei. Case-based evolutionary design approach for satellite mo-dule layout[J]. Journal of Scientific and Industrial Research,2007,66(12):989-994
[38]张宝.粒子群算法及其在卫星舱布局中的应用[D].大连理工大学博士论文,2006
[39]王奕首,史彦军,滕弘飞.用改进的散射搜索法求解带平衡约束的圆形packing问题[J].计算机学报,2009,32(6):1214-1211
[40]滕弘飞,黎自强,史彦军,王奕首.一种同构、非同构布局模式构造算法[J].计算机学报,2006,29(6):985-991
[41]康雁.求解圆形packing问题的启发式方法[D].中国科学院软件研究所博士论文,2002
[42]杨维嘉.布局问题求解算法与策略的研究[M].天津:天津大学,2005
[43] Hanan M,Wolff Sr P K, Agile B J. Some experimental results on placement techniques[C]. In: Proceedings of the 13th conference on design antomation.California,USA,1976,PP.214-224
[44] Colori A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[C]. Proceedings of the 1st European Conference on Artificial Life,1991,134-142
[45] Dorigo M. Optimization, learning and natural algorithm[D]. Ph.D.Thesis, Department of Elec- tronics, Politecnico di Milano, Italy, 1992
[46] Dorigo M, Maniezzo V, Colori A. Ant system: optimization by a colony of cooperating agents [J]. IEEE Transaction on systems, Man,and Cybernetics-Pary B,1996,26(1):29-41
[47]段海滨,王道波,朱家强等蚁群算法理论及应用领域研究的进展[J].控制与决策, 2004,19(12):1321-1326,1340
[48] Costa D, Hertz A. Ant can colour graphs[J]. Journal of the Operational Research Socie- ty,1997,48(3):295-305
[49] Maniezzo V, Colorni A. The ant system applied to the quadratic assignment problem[J]. IEEE Transaction on Knowledge and Data Engineering, 1999,11(5):769-778
[50] P Kuntz, P Layzell, D Snyers. A conoly of ant-like agents for partitioning in VLSI techno- ledge[C]. Proceedings of the 4th European conference on Artificial Life. Boston: MIT Press,1997.417-424
[51] Navarro Varela G, Sinclair M C. Ant colony optimization for virtual-wavelength-path routing and wave-length allocation[C]. Proceedings of the 1999 Congress on Evolutionary Computa- tion,1999,1809-1816
[52] R Schoonderwoerd, O Holland, J Bruten. Ant like agents for loadbalancing in telecommunica- tions networks[C]. Proceedings of Agents’97. Marinadel Rey, CA: ACM Press,1997.209-216
[53] Dorigo M, L M Gambardella. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Transaction On Evolutionary Computa-tion,1997,1 (1): 53-66
[54] Dorigo M, Maniezzo V, Colori A. Positive Feedback as a Search Strategy[R]. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di milano,Italy,1991
[55] Bullnheimer B, Hartl R F, Strauss C. A new Rank-based Version of The Ant System: A Computational Study[R]. Technical Report POM-03/97, Institute of Management Science, University of Vienna, 1997.
[56] Maniezzo V, Dorigo M, Colorni A. The ant System Applied to the Quadratic Assignment Problem[R]. Technical Report IRIDIA/94-28,Universite de Bruxelles, Belgium, 1994
[57] Stutzle T, Hoos H. Improvements on the Ant System: Introducing MAX-MIN Ant System[C]. Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithns,Springer Verlag,Wien.1997.245-249
[58]李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业出版社,2004.9
[59]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.12
[60] (意)多里戈,施蒂茨勒著;张军等译.蚁群优化[M].北京:清华大学出版社,2007.1
[61] Liu D Q, Teng H F. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles[J]. European J of Operational Research, 1999,112(2):413-420
[62] George J A, George J M, Lamar B W. Packing different-sized circles into a rectangular container[J]. European J of Operational Research,1995,84(3): 693-712
[63]李广强,滕弘飞,霍军周.并行混合免疫算法及其在布局设计中的应用[J].机械工程学报, 2003,39(6): 79-85
[64]刘占伟,滕弘飞.基于人智-图形-计算的布局设计方法[J].大连理工学报,2006,46(2):228-234
[65]王奕首,艾景波,史彦军,滕弘飞.文化粒子群优化算法[J].大连理工学报,2007,47(4):539-544
[66]唐飞,滕弘飞.一种改进的遗传算法及其在布局优化中的应用[J].软件学报,1999,10(10): 1096-1102
[67]于洋,查建中,唐晓君.基于学习的遗传算法及其在布局中的应用[J].计算机学报,2001,24 (12):1242-1249
[68]李广强,霍军周,滕弘飞.并行混合遗传算法及其在布局设计中的应用[J].计算机工程,2003,29(17):6-8
[69] Kennedy J, Eberhart R.C. Particle swarm optimization[C]. In Proceedings of IEEE International on Neural Networks, Perth Australia,1995,1942-1948
[70]李宁,刘飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究[J].计算机学报,2004,27(7):897-903
[71]周驰,高亮,高海兵.基于粒子群优化算法的约束布局优化[J].控制与决策,2005,20(1):36-40
[72]雷开友,邱玉辉.基于自适应粒子群算法的约束布局优化研究[J].计算机研究与发展,2006,43(10):1724-1731
[73]刘建,黄文奇.利用改进的微分进化算法求解带平衡约束的圆形packing问题[J].信息与控制,2006,35(1):103-107
[74]刘建,黄文奇.求解带平衡约束圆形packing问题的快速局部搜索算法[J].中国图形图像学报,2008,13(5):991-997
[75] Dorigo M, Dicaro G. The ant colony optimization metaheuristic[M].New Idea in optimization. McGraw Hill,1999
[76]李广强.布局方案设计的若干理论、方法及其应用[D].大连理工大学博士论文,2003
[2]黄宜军,施德恒,许启赛.钣金CAD中一个较优的排料算法[J].计算机辅助设计与图形学学报, 2000, 12(5):380-383
[3]周泓一,金廷赞.二维不规则形状的最优布局问题[J].浙江大学学报,1988,22(2):92-99
[4] Ahmad A. R., Basir O., Hassanein K. Fuzzy interference in the Web page layout design[C]. In: Proceedings of the first Workshop on Web Service: Modeling, Architecture & Infrastructure, France, 2003, pp. 33-41
[5] Ahmad A. R., Basir O., Hassanein K. An intelligent decision support system for layout design. Working Paper, Systems Design Engineering, University of Waterloo, 2004. (网络链接: http://pami.uwaterloo.ca/pub/rahim/IL-DSS-APDSI-2004.PDF
[6]曹先彬,刘克胜,王煦法.基于免疫遗传算法的装箱问题求解[J].小型微型计算机系统, 2000, 21(4):361-363
[7]何大勇,鄂明成,查建中等.基于空间分解的集装箱布局启发式算法及布局空间利用率规律[J].计算机辅助设计与图形学学报, 2000, 12(5):367-370
[8] Guenther R.Raidl,The Multiple Container Packing Problem:A Genetic Algorithm Approach With Weighted Codings[J],ACM SIGAPP Applied Computing Review,1999,7(2):22-31
[9] Kamran D, Maziar A, Hossein S F.“FARAGAM”algorithm in satellite layout[C]. In: Proceedings of 6th Asia-Pacific Conference on Multilateral Cooperation in Space Technology and Application, Beijing, 2001, 120-127
[10] Pierre M. Grigon, Georges M. Fadel. A GA based configuration design optimization Method [J]. Journal of Mechanical Design,2004,126(1):6-14
[11] Zhang Bao, Teng Hong-fei, Shi Yan Jun. Layout optimization of satellite module suing soft computing techniques[J]. Applied Soft Computing, 2008,8(5):507-521
[12] Bugajska M D, Sehultz A C. Coevolution of form and function in the design of micro air vehieles[C]. In: Proeeedings of the 2002 NASA/DOD Conference on Evolvable Hardware (EH02). Alexandria, Virginia,USA,2002:154-163
[13] Cahlon B. G. A model for the convective cooling of electronic components with application to optimal placement[J]. Mathematics and Computer Modeling, 1991, 15(2): 59-75
[14]孔天明,洪先龙,乔长阁. VEAP:基于全局优化的有效VLSI布局算法[J].半导体学报, 1997, 8(9): 692-699
[15]王乃龙,戴宏宇,周润德.用模拟退火算法实现集成电路热布局优化[J].半导体学报, 2003, 24(4): 427-432
[16]晏敏,张昌期,刘育骐.平面布局的一个拓扑模型:方图[J].小型微型计算机系统, 1989,10(2): 23-32
[17]史彦军.复杂布局的协同差异演化方法与应用研究[D].大连:大连理工大学,2005
[18]谭悦,蔡世俊.集成电路布局规划技术[J].微电子学,1997,27(2):78-84
[19]孔天明,洪先龙,乔长阁.VEAP:基于全局优化的有效VLSI布局算法[J].半导体学报,1997,8(9):692-699
[20] Teng Hongfei, Sun Shoulin, Ge Wenhai. Layout optimization for the dishes installed on a rotating table[J]. Science In China(Series A),1994,37(10):1272-1280
[21] Hadjiconstantinou E, Christofides N. A exact algorithm for general orthogonal two- dimensional knapsack problems[J]. European Journal of Operational Research, 1995, 83(1): 39-56
[22] Botter R C, Brinnati M A. Stowage container planning: a model for getting an optimal solution[C]. ICCAS’92, North Holland, 1992
[23]王金敏,马丰宁,初楠等.基于构造的布局启发方法[J].天津大学学报, 1998,31(1):17-22
[24]李言照,滕弘飞,钟万勰等.旋转舱内长方体群的装填布局优化[J].宇航学报, 1993,14(1): 37-43
[25]李广强,滕弘飞.装填布局的同构和非同构模式[J].计算机学报, 2003,26(10): 1248-1254
[26]吴慧中,王英林,一种立体空间布局模型及布局算法[J].计算机学报, 1994,17(11):835- 841
[27] Feng En-min, Wang Xi-lu, Wang Xiu-mei, et al. An algorithm of global optimization for solving layout problems[J]. European Journal of Operational Research, 1999,114(2):430-436
[28] Zhi-Guo Sun, Hong-Fei Teng. An Ant Colony Optimization based layout Optimization Algorithm[C].Proceedings of IEEE TENCON, 2002:1-4
[29]徐义春,肖人彬.用蚁群算法求解带平衡约束的圆形布局问题[J].控制与决策,2008,23(1): 25-29
[30]霍军周,李广强,滕弘飞.人机结合蚁群、遗传算法及其在卫星舱布局设计中的应用[J].机械工程学报,2005,41(3):112-116
[31]钱学森,于景元,戴汝为.一个科学新领域-开放的复杂巨型系统及其方法论[J].自然杂志, 1990,13(1): 3-10
[32]戴汝为,王珏.巨型智能系统的探讨[J].自动化学报,1993,19(6):645-655
[33] Lenat D B, Feigenbaum E A. On the thresholds of knowledge[J]. Artificial Intelligence, 1991,47(1):185- 230
[34]钱志勤,滕弘飞,孙治国.人机交互的遗传算法及其在约束布局优化中的应用[J].计算机学报, 2001, 24(5):553-559
[35]刘峻,滕弘飞,屈福政.人机交互遗传算法的人机界面[J].大连理工学报,2005,45(1):58-63
[36] Sanja Petrovic, Yong Yang, Moshe Dror. Case-based selection of initialization heuristics for metaheuristic examination timetabling[J]. Expert System with Application ,2007,33(2):772- 785
[37] Bo Jin, Teng Hong-fei. Case-based evolutionary design approach for satellite mo-dule layout[J]. Journal of Scientific and Industrial Research,2007,66(12):989-994
[38]张宝.粒子群算法及其在卫星舱布局中的应用[D].大连理工大学博士论文,2006
[39]王奕首,史彦军,滕弘飞.用改进的散射搜索法求解带平衡约束的圆形packing问题[J].计算机学报,2009,32(6):1214-1211
[40]滕弘飞,黎自强,史彦军,王奕首.一种同构、非同构布局模式构造算法[J].计算机学报,2006,29(6):985-991
[41]康雁.求解圆形packing问题的启发式方法[D].中国科学院软件研究所博士论文,2002
[42]杨维嘉.布局问题求解算法与策略的研究[M].天津:天津大学,2005
[43] Hanan M,Wolff Sr P K, Agile B J. Some experimental results on placement techniques[C]. In: Proceedings of the 13th conference on design antomation.California,USA,1976,PP.214-224
[44] Colori A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[C]. Proceedings of the 1st European Conference on Artificial Life,1991,134-142
[45] Dorigo M. Optimization, learning and natural algorithm[D]. Ph.D.Thesis, Department of Elec- tronics, Politecnico di Milano, Italy, 1992
[46] Dorigo M, Maniezzo V, Colori A. Ant system: optimization by a colony of cooperating agents [J]. IEEE Transaction on systems, Man,and Cybernetics-Pary B,1996,26(1):29-41
[47]段海滨,王道波,朱家强等蚁群算法理论及应用领域研究的进展[J].控制与决策, 2004,19(12):1321-1326,1340
[48] Costa D, Hertz A. Ant can colour graphs[J]. Journal of the Operational Research Socie- ty,1997,48(3):295-305
[49] Maniezzo V, Colorni A. The ant system applied to the quadratic assignment problem[J]. IEEE Transaction on Knowledge and Data Engineering, 1999,11(5):769-778
[50] P Kuntz, P Layzell, D Snyers. A conoly of ant-like agents for partitioning in VLSI techno- ledge[C]. Proceedings of the 4th European conference on Artificial Life. Boston: MIT Press,1997.417-424
[51] Navarro Varela G, Sinclair M C. Ant colony optimization for virtual-wavelength-path routing and wave-length allocation[C]. Proceedings of the 1999 Congress on Evolutionary Computa- tion,1999,1809-1816
[52] R Schoonderwoerd, O Holland, J Bruten. Ant like agents for loadbalancing in telecommunica- tions networks[C]. Proceedings of Agents’97. Marinadel Rey, CA: ACM Press,1997.209-216
[53] Dorigo M, L M Gambardella. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Transaction On Evolutionary Computa-tion,1997,1 (1): 53-66
[54] Dorigo M, Maniezzo V, Colori A. Positive Feedback as a Search Strategy[R]. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di milano,Italy,1991
[55] Bullnheimer B, Hartl R F, Strauss C. A new Rank-based Version of The Ant System: A Computational Study[R]. Technical Report POM-03/97, Institute of Management Science, University of Vienna, 1997.
[56] Maniezzo V, Dorigo M, Colorni A. The ant System Applied to the Quadratic Assignment Problem[R]. Technical Report IRIDIA/94-28,Universite de Bruxelles, Belgium, 1994
[57] Stutzle T, Hoos H. Improvements on the Ant System: Introducing MAX-MIN Ant System[C]. Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithns,Springer Verlag,Wien.1997.245-249
[58]李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业出版社,2004.9
[59]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.12
[60] (意)多里戈,施蒂茨勒著;张军等译.蚁群优化[M].北京:清华大学出版社,2007.1
[61] Liu D Q, Teng H F. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles[J]. European J of Operational Research, 1999,112(2):413-420
[62] George J A, George J M, Lamar B W. Packing different-sized circles into a rectangular container[J]. European J of Operational Research,1995,84(3): 693-712
[63]李广强,滕弘飞,霍军周.并行混合免疫算法及其在布局设计中的应用[J].机械工程学报, 2003,39(6): 79-85
[64]刘占伟,滕弘飞.基于人智-图形-计算的布局设计方法[J].大连理工学报,2006,46(2):228-234
[65]王奕首,艾景波,史彦军,滕弘飞.文化粒子群优化算法[J].大连理工学报,2007,47(4):539-544
[66]唐飞,滕弘飞.一种改进的遗传算法及其在布局优化中的应用[J].软件学报,1999,10(10): 1096-1102
[67]于洋,查建中,唐晓君.基于学习的遗传算法及其在布局中的应用[J].计算机学报,2001,24 (12):1242-1249
[68]李广强,霍军周,滕弘飞.并行混合遗传算法及其在布局设计中的应用[J].计算机工程,2003,29(17):6-8
[69] Kennedy J, Eberhart R.C. Particle swarm optimization[C]. In Proceedings of IEEE International on Neural Networks, Perth Australia,1995,1942-1948
[70]李宁,刘飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究[J].计算机学报,2004,27(7):897-903
[71]周驰,高亮,高海兵.基于粒子群优化算法的约束布局优化[J].控制与决策,2005,20(1):36-40
[72]雷开友,邱玉辉.基于自适应粒子群算法的约束布局优化研究[J].计算机研究与发展,2006,43(10):1724-1731
[73]刘建,黄文奇.利用改进的微分进化算法求解带平衡约束的圆形packing问题[J].信息与控制,2006,35(1):103-107
[74]刘建,黄文奇.求解带平衡约束圆形packing问题的快速局部搜索算法[J].中国图形图像学报,2008,13(5):991-997
[75] Dorigo M, Dicaro G. The ant colony optimization metaheuristic[M].New Idea in optimization. McGraw Hill,1999
[76]李广强.布局方案设计的若干理论、方法及其应用[D].大连理工大学博士论文,2003