湖南大学学报(自然科学版) 2006年 样位置．按原排样序列排样．更新零件最高轮廓线． b．否则，查询与最低水平线相邻的左右两段水 平线，将最低水平线提升到与高度较低的一段平齐， 更新零件最高轮廓线． 重复Step2，直至能排入该零件． 重复上述过程，直至所有零件排放完毕． 由于该法在排人零件时总是考虑整体排样高度 的调整，设法降低整体排样高度，因此称之为“高度 调整法”．显然，高度调整法同样满足BL条件．图2 显示了该方法与最低水平线法排放过程中的差异． 日目 圆圆国 (c)高度调整法 (b)最低水平线法 (a)捧样问题 图2 最低水平线法与高度调整法排样结果比较 Difference packing pattern between Lowest Fig．2 Horizontal Line algorithm and Height Adjustment algorithm 2．3最优选择策略 在选择运算中应用最优选择策略，可保证当前 群体中适应度最高的个体进入下一代；可保证最好 的个体保存到最后；可加快遗传算法的收敛速度．最 优选择策略的操作过程是：找到当前种群中适应度 最高和最低的个体；若当前最好的个体优于迄今为 止所找到的最佳个体，则代替之，然后用迄今为止最 好个体替换当前种群中最差个体；否则仅用迄今为 止最好个体替换当前种群中最差个体． 2．4适应度函数 遗传算法中利用适应度函数评价解的好坏，适 应度函数值越优，解的质量就越高．本文采用如下的 适应度函数：厂(P)=A／A1，其中A是排人矩形 件的总面积，A．是排样图整体高度轮廓线以下的板 材面积．显然，适应度函数值越大，解的质量就越高． 3排样算例 基于上述算法，开发了优化排样程序，进行了排 样实验．实验中取群体规模M=20，交叉概率P。= 0．7，变异概率P。=0．1．板材宽度为720 InIn，高度 不限．共有9种零件，数据见表1． 利用文献[4]中的算法进行20次重复的实验，得 到的适应度函数值的平均值为0．890 3．利用本文算法 进行20次重复实验，得到的适应度函数值的平均值为 0．911 6．得到的最优排样结果如图3所示． 万方数据 Tab．1 表1零件数据 The parts data of the case 图3排样效果图 №．3 The layeut chart of the case 4结论 针对二维不规则零件排样问题，对最小包络矩形 求取方法、遗传算法选择算子、解码算法进行了改进， 提出了～种改进的优化排样算法．从算例计算结果可 见，本文算法求得了较文献[4]更好的解，本文算法更 为有效． 参考文献 1|H。】砌E，TURTON B．A genetic algorithm for a 2D industrial [2] [3] packing problem[J]．Computers and Industrial Engin∞ring，1999， 37(1—2)：375—378． JOKOBS S．On genetic蛔th】s for the pacbng of pC峥固蛐[J]． Euregean Ja删of(枷donaIResearch，1996，88(1)：165—181． rithm of the ortl粥al packing of recta]【1916[J]．EuIDp∞n Jo‘lmal of ()perat制Research，1999，112(2)：413—420． LIu D Q，TENG H F．An improved BL-algorithm for genetic al驴一 [4]贾志欣，殷国富，罗阳，等．矩形件排样的模拟退火算法求解[J]． 四川I大学学报：工程科学版，2001，33(5)：35—38． JIA z X，YIN G F，LU0 Y，甜a1．Application of simulated ann池 Er研嘶Science，2001，33(5)：35—38．(InChinese) to the r。ctarl目】Iar packing problem[J]．Journal of Schuan University： 15 J LI M，ZHOU Z K．Particle s～varrfl optimizaticn for rectangl】lar parts optimal layout[A]∥Proc congress∞3rd International Syng瑚iurn orl[nstnmlentation Science and Technology．2004：327—331． [6]龚志辉，黄星梅．二维矩形件优化排样算法的改进研究[J]．湖南 大学学报：自然科学版，2003，30(3)：47—49． GONG Z H，HUANG X M．Improved algoriffan for re呦ngI】Iar pack— ing problem[J]．Jam∞l of Htm．an University：Nature Sciences，2003， 30(3)：47—49．(In Chinese) [7]曹矩，周济．矩形件排样优化的一种近似算法[J]．计算机辅助设 计与图形学学报，1995，7(3)：190—195． CAO J，ZHOU J．An approxinlate algorithm for rectarlglllar cutting stock probldn[J]．Jcxm均l of Camputer-Aided Design&Computer Graphies，1995，7(3)：190—195．(In Chinese) [8]H。LI AND J H．Adaptation in Natural and Artificial SySt∞l M J． Cambridge：M1T Press，1975． 

基于改进遗传算法的二维不规则零件优化排样 作者： 李明， 张光新， 周泽魁， LI Ming， ZHANG Guang-xin， ZHOU Ze-kui 作者单位： 工业控制技术国家重点实验室,浙江,杭州,310027;浙江大学,控制科学与工程系,浙江,杭州 ,310027 刊名： 湖南大学学报（自然科学版） 英文刊名： JOURNAL OF HUNAN UNIVERSITY(NATURAL SCIENCES) 年，卷(期)： 2006,33(2) 5次 被引用次数： 参考文献(8条) 1.HOPPER E;TURTON B A genetic algorithm for a 2D industrial packing problem[外文期刊] 1999(1-2) 2.JOKOBS S On genetic algorithms for the packing of polygons[外文期刊] 1996(01) 3.LIU D Q;TENG H F An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles 1999(02) 4.贾志欣;殷国富;罗阳 矩形件排样的模拟退火算法求解[期刊论文]-四川大学学报(工程科学版) 2001(05) 5.LI M;ZHOU Z K Particle swarm optimization for rectangular parts optimal layout[外文会议] 2004 6.龚志辉;黄星梅 二维矩形件优化排样算法的改进研究 2003(03) 7.曹矩;周济 矩形件排样优化的一种近似算法 1995(03) 8.HOLLAND J H Adaptation in Natural and Artificial Systems 1975 本文读者也读过(10条) 1. 曹新明.蒋瑞斌.CAO Xin-ming.JIANG Rui-bin 不规则零件最小包络矩形的求解研究[期刊论文]-科技通报 2007,23(1) 2. 李明.宋成芳.周泽魁.LI Ming.SONG Cheng-fang.ZHOU Ze-kui 一种二维不规则零件优化排样算法[期刊论文]- 四川大学学报（工程科学版）2005,37(4) 3. 陈竞驰 二维不规则排样问题研究[学位论文]2009 4. 徐利娜 二维不规则零件排样及相关问题研究[学位论文]2007 5. 翟红岩.苏传生.张莹.史俊友.ZHAI Hong-yan.SU Chuan-sheng.ZHANG Ying.SHI Jun-you 基于神经网络的不规 则件排样技术[期刊论文]-青岛科技大学学报（自然科学版）2009,30(4) 6. 邢长征.孙玉庆.XING Chang-zheng.SUN Yu-Qing 基于模拟退火遗传算法的板材优化下料[期刊论文]-辽宁工程 技术大学学报（自然科学版）2006,25(3) 7. 黄建江.须文波.董洪伟.HUANG Jian-jiang.XU Wen-bo.DONG Hong-wei 一种不规则零件排样的新粒子群优化策 略[期刊论文]-计算机工程与应用2007,43(19) 8. 宋亚男.叶家玮.邓飞其.冯穗豫 不规则图形排样系统中靠接算法比较研究[期刊论文]-计算机工程2004,30(19) 9. 胡志刚.王耘.胡树根.徐以国.HU Zhi-gang.WANG Yun.HU Shu-gen.XU Yi-Guo 单亲遗传算法在二维不规则件排 样中的应用[期刊论文]-轻工机械2009,27(1) 10. 侯桂玉.崔耀东.黄少丽.杨剑.潘涛.HOU Gui-yu.CUI Yao-dong.HUANG Shao-li.YANG Jian.PAN Tao 一种求解 圆形件下料问题的启发式算法[期刊论文]-计算机工程2010,36(13) 引证文献(5条) 1.陈婷.许超 钣金零件排样技术及其发展[期刊论文]-锻压装备与制造技术 2008(4) 2.郭昆.傅仰耿.陈建华 基于MVC模式的铁制工艺品排料系统的研究[期刊论文]-福建电脑 2008(11) 3.李敬花.樊付见.王昊.余锋 遗传模拟退火融合算法求解工程二维排样问题[期刊论文]-计算机集成制造系统 

2011(9) 4.谢友宝.罗婷婷.李凌辉.吕永海 混合遗传算法在飞机钣金零件排样中的应用[期刊论文]-机械与电子 2009(12) 5.贾丹.董方敏 二维优化排样问题研究[期刊论文]-计算机系统应用 2008(7) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_hndxxb200602012.aspx