求解矩形packing问题的纯粹拟人算法
|
摘要
NP难度问题是一大类问题,NP完全问题则是其中最简单最基本的一类问题。NP完全问题在科学哲学和现实生活中的重要价值在于它同时具有看来相反的两个性质:通俗性和难解性。导致NP完全问题难解的主要根源在于解空间随问题规模的扩大呈指数增长,甚至是一个连续欧氏空间的无穷集合。矩形packing问题属于NP难度问题。此问题来源于物件布局、切裁下料以及超大规模集成电路设计等实际问题,常见的提法有:矩形背包问题,矩形装填问题和矩形块布局问题。
我们将人类在近万年来所从事的一些特殊活动中采取的方法和形成的实践经验加以形式化,把它说精确、说完整,并予以进一步的发展,在此基础上设计出求解矩形packing问题的纯粹拟人算法。
在“占角动作”和“穴度”两个重要概念的基础上得到了挑选占角动作的具体策略,并提出了求解矩形背包问题的三个具体的纯粹拟人算法:最大穴度算法A_0,前瞻穴度算法A_1和强化穴度算法A_2。算法A_0采用纯粹贪心的办法放置矩形块,即每次挑选穴度最大的占角动作并将动作关联的矩形块按相应的位置和方向放在容器中。算法A_1在放每一块矩形块时,都运用回溯的策略,以确定一个“全局最好”的动作。算法A_2仅在放第一块时运用回溯的策略,以后就采用最大穴度算法放置剩下的矩形块。用Hopper和Turton提出的21个测试实例对三个算法的性能进行了实算测试,并与当今国际文献已报道的最先进的两个算法——初步拟人算法Heuristic1和混合启发式算法(HH)进行了对比。算法A_1求出了其中15个实例的最优解,算法A_2求出了其中7个实例的最优解,这一结果优于算法Heuristic1和HH所得结果。
以“角点数”和“贴边数”两个概念为基础,对算法A_0,A_1和A_2进行改进而得到了三个相应的改进算法A'_0,A'_1和A'_2。对Hopper和Turton提出的21个测试实例,算法A'_1求出了其中19个实例的最优解,算法A'_2求出了其中8个实例的最优解,这一结果比A_1和A_2所得结果要好。
结合二分的思想,将算法A'_1加以改造而得到了矩形装填问题的拟人求解算法A_3。用三组测试算例对算法性能进行了实算测试。对Hopper和Turton提出的21个测试实例,算法A_3所得容器高度与最优高度的偏差的平均值为0.04%;对Hopper提出的35个装填实例,偏差的平均值为1.8%;对Berkey和Martello等人提出的10组共500个装填实例,偏差的平均值为2.28%。这些结果比目前国际上已报道的最先进的启发式算法所得结果要好。
以算法A_0和A_1为基础,结合“聚类”的思想,提出了矩形块布局问题的拟人求解算法A_4。对MCNC和GSRC两组共21个实例,算法求出了其中20个实例的最优解,这一结果好于CompaSS算法(Compacting Soft and Slicing Packings)、基于角模块序列的模拟退火算法(CBL)及遗传算法所得结果。
在算法A0和A1的基础上,提出了求解价值优化的矩形packing问题的纯粹拟人算法A_5。算法中使用了两个主要的拟人策略——矩形块选择策略和占角动作选择策略。用国际上公认的21个小规模实例和630个大规模实例对算法性能进行了测试,并和基于人口进化理论的启发式算法(PH)进行了对比,算法A_5所得结果比PH算法所得结果好得多。
大量的实算测试和对比分析表明:我们提出的诸算法是求解矩形packing问题的有效算法。人们今后还可沿着“占角”和“穴度”的哲学思想,对直角多边形和长方体packing问题展开研究。
Among all NP-hard problems, NP-complete problems are the simplest and the mostfundamental ones. NP-complete problems are of critical value in philosophy of scienceand real life because of their two opposite characteristics: popularity and difficulty. Themain reason of the difficulty is that the solution space is an exponential function of theproblem size, even an infinite set in Euclidian space.
The rectangle packing problem has proven to be NP-hard. It is from some practicalproblems such as layout, cutting, very large scale integration (VLSI) designing etc and isgenerally described as rectangle knapsack problem, rectangle strip packing problem andrectangle placement problem, respectively.
We formalize the method and experience from some special works of human beingin ten-thousand-year, state it exactly and completely, and then upgrade it to a higher level.Based on this idea, pure quasi-human algorithms are proposed to solve the rectangle pack-ing problem.
Based on the corner-occupying action (COA) and caving degree, we give the COAselecting criterion and propose three pure quasi-human algorithms, i.e., maximum cavingdegree algorithm A0, look ahead caving degree algorithm A1 and strengthening caving de-gree algorithm A2, to solve the rectangle knapsack problem. In algorithm A0, pure greedystrategy is considered to pack a rectangle, that is, pick the COA with maximum caving de-gree and pack the corresponding rectangle into the container in the corresponding positionand orientation at each packing step. In algorithm A_1, backtracking strategy is consid-ered in order to determine a global best COA for packing a rectangle. In algorithm A2,backtracking strategy is used to pack the first rectangle, and then maximum caving degreealgorithm is used to pack the others. The performance of three algorithms is evaluated by21 instances provided by Hopper and Turton and compared with that of two most advancedalgorithms——simple quasi-human algorithm Heuristic1 and hybrid heuristic algorithm (HH). Optimal solutions of 15 instances are achieved by A_1 and 7 by A_2. The quality ofthe results is better than that of results obtained by Heuristic1 and HH.
Based on vertex degree and edge degree, we improve three algorithms A_0, A_1 and A_2and obtain algorithms A'_0, A'_1 and A'_2, respectively. For 21 instances provided by Hopperand Turton, optimal solutions of 19 instances are achieved by A'_1 and 8 by A'_2. The qualityof the results is superior to that of results obtained by A_1 and A_2.
In order to solve the rectangle strip packing problem , we modify the algorithm A'_1 onthe basis of dichotomy strategy and obtain a quasi-human algorithm A_3. The performanceof the algorithm is evaluated through three group benchmarks. For 21 instances providedby Hopper and Turton, 35 strip packing instances by Hopper and 10 group benchmarks(500 instances) by Berkey and Martello et al, the average deviation between the best con-tainer height and the optimum is 0.04%, 1.8% and 2.28%, respectively. The quality ofthese results is better than that of the results obtained by the most advanced heuristic al-gorithms which are reported up to now.
Based on A0 and A1 combining clustering strategy, a quasi-human algorithm A_4 ispresented to solve the rectangle placement problem. For MCNC and GSRC benchmarks(21 instances), optimal solutions of 20 instances are achieved by A_4. Experimental resultsdemonstrate that A4 is more efficient than CompaSS algorithm (Compacting Soft andSlicing Packings), simulated annealing algorithm based on corner block list (CBL) andgenetic algorithm.
On the basis of A_0 and A_1, a pure quasi-human algorithm A_5 is proposed to solve therectangle packing problem with value optimization. Two primary quasi-human strategies,i.e., rectangle selecting strategy and COA selecting criterion, are considered in the algo-rithm. The performance of the algorithm is evaluated by 21 small and 630 large publicinstances and compared with that of population heuristic algorithm (PH). The quality ofthe results achieved by A_5 is superior to that of the results by PH.
Experimental results and comparisons demonstrate that the presented algorithms inthis dissertation are efficient for solving the rectangle packing problem. In the future,rectilinear block packing and cuboid packing problems could be studied further on the basis of corner-occupying action and caving degree.
我们将人类在近万年来所从事的一些特殊活动中采取的方法和形成的实践经验加以形式化,把它说精确、说完整,并予以进一步的发展,在此基础上设计出求解矩形packing问题的纯粹拟人算法。
在“占角动作”和“穴度”两个重要概念的基础上得到了挑选占角动作的具体策略,并提出了求解矩形背包问题的三个具体的纯粹拟人算法:最大穴度算法A_0,前瞻穴度算法A_1和强化穴度算法A_2。算法A_0采用纯粹贪心的办法放置矩形块,即每次挑选穴度最大的占角动作并将动作关联的矩形块按相应的位置和方向放在容器中。算法A_1在放每一块矩形块时,都运用回溯的策略,以确定一个“全局最好”的动作。算法A_2仅在放第一块时运用回溯的策略,以后就采用最大穴度算法放置剩下的矩形块。用Hopper和Turton提出的21个测试实例对三个算法的性能进行了实算测试,并与当今国际文献已报道的最先进的两个算法——初步拟人算法Heuristic1和混合启发式算法(HH)进行了对比。算法A_1求出了其中15个实例的最优解,算法A_2求出了其中7个实例的最优解,这一结果优于算法Heuristic1和HH所得结果。
以“角点数”和“贴边数”两个概念为基础,对算法A_0,A_1和A_2进行改进而得到了三个相应的改进算法A'_0,A'_1和A'_2。对Hopper和Turton提出的21个测试实例,算法A'_1求出了其中19个实例的最优解,算法A'_2求出了其中8个实例的最优解,这一结果比A_1和A_2所得结果要好。
结合二分的思想,将算法A'_1加以改造而得到了矩形装填问题的拟人求解算法A_3。用三组测试算例对算法性能进行了实算测试。对Hopper和Turton提出的21个测试实例,算法A_3所得容器高度与最优高度的偏差的平均值为0.04%;对Hopper提出的35个装填实例,偏差的平均值为1.8%;对Berkey和Martello等人提出的10组共500个装填实例,偏差的平均值为2.28%。这些结果比目前国际上已报道的最先进的启发式算法所得结果要好。
以算法A_0和A_1为基础,结合“聚类”的思想,提出了矩形块布局问题的拟人求解算法A_4。对MCNC和GSRC两组共21个实例,算法求出了其中20个实例的最优解,这一结果好于CompaSS算法(Compacting Soft and Slicing Packings)、基于角模块序列的模拟退火算法(CBL)及遗传算法所得结果。
在算法A0和A1的基础上,提出了求解价值优化的矩形packing问题的纯粹拟人算法A_5。算法中使用了两个主要的拟人策略——矩形块选择策略和占角动作选择策略。用国际上公认的21个小规模实例和630个大规模实例对算法性能进行了测试,并和基于人口进化理论的启发式算法(PH)进行了对比,算法A_5所得结果比PH算法所得结果好得多。
大量的实算测试和对比分析表明:我们提出的诸算法是求解矩形packing问题的有效算法。人们今后还可沿着“占角”和“穴度”的哲学思想,对直角多边形和长方体packing问题展开研究。
Among all NP-hard problems, NP-complete problems are the simplest and the mostfundamental ones. NP-complete problems are of critical value in philosophy of scienceand real life because of their two opposite characteristics: popularity and difficulty. Themain reason of the difficulty is that the solution space is an exponential function of theproblem size, even an infinite set in Euclidian space.
The rectangle packing problem has proven to be NP-hard. It is from some practicalproblems such as layout, cutting, very large scale integration (VLSI) designing etc and isgenerally described as rectangle knapsack problem, rectangle strip packing problem andrectangle placement problem, respectively.
We formalize the method and experience from some special works of human beingin ten-thousand-year, state it exactly and completely, and then upgrade it to a higher level.Based on this idea, pure quasi-human algorithms are proposed to solve the rectangle pack-ing problem.
Based on the corner-occupying action (COA) and caving degree, we give the COAselecting criterion and propose three pure quasi-human algorithms, i.e., maximum cavingdegree algorithm A0, look ahead caving degree algorithm A1 and strengthening caving de-gree algorithm A2, to solve the rectangle knapsack problem. In algorithm A0, pure greedystrategy is considered to pack a rectangle, that is, pick the COA with maximum caving de-gree and pack the corresponding rectangle into the container in the corresponding positionand orientation at each packing step. In algorithm A_1, backtracking strategy is consid-ered in order to determine a global best COA for packing a rectangle. In algorithm A2,backtracking strategy is used to pack the first rectangle, and then maximum caving degreealgorithm is used to pack the others. The performance of three algorithms is evaluated by21 instances provided by Hopper and Turton and compared with that of two most advancedalgorithms——simple quasi-human algorithm Heuristic1 and hybrid heuristic algorithm (HH). Optimal solutions of 15 instances are achieved by A_1 and 7 by A_2. The quality ofthe results is better than that of results obtained by Heuristic1 and HH.
Based on vertex degree and edge degree, we improve three algorithms A_0, A_1 and A_2and obtain algorithms A'_0, A'_1 and A'_2, respectively. For 21 instances provided by Hopperand Turton, optimal solutions of 19 instances are achieved by A'_1 and 8 by A'_2. The qualityof the results is superior to that of results obtained by A_1 and A_2.
In order to solve the rectangle strip packing problem , we modify the algorithm A'_1 onthe basis of dichotomy strategy and obtain a quasi-human algorithm A_3. The performanceof the algorithm is evaluated through three group benchmarks. For 21 instances providedby Hopper and Turton, 35 strip packing instances by Hopper and 10 group benchmarks(500 instances) by Berkey and Martello et al, the average deviation between the best con-tainer height and the optimum is 0.04%, 1.8% and 2.28%, respectively. The quality ofthese results is better than that of the results obtained by the most advanced heuristic al-gorithms which are reported up to now.
Based on A0 and A1 combining clustering strategy, a quasi-human algorithm A_4 ispresented to solve the rectangle placement problem. For MCNC and GSRC benchmarks(21 instances), optimal solutions of 20 instances are achieved by A_4. Experimental resultsdemonstrate that A4 is more efficient than CompaSS algorithm (Compacting Soft andSlicing Packings), simulated annealing algorithm based on corner block list (CBL) andgenetic algorithm.
On the basis of A_0 and A_1, a pure quasi-human algorithm A_5 is proposed to solve therectangle packing problem with value optimization. Two primary quasi-human strategies,i.e., rectangle selecting strategy and COA selecting criterion, are considered in the algo-rithm. The performance of the algorithm is evaluated by 21 small and 630 large publicinstances and compared with that of population heuristic algorithm (PH). The quality ofthe results achieved by A_5 is superior to that of the results by PH.
Experimental results and comparisons demonstrate that the presented algorithms inthis dissertation are efficient for solving the rectangle packing problem. In the future,rectilinear block packing and cuboid packing problems could be studied further on the basis of corner-occupying action and caving degree.
引文
[1] Cook S. The complexity of theorem-proving procedures. in: Proceedings of 3rd ACM Sym-posium on Theory of Computing. Shaker Heights, Ohio, USA. 1971. New York: ACM Press,1971. 151～158
[2] Dowsland K A, Dowsland W B. Packing problems. European Journal of Operational Research,1992, 56(1):2～14
[3] Alvarez-Valdes R, Parren?o F, Tamarit J M. A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems. Journal of the Operational Research Society, 2005,56(4):414～425
[4] Alvarez-Valdes R, Parren?o F, Tamarit J M. A tabu search algorithm for a two-dimensional non-guillotine cutting problem. European Journal of Operational Research,doi:10.1016/j.ejor.2005.11.068
[5] Beasley J E. A population heuristic for constrained two-dimensional non-guillotine cutting.European Journal of Operational Research, 2004, 156(3):601～627
[6] Bortfeldt A. A genetic algorithm for the two-dimensional strip packing problem with rectangularpieces. European Journal of Operational Research, 2006, 172(3):814～837
[7] Burke E K, Kendall G, Whitewell G. A new placement heuristic for the orthogonal stock-cuttingproblem. Operations Research, 2004, 52(4):655～671
[8] Caprara A, Monaci M. On the two-dimensional knapsack problem. Operations Research Letters,2004, 32(1):5～14
[9] Gonc?alves J F. A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packingproblem. European Journal of Operational Research, doi:10.1016/j.ejor.2005.11.062
[10] Jansen K, Zhang G. On rectangle packing: maximizing benefits. in: Munro J I, ed.. Proceed-ings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. New Orleans,Louisiana, USA. 2004. Philadelphia, Pennsylvania: Society for Industrial and Applied Mathe-matics, 2004. 204～213
[11] Zhang D, Deng A. A hybrid heuristic algorithm for the rectangular packing problem. LectureNotes in Computer Science, 2005, 3514:783～791
[12] Wu Y L, Huang W, Lau S C, et al. An effective quasi-human based heuristic for solving therectangle packing problem. European Journal of Operational Research, 2002, 141(2):341～358
[13] Baker B S, Coffman E G, Rivest R L. Orthogonal packings in two dimensions. SIAM Journalon Computing, 1980, 9(4):846～855
[14] Hopper E, Turton B C H. An empirical investigation of meta-heuristic and heuristic algorithmfor a 2D packing problem. European Journal of Operational Research, 2001, 128(1):34～57
[15] Hifi M, M’Hallah R. A hybrid algorithm for the two-dimensional layout problem: the casesof regular and irregular shapes. International Transactions in Operational Research, 2003,10(3):195～216
[16] Zhang D, Deng A. An effective hybrid algorithm for the problem of packing circles into a largercontaining circle. Computers & Operations Research, 2005, 32(8):1941～1951
[17] Zhang D, Liu Y, Chen S, et al. A meta-heuristic algorithm for the strip rectangular packingproblem. Lecture Notes in Computer Science, 2005, 3612:1235～1241
[18] Hadjiconstantinou E, Iori M. A hybrid genetic algorithm for the two-dimensionalsingle large object placement problem. European Journal of Operational Research,doi:10.1016/j.ejor.2005.11.061
[19]许如初,黄文奇.解不等圆packing问题拟物拟人算法初态选取.华中理工大学学报, 1998,26(4):1～3
[20] Huang W, Xu R. Two personification strategies for solving circles packing problem. Science inChina, Series E (Technological Sciences), 1999, 42(6):595～602
[21] Huang W, Kang Y. A heuristic quasi-physical strategy for solving disks packing problem. Sim-ulation Modelling Practice and Theory, 2002, 10(3-4):195～207
[22] Huang W, Li Y, Akeb H, et al. Greedy algorithms for packing unequal circles into a rectangularcontainer. Journal of the Operational Research Society, 2005, 56(5):539～548
[23] Huang W, Li Y, Li C, et al. New heuristics for packing unequal circles into a circular container.Computers & Operations Research, 2006, 33(8):2125～2142
[24]黄文奇,刘景发.基于欧氏距离的矩形Packing问题的确定性启发式求解算法.计算机学报,2006, 29(5):734～739
[25] Holland J. Adaptation in natural and artificial systems. Ann Arbor: University of MichiganPress, 1975
[26] De Jong K. An analysis of the behavior of a class of genetic adaptive systems: [PhD Disserta-tion]. University of Michigan, 1975
[27] Goldberg D E. Genetic algorithms in search, optimization and machine learning. ReadingMassachusetts: Addison-Wesley Publishing Company, 1989
[28] Davis L. Applying adaptive algorithms to epistatic domains. in: Joshi A K, ed.. Proceedingsof the International Joint Conference on Artificial Intelligence. Los Angeles, California, USA.1985. San Francisco, California: Morgan Kaufmann Publishers, 1985. 162～164
[29] Goldberg D E, Lingle R. Alleles, loci and the traveling salesman problem. in: GrefenstetteJ J, ed.. Proceedings of the 1st International Conference on Genetic Algorithms. Pittsburgh,Pennsylvania, USA. 1985. Hillside, New Jersey: Lawrence Erlbaum Associates Publishers,1985. 154～159
[30] Oliver I M, Smith D J, Holland J. A study of permutation crossover operators on the travelingsalesman problem. in: Grefenstette J J, ed.. Proceedings of the 2nd International Conference onGenetic Algorithms. Cambridge, Massachusetts, USA. 1987. Hillside, New Jersey: LawrenceErlbaum Associates Publishers, 1987. 224～230
[31] Shahookar K, Mazumder P. VLSI cell placement techniques. ACM Computing Surveys, 1991,23(2):143～220
[32] Jakobs S. On genetic algorithms for the packing of polygons. European Journal of OperationalResearch, 1996, 88(1):165～181
[33] Sechen C. Chip-planning, placement, and global routing of macro/custom cell integrated cir-cuits using simulated annealing. in: Proceedings of the 25th ACM/IEEE Conference on DesignAutomation. New Jersey, USA. 1988. Los Alamitos, California: IEEE Computer Society Press,1988. 73～80
[34] Kennedy J, Eberhart R C. Particle swarm optimization. in: Proceedings of IEEE InternationalConference on Neural Networks. Perth, Australia. 1995. Piscataway, New Jersey: IEEE Press,1995. 1942～1948
[35] Clerc M, Kennedy J. The particle swarm—explosion, stability, and convergence in a multidi-mensional complex space. IEEE Transactions on Evolutionary Computation, 2002, 6(1):58～73
[36]雷秀娟,史忠科,王来军,等.粒子群优化算法在多目标优化中的应用与仿真.计算机工程与应用, 2006, 42(2):28～29
[37] Eberhart R C, Shi Y. Particle swarm optimization: developments, applications and resources. in:Furuhashi T, Mckay B, eds.. Proceedings of the 2001 Congress on Evolutionary Computation.Seoul, South Korea. 2001. Piscataway, New Jersey: IEEE Press, 2001. 81～86
[38] Clerc M. Discrete particle swarm optimization, illustrated by Traveling Salesman Problem.in: Godfrey C. Onwubolu and B. V. Babu, eds.. New optimization techniques in engineering.Heidelberg, Germany: Springer-Verlag Publishers, 2004. 219～239
[39] Jiang J Q, Liang Y C, Shi X H, et al. A hybrid algorithm based on PSO and SA and its applicationfor two-dimensional non-guillotine cutting stock problem. Lecture Notes in Computer Science,2004, 3037:666～669
[40]刘飞,孙明,李宁,等.粒子群算法及其在布局优化中的应用.计算机工程与应用, 2004,40(12):71～73,93
[41]周驰,高亮,高海兵.基于粒子群优化算法的约束布局优化.控制与决策, 2005, 20(1):36～40
[42] Venayagamoorthy G K, Smith S C, Singhal G. Particle swarm-based optimal partitioning al-gorithm for combinational CMOS circuits. Engineering Applications of Artificial Intelligence,2007, 20(2):177～184
[43] Sha D Y, Hsu C Y. A hybrid particle swarm optimization for job shop scheduling problem.Computers and Industrial Engineering, 2006, 51(4):791～808
[44] Lian Z, Jiao B, Gu X. A similar particle swarm optimization algorithm for job-shop schedulingto minimize makespan. Applied Mathematics and Computation, 2006, 183(2):1008～1017
[45] Dorigo M, Maniezzo V, Colorni A. Positive feedback as a search strategy. Technical report,Dipartimento di Elettronica, Politecnico di Milano, Italy, 1991
[46] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents.IEEE Transactions on Systems, Man and Cybernetics, Part B, 1996, 26(1):29～41
[47] Dorigo M, Gambardella L M. Ant colony system: a cooperative learning approach to the travel-ing salesman problem. IEEE Transactions on Evolutionary Computation, 1997, 1(1):53～66
[48] Colorni A, Dorigo M, Maniezzo V. Ant colony system for job-shop scheduling. Belgian Journalof Operations Research Statistics and Computer Science, 1994, 34(1):39～53
[49] Kuntz P, Layzell P, Snyers D. A colony of ant-like agents for partitioning in VLSI technology.in: Harvey I, Husbands P, eds.. Proceedings of the 4th European Conference on Artificial Life.Boston. 1997. Cambridge, Massachusetts: MIT Press, 1997. 417～424
[50]高尚,侯志远.集合划分问题的蚁群算法.航空计算技术, 2006, 36(2):126～128
[51]张勇德,黄莎白.多目标优化问题的蚁群算法研究.控制与决策, 2005, 20(2):170～173
[52] Dorigo M, Stützle T. Ant Colony Optimization. Cambridge, Massachusetts, USA: MIT Press,2004
[53] Dorigo M, Blum C. Ant colony optimization theory: a survey. Theoretical Computer Science,2005, 344(2-3):243～278
[54] Young F Y, Wong D F. Slicing ?oorplans with pre-placed modules. in: Proceedings of the 1998IEEE/ACM International Conference on Computer Aided Design. San Jose, California, USA.1998. New York: ACM Press, 1998. 252～258
[55] Young F Y, Wong D F, Yang H H. Slicing ?oorplans with range constraints. IEEE Transactionson Computer-Aided Design of Integrated Circuits and Systems, 2000, 19(2):272～278
[56] Young F Y, Wong D F, Yang H H. On extending slicing ?oorplan to handle L/T-shaped modulesand abutment constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuitsand Systems, 2001, 20(6):800～807
[57] Yuen W S, Young F Y. Slicing ?oorplan with clustering constraints. in: Proceedings of the 2001Conference on Asia South Pacific Design Automation. Yokohama, Japan. 2001. New York:ACM Press, 2001. 503～508
[58] Guo P N, Cheng C K, Yoshimura T. An O-tree representation of non-slicing ?oorplan and itsapplication. in: Proceedings of the 36th ACM/IEEE Conference on Design Automation. NewOrleans, Louisiana, USA. 1999. New York: ACM Press, 1999. 268～273
[59] Pang Y, Balasa F, Lampaert K, et al. Block placement with symmetry constraints based on theO-tree non-slicing representation. in: Proceedings of the 37th ACM/IEEE Conference on DesignAutomation. Los Angeles, California, USA. 2000. New York: ACM Press, 2000. 464～467
[60] Balasa F. Modeling non-slicing ?oorplans with binary trees. in: Proceedings of the 2000IEEE/ACM International Conference on Computer-Aided Design. San Jose, California, USA.2000. Piscataway, New Jersey: IEEE Press, 2000. 13～16
[61] Chan H H, Markov I L. Practical slicing and non-slicing block-packing without simulated an-nealing. in: Proceedings of the 14th ACM Great Lakes Symposium on VLSI. Boston, Mas-sachusetts USA. 2004. New York: ACM Press, 2004. 282～287
[62] Wong D F, Liu C L. A new algorithm for ?oorplan design. in: Proceedings of the 23rdACM/IEEE Conference on Design Automation. Las Vegas, Nevada, USA.1986. Piscataway,New Jersey: IEEE Press, 1986. 101～107
[63] Murata H, Fujiyoshi K, Nakatake S, et al. Rectangle-packing-based module placement. in:Proceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design. SanJose, California, USA. 1995. Washington, DC: IEEE Computer Society, 1995. 472～479
[64] Nakatake S, Fujiyoshi K, Murata H, et al. Module placement on BSG-structure and IC layoutapplications. in: Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design. San Jose, California, USA. 1996. Washington, DC: IEEE Computer Society,1997. 484～491
[65] Murata H, Fujiyoshi K, Nakatake S, et al. VLSI module placement based on rectangle-packingby the sequence-pair. IEEE Transactions on Computer-Aided Design of Integrated Circuits andSystems, 1996, 15(12):1518～1524
[66] Murata H, Fujiyoshi K, Kaneko M. VLSI/PCB placement with obstacles based on sequencepair. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998,17(1):60～68
[67] Kang M, Dai W W M. Arbitrary rectilinear block packing based on sequence pair. in: Proceed-ings of the 1998 IEEE/ACM International Conference on Computer-Aided Design. San Jose,California, USA. 1998. New York: ACM Press, 1998. 259～266
[68] Ohmura T, Fujiyoshi K, Kodama C. Area optimization of packing represented by sequence-pair.in: Proceedings of the 2000 IEEE Asia-Pacific Conference on Circuits and Systems. Tianjin,China. 2000. Piscataway, New Jersey: IEEE Press, 2000. 813～816
[69] Tang X, Tian R, Wong D F. Fast evaluation of sequence pair in block placement by longestcommon subsequence computation. in: Proceedings of the Conference on Design, Automationand Test in Europe. Paris, France. 2000. New York: ACM Press, 2000. 106～111
[70] Tang X, Wong D F. FAST-SP, a fast algorithm for block placement based on sequence pair. in:Proceedings of the 2000 Conference on Asia and South Pacific Design Automation. Yokohama,Japan. 2001. New York: ACM Press, 2001. 521～526
[71] Lai J, Lin M S, Wang T C, et al. Module placement with boundary constraints using thesequence-pair representation. in: Proceedings of the 2001 Conference on Asia and South Pa-cific Design Automation. Yokohama, Japan. 2001. New York: ACM Press, 2001. 515～520
[72] Xu N, Hong X, Dong S, et al. TSCSP: tabu search algorithm for VLSI module placementbased on the clustering sequence-pair. in: Tang T A, Li W, Yu H, eds.. Proceedings of the5th International Conference on Advanced System Integrated Circuits. Beijing, China. 2003.Piscataway, New Jersey: IEEE Press, 2003. 306～310
[73]刘锐,洪先龙,董社勤,等.基于序列对表示的对齐约束模块布局算法(英文).软件学报,2003, 14(8):1418～1424
[74] Kang M, Dai W W M. General ?oorplanning with L-shaped, T-shaped and soft blocks based onbounded slicing grid structure. in: Proceedings of 1997 Asia and South Pacific Design Automa-tion Conference. Chiba, Japan. 1997. Piscataway, New Jersey: IEEE Press, 1997. 265～270
[75] Nakatake S, Furuya M, Kajitani Y. Module placement on BSG-structure with pre-placed mod-ules and rectilinear modules. in: Proceedings of 1998 Asia and South Pacific Design AutomationConference. Yokohama, Japan. 1998. Piscataway, New Jersey: IEEE Press, 1998. 571～576
[76]李翠超,严晓浪,于志伟.基于BSG模型的BBL布局.微电子学, 2000, 30(2):79～82
[77] Chen S, Hong X, Dong S, et al. An O(n log log n) algorithm for evaluation of bounded slice-line grid. in: Tang T A, Li W, Yu H, eds.. Proceedings of the 5th International Conference onAdvanced System Integrated Circuits. Beijing, China. 2003. Piscataway, New Jersey: IEEEPress, 2003. 208～211
[78] Hong X, Huang G, Cai Y, et al. Corner block list: an effective and efficient topological represen-tation of non-slicing ?oorplan. in: Proceedings of the 2000 IEEE/ACM International Conferenceon Computer-Aided Design. San Jose, California, USA. 2000. Piscataway, New Jersey: IEEEPress, 2000. 8～12
[79] Hong X, Dong S, Huang G, et al. A non-slicing ?oorplanning algorithm using corner block listtopological representation. in: Proceedings of the 2000 IEEE Asia-Pacific Conference on Cir-cuits and Systems. Tianjin, China. 2000. Piscataway, New Jersey: IEEE Press, 2000. 833～836
[80] Zhou S, Dong S, Cheng C, et al. ECBL: an extended corner block list with solution space in-cluding optimum placement. in: Proceedings of the 2001 International Symposium on PhysicalDesign. Sonoma, California, USA. 2001. New York: ACM Press, 2001. 150～155
[81] Ma Y, Hong X, Dong S, et al. A compact algorithm for placement design using corner block listrepresentation. in: Proceedings of the 4th International Conference on Advanced System Inte-grated Circuits. Shanghai, China. 2001. Piscataway, New Jersey: IEEE Press, 2001. 146～149
[82] Ma Y, Dong S, Hong X, et al. VLSI ?oorplanning with boundary constraints based on cornerblock list. in: Proceedings of the 2001 Conference on Asia and South Pacific Design Automa-tion. Yokohama, Japan. 2001. New York: ACM Press, 2001. 509～514
[83] Ma Y, Hong X, Dong S, et al. Floorplanning with abutment constraints and L-shaped/T-shapedblocks based on corner block list. in: Proceedings of the 38th Conference on Design Automation.Las Vegas, Nevada, USA. 2001. New York: ACM Press, 2001. 770～775
[84] Ma Y, Hong X, Dong S, et al. Floorplanning with abutment constraints based on corner blocklist. Integration, the VLSI journal, 2001, 31(1):65～77
[85]洪先龙,马昱春,董社勤,等.角模块序列布图表示及基于角模块序列表示的边界约束布图规划算法.中国科学(E辑), 2002, 32(3):409～418
[86] Ma Y, Hong X, Dong S, et al. Stairway compaction using corner block list and its applicationswith rectilinear blocks. in: Proceedings of the 2002 Conference on Asia South Pacific DesignAutomation/VLSI Design. Bangalore, India. 2002. Washington, DC: IEEE Computer Society,2002. 387～392
[87] Dhamdhere S, Zhou N, Wang T C. Module placement with pre-placed modules using the cornerblock list representation. in: Proceedings of the IEEE International Symposium on Circuits andSystems. Scottsdale, Arizona, USA. 2002. Piscataway, New Jersey: IEEE Press, 2002. I-349～I-352
[88] Zeng Y, Dong S, Hong X. Floorplanning with soft rectilinear blocks using corner block list.in: Tang T A, Li W, Yu H, eds.. Proceedings of the 5th International Conference on AdvancedSystem Integrated Circuits. Beijing, China. 2003. Piscataway, New Jersey: IEEE Press, 2003.356～359
[89] Ma Y, Hong X, Dong S, et al. Arbitrary convex and concave rectilinear block packing based oncorner block list. in: Proceedings of the 2003 International Symposium on Circuits and Systems.Bangkok,Thailand. 2003. Piscataway, New Jersey: IEEE Press, 2003. V-493～V-496
[90] Hong X, Dong S, Huang G, et al. Corner block list representation and its application to?oorplan optimization. IEEE Transactions on Circuits and Systems-II: Express Briefs, 2004,51(5):228～233
[91] Lin J M, Chang Y W. TCG : a transitive closure graph-based representation for non-slicing?oorplans. in: Proceedings of the 38th Conference on Design Automation. Las Vegas, Nevada,USA. 2001. New York: ACM Press, 2001. 764～769
[92] Lin J, Chang Y. TCG-S: orthogonal coupling of P*-admissible representations for general ?oor-plans. in: Proceedings of the 39th Conference on Design Automation. New Orleans, Louisiana,USA. 2002. New York: ACM Press, 2002. 842～847
[93] Lin J M, Chang Y W. TCG: a transitive closure graph-based representation for general?oorplans. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2005,13(2):288～292
[94] Lin J M, Chang Y W, Lin S P. Corner sequence——a P-admissible ?oorplan representation witha worst case linear-time packing scheme. IEEE Transactions on Very Large Integration (VLSI)Systems, 2003, 11(4):679～686
[95] Chang Y C, Chang Y W, Wu G M, et al. B*-trees: a new representation for non-slicing ?oor-plans. in: Proceedings of the 37th Conference on Design Automation. Los Angeles, California,USA. 2000. New York: ACM Press, 2000. 458～463
[96] Lee H C, Chang Y W, Hsu J M, et al. Multilevel ?oorplanning/placement for large-scale mod-ules using B*-trees. in: Proceedings of the 40th Conference on Design Automation. Anaheim,California, USA. 2003. New York: ACM Press, 2003. 812～817
[97] Chazelle B. The bottomn-left bin-packing heuristic: an efficient implementation. IEEE Ttans-actions on Computers, 1983, c-32(8):697～707
[98] Hopper E. Two-dimensional packing utilising evolutionary algorithm and other meta-heuristicmethods: [PhD Dissertation]. Cardiff University, UK, 2000
[99] Lesh N, Marks J, Mcmahon A, et al. New heuristic and interactive approaches to 2D rectangularstrip packing. ACM Journal of Experimental Algorithmics, 2005, 10:article no. 1.2, 1～18
[100] Tam Y, Wu Y L, Huang W, et al. An effective quasi-human based heuristic for solving rectanglepacking problem. in: Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems.Chiangmai, Thailand. 1998. Piscataway, New Jersey: IEEE Press, 1998. 137～140
[101] Yang Z, Dong S, Hong X, et al. VLSI placement with arbitrary rectilinear block with less?exibility first principles. in: Tang T A, Li W, Yu H, eds.. Proceedings of the 5th InternationalConference on Advanced System Integrated Circuits. Beijing, China. 2003. Piscataway, NewJersey: IEEE Press, 2003. 225～228
[102] Yang Z, Dong S, Hong X, et al. Arbitrary rectilinear block packing based on less ?exibility firstprinciples. Chinese Journal of Semiconductors, 2004, 25(11):1416～1422
[103] Dong S, Hong X, Wu Y L, et al. VLSI block placement using less ?exibility first principles. in:Proceedings of the 2001 Conference on Asia and South Pacific Design Automation. Yokohama,Japan. 2001. New York: ACM Press, 2001. 601～604
[104] Dong S, Hong X, Wu Y L, et al. VLSI placement with pre-placed modules based on less ?ex-ibility first principles. in: Proceedings of the 4th International Conference on Advanced Sys-tem Integrated Circuits. Shanghai, China. 2001. Piscataway, New Jersey: IEEE Press, 2001.106～109
[105] Dong S, Yang Z, Hong X, et al. Module placement based on quadratic programming and rect-angle packing using less ?exibility first principle. in: Proceedings of the 2004 InternationalSymposium on Circuits and Systems. Vancouver, Canada. 2004. Piscataway, New Jersey: IEEEPress, 2004. V-61～V-64
[106]黄文奇,詹叔浩.求解Packing问题的拟物方法.应用数学学报, 1979, 2(2):176～180
[107]黄文奇,朱虹,许向阳,等.求解方格packing问题的启发式算法.计算机学报, 1993,6(11):829～836
[108]康雁,黄文奇.求解圆形Packing问题的一个启发式算法.计算机研究与发展, 2002,39(4):410～414
[109]黄文奇,王瑞民.求解单位等边三角形Packing问题的占角算法.鄂州大学学报, 2000,7(2):1～3
[110]黄文奇,金人超.求解SAT问题的拟物拟人算法——Solar.中国科学(E辑), 1997,27(2):179～186
[111] Huang W, Jin R. Quasiphysical and quasisociological algorithm solar for solving SAT problem.Science in China, Series E (Technological Sciences), 1999, 42(5):485～493
[112]王磊,黄文奇.求解工件车间调度问题的一种新的邻域搜索算法.计算机学报, 2005,28(5):809～816
[113] Huang W, Liu J. Structure optimization in a three-dimensional off-lattice protein model.Biopolymers, 2006, 82(5):93～98
[114] Huang W, Chen M, Lu¨Z. Energy optimization for off-lattice protein folding. Physical ReviewE-Statistical, Nonlinear, and Soft Matter Physics, 2006, 74(4):041907–1～041907–6
[115] Hochbaum D, Maass W. Approximation schemes for covering and packing problems inimage processing and VLSI. Journal of the Association for Computing Machinery, 1985,32(1):130～136
[116] Huang W, Zhan S. A quasi-physical method of solving packing problems. Mathematical Re-views of American Mathematical Society, 1982, 82h:52002
[117]黄文奇.求解Covering问题的拟物方法——NP难度问题的一个处理途径.计算机学报,1989, 12(8):610～616
[118]黄文奇.处理NP难度问题的拟物和拟人方法.见:苏运霖,国际离散数学和算法研讨会议论文集.广州:暨南大学出版社, 1994. 89～91
[119] Huang W, Wang G. A quasi-mechanical method for solving the rectangle covering problem-an approach to tackling NP hard problems. Graphical Models and Image Processing, 1994,56(3):267～271
[120]黄文奇,许如初.求解NP-hard问题的拟人方法.江西师范大学学报(自然科学版), 1998,22(增刊):78
[121]黄文奇,许如初,陈卫东,等.求解packing及CNF-SAT问题的拟物拟人方法.华中理工大学学报, 1998, 26(9):5～7
[122] Huang W, Li Y, Ge′rard S, et al. A”learning from human”heuristic for solving unequal circlepacking problem. in: Hao J K, ed.. Proceedings of the First International Workshop on Heuris-tics. Beijing, China. 2002. Beijing: Tsinghua University Press, 2002. 39～45
[123] Huang W, Li Y, Jurkowiak B, et al. A two-level search strategy for packing unequal circles intoa circle container. Lecture Notes in Computer Science, 2003, 2833:868～872
[124]黄文奇,许如初.近世计算理论导引——NP难度问题的背景、前景及其求解算法研究.北京:科学出版社, 2004
[125]黄文奇,吕志鹏.求解蛋白质折叠问题的拟人算法:对PERM的改进.科学通报, 2004,49(17):1801～1804
[126] Berkey J O, Wang P Y. Two dimensional finite bin packing algorithms. Journal of the Opera-tional Research Society, 1987, 38(5):423～429
[127] Martello S, Vigo D. Exact solution of the two-dimensional finite bin packing problem. Manage-ment Science, 1998, 44(3):388～399
[128] Martello S, Monaci M, Vigo D. An exact approach to the strip-packing problem. INFORMSJournal on Computing, 2003, 15(3):310～319
[129] Iori M, Martello S, Monaci M. Metaheuristic algorithms for the strip packing problem. in:Pardalos PM, Korotkith V, eds.. Optimization and industry: new frontiers. Dordrecht: KluwerAcademic Publishers, 2003. 159～179
[130] Chan H H, Markov I L. http://vlsicad.eecs.umich.edu/BK/CompaSS/
[131]王小港,姚林声,甘骏人.一种有效的VLSI布图规划算法.微处理机, 2002, (1):4～7
[132] Beasley J E. An exact two-dimensional non-guillotine cutting tree search procedure. OperationsResearch, 1985, 33(1):49～64
[133] Fekete S P, Schepers J. A new exact algorithm for general orthogonal d-dimensional knapsackproblems. Lecture Notes in Computer Science, 1997, 1284:144～156
[134] Hadjiconstantinou E, Christofides N. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of Operational Research, 1995, 83(1):39～56
[135] Wang P Y. Two algorithms for constrained two-dimensional cutting stock problems. OperationsResearch, 1983, 31(3):573～586
[136] Christofides N, Whitlock C. An algorithm for two-dimensional cutting problems. OperationsResearch, 1977, 25(1):30～44
[137] Kolesar P J. A branch and bound algorithm for the knapsack problem. Management Science,1967, 13(9):723～735
[2] Dowsland K A, Dowsland W B. Packing problems. European Journal of Operational Research,1992, 56(1):2～14
[3] Alvarez-Valdes R, Parren?o F, Tamarit J M. A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems. Journal of the Operational Research Society, 2005,56(4):414～425
[4] Alvarez-Valdes R, Parren?o F, Tamarit J M. A tabu search algorithm for a two-dimensional non-guillotine cutting problem. European Journal of Operational Research,doi:10.1016/j.ejor.2005.11.068
[5] Beasley J E. A population heuristic for constrained two-dimensional non-guillotine cutting.European Journal of Operational Research, 2004, 156(3):601～627
[6] Bortfeldt A. A genetic algorithm for the two-dimensional strip packing problem with rectangularpieces. European Journal of Operational Research, 2006, 172(3):814～837
[7] Burke E K, Kendall G, Whitewell G. A new placement heuristic for the orthogonal stock-cuttingproblem. Operations Research, 2004, 52(4):655～671
[8] Caprara A, Monaci M. On the two-dimensional knapsack problem. Operations Research Letters,2004, 32(1):5～14
[9] Gonc?alves J F. A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packingproblem. European Journal of Operational Research, doi:10.1016/j.ejor.2005.11.062
[10] Jansen K, Zhang G. On rectangle packing: maximizing benefits. in: Munro J I, ed.. Proceed-ings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. New Orleans,Louisiana, USA. 2004. Philadelphia, Pennsylvania: Society for Industrial and Applied Mathe-matics, 2004. 204～213
[11] Zhang D, Deng A. A hybrid heuristic algorithm for the rectangular packing problem. LectureNotes in Computer Science, 2005, 3514:783～791
[12] Wu Y L, Huang W, Lau S C, et al. An effective quasi-human based heuristic for solving therectangle packing problem. European Journal of Operational Research, 2002, 141(2):341～358
[13] Baker B S, Coffman E G, Rivest R L. Orthogonal packings in two dimensions. SIAM Journalon Computing, 1980, 9(4):846～855
[14] Hopper E, Turton B C H. An empirical investigation of meta-heuristic and heuristic algorithmfor a 2D packing problem. European Journal of Operational Research, 2001, 128(1):34～57
[15] Hifi M, M’Hallah R. A hybrid algorithm for the two-dimensional layout problem: the casesof regular and irregular shapes. International Transactions in Operational Research, 2003,10(3):195～216
[16] Zhang D, Deng A. An effective hybrid algorithm for the problem of packing circles into a largercontaining circle. Computers & Operations Research, 2005, 32(8):1941～1951
[17] Zhang D, Liu Y, Chen S, et al. A meta-heuristic algorithm for the strip rectangular packingproblem. Lecture Notes in Computer Science, 2005, 3612:1235～1241
[18] Hadjiconstantinou E, Iori M. A hybrid genetic algorithm for the two-dimensionalsingle large object placement problem. European Journal of Operational Research,doi:10.1016/j.ejor.2005.11.061
[19]许如初,黄文奇.解不等圆packing问题拟物拟人算法初态选取.华中理工大学学报, 1998,26(4):1～3
[20] Huang W, Xu R. Two personification strategies for solving circles packing problem. Science inChina, Series E (Technological Sciences), 1999, 42(6):595～602
[21] Huang W, Kang Y. A heuristic quasi-physical strategy for solving disks packing problem. Sim-ulation Modelling Practice and Theory, 2002, 10(3-4):195～207
[22] Huang W, Li Y, Akeb H, et al. Greedy algorithms for packing unequal circles into a rectangularcontainer. Journal of the Operational Research Society, 2005, 56(5):539～548
[23] Huang W, Li Y, Li C, et al. New heuristics for packing unequal circles into a circular container.Computers & Operations Research, 2006, 33(8):2125～2142
[24]黄文奇,刘景发.基于欧氏距离的矩形Packing问题的确定性启发式求解算法.计算机学报,2006, 29(5):734～739
[25] Holland J. Adaptation in natural and artificial systems. Ann Arbor: University of MichiganPress, 1975
[26] De Jong K. An analysis of the behavior of a class of genetic adaptive systems: [PhD Disserta-tion]. University of Michigan, 1975
[27] Goldberg D E. Genetic algorithms in search, optimization and machine learning. ReadingMassachusetts: Addison-Wesley Publishing Company, 1989
[28] Davis L. Applying adaptive algorithms to epistatic domains. in: Joshi A K, ed.. Proceedingsof the International Joint Conference on Artificial Intelligence. Los Angeles, California, USA.1985. San Francisco, California: Morgan Kaufmann Publishers, 1985. 162～164
[29] Goldberg D E, Lingle R. Alleles, loci and the traveling salesman problem. in: GrefenstetteJ J, ed.. Proceedings of the 1st International Conference on Genetic Algorithms. Pittsburgh,Pennsylvania, USA. 1985. Hillside, New Jersey: Lawrence Erlbaum Associates Publishers,1985. 154～159
[30] Oliver I M, Smith D J, Holland J. A study of permutation crossover operators on the travelingsalesman problem. in: Grefenstette J J, ed.. Proceedings of the 2nd International Conference onGenetic Algorithms. Cambridge, Massachusetts, USA. 1987. Hillside, New Jersey: LawrenceErlbaum Associates Publishers, 1987. 224～230
[31] Shahookar K, Mazumder P. VLSI cell placement techniques. ACM Computing Surveys, 1991,23(2):143～220
[32] Jakobs S. On genetic algorithms for the packing of polygons. European Journal of OperationalResearch, 1996, 88(1):165～181
[33] Sechen C. Chip-planning, placement, and global routing of macro/custom cell integrated cir-cuits using simulated annealing. in: Proceedings of the 25th ACM/IEEE Conference on DesignAutomation. New Jersey, USA. 1988. Los Alamitos, California: IEEE Computer Society Press,1988. 73～80
[34] Kennedy J, Eberhart R C. Particle swarm optimization. in: Proceedings of IEEE InternationalConference on Neural Networks. Perth, Australia. 1995. Piscataway, New Jersey: IEEE Press,1995. 1942～1948
[35] Clerc M, Kennedy J. The particle swarm—explosion, stability, and convergence in a multidi-mensional complex space. IEEE Transactions on Evolutionary Computation, 2002, 6(1):58～73
[36]雷秀娟,史忠科,王来军,等.粒子群优化算法在多目标优化中的应用与仿真.计算机工程与应用, 2006, 42(2):28～29
[37] Eberhart R C, Shi Y. Particle swarm optimization: developments, applications and resources. in:Furuhashi T, Mckay B, eds.. Proceedings of the 2001 Congress on Evolutionary Computation.Seoul, South Korea. 2001. Piscataway, New Jersey: IEEE Press, 2001. 81～86
[38] Clerc M. Discrete particle swarm optimization, illustrated by Traveling Salesman Problem.in: Godfrey C. Onwubolu and B. V. Babu, eds.. New optimization techniques in engineering.Heidelberg, Germany: Springer-Verlag Publishers, 2004. 219～239
[39] Jiang J Q, Liang Y C, Shi X H, et al. A hybrid algorithm based on PSO and SA and its applicationfor two-dimensional non-guillotine cutting stock problem. Lecture Notes in Computer Science,2004, 3037:666～669
[40]刘飞,孙明,李宁,等.粒子群算法及其在布局优化中的应用.计算机工程与应用, 2004,40(12):71～73,93
[41]周驰,高亮,高海兵.基于粒子群优化算法的约束布局优化.控制与决策, 2005, 20(1):36～40
[42] Venayagamoorthy G K, Smith S C, Singhal G. Particle swarm-based optimal partitioning al-gorithm for combinational CMOS circuits. Engineering Applications of Artificial Intelligence,2007, 20(2):177～184
[43] Sha D Y, Hsu C Y. A hybrid particle swarm optimization for job shop scheduling problem.Computers and Industrial Engineering, 2006, 51(4):791～808
[44] Lian Z, Jiao B, Gu X. A similar particle swarm optimization algorithm for job-shop schedulingto minimize makespan. Applied Mathematics and Computation, 2006, 183(2):1008～1017
[45] Dorigo M, Maniezzo V, Colorni A. Positive feedback as a search strategy. Technical report,Dipartimento di Elettronica, Politecnico di Milano, Italy, 1991
[46] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents.IEEE Transactions on Systems, Man and Cybernetics, Part B, 1996, 26(1):29～41
[47] Dorigo M, Gambardella L M. Ant colony system: a cooperative learning approach to the travel-ing salesman problem. IEEE Transactions on Evolutionary Computation, 1997, 1(1):53～66
[48] Colorni A, Dorigo M, Maniezzo V. Ant colony system for job-shop scheduling. Belgian Journalof Operations Research Statistics and Computer Science, 1994, 34(1):39～53
[49] Kuntz P, Layzell P, Snyers D. A colony of ant-like agents for partitioning in VLSI technology.in: Harvey I, Husbands P, eds.. Proceedings of the 4th European Conference on Artificial Life.Boston. 1997. Cambridge, Massachusetts: MIT Press, 1997. 417～424
[50]高尚,侯志远.集合划分问题的蚁群算法.航空计算技术, 2006, 36(2):126～128
[51]张勇德,黄莎白.多目标优化问题的蚁群算法研究.控制与决策, 2005, 20(2):170～173
[52] Dorigo M, Stützle T. Ant Colony Optimization. Cambridge, Massachusetts, USA: MIT Press,2004
[53] Dorigo M, Blum C. Ant colony optimization theory: a survey. Theoretical Computer Science,2005, 344(2-3):243～278
[54] Young F Y, Wong D F. Slicing ?oorplans with pre-placed modules. in: Proceedings of the 1998IEEE/ACM International Conference on Computer Aided Design. San Jose, California, USA.1998. New York: ACM Press, 1998. 252～258
[55] Young F Y, Wong D F, Yang H H. Slicing ?oorplans with range constraints. IEEE Transactionson Computer-Aided Design of Integrated Circuits and Systems, 2000, 19(2):272～278
[56] Young F Y, Wong D F, Yang H H. On extending slicing ?oorplan to handle L/T-shaped modulesand abutment constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuitsand Systems, 2001, 20(6):800～807
[57] Yuen W S, Young F Y. Slicing ?oorplan with clustering constraints. in: Proceedings of the 2001Conference on Asia South Pacific Design Automation. Yokohama, Japan. 2001. New York:ACM Press, 2001. 503～508
[58] Guo P N, Cheng C K, Yoshimura T. An O-tree representation of non-slicing ?oorplan and itsapplication. in: Proceedings of the 36th ACM/IEEE Conference on Design Automation. NewOrleans, Louisiana, USA. 1999. New York: ACM Press, 1999. 268～273
[59] Pang Y, Balasa F, Lampaert K, et al. Block placement with symmetry constraints based on theO-tree non-slicing representation. in: Proceedings of the 37th ACM/IEEE Conference on DesignAutomation. Los Angeles, California, USA. 2000. New York: ACM Press, 2000. 464～467
[60] Balasa F. Modeling non-slicing ?oorplans with binary trees. in: Proceedings of the 2000IEEE/ACM International Conference on Computer-Aided Design. San Jose, California, USA.2000. Piscataway, New Jersey: IEEE Press, 2000. 13～16
[61] Chan H H, Markov I L. Practical slicing and non-slicing block-packing without simulated an-nealing. in: Proceedings of the 14th ACM Great Lakes Symposium on VLSI. Boston, Mas-sachusetts USA. 2004. New York: ACM Press, 2004. 282～287
[62] Wong D F, Liu C L. A new algorithm for ?oorplan design. in: Proceedings of the 23rdACM/IEEE Conference on Design Automation. Las Vegas, Nevada, USA.1986. Piscataway,New Jersey: IEEE Press, 1986. 101～107
[63] Murata H, Fujiyoshi K, Nakatake S, et al. Rectangle-packing-based module placement. in:Proceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design. SanJose, California, USA. 1995. Washington, DC: IEEE Computer Society, 1995. 472～479
[64] Nakatake S, Fujiyoshi K, Murata H, et al. Module placement on BSG-structure and IC layoutapplications. in: Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design. San Jose, California, USA. 1996. Washington, DC: IEEE Computer Society,1997. 484～491
[65] Murata H, Fujiyoshi K, Nakatake S, et al. VLSI module placement based on rectangle-packingby the sequence-pair. IEEE Transactions on Computer-Aided Design of Integrated Circuits andSystems, 1996, 15(12):1518～1524
[66] Murata H, Fujiyoshi K, Kaneko M. VLSI/PCB placement with obstacles based on sequencepair. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998,17(1):60～68
[67] Kang M, Dai W W M. Arbitrary rectilinear block packing based on sequence pair. in: Proceed-ings of the 1998 IEEE/ACM International Conference on Computer-Aided Design. San Jose,California, USA. 1998. New York: ACM Press, 1998. 259～266
[68] Ohmura T, Fujiyoshi K, Kodama C. Area optimization of packing represented by sequence-pair.in: Proceedings of the 2000 IEEE Asia-Pacific Conference on Circuits and Systems. Tianjin,China. 2000. Piscataway, New Jersey: IEEE Press, 2000. 813～816
[69] Tang X, Tian R, Wong D F. Fast evaluation of sequence pair in block placement by longestcommon subsequence computation. in: Proceedings of the Conference on Design, Automationand Test in Europe. Paris, France. 2000. New York: ACM Press, 2000. 106～111
[70] Tang X, Wong D F. FAST-SP, a fast algorithm for block placement based on sequence pair. in:Proceedings of the 2000 Conference on Asia and South Pacific Design Automation. Yokohama,Japan. 2001. New York: ACM Press, 2001. 521～526
[71] Lai J, Lin M S, Wang T C, et al. Module placement with boundary constraints using thesequence-pair representation. in: Proceedings of the 2001 Conference on Asia and South Pa-cific Design Automation. Yokohama, Japan. 2001. New York: ACM Press, 2001. 515～520
[72] Xu N, Hong X, Dong S, et al. TSCSP: tabu search algorithm for VLSI module placementbased on the clustering sequence-pair. in: Tang T A, Li W, Yu H, eds.. Proceedings of the5th International Conference on Advanced System Integrated Circuits. Beijing, China. 2003.Piscataway, New Jersey: IEEE Press, 2003. 306～310
[73]刘锐,洪先龙,董社勤,等.基于序列对表示的对齐约束模块布局算法(英文).软件学报,2003, 14(8):1418～1424
[74] Kang M, Dai W W M. General ?oorplanning with L-shaped, T-shaped and soft blocks based onbounded slicing grid structure. in: Proceedings of 1997 Asia and South Pacific Design Automa-tion Conference. Chiba, Japan. 1997. Piscataway, New Jersey: IEEE Press, 1997. 265～270
[75] Nakatake S, Furuya M, Kajitani Y. Module placement on BSG-structure with pre-placed mod-ules and rectilinear modules. in: Proceedings of 1998 Asia and South Pacific Design AutomationConference. Yokohama, Japan. 1998. Piscataway, New Jersey: IEEE Press, 1998. 571～576
[76]李翠超,严晓浪,于志伟.基于BSG模型的BBL布局.微电子学, 2000, 30(2):79～82
[77] Chen S, Hong X, Dong S, et al. An O(n log log n) algorithm for evaluation of bounded slice-line grid. in: Tang T A, Li W, Yu H, eds.. Proceedings of the 5th International Conference onAdvanced System Integrated Circuits. Beijing, China. 2003. Piscataway, New Jersey: IEEEPress, 2003. 208～211
[78] Hong X, Huang G, Cai Y, et al. Corner block list: an effective and efficient topological represen-tation of non-slicing ?oorplan. in: Proceedings of the 2000 IEEE/ACM International Conferenceon Computer-Aided Design. San Jose, California, USA. 2000. Piscataway, New Jersey: IEEEPress, 2000. 8～12
[79] Hong X, Dong S, Huang G, et al. A non-slicing ?oorplanning algorithm using corner block listtopological representation. in: Proceedings of the 2000 IEEE Asia-Pacific Conference on Cir-cuits and Systems. Tianjin, China. 2000. Piscataway, New Jersey: IEEE Press, 2000. 833～836
[80] Zhou S, Dong S, Cheng C, et al. ECBL: an extended corner block list with solution space in-cluding optimum placement. in: Proceedings of the 2001 International Symposium on PhysicalDesign. Sonoma, California, USA. 2001. New York: ACM Press, 2001. 150～155
[81] Ma Y, Hong X, Dong S, et al. A compact algorithm for placement design using corner block listrepresentation. in: Proceedings of the 4th International Conference on Advanced System Inte-grated Circuits. Shanghai, China. 2001. Piscataway, New Jersey: IEEE Press, 2001. 146～149
[82] Ma Y, Dong S, Hong X, et al. VLSI ?oorplanning with boundary constraints based on cornerblock list. in: Proceedings of the 2001 Conference on Asia and South Pacific Design Automa-tion. Yokohama, Japan. 2001. New York: ACM Press, 2001. 509～514
[83] Ma Y, Hong X, Dong S, et al. Floorplanning with abutment constraints and L-shaped/T-shapedblocks based on corner block list. in: Proceedings of the 38th Conference on Design Automation.Las Vegas, Nevada, USA. 2001. New York: ACM Press, 2001. 770～775
[84] Ma Y, Hong X, Dong S, et al. Floorplanning with abutment constraints based on corner blocklist. Integration, the VLSI journal, 2001, 31(1):65～77
[85]洪先龙,马昱春,董社勤,等.角模块序列布图表示及基于角模块序列表示的边界约束布图规划算法.中国科学(E辑), 2002, 32(3):409～418
[86] Ma Y, Hong X, Dong S, et al. Stairway compaction using corner block list and its applicationswith rectilinear blocks. in: Proceedings of the 2002 Conference on Asia South Pacific DesignAutomation/VLSI Design. Bangalore, India. 2002. Washington, DC: IEEE Computer Society,2002. 387～392
[87] Dhamdhere S, Zhou N, Wang T C. Module placement with pre-placed modules using the cornerblock list representation. in: Proceedings of the IEEE International Symposium on Circuits andSystems. Scottsdale, Arizona, USA. 2002. Piscataway, New Jersey: IEEE Press, 2002. I-349～I-352
[88] Zeng Y, Dong S, Hong X. Floorplanning with soft rectilinear blocks using corner block list.in: Tang T A, Li W, Yu H, eds.. Proceedings of the 5th International Conference on AdvancedSystem Integrated Circuits. Beijing, China. 2003. Piscataway, New Jersey: IEEE Press, 2003.356～359
[89] Ma Y, Hong X, Dong S, et al. Arbitrary convex and concave rectilinear block packing based oncorner block list. in: Proceedings of the 2003 International Symposium on Circuits and Systems.Bangkok,Thailand. 2003. Piscataway, New Jersey: IEEE Press, 2003. V-493～V-496
[90] Hong X, Dong S, Huang G, et al. Corner block list representation and its application to?oorplan optimization. IEEE Transactions on Circuits and Systems-II: Express Briefs, 2004,51(5):228～233
[91] Lin J M, Chang Y W. TCG : a transitive closure graph-based representation for non-slicing?oorplans. in: Proceedings of the 38th Conference on Design Automation. Las Vegas, Nevada,USA. 2001. New York: ACM Press, 2001. 764～769
[92] Lin J, Chang Y. TCG-S: orthogonal coupling of P*-admissible representations for general ?oor-plans. in: Proceedings of the 39th Conference on Design Automation. New Orleans, Louisiana,USA. 2002. New York: ACM Press, 2002. 842～847
[93] Lin J M, Chang Y W. TCG: a transitive closure graph-based representation for general?oorplans. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2005,13(2):288～292
[94] Lin J M, Chang Y W, Lin S P. Corner sequence——a P-admissible ?oorplan representation witha worst case linear-time packing scheme. IEEE Transactions on Very Large Integration (VLSI)Systems, 2003, 11(4):679～686
[95] Chang Y C, Chang Y W, Wu G M, et al. B*-trees: a new representation for non-slicing ?oor-plans. in: Proceedings of the 37th Conference on Design Automation. Los Angeles, California,USA. 2000. New York: ACM Press, 2000. 458～463
[96] Lee H C, Chang Y W, Hsu J M, et al. Multilevel ?oorplanning/placement for large-scale mod-ules using B*-trees. in: Proceedings of the 40th Conference on Design Automation. Anaheim,California, USA. 2003. New York: ACM Press, 2003. 812～817
[97] Chazelle B. The bottomn-left bin-packing heuristic: an efficient implementation. IEEE Ttans-actions on Computers, 1983, c-32(8):697～707
[98] Hopper E. Two-dimensional packing utilising evolutionary algorithm and other meta-heuristicmethods: [PhD Dissertation]. Cardiff University, UK, 2000
[99] Lesh N, Marks J, Mcmahon A, et al. New heuristic and interactive approaches to 2D rectangularstrip packing. ACM Journal of Experimental Algorithmics, 2005, 10:article no. 1.2, 1～18
[100] Tam Y, Wu Y L, Huang W, et al. An effective quasi-human based heuristic for solving rectanglepacking problem. in: Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems.Chiangmai, Thailand. 1998. Piscataway, New Jersey: IEEE Press, 1998. 137～140
[101] Yang Z, Dong S, Hong X, et al. VLSI placement with arbitrary rectilinear block with less?exibility first principles. in: Tang T A, Li W, Yu H, eds.. Proceedings of the 5th InternationalConference on Advanced System Integrated Circuits. Beijing, China. 2003. Piscataway, NewJersey: IEEE Press, 2003. 225～228
[102] Yang Z, Dong S, Hong X, et al. Arbitrary rectilinear block packing based on less ?exibility firstprinciples. Chinese Journal of Semiconductors, 2004, 25(11):1416～1422
[103] Dong S, Hong X, Wu Y L, et al. VLSI block placement using less ?exibility first principles. in:Proceedings of the 2001 Conference on Asia and South Pacific Design Automation. Yokohama,Japan. 2001. New York: ACM Press, 2001. 601～604
[104] Dong S, Hong X, Wu Y L, et al. VLSI placement with pre-placed modules based on less ?ex-ibility first principles. in: Proceedings of the 4th International Conference on Advanced Sys-tem Integrated Circuits. Shanghai, China. 2001. Piscataway, New Jersey: IEEE Press, 2001.106～109
[105] Dong S, Yang Z, Hong X, et al. Module placement based on quadratic programming and rect-angle packing using less ?exibility first principle. in: Proceedings of the 2004 InternationalSymposium on Circuits and Systems. Vancouver, Canada. 2004. Piscataway, New Jersey: IEEEPress, 2004. V-61～V-64
[106]黄文奇,詹叔浩.求解Packing问题的拟物方法.应用数学学报, 1979, 2(2):176～180
[107]黄文奇,朱虹,许向阳,等.求解方格packing问题的启发式算法.计算机学报, 1993,6(11):829～836
[108]康雁,黄文奇.求解圆形Packing问题的一个启发式算法.计算机研究与发展, 2002,39(4):410～414
[109]黄文奇,王瑞民.求解单位等边三角形Packing问题的占角算法.鄂州大学学报, 2000,7(2):1～3
[110]黄文奇,金人超.求解SAT问题的拟物拟人算法——Solar.中国科学(E辑), 1997,27(2):179～186
[111] Huang W, Jin R. Quasiphysical and quasisociological algorithm solar for solving SAT problem.Science in China, Series E (Technological Sciences), 1999, 42(5):485～493
[112]王磊,黄文奇.求解工件车间调度问题的一种新的邻域搜索算法.计算机学报, 2005,28(5):809～816
[113] Huang W, Liu J. Structure optimization in a three-dimensional off-lattice protein model.Biopolymers, 2006, 82(5):93～98
[114] Huang W, Chen M, Lu¨Z. Energy optimization for off-lattice protein folding. Physical ReviewE-Statistical, Nonlinear, and Soft Matter Physics, 2006, 74(4):041907–1～041907–6
[115] Hochbaum D, Maass W. Approximation schemes for covering and packing problems inimage processing and VLSI. Journal of the Association for Computing Machinery, 1985,32(1):130～136
[116] Huang W, Zhan S. A quasi-physical method of solving packing problems. Mathematical Re-views of American Mathematical Society, 1982, 82h:52002
[117]黄文奇.求解Covering问题的拟物方法——NP难度问题的一个处理途径.计算机学报,1989, 12(8):610～616
[118]黄文奇.处理NP难度问题的拟物和拟人方法.见:苏运霖,国际离散数学和算法研讨会议论文集.广州:暨南大学出版社, 1994. 89～91
[119] Huang W, Wang G. A quasi-mechanical method for solving the rectangle covering problem-an approach to tackling NP hard problems. Graphical Models and Image Processing, 1994,56(3):267～271
[120]黄文奇,许如初.求解NP-hard问题的拟人方法.江西师范大学学报(自然科学版), 1998,22(增刊):78
[121]黄文奇,许如初,陈卫东,等.求解packing及CNF-SAT问题的拟物拟人方法.华中理工大学学报, 1998, 26(9):5～7
[122] Huang W, Li Y, Ge′rard S, et al. A”learning from human”heuristic for solving unequal circlepacking problem. in: Hao J K, ed.. Proceedings of the First International Workshop on Heuris-tics. Beijing, China. 2002. Beijing: Tsinghua University Press, 2002. 39～45
[123] Huang W, Li Y, Jurkowiak B, et al. A two-level search strategy for packing unequal circles intoa circle container. Lecture Notes in Computer Science, 2003, 2833:868～872
[124]黄文奇,许如初.近世计算理论导引——NP难度问题的背景、前景及其求解算法研究.北京:科学出版社, 2004
[125]黄文奇,吕志鹏.求解蛋白质折叠问题的拟人算法:对PERM的改进.科学通报, 2004,49(17):1801～1804
[126] Berkey J O, Wang P Y. Two dimensional finite bin packing algorithms. Journal of the Opera-tional Research Society, 1987, 38(5):423～429
[127] Martello S, Vigo D. Exact solution of the two-dimensional finite bin packing problem. Manage-ment Science, 1998, 44(3):388～399
[128] Martello S, Monaci M, Vigo D. An exact approach to the strip-packing problem. INFORMSJournal on Computing, 2003, 15(3):310～319
[129] Iori M, Martello S, Monaci M. Metaheuristic algorithms for the strip packing problem. in:Pardalos PM, Korotkith V, eds.. Optimization and industry: new frontiers. Dordrecht: KluwerAcademic Publishers, 2003. 159～179
[130] Chan H H, Markov I L. http://vlsicad.eecs.umich.edu/BK/CompaSS/
[131]王小港,姚林声,甘骏人.一种有效的VLSI布图规划算法.微处理机, 2002, (1):4～7
[132] Beasley J E. An exact two-dimensional non-guillotine cutting tree search procedure. OperationsResearch, 1985, 33(1):49～64
[133] Fekete S P, Schepers J. A new exact algorithm for general orthogonal d-dimensional knapsackproblems. Lecture Notes in Computer Science, 1997, 1284:144～156
[134] Hadjiconstantinou E, Christofides N. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of Operational Research, 1995, 83(1):39～56
[135] Wang P Y. Two algorithms for constrained two-dimensional cutting stock problems. OperationsResearch, 1983, 31(3):573～586
[136] Christofides N, Whitlock C. An algorithm for two-dimensional cutting problems. OperationsResearch, 1977, 25(1):30～44
[137] Kolesar P J. A branch and bound algorithm for the knapsack problem. Management Science,1967, 13(9):723～735