（计算机软件与理论专业论文）并行遗传算法在装箱问题中的应用研究.pdf

山东大学硕士学位论文 摘要 装箱问题是最经典的组合优化问题之一，同时也是算法分析理论中研究的 重点。装箱问题源于现实生活，有着极为广泛和深厚的应用背景。例如装箱问 题在多处理器调度、资源分配和日常生活中的计划、包装、调度等各领域有着 广泛的应用。而且装箱问题理论的形成也有着深刻的意义，作为一种最早研究 的n p 难解问题，为其它n p 难解问题的研究提供了理论性研究平台和诸多借鉴的 典范。该问题已经有四十多年的研究历史，在此期间，许多著名的组合优化方 面的学者为装箱问题创建了比较完善的理论和丰富的算法，但是关于装箱问题 及其算法的研究仍远未结束。 本文利用并行遗传算法来求解一维装箱问题，针对一维装箱问题，围绕如 何提高并行算法的效率以及求解的精度提出了一些关键性的技术。主要内容如 下： 1 、本文比较了解决一维装箱问题较好的组遗传算法，针对组遗传算法交叉 算子的不足，在叉的过程中增加了一种“替换”机制，从而提出了一种改进的 交叉算子。此交叉算子能够保证染色体在交叉的过程中尽量的减少箱子的个 数，同时尽可能使能箱子装满物品。 2 、为了提高种群的多样性，在进化的过程中跳出局部最优解，本文设计了 新的变异算子，在变异的过程中主要采取增加一个箱子，减少一个箱子，箱子 数不变但箱子所装物品进行恰当重组的操作。 3 、从“多群体粗粒度 并性遗传算法模型入手，受“金字塔 模型的启 发，本文提出了一种并行遗传算法的“金字塔层次模型，根据种群的平均适 应度将各个种群分成不同的层次，每一层具有不同交叉和变异概率。层次较高 的种群具有较低的交叉和变异概率，迁移时只是从低层次向高层次迁移。 4 、在迁移策略上，为了尽可能降低通信费用，本文提出了“双阈值”的迁 移策略，根据相邻两层之间种群的适应度方差设置双阈值，将迁移分为三种情 况：小于最小闽值时不迁移；介于两个阂值之间用下层的优秀个体去替换上层 的较差个体；大于最大的阈值，进行层次调整。 5 、在迁移周期上，本文采用的不固定间隔的迁移周期，当进化缓慢时才进 行迁移的申请。 山东大学硕士学位论文 基于上述的研究，最后本文给出了实现并行遗传算法求解装箱问题的伪代 码，并在实践中利用伪并行遗传算法来模拟并行遗传算法求解一维装箱问题， 通过实际数据的运算精度和效率说明了这种算法的优越性。 关键词装箱问题；并行遗传算法；金字塔层次模型；双阈值迁移； i i 山东大学硕十学位论文 a b s t r a c t b i np a c k i n gp r o b l e m ( b p p ) i so n eo ft h em o s tf a m o u sc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m a n di ti st h ee m p h a s i so ft h ea n a l y s i so fa p p r o x i m a t i o na l g o r i t h m s a so n e o fm ee a r l i e s ts t u d i e dn p h a r dp r o b l e m , i tw o r k s 髂ar e s e a r c hp l a t f o r m f o rt h e c o m p l e x i t yt h e o r ya n dg i v e sd i r e c t o r st oo t h e rn p h a r dp r o b l e m s b i np a c k i n gc o m e s f r o mo u rl i v e sa n dh a sm a n yi m p o r t a n t a p p l i c a t i o n ss u c h 罄m u l t i p r o c e s s o rs c h e d u l i n g ， r e s o l r c ea l l o c a t i o n ，a n dr e a l 。w o r l dp l a n n i n g ，p a c k i n ga n ds c h e d u l i n g o p t i m i z a t i o n p r o b l e m s t h ep r o b l e m sh a sb e e ns t u d i e dm o r et h a nf o r t yy e a r s ，m a n yf a m o u s c o m b i n a t o r i a lo p t i m i z a t i o nr e s e a r c h e r sh a v eb u i l tu pi n t e g r a t et h e o r i e sa n de x p l o r e d m a n ya l g o r i t h m sf o r t h ep r o b l e m , b u t 廿1 et o p i c sa r ef a rf r o me n d i n g b yu s i n gt h ep a r a l l e lg e n e t i ca l g o r i t h mt os o l v et h eo n e d i m e n s i o n a lb i np a c k i n g p r o b l e m , f o rt h eo n e d i m e n s i o n a lp a c k i n gp r o b l e m ，c e n t e r i n go nh o wt oi m p r o v et h e e f f i c i e n c yo ft h ep a r a l l e la l g o r i t h m sa n dt h ed a t ac o m p u t i n gp r e c i s i o n ，t h ep a p e rp u t s f o r w o r dan u m b e ro fk e y t e c h n o l o g i e s t h ef o l l o w i n gk e ye l e m e n t s ： 1 b yc o m p a r i n gw i t ht h eg r o u p i n gg e n e t i ca l g o r i t h ma c h i e v i n gb e t t e rr e s u l ti nt h e o n e - d i m e n s i o n a lb i np a c k i n gp r o b l e m ，f o rt h el a c ko fc r o s s o v e ro p e r a t o ro ft h e g r o u p i n gg e n e t i ca l g o r i t h m , t h ep a p e rp u tf o r w a r da l l i m p r o v e dc r o s s o v e r o p e r a t o r ，a d d i n ga “r e p l a c e m e n t ”m e c h a n i s mi nt h ec r o s s o v e rp r o c e s s t h ec r o s s o v e r o p e r a t o re n s u r er e d u c e i n gt h en u m b e ro fb i n st ot h ee x t e n tp o s s i b l ea n dm a k i n g e v e r y b i nf i l l e dw i t hi t e m sa sm u c ha sp o s s i b l ei nt h ec r o s s o v e r p r o c e s s 2 i no r d e rt oi n c r e a s et h ed i v e r s i t yo fs p e c i e si nt h e e v o l u t i o n a r yp r o c e s s ， j u m p i n go u to ft h el o c a lo p t i m a ls o l u t i o n ，w ed e s i g nan e wm u t a t i o no p e r a t o r t h e m a i no p e r a t o r si sa d d i n ga b i n ，d e l e t i n gab i n ，o rt h es a m en u m b e ro fb i n sb u t t h ei t e n 坞 i nb i n si sc o m b i n e da p p r o p r i a t e l y 3 s t a r t i n gw i t ht h e “c o a r s e - g r a i n e da n dm o r eg r o u p s ”g e n e t i ca l g o r i t h mm o d e l ， e n l i g h t e n e db yt h e “p y r a m i d ，m o d e l ，t h ep a p e rp r o p o s e da p y r a m i dh i e r a r c h i c a l m o d e l ”o fp a r a l l e lg e n e t i ca l g o r i t h m a c c o r d i n gt ot h ea v e r a g e f i t n e s s ，t h ep o p u l a t i o n w i l lb ed i v i d e di n t od i f f e r e n tl e v e l s ，t h ed i f f e r e n tl e v e l sp o p u l a t i o n sh a v e d i f f e r e n t p r o b a b i l i t yo fc r o s s o v e ra n dm u t a t i o n t h eh i g h e rl e v e lp o p u l a t i o n sh a v et h el o w p r o b a b i l i t yo fc r o s s o v e ra n dm u t a t i o n ，t h em i g r a t i o no n l yh a p p e nf r o mt h el o w e rl e v e l p o p u l a t i o nt ot h eh i g h e rl e v e lp o p u l a t i o n i i i 山东大学硕士学位论文 4 f o rt h em i g r a t i o ns t r a t e g y ，i no r d e rt om i n i m i z ec o m m u n i c a t i o nc o s t s ，t h e p a p e rp r o p o s e da “d u a l t h r e s h o l dm i g r a t i o ns t r a t e g y ”s e t i n g 叩t h ed u a l t h r e s h o l d a c c o r d i n gt ot h ep o p u l a t i o nf i t n e s sv a r i a n c e ，t h em i g r a t i o nw i l lb er e l o c a t e d i n t ot h r e e s i t u a t i o n s ：l e s st h a nt h em i n i m u mt h r e s h o l d , m i g r a t i o nd o e s n th a p p e n ；b e t w e e nt h e d u a l - t h r e s h o l d , r e p l a c i n gt h ep o o ri n d i v i d u a lo ft h eh i g h e rl e v e lp o p u l a t i o nw i t ht h e o u t s t a n d i n gi n d i v i d u a l so f t h el o w e rl e v e lp o p u l a t i o n ；l a r g e rt h a nt h el a r g e s tt h r e s h o l d , a d ju s t i n gt h el e v e l st h ep o p u l a t i o n s 5 i nt h em i g r a t i o nc y c l e ，t h ep a p e ru s et h en o tf i x e di n t e r v a lm i g r a t i o nc y c l e ，a m i g r a t i o na p p l i c a t i o n sh a p p e n so n l yw h e nt h ee v o l u t i o ni sv e r ys l o w b a s e do nt h ea b o v es t u d y ，t h i sp a p e rg i v e st h ep s e u d o - c o d er e a l i z a t i o no ft h e p a r a l l e lg e n e t i ca l g o r i t h mf o ro n e d i m e n s i o n a lb i np a c k i n gp r o b l e m a n di np r a c t i c e u s i n gp s e u d o - p a r a l l e lg e n e t i ca l g o r i t h mt os i m u l a t ep a r a l l e lg e n e t i ca l g o r i t h mt os o l v e t h eo n e - d i m e n s i o n a lb i np a c k i n gp r o b l e m ，t h r o u g ha c t u a ld a t ac o m p u t i n gp r e c i s i o n a n de f f i c i e n c y ，t h i sa l g o r i t h ms h o w si t sa d v a n t a g e s k o y v c o r d s ：b i np a c k i n go r o b l 0 1 1 1 ：p a r a i i e ig e n o t i ca i g o ti t h m ：p y r a m i d h i e r s r c h i c a lm o d e i ：d u a i t h r e s h o i dm i g r a t i 0 1 3 ： i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均已在文中以明确方式标 明。本声明的法律责任由本人承担。 论文作者签名：之鲡日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留 或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：乏移矿师 山东大学硕士学位论文 量曼曼皇皇曼曼! 曼量曼量曼曼量曼曼量皇曼曼曼璺曼曼曼! 曼! 皇皇- ii i_ 曼皇! 皇曼曼曼皇曼皇曼皇曼曼! 曼曼皇曼曼皇曼曼曼曼曼曼曼皇曼量皇 第1 章绪论 装箱问题是研究最早、应用最广泛的n p 难解问题之一。装箱问题是许多具 有重要意义的实际优化问题的基础，在建筑中经常需要从长度一定的棍子上切 割不同长度的棒和管；电气布线中电线来自长度一定的线卷；贴墙纸需要从改 订长度的纸卷中得到；具有相同宽度，不同长度的材料需要用平板架运送到建 筑工地；在金属制造工业中，钢片需要从大块刚片中切除。当然物品的尺寸不 一定是几何尺寸，比如，电子工业中不同长度，一字节的微代码程序需要存储 至具有固定尺寸的存储器中：在娱乐工业中，歌曲集被发布在给定容量的媒质 ( 光盘，磁带) 中；在作业管理中，不同执行时间的任务需要在满足所有任务时 间限制的前提之下被分配到不同的工人；在运输工业中，要把不同重量的货物 装入一定载重量的卡车中。所有这一切都可以归结为装箱问题。考虑这些装箱 问题的共同特性，可以看作是把一些具有不同大小的物品放入到固定容量的箱 子中，并最小化使用的箱子的总容量。因此，找到一个高效的装箱问题的解法 具有较现实的意义。 1 1 研究背景 早在7 0 年代初就有学者开始研究装箱问题。负载受限的卡车装运到商业电 视中电视间歇的安排【1 5 】，以及著名的s t o c k - c u t t i n g f 司题( 把固定长度的原料按 要求切割成所需大小的器件) 、剪裁问题( s t o c k c u t t i n g 问题的二维推广) 等 等，这类问题广泛存在于日常生活中： 1 在计算机科学中的存储分配、共享资源调度、文件存储等宏观、微观操作 中大量存在着这类问题： 2 在服装公司，通过合理的剪裁，使每一件衣服节约1 平方英寸皮革，可以 节省大量的制造成本： 3 现实生活中的包装问题更是广泛存在，合理的包装方式可以节省大量的运 输耗费，减少原材料消耗。在这四十多年来，人们建立了装箱问题较为完善的 理论，同时开发了大量的算法。尽管多年来许多学者的努力极大地推进了装箱 问题的研究进展，但关于装箱问题的研究还远没有结束。因为实际应用千变万 化，如何有效的将经典装箱问题的研究成果应用于这些实际问题中也是一类急 待解决的问题。 【l j 东大学硕士学位论文 1 2 装箱问题的分类及衍生问题 正如前面所提到的广义的装箱问题指的是一个大的范围。到目前为止，就 所涉及到的维数方面而言，可以把装箱问题分为三类：一维装箱问( o n e d i m e n s i o n a lb i np a c k i n gp r o b l e m ) ，二维装箱问题( t w o - d i m e n s i o n a lb i np a c k i n g p r o b l e m ) 三维装箱问题( t h r e e d i m e n s i o n a lb i np a c k i n gp r o b l e m ) 。显而易见，随着 维数的增加，装箱问题的难度和算法的复杂性都大大提高了，这给我们的研究 工作带来了较多的困难和阻碍，但这些问题都有着极为广泛的应用价值。下面 分别给出二维和三维装箱问题的数学描述。 在二维装箱问题中：给定一个由n 个矩形物件组成的物件集合j = 1 ， 2 ，n ) ，每个物件的宽为w i ，高为h i ，此处有一些宽为w ，高为h 的完全相 同的矩形箱子，要求给出一种装箱方案，在物件没有重叠的情况下，把所有物 件装入箱子中，并且物件边与箱子边平行，使得所需的箱子数目尽可能少。这 里假设物件的方向已固定，该问题记为“2 b p 。二维装箱问题在工业领域有许 多的应用，尤其是在木材、玻璃的切割工业、装载运输和仓储业中。这里就不 一一叙述了，作为二维装箱问题的一个特例，当每个物件的宽 w j = w ，j = l ，2 ，3 - - n 时，就是经典的一维装箱问题了由于一维装箱问题为大家所 知是n p 完全问题，自然二维装箱问题也是n p 完全问题。目前，对于二维装箱 问题的一些较好的结果有：2 0 0 4 年，由c o r r e a 和k e n y o n 提出了一个近似值为 2 + e 的p t a s 算法【1 2 1 。该算法是把正方形物件放入正方形的箱子中。 三维装箱问题的数学描述： 在三维装箱问题中，给定一个由n 个长方体的盒子组成的集合j = ( 1 ，2 ，n ) 每个盒子的宽为w ，高为h i ，深为d j ( 均为整数) ，此处有一些宽为w ，高为h ， 深为d 的完全相同的三维的箱子，要求给出一种装箱方案，把所有盒子装入上 述箱子中，使得所需的箱子数目尽可能少，这里假设盒子的方向已固定。该问 题记为“3 b p 。三维装箱问题在切割和装载运输中也有着极为广泛的应用价 值。由于盒子的方向固定，即不允许旋转，因此，该模型也可以用来解决许多 排序问题。本文将重点讨论一维装箱问题，对于二维和三维装箱问题的一些具 体算法不再详细介绍。下面将进一步介绍一维装箱问题的衍生问题。在2 0 世纪 8 0 代以前，对装箱问题的研究主要集中在一些所谓经典的模型上，即上文所提 到的一维经典装箱问题，二维装箱问题和三维装箱问题。近十多年来则出现了 许多新的模型，一方面是由于装箱问题极为广泛和重要的应用价值，另一方 面，随着信息技术的发展，一些经典模型已经不能满足生产、生活领域的需要 2 山东大学硕士学位论文 而迫切需要够建新的模型。这些模型问题主要是由一维装箱问题所衍生而来 的，我们把它们称为装箱问题的衍生问题，装箱问题的衍生问题主要有三个：第 一个是箱子覆盖问题( b i nc o v e r i n gp r o b l e m ) ，它也称为装箱问题的对偶；第 二个是最大基数装箱问题( m a x i m u mc a r d i n a l i t yb i np a c k i n gp r o b l e m ) ：第三 个是最小基数箱子覆盖问题( m i n i m u mc a r d i n a l i t yb i nc o v e r i n gp r o b l e m ) ， 也称作最大基数装箱问题的对偶【l4 1 。此外，关于装箱问题的衍生问题还有一 类，即染色的装箱问题，这是目前所提出的一类新问题，还处于探讨和研究阶 段，它包括几个不同的模型。 本文的重点是来解决一维装箱问题，对于一维装箱问题的详细情况将在后 面的章节介绍。对于以后所提到的装箱问题主要是指一维装箱问题。 3 山东大学硕士学位论文 第2 章遗传算法概述 2 1 自然进化与遗传算法 自从达尔文的进化论得到人们的接受之后，生物学家们就对进化机制产生 了极大的兴趣。化石记录表明我们所观察到的复杂结构的生命是在相对短的时 间进化而来的，对这一点包括生物学家在内的许多人都感到惊奇。虽然目前关 于推动这个进化的机制还没有完全弄清楚，但它们的某些特征己为人所知。进 化是发生在作为生物体结构编码的染色体上，通过对染色体的译码部分地生成 生物体，但下面几个关于进化理论的一般特性已广为人们所接受： ( 1 ) 进化过程发生在染色体上，而不是发生在它们所编码的生物个体上。 ( 2 ) 自然选择把染色体以及由它们所译成的结构的表现联系在一起，那些适应 性好的个体的染色体经常比差的个体的染色体有更多的繁殖机会。 ( 3 ) 繁殖过程是进化发生的那一刻，变异可以使生物体子代的染色体不同于它们 父代的染色体，通过结合两个父代染色体中的物质，重组过程可以在子代中产 生有很大差异的染色体。 ( 4 ) 生物进化没有记忆。有关产生个体的信息包含在个体所携带的染色体的集 合以及染色体编码的结构之中，这些个体会很好的适应它们的环境。 大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自 然选择的原则是适应者生存，不适应者淘汰。自然选择决定了群体中哪些个个 体能够存活并繁殖；有性生殖保证了后代基因中的混合与重组。比起那些仅包 含单个亲本的基因拷贝和依靠偶然变异来改进的后代，这种由基因重组产生的 后代进化要快得多。6 0 年代美 m i c h i g a n 大学的j o h nh o l l a n d 2 】在从事如何能 建立能学习的机器的研究中注意到学习不仅可以通过单个生物体的适应而且通 过一个群体的许多代的进化也能发生。受达尔文进化论的启发，他逐渐认识 到，在机器学习的研究中，为了获得一个好的学习算法，仅靠单个策略的建立 是不够的，还要依赖于一个包含许多候选策略的群体的繁殖。它们的思想起源 于遗传进化，h o l l a n d 2 1 就将这个研究领域命名为遗传算法( g e n e t i c a l g o r i t h m ) 。 h o l l a n d 创建的遗传算法是一种概率搜索算法，它是利用某种编码技术作 用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的群体的进化 过程。遗传算法通过有组织的而不是随机的信息交换来重新组合那些适应性好 的串，在每一代中，利用上一代串结构中适应性好的位和段来生成一个新的串 4 山东大学硕士学位论文 的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来代替原来的 部分。遗传算法是一类随机算法，但它不是简单的随机走动，它可以有效地利 用已有的信息来搜寻那些有希望改替解的质量的串。类似于自然进化，遗传算 法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似， 遗传算法对求解问题的本身一无所知，并基于适应值来选择染色体，使适应性 好的染色体比适应值差的染色体有更多的繁殖机会。 2 2 遗传算法基本流程 遗传算法( g a ) 是一类随机优化算法，但不是简单的随机比较而是通过对染 色体或个体或串的评价和对染色体及其基因的作用有效地利用已有的信息来指 导搜索，有希望改善优化质量的状态。 【标准遗传算法的步骤】 s e t p l 令k = o ，随机产生n 个初始个体构成初始种群p ( 0 ) ； s e t p 2 评价p ( k ) 中各个体的适应值； s e t p 3 判断算法收敛准则是否满足，若满足则输出搜索结果否则执行下一步 骤： s e t p 4 令r e = o ： s e t p 5 根据适应值大小以一定方式执行复制操作从p ( k ) 中选出两个个体作为父 代： s e t p 6 若交叉概率p 。 $ o ，1 则对选中个体执行交叉操作生成两个临时子 代，否则将选中的父代个体直接作为临时子代； s e t p 7 按变异概率踟对临时个体执行变异操作产生两个新个体放入p ( k + 1 ) 同 时令m - - - m + 2 ： s e t p 8 若m 2 = 46 27 35 891 。 3 变异操作 当交叉操作产生的后代适应度值不再进化且没有达到最优时就意味着算法 的早熟收敛。遗传算法的变异操作，是指将个体染色体的某些基因位的值用其 他基因位的值来代替，从而形成一个新的个体。变异操作一定程度上克服了这 种早熟收敛的情况有利于增加种群的多样性。目前常用的变异算子有：基本变 异操作、互换操作、插入操作、逆序操作等。 1 基本变异操作即对于基本遗传算法中用二进制符号串表示的个体，若需要变 异操作的基因值为0 ，则变为1 ；反之，若原有的基因值为l ，则变异操作，将其 变为o 【2 l j 。 2 互换操作即随机交换染色体中两不同基因的位置。 3 逆序操作即将染色体中两不同随机位置间的基因串逆序。 4 插入操作即随机选择某个点插入到串中的不同随机位置。 2 3 5 算法终止条件 遗传算法是一个反复迭代的过程，每次迭代期间，要执行适应度计算，选 择、交叉、变异等操作，直至满足终止条件。遗传算法的收敛理论说明了遗传 算法具有概率i 收敛的极限性质，然而实际算法通常难以实现理论上的收敛条 件。因此追寻的目标应该是具有一定优化质量的快速搜索，这显然与算法操作 设计和参数选取有关。由于实际应用遗传算法时不允许让其无停止地进行搜 索，同时问题的最优解也通常未知，因此必须设计一些近似收敛准则来终止算 法进程。常用方法包括给定一个最大进化步数、给定个体评价总数、给定最佳 搜索解的最大滞留步数等。应该认识到遗传算法不是一个简单的系统，而是一 种复杂的非线性随机智能优化计算模型。纯粹用数学方法来预测其运算结果很 难目前为兼顾优化质量和效率。所采取的设计方法大多是经验法或试探法，该 方面理论还有待更深入地研究与完善。 2 4 遗传算法的改进 尽管遗传算法在理论上具有概率1 的收敛特性，但实际应用时往往出现早熟 收敛或收敛缓慢等缺点。因此，设计遗传算法的框架、操作和参数，主要应针 对如何设法高效产生或有助于产生优良的个体成员，而这些成员应能够充分表 1 2 山东大学硕士学位论文 征整个解空间的特性，从而提高算法的搜索效率，避免早熟收敛现象。自从 1 9 7 5 年h o l l a n d 系统地提出遗传算法完整结构和理论以来，众多学者一直致力于 推动遗传算法的发展，对编码方式、控制参数的确定和交叉机理等进行了深入 的研究，提出了各种改进的遗传算法现今的改进方法除了采用自适应算法参数 外，大都是针对基因操作、种群的宏观操作、基于知识的操作、和并行化g a 进 行的。以下对此作简单综述： 1 交叉操作 在交叉操作方面主要有如下改进算子 g o l d b e r g ( 1 9 8 9 ) 提出了部分映射交叉( p m x ) ；s t a r k w e a t h e r 等( 1 9 9 1 ) 提出了增 强边缘重组算子( e n h a n c e de d g er e c 伽b i n a t i o n ) ：d a v i s ( 1 9 9 1 ) 提出了序号交 叉算子( o r d e rc r o s s o v e r ) 和均匀排序交叉算子( u n i f o r mo r d e r - b a s e d c r o s s o v e r ) ；s m i t h ( 1 9 8 5 ) 提出了循环交叉算子( c y c l ec r o s s o v e r ) ，d e j o n g ( 1 9 7 5 ) 提出了单点交叉算子( o n e - p o i n tc r o s s o v e r ) 和多点交叉算子： s y s w e r d a ( 1 9 8 9 ) 提出了双点交叉算子( t w o - p o i n tc r o s s o v e r ) 另外还有置换交 叉、算术交叉、启发式交叉等 2 变异操作 对于变异操作，除前面介绍的常用变异算子外，变异操作主要发展了自适 应变异，多级变异等操作。 3 其他一些高级基因操作 除上述常用遗传操作外还有如下高级基因操作 双倍体和显性遗传( d i p l o i da n dd o m i n a n c e ) 用以延长曾经适配值高而目前较差 的基因块的寿命并且在变异概率低的情况下也能保持一定的多样性。 倒位操作( i n v e r s i o n ) 用以助长有用基因块的紧密形式，加强了算法的效率。 优先策略( e l i t i s m ) 用以把目前解群中最好的解直接放入下一代种群中，如此保 证各代种群中总会有目前为止最好的解。 静态繁殖( s t e a d y s t a t er e p r o d u c t i o n ) 用在迭代过程中用部分优质子串来更新 部分父串作为下一代种群以使优质的父串在下一代中得以保留。 多倍体结构( m u l t i p l ec h r o m o s o m es t r u c t u r e ) 分离( s e g r e g a t i o n ) 异位 ( t r a n s l o c a ti o n ) 等操作。 在种群宏观操作方面主要是引入小生存环境和物种形成( n i c h ea n d s p e c t i a t i o n ) 的思想形成了多种群的遗传算法【3 6 l 。 山东大学硕+ 学位论文 在基于知识的操作方面主要是将问题的特殊信息与g a 相结合包括混合算法的构 造以及在遗传算子中增加知识的操作，衍生出共生遗传算法、基于决策树的遗 传算法等。 4 算法结构方面的改进 在算法结构方面已开展了如下研究工作 k r i s h n a k u m a r ( 1 9 8 9 ) 为克服群体数目大造成计算时间长的缺点提出了所谓脚 g a 的小群体方法其仿真结果显示了较高的计算效率和适于动态系统优化的潜 力，但尚无严格的理论分析。 s c h r a u d o l p h 等( 1 9 9 7 ) 针对二进制编码优化精度差的缺点提出了一种类似于 对解空间进行尺度变换的参数动态编码策略，较好地提高了g a 的精度但不适于 非线性较强的多模型优化问题。 a n d r o u l a k i s 等( 1 9 9 1 ) 采用实数编码提出了一种扩展遗传搜索算法，把搜索 方向作为独立的变量来处理以解决有约束的优化问题。 p o t h s 等( 1 9 9 4 ) 为克服算法早熟收敛的缺点提出了类似于并行实现思想的基 于变迁和人工选择的遗传算法。 g r e f e n s t e t t e ( 1 9 8 1 ) 全面研究了g a 并行化实现的结构问题并给出了多种结 构形式主要有同步主一仆方法( s y n c h r o n o u sm a s t e r - s l a v e ) 、亚同步主一仆方法 ( s e m i s y n c h r o n o u sm a s t e r - s l a v e ) 、分布式异步并发方法( d i s t r i b u t e d a s y n c h r o n o u sc o n c u r r e n t ) 、 网络方法( n e t w o r k ) 。g o l d b e r g ( 1 9 8 9 ) 提出了基 于对象设计g a 并行结构的思想。m u h l e n b e i n 等( 1 9 9 1 ) 用并行遗传算法求解高 维多模型函数的全局最小解，从而提供t g a 求解高度复杂优化问题的有力实 例。 2 5 并行遗传算法 由于本文主要采用的是并行的思想来实现装箱问题的，所以我们来介绍一 下并行遗传算法。 由于遗传算法固有的内在并行机制，因此并行处理很自然成为提高遗传算 法运行速度的途径之一。目前的并行处理方案主要分以下三类： 1 全局型主从式模型( m a s t e rs l a v em o d e l ) 并行系统分为一个主处理器和若干个从处理器，主处理器监控整个染色体 种群并基于全局统计执行选择操作，各个从处理器接受来自主处理器的个体进 1 4 山东大学硕十学位论文 行重组交叉和变异产生新代个体，并计算适应度再把计算结果传给主处理 器。模式如下： 图2 - 2 全局性主从模式 这种方式的缺点是：通信时间超过计算时间反而会降低速度，而且这种方法 要求有同步机制，这就会导致主进程忙而子进程闲或反之引起负载不平衡效率 不高【6 1 。 2 独立型粗粒度模型( c o a r s eg r a i n e dm o d e l ) 也称为分布式遗传算法( d i s t r i b u t e dg e n e t i ca l g o r i t h m ，d g a ) ，将种群分成 若干个子群，并分配给各自对应的处理器，每个处理器不仅独立计算适应度而 且独立的进行选择、重组、交叉和变异操作。还要定期地相互传送适应度最好 的个体从而加快满足终止条件的要求。粗粒度模型是目前应用最广泛的一种并 行算法。可以描述如下： b e g i n ( 1 ) 产生一个初始群体并将它划分为p 个子群 ( 2 ) f o ri = lt opp a r a l l e ld o 初始化 评估第一代子群的适应度 w h il er u n n i n gd o f o rj = lt og ( g e n e r a t i o n ) d o s el e c t ， c r o s s o v e r ， m u t a ti o na n de v a l u a t e t of r o m p o p u l a ti o n e n df o r s e l e c te m i g r a n t s * 选择要迁移出的个体，i ： d ot h ef o l l o w i n gi np a r a l l e l s e n de m i g r a n t s * 发送迁出的个体水 山东大学硕士学位论文 r e c e i v ei m m i g r a n t s 术接受迁入的个体木 e n dd o e n dw h i l e e n df o r e n d 其中p 是处理器的个数也就是子群的个数，另外，发送要迁出的个体和接受要迁 出的个体是并行执行的，为了避免通信中的死锁 1 9 。 3 分散型细粒度模型( f i n eg r a i n e dm o d e l ) 为种群中的每一个个体分配一个处处理理器，每个处理器进行适应度的计 算，而选择、重组、交叉和变异的操作仅在与相邻的一个处理器之间互相传递 个体进行。细粒度模型也称邻域模型( n e i g h b o r h o o dm o d e l ) 适合于连接机阵列 机和s i m d 系统目前这方面的研究有m a n d e r i c k 和s p i e s s e n s 基于二维网络拓朴 结构开发了一种大规模并行遗传算法，用于研究同类群大小及染体长度对于算 法性能的影响。m u h l e n b e i n 提出了一种异步通信模式并将它应用到复杂组合问 题上。k o s a k 6 1 将群体中个体映射到一个连接机的处理单元并指出这种方法对 网络设计的有效性。 迁移是并行遗传算法引入的一个新的算子，它是指在进化过程中子群间交 换个体的过程。一般的迁移方法是将子群体中最好的个体发给其它的子群体， 通过迁移可以加快较好个体在群体中的传播提高收敛速度和解的精度。与单种 群相比只需要较少的个体评价计算工作量。因此即使是采用单一处理器的计算 机上以串行方式( 伪并行) 实现并行算法也能产生较好的结果。因此迁移算子的 采用使并行算法更适合于全局寻优并且计算量较小。以基于粗粒度模型的并行 算法为例其迁移策略可分为以下两种： 1 一传多 每个处理器对应有若干个相邻处理器，每个处理器产生新一代个体后都将 自己最好的一个个体传送给其所有相邻处理器，并且接受来自相邻处理器的最 好个体，将这些个体与自己的个体同时考虑淘汰适应度差的个体4 1 。 2 一传一 考虑到染色体的多样性每个处理器都将自己最好的个体仅传给与之相邻的 一个处理器。同时增加两个参数：一是s e n d r a t e 决定处理器之间通讯的频 率。如：s e n d d a t e = 3 时表示当遗传代数是3 的倍数时各处理器之间相互传送个 体。二是s e n d - b e s t 决定每次传送给最好个体的数目。女f l s e n d - b e s t = 5 时表示每 1 6 山东大学硕士学位论文 个处理器把最好的前5 个个体传给各自的相邻处理器。其程序流程如图2 - 3 所示 【4 】 图2 - 3 一传一的流程图 1 7 山东大学硕十学位论文 第3 章一维装箱问题 由于本文的重点是来解决一维装箱问题，下面我们来重点介绍一维装箱问题。 3 1 一维装箱问题的定义和数学描述 经典的一维装箱问题是这样描述的：n 个物品( u 。，u 。u 。) 要装入k 个箱子 中( b l ，b 2 b k ) ，箱子的体积为c ，n 个物品的体积分别为v ( u 。) ，v ( 1 1 2 ) v ( u 。) ，要 求：v ( u i ) 鱼。 一个箱子可以装一件物品，也可以装几件物品，但每个箱子所装的物品体 积之和不能超过箱子的体积。如何确定装箱方案才能装下r l 件物品，并使箱子 的数目达到最少1 5 1 。 用线性规划的方法描述如下： s t wj x ，c yff ，= ( 1 2 ，刀) j = 1 x ，= 1 i ，歹= ( 1 2 柚) i = 1 x f ，= o 或1f ，= ( 1 ，2 ，刀) y f = o 或1i ，= ( 1 ，2 ，即) 其中 而= o 表示第j 个物品没有装入第i 个箱子中。 而= 1 表示第j 个物品装入第i 个箱子中。 只= 0 表示第i 个箱子没有被占用。 ”= 1 表示第i 个箱子被占用。 k 表示第j 件物品的体积。 儿 九崩 = zmm l 【j 东大学硕士学位论文 3 2 一维装箱问题的研究现状 从一维装箱问题的提出到现在，各类不同的算法不断被提出。主要是近似 算法和遗传算法。下面我们分别来介绍这些算法。 3 2 1 一维装箱问题的近似算法 lf i r s tf i t ( f f ) 算法 输入：l = ( a l ，a 2 a n ) 及每个物件的大小s ( a i ) e ( o ，1 ) i = l ，2 ，3 ，1 1 。 输出：需要的箱子数目m b e g i n s t e p l ：把物件a 1 放入第一个箱子b l 中。 s t e p 2 ：设在第i 步循环时。巳有的箱子编号为b 1 ，b 2 b k ，如果a i 不能依次的放r 入任何一个箱子b j 中，j 1 , 2 k ) 中，则新开一个箱子k + l ，把a i 放入放入 b k + l 之中，如果a l 可以放入某个b j 之中，则把它放入b j 中，直到把物件 a l ，a 2 ，a 3 a n ，全部放入m 个箱子中 s t e p 3 ：输出所用箱子数m