【作者】 岳琪；

【导师】 曹军；

【作者基本信息】 东北林业大学 ， 机械设计及理论， 2005， 博士

【摘要】 优化下料,是一个在产品设计、制造和使用中如何节约原料、优化利用资源的问题。对优化下料问题的研究具有重要经济意义和社会效益。它在计算理论上非常复杂和困难,而在实际生产中却有着广泛的应用。随着智能优化算法理论和计算机技术的发展,为人们提供了用现代优化算法和计算机进行优化下料的可能性。本文研究的优化下料问题主要是板式家具生产中在矩形原料板上的大规模矩形件排样问题。 针对在板式家具中板材下料问题的具体特点,结合板式家具下料的工艺和约束条件,给出了在矩形原料板材上的矩形零件优化下料的定义、特点、性质并提出了在工艺条件以及规模约束下的大规模板式家具优化下料的数学模型。在对下料优化方案生成算法的研究中,提出了一种“生成即可行”的排样方法。根据板式家具下料“一刀切(Guillotine Cutting)”的工艺特性,设计了一种二叉树结构来表现排样方案的生成过程,保证了所有的方案在产生时即可行,使整个方案生成过程中的所有解都是可行解,因此避免了在寻优过程中再对编码进行可行性验证的操作。 提出了将现代智能优化算法:遗传算法(GA)、模拟退火算法(SA)和根据这两种算法的各自优势将其融合后的遗传退火算法(GASA)在大规模板式家具下料中的应用。并在应用过程中,对算法进行了改进。针对模拟退火算法冷却进度表和邻域范围难以确定,进入局部最优后难以跳出的问题,设计了温度可控的冷却进度表,提出了搜索进入局部最优的判定函数和升温函数,使搜索进入局部最优后能及时升温,并从局部最优中跳出,保证了解的最优性。设计了初始温度、邻域结构和随机接受函数,提高了求解速度;针对遗传算法在矩形件优化下料问题中应用的实际特点,提出一种全新的面向对象的遗传编码方式和基于“贯通原料”的基因变异方式,将变异后不可用基因数量降到了零,就适应度函数、初始群体的生成和遗传操作等关键问题提出了相应的设计方法;对两种算法进行了详细的对比分析和论证,从理论和实践的角度总结了两种算法各自优缺点,取模拟退火算法和遗传算法的各自长处,将它们有机地结合在一起,分别采用了本文提出的模拟退火算法中升温的控制和遗传算法中的编码和变异的方式,生成温控遗传-退火算法,混合算法搜索全局最优的能力大大提高;对三种算法从理论和实践的角度进行了对比分析,遗传-退火算法兼有遗传算法中种群、个体、交配、基因、遗传、变异等淘汰劣质解的操作,也有模拟退火算法中冷却进度表和接受概率等寻优控制技术,可以更好地实现大规模矩形件下料问题的快速求解。 研制了板式家具大规模矩形件优化下料系统,实验表明,该软件的优化效果高于国内同类研究成果,而且操作极其简便,节约原材料效果显著,实用性强。对同一组数据的求解,第三种遗传退火算法优化效率更高。更多还原

【Abstract】 Cutting stock is concerned with how to saving material, optimize resources in product designing, manufacturing. The research on the problem has important economic meaning and social benefit. It is very complicated and difficult in computing theory, but it has got the extensive application in the actual manufacture. With the development of intelligent optimize algorithm theory and computer technology, it offers the possibility to people to solve the problem with modern optimal algorithm and computer. In this paper, the cutting stock problem was consistsed of packing rectangular items onto a rectangular raw material in the fibre furniture manufacture.Considered of the concrete characteristics of the cutting stock problem in the fibre furniture, it combined the craft and restraint condition in the fibre furniture, it gave the definition, characteristics and nature of cutting stock in rectangle parts on the rectangle raw material board, and had put forward the restrained of craft and items’ scale modes of the fibre furniture, the mathematics model was given; On the research of cutting stock algorithm, the paper presented a method of "Be Feasible on Producing". According to the craft characteristic of "Guillotine cutting" in the fibre furniture manufacture, the paper adopted the binary tree structure to perform the process with layout pattern, ensureed that all schemes were feasible while producing. It made the whole solutions feasible while the cutting patterns were generated, so that it avoided carrying on feasible verification to encode in the course of searching optimal solution; The paper presented the application of modern intelligent optimizing algorithm: Genetic Algorithm (GA), Simulated Annealing (SA), and hybrid algorithm according to each advantages of Genetic Algorithm and Simulated Annealing (GASA) in the fibre furniture cutting phase, and in the course of applying, the paper improveed the algorithm; To the question of the difficulty in determining the proper cooling schedule and choosing a proper neighborhood in simulated annealing algorithm, and also the difficulty of escaping from the local optimal solution, the paper designed a temperature controlled cooling schedule, local optimum judging function and temperature raising function was given, it raised temperature in time after the search entered the local optimal solution, and it could make searching escape from the local optimal solution, ensured the final solution to be the optimal. It designed initial temperature, neighborhood structure and random acceptive function, the paper improved the speed of solving process; To the question of characteristic of Genetic Algorithm applied in the rectangular cutting stock problem, the paper presented a kind of Objective Oriented genetic coding method. It proposed the genetic mutation scheme on the basis of " Run-Through Material", unused gene quantity had been brought down to zero after making a variation, and it put forward corresponding definite method and key points, fitness function, initial formulation and genetic operation; The paper carried on detailed comparing and analysis to the two algorithms mentioned above, summarized the advantages and deficiencies in terms of the theory and the implementation of the two algorithms, fetched the advantages of Simulated Annealing algorithm and Genetic Algorithm, combined them together well, included the temperature controled ofSimulated Annealing algorithm and the coding method and the way of variation of Genetic Algorithm, that made the ability of searching for the optimum of the new hybrid algorithm: Genetic-Simulated Annealing algorithm to be improved greatly; The paper compared and analyzed the three kinds of algorithms in terms of theory and practice, Genetic-Simulated Annealing algorithm had not only such operation of individual, mating, gene, heredity, making a variation etc. in Genetic Algorithms, but also had Simulation Anneal algorithm’s temperature controling, cooling schedule and technology of accepting probability etc. too, it could get the large scale rectangular cutting’s best solution faster.The paper developed the fibre furniture manufacture’s large scale rectangular cutting stock system, the experiment showed that the optimization result of the sysytem is higher than the domestic similar research results, and it was extremely simple and convenient to operate, it was remarkable to economize the raw materials, and it was practicability. To solve the same group data, the third method (Genetic-Simulated Annealing) is more efficiency.更多还原