（应用数学专业论文）优化排样问题的近似算法.pdf

华中科技大学硕士学位论文 摘要 优化排样是一个属于在计算理论上非常困难、在实际中有广泛应用的急待解 决的课题。随着当今计算机技术、c a d 技术和人工智能技术的飞速发展，为人们 提供了用计算机进行辅助优化排样的可能性。本文从优化理论韵数学模型及其对 优化排样问题的适应性和有效性等方面对一维和二维优化排样问题进行了研究， 并根据优化排样的特点以及它们在实际应用中的不同要求构造了具有针对性的优 化排样算法。 关于一维优化排样问题，首先用邻域搜索算法进行了求解，该方法避免了求 解大规模分割模式和线性规划问题，对小规模问题有较好的效果。对于大规模的 线材分割问题，运用进化规划和邻域搜索算法相结合的方法进行求解，实验表明 该算法对大规模问题有较好的效果。蚂蚁算法是近年发展起来的求解组合优化问 题的一种仿生算法，本文尝试性的利用该算法求解一维排样问题。 关于二维矩形件优化排样问题，对矩形件中有多边成比例的情况，提出了一 种算法，该算法根据矩形件的边长对板材长宽求余后余数大小，确定矩形件的排 放；而为了满足工艺上一块板材尽量排放不多于三种零件的要求，提出了一种丁 字尺方法解决该问题，该方法保证在每块板材上排放的矩形件少于三种：基于一 维问题的蚂蚁算法，本文将二维矩形件排样翘题转化为一维背包问题，然后进行 求解。 文章最后进行了总结，并提出了有待进一步研究的问题。 关键词：矩形件排样近似算法蚂蚁算法组合优化 华中科技大学硕士学位论文 a b s t r a c t o p t i m a ll a y o u ti s a nu r g e n tp r o b l e mt h a ti sv e r yd i f f i c u l ti nc o m p u t a t i o nt h e o r y , b u th a sb e e n w i d e l yu s e d i np r a c t i c e w i t ht h er a p i dd e v e l o p m e n to ft h et e c h n i q u e so f c o m p u t e r , c a d a n da r t i f i c i a li n t e l l i g e n c e ，t h ec o m p u t e ra i d e do p t i m a ll a y o u tb e c o m e s p o s s i b l e t w oc l a s s e so fb a s i co p t i m a ll a y o u tp r o b l e m sa r es t u d i e d ：o n e - d i m e n s i o n a l s t o c k - c u t t i n gp r o b l e ma n dr e c t a n g u l a rl a y o u tf r o m t h ea s p e c t so fm a t h e m a t i c a lm o d e l o f o p t i m i z a t i o n a n di t sa d a p t a b i l i t ya n d e f f i c i e n c y f o rt h e o p t i m a ll a y o u t p r o b l e m s a c c o r d i n g t ot h en a t u r e so f t h e o p t i m a ll a y o u tp r o b l e m s a n dd i f f e r e n tn e e d s o f t h e mi np r a c t i c e ，s e v e r a lo p t i m a ll a y o u ta l g o r i t h m sa r ep r e s e n t e d b a s e do nt h ei d e ao fk - o p ta l g o r i t h mf o rt s p , p r e s e n tak - o p ta l g o r i t h mf o rt h e o n e d i m e n s i o n a lc u t t i n g - s t o c kp r o b l e m t h ea l g o r i t h ma v o i d st h eg r e a tc o m p l e x i t yo f d e d u c i n gc u t t i n g - p a t t e r n sa n ds o l v i n gl p , r e s u l ts h o w st h a tt h ea l g o r i t h mi sv a l i dt o s m a l l s c a l e p r o b l e m a n d f o rt h e l a r g e s c a l ep r o b l e m ，t h ep a p e rp r o p o s e s a n e v o l u t i o n a r ya p p r o a c h ，e x p e r i m e n ts h o w si t w o u l db em o r ee f f e c t i v e a n tc o l o n y a l g o r i t h mi sa n e w t y p eo f s i m u l a t e de v o l u t i o n a r ya l g o r i t h m ，t h ep a p e r a t t e m p t t os o l v e t h es t o c k c u t t i n gp r o b l e mb yu s i n g t h i sa l g o r i t h m b a s e do na c t u a lb a n k i n gt e c h n o l o g i c a tr e q u i r e m e n to fr e c t a n g u l a rp i e c e s ，t h i s p a p e re v a l u a t e dt h er e m a i n d e ro f t h el e n g t ho rw i d t ho fr e c t a n g u l a rs h e e tm a t e r i a lt o t h a to f r e c t a n g u l a r p i e c e s ，a n dp r o p o s e d a na p p r o x i m a t e a l g o r i t h mf o rt w o d i m e n s i o n a l l a y o u to ft h er e c t a n g u l a rp i e c e s o nt h er e c t a n g u l a rs h e e tm a t e r i a la c c o r d i n gt ot h e r e s u l to fr e m a i n d e r f o r i m p r o v i n gu n l o a d i n gp r o d u c t i v i t y , p r o p o s e ats q u a r e a p p r o x i m a t ea l g o r i t h m f i r s td i v i d e dr e c t a n g u l a rs h e e ti n t ot h r e eb l o c k s ，t h e np l a c ea k i n do f r e c t a n g u l a rp i e c e so n e a c hb l o c k e x p e r i m e n t a lr e s u l ts h o w st h a tt h ea l g o r i t h m i sv a l i dt ot h el a r g e s c a l er e c t a n g u l a rl a y o u ta n de n s u r e st h ep r o d u c t i v i t yo f u n l o a d i n g t w o - - d i m e n s i o n a ls t o c k c u t t i n gp r o b l e m c a nb es e t t l e db y s o l v i n g t w oo n e - - d i m e n s i o n a l k n a p s a c kp r o b l e m s ，t h i sp a p e rp r e s e n t s an e wa l g o r i t h mb a s e d0 1 1t h ea n t c o l o n y o p t i m i z a t i o n i d e a a tl a s t ，a l lt h ew o r k si nt h i st h e s i sa r es u m m a r i z e da n ds o m e p r o s p e c t sa r ea l s o p r o p o s e d k e y w o r d s ：r e c t a n g u l a r p i e c e a n t c o l o n ya l g o r i t h m l a y o u ta p p r o x i m a t ea l g o r i t h m c o m b i n a t o r i a lo p t i m i z a t i o n 独创性声明 本人声明所呈交的学位论：贮是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名：勿舫 日期：矿矾年胡垆 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和忙编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于不保密z ( 请在以上方框内打“4 ”) 学位论文作者签名：勿扣 4 日期甜呻月妒 朽丫 姊懒 臌僻 瞰肋指日 华中科技大学硕士学位论文 1 1 选题背景及其意义 1 绪论 1 1 1 优化排样问题的意义 计算机辅助优化排样，又称为c a n ( c o m p u t e r a i d e d n e s t i n g ) ，是广泛应用 的计算机辅助技术之一。在国民经济的许多行业中，都会遇到材料分割问题。c a n 的应用，就是生成高利用率的材料分割排样方案。因此，凡是需要进行材料分割 的行业，都可以利用c a n 排样，达到节约材料，降低产品成本的目的。实际意 义具体表现在以下几个方面1 】： 1 ) 节约材料 人工排样受人的工作态度与能力所限制，很难给出材料利用率最高或接近最 高的排样方案。应用计算机辅助优化排样，可以充分发挥计算机强大的计算能力， 经过大量的排样方案的比较，选出材料利用率最高或接近最高的排样方案，达到 节约材料的目的。 2 ) 减少排样工作量 人工排样时，为了得到一个较好的排样方案往往需要长时间的反复。应用计算 机辅助优化排样，可以在非常短的时间内完成排样任务，并且得到高质量的排样方 案。 3 ) 化简切割工艺 排样时经常遇到这样的情况，存在许多材料利用率非常接近的排样方案。称 材料利用率最高的排样方案为最优排样方案。应用计算机辅助优化排样，可以在 大量的达到最优或接近最优的排样方案中，选择切割工艺尽可能简单的排样方案， 减少分割工作量。 1 1 2 优化排样问题的分类 通常根据被分割材料的形状，将排样问题分为以下几种类型【l 】【6 】【7 】 8 】 9 】= 华中科技大学硕士学位论文 1 ) 一维排样问题 一维排样问题，又称线性排样问题，是指在排样时只需要考虑一个方向的尺 寸。例如，将较长的线材、管材、棒材等，分割成各种较短的毛坯。典型的应用 领域包括门窗、金属结构、金属制品、普通机械、专用设备、交通运输设备、电 气机械等制造行业，这些行业所属企业在制造过程中，需要将线材分割成较短的 毛坯，用于生产产品。 2 ) 一维半排样问题 一维半排样问题，又称为卷材排样问题，是指被分割的材料宽度较小，长度 很大，排样时可以将长度看作无限长。布匹、纸张、皮革、塑料、金属网、金属 薄板等，都可以以卷材的形式供应。典型的应用领域包括服装、皮革制品、纸制 品、塑料制品等制造行业。当金属薄板的厚度在o 5 1 r a n 以下时，经常以卷材的形 式供应，例如生产空调器用的镀锌钢板等。在分割过程中，通常先沿着卷材的长 度方向，将其分割成很长的条带，然后再将条带分割成较小的毛坯。 3 ) 二维排样问题 二维排样问题，又称为板材排样问题，是指将板材分割成各种形状的毛坯。 这些毛坯可以是矩形、圆形、扇形等规则形状，也可以是不规则形状。典型的应 用领域包括木材制造业、家具制造业、普通机械制造业、专用设备制造业等行业。 4 ) 三维排样问题 在三维排样问题中，材料与毛坯都必须按立体形状处理。典型的应用领域包 括木材加工业，在那里需要将原木分割成尺寸较小的方木。原木的锥度、长度、 弯度可以不同，但方木的尺寸都很规则。需要确定分割方案，使原木分割后产生 的方木价值尽可能大。 1 1 3 优化排样问题的复杂性 尽管国内外大量学者很早就开始了优化排样问题的研究工作，但到目前为止 仍然没有获得令人非常满意的解决方法。这主要是问题本身的复杂性造成的。 从计算复杂性来看，优化排样问题是属于计算机科学理论前沿领域的一类问 2 华中科技大学硕士学位论文 题：n p 完全问题。n p 完全问题是n p 类中最困难的问题 2 1 1 3 1 。而对于n p 完全问 题，传统的理论和算法均有其局限性，或者根本无法求解，或者其求解的计算量 是爆炸性的，即使用最快的计算机进行计算，所花的时间和费用也是人们不可接 受的。 排样问题需要处理数量庞大的可行切割方式，在一维排样中，可行分割模式 的数量很容易超过百万，二维排样问题的可行分割模式的数量更为巨大，无论对 于整数规划的数学模型还是其他的模型都不可能通过对所有的可行分割模式一一 列举来规划优选，因为即使是利用现在最先进的计算机处理稍微复杂的排样问题 也是无法胜任的。所以在各种优化排样的数学模型中，几乎都利用了启发式算法 和其他方法相结合，来减少庞大数量的可行分割模式给运算结果带来的障碍。 现在已经提出了很多针对不同结果满意度的启发式算法及其改进算法，但它 们的分支和计算量仍然很大。各种算法在软件的使用过程中，为了增加搜索速度、 减少计算误差和避免计算时间过长，提出了一系列处理方法：包括设置某一闽值 因子控制可行分割模式的生成数量、设置单一排样最低的材料利用率、限制排样 零件的组合、设置消减计算机计算误差的精度、设置各种闽值等，这一系列的处 理包括启发式算法本身都会引起优化计算的结果偏差。而且在处理庞大数量的排 样方案时，对搜索的深度和广度而言，相同算法条件下，随搜索深度和广度的增 加，搜索时间越长。所以任何启发式函数的设置都限制遍历全部分割模式而引起 算法误差【5 j 。 由上面可见，优化下料理论研究较多，但在实际应用中没有一种能彻底消除 程序误差。程序误差的存在，使实际应用中往往出现这样的情况：将原始排样的 数据做微小改变，结果会大大不同；将程序中某一阈值因子改变，优化结果会很 大变化：将消除计算机误差处理的精度改变，结果也将发生一定变化：一个优化 程序可能对某一组数据效果相对较好，对另外一组数据效果相对并不理想等。这 些都是由优化排样问题本身的复杂性和算法本身所决定的。 从以上分析可以看出，很难设计一种算法，使之满足各种排样方式和排样数 据。所以，对于优化排样问题的研究一直是国内外学者研究的重点，但由于n p 华中科技大学硕士学位论文 问题在理论上没有突破，所以对于优化排样问题的研究也难以有突破性的进展。 目前，主要是对于特定的某一类问题，研究相应的启发式算法。 1 1 4 研究排样问题的可行性 到目前为止，所有的n p 完全问题还没有找到多项式时间的算法。然而类似 于优化排样这样的n p 完全问题具有很重要的意义，经常会遇到。所以对于这类 问题，有必要寻求有效的算法。目前通常采用以下几种办法【2 】【6 】： ( 1 ) 对特殊实例求解。遇到一个n p 完全问题时，应仔细考察是否必须在一 般的意义下求解。也许只要针对某种特殊情形就够了。特殊情形下的n p 完全问 题常常有高效的算法。 ( 2 ) 用动态规划法，回溯法或分支定界法求解。在许多情况下，他们比枚举 方法要有效得多。 ( 3 ) 用概率算法求解。有时可通过概率分析法来证明某个n p 完全问题的 “难”实例是很稀少的。因此可以用概率算法来求解这类n p 完全问题，设计出 在平均情况下的高效算法。 ( 4 ) 只求近似解。实际中遇到的n p 完全问题不一定要求精确解，可能只要 求在一定的误差范围内的近似解就够了。许多n p 完全问题的近似解法可以在很 少的时间内得到一个精度很高的解。因此在实践中人们常常只是求n p 完全问题 的近似解。 ( 5 ) 用启发式方法求解。在用别的方法都不能奏效时，也可采用启发式算法 求解n p 完全问题。这类方法根据具体i n - j 题的启发式搜索策略来寻求问题的解。 在实际使用时可能很有效，但很难说清它的道理。 尽管优化排样问题很难处理，但是可以遵循上述思想，结合具体的实际问题， 利用现有的数学知识和运筹学理论和方法，找到实用有效的算法。本文的工作是 基于这种思想展开的。 华中科技大学硕士学位论文 1 2 优化排样问题数学模型 1 2 1 一维优化排样问题的定义 一维优化排样问题是指按照某种分割方案，将给定长度的线材分割成一 定数量、指定长度的较短毛坯，其目标是寻求最优的分割方案，使得既满足需要， 又要使总的原材料利用最少，以此达到降低成本、提高经济效益的目的。 1 2 2 一维优化排样问题的数学模型 对于一维优化排样问题，设线材的长度为上，要求截m 种长度不同并满足需 要的条料1 ，2 ，m ，其长度分别为o ，：，z 。，需求数量为q ，j ：，* o t js 。 对于该问题，每根线材有多种不同的分割模式，定义如下分割模式向量： 吼= ( a l k , a 2 ，口m 女) ； k = 1 , 2 ，1 4 j ； 其中，u = 1 , 2 ，m ) 表示分割模式a 。在原材料上所分割的第i 种条料的数目，w 为分割模式的总数目。记唯为第七种分割模式的损失，则有： m n ，i = l ，2 ，m ) 。如果以为合理的分割模式，则必有 l - l o r k 2 ) 进行变换。但对于排列序列中元素个数的不同，选 华中科技大学硕士学位论文 一= = = = = = = = = = = j j _ 目= = = # = = = ；= = = ；= = = = = = = # 取怎样一个较优的k 值，理论上没有确定的说法【3 剐。 该算法的实现过程主要有以下几步： s t e p l ：根据需要排样零件的种类和数目，随机产生一种零件排列。 s t e p 2 ：对上面初始排列方式进行k - s w a p ( k 2 ) 变换。 s t e p 3 ：对每种变换后的排列，计算分割余料总和及原线材利用根数，并进行 比较，输出最优结果。 2 1 4 算例 下面以沈阳远大企业集团要求的一个实际数据为例，采用4 一s w a p 变换用该 算法进行了计算。原材料的长度为4 8 5 0 ，需要的零件种类、长度和数量如表2 1 ： 表2 1 一维排样数据一 【类别 l23456789l o1 1i 21 3 i 长度1 2 9 7 1 2 2 29 6 49 1 98 9 89 4 21 1 7 51 0 9 38 3 61 2 0 31 2 8 53 0 86 7 8 l 数量31 2 33 2661 0 8616 7334 通过上述算法，得到的结果是需要原材料8 4 根，总的材料利用率为9 6 3 1 。 2 1 5 结论及其改进 由于邻域搜索算法本身存在的缺陷，其对大规模问题求解的速度非常慢，所 以该方法只对一维小规模排样问题比较有效。该问题求解一维小规模排样问题的 优点是不需要求解分割模式，而且不需要求解整数规划模型。但是，即便对于这 样的小规模问题，有时求解仍然存在某些困难，这时可以采用一些改进的邻域搜 索算法求解 3 9 】。对于大规模问题，可以考虑采用其他方法求解。 2 2 进化规划算法 简单的邻域搜索算法对于小规模一维排样问题有较好的效果，可是对于大规 模的问题依然难于解决，所以要探索新的求解方法。丽邻域搜索算法作为一种比 华中科技大学硕士学位论文 较“老”的算法，虽然在算法的思想上不如近年来提出的一些算法的思想新颖( 如： 与生物学理论相结合的遗传算法，与热学相结合的模拟退火算法等) ，但将这些算 法与邻域搜索算法配合起来一道来寻优，往往能有更好的寻优效果。本文基于这 种思想，将进化规划与邻域搜索算法相结合，解决大规模一维优化排样问题。 2 2 1 进化规划算法的基本结构 4 0 i 进化规划和遗传算法、进化策略同属进化算法，他们都是借鉴自然界生物优 胜劣汰、适者生存的机理发展而来的一类随机优化算法。但有所不同的是，遗传 算法需要对解空间进行编码，寻优在编码空间中进行，通过对编码的变异和交换 操作来产生子代。而进化规划无需对解空间编码，可直接在解空间中寻优，并且 不需重组，只通过变异算子产生子代。因此，进化规划对问题描述更简单。 进化规划的算法，可归纳为： ( i ) 确定问题的表达方式。 ( 2 ) 随机产生初始群体，并计算其适应度。 ( 3 ) 用下述操作产生新群体：突变：对旧个体添加随机量，产生新个体。 计算新个体适应度；选择：挑选优良个体组成新群体。 ( 4 ) 反复执行( 3 ) ，直至满足终止条件，选择其中的最佳个体作为进化规划 的最优解。 2 2 2 下料问题的进化规划算法 ( i ) 问题描述 在许多数字表示的优化问题中，进化规划用一实值向量作为可行解的一个个 体。一个向量包含目标向量，自适应参数。本文考虑的进化规划，个体只有一个 整数向量i ，就是所有需求零件的一个排列。 在邻域搜索算法中所用到的零件列表作为染色体：经过分割，染色体转变为 包含切割点的解；分割余料表示每根原线材的浪费。 ( 2 ) 变异 不同于数字优化的进化规划算法，这里染色体本身不能变化。例如，在染色 1 3 华中科技大学硕士学位论文 体中的5 不能变化为4 ，因为5 是用户需要排样零件的长度，所能变化的只能是 排列顺序。有很多方法可以用来变换顺序，这里仍采用邻域搜索算法中基于k 点 变换的简单变异算子。 在理论上，全局最优解可以从任何初始排列表个体中通过一系列2 一s w a p 变 换得到。但是，这是一个非常慢的过程，而且可能在一个很长的时间段内陷入局 部最优解。所以，通过多次交换增大搜索步长是有益的。首先以3 - - s w a p 作为基 本的交换算予，并且在每次变异中多次使用3 一s w a p 变换，这样就增加了搜索步 长。若最初排列表远离最优解，这样则可以加快趋于最优解。平衡的做法是在大 步长的搜索中多次应用3 一s w a p 变换于变异中，小步长搜索每次只用一次3 - - s w a p 变换。 ( 3 ) 适应度函数 根据染色体列表，可以计算出每个染色体所用的总原材料根数m ，以及每一 根原材料的浪费w i ( i = 1 , 2 ，m ) 。定义适应度函数如下： f v a l 。= 熹c 喜、， w2 而( 善、九 该适应度函数强调了每个染色体的最小浪费。 2 2 3 算法步骤 由以上分析，将下料问题的进化规划算法描述如下： s t e p l ：随机产生包含“个个体的初始群体。置进化代数为k = 1 ，每一个个体 为一整数向量x ，( i = 1 , 2 ，“) 。 s t e p 2 ：利用适应度函数计算群体中每个个体x ，( f = 1 , 2 ，“) 的适应度函数值。 s t e p 3 ：对每个父代x ，( f = 1 , 2 ，“) ，利用3 - - s w a p 交换变异产生单一后代x ：。 s t e p 4 ：计算每一后代x ：( f = 1 , 2 ，“) 的适应度函数值。 s t e p 5 ：将父代和子代的适应度函数值相比，选择适应度好的甜个体作为下一 代父代个体。 华中科技大学硕士学位论文 s t e p 6 ：如果停止准则满足，则停止；否则七= k 十1 ，转s t e p 3 。 流程图如图2 1 。 图2 1 进化规划算法流程图 华中科技大学硕士学位论文 2 2 4 算例 下面以某企业要求的一个实际数据为例，利用该算法进行了计算。原材料的 长度为7 0 0 0 ，需要的零件种类、长度和数量如表2 2 表2 2 一维排样数据二 类别 l234567 长度 1 1 2 61 1 6 21 3 8 21 5 0 41 8 2 42 3 9 42 3 9 9 数量1 1 01 01 01 262 02 0 类别 891 01 11 2 1 31 4 长度 2 6 6 42 6 6 92 7 5 04 9 95 0 46 1 4 6 1 9 数量 2 02 08 0 4 04 01 2 04 0 通过上述算法，得到的结果是需要原材料1 1 5 根，材料利用率为9 1 8 4 。 2 2 5 结论及其改进 通过对该算例进行实验，虽然在计算效率上有一定改进，但是材料利用率偏 低。所以，在应用进化规划的过程中，需要对变异算子及适应度函数做深入的研 究，这也是笔者需要进一步改进的地方。 2 3 蚂蚁算法 2 3 1 蚂蚁算法概述 蚁群算法是一种新型的模拟进化算法，该算法首先由意大利学者m d o r i g o 、 v m m a i e z z o 、a c o l o r i n i 等人于1 9 9 1 年首先提出的，称之为蚁群系统( a n t c o l o n y s y s t e m ) ，并用该算法求解t s p 问题、分配问题、j o b s h o p 调度问题，取得了较好 的效果。受其影响，蚁群系统模型引起了其他研究者的注意，d c o s t a 等人在此基 础上，提出了一种求解分配类型问题( a s s i g n m e n tt y p ep r o b l e m ) 的一般模型，并 用来研究图着色问题，这些研究成果都显示出了蚁群算法的优点。 蚁群算法模拟真实蚁群的协作过程，算法由许多蚂蚁共同完成。每只蚂蚁在 1 6 华中科技大学硕士学位论文 候选解的空间中独立搜索解，并在所搜索的解上留下一定的信息量。解的性能越 好，蚂蚁留在其上的信息量越大，信息量越大的解被选择的可能性越大。在算法 的最初阶段，所有解上的信息量是相同的。随着算法的推进较优解上的信息量增 加，算法渐渐收敛。 蚁群算法同其他模拟进化算法一样，通过候选解组成的群体在进化过程中来 寻求最优解。蚁群算法有如下优点：( 1 ) 较强的鲁棒性( 2 ) 分布式计算( 3 ) 易 与其他方法结合。众多的研究已经表明蚁群算法具有很强的发现求好解的能力。 2 3 2 蚂蚁算法原理i 圳 为了说明人工蚊群系统的原理，先从蚁群系统搜索食物的过程谈起，像蚂蚁、 蜜蜂等群居昆虫，虽然单个昆虫的行为极其简单，但由单个简单的个体组成的群 体却表现出极其复杂的行为。仿生学家经过大量细致观察研究发现，蚂蚁个体之 间是通过一种称之为外激素( p h e r o m o n e ) 的物质进行信息传递的。蚂蚁在运动过 程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在新的运动过程中能够 感知这种物质，并以此指导自己的运动方向。因此，由大量蚂蚁组成的蚁群的集 体行为表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择 该路径的概率越大，蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。 下面引用m d o f i g o 所举的例子说明蚁群系统的原理。如图2 2 所示，设a 是 巢穴，e 是食物源，h c 为一障碍物。由于障碍物的存在，蚂蚁只能经过h 或c 由a 到达e ，或由e 到达a ，各点之间的距离如图所示。设每个时间单位有3 0 只蚂蚁由a 到达b ，有3 0 只蚂蚁由e 到达d 点，蚂蚁过后留下的激素物质量为 1 。为方便，设该物质停留时间为1 个单位。在初始时刻，由于路径b h 、b c 、 d h 、d c 上均无信息存在，位于b 和d 点的蚂蚁可以随机选择路径。从统计的角 度看可以认为它们以相同的概率选择b h 、b c 、d h 、d c ，经过一个单位时间后， 在路径b c d 上的信息量是路径b h d 上信息量的两倍。t = 1 时刻，将有2 0 只蚂 蚁由b 和d 到达c ，有1 0 只蚂蚁由b 和d 到达h 。随着时间的推移，蚂蚁将会 以较大的概率选择路径b c d ，最终完全选择路径b c d ，从而找到由蚁巢到食物 华中科技大学硕士学位论文 源的最短路径。 h 图2 2蚁群系统示意图 2 3 3 基本蚁群系统模型1 4 2 忡l c 为描述方便，以求解n 个城市的t s p 问题为例，来说明蚁群算法的实现过程。 n 个城市的t s p1 9 题就是寻找通过埠个城市各一次且最后回到出发点的最短路 径。对于其他问题，可以对此模型稍作修改便可应用，虽然从形式上看略有不同， 但基本原理是相同的，都是通过模拟实际蚂蚁的行为达到优化目的。为模拟实际 蚂蚁的行为，首先引进如下记号：设埘是蚁群中蚂蚁的数量，d ( f ，2 1 , 2 ， ) 表 示城市f 和城市，之间的距离，7 f ( ，) 表示时刻 在连线扩上残留的信息量。初始时 刻，各条路径上的信息量相等，设7 u ( o ) 2c ( c 为常数) 。蚂蚁( t = 1 ，2 ，h ) 在 运动过程中，根据各条路径上的信息量决定转移方向，p ；表示在f 时刻蚂蚁k 由 位置f 转移到位置，的概率， 硝- j 警，一帆硝= 。删( 咖檬o ) 。”“ 1 0 o t h e r w i s e 其中，a l l o w e d 。( o ，l ，n 一1 ) 一t a b u 为蚂蚁t 下一步允许选择的城市。与实 际蚁群不同，人工蚁群系统具有记忆功能。t a b u ( 七= 1 ，2 ，m ) 用以记录蚂蚁i 以 前所走过的城市，集合随着进化过程作动态调整。随着时间的推移，以前留下的 信息量逐渐消逝。用参数1 一p 表示信息挥发程度，经过，z 个时刻，蚂蚁完成一次 华中科技大学硕士学位论文 循环，各路径上信息量要根据下式作调整 f 口0 + 行) = p + f 口o ) + a r ”p ( 0 , 1 ) 、 a r f = a r ； f ；表刁- - 、，口、。, 。，。z 。z 。l _ 爵息量，表示本次循环中路径 f 上的信息量的增量。 根据不同问题，a r ；有三种表示方式： 纠= 嚣撒黼种鳓 k ；q 吒 ( 若蚂蚁2 在本次循环中经过) ” 1 0( 其他) 叫= 侣嚣蚍在本次循环悭蝴 式中：q 为常数，丘为l j 第蚂蚁在本次循环中所走过的路径总长度。口，分 别为蚂蚁在运动过程中所积累的信息及启发式因子，它们在蚂蚁选择路径中起不 同作用。表示城市f 到城市，的期望程度，由启发式算法确定或直接取为1 d u 。 参数q ，c ，口，户一般由实验方法确定其最佳组合。三种表示方式中，第 一个利用整体信息，后两个利用局部信息。三种表示方式分别被称为a n t c y c l e s y s t e m ，a n t q u a n t i t ys y s t e m 及a n t - d e n s i t ys y s t e m 。停止条件可以用固定循环次数 或者当进化趋势不明显时便停止计算。 蚁群算法是一个递推过程，其实现过程的伪代码表示如下： b e g i n 初始化过程： n c y c l e = 0 ： b e s t c y c l e = 0 华中科技大学硕士学位论文 a r 口= 01 由某种启发式算法确定； t a b uk = o ： w h i l e ( n o tt e r m i n a t i o nc o n d i t i o n ) fn c y c l e = n c y c l e + l ； f o r ( i n d e x 2 o ；i n d e x 预定迭代次数； e n d 2 3 7 算法小结 蚂蚁算法就是通过蚂蚁在整个解空间中的不断移动来搜索最优解。对一维优 化排样，在每个变量上设置蚂蚁，然后蚂蚁通过状态转移，选择每种分割模式的 数量。最终在所有蚂蚁的搜索路径上寻找到最优解。在把原背包问题转化为o l 背包问题后，设置蚂蚁的数量减少，计算复杂度可能会减少。 华中科技大学硕士学位论文 3 二维矩形件排样问题的近似算法 对于矩形件排样问题，尽管现有的研究方法很多，但是仍难找到一种排样算 法，使其对于所有实际情况都有很好的效果。所以，一般是针对具体的问题而采 用某一方法，以下的讨论也是基于具体的问题类展开的。 3 1 矩形件排样问题的求余算法 3 1 1 算法描述 对于第一章描述的矩形件排样问题，下面分三类情况阐述求余算法： ( 1 ) 若存在某个q 或玩，使得w a ，= o 或w b ，= o ，则首先排放这一类零件。 w a 。= o ( 矿6 ，= 0 ) 表明板材的宽的方向上能纵( 横) 向排放下整数个这种类 型的零件。以下仅考虑w a ，= 0 的情况，当埠，o o e w a ，】= o 时，板材的宽的方向上 恰好能排放完整数排该种零件，而且在该种零件的纵向上没有空余部分。否则， 对于排放完整数排后剩下的零件，留到后面作填充用或者最后单独再排。 ( 2 ) 若存在边长成倍数关系的矩形件，则可以先考虑组合这些矩形件。以使 组合后通过以上方法求余数所得的余数比没有组合时更小或余数为0 ，这也就意 味着所浪费的面积可能更小。 对于这些边长成倍数关系的矩形件，可以假设一边相同。( 若有倍数关系，则 可以先将小的矩形件拼成大的矩形件) 。记矩形件的另一边长为五，z ：，z 。：则 我们要求m i n w a l z l + 口：z ：+ + 口。 ) 。事实上，这个问题可以转化为整数 线性规划问题，对此要求矿 口。而+ a 2 2 2 + + 口，z 。 最小，也就是要求 一c ( 1 2 1 + a 2 2 2 + + 8 。z 。) 最小。这就转化为求c ( a l z l + d 2 2 2 + + 日。z 。) 最 大。令阳= d i ；则有如下整数规划问题： 华中科技大学硕士学位论文 m a x ( d l z l + d 2 2 2 + - - + d 。z ) 占f 盔z l + d 2 2 2 + + d 。z 。w 其中谚w z ，；4 为整数 对这个整数规划的求解，可以应用分枝定界法或者割平面法 4 5 3 。 通过组合，对组合后的矩形件进行排样，这样可以达到节省更多材料的目的。 图3 1 可以说明这一点。图3 1 中假设板材w = 2 5 5 0 ，a 中的零件长为5 0 0 ，宽 为4 5 0 ，则在宽的方向上排满5 个后有空余部分，b 中的零件长为5 0 0 ，宽为4 0 0 ， 在宽的方向上排满6 个后有空余部分，但若组合这两种零件，在宽的方向上每种 零件各排3 个，则通过以上排究一排后便没有空余的部分( 如图3 1c 所示) ，这 样便没有材料浪费。若组合后的矩形件满足( 1 ) 中的条件，则按( 1 ) 中的方法 进行，否则按照( 3 ) 中的方法进行。 口 a b c 图3 1 矩形件排样组合图 ( 3 ) 若不存在以上的两种情况，记c = m i n b 。) ( i 未排的矩形件种类) ，若 w a ，及w b ，均小于c ，按求余较小的结果所确定的方向排样。这类零件不论按 纵向还是横向排放完一排后，均没有零件能够填充：若w a ，及w b ，均大于c ， 则我们按求余较大的结果所确定的方向排样，这样排放完一种零件剩下的空余部 分可以用小的矩形件按初始排样的方法进行填充。若有w a 。及w b 。不同时大干 或小于c 的情况( 不妨设w a 。大于c ) ，则先看是否存在口，( j 未排的矩形件种 类) 满足( 矿一r a ，) 日， c ) 则按求余较大的结果所确定的方向 排放这些零件，排放整数列。 3 3 i f ( 口。 c 矿髓 c ) 若有q 满足( 一阳) d 矿6 ， b j 满y ：( w 一阳，) 6 j 矽岛( 其中r = w a 。】) 则纵向排放该种零件，否则横 向排放。 3 4 z f ( w a ， c ) 若有口，满足( 矿一r 岛) 口j 矽4 ， 或乃满足( 矿一r b ，) 0 矽口i ( 其中，= 吵阮】) 则横向排放该种零件，否则纵 向排放。 s t e p 4 对于以上步骤中排放零件所余下的空余部分，则更新形，再按j 垆l 华中科技大学硕士学位论文 至：l j s t e p 3 的步骤依次对余下的零件进行排样。 3 1 3 实验结果与结论 在本节提出的排样方案中，能满足“一刀切”的下料工艺要求。而且，在文 中只讨论了板材的宽矿对待排矩形件长或宽求余的结果，对于排放矩形件后剩下 的板材余料的长，也可以考虑其对矩形件长或宽的求余结果。事实上，板材长宽 对待排矩形长宽的求余可以同时进行，再根据这些结果排样。根本的目的是使不 能填充的部分的面积达到最小，以此来提高材料的利用率。 下面利用本算法对一个实例进行验证。给定板材的长宽分别为l = 1 2 0 3 0m i l l ， w = 2 5 5 0m m ，需要排样零件的类别、个数、长、宽( m m ) 如表3 1 所示。在这个 实例中，开始可以组合矩形件类1 和2 ；然后组合类1 和6 ；还可以组合类1 ，6 和7 。其他的组合和后继排样由该算法可以相继进行。 表3 1矩形件排样数据一 z12345678 咒 9 64 81 6884 03 23 2 口 4 5 04 0 01 1 4 02 5 0 02 5 0 03 0 01 5 0 02 7 0 b2 7 02 7 01 7 03 0 01 3 92 7 02 7 01 l o z91 01 11 21 31 41 5 玎 81 61 63 23 088 d 1 9 9 37 1 05 0 08 0 03 0 01 3 6 01 7 6 0 b1 6 56 7 55 0 05 0 07 41 6 97 8 5 经过编程验算，得出的排样图如图3 2 ，可以看出这种算法得出的材料利用 率是可以接受的。 华中科技大学硕士学位论文 图3 2 矩形件排样图一 通过其他的实验表明，这种方法对种类少但数量较多的矩形件有比较好的效 果。对于含有较多成倍数关系边的矩形件，利用整数规划求解进行组合后排样效 果更好。 3 2 矩形件排样问题的丁字尺法 3 2 1 问题背景 一般设计的某种排样算法在单纯考虑材料利用率的同时，可能因为提高了材 料利用率而增加了零件排样的复杂度( 如排放的种类较多) ，这样就影响了生产 过程中分割排样的效率，延长了生产加工时间，从而也影响了生产成本。大型企 业的生产加工中，在要求材料利用率的同时，同时也要求保证较高的生产效率。 所以，一个好的排样算法，应该考虑到材料利用率和分割效率两个优化指标的综 合，这是一个多目标规划问题。本节综合考虑到材料利用率、生产效率和“一刀 切”的工艺约束，采用下面的