（基础数学专业论文）布局问题的演化算法.pdf

摘要 布局问题来源于现代生产的许多领域并且表现为多种形式，如服 装行业，部件拼装和超大规模集成电路( s l s i ) 。布局结果的好坏对 行业生产的合理性、经济性和安全性等质量指标具有重要的影响，布 局的过程也就是最优化过程。布局问题属于组合优化问题而且是n p 完全问题。虽然经过几代人的努力，但迄今尚无成熟的理论和有效的 数值计算方法，因此布局问题的研究仍具有重要的理论和实际意义。 演化计算是用计算机来模拟大自然的演化过程，特别是生命的进化过 程来求解复杂问题的一类计算模型。在解决优化问题的方法中，演化 计算是一个强有力的工具。 遗传算法是一种基于生物学进化原理的搜索算法。文中把生物学 中的遗传、变异、交叉用于二维布局中，从多个父代个体中生成多个 子代个体，根据目标函数值的优劣进行淘汰。 文中通过对矩形物体基于布置点的布局方法进行改进，在引入新 的个体表达方式和物体布局规则的基础上，提出了求解矩形物体布局 问题的分布估计算法并介绍了分布估计算法的主要特点。实例表明该 算法优于传统的遗传算法。 【关键词】布局问题遗传算法分布估计算法 a b s t r a c t t w o d i m e n s i o n a lp l a c e m e n tp r o b l e ma r i s e sf r o mav a r i e t yo f s 心m t i o i l si n c l u d i n ga p p a r e li n d u s t r y ，p a r t sn e s t i n gp r o b l e m s a n ds u p e rl a r g e s c a l ei n t e g r a ti o n ( s l s i ) t h ep l a c e m e n tr e s u l t h a sa ni m p o r t a n ti m p a c to nt h eq u a l i t i e st a r g e ti np r o f e s s i o n p r o d u c t i o n ，f o re x a m p l er a t i o n a l i z a t i o n ，e c o n o m i c a ls e c u r i t y ， o t c a n dt h ep l a c e m e n t p r o c e s s i sa l s ot h e o p t i m u m o n e p l a c e m e n tp r o b l e mb e l o n g st oa g g r e g a t eo p t i m u mp r o b l e ma n di t i sn pc o m p l e t ep r o b l e m t h o u g ha f t e rt h eh a r dw o r k ，b yf a rt h e r e i sn o tm a t u r et h e o r ya n dp r a c t i c a ls i g n i f i c a n c e e v o l u t i o n c a l c u l a t i o ni st h ee v o l u t i o np r o c e s sw h i c hi m i t a t e st h en a t u r e b yc o m p u t e r ，e s p e c i a l l yt h ee v o l u t i o np r o c e s so fl i f et os o l v e c o m p li c a t e dp r o b l e m i nt h e s em e t h o d so fs e t t li n go p t i m u m p r o b l e m ，e v o l u t i o nc a l c u l a t i o ni sav i g o r o u si n s t r u m e n t e v o l u t i o nc a l c u l a t i o ni st h ee v o l u t i o np r o c e s sw h i c hi m i t a t e s t h em s 。t u r eb yc o m p u t e r c t m e t i ca l g o r i t h m ( g a ) i sas e a r c h i n ga l g o r i t h mt h a ti s b a s e do nt h ee v o l u t i o nt h e o r ya n dp r i n c i p l e so fg e n e t i c so f ”o s c i e n c e t h r e eo p e r a t o r s ( c r o s s o v e rr e p l i c a t i o nm u t a t i o n ) a r ou s e di nt w o d i m e n s i o n a lp l a c e m e n tp r o b l e m m a n yp a r e n t g e n e r a ti o n sm a k em a n yf ili a lg e n e r a ti o n s ，a n dt h e nt h e i n d i v i d u a lw i l lb ea b a n d o n e da c c o r d i n gt ot h ev a l u eo ft h e o b j e c t i v ef u n c t i o n i nt h i sp a p e r ，b yi m p r o v i n gt h em e t h o df o rp l a c i n gr e c t a n g l e b a s e do n p l a c e m e n tp o i n t s ，w ep r e s e n tt h ee s t i m a t i o no f d i s t r i b u t i o na l g o r i t h mf o rt w o d i m e n s i o n a lp l a c e m e n tp r o b l e m t e s tr e s u l t ss h o wt h a te d ai sb e t t e rt h a ng e n e t i ca l g o r i t h m s k e y w o r d s ：p l a c e m e n tp r o b l e m ，g e n e t i ca l g o r i t h m ，e s t i m a t i o n o fd i s t r i b u t i o na l g o r i t h m m 布局问题的演化算法 附录3 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文是本人在导师的指导下独 立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不含其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标 明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：吻8 形簪 于。阻p 匕入l 卜佃亚佃：笙二一：f 一 钐舯7 年，月矗佰 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密函 ( 请在以上相应方框内打“4 ”) 作者签名：望昼兰奎日期：2 丑年生月互窆日 导师签名：铋日期：z 鱼一厂l 年一月咀日 s 】 布局问题的演化算法 1绪论 1 。j 引言 在大干世界中有一大类非常有趣的的问题，目前人们对它们还 没有快速合理的解决方法。其中许多问题都是生产实践中常常会碰 到的组合优化问题。例如： ( 1 ) 旅行商问题( t s p ) ：给定n 个城市和每两个城市之间的距 离，一个旅行商从其中一城市出发巡回售货，每个城市恰好经过一 次最后回到出发城市，这个旅行商应该如何选择路线使得经过的路 径最短? ( 2 ) 布局问题( p l p ) ：设有n 个已知长宽的矩形物体，要找一 个最优布局将它们放置到个包络矩形内，使各物体之间没有重叠 且包络矩形的面积最小? ( 3 ) 0 1 背包问题( k p ) ：给定一个可装重量m 的背包及1 1 件 物品，物品z 的重量和价值分别为形和c ( f ：1 , 2 ，儿) 。要选择若干 物品装入包中，使得其价值之和最大。 这一系列问题还有函数优化问题( 包括线性函数和非线性函 数) ，当其中问题的规模n 较大时，会出现所谓的“组合爆炸 问题， 从而使得传统的基于穷举思想的方法对此无能为力。因此，人们只 能寻找各种启发式方法和人工智能的方法来解决这类问题。 自然界从来都是人类学习和研究的主要对象，更是人类智慧的 湖南师范大学高校教师在职硕士学位论文 来源。人类很早就从自然界得到启发而改进自己的工具，鲁班被茅 苇划破而发明锯子，也许早先的发明只是偶然的模仿和发现， 到后来人们已经有意识地进行这方面的研究，这就是我们现在所说 的“仿生学”。顾名思义，仿生学就是模仿生物的某些功能，达到解 决人类问题的一门科学。演化计算是模拟自然界的进化过程并从中 得到启示的一种随机搜索算法。其优点包括概念及计算的简单性、 算法的普适性、卓越的问题求解能力、良好的并行性、对动态环境 的鲁棒性等。在过去的几十年里，用于求解组合问题的各种智能技 术已经得到成功开发。 本文将围绕智能计算的重要分支遗传算法和分布估计算法 及其在组合优化中的应用而展开。遗传算法( g e n e t i ca l g o r i t h m g a ) 是模拟自然界生物的遗传选择和自然淘汰等生物进化过程的仿生优 化算法。分布估计算法是演化计算的前沿工具，它继承了遗传算法 的群体演化模式，强化了演化过程中基因模块的保持，因而具有遗 传算法所没有的优势。本文将计算智能的这两个分支综合在一起应 用于组合优化中求解布局问题，做了一个对比研究，并取得了较好 的结果。布局问题是一个著名的n p 完全问题，求解时不仅要考虑 物体的放置顺序，还要考虑物体的放置方向，长和宽的限制等因素， | 人f 此布局问题要比其他n p 难题复杂得多。迄今为止尚无成熟的理 论和有效的数值计算方法。此外，尽管实际中经常会遇到不规则物 体的布局，但对二维布局问题的研究大多局限于矩形物体，不规则 物体的布局往往采用一定的方法转化为矩形物体的布局问题。因此， 布局问题的演化算法 对矩形物体布局问题的研究仍具有重要的理论和实际意义。在研究 方法上，人们提出了多种求解途径，归纳起来可分为两类：一类是 近似算法，如下次适应、首次适应、降序下次适应、最适应等；另 一类为布局优化算法，如数学规划、图论法等。由于问题的复杂性， 基于穷举思想的传统方法对此类布局问题的解决能力非常有限，因 此众多学者都在寻找各种启发式方法和智能方法来求解布局问题。 本文就是用智能计算的方法来探讨布局问题。 自1 8 3 1 年高斯( g a u s s ) 研究布局问题【1 】开始，虽然经过几代人 的努力，但迄今尚无成熟的理论和有效的数值计算方法。所谓布局 问题就是将一些物体，按一定要求合理地放置在一个空间内，使所 占守间尽量的小。布局问题涉及现实生活中的许多行业，比如航空 器上精密仪器的合理摆放问题、各种板材的下料问题、土地规划问 题、大规模电路设计问题等等。布局结果的好坏对行业生产的合理 性、经济性和安全性等质量指标具有重要的影响，布局的过程也就 是问题最优化过程。优化方法涉及的工程领域很广，问题种类与性 质繁多，归纳而言，最优化问题可分为函数最优化问题和组合最优 化问题两大类，其中函数最优化的对象是在一定区间内连续的变量， i f i j 组合优化的对象则是解空间中的离散状态【2 】。布局问题就属于组 合优化问题。 布局问题属于n p 完全问题，求解时我们不仅要考虑物体的放 j 潜顺序，还要考虑物体的放置方向、长度和宽度的限制等因素，因 此要比其他的n p 难题复杂得多。此外，尽管实际中经常会遇到不 湖南师范大学高校教师在职硕士学位论文 规则物体的布局问题，但对二维布局问题的研究大多局限于矩形物 体，不规则物体的布局往往采用一定的方法转化为矩形物体的布局 问题。因此，对矩形物体的布局问题的研究仍具有重要的理论和实 际意义。本文所研究的正是矩形物体的二维布局问题。 二维布局问题又称为二维切割问题，切割问题可分为两类：一 刀切问题和非刀切问题。所谓一刀切问题是指裁剪时必须从矩形 的一条边裁剪到对边，且平行于其余两边。 2 演化计算的基本结构与特征 当前的科学技术中有两大前沿学科，即生命科学和信息科学。 这两大学科既互相渗透又互相促进，同时也影响并带动其他学科的 发展。演化计算与这两大学科有着密切的关系。对演化计算的研究； 是当前信息科学的重要问题之一，众多相关学科的研究者不断介入、 积：趿探讨演化计算在各个方面的应用。演化来自生物学，用于描述 生物物种从一个状态到另一个状态的一个过程。自然界中的生物种 通过长期积累适应环境的功能来对付环境所带来的特殊挑战，从而 实现生物种的不断进化和繁衍后代。演化计算是用计算机来模拟大 自然的演化过程，特别是生命的进化过程来求解复杂问题的一类计 强纠鬯【3 】。 传统演化计算是模拟“物竞天择 与“自然遗传”的生物进化 过程所产生的随机化计算模型。它的起源可以追到本世纪5 0 年代后 期，但是，几乎在以后三十年时间里这一领域的工作对于广大的科 学l 作者相当陌生，造成这种状况的原因主要是当时缺少强大的计 布局问题的演化算法 算机硬件平台和早期演化计算本身的方法论缺陷。一直到了7 0 年代， h o l l a n d s l ，r e c h e n b e r d 6 1 ，s c h w e f e l e 1 ，f o g e l 等人的奠基性工作 才慢慢地改变了这种状况。特别是最近十年，以演化计算为主题的 出版物和学术会议逐年增加，充分说明了演化计算作为一个新兴学 科分支的巨大潜力。如今，面向应用的演化计算研究几乎渗透到各 行各业，正掀起了一个世界范围内的演化计算研究热潮。在国内， 武汉大学和中国科技大学率先开展了演化计算研究。那么，究竟是 什么原因使得演化计算在最近十年来被广泛研究和应用呢? 除了计 算，饥性能有了极大的提高外，我们认为主要归功于演化计算具有自 组织性、自学习性、自适应性、自优化等智能特征，同时又具有内 在并行性，原理的简单性，优良的全局性，计算的随机性与应用的 广泛性。传统的演化计算是由三个强相互联系、但事实上又是彼此 独立发展起来的分支组成的，它们是遗传算法( o a s ) 、演化规划( e p ) 、 演化策略( e s ) 。遗传算法最初由h o l l a n d 作为研究自适应过程的一般 模型被提出的，后来经d ej o n g ，g o l d - b e r g 及其他学者进一步扩充 和完善，现在主要应用于优化领域。特别值得一提的是k o z a 在遗传 算法方面的开创性工作，现已发展为演化计算的一个新分支一遗传 ，眦没计( g p ) ，k o z a 的思想可望成为真正意义上的自动程序设计 的理论与方法学 c 2 9 1 。演化规划是由f o g e ll j 作为产生人工智能 的一种尝试而提出的，b u r g i n ， a t m a r 及其他学者在这一领域作了 深入的工作，其方法是演化一个有限态自动机使之具有最佳的预测 能力，后来，f o g e ld b 借助于演化策略方法对演化规划进行了发展， 写 湖南师范大学高校教师在职硕士学位论文 并应用于数值优化与神经网络的训练等问题之中。r e c h e n b e r g 和 s c h w e f e l 为求解主要由试验得来的困难的离散或连续的多参数优化 问题提出了演化策略，后来，其他学者在这一领域继续展开了深入 的研究工作，演化策略得到了迅速发展。从8 0 年代开始，由于计算 机硬件性能的提高，使得演化计算可以应用于求解高度复杂的现实 优化问题，由此吸引了许多学科研究者的注意，导致了它的广泛研 究和应用，并于1 9 9 4 年召开了第一届演化计算国际会议。但是，有 点不可思议的是：在传统演化计算的各个分支里按照不同原则进行 演化计算研究的学者们过去一直保持彼此隔离，到9 0 年代初这种现 雾，才有了根本改变，各个分支渐渐相互渗透、借用和交融，终于形 成了现代意义上的演化计算的统一框架。现在，遗传算法、演化策 略、演化规划、遗传程序设计和模拟退火算法构成了演化计算的主 要分支和发展方向。 1 2 1 演化算法的基本结构 不同的编码方案、选择策略和遗传算子相结合，可构成不同的 演化算法，但其基本结构可描述如下： 乒：= 0 ： 随机产生初始种群e ( t ) 一 z 。，z 2 ，z 一) ； 计算p ( t ) 中每一个体的适应值； w h i l e ( 不满足停止准则) d o 布局问题的演化算法 由p ( o 通过遗传、变异等操作形成新一代种群p ( + 1 ) ； 计算p ( t + 1 ) 中个体的适应性； t ：= t + 1 ： 输出p ( t ) ； ) 其中t 表示演化代数，p ( t ) 表示第t 代种群，n 为群体规模，xf 为组成群体的个体，“，z 2 ，z 托 表示问题的一个可能解。 i 2 2 演化算法的基本步骤 在上述流程的基础上，设计演化算法的基本步骤可确定为： 1 ) 确定编码方案 演化算法求解问题不是直接作用在问题的解空间上，而是利用 解的某科，编码表示。选择何种编码表示有时将对算法的性能、效率 等产生很大影响。 2 ) 确定适应函数 适应值是对解的质量的一种度量，通常依赖于解的行为与环境 ( 即种群) 的关系，一般以目标函数或费用函数的形式来表示。解的适 应仳己演化过程中进行选择的唯一依据。 3 ) 确定选择策略 优胜劣汰的选择机制使适应值大的解有较高的存活概率，这是 演化算法与一般搜索算法的主要区别之一。不同的选择策略对算法 的性能有较大的影响。 湖南师范大学高校教师在职硕士学位论文 ) 选取控制参数 控制参数主要包括种群的规模、算法执行的最大代数、执行不 同遗传操作的概率，以及其它一些辅助性控制参数。 5 ) 设计遗传算子 演化算法中的遗传算子主要包括再 _ ( r e p r o d u c t i o n ) 、杂交( c r o s s o v e t ) 、变异( m u t a t i o n ) ，以及其它高级操作。 6 ) 确定算法的终止准则 由于演化计算没有利用目标函数的梯度等信息，所以在演化过 棵，；，无法确定个体在解空间中的位置，因而无法用传统方法判定算 法收敛与否，以便终止算法。常用的办法是，预先规定一个最大的 演化代数，或算法在连续多少代解的适应值没有明显改进时，即终 止。 7 ) 编程上机运行 完成上述工作后，即可按演化计算的算法结构编程，进行问题 求解。由于演化算法的随机性及不确定性等特点，通常要多运行几 次才能得到可靠的解。 应该注意的是，上述基本步骤密切相关，编码方案与遗传算子 的波汁等是同步考虑的，有时甚至需要上机运行与算法设计交替进 行。 总的来说，演化计算主要由七个部分组成：个体的编码表示、 ： - f it 、, 化种群、适应函数、遗传操作、选择策略、算法控制参数和算 法终止条件。 布局问题的演化算法 演化计算的基本特征【3 】，除了其自组织、自适应性和本质并行 性外，还具有过程性、多解性、不确定性、非定向性、内存学习性、 统计性、稳定性和整体优化性。 基于上述特征，演化计算与传统的搜索算法相比具有如下的不 同点： ( 1 ) 演化计算不是直接作用在解空间上，而是利用解的某种编 码表示； ( 2 ) 演化计算从一个群体( 即多个点而不是从一个点) 开始搜 索，这是它能以较大的概率找到整体最优解的主要原因之一； 彗 ( 3 ) 演化计算只使用解的适应性信息( 即目标函数) ，并在增 加收益和减少开销之间进行权衡，而传统搜索算法一般要使用导数 等其他辅助信息； ( 4 ) 演化计算使用随机转移规则而不是确定性的转移规则。 1 2 3 演化算法的编码表示 设计演化算法的一个重要步骤是，对所解问题的变量进行编码 表示，编码表示方案的选取在很大程度上依赖于问题的性质及遗传 算子的设计。通常，在设计演化算法时，只有两个方面与所求问题 有关，即问题的编码表示与适应函数的确定。 根据编码方式的不同，演化算法的编码策略大致可分为二进制 编码、实数编码、有序串编码与结构性编码等。 二进制编码就是将原问题的解空间映射到位串空间b = 0 ，1 ) 上，然后在位串空间上进行遗传操作，结果再通过解码过程还原成 湖南师范大学高校教师在职硕士学位论文 其表现型，以进行适应值的评估。当变量不止一个分量时，我们可 以对各分量分别进行编码，然后合并成一个长串。解码时，根据其 对应的子串分别进行解码即可。 采用二进制编码时，一般要先给出求解精度以确定串长。而一 旦精度确定后，就很难在算法执行过程中进行调整，因而算法缺乏 微调( f i n e t u n i n g ) 的功能。在求解高维优化问题或要求精度很高时， 二进制串很长，因而算法的搜索效率很低。 基于上述原因，有人提出了g r a y 编码、动态编码等策略。g r a y 编码是将二进制编码通过g r a y 变换后得到的编码，目的是为了减少 翻转次数，克服二进制编码的h a m m i n g 悬崖( h a m m i n gc l i f f s ) 的缺点。 动态编码是当算法收敛到某局部最优时，增加搜索的精度。办法是， 在保持二进制串长不变的前提下减小搜索区域。为了克服二进制编 码的缺点，对于问题的变量是实向量的情况，也可直接采用实进制 进行编码。这样，可直接在解的表现型上进行遗传操作，从而便于 引入与问题领域相关的启发式信息，以增加演化算法的搜索能力。 从演化计算的各分支看，在求解数值优化问题时，演化策略及演化 规划都采用实数编码，而且在早期不使用杂交算子( 演化策略中现在 使用的重组算子非常类似杂交算子) 。遗传算法则较多地采用二进制 编码。近几年，遗传算法在求解高维或复杂优化问题时也大多使用 实数编码。由于实数编码表示比较自然，而且较易引入相关的领域 知识，因此，我们认为其使用将越来越广泛。 对很多组合优化问题，目标函数的值不仅与表示解的字符串中 布局问题的演化算法 各字符的值有关，而且与其所在字符串的位置有关，这样的问题称 为有序问题。若目标函数的值只与表示解的字符串中各字符的位置 有关，与其具体的字符值无关，则称为纯有序问题。对这类问题， 较“然的编码表示就是有序串编码。用演化算法求解有序问题时， 传统的遗传操作可能产生非法的后代。因此，对这类问题要针对具 体问题专门设计有效且能保证后代合法的遗传算子。这类编码方案 较多地用在组合优化问题中。对很多问题，更自然的表示是树或图 的形式。这时，采用其它形式的编码可能很困难。这种将问题的解 表示成树或图的形式的编码称为结构式编码。对这种非线性编码方 式，我们应非常谨慎地设计遗传算子，以便不产生或少产生非法的 后代。对结构式编码要讨论通用的遗传算子很困难，一般是就具体 问题具体分析。因为遗传算子直接在解的表现型上进行操作，所以 比较容易加入与领域有关的知识和一些启发式信息。 1 3国内外对布局问题的研究现状 布局问题属于n p 完全问题。在研究方法上，学者们提出了多 种水解途径。但由于问题的复杂性，基于穷举思想的传统方法对布 局问题的解决能力非常有限，因此吸引了许多研究人员对它进行深 入的研究。d o w s l a n d 4 】对各种布局问题进行了综述和分类。 s c h c i t h a u e r 5 对布局问题的模型进行了研究。u d y 6 】利用序列二次 规划和广义简约梯度法来解小型三维布局问题，但其解的质量过分 依赖于初始位置的选择。k i m 7 】通过惩罚因子将布局约束转化为目 标函数惩罚项，然后用无约束优化方法来求解布局问题。由于优化算 1 1 湖南师范大学高校教师在职硕士学位论文 法本身只能找到局部最优解，因而对于规模大或物体形状复杂的布 局问题，局部最优的数目将急剧增加且其质量将急剧下降，即与全 局最优解的差别越来越大。此外，布局问题中导数的求解也十分困 雉。 王金敏等针对目标的布局采用启发式算法进行了研究讨论，该 算法在布局开始时确定布局目标，并且不断地将布局空间进行分解， 然后通过群组构造布局物体，让每个局部最优解达到或优于布局目 标值，从而得到比较稳定的全局解，达到了基于目标的布局启发式 算法追求的目标，同时通过实例验证，并与不同算法的布局结果进 行比较，证明了该算法的有效性【8 】。王金敏等也对矩形物体布局问 题利用构造算法进行了探讨分析。构造算法通过分析矩形物体布局 问题的特点，提出了定量的定序规则和定位规则。该算法既可用来 解决工业上的一刀切问题，又能解决其它非一刀切问题 9 】。文献 1 0 】 通过模拟退火算法探讨了布局问题的求解。肖美华等将矩形件正交 排样问题转化为一个排列问题，运用了求一个排列所对应的排样图 的下台阶算法( 改进的b l 算法) ，将下台阶算法与遗传算法相结合， 并对遗传算法作了改进，在遗传算法中运用模拟退火算法作为个体 f 即选择策略，运用上述思想于矩形件排样问题的求解，给出了算法 的实现，并分别从编码、遗传算子( 繁殖、杂交、变异) 的设计、 选择策略、适应性函数选择等方面，进行分析f 1 1 】。郭宏伟、袁立等 ，旌十布置点的矩形物体布局问题的利用遗传算法进行了研究 a 2 】，并 且设计出遗传算法新的编码方法和解码方法，解决了布局问题求解 布局问题的演化算法 的三个问题：待布入物体的摆放顺序、待布入物体的摆放方式、待 布入物体的摆放位置。这些研究为利用遗传算法解决布局问题起到 了非常积极的作用。吴斐，侯云章等基于启发式结果的模拟退火算 法澍二维空间的正交布局问题进行了研究 1 3 1 。通过对给定m 个矩 形块，将其摆放到布局空间内，并且要将矩形块的各个边限制为 分别平行与布局空间的各个边。对于每个布局物体i ，建立相应 的五元组数据结构( x i ，y i ，l i ，w i ，m o d e ) 其中( x i ，y i ) 为i 的中心坐标，“，w i 为物体的长和宽。m o d e 表示物体i 的摆放方 式。此处有两种摆放方式：m o d e = 0 ，表示物体的长对应于布局空 间的长；m o d e = 1 表示物体的宽对应于布局空间的长。以布局空间 的左上角作为坐标原点，以布局空间的长l 作为x 轴，宽w 作为y 轴，建立平面坐标系。这样建立的五元组也就可以准确表 示待布局物体在布局空间中的准确位置。同时使物体与物体之间紧 密相邻，并且尽量靠近布局空间的某一个边，以使布局空间所剩的 面积尽量多。模拟退火算法属于仿物算法，也是智能计算的重要组 成部份。文献1 0 和文献1 3 为应用模拟退火算法求解布局问题做出 了积极的贡献。 虽然并行算法在理论上不能完全解决n p 完全问题，但解决实 际题确实可行。并行化计算能提供工程和科学中需要的高质性能、 实时控制中的快速响应及高可靠度系统中所必需的容错处理等，因 此对并行布局算法的研究符合时代发展的需要。在对布局问题进行 4 ；i j ：研究的同时，也有不少研究者对布局问题进行了并行算法的研 湖南师范大学高校教师在职硕士学位论文 究与探讨。文献【1 4 】设计出基于s i m d c r e w 共享存储模型的并行 矩形物体的布局算法，并通过与串行算法的比较和实例分析验证了 该并行算法的有效性。并行算法在一定程度上进一步推动了布局问 题更丰富多样的求解方法的发展和应用，进一步充实了智能计算的 理论基础。 1 4 本文的主要工作 本文在分析研究了目前求解布局问题的主要几种方法的基础 上，利用分布估计算法对二维矩形物体的布局问题进行了研究探讨。 在第二章，介绍了遗传算法的基本理论、遗传算法的基本步骤、 遗传算法的基本操作、遗传算法的特点、遗传算法关键参数与操作 的设汁、遗传算法的改进与结合，并且对利用遗传算法求解布局问 题进行了算例说明和遗传算法的实现。 在第三章，介绍了分布估计算法，通过引入新的个体表达方式 和新的物体布局规则，第一次将分布估计算法成功应用于布局问题 的求解。通过求解布局问题算例，将运用该算法所得的结果与运用 遗传算法求解同一布局问题所得的进行了分析比较，证明了新算法 的有效性和适用性。分布估计算法中的概率模型评估算子是一种实 现非常简单、稳定性能良好的有效算子 在第四章，对本文研究工作进行了总结，并对今后的进一步研 究与探讨工作有了初步计划和安排。 布局问题的演化算法 2 遗传算法在布局问题中的应用 遗传算法( g e n e t i ca l g o r i t h m - g a ) 是模拟达尔文的遗传选择和 自然淘汰等生物进化过程的仿生优化算法。遗传算法研究的兴起是 在8 0 年代末和9 0 年代初期，但它的历史起源可追溯至6 0 年代初期。 早期的研究大多以对自然系统的计算机模拟为主。如f r a s e r 的模拟 研究，他提出了和现在的遗传算法十分相似的概念和思想。h o l l a n d 和d e j o n g 的创造性研究成果改变了早期遗传算法研究的无目标性和 理论指导的缺乏。其中，h o l l a n d 于1 9 7 5 年出版的著名著作 系统地阐述了遗传算法的基本理论和方” 法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。 这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要 性。同年，d e j o n g 的重要论文 将 h o l l a n d 的模式理论与他的计算实验结合起来，并提出了诸如代沟等 新的遗传操作技术。可以认为，d e j o n g 所作的研究工作是遗传算法 发展过程中的一个里程碑 1 5 。遗传算法通过对生物遗传和进化过 程中选择、交叉、变异机理的模仿，来完成对问题最优解的搜索过 程，算法具有良好的全局搜索能力。进入8 0 年代，遗传算法迎来了 兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课 题，遗传算法的应用领域也不断扩大。 湖南师范大学高校教师在职硕士学位论文 目前遗传算法所涉及的主要领域有自动控制、规划设计、组合 优化、图象处理、信号处理、人工生命等。可见，遗传算法的应用 研究已从初期的组合优化求解拓展到了许多更新、更工程化的应用 方面。尽管遗传算法本身在理论和应用方法上仍然有很多要进一步 研究的问题，但它在机器学习、组合优化、优化控制、任务调度、 图像处理、神经网络等领域都得到了成功的应用。与此同时，应用 实践表明，遗传算法在应用中也存在一些不尽人意的问题，最突出 的是遗传算法容易产生早熟、局部寻优能力较差等。因此众多学者 致力于遗传的改进、加强和与其他算法结合运用，同时，更多的新 的算法得到了实现。 2 1 遗传算法的基本理论 遗传算法是一种概率搜索算法，它是利用某种编码技术作用于 称为染色体的二进制串，其基本思想是模拟由这些串组成的群体的 进化过程0 6 。遗传算法通过有组织地、然而也是随机地信息交换来 重新结合那些适应性好的串，在每一代中利用上一代串结构中适应 性好的位和段来生成一个新的串的群体；同时也在串结构中尝试用 新的位和段来代替原来的部分。遗传算法对求解问题的本身一无所 知，它所需要的仅仅是对算法所产生的每个染色体进行评价，并基 于适应值来选择染色体，使适应性好的染色体比适应性差的染色体 有更多的繁殖机会。从而达到优化的目的。 图2 1 中表示了遗传算法的执行过程。 布局问题的演化算法 0 户 0 0- 蠡镀110-o 毛。罟、霾粉主 2 色 图2 - 1 遗传算法原理 2 2 遗传算法的基本步骤 遗传算法开始于一个用染色体形式表达的初始解集，总是用前 一代解集的解来生成后一代解集的解，整个过程有一个进化的思想， 那就是新一代总是要比旧一代要优良。因此在选择产生新一代的父 体时胎，足参照他们的适应值，适应值越大，再生的机会越大。进化 的过程不断延续，直到满足终止条件。所以，标准遗传算法的主要 步骤町描述如下： ( 1 ) 随机产生一组初始个体构成初始种群，并计算种群中每一 个染色体的适应值； 湖南师范大学高校教师在职硕士学位论文 ( 2 ) 判断算法收敛准则是否满足。若满足则输出搜索结果；否 则执行以下步骤； ( 3 ) 根据适应值大小以一定方式执行复制操作； ( 4 ) 按交叉概率见执行交叉操作； ( 5 ) 按变异概率p 历执行变异操作； ( 6 ) 返回步骤( 2 ) 。 卜述算法中，适应值是对染色体( 个体) 进行评价的一种指标， 是g a 进行优化的主要信息，它与个体的目标值存在一种对应关系； 箩制操作通常采用比例复制，即复制概率正比于个体的适应值，这 意味着适应值高的个体在下一代中复制自身的概率也大，从而提高 了种群的平均适应值，达到优化的目的；交叉操作通过交换两个父 代全体的部分信息构成后代个体，使后代个体继承了父代的奏效模 式，从而有助于产生优良个体；变异操作通过随机改变个体中某些 基因而产生新个体，有利于增加种群的多样性，避免算法早衰。 遗传算法的流程图可用图2 2 描述。 布局问题的演化算法 遗传算法的优化框图： 图2 2 遗传算法的优化框图 湖南师范大学高校教师在职硕士学位论文 2 3 遗传算法的基本操作 遗传算法包括三个基本的操作( 也称为三个基本算子) ：选择、 交叉和变异，这三个基本操作又是循环往复执行的且与进化的过程 ( 代数) 无关。下面对各个基本操作进行简单介绍。 2 3 1 选择( s e l e c ti o n ) 选择也称为复制，其目的为把当前群体中的个体按与适应值成 比例的概率复制到新的群体中。选择( 复制) 过程可用最常用的技 术赌盘选择来实现，此外还有随机遍历抽样、局部选择、截断 选择、锦标赛选择等算法也可实现选择过程。 2 ，3 ，2 交叉( c r o ss o v e r ) 交叉也称为杂交，是结合来自父代种群中的信息产生新的个体。 杂交算子有多种，主要分为两类：二进制编码和实值编码。在二进 制编码算子中又有单点交叉、多点交叉、均匀交叉等。其中最简单 的单点杂交算子的作用过程如下：首先产生一个在1n l 一1 2 _ 间的 一致随机数i ；然后配对的两个个体( 染色体) 相互对应地交换从i 到z 的位段( 基因) ，其中z 为个体( 染色体) 的串长。 2 3 3 变异( m u t ati o n ) 交叉之后的子代经历的变异是子代基因以小概率扰动产生的变 化。对于二进制串，就是相应位从0 变1 或是从1 变0 。与选择算子 和交叉算子相比，变异算子是遗传算子中次要的算子，它在恢复群 体- i i 火去的多样性方面具有潜在的作用。同生物界一样，g a 中变异 发生的概率很低，通常取值在0 0 0 1 - 0 0 1 之间。变异为新个体的产 布局问题的演化算法 生提供了机会。 上述各种算子的实现是多种多样的，而且许多新的算子正在不 断地提出，以改进g a 的某些性能。系统参数( 个体数n ，基因链长度 l ，交义概率p c ，变异概率p m 等) 对算法的收敛速度及结果有很大的影 响，应视具体问题选取不同的值。 2 4 遗传算法的特点 遗传算法作为一种快捷、简单、容错性强的算法，在各类结构 对象的优化过程中显示出明显的优势。与传统的优化算法相比，遗 传算法主要具有以下不同之处： ( 1 ) 遗传算法不是直接作用在参变量集上，而是利用参变量的 某种编码； ( 2 ) 遗传算法不是从单个点，而是从点的群体开始搜索； ( 3 ) 遗传算法利用个体适应值的信息，无须导数或其他辅助信 息； ( 4 ) 遗传算法利用概率转移规则，而非确定性规则。 遗传算法的优越性主要表现在：首先，它在搜索过程中不容易 陷入局部最优，即使在所定义的适应函数是不连续的、非规则的或 是有噪声的情况下，遗传算法也能以较大的概率找到整体最优解； 其次，由于遗传算法固有的并行性，它非常适用于大规模并行计算 机。其最主要的特点体现在下述两个方面：( 1 ) 智能性：遗传算法 在确定了编码方案、适应值函数及遗传算子以后，算法将利用演化 过程中获得的信息自行组织搜索。“物竞天择、优胜劣汰、适者生存”， 2 1 湖南师范大学高校教师在职硕士学位论文 适应值大的个体具有较高生存概率，是具有“潜在学习能力”的自 适应搜索技术。( 2 ) 本质并行性：g a 在本质上是并行的，适于求解 复杂的问题和搜索复杂的解空间，低阶、短定义长度的模式在群体 的遗传过程中将指数增加。大小为撑的群体中，每代处理的模式数目 加( 疗3 ) ，它的鲁棒性强，容易直接移植到实际问题中。 2 5 遗传算法关键参数与操作的设计 一般情况下，遗传算法的设计是按如下步骤进行的： ( 1 ) 确定问题的编码方案； ( 2 ) 确定适应值函数； ( 3 ) 遗传算子的设计； ( 4 ) 遗传算法参数的选择。主要包括初始群体所含个体的个数、 交叉概率、变异概率、遗传代数等； ( 5 ) 确定遗传算法的终止条件。 2 6 遗传算法的改进与结合 遗传算法的主要任务和目的，是设法产生或有助于产生优良的 个体，且这些个体能充分表现出解空间中的解，从而使算法效率提 芦j 燧免产衰现象发生。但实际应用遗传算法时，往往出现早衰和 收敛性能差等缺点，于是出现了各种各样的改进或结合。目前的改 进方法基本上是针对基因操作、种群的宏观操作、基于知识的操作 和并行化计算操作。 郭涛算法正是基于以上思想提出的一类基于子空间搜索和群体 布局问题的演化算法 爬山法结合的群体随机搜索算法，也称为多父体杂交算法。该算法 有以下特点： 1 ) 利用了演化计算中的群体搜索策略，保证了搜索空间的全局 阽，二自利于搜索问题的解。 2 ) 采用随机子空间中的随机搜索( 多父体重组) 策略，特别是子 空间中随机搜索的非凸性： mm x k q z ，其中吗= i ， - 0 5 sq 1 5 扛ii = l 使算法搜索的子空间可复盖多父体的凸组合空间，保证了随机 搜索的遍历性，即解空间中不存在算法搜索不到的“死角 。 3 ) 采用了“劣汰策略”，每次只把群体中适应性最差( 目标函数 值最人) 的个体淘汰出局，淘汰压力最小，既保证了群体的多样性，铷 也保证了适应性最好( 目标函数值最小) 的个体可以“万寿无疆”。这 种“群体爬山策略 ， 保证了整个群体最后集体登上最高峰( 深谷) 。 当最优解不唯一时，算法可能一次同时找到多个最优解。 精英多父体杂交算法改进了郭涛算法中个体交叉时个体的选择 方案。在郭涛算法中是随机选择个体进行交叉；在精英多父体杂交 方法中，增加选择的压力，选择当前群体年的最好的若干个体，这 样做可以使个体中好的基因有更多的繁殖与生存机遇，能明显加快 算法的收敛速度。 本文讨论的分布估计算法，又称为基于概率模型的遗传算法继 承了遗传算法的群体演化模式，强化了演化过程中基因模式的保存， 也是遗传算法的改进提高。 3 湖南师范大学高校教师在职硕士学位论文 2 7 布局问题的遗传算法实现 基于文献1 2 、1 7 的思想，假定有m 个长方体布局物体需要摆放 到布局空间内。此时，布局问题所追求的目标是使布局物体尽量紧 密相邻并靠近布局空间的某一面，以便留下尽可能多的剩余空间放 入其它布局物体，或者所追求的说目标是在布局空间宽度固定的情 况下使布局物体所占布局空间的长度尽可能的小。据此，布局问题的 目标函数可写为： m i n ，唧+ 仃z 荟“+ 卿z ) 式中1 表示布局完成后布局物体所形成的最小包容布局空间的 长度，( ) 1 、( i ) 2 为权重因子( ( i ) 1 + ( i ) 2 = 1 ) ，x i 和y ；第i 个布局物体中 心点坐标值，q 为权重因子。布局空间的长度越小，表明布局物体摆 放的越紧密，利用率越高。目标函数的第二项数值越小，表示布局物 体的摆放位置越靠近布局空间的左下角，浪费的布局空间也就越少。 算法采用二维数组来表示个体结构，例如个体f ( 4 ，1 ) ( 2 ，0 ) ( 1 ，1 ) ( 5 ， 1 ) ( 3 ，0 ) ) 表示五个布局物体的排放顺序和排放方式。数组第一维下 标的组合( 4 ，2 ，1 ，5 ，3 ) 表示物体在平面上排放的先后顺序，数 组第二维下标表示物体在平面上排放的方式，具体为：0 表示布局物 体的长平行于水平方向，1 表示布局物体的长平行于垂直方向。 基于遗传算法的二维布局求解算法流程如下： ( 1 ) 设置种群进化代数并初始化g e n = l ； ( 2 ) 随机生成n 个初始解； 布局问题的演化算法 ( 3 ) 根据目标函数的定义，计算各个体的适应值； ( 4 ) 选择操作 ( 5 ) 交叉操作 ( 6 ) 变异操作 ( 7 ) 计算新个体的适应值； ( 8 ) 判断进化代数g e n 是否小于g e n _ m a x ，若是，结束算法并给出 最优解，若否，则继续； ( 9 ) g e n = g e n + l ，转第4 步。 算例计算5 0 个尺寸如下的矩形物体在宽度固定在4 0 0 ，长度 不限的矩形内优化布局方式( 单位：c m ) ： ( 3 0 ，1 2 0 ) ，( 3 0 ，1 0 0 ) ，( 3 0 ，8 0 ) ，( 3 0 ，6 0 ) ，( 3 0 ，4 0 ) ( 4 0 ，1 2 0 ) ，( 4 0 ，1 0 0 ) ，( 4 0 ，8 0 ) ，( 4 0 ，6 0 ) ，( 4 0 ，4 0 ) ( 5 0 ，1 2 0 ) ，( 5 0 ，1 0 0 ) ，( 5 0 ，8 0 ) ，( 5