卫星舱布局问题的智能求解方法研究
摘要
本文针对复杂的卫星舱布局优化设计问题,采用现代智能优化技术,研究了多种布局情形,多种布局方法,并通过算例验证了这些方法的良好性能。
首先介绍了布局优化问题的背景,指出充分利用问题本身的启发式信息有利于求解卫星舱布局优化问题。本着从简单到复杂的原则,分别对卫星舱二维圆形布局问题、卫星舱二维多边形布局问题、以及卫星舱三维布局问题展开研究。
针对卫星舱二维圆形布局问题,改进了现有的计算模型,将多目标优化问题分为两个步骤求解。第一个步骤中引进一般圆形布局问题中基于快速下降法的局部搜索方法,第二个步骤考虑平衡约束。为了得到近似全局最优解,采用多次迭代方法,从多点出发求解。通过在测试集上的计算,表明本文的处理方法相对于文献中的方法有更好的性能。
其次,给出了卫星舱二维圆形布局问题的构造方法。该方法在定位规则的约束下,逐个布置每个布局物的位置。因为采用不同的定位次序会得到不同的布局质量,本文采用了粒子群优化算法、遗传算法、以及蚁群优化算法等三种方法来进行定位次序的全局优化搜索。在相同的测试集上,构造法的计算效果对比最速下降法有进一步的提高。
随后,研究了卫星舱二维多边形布局问题。在以定量的方式定义了多边形的覆盖之后,采用模拟退火方法进行覆盖量和不平衡量的优化。设计了一个可计算出理论最优值的多边形布局物测试集,该测试集既包含凸多边形布局物,也包含凹多边形布局物。在该测试集上的计算表明,在布局物数目不多的情况下,算法能保证所求布局解的性能。通过在一个现有的矩形布局物的测试集上的计算,表明算法的性能优于文献中的遗传算法。
最后,综合二维计算的研究成果,给出了卫星舱三维布局问题的求解方法。利用启发式方法将布局物分成两个集合,采用模拟退火方法对每个集合中的布局物在卫星舱中进行布局优化计算。利用五个测试算例,验证了方法的可行性。与现有算法相比,本文的算法具有优势。
简言之,本文针对卫星舱布局优化问题的多种模型,采用了多种方法进行计算。本文的计算结果表明,采用启发式方法,结合元启发式方法,是求解卫星舱复杂布局优化问题的有力手段。
The main topic of this thesis is solving the layout optimization problems in satellite by the modern intelligent computation methods. Several models and a series of methods for the problems are studied. The performances of these methods are investigated by the computations on some benchmarks.
We begin the thesis by introducing the background of the general layout optimization problems, and then we point out reasonably that making full use of the heuristic information of the problems themselves is conducive to solving them. Under the problem-solving philosophy of from simple to complex, we first study the two-dimensional layout problem in satellite, in which the packed objects are circular. Then we continue to study the cases of packing polygon objects. Finally, we extend the research to the three -dimensional problems.
For the two-dimensional problem of packing circular objects in satellite, we first modify the existed computational models in order that we can solve the problem in two steps. In the first step, we use the existed local search algorithm for the general circle packing problem, which is based on the gradient descent method, to obtain a layout without overlaps. In the second step, we concern the balance issue. To search for the global optimal solution, we run the two-step optimization multiple times and each time the algorithm starts from different point. The computation on the benchmarks shows that our method has better performance than literatures.
Secondly, we invent a constructive heuristic for the two-dimensional problem of packing circular objects. In the constructive heuristic, the objects are positioned in a sequence by the construction rules. Because different positioning sequences can result in layouts with different quality, we develop three meta-heuristics to search for the optimal positioning sequence, including the discrete particle swarm algorithm, the genetic algorithm, and the ant colony algorithm. On the same benchmarks, the new methods outperform the two-step optimization introduced above.
Next, we study the two-dimensional problem of packing polygon objects. We first define the measurement of the overlaps between the polygons, and then we use simulated annealing method to optimize the overlaps and the unbalance. We design a benchmark for the problem, in which the theoretical solution for each instance is known. The results on the benchmark show that the algorithm has good performance if the amount of objects is not very large. On another old benchmark for packing rectangle objects, the algorithm shows better performance than the genetic algorithm in literature.
At last, we integrate the techniques on the two-dimensional problems, and apply them on the three-dimensional problem. We provide a heuristic to divide the objects into two sets, and then use the simulated annealing to pack the objects in each set on the two packing spaces of the satellite. The algorithm is tested on a 5-instance benchmark, and the results show that the solving strategy is feasible and able to compete with other existed algorithms.
In short, we studied several models for the packing problems in satellite, and provide some algorithms for them. Our researches demonstrate that combination of the heuristic method and meta-heuristic method is a powerful tool for the layout problems in satellite.
首先介绍了布局优化问题的背景,指出充分利用问题本身的启发式信息有利于求解卫星舱布局优化问题。本着从简单到复杂的原则,分别对卫星舱二维圆形布局问题、卫星舱二维多边形布局问题、以及卫星舱三维布局问题展开研究。
针对卫星舱二维圆形布局问题,改进了现有的计算模型,将多目标优化问题分为两个步骤求解。第一个步骤中引进一般圆形布局问题中基于快速下降法的局部搜索方法,第二个步骤考虑平衡约束。为了得到近似全局最优解,采用多次迭代方法,从多点出发求解。通过在测试集上的计算,表明本文的处理方法相对于文献中的方法有更好的性能。
其次,给出了卫星舱二维圆形布局问题的构造方法。该方法在定位规则的约束下,逐个布置每个布局物的位置。因为采用不同的定位次序会得到不同的布局质量,本文采用了粒子群优化算法、遗传算法、以及蚁群优化算法等三种方法来进行定位次序的全局优化搜索。在相同的测试集上,构造法的计算效果对比最速下降法有进一步的提高。
随后,研究了卫星舱二维多边形布局问题。在以定量的方式定义了多边形的覆盖之后,采用模拟退火方法进行覆盖量和不平衡量的优化。设计了一个可计算出理论最优值的多边形布局物测试集,该测试集既包含凸多边形布局物,也包含凹多边形布局物。在该测试集上的计算表明,在布局物数目不多的情况下,算法能保证所求布局解的性能。通过在一个现有的矩形布局物的测试集上的计算,表明算法的性能优于文献中的遗传算法。
最后,综合二维计算的研究成果,给出了卫星舱三维布局问题的求解方法。利用启发式方法将布局物分成两个集合,采用模拟退火方法对每个集合中的布局物在卫星舱中进行布局优化计算。利用五个测试算例,验证了方法的可行性。与现有算法相比,本文的算法具有优势。
简言之,本文针对卫星舱布局优化问题的多种模型,采用了多种方法进行计算。本文的计算结果表明,采用启发式方法,结合元启发式方法,是求解卫星舱复杂布局优化问题的有力手段。
The main topic of this thesis is solving the layout optimization problems in satellite by the modern intelligent computation methods. Several models and a series of methods for the problems are studied. The performances of these methods are investigated by the computations on some benchmarks.
We begin the thesis by introducing the background of the general layout optimization problems, and then we point out reasonably that making full use of the heuristic information of the problems themselves is conducive to solving them. Under the problem-solving philosophy of from simple to complex, we first study the two-dimensional layout problem in satellite, in which the packed objects are circular. Then we continue to study the cases of packing polygon objects. Finally, we extend the research to the three -dimensional problems.
For the two-dimensional problem of packing circular objects in satellite, we first modify the existed computational models in order that we can solve the problem in two steps. In the first step, we use the existed local search algorithm for the general circle packing problem, which is based on the gradient descent method, to obtain a layout without overlaps. In the second step, we concern the balance issue. To search for the global optimal solution, we run the two-step optimization multiple times and each time the algorithm starts from different point. The computation on the benchmarks shows that our method has better performance than literatures.
Secondly, we invent a constructive heuristic for the two-dimensional problem of packing circular objects. In the constructive heuristic, the objects are positioned in a sequence by the construction rules. Because different positioning sequences can result in layouts with different quality, we develop three meta-heuristics to search for the optimal positioning sequence, including the discrete particle swarm algorithm, the genetic algorithm, and the ant colony algorithm. On the same benchmarks, the new methods outperform the two-step optimization introduced above.
Next, we study the two-dimensional problem of packing polygon objects. We first define the measurement of the overlaps between the polygons, and then we use simulated annealing method to optimize the overlaps and the unbalance. We design a benchmark for the problem, in which the theoretical solution for each instance is known. The results on the benchmark show that the algorithm has good performance if the amount of objects is not very large. On another old benchmark for packing rectangle objects, the algorithm shows better performance than the genetic algorithm in literature.
At last, we integrate the techniques on the two-dimensional problems, and apply them on the three-dimensional problem. We provide a heuristic to divide the objects into two sets, and then use the simulated annealing to pack the objects in each set on the two packing spaces of the satellite. The algorithm is tested on a 5-instance benchmark, and the results show that the solving strategy is feasible and able to compete with other existed algorithms.
In short, we studied several models for the packing problems in satellite, and provide some algorithms for them. Our researches demonstrate that combination of the heuristic method and meta-heuristic method is a powerful tool for the layout problems in satellite.
引文
[1]Dyckhoff H.A typology of cutting and packing problems.European Journal of Operational Research,1990,44(1):145-159.
[2]黄献清,刘建瓴,刘桂雄.面向精密机械制造的一维下料计算机辅助系统设计.机电产品开发与创新,2005,18(1):64-66.
[3]崔耀东,周儒荣.单一尺寸矩形件排样时长板的最优分割.计算机辅助设计与图形学学报,2001,13(5):434-437.
[4]段国林,查建中,林建平等.模拟退火法在钟手表机芯布局中的应用.计算机辅助设计与图形学学报,1999,11(3):276-279.
[5]Cagan J,Shimada K,Yin S.A survey of computational approaches to three -dimensional layout problems.Computer Aided Design,2002,34(3):697-611.
[6]史彦军.复杂布局的协同差异演化方法与应用研究:[博士学位论文].大连理工大学,2005.
[7]唐晓君.虚拟环境下人机结合的布局问题求解理论与方法研究:[博士学位论文].北方交通大学,2003.
[8]张玉萍,宋健,蒋寿伟.基于离散化和遗传算法的皮革制造中的排样问题.计算机工程,2004,30(23):151-152.
[9]曹炬,周济.矩形件排样优化的一种近似算法.计算机辅助设计与图形学学报,1995,7(3):190-195.
[10]滕弘飞,孙自国,刘德全等.复杂布局问题:航天器舱布局方案设计.大连理工大学学报,2001,41(5):578-688.
[11]Li Z,Milenkovic V.A Compaction algorithm for non-convex polygons and its application.in:Proceedings of the 9th Annual ACM Symposium on Computational Geometry.New York:ACM Press,1993.153-162.
[12]Liu D,Teng H.An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles.European Journal of Operational Research,1999,112(2):413-420.
[13]Feng E,Wang X L,Wang X M,et al.An algorithm of global optimization for solving layout problems.European Journal of Operational Research,1999,114(2):430-436.
[14]Baase S,Gelder A V.Computer Algorithms:Introduction to Design and Analysis.(3). Boston:Addison Wesley Longman,2000.
[15]余祥宣,崔国华,邹海明.计算机算法基础(第二版).武汉:华中科技大学出版社,2000.
[16]Fowler R J,Paterson M S,Tanimoto S L.Optimal packing and covering in the plane are NP-complete.Information Processing Letters,1981,12(3):133-137.
[17]Sweeney P E,Patemoster E R.Cutting and packing problems:a categorized,application-orientated research.Journal of Operation Research Society,1992,43(7):691-706.
[18]Imahori S.Study on local search algorithms for cutting and packing problems:[Phd thesis].Kyoto University,2004.
[19]W(a|¨)scher G,Hauβner H,Schumann H.An improved typology of cutting and packing problems:Technical Economics and Management.Otto von Guericke University,2006.
[20]张春玲,崔耀东.一维优化下料问题.桂林工学院学报,2004,24(1):103-106.
[21]Gilmore P C,Gomo R E.A linear programming approach to the cutting stock problem.Operations Research,1961,9(6):849-859.
[22]Gilmore P C,Gomo R E.A linear programming approach to the cutting stock problem:part Ⅱ.Operations Research,I963,11(6):863-888.
[23]Valerio D E,Carvalho J M.Exact solution of cutting stock problems using column generation and branch and bound.International Transactions in Operational Research,1998,5(1):35-44.
[24]Gradisar M,Kljajic M,Resinovie G,et al.A sequential heustic procedure for one-dimensional cutting.European Journal of Operational Research,1999,114(3):557-568.
[25]Johnson D S,Demers A,Ullman J D,et al.Worst-case performance bounds for simple one-dimensional packing algorithms.SIAM Journal on Computing,1974,3(4):291-307.
[26]Waugner B J.A genetic algorithm solution for one-dimensional bundled stock cutting.European Journal of Operational Research,1999,117(2):368-381.
[27]刘道海,方毅,黄樟灿.一种求解组合优化问题的演化算法.武汉大学学报(理学版),2002,48(3):315-318.
[28]Baker B S,Coffman E G,Rivest R L.Orthogonal packings in two dimensions.SIAM Journal on Computing,1980,9(4):846-855.
[29]Wu Y L,Huang W,Lau S C,et al.An effective quasi-human based heuristic for solving the rectangle packing problem.European Journal of Operational Research,2002,141(2):341-358.
[30]陈端兵,黄文奇.一种求解矩形块装填问题的拟人算法.计算机科学,2006,33(5):234-237.
[31]Zhang D,Kang Y,Deng A.A new heuristic recursive algorithm for the strip rectangular packing problem.Computers & Operations Research,2006,33(6):2209-2217.
[32]Martello S,Vigo D.Exact solution of the two-dimensional finite bin packing problem.Management Science,1998,44(3):388-399.
[33]Leung T W,Yung C H,Marvin D,et al.Application of genetic search and simulated annealing to the two-dimensional nonguillotine cutting stock problem.Computers &Industrial Engineering,2001,40(3):201-204.
[34]Faina L.An application of simulated annealing to the cutting stock problem.European Journal of Operational Research,1999,114(3):542-556.
[35]Hwang S M,Kao C Y,Horng J T.On solving rectangle bin packing problems using GAs.in:Proceedings of the 1994 IEEE International Conference on Systems,Man,and Cybernetics.Piscataway,NJ:IEEE Press,1994.1583-1590.
[36]Harwig J M.An adaptive tabu search approach to cutting and packing problems:[Phd thesis].University of Texas at Austin,2003.
[37]Lodi A,Martello S,Monaci M.Two-dimensional packing problems:A survey.European Journal of Operational Research,2002,141(2):241-252.
[38]Lodi A,Martello S,Vigo D.Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems.INFORMS Journal on Computing,1999,11(4):345-357.
[39]Lodi A,Martello S,Vigo D.Recent advances on two-dimensional bin packing problems.Discrete Applied Mathematics,2002,123(1-3):373-390.
[40]Audet C,Hansen P,Savard G.Essays and Surveys in Global optimization.Berlin:Springer,2005.
[41]Graham R L,Lubachevsky B D.Dense packing of equal disks in an equilateral triangle from 22 to 34 and beyond.The Electronic Journal of Combinatorics,1995,2. A1#(electronic).
[42]Wang H,Huang W,Zhang Q,et al.An improved algorithm for the packing of unequal circles within a larger containing circle.European Journal of Operational Research,2002,141(2):440-453.
[43]黄文奇,许如初.支持求解圆形packing问题的两个拟人策略.中国科学(E辑),1999,29(4):347-353.
[44]黄文奇,詹叔浩.求解packing问题的拟物方法.应用数学学报,1979,3(2):176-180.
[45]Zhang D,Deng A.An effective hybrid algorithm for the problem of packing circles into a larger containing circle.Computers & Operations Research,2005,32(8):1941-1951.
[46]George J A,George J M,Lamar B W.Packing different-sized circles into a rectangular container.European Journal of Operational Research:1995,84(3):693-712.
[47]Huang W,Li Y,Li C M,et al.New heuristics for packing unequal circles into a circular container.Computers & Operations Research,2006,33(8):2125-2142.
[48]Dowsland K A,Vaid S,Dowsland W B.An algorithm for polygon placement using bottom-left strategy.European Journal of Operational Research,2002,141(2):371-381.
[49]Freeman H,Shapira R.Determining the minimum-area encasing rectangle for an arbitrary closed curve.Communications of the ACM,1975,18(7):409-413.
[50]Dori D,Ben-Bassat M.Efficient nesting of congruent convex figures.Communications of the ACM,1984,27(3):228-235.
[51]陈传波,何大华,黄文奇.求解单位等边三角形Packing问题的近似算法.计算机学报,2003,26(2):212-220.
[52]Dowsland K A,Dowsland W B.Solution approaches to irregular nesting problems.European Journal of Operational Research,1995,84(3):506-521.
[53]Albano A,Sapuppo G.Optimal allocation of two-dimensional irregular shapes using heuristic search methods.IEEE Transactions on Systems,Man and Cybernetics,1980,SMC10(5):242-248.
[54]Blazewicz J,Hawryluk P,Walkowiak R.Using a tabu search approach for solving the two-dimensional irregular cutting problem.Annals of Operations Research,1993,41(4):313-325.
[55]Sakait J,Hae C G.Two-dimensional packing problems using genetic algorithms.Engineering with Computers,1998,14(3):206-213.
[56]黄文奇,宋恩民,陈益等.求解空间Packing问题的实用近似快速算法.高等学校计算数学学报,1995,(1):21-30.
[57]George J A,Robinson D F.A heuristic for packing boxes into a container.Computer and Operational Research,1980,7(3):147-156.
[58]Terno J,Scheithauer G,Sommerweisz U,et al.An efficient approach for the multi-pallet loading problem.European Journal of Operational Research,2000,123(2):372-381.
[59]戴佐,袁俊良,查建中.一种基于八叉树结构表达的三维实体布局启发式算法.软件学报,1995,6(10):629-636.
[60]Martello S,Pisinger D,Vigo D.The three-dimensional bin packing problem.Operations Research,2000,48(2):256-267.
[61]Bischoff E E,Janetz F,Ratcliff M S W.Loading pallets with non-identical items.European Journal of Operational Research,1995,84(3):681-692.
[62]Gehring H,Bortfeldt A.A genetic algorithm for solving the container loading problem.International Transactions in Operational Research,1997,4(5-6):401-418.
[63]Loris F.A global optimization algorithm for the three-dimensional packing problem.European Journal of Operational Research,2000,126(2):340-354.
[64]Faroe O,Pisinger D,Zachariasen M.Guided local search for the three-dimensional bin-packing problem.INFORMS Journal on Computing,2003,15(3):267-283.
[65]余金培.现代小卫星技术与应用.上海:上海科学普及出版社,2004.
[66]王希季,李大耀.卫星设计学.上海:上海科学技术出版社,1997.
[67]徐博明.气象卫星有效载荷技术.北京:中国宇航出版社,2005.
[68]Teng H,Sun S,Ge W,et al.Layout optimization for the dishes installed on a rotating table-the packing problem with equilibrium behavioral constrains.Science in China (Series A),1994,37(10):1272-1279.
[69]滕弘飞,张宝,刘峻等.航天器布局方案设计.大连理工大学学报,2003,43(1):86-92.
[70]Tanner S,Fennel R.The placement of equipment in the space station freedom using constraint based reasoning.in:American Association for Artificial Intelligence,Conference on Innovative Applications of AI.Anaheim.CA,1991.51-71.
[71]Ferebee M J,Allent C L.Optimization of payload placement on arbitrary spacecraft.Journal of Spacecraft and Rockets,1991,28(5):612-614.
[72]唐飞,滕弘飞.一种改进的遗传算法及其在布局优化中的应用.软件学报,1999,10(10):1096-1102.
[73]钱志勤,滕弘飞,孙治国.人机交互的遗传算法及其在约束布局优化中的应用.计算机学报,2001,24(5):553-559.
[74]于洋,查建中,唐晓君.基于学习的遗传算法及其在布局中的应用.计算机学报,2001,24(12):1242-1249.
[75]刘建,黄文奇.利用改进的微分进化算法求解带平衡约束的圆形packing问题.信息与控制,2006,35(1):103-107.
[76]李宁,刘飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究.计算机学报,2004,27(7):897-903.
[77]周驰,高亮,高海兵.基于粒子群优化算法的约束布局优化.控制与决策,2005,20(1):36-40.
[78]李广强,赵洪伦,赵凤强等.人机合作的免疫算法及其在布局设计中的应用.计算机工程,2005,31(21):4-6.
[79]霍军周,李广强,滕弘飞等.人机结合蚁群/遗传算法及其在卫星舱布局设计中的应用.机械工程学报,2005,41(3):112-116.
[80]Huang W,Chen M.Note on:An improved algorithm for the packing of unequal circles within a larger containing circle.Computers & Industrial Engineering,2006,50(3):388-344.
[81]Teng H,Sun S,Liu D,et al.Layout optimization for the objects located within a rotating vessel-a three-dimensional packing problem with behavioral constraints.computers & Operations Research,2001,28(6):521-535.
[82]戴汝为.人-机结合的智能科学和智能工程.中国工程科学,2004,6(5):24-28.
[83]钱志勤,滕弘飞.复杂布局设计问题的算法.中国机械工程,2002,13(8):696-699.
[84]Nurmela K J.Stochastic optimization methods in sphere packing and covering problems in discrete geometry and coding theory:[Phd thesis].Helsinki University of Technology,1997.
[85]程麟趾.非线性规划.现代工程数学手册(汪胡祯 主编).武汉:华中理工大学出版社.1990.
[86]林锉云,董加礼.多目标优化的方法与理论.长春:吉林教育出版社,1992.
[87]Kennedy J,Eberhart R C.Particle swarm optimization,in:Proc.IEEE Int'l.Conf.on Neural Networks.Piscataway,NJ:IEEE Press,1995.1942-1948.
[88]Kennedy J,Eberhart,R C,Shi Y.Swarm Intelligence.San Francisco:Morgan Kaufrnann Publishers,2001.
[89]Rao S S.Engineering optimization-theory and practice.New York:Wiley,1996.
[90]Kennedy J,Eberhart R C.A discrete binary version of the particle swarm algorithm,in:IEEE Conference on Systems,Man,and Cybernetics.Piscataway,NJ:IEEE Press,1997.4104-4109.
[91]Boeringer D W,Wemer D H.Particle swarm optimization versus genetic algorithms for phased array synthesis.IEEE Transactions on Antennas and Propagation,2004,52(3):771-779.
[92]Onwubolu G,Clerc M.Optimal path for automated drilling operations by a new heuristic approach using particle swarm optimization.International Journal of Production Research,2004,42(3):473-491.
[93]高海兵,周驰,高亮.广义粒子群优化模型.计算机学报,2005,28(12):1980-1987.
[94]Holland J.Adaptation In Natural and Artificial Systems.Ann Arbor:University of Michigan Press,1975.
[95]Muhlenbein.Genetic algorithms,in:Aarts E and Lenstra J K editors.Local Search in Combinatorial Optimization.New York:Wiley,1997.
[96]Poshyanonda P,Dagli C H.Genetic neuro-nester.Journal of Intelligent Manufacturing,2004,15(2):201-218.
[97]Beasley J E,Chu P C.A genetic algorithms for the set covering problem.European Journal of Operational Research,1996,94(2):392-404.
[98]Back T.Optimization by means of genetic algorithms,in:K(o|¨)hler E,editor.Proceedings of the 36th International Scientific Colloquium.Ilmenau,German,1991.163-169.
[99]Back T,Fogel D B,Michalewicz Z.Handbook of Evolutionary Computation.New York:Oxford University Press,1997.
[100]Corcoran A L,Wainwright R L.LibGA:a user-friendly workbench for order-based genetic algorithm research,in:Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing:states of the art and practice.New York:ACM Press,1993.111-117.
[101]Dorigo M,Dicaro G.The Ant colony optimization metaheuristic,in:Come D,Dorigo M,Glover F,editors.New Ideas in Optimization.US:McGraw-Hill,1999.
[102]陶振武.基于群集智能的产品共进化设计方法研究:[博士学位论文].华中科技大学,2007.
[103]Birgin E G,Martinez J M,Mascarenhas W F,et al.Method of sentinels for packing items within arbitrary convex regions.The Journal of the Operational Research Society,2006,57(6):735-746.
[104]Birgin E G,Martinez J M,Nishihara F H,et al.Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization.Computers &Operations Research,2006,33(12):3535-3548.
[105]O'Rourke J.Computational Geometry in C(2nd Ed.).Cambridge:Cambridge University Press,1998.
[106]周培德.计算几何-算法分析与设计.北京:清华大学出版社,2000.
[107]Kirkpatrick S,Gelatt C D,Vecchi M P.Optimization by simulated annealing.Science,1983,220(4598):671-680.
[108]翟金刚,冯恩民,李振民等.带性能约束布局问题的不干涉遗传算法.大连理工大学学报,1999,39(3):352-357.
[109]Shi Y,Eberhart R C.Comparing inertia weights and constriction factors in particle swarm optimization,in:Proceedings of the 2000 Congress on Evolutionary Computation.Piscataway,NJ:IEEE Press,2000.84-88.
[110]张宝.粒子群算法及其在卫星舱布局中的应用研究:[博士学位论文].大连理工大学,2006.
[2]黄献清,刘建瓴,刘桂雄.面向精密机械制造的一维下料计算机辅助系统设计.机电产品开发与创新,2005,18(1):64-66.
[3]崔耀东,周儒荣.单一尺寸矩形件排样时长板的最优分割.计算机辅助设计与图形学学报,2001,13(5):434-437.
[4]段国林,查建中,林建平等.模拟退火法在钟手表机芯布局中的应用.计算机辅助设计与图形学学报,1999,11(3):276-279.
[5]Cagan J,Shimada K,Yin S.A survey of computational approaches to three -dimensional layout problems.Computer Aided Design,2002,34(3):697-611.
[6]史彦军.复杂布局的协同差异演化方法与应用研究:[博士学位论文].大连理工大学,2005.
[7]唐晓君.虚拟环境下人机结合的布局问题求解理论与方法研究:[博士学位论文].北方交通大学,2003.
[8]张玉萍,宋健,蒋寿伟.基于离散化和遗传算法的皮革制造中的排样问题.计算机工程,2004,30(23):151-152.
[9]曹炬,周济.矩形件排样优化的一种近似算法.计算机辅助设计与图形学学报,1995,7(3):190-195.
[10]滕弘飞,孙自国,刘德全等.复杂布局问题:航天器舱布局方案设计.大连理工大学学报,2001,41(5):578-688.
[11]Li Z,Milenkovic V.A Compaction algorithm for non-convex polygons and its application.in:Proceedings of the 9th Annual ACM Symposium on Computational Geometry.New York:ACM Press,1993.153-162.
[12]Liu D,Teng H.An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles.European Journal of Operational Research,1999,112(2):413-420.
[13]Feng E,Wang X L,Wang X M,et al.An algorithm of global optimization for solving layout problems.European Journal of Operational Research,1999,114(2):430-436.
[14]Baase S,Gelder A V.Computer Algorithms:Introduction to Design and Analysis.(3). Boston:Addison Wesley Longman,2000.
[15]余祥宣,崔国华,邹海明.计算机算法基础(第二版).武汉:华中科技大学出版社,2000.
[16]Fowler R J,Paterson M S,Tanimoto S L.Optimal packing and covering in the plane are NP-complete.Information Processing Letters,1981,12(3):133-137.
[17]Sweeney P E,Patemoster E R.Cutting and packing problems:a categorized,application-orientated research.Journal of Operation Research Society,1992,43(7):691-706.
[18]Imahori S.Study on local search algorithms for cutting and packing problems:[Phd thesis].Kyoto University,2004.
[19]W(a|¨)scher G,Hauβner H,Schumann H.An improved typology of cutting and packing problems:Technical Economics and Management.Otto von Guericke University,2006.
[20]张春玲,崔耀东.一维优化下料问题.桂林工学院学报,2004,24(1):103-106.
[21]Gilmore P C,Gomo R E.A linear programming approach to the cutting stock problem.Operations Research,1961,9(6):849-859.
[22]Gilmore P C,Gomo R E.A linear programming approach to the cutting stock problem:part Ⅱ.Operations Research,I963,11(6):863-888.
[23]Valerio D E,Carvalho J M.Exact solution of cutting stock problems using column generation and branch and bound.International Transactions in Operational Research,1998,5(1):35-44.
[24]Gradisar M,Kljajic M,Resinovie G,et al.A sequential heustic procedure for one-dimensional cutting.European Journal of Operational Research,1999,114(3):557-568.
[25]Johnson D S,Demers A,Ullman J D,et al.Worst-case performance bounds for simple one-dimensional packing algorithms.SIAM Journal on Computing,1974,3(4):291-307.
[26]Waugner B J.A genetic algorithm solution for one-dimensional bundled stock cutting.European Journal of Operational Research,1999,117(2):368-381.
[27]刘道海,方毅,黄樟灿.一种求解组合优化问题的演化算法.武汉大学学报(理学版),2002,48(3):315-318.
[28]Baker B S,Coffman E G,Rivest R L.Orthogonal packings in two dimensions.SIAM Journal on Computing,1980,9(4):846-855.
[29]Wu Y L,Huang W,Lau S C,et al.An effective quasi-human based heuristic for solving the rectangle packing problem.European Journal of Operational Research,2002,141(2):341-358.
[30]陈端兵,黄文奇.一种求解矩形块装填问题的拟人算法.计算机科学,2006,33(5):234-237.
[31]Zhang D,Kang Y,Deng A.A new heuristic recursive algorithm for the strip rectangular packing problem.Computers & Operations Research,2006,33(6):2209-2217.
[32]Martello S,Vigo D.Exact solution of the two-dimensional finite bin packing problem.Management Science,1998,44(3):388-399.
[33]Leung T W,Yung C H,Marvin D,et al.Application of genetic search and simulated annealing to the two-dimensional nonguillotine cutting stock problem.Computers &Industrial Engineering,2001,40(3):201-204.
[34]Faina L.An application of simulated annealing to the cutting stock problem.European Journal of Operational Research,1999,114(3):542-556.
[35]Hwang S M,Kao C Y,Horng J T.On solving rectangle bin packing problems using GAs.in:Proceedings of the 1994 IEEE International Conference on Systems,Man,and Cybernetics.Piscataway,NJ:IEEE Press,1994.1583-1590.
[36]Harwig J M.An adaptive tabu search approach to cutting and packing problems:[Phd thesis].University of Texas at Austin,2003.
[37]Lodi A,Martello S,Monaci M.Two-dimensional packing problems:A survey.European Journal of Operational Research,2002,141(2):241-252.
[38]Lodi A,Martello S,Vigo D.Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems.INFORMS Journal on Computing,1999,11(4):345-357.
[39]Lodi A,Martello S,Vigo D.Recent advances on two-dimensional bin packing problems.Discrete Applied Mathematics,2002,123(1-3):373-390.
[40]Audet C,Hansen P,Savard G.Essays and Surveys in Global optimization.Berlin:Springer,2005.
[41]Graham R L,Lubachevsky B D.Dense packing of equal disks in an equilateral triangle from 22 to 34 and beyond.The Electronic Journal of Combinatorics,1995,2. A1#(electronic).
[42]Wang H,Huang W,Zhang Q,et al.An improved algorithm for the packing of unequal circles within a larger containing circle.European Journal of Operational Research,2002,141(2):440-453.
[43]黄文奇,许如初.支持求解圆形packing问题的两个拟人策略.中国科学(E辑),1999,29(4):347-353.
[44]黄文奇,詹叔浩.求解packing问题的拟物方法.应用数学学报,1979,3(2):176-180.
[45]Zhang D,Deng A.An effective hybrid algorithm for the problem of packing circles into a larger containing circle.Computers & Operations Research,2005,32(8):1941-1951.
[46]George J A,George J M,Lamar B W.Packing different-sized circles into a rectangular container.European Journal of Operational Research:1995,84(3):693-712.
[47]Huang W,Li Y,Li C M,et al.New heuristics for packing unequal circles into a circular container.Computers & Operations Research,2006,33(8):2125-2142.
[48]Dowsland K A,Vaid S,Dowsland W B.An algorithm for polygon placement using bottom-left strategy.European Journal of Operational Research,2002,141(2):371-381.
[49]Freeman H,Shapira R.Determining the minimum-area encasing rectangle for an arbitrary closed curve.Communications of the ACM,1975,18(7):409-413.
[50]Dori D,Ben-Bassat M.Efficient nesting of congruent convex figures.Communications of the ACM,1984,27(3):228-235.
[51]陈传波,何大华,黄文奇.求解单位等边三角形Packing问题的近似算法.计算机学报,2003,26(2):212-220.
[52]Dowsland K A,Dowsland W B.Solution approaches to irregular nesting problems.European Journal of Operational Research,1995,84(3):506-521.
[53]Albano A,Sapuppo G.Optimal allocation of two-dimensional irregular shapes using heuristic search methods.IEEE Transactions on Systems,Man and Cybernetics,1980,SMC10(5):242-248.
[54]Blazewicz J,Hawryluk P,Walkowiak R.Using a tabu search approach for solving the two-dimensional irregular cutting problem.Annals of Operations Research,1993,41(4):313-325.
[55]Sakait J,Hae C G.Two-dimensional packing problems using genetic algorithms.Engineering with Computers,1998,14(3):206-213.
[56]黄文奇,宋恩民,陈益等.求解空间Packing问题的实用近似快速算法.高等学校计算数学学报,1995,(1):21-30.
[57]George J A,Robinson D F.A heuristic for packing boxes into a container.Computer and Operational Research,1980,7(3):147-156.
[58]Terno J,Scheithauer G,Sommerweisz U,et al.An efficient approach for the multi-pallet loading problem.European Journal of Operational Research,2000,123(2):372-381.
[59]戴佐,袁俊良,查建中.一种基于八叉树结构表达的三维实体布局启发式算法.软件学报,1995,6(10):629-636.
[60]Martello S,Pisinger D,Vigo D.The three-dimensional bin packing problem.Operations Research,2000,48(2):256-267.
[61]Bischoff E E,Janetz F,Ratcliff M S W.Loading pallets with non-identical items.European Journal of Operational Research,1995,84(3):681-692.
[62]Gehring H,Bortfeldt A.A genetic algorithm for solving the container loading problem.International Transactions in Operational Research,1997,4(5-6):401-418.
[63]Loris F.A global optimization algorithm for the three-dimensional packing problem.European Journal of Operational Research,2000,126(2):340-354.
[64]Faroe O,Pisinger D,Zachariasen M.Guided local search for the three-dimensional bin-packing problem.INFORMS Journal on Computing,2003,15(3):267-283.
[65]余金培.现代小卫星技术与应用.上海:上海科学普及出版社,2004.
[66]王希季,李大耀.卫星设计学.上海:上海科学技术出版社,1997.
[67]徐博明.气象卫星有效载荷技术.北京:中国宇航出版社,2005.
[68]Teng H,Sun S,Ge W,et al.Layout optimization for the dishes installed on a rotating table-the packing problem with equilibrium behavioral constrains.Science in China (Series A),1994,37(10):1272-1279.
[69]滕弘飞,张宝,刘峻等.航天器布局方案设计.大连理工大学学报,2003,43(1):86-92.
[70]Tanner S,Fennel R.The placement of equipment in the space station freedom using constraint based reasoning.in:American Association for Artificial Intelligence,Conference on Innovative Applications of AI.Anaheim.CA,1991.51-71.
[71]Ferebee M J,Allent C L.Optimization of payload placement on arbitrary spacecraft.Journal of Spacecraft and Rockets,1991,28(5):612-614.
[72]唐飞,滕弘飞.一种改进的遗传算法及其在布局优化中的应用.软件学报,1999,10(10):1096-1102.
[73]钱志勤,滕弘飞,孙治国.人机交互的遗传算法及其在约束布局优化中的应用.计算机学报,2001,24(5):553-559.
[74]于洋,查建中,唐晓君.基于学习的遗传算法及其在布局中的应用.计算机学报,2001,24(12):1242-1249.
[75]刘建,黄文奇.利用改进的微分进化算法求解带平衡约束的圆形packing问题.信息与控制,2006,35(1):103-107.
[76]李宁,刘飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究.计算机学报,2004,27(7):897-903.
[77]周驰,高亮,高海兵.基于粒子群优化算法的约束布局优化.控制与决策,2005,20(1):36-40.
[78]李广强,赵洪伦,赵凤强等.人机合作的免疫算法及其在布局设计中的应用.计算机工程,2005,31(21):4-6.
[79]霍军周,李广强,滕弘飞等.人机结合蚁群/遗传算法及其在卫星舱布局设计中的应用.机械工程学报,2005,41(3):112-116.
[80]Huang W,Chen M.Note on:An improved algorithm for the packing of unequal circles within a larger containing circle.Computers & Industrial Engineering,2006,50(3):388-344.
[81]Teng H,Sun S,Liu D,et al.Layout optimization for the objects located within a rotating vessel-a three-dimensional packing problem with behavioral constraints.computers & Operations Research,2001,28(6):521-535.
[82]戴汝为.人-机结合的智能科学和智能工程.中国工程科学,2004,6(5):24-28.
[83]钱志勤,滕弘飞.复杂布局设计问题的算法.中国机械工程,2002,13(8):696-699.
[84]Nurmela K J.Stochastic optimization methods in sphere packing and covering problems in discrete geometry and coding theory:[Phd thesis].Helsinki University of Technology,1997.
[85]程麟趾.非线性规划.现代工程数学手册(汪胡祯 主编).武汉:华中理工大学出版社.1990.
[86]林锉云,董加礼.多目标优化的方法与理论.长春:吉林教育出版社,1992.
[87]Kennedy J,Eberhart R C.Particle swarm optimization,in:Proc.IEEE Int'l.Conf.on Neural Networks.Piscataway,NJ:IEEE Press,1995.1942-1948.
[88]Kennedy J,Eberhart,R C,Shi Y.Swarm Intelligence.San Francisco:Morgan Kaufrnann Publishers,2001.
[89]Rao S S.Engineering optimization-theory and practice.New York:Wiley,1996.
[90]Kennedy J,Eberhart R C.A discrete binary version of the particle swarm algorithm,in:IEEE Conference on Systems,Man,and Cybernetics.Piscataway,NJ:IEEE Press,1997.4104-4109.
[91]Boeringer D W,Wemer D H.Particle swarm optimization versus genetic algorithms for phased array synthesis.IEEE Transactions on Antennas and Propagation,2004,52(3):771-779.
[92]Onwubolu G,Clerc M.Optimal path for automated drilling operations by a new heuristic approach using particle swarm optimization.International Journal of Production Research,2004,42(3):473-491.
[93]高海兵,周驰,高亮.广义粒子群优化模型.计算机学报,2005,28(12):1980-1987.
[94]Holland J.Adaptation In Natural and Artificial Systems.Ann Arbor:University of Michigan Press,1975.
[95]Muhlenbein.Genetic algorithms,in:Aarts E and Lenstra J K editors.Local Search in Combinatorial Optimization.New York:Wiley,1997.
[96]Poshyanonda P,Dagli C H.Genetic neuro-nester.Journal of Intelligent Manufacturing,2004,15(2):201-218.
[97]Beasley J E,Chu P C.A genetic algorithms for the set covering problem.European Journal of Operational Research,1996,94(2):392-404.
[98]Back T.Optimization by means of genetic algorithms,in:K(o|¨)hler E,editor.Proceedings of the 36th International Scientific Colloquium.Ilmenau,German,1991.163-169.
[99]Back T,Fogel D B,Michalewicz Z.Handbook of Evolutionary Computation.New York:Oxford University Press,1997.
[100]Corcoran A L,Wainwright R L.LibGA:a user-friendly workbench for order-based genetic algorithm research,in:Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing:states of the art and practice.New York:ACM Press,1993.111-117.
[101]Dorigo M,Dicaro G.The Ant colony optimization metaheuristic,in:Come D,Dorigo M,Glover F,editors.New Ideas in Optimization.US:McGraw-Hill,1999.
[102]陶振武.基于群集智能的产品共进化设计方法研究:[博士学位论文].华中科技大学,2007.
[103]Birgin E G,Martinez J M,Mascarenhas W F,et al.Method of sentinels for packing items within arbitrary convex regions.The Journal of the Operational Research Society,2006,57(6):735-746.
[104]Birgin E G,Martinez J M,Nishihara F H,et al.Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization.Computers &Operations Research,2006,33(12):3535-3548.
[105]O'Rourke J.Computational Geometry in C(2nd Ed.).Cambridge:Cambridge University Press,1998.
[106]周培德.计算几何-算法分析与设计.北京:清华大学出版社,2000.
[107]Kirkpatrick S,Gelatt C D,Vecchi M P.Optimization by simulated annealing.Science,1983,220(4598):671-680.
[108]翟金刚,冯恩民,李振民等.带性能约束布局问题的不干涉遗传算法.大连理工大学学报,1999,39(3):352-357.
[109]Shi Y,Eberhart R C.Comparing inertia weights and constriction factors in particle swarm optimization,in:Proceedings of the 2000 Congress on Evolutionary Computation.Piscataway,NJ:IEEE Press,2000.84-88.
[110]张宝.粒子群算法及其在卫星舱布局中的应用研究:[博士学位论文].大连理工大学,2006.