摘要
排样问题是一类经典的组合优化问题,在现实生产中具有广泛的应用。排样问题是将待排样物体合理的摆放在指定的空间(平面)中,满足必要的约束,并且达到某种最优目标。布局结果的好坏对相关行业生产的合理性、经济性和安全性等指标有重大影响。
针对卷料上的圆形件下料问题,本文提出了基于品排的斜排,有效的提高了原材料的利用率。
基于遗传算法等进化算法在工程设计、制造业、自动控制和商业金融等领域的广泛应用和取得的显著效果,本文采用另一种进化算法--进化策略来尝试解决两类一维下料问题。它们分别是单型材长的一维下料问题(Cutting Stock Problem,CSP)和可接的一维下料问题。
对于单型材长的CSP,提出了基于进化策略的复合算法。它采用零件序列作为染色体,只采用单个体的变异和精英选择机制来实现进化。另外,在一次进化过程完成后,增加一个搜索算子来增强ES的局部搜索能力,弥补了ES在这方面的缺陷。
对于可接的CSP,ES结合了排序聚合法。它的适应值函数综合考虑了型材利用率最大化和焊点数最小化,满足了企业的实际要求。
我们的工作对于二维和其他的排样问题具有一定的借鉴价值。
Layout problem is a kind of classical combinatorial optimization problem. It has a wide range of application in a wide field. Layout problem means putting some objects on a specified space (or plane) within reason, satisfying some necessary restrictions, and reaching some optimal aim. The result of layout has an important impact on rationality, economization and security of production.
For circle packing on a Roll of Material, this paper puts forward a new method: oblique arrangement based on interlaced arrangement, which improves utilization percent of material. Because recently evolutionary algorithm has got a marked achievement on engineering, manufacturing, automation, business and finance, this paper adopts evolutionary strategy, one kind of evolutionary, to try to settle two kind of one dimensional layout problem. They are single stock length cutting stock problem (CSP) and CSP that items can be welded.
For single stock length CSP, we propose a compound ES, which takes item list as chromosome, and just relies on individual mutation and elitist election to realize colony evolution. In addition, after a process of evolution, we add a search operator to enhance local search capability of ES.
In the second problem, ES is combined with a linear aggregation method. Its fitness function synthetically considers maximizing the usage rate of material and minimizing the time of soldering the items, satisfying practice.
Our work can be used for reference for other layout problems.
引文
[1] Harald Dyckhoff. A typology of cutting and packing problems. European Journal of Operational Research,1990,44(2):145～149
[2] Kantorovich L V. Mathematical methods of organizing and planning production. Management Science, 1960(6):363～366
[3] Dagli C H. knowledge-based systems for cutting stock problems. European Journal of Operational Research,1990,44(2):160～166
[4] Pariam Kopardekar. Mital Anil Cutting Stock problem: A heuristic solution based on operator’s intuitive strategy. NT.J. Computer Integrated manufacturing, 1999,12(4):371～382
[5] Loris Faina. An application of simulated annealing to cutting stock problem. European Journal of Operational Research,1999,114: 542～556
[6] K.K. Lam, Jammy W.M. Chen.Developing a simulated annealing for the cutting stock problem.Computers & Industrial Engineering, 1997, 32(1):115～127
[7] Tadahiko Murata, Hisao Ishibuchi, Hideo Tanaka. Genetic algorithms for flowshop scheduling problems. Computers & Industrial Engineering, 1996, 30(4):1061～1071
[8] Fugal, D.B., Applying Evolutionary Programming to Selected Traveling Salesman Problems, Cybernetics and Systems,1993(24):27～36
[9] Chemung Moon, Jongsoo Kim, Gyunghyun Choi, Yoonho Seo. An efficient genetic algorithm for the traveling salesman problem with precedence constraints. European Journal of Operational Research, 2002, 240(3):606～617
[10] Yan Yang, Mohamed S. Kamel. An aggregated clustering approach using multi-ant colonies algorithms. Pattern Recognition,2006,39(7):1278～1289
[11] David Levine. Application of a hybrid genetic algorithm to airline crew scheduling.Computers & Operations Research,June, 1996,23(6):547～558
[12] T Chocklingham, S Arunkumar. Genetic algorithm based heuristics for the mapping problem.Location Science, 1996, 4(4):282～283
[13] Lawrence Davis.handbook of genetic algorithm.Van Nostrand Reinhold, New York,1991
[14] E.G. Coffman,Jr., M.R. Grarey, D.S. Johnson. Approximation algorithms for bin packing: A survey. In: Dorit S,editor. Approximation algorithms for NP-hard problems. Boston: PWS Publishing Company, 1995
[15] Richard vahrenkamp. Random research in the one-dimensional cutting stock problem. European Journal of operational research, 1999(95):191～200
[16] Falkenauer E. A hybrid grouping genetic algorithm for bin-packing. Journal of Heuristics, 1996, 2(1):5～30
[17] Hinterding R., Khan L. Genetic algorithm for cutting stock problems: with and without contiguity, In: Yao X, editor. Progress in evolutionary computation. Lecture notes in artificial intelligence. Berlin: Springer, 1995, Vol. (956): 166～186
[18] Yao X. Simulated annealingwith extended neighbourhood. International Journal of Computer Mathematics,1991(40):169～189.
[19] Ko-Hsin Liang, XinYao, Charles Newton., David Hoffman. A New evolutionary approach to cutting stock problems with and without contiguity. Computers & Operator research, 2002(29):1641～1659
[20] Reeves C. Hybrid genetic algorithms for bin-packing and related problems. Annals of Operators Research, 1996(63): 371～396
[21] 贾志欣.排样问题的分类研究.锻压技术.2004(4):8～10
[22] 贾志欣 . 排样问题的研究现状与趋势. 计算机辅助设计与图形学学报 . 2004,16(7):890～897
[23] 王宏达,尚久浩,樊养余.智能排样算法分析与展望.机电工程技术. 2004, 33(10):9～11
[24] 高伟增,饶运清.排样智能的现状分析及实施策略.机械与电.2001(4):57～59
[25] 王雄志,林福勇.流水车间作业排序问题蚁群算法研究.运筹与管理,2006,15(3):80-84
[26] 王雪飞.一种基于神经网络的非线性时变系统仿真建模方法.计算机研究与发展,2006,43(7):1167-1172
[27] 基于共生矩阵分析的自适应神经系统图像复原算法.计算机辅助设计与图形学报, 2006,18(8):1205-1211
[28] 尹莹莹,孙亮.一种进化型蚁群算法及其在 TSP 问题中的检验.计算机仿真,2006,23(4):167-170
[29] 贾志欣,殷国富,罗阳.二维不规则零件排样问题的遗传算法求解.计算机辅助设计与图形学报, 2002,5(5):467～470
[30] 刘德全,腾弘飞.矩形件排样的遗传算法求解.小型微型计算机系统,1998, 19(12):20～25
[31] 曹炬.实用冲裁件优化排样系统的研究与开发.锻压机械,1999,34(1):44～47
[32] 曹炬,周济.矩形件排样优化的一种近似算法.计算机辅助设计与图形学报, 1995, 7(3): 190～195
[33] 曹炬,胡修彪.大规模矩形件优化排样的遗传算法.锻压机械,1999,34(4): 17～20
[34] 曹炬.二维异形切割件优化排样的拟合算法.中国机械工程,2000,11(4): 438～441
[35] 曹炬.实用异形件优化排样系统的研究与开发.计算机工程与应用, 1999,35(10):37～40
[36] 刘嘉敏,张胜男,黄有群.二维不规则形状自动排料算法的研究与实现.计算机辅助设计与图形学学报,2000,12(7):488～491
[37] 吴建兵,杨杰,吴月华.人工生命与人工智能.模式识别与人工智能,1998,9(3):274～279
[38] 李敏强,寇纪淞,林丹等.遗传算法的基本理论与应用.第一版.北京:科学出版社,2002.
[39] 王小平,曹立民.遗传算法——理论、应用与软件实现.第 1 版.西安:西安交通大学出版社,2002.74～76
[40] Michalewicz. Z.演化程序——遗传算法和数据编码的结合. 第一版. 周家驹,何险峰译.北京:科学出版社,2000
[41] 王煦法,杨奕若,张小俊等. 遗传算法在模式识别中的应用.小型微型计算机系统,1997,18(10):32～36
[42] 王雪梅,王义和.模拟退火法与遗传算法的结合.计算机学报,1997,20(4):381～384
[43] 李元香,张进波,徐静雯等.基于变长编码求解一维下料问题的演化算法.武汉大学学报(理学版)2001.47(3):298～293
[44] 谢涛,陈火旺.多目标优化与决策问题的演化算法.中国工程科学,2002,4(2):59～68
[45] 谢涛,陈火旺,康立山.多目标优化的演化算法.计算机学报,2003,26(8):997～1003
