切割问题的概率解法  

Probability-Based Algorithms for Solving Cutting Problems

作　　者：陈盛双[1] 胡晓林[2] 黄樟灿[1] 

机构地区：[1]武汉理工大学(东院)基础课部,湖北武汉430070 [2]武汉理工大学(东院)汽车工程学院,湖北武汉430070

出　　处：《武汉理工大学学报（信息与管理工程版）》2001年第2期93-96,共4页Journal of Wuhan University of Technology：Information & Management Engineering

基　　金：国家自然科学基金资助项目! (70 0 710 42 )

摘　　要：如何从一个大物体中切割出一个预定形状的小物体 ,而使切割费用最少 ,这是在工业生产中是一个常常需要考虑的问题。文中具体描述了两类切割问题———立体切割和平面切割 ,并通过分析建立了各自的数学模型。这两类切割问题都只是要求一个最优次序 ,鉴于概率算法在优化这类与次序有关的问题时一般不需要了解问题的内在实质 ,因此 ,提出了用概率算法求解这两类切割问题的统一框架 ,并对基于两种概率算法———郭涛算法 (演化计算的一种 )和模拟退火算法的求解过程进行了简要描述。实例计算中 ,首先用郭涛算法求解立体切割问题和一个规模较小的平面切割问题 ,均得到了最优解 ;然后针对一个规模较大的平面切割问题 ,用模拟退火算法求解 ,通过比较几组控制参数的实际效果 ,选定了一个最优的冷却进度表 ;最后针对不同规模的平面切割问题 ,对郭涛算法和模拟退火算法进行了详细比较 ,发现随着问题规模的增大 ,后者的效果要明显好于前者 ,并对此做了一些定性的分析。How to minimize the cutting cost when cutting a small object of a given size from a bigger one is an important problem in the industrial production. Two types of cutting problems —— solid cutting and plane cutting —— are described and the mathematics mode ls for these two cuttings are constructed. Essential for these two cutting problems is to find an optimal cutting order. When Probability Based Algorithms are used to optimize the problems concerning orders, it is not necessary to know the essence of the problem, and there fore the process of optimization is simplized. An optimizing framework using Probability Based Algorithms is presented to solve these two types of cutting problems. Two kinds of Probability Based Algorithms, T Guo's Algorithm(TGA)(a new evolutionary algorithm) and the Simulated Annealing Algorithm(SAA), and their solving processes are discussed. Examples are given to solve solid cutting problems and plane cutting problems of few cuttings using TGA, and both of the optimal solutions for these two problems are found out. The SAA is used to solve plane cutting problems of many cuttings. By using evolutionary parameters, an optimal solution is found out. TGA and the SAA are compared in solving plane cutting problems of different quantities of cuttings and the result shows that the SAA is more effective if the number of cuttings gets large enough. Some qualitative analyses are made to explain this phenomenon.

关 键 词：立体切割 平面切割 演化计算 模拟退火算法 概率算法 郭涛算法 切割问题 

分 类 号：O224[理学—运筹学与控制论] TP301.6[理学—数学]