[doc格式] 求解矩形件优化排样的自适应模拟退火遗传算法

[doc格式] 求解矩形件优化排样的自适应模拟退火遗传算法 求解矩形件优化排样的自适应模拟退火遗 传算法 第2O卷第11期 2008年11月 计算机辅助 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 与图形学 JOURNAIOFCOMPUTER—AIDEDDESIGN&COMPUTERGR APHICS Vo1.2O,No.11 NOV.,2008 求解矩形件优化排样的自适应模拟退火遗传算法 蒋兴波孙吕肖庆刘成城” (北京大学计算机科学技术研究所北京100871) (第二军医大学卫生勤务学系上海200433) .(北京大学电子出版新技术国家工程研究中心北京100871) (jiangxb@founder.corn.cn) 摘要矩形件优化排样是一个NPC问题,在工业界有着广泛的应用.针对该问题,提出一种自适应模拟退火遗传 算法.采用一种基于环形交叉算子和环形变异算子的自适应遗传算法来自动调整交叉和变异概率;同时引入模拟退 火算法对个体适应度大于平均适应度的个体进行退火处理.自适应 模拟退火遗传算法充分发挥了自适应遗传算法 与模拟退火算法各自的全局搜索能力与局部搜索能力.对比实验 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明,该算法结合改进的最左最下布局算法解决矩 形件优化排样问题更加有效. 关键词自适应模拟退火遗传算法;模拟退火算法;自适应遗传算法;形 件优化排样;启发式布局算法 中图法分类号TP391.72 OptimalPackingofRectangleswithanAdaptiveSimulatedAnnealingGenetic Algorithm JiangXingbo?.LuXiaoqing’.’LiuChengcheng ‘(InstituteofComputerScienceandTechnology,PekingUniversity,Beijing100871) (FacultyofHealthServices,SecondMilitaryMedicalUniversity,Shanghai200433) .(NationalEngineeringResearchCenterofNewTechinElectronicPublishing,PekingUniversity,Beijing100871) AbstractAnadaptivesimulatedannealinggeneticalgorithmispresentedfortheoptimallayout problemofrectangles,whichisaNP—completeproblemandpossesseswide spreadapplicationsinthe industry.Adaptivegeneticalgorithm,whichusescircularcrossoveroperator andcircularmutation operator,isadoptedtochangetheprobabilityofcrossoversandmutationsautomatically.Simulated annealingalgorithmisusedtomodifytheindividualswhosefitnessvaluesarehigherthantheaverage valueofthepopulation.Thepresentedhybridalgorithmsyncretizestheglobalsearchcapabilityofthe adaptivegeneticalgorithmandthelocalsearchcapabilityofthesimulatedannealingalgorithm.The comparisonresultsshowthattheoptimalpackingofrectanglescanbeeffectivelysolvedbycombining theadaptivesimulatedannealinggeneticalgorithmwiththeimprovedbottom—leftalgorithm. Keywordsadaptivesimulatedannealinggenetic geneticalgorithm;optimalpackingofrectangles; 矩形件优化排样通常指在宽度固定,长度不限 的矩形版面上排人不同规格的矩形件,使排入区域 algorithm;simulatedannealingalgorithm;adaptive heuristiclayoutalgorithm 的剩余空间最少,从而达到节省版面的目的.它是一 个典型的组合优化问题,应用范围非常广泛,如新闻 收稿日期:2008—01—07;修回日期:2008—0314.蒋兴波,男,1971年生, 硕士,讲师,CCF学生会员,主要研究方向为文字与图形信息处理, 智能算法.吕肖庆,男,1971年生,硕士,副研究员,硕士生导师,论文通讯作者,主要研究方向为出版自动化,人工智能和模式识别(1vxiaoqing@ lest.pku.edu.cn).刘成城,男,1983年生,硕士研究生,主要研究方向为文字与图形信息处理,智能算法. 计算机辅助设计与图形学 组版,布料切割,金属下料等都可归结为优化排样问 题.从计算复杂度上看,该问题是一个NPC问题,其 计算复杂度随着排样规模的增大呈指数增长.因此, 在时间花费和原材料节省之间取得一个平衡点,就 成为该类问题的研究重点. 针对排样问题,常采用遗传算法(genetic algorithm,GA)E13,模拟退火算法(simulated annealingalgorithm,SAA)_】等启发式搜索算法与 最左最下(bottom—left,BL)l_2],最左最下填充 (bottom—leftfill,BLF)I3等启发式布局算法相混合 的方式来求解.混合算法中,搜索算法主要产生矩形 件的一个(或一组)排人顺序,布局算法则按照该顺 序将矩形件排入版面中,并将最终排样长度返回给 搜索算法,由搜索算法根据该长度确定这些顺序的 优劣,进而产生下一个(或一组)排入顺序.Jakobsl_2 将GA和BL布局算法相结合形成混合算法,来求 解优化排样问题;由于BL布局算法存在即使穷举 所有排样顺序,仍不能得到最优解的问题,因此Liu 等_4]提出一种改进的BL(improvedbottom,left, IBL)布局算法,并将其与GA相结合,取得了较好 的实验结果;Yeung等[.和Tang等混合了GA 和IBL布局算法分别求解布料裁剪和金属切割问 题;针对不规则零件的排样问题,贾志欣等提出了 一 种新的启发式布局算法,—最低水平线法,并将 其与GA相结合,取得了一定的排样效果.Fainal8 则将SAA与一刀切,非一刀切布局算法相结合,来 解决切割问题;王罡等则采用SAA与空闲块算 法实现了图片的优化排版.Hopper等叼分别将 GA,SAA等搜索算法与BL,BLF布局算法相混合, 同时给出了7大类共21组实例,并对这些混合算法 进行了测试. 在实际应用中,起源于自然界规律的GA和 SAA各有其优缺点:GA具有全局搜索能力强,鲁 棒性强以及简单通用等优点,却存在局部搜索能力 弱,易早熟等缺点;SAA虽然具有较强的局部搜索 能力,但是由于该算法的状态产生和接受操作每一 时刻仅保留一个解,因此存在缺乏历史搜索信息,收 敛速度慢等缺点. 本文将自适应遗传算法(adaptivegenetic algorithm,AGA)和SAA结合起来,形成了既具有 AGA全局搜索能力,又具有SA局部搜索能力的高 效的,强鲁棒性的自适应模拟退火遗传算法 (adaptivesimulatedannealinggeneticalgorithm, ASAGA),通过将该算法与IBL布局算法相结合, 来解决矩形件优化排样问题. 1排样问题模型 1.1问题描述 矩形件的优化排样问题是将若干个大小不一的 矩形件{,不,…,不}排人一个宽度w固定,长度L 不限的版面T中,使得该版面的利用率最高,从而 达到节省空间的目的.矩形件的排人过程中要求满 足以下约束条件: 1)和7r互不重叠,i~j;i,=1,2,…,. 2)必须排入版面T内,即矩形件在排人过程 中不能超出版面宽度W. 3)的边必须与版面T的边平行,不可以90. 旋转. 1.2数学模型 在由个矩形不(一1,2,…,,2)组成的集合C一 {不,7r2,…,不}中,7t”为一个五元组 不一(z,,叫,h,). 其中,(z,Y)表示第i个矩形件的左下角坐标; (叫,h)表示第i个矩形件的宽度和高度;0为第i 个矩形件的旋转角度,?(0,90.}. 定义1.版面的利用率F是指矩形件的面积之 和与使用版面总面积的比值,即 F一 i=1 f32>/-0 l?o l32+叫?W,if一0.or Iz+h,?V,if=90. 其中,w为版面T的宽度,H为通过IBL布局算法 得到的排样长度. 通过定义l,可以将问题表述为:求满足约束条 件下的排样优化,使得版面的利用率F取得最大 值,即max(F). 式(1)中,由于W,训和都是确定值,因此版 面利用率的大小只与排样长度H有关,为了简化计 算,直接将目标函数F表示为 F—H(2) 式(2)将矩形的排样优化问题进一步转换成对 F(或H)求最小值的搜索问题,即min(F)(或 min(H)). 蒋兴波等:求解矩形件优化排样的自适应模拟退火遗传算法 2算法设计 2.1算法流程 算法lIASAGA+IBL算法 Step1.编码. Step2.k-二0;随机产生1/2个个体组成的初始群体 pop()一{,,J,…,};对每个个体J进行IBI布局;计算 每个个体的适应度_厂(j);设定初始温度. Step3.判断是否满足停止条件.若是,则停止计算,输 出最佳结果;否则,继续下一步. Step4.计算平均适应度f;取个体I,i一0: Step4.1. /20: do if厂(I)> 在J个体的邻域N(,)中随机选择一个体It; 对个体,,进行IBL布局; 计算适应度差值?一1/f(Ij)一1/f(j); if((??O)or(exp(,?/)? rand[0,1])) 将J个体添加人群体中; break else ,z+4-: endif else break endif while(n<loopnum) Step4.2.取下一个个体j…; Step4.3.如果每个个体都已经遍历,转Step5;否则, 转Step4.1. Step5.运用排序选择操作选择m个个体形成新的群体 selpop1(+1),计算selpopl(志十1)的平均适应度,最大 适应度厂…和最小适应度厂…. Step6.计算每对交叉个体的交叉概率P,根据P执行 交叉操作,产生群体crosspop(k+1). Step7.计算每个个体的变异概率,根据P执行变异 操作,产生群体mutpop(k+1). Step8.对群体mutpop(k+1)中的所有个体I进行IBL 布局,计算个体的适应度l厂(,). Step9.降温计算+1一(瓦),pop(k4”1)=mutpop(k4. 1),=+1,转Step3. 2.2ASAGA的描述 2.2.1编码及适应度函数 矩形件的优化排样采用整数编码,即个矩形 件分别用整数1,2,…,进行编号,矩形件的一个排 样 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 对应一个染色体编码,一{不,不,…,},其 中l不l表示第i个被排人版面T的矩形件编号(1? f?),当<O时,矩形旋转90.;否则不旋转,, 表示第个个体. 例如,个体J,的染色体编码为(一53—76110 8—24—9),表示排人顺序为5376llO8249.在 排入过程中,编号为5,7,2和9的矩形进行9O.旋转. 在式(2)中,目标函数只与排样后占用的版面长 度H有关,因此适应度函数可以表示为 (L)一1/F()一1/H(L)(3) 一 旦矩形件的排人顺序和排人方式(旋转与否) 确定后,就可以通过BL和IBL等布局算法求得目 标函数值F(或者排样长度H),并通过式(3)得出该 个体对应的适应度值. 2.2.2模拟退火 1)初始温度 SAA要求初始温度应该足够高,以满足接受概 率为”1”的初始要求.但在实际应用中,初始温度 T0一CxD是无法实现的. 本文采用 T.一×L×(1/一1/fm)(4) 确立初始温度.其中,a为调节参数,L为染色体长 度,和分别为初始群体中的最大适应度和最 小适应度. 通过式(3),可将式(4)改写为 To—aXL×(H一H.)(5) 其中H和H分别为初始群体中最大排样长度 与最小排样长度. 2)降温函数 在SA中,由于线性降温会在高温区域停留较 长时间,而接近低温区域时,温度下降又会过快,使 得系统会很快冻结,不能很好地完成搜索工作.比例 降温则弥补了这一缺陷,本文采用的比例降温函 数为 T抖l—d(T)一×Tk(6) 其中为比例因子,一般取小于1的正数. 3)新个体接受概率 用适应度作为ASAGA中的能量.设J邻域中 产生的新个体为I,,记s为接受I,的概率,接受概 率定义为 f1,厂(Ii)?厂(J) s[IJ一1eXp(一)’,(< 1428计算机辅助设计与图形学 为了缩短搜索时间,提高搜索效率,ASAGA只 对AGA中适应度高于群体平均适应度的较优个体 (而不是全体个体)进行SA搜索;同时,为了进一步 提高AGA中群体的多样性,ASAGA将SAA得到 的较优个体(优于当前个体)直接添加到当前群体中 (而不是替换当前个体). 2.2.3自适应交叉,变异概率 GA的性能在很大程度上受到交叉概率P和变 异概率P的影响,本文采用改进自适应遗传算 法l_1,其对P,P的自动调节如 j二,厂?J…Jag f<{ 堡,厂?fa n1axavg 厂<_,, (8) (9) 其中,厂为每代群体的平均适应度,为群体中 最大适应度,.厂为要交叉的2个个体中较大的适应 度,_厂为变异个体的适应度,PPP和P? [o,1]. 2.2.4操作算子 1)选择 为了减少上一代产生的最佳个体丢失,本文在 采用排序选择方法的同时,还混合使用了最优保存 策略. 排序选择方法的主要着眼点是个体适应度值之 间的大小关系,对个体适应度是否取正值或负值以 及个体适应度之间的数值差异程度并无特别要求. 选择操作步骤如下: Step1.对群体中所有个体按适应度从大到小排序. Step2.按 P(J】一×(1一)(10),,,f 计算每个个体的选择概率.其中,表示排列在第i个位置 个体的选择概率,m表示群体大小,A为调节参数. Step3.基于Step2计算得出的个体概率值用比例选择 (赌盘选择)的方法产生下一代群体. 2)交叉 交叉是产生新个体的主要方法.本文采用环形 部分交叉:首先随机生成起始交叉点P?[1,]; 其次随机生成交叉长度L?[1,];之后将P,后 的L位基因进行交换,如果P+L>n,则将染色 体尾部的一L,位基因以及首部P,+L,,位基 因进行互换;最后依次将未出现的基因填入空白基 因位. 交叉操作步骤如下: Step1.z一0. Step2.对m个个体进行两两随机配对,产生m对个体 (一m/2的下取整). Step3.—i+1,如果I>m,交叉结束;否则,继续. Step4.取配对个体,根据平均适应度…最大适应度 l厂m…配对个体中的较大适应度,P一和P一并按式(8)计 算交叉概率P. Step5.在[O,1]之间产生随机数Pd,如果Pd>P, 转Step3;否则,对当前配对个体进行环形部分交叉,转 Step3. 3)变异 变异是产生新个体的辅助方法,它决定了GA 的局部搜索能力,同时保持群体的多样性.本文变异 包括旋转变异和排人顺序变异2部分. a.旋转变异.采用单点取反和环形部分取反2 种方式. 单点取反变异.首先随机生成变异点P?[1, ];其次取反.例如,对于个体J,一(不,不,…,, … ),P一i,则变异后产生的新个体为,一(Tr, 不2,…,一7r,…,7r). 环形部分取反变异.首先随机生成变异点 P?[1,];其次随机生成变异长度L?[1,”]; 最后将P后的L位取反,如果P+L>n,将 染色体尾部的—L位基因以及首部的P+L一 n位基因取反. b.排入顺序变异.采用两点位置互换与环形部 分逆转2种方式. 两点位置互换变异.首先随机生成2个变异点 i,i.?[1,,2];其次将2个基因互换.例如,,,一(不, 2,…,不订,…,,…,不),i1,i2?[1,],则变异后产 生的新个体为I:=(不1,7t”2,…,7l”…,,…,). 环形部分逆转变异.首先随机生成变异点 P?[1,n];其次随机生成变异长度L?[1,]; 最后将P后的L位逆转,即将(P+i)rood (即P+i对取模)与(P+L一)rood互换, i?Eo,L/2]. 变异操作步骤如下: Step1.i一0. Step2.—i+1,如果i>m,转Step6;否则,继续. Step3.根据平均适应度_厂a…最大适应度厂m…个体适 应度f,P和P.并按式(9)计算个体J的变异概率P. Step4.在[o,1]之间产生随机数Pdl,如果Pd】>P, 转Step2;否则继续. Step5.在[O,1]之间产生随机数P如果P< 0.7,则进行单点取反变异;否则,进行环形部分取反变异,转 Step2. 蒋兴波等:求解矩形件优化排样的自适应模拟退火遗传算法 Step6.z一0. Step7.—+1,如果>m,变异结束;否则,继续. Step8.根据个体适应度_厂,平均适应度…最大适应 度厂m,P和P,并按式(9)计算个体,的变异概率P. Step9.在[O,1]之间产生随机数P.,如果P…>P, 转Step7;否则,继续. Stepl0.在Eo,1]之间产生随机数Pd{,如果Pa< 0.7,则进行两点位置互换变异;否则,进行环形部分逆转变 异,转Step7. 2.3启发式布局算法 BLF虽然能取得较好的排入效果,但其复杂度 为O(n.)],而BL布局算法的效果明显不如IBL 布局算法],因此本文采用IBL布局算法来实现矩 形件在版面T上的排入. IBL布局的排入过程如下: Step1.将Ij(1)排人在版面丁的左下角. Step2.将第1i()(i一2,3,…,n)个矩形件置于版面的 右上角,垂直向下移动该矩形件,一直到不能移动为止;然后 水平向左移动该矩形件,在向左移动过程中,遵循向下优先 的原则. Step3.转Step2,直到所有的矩形件都排入完毕. IBL的具体布局过程如图l(染色体为一2413 — 5)所示. 3实验结果 图1IBI布局示意图 为了验证ASAGA对优化排样求解的有效性, 本文将AGA+IBL和ASAGA+IBL与文献[2, 10]中给出的实例进行了实验对比分析. 实验平台为P?3.0GHz,512MB,Windows Server2003,运行参数如表1所示. 表1运行参数 表1中,P和P表示交叉概率;P和P.表 示变异概率;LoopNum表示模拟退火对较优个体 最多可进行的邻域搜索次数;a,和分别表示式 (5),(6),(10)中的调节参数和比例因子,一般为多 次实验取得的经验值. 文献[2]中,Jakobs将4Ox15的矩形版面分成 了25个小矩形和50个小矩形2组,并将版面宽度 w定为40,用GA+BL对该2组实例进行了优化 排样求解;在文献/-4]中,Liu等对文献[2]中的布局 算法进行了改进,采用了GA混合IBL对该实例进 行求解. 本文测试中,AGA的群体大小和生成代数参照 文献[4],分别为20和100;ASAGA的群体大小和 生成代数则分别设为2O和60.表2所示为对文献 [2]中的每组实例重复运行100次,得到的最小排样 长度H…,平均排样长度H,最大排样长度H 以及100次运行的总时间T小 表2中,w表示每个大类排样版面的宽度,H 表示排样最优长度,表示每组实例的矩形件个数. 从测试数据可以得出,对于该2组实例,AGA+IBL 与ASAGA+1BL求得的结果皆明显优于文献[2] 和文献[4]中得出的结果;同时,相对于AGA+ IBL,ASAGA+IBL求解效率更高,结果更优. 文献[10]中,Hopper等给出了7大类数据,每 大类由3组实例组成.本文的测试中,AGA的群体 大小和生成代数参照文献Elo],分别为5O和1000; ASAGA的群体大小和生成代数则分别设为50和 400,对每个实例测试50次.每大类的平均排样长度 如表3所示(即共15O次测试的平均排样长度). 表2实验结果比较 计算机辅助设计与图形学2008年 表3实验结果比较 文献Elo]中,Hopper等将不同算法分别对不同 数量及不同类型的矩形件排样进行了对比实验分 析.在搜索算法相同的情况下,BLF算法的排样效 果优于BF算法,但其时间复杂度却较高,为O(n.), 而后者为0();在布局算法相同的情况下,混合 排样算法排样效果从高到低依次是SA—GA, NE(na~veevaluation——进化算法)一HC(hill— c1imbing——爬山算法)和RS(randomsearch—_-- 随机搜索算法),但是SA迭代次数较高,一般是GA 和NE的5倍. 从表3可以看出,使用AGA+IBL和ASAGA+ IBL的求解结果明显优于文献[1O]中的GA+BL 和SA+BL得出的求解结果;相对于AGA+IBL, ASAGA+IBL能取得更优解. 表4所示为由AGA+IBL与ASAGA+IBL对 21组实例求得的目标函数值(最小排样长度H…, 平均排样长度H…最大排样长度H)以及50次 运行的总时间丁.从实验结果可知,无论是优化 排样长度还是计算时间,ASAGA+IBL皆优于 AGA+IBI. 表4对21组实例求得的目标值及运行总时间 蒋兴波等:求解矩形件优化排样的自适应模拟退火遗传算法1431 4结论 矩形件优化排样问题在实际应用和科学研究方 面都具有重要意义,虽然相关人员对该问题做了大 量的研究,但至今仍未找到一个完美的解决方案.本 文用ASAGA+IBL进行求解,取得了较快的收敛 速度和较高的搜索精度.但在理论方面的分析和证 明还需要完善;同时,在启发式布局方面,如何在一 个比较低的计算复杂度下获得一个较高的布局效 果,也有待进一步研究. [1] [23 E33 E4] 参考文献 [5] [6] [7] [83 r9] WangLing.Intelligentoptimizationalgorithmswith applicationsEM].Beiiing:TsinghuaUniversityPress,2001 (inChinese) (王凌.智能优化算法及其应用EM].北京:清华大学出版 社,2001) JakobsS.Onthegeneticalgorithms{orthepackingof polygons[J].EuropeanJournalofOperationalResearch, 1996,88(1):165-181 ChazelleB.TheBottom—leftbinpackingheuristic:an efficientimplementation[j].IEEETransactionson Computers,1983,C32(8):697—707 LiuDQ,TengHF.AnimprovedBIalgorithmforgenetic algorithmoftheorthogonalpackingofrectanglesEJ]. EuropeanJournalofOperationalResearch,1999,112(2): 4]3—420 [10] [11] YeungLHW,TangWKS.Ahybridgeneticapproachfor garmentcuttingintheclothingindustry[J].IEEE TransactionsonIndustrialElectronics,2003,50(3):449— 455 TangKW,TangWKS.Metalcuttingwithhybridgenetic algorithmEc]//Proceedingsofthe3rdIEEEInternational ConferenceIndustrialInformatics,Perth,2005:735-739 JiaZhixin,YinGuofu,LuoYang.Two—dimensional irregularpartspackingwithgeneticalgorithmEJ3.Journalof ComputerAidedDesign&ComputerGraphics,2002,14 (5):467-470(inChinese) (贾志欣,殷国富,罗阳.二维不规则零件排样问题的遗传 算法求解EJ].计算机辅助设计与图形学,2002,14(5): 467—470) FainaL.Anapplicationofsimulatedannealingtocutting stockproblemEJ].EuropeanJournalofOperational Research,1999,114(3):542-556 WangGang.PengGuohua.YuQian.Applicationof simulatedannealingalgorithminpicturemakeupoptimization EJ].JournalofSouthwestUniversityofNationalities: NaturalScienceEdition,2006,32(3):586-590(inChinese) (王罡,彭国华,余迁.模拟退火算法在图片优化排版中 的应用EJ3.西南民族大学:自然科学版,2006,32(3): 586—59O) HopperE,TurtonBCH.Anempiricalinvestigationof meta—heuristicandheuristicalgorithmsfora2Dpacking problemEJ].EuropeanJournalofOperationalResearch, 2001,128(1):34—57 WangXiaoping,CaoLiming.Geneticalgorithm:theory, applicationandimplementation[M].Xi’an:Xi’anJiaotong UniversityPress,2002(inChinese) (王小平,曹立明.遗传算法——理论,应用与软件实现 [M].西安:西安交通大学出版社,2002)