（系统工程专业论文）基于空间划分的搜索算法.pdf

山东大学硕士学位论文 摘要 优化是一种以数学为基础，用于求解各种工程问题优化解的应用技术，它 作为一个重要的科学分支一直受到人们的广泛重视，并在诸多工程领域得到广 泛应用然而，随着求解问题规模的扩大和复杂度的提高，目前这些优化算法 的收敛速度将非常慢，有时甚至得不到满意解因此，研究优化方法对改进算 法性能、拓宽算法应用领域、完善算法体系具有重要的作用。空间划分与空间 收缩的引入，给优化算法的研究提供了新思路 优化搜索算法主要可分为两类：全局搜索算法和局部搜索算法。本文首先 介绍了优化算法的发展概况，重点介绍了一种典型的全局搜索算法一遗传算法 及一种典型的搜索优化算法一禁忌搜索算法。最后介绍了一种新的确定型优化 算法一区间优化算法 本文的一个重点是提出了一种基于网格划分的混合搜索算法。该算法引入 了空间划分和收缩的思想，在求解过程中首先应用一种全局优化算法确定优解 信息，其次使用网格划分和合并将解空间快速划分和收缩为多个子空间，然后 用一种局部优化算法在模型的极值点附近搜索，可以很快地收敛到极值点。仿 真结果表明该算法在搜索效率、应用范围，解的精确性和鲁棒性上都体现了良 好的性能。 另外，本文改进了区间优化算法。对一维优化问题，该算法加入了一个新 的区阃删除步骤。该删除步骤包含边界删除和内部删除两部分，可以快速有效 地删除不包含全局极小点的空间。对多维优化问题，提出了混合区间演化算法， 将区间算法和演化算法取长补短，很好的融合在一起。数值试验表明，一维和 多维两种区间算法都是可靠、有效的。文章的最后，作者总结全文，指出了有 待进一步解决的问题，并对优化算法的发展前景作出了展望 关键词：优化；空间划分；遗传算法；禁忌搜索；网格划分：区间算法 第1 页 山东大学硕士学位论文 a b s t r a c t o p t i m i z a t i o ni so n et y p eo fa p p l i c a t i o nt e c h n o l o g yb a s e do nm a t h e m a t i c sa n d u s e dt oa c q u i r et h eo p t i m i z e dr e s o l u t i o n so f d i v e r s i f i e de n g i n e e r i n gp r o b l e m s p e o p l e h a v eb e e nw i d e l yp a y i n ga t t e n t i o nt oi ta sa l li m p o r t a n tb r a n c ho fs c i e n c ef r o mt h e b e g i n n i n g , a n di tw a sr a p i d l yc a r r i e do u ta n da p p l i e di nm a n ye n g i n e e r i n gf i e l d s b u t t h ec o n v e r g e n ts p e e do fs o m ep r o b l e m sw i t hl a r g es c a l e sa n dh i g hc o m p l e x i t yw o u l d g r e a t l ys l o wd o w nb e c a u s eo fo p t i m i z a t i o na l g o r i t h m s i n h e r e n tf a u l t a c c e r d i n g l y t h et h e o r yr e s e a r c ho no p t i m i z a t i o na l g o r i t h m sh a sr e m a r k a b l ee f f e c t so ni m p r o v i n g p e r f o r m a n c e p e r f e c t i n g a r c h i t e c t u r ea n ds p r e a d i n g a p p l i c a b l e l e t h e i n t e r v e n t i o no fs p a c ep a r t i t i o na n ds p a c ec o n l r a e tt h e o r yp r o v i d e sn e wi d e a sf o r o p t i m i z a t i o na l g o r i t h m s t h ee v o l v e m e n to fs e a r c ho p t i m i z a t i o na l g o r i t h m si sf i r s t l yi n t r o d u c e di nt h i s t h e s i sb yc l a s s i f y i n gi ti n t ot w og r o u p s ：t h eg l o b a ls e a r c ha l g o r i t h m sa n dt h el o c a l s e a r c ha l g o r i t h m s t h e nw ei n t r o d u c eo n et y p i c a lg l o b a ls e a r c ha l g o r i t h m - g e n e t i c a l g o r i t h m ，a n do n et y p i c a ll o c a ls e a r c ha l g o r i t h m t a b us e a r c ha l g o r i t h m an e w c e r t a i na l g o r i t h mi sa l s od e s c r i b e d i n t e r v a lo p t i m i z a t i o na l g o r i t h m o n ee m p h a s i so f t h i sp a p e ri st op r e s e n tah y b r i ds e a r c ha l g o r i t h mb a s e do ng r i d p a r t i t i o n i n g t h ei d e a sa b o u ts p a c ep a r t i t i o na n ds p a c ec o n t r a c t i n ga r ea p p l i e di n t h i s h y b r i da l g o r i t h m ：a s c e r t a i nt h ee l i t ei n d i v i d u a l sb yo n et y p eo fg l o b a lo p t i m i z a t i o n a l g o r i t h m sd u r i n gt h ef i r s ts t e p ，t h e nr a p i d l yp a r t i t i o ns p a c ea n dc o n t r a c ti tt om u l t i s u b s p a c e s ，i ns u c c e s s i o nt h ee x t r e m u mi sc o n v e r g e do ni ns h o r tt i m eb yh u n t i n g n e a r b yt h em o d e l se x t r e m u mu s i n gas o r to fl o c a lo p t i m i z a t i o na l g o r i t h m s t h e s i m u l a t i o nr e s u l t ss h o wt h a tt h eh y b r i da l g o r i t h mh a se x c e l l e n tp e r f o r m a n c ei n e f f i c i e n c y , a p p l i c a b l ef i e l d s ，r e s u l t sp r e c i s i o na n dr o b u s t i c i t y , t h e r e f o r ei tp r o v e so u r a l g o r i t h mc a nw o r ke f f i c i e n t l y f u r t h e r m o r e ，s o m ei m p r o v e m e n t s a r em a d et ot h ei n t e r v a l o p t i m i z a t i o n a l g o r i t h mi nt h ep a p e r a sf o ro n e d i m e n s i o no p t i m i z a t i o np r o b l e m san e ws t e po f i n t e r v a lp r u n i n gt h a ti n c l u d e sb o u n d a r yp r u n i n ga n di n n e rp r u n i n gi sc o m b i n e di n t o t h ea l g o r i t h mc o m p u t a t i o np r o c e s s ，a n di tc a r lr a p i d l yd e l e t et h es p a c eb a r r i n gg l o b a l e x t r e m u m sw i t h h i g he f f i c i e n c y ah y b r i di n t e r v a le v o l u t i o n a r ya l g o r i t h m i s d e l i v e r e da sf o rm u l t i - d i m e n s i o no p t i m i z a t i o np r o b l e m s t h eh y b r i da l g o r i t h mt a k e s 第n 页 山东大学硕士学位论文 s t r o n gp o i n t sf r o mi n t e r v a lm e t h o da n de v o l u t i o n a r ya l g o r i t h mt oo f f s e tt h e i r w e a k n e s s e s ，h e n c 地t h et w oa l g o r i t h m sa r es y n c r c t i z e dw e l l t h en u m e r i c a l e x p e r i m e n t si n d i c a t et h a tb o t ho n e - d i m e n s i o na n dm u l t i d i m e n s i o na l g o r i t h m sa r c r e l i a b l ea n de f f i c i e n t i nt h ef i n a lt h es u m m a r i z a t i o ni sp r e s e n t e d s o m ep r o b l e m st o b es o l v e da n dt h ep r o s p e c to f o p t i m i z a t i o na l g o r i t h m sa r ep o i n t e do u t k e yw o r d s ：o p t i m i z a t i o n ；s p a c ep a r t i t i o n ；g e n e t i ca l g o r i t h m ；t a b us e a r c h ；g r i d p a r t i t i o n ；i n t e r v a lm e t h o d 第页 l 附件一： 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：鞋： 碴日期：塑竺篁：! ! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：径：丝导师签各j 垒! f 查日期：翌! ：三：， 1 1 课题背景 第一章绪论 优化技术是一种以数学为基础，用于求解各种寻优问题优化解的应用技术 作为一个重要的科学分支，它一直受到人们的广泛重视，并在诸多工程领域得 到迅速推广和应用，如系统控制、人工智能、模式识别、生产调度、超大规模 集成电路( v l s i ) 技术和计算机工程等 所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制， 通过一定的途径或规则来得到满足用户需求的问题的解。在很多情况下，一个 最优化问题可以用许多方法加以解决，而每种方法又能够采取多种算法予以实 现。优化方法涉及的应用领域很广，问题种类与性质繁多。归纳而言，最优化 问题可分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定 区间内的连续变量，而组合优化的对象则是解空间中的离散状态。根据目标函 数和约束条件的性质，又可分为线性规划问题和非线性规划问题。对于一些规 模较小的优化问题，传统的优化算法【l 】就能进行求解，如求解线性规划的单纯 形法、求解混合整数线性规划的割平面法和分支定界法、求解非线性规划问题 的序列无约束最小化法( s u m t ) 和序列二次规划法( s q p ) 等，这些算法在求解小 规模的优化问题时能够达到较高的速度和精度但在实际的生产过程中的优化 问题大多是n p c 问题，由于求解复杂度过大，传统的优化算法已经无能为力 2 0 世纪8 0 年代以来，一些新颖的优化算法【2 】，如人工神经网络、混沌，遗 传算法、进化规划、模拟退火、禁忌搜索、蚁群算法及其混合优化策略等，通 过模拟或揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、物理 学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供 了新的思路和手段这些算法独特的优点和机制，引起了国内外学者的广泛重 视并掀起了该领域的研究热潮，且在诸多领域得到了成功应用。在优化领域， 由于这些算法构造的直观性与自然机理，因而通常被称作智能优化算法 ( i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) ，或称为现代启发式算法( m e t a - h e u r i s t i e a l g o r i t h m s ) 。对于复杂优化问题的求解，智能算法较传统优化方法具有实用性、 通用性、灵活性强，效率高等特点因此智能算法在优化领域的研究日趋活跃 现在的智能优化算法，一般是以某种规则搜索优化问题的解空问。例如全 第1 页 山东大学硕士学位论文 局搜索算法就是在问题的全空间上搜索因此当问题规模变大时，搜索空间迅 速增大，随之搜索时间急剧增加。而分支定界算法虽然可以舍弃部分劣解空间， 本质上还是一种枚举法。由于算法本身的局限性，在很多问题上还无法达到高 精度和高效率。在现代优化算法的基础上，对搜索空间进行选择淘汰或压缩的 优化方法，正凭借其高效、快速的优点日益受到人们的重视。 实现生产过程的最优化，对提高生产效率与效益、节省资源具有重要的作 用。同时优化方法的理论研究对改进算法性能、拓宽算法应用领域、完善算法 体系同样具有重要作用因此，优化理论与算法的研究是一个同时具有理论意 义和应用价值的重要课题。 1 2 优化模型与优化算法 1 2 1 优化模型 解决优化问题的主要手段就是建立数学模型，求解最优策略。目前优化领 域中主要采用的模型还是数学规划模型，用数学公式加以表达： r a 饨s i n ， s t g ( x ) 其中s 是解域，是价值函数，g 是约束条件集合。如果和g 都是线性函 数，则该模型为线性规划( l i n e a rp r o g r a m m i n g ) 模型，否则就是非线性规划 ( n o n l i n e a rp r o g r a m m i n g ) 模型。如果没有g ) 的限制即为无约束优化模型，否则 为有约束优化模型。如果x 必须是整数，则为整数规划( i n t e g e rp r o g r a m m i n g ) 模 型，如果要求部分工是整数，则为混合整数规划( m i x e di n t e g e rp r o g r a m m i n g ) 模 型。进一步细分又可以分为混合整数线性规划( m i l p ) 和混合整数非线性规划 ( m i n l p ) 。 1 2 2 优化算法 上面对优化算法已经有了初步的解释，本节详细概括优化算法的类型。就 优化机制与行为而分，目前实际寻优过程中常用的优化算法主要可分为：经典 算法，构造型算法改进型算法、基于系统动态演化的算法和混合型算法等。 第2 页 山东大学硕士学位论文 1 经典算法包括线性规划、动态规划、整数规划和分枝定界等传统运筹学 中的算法，其算法的计算复杂性一般很大，只适于求解小规模问题，在复杂优 化问题中往往不实用。 2 构造型算法用构造的方法快速建立问题的解。通常算法的优化质量差， 难以满足工程需要譬如，调度问题中的典型构造方法有j o h n s o n 法、p a l m e r 法、g u p t a 法、c d s 法、d a u n e n b r i n g 的快速接近法、n e h 法等 3 改进型算法，或称邻域搜索算法，即从任意一个解出发，对其邻域的不 断搜索和对当前解的替换来实现优化根据搜索行为，它又可分为局部搜索法 和指导性搜索法： 局部搜索法：以局部优化策略在当前解的邻域中按照贪婪原则搜索，如只 接受优于当前解的状态作为下一个当前解的爬山法；接受当前解邻域中的最好 解作为下一个当前解的最陡下降法等。 指导性搜索法：利用一些指导规则来指导整个解空间中对全局优良解的探 索，如模拟退火算法( s a ) ，遗传算法( g a ) ，进化规划( e p ) ，进化策略( e s ) ，禁忌 搜索口s ) ，蚁群算法( a c a ) 等 4 基于系统动态演化的方法将优化过程转化为系统动态的演化过程，应用 系统动态的演化来实现优化，如神经网络和混沌搜索等 5 混合型算法针对具体优化问题，将上述各种算法进行交叉、融合、组合 而形成的各类杂交算法，这也是本课题着重研究的问题。 优化算法当然还可以从别的角度进行分类，如确定型算法和不确定型算法， 局部优化算法和全局优化算法等。 1 2 2 1 局部优化算法 局部搜索算法是基于贪婪思想利用邻域函数进行搜索的，邻域函数是优化 算法中的一个重要概念，其作用就是指导如何由一个( 组) 解来产生一个( 组) 新的 解邻域函数的设计往往依赖于问题的特性和解的表达方式( 编码) 它通常可描 述为：从一个初始解出发，利用邻域函数持续地在当前解的邻域中搜索比它好 的解，若能够找到如此的解，就使之成为新的当前解，然后重复上述过程，否 第3 页 山东大学硕士学位论文 则结束搜索过程，并以当前解作为最终解可见，局部搜索算法尽管具有通用 易实现的特点，但搜索性能完全依赖于邻域函数和初始解，邻域函数设计不当 或初值选取不合适则算法最终的性能将会很差同时，贪婪思想无疑将使算法 丧失全局优化的能力，也即算法在搜索过程中无法避免陷入局部极小。因此， 若不在搜索策略上进行改进，那么要实现全局优化，局部搜索算法采用的邻域 函数必须是“完全的”。即邻域函数将导致解的完全枚举。而这在大多数情况下 是无法实现的，而且穷举的方法对于大规模问题在搜索时间上是不允许的。典 型的局部优化算法主要有：某些运筹学方法【3 】( 最速下降法、n e w t o n 法、共轭方 向法等) ，m o n t ec a r l o 4 方法，禁忌搜索算法【1 7 , 1 8 1 等。 1 2 2 2 全局优化算法 鉴于局部搜索算法的上述缺点，作为全局指导性搜索算法的智能优化算法， 从不同的角度利用不同的搜索机制和策略消除局部搜索算法的局限性。在许多 工程领域中，求解全局优化问题是一项非常吸引人的课题。目前，求解全局优 化问题已有许多不同的算法，这些方法也可以分成确定型和随机型的，前者包 括一些运筹学方法如分支定界法p j 、序贯二次规划等，后者包括均匀分布搜索 法，模拟退火算法1 6 1 ，粒子群算法f - 9 、蚁群算法，遗传算法 1 0 - 1 4 1 、演化策略1 1 5 , 1 6 】、 演化规划等当目标函数具有为数不多的极点，确定型方法表现出计算效率高 的优点，但同时暴露出算法的复杂性，对目标函数性质要求高，不可靠等缺点。 而随机型方法有较强的稳健性，算法容易实现，但常表现出计算效率低的缺陷。 遗传算法，作为全局优化算法的典型代表，因其简单通用、鲁棒性强、适 于并行处理，在过去2 0 年中己广泛应用于计算机科学、优化调度、运输问题、 组合优化、复杂函数系统优化、机器学习、系统识别、神经网络设计等领域。 但是它也表现出作为全局优化算法的普遍的弊病：精细局部寻优能力较差；早 熟收敛，爬山特性差，而且在进化后期搜索效率较低。因此，目前很多学者致 力于解决全局优化算法的局部寻优能力，以及提高后期搜索性能的问题，其中 之一就是吸纳全局优化算法和局部优化算法的优点，构造既有全局搜索性能， 同时利用局部搜索算法的高效和强引导性达到高性能的混合优化算法。 第4 页 山东大学硕士学位论文 1 3 空间划分与空间收缩 随着所求解问题规模的扩大和复杂度的提高，由于算法本身的缺陷，使某 些问题的收敛速度非常慢而空间搜索算法，将解空间的压缩机制运用到最优 化方法上来，大大提高了问题的收敛速度。空间划分与收缩相辅相成，在搜索 中经常是同时使用。 目前很多优化算法中融入了空问划分和空间收缩的思想，一类空间搜索算 法是空间收缩算法，它需要充分的信息来定位最优解，并以此为依据不断缩小 解空间范围，从而实现搜索空间向最优解收缩目前大多数的空间搜索算法是 通过对空间的划分和淘汰实现搜索，因此实际上也是一类分支定界算法。它将 整个搜索空间作为初始空间，然后将初始空间划分为由若干子空间组成的空间 集，最后通过在各个子空间内选取测试点来确定保留与淘汰的空间。这种算法 要求解空间有很好的局域性，否则就需要用较多的子空间和测试点，导致问题 规模增大 传统优化算法中，分支定界法，基本思想是将不易求解的问题逐步分裂为 子问题，在求解过程中利用较小工作量给子问题“定界”或得出其最优解，以 此删除一些子问题，从而只需求解较少的子问题以求得最优解，可以求解混合 整数线性规划问题；区间算法，基本思想是将分支定界方法和m o o r e - s k e l b o e 算法相结合，它的一般过程可概括为五个基本步骤，即：定界、分支、终止、 删除和分裂，突出优点是能在给定精度内求出问题的全部全局极小点，能解决 连续函数的优化问题。现代优化算法中，有很多空间搜索算法，也是通过空间 的划分和淘汰实现搜索。m i h d e 算法【19 】已经成功解决了很多m i n l p 问题，但 对有些问题得到的解的质量不高。g t 算法1 2 0 1 是一种快速而有效的空间搜索算 法，它首先将解空间划分为若干子空间，然后在每个子空间内分别选取若干个 测试点，通过测试点的好坏来确定保留或淘汰的空间在局域性不好的搜索空 间中，如果这种算法保留的空间和测试点数不足够大，则很难找到全局最优点。 a c s s o s l 2 1 1 也是一种快速的空间收缩的算法，但它要求适应值函数的搜索空间 具有连续性和凸性，对于不满足这些条件的问题便无能为力 基于空间收缩的并行演化算法【2 2 1 通过分布信息定位最优解的可能分布， 逐步缩小求解空间收缩空间时由于采用了由精英个体决定下次搜索空间的方 第5 页 山东大学硕士学位论文 法，因此算法具有更高的搜索效率，应用范围也更广在由精英个体确定空间 的思想启发之下，又提出一种新的空间划分和空间收缩算法【2 4 捌，该算法将空 间划分和空间收缩同时完成后，得到多个收缩后的子空间由于模型在空间中 都是由各个峰和谷组成，因此可以令算法只在峰或者谷附近搜索而避免在其他 非优解区域的搜索，从而加速算法收敛采用的方法是在第一次不完全演化结 束后，将得到的精英解根据其在空间的位置及适应度值选择聚类中心，进而将 全部精英解都划分到最近的类中，由聚类后的精英解确定出优化问题的峰或者 谷，进而将空间划分并且收缩为多个子空间，每个子空间内至少有一个局部最 优解。然后在这些子空间中，再根据收缩标准来决定是继续进行收缩还是直接 进入完全演化。这两种方法对模型没有特殊要求，可以解决线性，非线性，混 合整数等模型，但是前者对空间进行收缩后，很有可能丢掉全局最优解，后者 怎样选择聚类中心，以及k 均值聚类本身的精度都制约了空间的划分和收缩的 准确性。 1 4 论文主要研究内容 本文在研究优化算法的基础上，将空间划分与收缩的思想结合进来，首先 提出一种基于网格划分的混合搜索算法，并对其在生产调度模型中的应用进行 了研究。其次改进了一维和多维区间优化算法。本文的具体安排如下； 1 第一章是绪论，简要介绍了论文的写作背景、优化模型、各种优化 算法、空间划分与收缩，以及论文的主要内容。 2 第二章是优化算法的理论基础，重点介绍了遗传算法、禁忌搜索算 法和区间算法。 3 第三章提出了一种基于网格划分的混合搜索算法，该算法将空间划 分与收缩的思想和搜索算法相结合，仿真试验表明它提高了搜索算 法的效率和效果，并将该算法应用在生产调度模型中，取得了良好 的效果 4 第四章讨论区间优化算法，针对一维情况改进了区间分支定界法， 二维情况提出了混合区间演化算法并通过仿真检验了算法的性 能。 5 第五章是结束语，对全文进行了总结，并对优化算法的发展前景进 行了展望。 第6 页 山东大学硕士学位论文 第二章优化算法 2 1 全局搜索算法 2 1 1 概况 目前有很多搜索算法的全局性能非常好，可以视作全局搜索算法。全局搜 索算法从不同的角度利用不同的搜索机制和策略消除局部搜索算法的局限性 在许多工程领域中，求解全局优化问题是一项非常吸引人的课题。 近3 0 年来，出现了一系列新型的全局优化搜索算法。这些算法主要是通过 模拟自然领域中具有某种优化特征的群体演化过程而建立起来的。其中比较典 型的有遗传算法、模拟退火算法和蚁群算法等。遗传算法模拟了生物体内染色 体群体的遗传进化过程，模拟退火算法模拟了固体退火过程中系统内原子群体 趋向能量最低的基态的过程，蚁群算法则模拟了蚁群通过个体之间的信息交流 与相互协作找至h 蚁穴到食物源的最短路径的过程。这些算法成功地解决了许多 复杂的优化问题。算法的构造方法表明，模拟具有某种优化特征的群体演化过 程是建立全局搜索算法的一条有效途径。在全局搜索算法中，最具代表性的是 遗传算法。 2 1 2 遗传算法 遗传算法( g a g e n e t i ca l g o r i t h m ) 是模拟达尔文的遗传选择和自然淘汰的生 物进化过程的计算模拟，由美 m i c h i g a n 大学的j h o l l a n d 教授于1 9 7 5 年首次提 出。他提出位串编码，将串赋予特定的信息，并将“适者生存”的进化理论引 入串结构，在串之间进行有组织但随机的信息交换。通过遗传中的选择、交叉 和变异等操作，使得串中的适应度值高的部分被保留，并在串之间进行组合， 淘汰适应度低的串或串的一部分，从而不断产生出新的更好的个体，子个体中 包含有父个体的大量信息，但在总体上胜过父个体，从而使得种群向前进化发 展，不断接近或达到问题的最优解，是模拟生物进化过程的计算模型遗传算 法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理 以及应用范围广等显著特点，得到了广泛注意。 第7 页 山东大学硕士学位论文 2 1 2 1 基本概念 遗传算法是具有“生成十检测”( g e n e r a t ea n dt e s t ) 的迭代过程的搜索算法。 遗传算法是一种群体型操作，该操作以群体中的所有个体为对象，选择 ( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 、变异( m u t a t i o n ) 是遗传算法的三个主要操作算子， 它们构成了所谓的遗传操作( g e n e t i co p e r a t i o n ) ，使遗传算法具有了其他传统方法 所没有的特性。 由于遗传算法是自然遗传学和计算机科学相互交叉、相互渗透的产物，因 此借鉴了许多自然遗传学中的术语 个体( i n d i v i d u a l s ) ：遗传算法处理的基本单位，是通过基匮l ( g e n e ) 编r 冯( c o d i n g ) 的，每一位带有特定信息的染色体( c h r o m o s o m e ) 。通常用一维串结构的数据结 构来表现。 种群( p o p u l a t i o n ) ：一定数量的个体的组成种群中个体的数目称为种群规 模( p o p u l a t i o ns i z e ) 。 适应度函数( f i t n e s sf u n c t i o n ) ：每个个体对环境的适应程度叫做适应度。对 于优化问题，适应度函数通常就是目标函数或目标函数的变形。遗传算法对适 应度函数的要求较低，只要是可以加以比较的非负函数。 编码( c o d i n g ) 、解码( d e c o d i n g ) ：把搜索空间中的参数或解转换成遗传空间中 的染色体或个体，称为编码操作，是从问题的状态空间到遗传算法的位串空间 的映射。反之，则成为解码操作。编码和解码是遗传算法中两个必须包含的数 据转换操作。 2 12 2 基本原理 2 1 2 2 1 五个基本要素 遗传算法具有5 个控制要素：编码机制，初始种群的设定，适应度函数的设 定，遗传算子，控制参数的设定。 1 编码机制 编码机制是遗传算法的基础。通常遗传算法不直接处理问题的状态空间的 数据，而是将各种实际问题变换为与具体问题无关的串个体( 染色体) 。对染色体 第8 页 山东大学硕士学位论文 串的遗传操作只与遗传算法理论、技术有关，而与具体实际问题无关这一特 点大大增强了遗传算法的通用性当应用问题变化时，可以只改变适应度函数， 而无需改变其他操作。加强了代码的通用性最常用的编码是二进制串结构编 码 2 初始种群的设定 遗传算法的处理流程中，编码设计之后的任务是初始种群的设定，并以此 为起点一代代的进化直到满足某种进化中止规则而中止常用的设定是采用随 机化的方法产生初始种群。 3 适应度函数的设定 标准遗传算法在搜索过程中，基本不需要采用外部信息，仅仅以适应度函 数为依据。个体的适应度函数值越大，该个体的生存能力越强。在简单优化中， 通常可以直接利用目标函数作为适应度函数 4 遗传算子 优胜劣汰是g a 的基本思想，通过选择、交叉、变异等遗传算子中得以体现。 选择( s e l e c t i o n ) ：决定以定的概率从种群中选择若干个体的操作。般而 言，选择的过程是一种基于适应度的优胜劣汰的过程。 交叉( c r o s s o v e r ) ：两个染色体的某一位置处被切断，其前后两串分别交叉组 合形成两个新的染色体。又称为基因重组( r e c o m b i n a t i o n ) ，俗称“杂交”。 变异( m u t a t i o n ) ：在染色体进行复制的过程中，以很小的概率在某些位置上 产生“差错”，从而产生新的染色体。 5 控制参数的设定 控制参数主要有：种群规模、迭代次数、交叉概率、变异概率等。标准遗 传算法采用实现设定的固定值。一般是：采用二进制编码，用轮盘赌选择法选 择个体，交叉操作在父代配对时采用随机方法，实行单点交叉，用随机取反法 变异，生成子代个体，种群内允许相同的个体出现。 由以上论述可知。遗传算法从任一设定的初始种群出发，采用选择操作， 把优秀的个体( 适应度值大的个体) 作为父代( 实现优胜劣汰) ，通过交叉( 在产生新 的个体的同时，实现了优秀个体间的信息交换) ，变异( 产生新的个体，保持种群 的多样性，避免算法的早熟) 等操作，使种群代一代地进化到解空间中的最优 解附近，甚至收敛到最优解 第9 页 山东大学硕士学位论文 2 1 2 2 2 基本流程 标准遗传算法( s g a ) 的主要步骤描述如下： ( 1 ) 随机产生一组初始个体构成初始种群并采用二进制编码，个体跃度、种 群规模、交叉概率、变异概率为固定值，并评价每个体的适应度值( f i t n e s sv a l u e ) ； ( 2 ) 判断算法收敛准则是是否满足，着满足则输出搜索结果，否则执行以下 步骤； ( 3 ) 根据适应度值大小以一定方式执行复制操作； ( 4 ) 按事先设定的概率分别执行交叉，变异操作； ( 5 ) 返回步骤( 2 ) 2 1 2 3 主要特点 1 优点： ( 1 ) 多点搜索，较强的全局搜索能力。遗传算法是采用同时处理群体中多个个体 的方法，即同时利用搜索空间中多个解的信息，减少了遗传算法陷于局部最 优解的风险。遗传算法的许多操作都是从寻找全局最优解的角度出发设计 的，例如初始点是多个，即使其中有一个初始点选得很好，也不一定能很快 向该初始点收敛。同时，这也使遗传算法十分易于并行化 ( 2 ) 遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索过 程朝着搜索空间的更优化的解区域移动。 ( 3 ) 常规遗传算法基本上不用搜索空间的知识，而仅用适应度函数值来评估个体， 并在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且定 义域可任意设定，对该函数的唯一要求是对于输入可计算出加以比较的正的 输出。 ( 4 ) 遗传算法的处理对象通常不是参数本身，而是对参数集进行了编码的个体。 此编码操作，使得遗传算法可直接对结构对象进行操作。 ( 5 ) 由于g a 的结构是开放式的，与问题无关，而且g a 具有良好的全局寻优能 力，所以容易和其它算法综合 2 缺点 遗传算法在各种问题的求解与应用中展现了其特点和魅力，同时也暴露出 第l o 页 山东大学硕士学位论文 它在理论和应用上的诸多不足和缺陷比如相对鲜明的生物基础，其数学基础 显得极为薄弱，尤其是缺乏深刻且具普遍意义的理论分析。正因为如此，遗传 算法现阶段的研究重点又回到了基础理论的开拓与深化，以及更通用、更有效 的操作技术和方法上的研究。 ( 1 ) 遗传算法虽然有很强的全局寻优能力，但其精细局部寻优能力却较差 ( 2 ) 当搜索空间较大时，遗传算法的搜索效率较低。 ( 3 ) 早熟收敛，爬山特性差，而且在进化后期搜索效率较低 ( 4 ) 在遗传优化过程中，每代总要维持一定规模的群体，若群体规模太小，含有 的信息量也少，不能使算法得到充分发挥，若群体规模大，包含的信息量也 大，但计算次数呈非多项式时间增加，因而限制了算法的使用。 ( 5 ) 另外一个显著特点就是可调参数多，不同的参数配霞将对g a 的优化效果带 来显著的影响。特别是随着g a 的不断改进，参数也随之增加，使得参数设 计日益成为影响g a 性能的一个关键问题。 ( 6 ) 常规遗传算法基本上不用搜索空间的知识，对优化问题的目标函数和约束条 件没有特别要求，因此优化问题的特别性质没有被很好利用。 ( 7 ) 常规遗传算法偏好使用离散变量尤其是01 变量作为基因，这可能会导致 计算上出现较大困难。 ( 8 ) 遗传算法目前的研究主要是以仿生和实验为主，有效性也主要是通过实验以 及实际应用的效果得以验证的。其寻优机制还没有彻底揭示，今后还期待这 种算法的理论基础在现有的模式定理、积木块假设等理论的基础上有大的发 展。 2 2 局部搜索算法 2 2 1 概况 在绪论中提到过，局部搜索算法是基于贪婪思想利用邻域函数进行搜索的， 邻域函数是优化中的一个重要概念，其作用就是指导如何由一个( 组) 解来产生一 个( 组) 新的解局部搜索算法搜索性能完全依赖于邻域函数和初始解，邻域函数 设计不当或初值选取不合适会导致算法的最终性能很差。同时，贪婪思想无疑 将使算法丧失全局优化的能力，也即算法在搜索过程中无法避免陷入局部极小 第1 l 页 山东大学硕士学位论文 局部搜索算法虽然具有这样一些缺点，但是它也有全局搜索算法不具备的一些 优点，首先它具有通用易实现的特点，算法的时间和空间复杂性一般较小，另 外，局部搜索算法的局部寻优能力比全局搜索算法要强大得多，一旦初始解选 择合理，应用局部搜索算法得到的最优解的质量要好于全局搜索算法。 本文着重描述一种典型的局部搜索算法一禁忌搜索算法 2 2 2 禁忌搜索 禁忌搜索( t a b us e a r c h 或t a b o os e a r c h 。简称t s ) 的思想最早是由g l o v e r 在 1 9 8 6 年提出的它是对局部邻域搜索的一种扩展，是对人类智力过程的一种模 拟，这种算法被称为禁忌搜索启发式算法。这种算法戏剧性的改变了我们求解 一些实际工程问题的能力，可以帮助我们解决一大批在应用科学，商业、工程 领域遇到的工程优化问题。 禁忌搜索算法是继模拟退火算法之后出现的又一种十分有效的局部搜索算 法，是四大现代启发式算法之一。禁忌搜索算法与模拟退火一样也是一种“爬 山”算法，前者模拟了一种智力过程，而后者则模拟了固体退火这一物理过程。 禁忌搜索算法已在诸多组合优化领域显示出强大的寻优能力，并以其较高的求 解质量和效率得到人们越来越多的青睐。 2 2 2 1 基本思想 禁忌( t a b uo rt a b o o ) 这个词来自于t o n g a n ( 玻利尼西亚的一种语言) ，被 t o n g a n 岛的土著居民用来指那些神圣而不可侵犯的东西。根据韦伯斯特字典， 这个词现在也意味着“作为一种保护性措施，被社会风俗强行禁止的行为”或 是“由于构成危险而禁止的”事物。这个单词注重实效的感觉非常符合禁忌搜 索的题目。在禁忌搜索这种情况下要避免落入迂回搜索的危险，包括落入陷阱 而无法跳出的情况。另一方面，从更广阔的社会背景来看，这种保护性限制在 必要情况下是可以被替代的同样，在有更好替代方法的情况下，禁忌搜索的 禁忌规则可以彼蔑视。然而，与传统方法最重要的联系来自于这个事实，即一 般来说所持有的禁忌是通过社会记忆来传播的，必然随着时间的流逝而修改 这就形成了禁忌搜索与“t a b u ”本意的基本连接禁忌搜索中被禁止的元素依 第1 2 页 山东大学硕士学位论文 靠不断演变的存储来接受它们的状态，这种存储允许元素禁忌状态根据时间和 环境来变化 简单t s 算法的基本思想是：给定一个当前解( 初始解) 和一个邻域，然后在 当前解的邻域中确定若干候选解：若最佳侯选解对应的目标值优于当前最优解 状态，则忽视其禁忌特性，用其代替当前解和最优解状态，并将相应的对象加 入禁忌表( 用于记录候选解禁忌属性的表) ，同时修改禁忌表中各对象的任期： 若不存在上述候选解，则在候选解中选择未被禁忌的最佳状态为新的当前解， 而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各 对象的任期；如此重复上述搜索过程直至满足停止准则。 2 2 。2 1 1 特点 1 记忆的使用 禁忌搜索中引入的记忆涉及到四个基本尺度，并通过它们的引导搜索，它 们分别为崭新( r e c e n c y ) ，频率( f r e q u e n c y ) 、品质( q u a l i t y ) 、和影响 ( i n f l u e n c e ) 。 基于崭新的记忆和基于频率的记忆相互补充。品质尺度指的是区别搜索过 程中被访问过的解的品质的能力。在寻优过程中，它成为基于激励学习的基础， 激励寻优向好的区域移动，同时惩罚并阻碍其向不理想的方向发展。影响尺度 是指，在搜索过程中所作出的选择对品质和结构的影响( 在某种意义上，品质可 看作影响的一种特殊形式) 记录对特定解所做出的选择的影响，成为种另一 层次的学习对比一下可看出，在分支定界法中，对于决策树的给定节点，分 离规则是预先规定的，一旦选择了分支方向，则算法自始至终分支方向保持不 变由上可知，基于记忆的影响的评估与开发要比在树中搜索中应用要灵活， 这是t s 框架的一个重要特征。 t s 中应用的记忆既是明确的又是属性的。明确记忆是记录完整的解，尤其 那些搜索过程中遇到的好解，它的范围囊括了那些好解的颇具吸引力但尚未开 发的邻域。此外，t s 算法使用属性记忆来引导搜索，这些属性即解的移动( 从一 个解移动到另一个解) 2 集中性( i n t e n s i f i c a t i o n ) 和广泛性( d i v e r s i f i c a t i o n ) 第1 3 页 山东大学硕士学位论文 集中搜索策略是以改变选择规则为基础，进而激发曾发现的较好解的特征 和移动组合，它可能返回到有“吸引力”的区域进行彻底全面的搜索。由于精 华解都被记录下来以便搜索它的邻域，所以明确记忆与集中性搜索策略有着密 切的联系 3 记忆和禁忌类 t s 的另一个特点是短期记忆和长期记忆。每种记忆类型都有其自身的策略， 但这两种类型的记忆执行同样的行为，即改变当