（运筹学与控制论专业论文）遗传算法在分配问题中的应用.pdf

摘要进化算法是模拟自然界生物进化过程而形成的一种现代优化算法。作为一种有效的随机搜索算法，和传统优化方法相比，进化算法对目标函数的解析性质要求不高，不需要导数信息等，具有易于实施和隐式并行性。其独特的性能己在众多领域内获得了成功的应用，着重用于解决复杂的、大规模的、非线性、不可微的优化问题。首先，对民航机场机位分配问题，在h d i n g 等人提出的模型的基础上给出了更符合实际的民航机场机位分配问题( a g a p ) 的数学模型。并且设计了一种有效的遗传算法，包括遗传算法的编码及初始种群生成算法、相应的杂交和变异算子，该算法的杂交、变异都能生成可行解，不需要对解进行修正，减少了运算量，并且这种变异算子不仅保证了算法具有较好的全局搜索能力而且能灵活有效地处理约束条件，使得算法迅速有效地找到全局最优解。第二，对于超市货架空间分配问题，提出了一个遗传算法和模拟退火算法及一个局部搜索算法混合的算法。首先，设计了产生初始种群的一个有效方法。第二，设计了一种比较直观的编码方法，我们用一个矩阵作为一种货架分配方案，矩阵的第f 行第k 列的元素表示了第f 个产品分配给第k 个货架的数量。第三，设计了与编码相应的杂交和变异算子，该杂交算子具有局部搜索的能力，变异算子和模拟退火算法以及局部搜索算法相互结合，从不同的区域对整个解空间进行有效搜索，提高了算法的搜索效率和解的质量。第三，对于超市货架空间分配问题，本文在前人所作研究的基础上，建立了一个多目标优化模型，并且针对该模型设计一种遗传算法和局部搜索算法结合的混合算法。首先我们针对问题特点设计了三种局部调节算法，这三种局部调节算法从不同的方向对解进行逐步改善。在遗传算法中融入了这三种局部调节算法，使得遗传算法的局部搜索能力得到了极大提高。最后，经过大量的数据仿真试验，验证了本文所述算法的正确性和有效性。关键词：机场机位分配货架分配进化算法混合遗传算法a b s t r a c te v o l u t i o n a r ya l g o r i t h m so r en e wk i n d so f m o d e mo p t i m i z a t i o na l g o r i t h m st h a ta r ei n s p i r e db yp r i n c i p l eo fn a t u r ee v o l u t i o n c o m p a r e dw i t ht h et r a d i t i o n a lo p t i m i z a t i o na l g o r i t h m , t h ee v o l u t i o n a r ya l g o r i t h m sr e q u i r el i t t l ek n o w l e d g ea b o u tp r o b l e m sc o n s i d e r e d , a n dt h e ya r ce a s yt oi m p l e m e n ta n da r eo fi n h e r e n t l yp a r a l l e ls e a r c ha b i l i t y t h e r e f o r e ，t h ee v o l u t i o n a r ya l g o r i t h m sh a v eb e e ns u c c e s s f u l l ya p p l i e dt ov a r i o u sf i e l d s ，e s p e c i a l l yt os o m ec o m p l e x ，l a r g es c a l e ，n o n l i n e a ra n dn o n - d i f f e r e n t i a b l eo p t i m i z a t i o np r o b l e m s f i r s t l y , an e wm o d e lf o ra i r p o r tg a t ea s s i g n m e n tp r o b l e m ( a g a p ) i sd e v e l o p e db a s e do nt h em o d e lw h i c hi sp r o p o s e db yh d i n g ，w h e r ee a c ho ff l i g h t sc a no n l yb ea s s i g n e dt os o m eg a t e s ，a n dt h eo b j e c t i v ei st om i n i m i z et h ed i s t a n c et h ep a s s e n g e r sw a l ko rt h ec o n n e c t i o nt i m e s t os o l v et h i sp r o b l e m , ag e n e t i ca l g o r i t h mi sp r o p o s e db a s e do n an e we n c o d i n gs c h e m ec a l l e d ( u s ea n o t h e rd a m ei n s t e a do f a g a p ) ，an o v e lc r o s s o v e ra n dm u t a t i o no p e r a t o r s t h es o l u t i o n sg e n e r a t e db yt h ep r o p o s e dc r o s s o v e ra n dm u t a t i o no p e r a t o r sa g ea l w a y sf e a s i b l e ，a n dt h em u t a t i o no p e r a t o rn o to n l yh a ss t r o n ge x p l o r a t i o na b i l i t y , b u ta l s oc a l lh a n d l et h ec o n s t r a i n t se f f e c t i v e l y m o r e o v e r , t h ec o n v e r g e n c eo ft h ep r o p o s e da l g o r i t h mi sp r o v e d t h es i m u l a t i o n si n d i c a t et h ep r o p o s e dg e n e t i ca l g o r i t h mc a nf i n do p t i m a ls o l u t i o nq u i c k l y s e c o n d l y , ah y b r i dg e n e t i ca l g o r i t h mf o rt h es h e l fs p a c ea l l o c a t i o ni sp r e s e n t e db a s e do ny a n g m o d e lw h i c h w a sp r o p o s e di n1 9 9 9 ，w h e r et h ea l g o r i t h mi n t e g r a t e dt h es i m u l a t e c la n n e a l i n ga n dal o c a lr e s e a r c hm e t h o di n t oag e n e t i ca l g o r i t h m i nt h ee n c o d i n g , am a t r i xi sa d o p t e dt or e p r e s e n tas o l u t i o n “e ，as p a c e - a l l o c a t i o ns c h e m e ) ，w h e r et h ee l e m e n to ft h e i t h1 0 wa n dt h ek t hc o l u m nr e p r e s e n t st h ea m o u n to fp r o d u c tfo ns h e l fk t h e nc r o s s o v e ra n dm u t a t i o no p e r a t o r sa r ed e s i g n e d m o r e o v e r ,at h r e s h o l dv a l u e b a s e do ns t r u c t u r eo fp h e n o t y p ea n di t sf i t n e s si sd e f i n e dt og e n e r a t eg o o de n o u g hi n i t i a lp o p u l a t i o n c o m p a r et oo t h e rh e u r i s t i cm e t h o d s , t h en u m e r i c a le x p e r i m e n t sd e m o n s t r a t et h ep r o p o s e da l g o r i t h mi sv e r ye f f i c i e n ti ns e a r c h i n gt h es o l u t i o ns p a c ea n dh a sar a p i ds p e e d t h i r d l y , ah i - o b j e c t i v em o d e lf o rt h es h e l fs p a c ea l l o c a t i o np r o b l e mi sp r o p o s e db a s e do ni m p r o v i n gt h ee x i s t i n gw o r k , a n dah y b r i dg e n e t i ca l g o r i t h mf o rt h i sm o d e li sd e s i g n e d m o r e o v e r , t h r e el o c a lm e t h o d sw h i c hc a ni m p r o v et h ef e a s i b l es o l u t i o nf r o md i f f e r e n td i r e c t i o n sa r ed e s i g n e da c c o r d i n gt ot h es p e c i f i cf e a t u r e so ft h ep r o b l e m , a n dt h e ya r ec o m b i n e di n t ot h eg e n e t i ca l g o r i t h mt oi n c r e a s ei t ss e a r c ha b i l i t y an u m b e ro fs i m u l a t e dr e s u l t ss h o wt h ee f f i c i e n c yo f t h ep r o p o s e da l g o r i t h m s k e y w o r d s ：a i r p o r tg a t ea s s i g n m e n ts h e l fs p a c ea h o c a t i o ne v o l u t i o n a r ya l g o r i t h mh y b r i dg e n e t i ca l g o r i t h m创新性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：臻缸盂珥日期塑掣：笙关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)日期型z ：z ：堑同期弛! 竺第一章绪论第一章绪论1 1 引言本文主要是用进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 【l l 【2 1 和进化算法与其它优化算法的混合算法来有效地解决一些分配问题，主要包括民航机场机位分配问题和超市货架分配问题。2 0 世纪8 0 年代以来，随着人工智能、仿生学的兴起，人们从不同的角度出发对生物系统及其行为特征进行了模拟，设计出了如进化算法、免疫算法、蚁群算法以及粒子群算法等通用性较强的智能优化方法和模式，这些算法及其理论对现代科技发展产生了重大的影响，并且还在继续推动着科学技术的发展。其中进化算法是在对自然界生物进化机制的模拟中形成的一种自适应的全局优化概率搜索算法，它主要有以下几大分支：遗传算法( g e n e t i ca l g o r i t h m , g a ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 、进化策略( e v o l u t i o n a r ys t r a t e g y ，e s )和遗传程序设计( g e n e t i cp r o g r a m m i n g ，g p ) ，当然还存在若干将上述算法的各种特点加以结合而形成的混合算法。作为强有力且应用广泛的随机搜索和优化方法，遗传算法可以说是当今影响最广泛的进化计算方法之一。在过去的几年中，遗传算法界将更多的注意力放在工业工程领域的优化问题上，并由此产生了一批新的研究和应用。本文对民航机场机位分配问题在以前研究者的研究基础上对该问题的数学模型进行了修正，使之与实际更接近，并利用了进化算法的众多优点，设计了一种新的与问题一致的编码方法及初始种群生成算法、相应的杂交和变异算子，从而有效的解决了该问题，且该算法的杂交、变异都能生成可行解，不需要对解进行修正，有效地解决处理了约束条件，使得进化过程一直在可行域内搜索。遗传算法由于其运算简单和解决问题的有效能力而被广泛应用到众多的领域。理论上已证明，遗传算法能从概率的意义上以随机的方式寻求到问题的最优解。但另一方面，应用实践表明，在遗传算法的应用中也会出现一些不尽人意的问题，这些问题中最主要的是它容易产生早熟现象、局部寻优能力较差等。另外，遗传算法也无法避免可能多次搜索同一个可行解。另一方面，梯度法、爬山法、模拟退火算法、列表寻优法、禁忌搜索算法和一些含有与问题知识相关的启发式局部搜索算法却具有很强的局部搜索能力。所以，在遗传算法中融入这些局部搜索能力很强的算法，构成一种混合遗传算法( h y b r i dg e n e t i ca l g o r i t h m ) 以提高遗传算法运行效率和求解质量成为近几年研究者的热点 3 1 1 4 5 1 1 6 1 。本文针对超市货架分配问题设计了一个自适应的混合遗传算法，提高了遗传算法的运行效率，有效2遗传算法在分配问题中的应用地解决处理了实际问题的约束条件，找到了问题的近似全局最优解。1 2 优化问题的研究概况优化技术是- n 应用性很强的年轻学科，它研究某些数学上定义的问题的最优解，即对于给出的实际问题，从众多的方案中选出最优方案。虽然最优化可以追溯到十分古老的极值问题，然而，它成为一门独立的学科是在2 0 世纪4 0 年代末。现在，随着线性规划、非线性规划、随机规划、非光滑规划、多目标规划、整数规划等各种最优化问题的理论研究的迅速发展，新方法的不断出现，以及计算机技术的发展，优化技术日益得到重视并在诸多工程领域被迅速推广和广泛应用，例如计算机工程、人工智能、模式识别、系统工程、生产调度等等。在实际的生产过程中，运用最优化技术，使各项指标达到最优，有利于提高生产效率，节省资源，这使得最优化理论有了实际意义。因此，优化方法的理论研究及改进算法性能、拓宽算法应用领域、完善算法体系等方面的研究是具有理论意义和实用价值的。1 - 2 1 优化问题的描述最优化方法涉及的工程领域很广，问题种类繁多，总的可以分为连续变量的优化问题和离散变量的优化问题。最优化问题的一般形式为m i n f ( x )s t x e x其中工r ”是决策变量，o ) 为目标函数( o b j e c t i v ef u n e d o n ) ，x c r ”为约束集或可行域( f e a s i b l er e g i o n ) ，可行域内的点称为可行解( f e a s i b l es o l u t i o n ) ；将可行域中使目标函数达到最小的解称为最优解 0 ) ，每个箱子有重量限制( c 0 ) 。问题是寻找最优的将物品分配到箱子的方案，从而使得每个箱子中物品的重量之和不超过其限制，而实用的箱子数量最少。其中对于栉个箱子来说，重量国，和重量限制c 。是正实数( f ；1 , 2 ，栉) 。( 2 ) 背包问题( k n a p s a c kp r o b l e m ) ：背包问题已经被集中的研究【”，这个问题有以下几种变形：0 - 1 背包问题( 0 - 1k n a p s a c kp r o b l e m ) ：已知有一个背包，其承重的上限是w ，存在n 个不同的项目可以使用，每个项目_ ，具有重量国，和费用c ，。问题是如何寻找项目的最优子集从而在满足背包承重约束的基础上最大化总费用。费用、重量和承重是正整数。多选择背包问题( m u l t i p l e - c h o i c ek n a p s a c kp r o b l e m ) ：有一个承重有限的背包。将要放入背包的物品被分为相互排斥的若干类。每类中有若干不同的项目。问题是从每类中选择一个项目使得项目总重量在满足背包承重约束的前提下最小化费用。多约束背包问题( m u l t i e o n s t r a i n e dk n a p s a c kp r o b l e m ) ：是带有一组约束的背包问题。已知存在承重分别为w l ，w 2 ，的所个背包和刀个物品，每个物品的费用为c ，j = 1 , 2 ，撑。如果第，个物品放入第i 个容量为w ，的箱子，则设它在第i 个约束中的权重为一我们希望将尽量多的物品放入背包，在确保背包承重满足的前提下最大化总费用。背包问题还有界背包问题、无界背包问题等变形。1 2 3 现代优化算法简述所谓优化算法，其实就是一种搜索过程或规则，根据现有优化问题的特点，利用某种思想或机制，按照相应的某种途径和方法来得到满足现实要求的问题的解。现有的优化算法大致可以分为以下几类：( 1 ) 经典算法：包括线性规划和非线性规划的传统算法、动态规划的传统算法、整数规划的传统算法和分支定界法。它们或对目标函数的解析性质要求较4遗传算法在分配问题中的应用高，或计算复杂性很大，只适用于求解小规模的简单问题，很难适用于工程中出现的大规模问题。( 2 ) 构造型算法：通过对问题的分析，希望用构造的方法快速建立问题的解。通常这样的方法不是很有效，对于庞大复杂的问题，很难满足需要。比如调度问题中的典型构造方法有j o h n s o n 法、g u t p a 法、c d s 法、p a l m c ：r 法、d a u n e n b r i n g 的快速接近法等。( 3 ) 混合型算法：指根据不同问题的具体需要，利用上述各种算法的优点，克服其弊端，从结构或操作上混合而产生的各种算法。实践证明这种算法往往是快捷有效的。求解无约束优化问题的算法大致可分为确定性算法和随机算法两类：确定性算法：确定性算法往往对目标函数的解析性质要求比较高，要用到目标函数的梯度信息或者高阶导数信息，代表性的方法如l e 、，y 的隧道法【7 1 和g 它的填充函数法嗍等：( 1 ) 隧道算法：隧道算法的思想是从当前最好点出发，通过在该点建立一个隧道函数，希望能打通一条隧道，从而进入另一个深谷里，找到相应的具有下降方向的点，再通过局部搜索，找到新的深谷里的局部最小点。这样层层迭代，直到全局最优。( 2 ) 填充函数法：填充函数法也是基于当前最好点，根据该点建立一个相应的辅助函数，该函数能够填平当前最好点所在的深谷，帮助搜索跳出局部极小，转移到一个地势更低的深谷，获取该深谷的一个点，从该点重新搜索，希望能找到比当前点更好的点。该方法的关键在于如何去建立一个合适的填充函数。随机算法：随机方法对目标函数要求低，稳定性好，但收敛速度慢。代表性的方法有进化算法 1 1 【9 】、m o n c - c a r l o 随机实验法、模拟退火算法( s i m u l a t e da n n e a l i n g )l 埘( 1 ) m o n e - c a r l o 随机实验法：m o n e - c a r l o 随机实验法是按均匀分布在搜索空间随机产生大量的实验点，然后找出其在可行域中最好点作为最优解的一种随机近似方法。( 2 ) 模拟退火算法：模拟退火算法( s i m u l a t e da n n e a l i n g ) 【1 0 l 是基于固体冷却过程和一般组合优化问题之间相似的特点而产生的一种优化算法。固体物质退火的物理模型与随机过程的理论结合形成了模拟退火算法的基本思想。事实证明，对离散变量的组合优化问题和连续变量函数的极小化问题模拟退化算法都是有效可行的。第一章绪论5( 3 ) 进化算法：进化算法是基于生物进化论的杂交、变异和选择等原理而设计的一种新型优化算法。一求解约束优化问题的算法约束优化问题的求解方法众多，最常见最基本的是罚函数法。它把约束优化问题转化为无约束优化问题，再用无约束优化问题的方法去求解。和众多的方法比较，罚函数法可以说是一种相当有效、成功率较高的方法。另有一些是改进无约束优化问题的方法，通过对处理无约束优化问题的方法的改进，使之能用于约束优化的情况。下面对几种方法进行简单的介绍：( 1 ) 基于罚函数的方法：静态罚函数法【1 1 】：考虑如下的非线性规划问题i r a i n，( x )一【s 上晶( x ) 0其中f = 1 , 2 ，m 。适应度函数为：f ( x ) = 厂( x ) + p ( x )惩罚项p ( x ) 定义为：若x 是可行的，则p o ) = o ；否则p ) = ( 功由于对于每个约束优可分为几个违反级，所以按照违反级，r 是袖应变化的约束i 的惩罚系数。动态罚函数法【1 2 】：该方法使用了与时间( 迭代次数、代数等) f 有关的罚函数，在第f 代个体的适应度函数设置为：f ( x ) - - f ( x ) + ( c t ) 8 ( x ) ，其中c , o ，为可调参数，z 在x 为可行解时取0 ，在工为不可行觯_ 时取约束违反量的绝对值。豫8 。( 2 ) 基于搜索容许解的方法：如行为记忆法【”l ：该方法逐步处理约束，每次处理一个，使得种群中满足该约束的个体达到预先规定的比例，如在处理第，个约束的时候，要保持前，一1 个约束均满足，这样使得最后种群中有足够多的可行解。( 3 ) 多目标的方法p 4 1 ”】：s c h a f f e r 将目标函数厂( 茗) 及约束惩罚函数薪( x ) = m a x ( o ，g ，( 工) ) ，f = 1 , 2 ，m 合并在一起组成一个向量，再用多目标技术来极小化该向量的所有分量。( 4 ) 混合方法：基于各种处理约束问题的方法，出现了大量的混合算法，代表性的有把进化算法与其他传统方法结合。1 9 7 9 年，j a np a r e d i s 提出了协同进化算法( c o e v o l u t i o n a r yg e n e t i c a l g o r i t h m , c g a ) 解决一般的约束问题，其中一个种群由问题的解组成，称为解种群( s o l u t i o np o p u l a t i o n ) ；另一个种群由约束组成，称为测试种群( t e s tp o p u l a t i o n ) 。这两个种群协同进化，种群间的相互作用通过适应度评价来实现。作为一种混合算法，协同进化算法是一种有效的优化算法。6遗传算法在分配问题中的应用1 3 本文的主要工作及安排本文共分六章，首先我们对两类特殊的分配问题( 民航机场机位分配问题和超市货架分配问题) 的模型作了更深入的研究，对这两类分配问题的模型作出了改进，提出了更符合实际的新模型；其次在此基础上，针对民航机场机位分配问题设计了一个有效的遗传算法，及与实际问题相应的编码方法和杂交、变异算子，有效地处理了约束条件，取得了良好的效果；针对超市货架分配问题设计了一个模拟退火算法与遗传算法结合的混合算法，结合了两种算法的优点，提高了遗传算法的效率，并且提出了一个双目标的超市货架分配模型，针对此模型设计了几种局部搜索算法，再把这几种局部搜索算法柔和进遗传算法中，实验显示新模型和我们的算法是有效的。第一章：简单介绍了全局优化问题的发展概况及已有的典型算法。第二章：介绍了进化算法的几种主要分支：遗传算法、进化策略、进化规划和粒子群算法；还比较详细地介绍了模拟退火算法。第三章：对民航机场机位分配问题的模型作了修正并设计了一个新的遗传算法，进行了数据模拟实验，结果表明了算法是稳定有效的。第四章：介绍了超市货架分配问题及其发展的概况。第五章：针对y a n g 的超市货架问题的模型设计了一个新的模拟退火遗传算法，并进行了数值仿真，和其他几种算法进行了比较，结果显示新算法相比其他算法更有效。第六章：在第五章模型的基础上对货架分配问题的多目标模型作了一个初步的探讨，提出了一个双目标的超市货架分配模型，设计了一个局部搜索算法和遗传算法结合的混合算法，并进行了计算机仿真，实验显示，新模型能提高超市的运营效率，增加超市的长期利润，有着重要的现实意义，并且实验结果也显示新算法也是稳定的、有效的。第二章进化算法概述第二章进化算法概述自然界中的生物对其生存环境具有优良的自适应性，各种物种在一种竞争的环境中生存，优胜劣汰，使得物种不断改进。近3 0 年来，人们从不同的角度出发对生物系统及其行为特征进行了模拟，产生了一些对现代科技发展有重大影响的新兴学科，其中对自然界中生物进化机制的模拟就产生了进化计算理论。总的来说，共产生了遗传算法( g e n e t i ca l g o r i t h m , 简称g a ) 、进化策略( e v o l u t i o n a r ys t r a t e g y , 简称e s ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，简称e p ) 、遗传程序设计等四种典型的方法。这些方法在进化原则上是一致的，但有不同的侧重点，其中遗传算法是最具代表性的，进化策略侧重于数值分析，进化规划的应用则介于数值分析与人工智能之间。遗传程序设计是对算法程序进行进化。近来这几种不同的方法积极地进行了相互交流，使得它们之间的区别也在不断地缩小。进化算法提供了一种求解复杂系统优化问题的通用框架，其基本着眼点是基于对生物进化过程的模拟，开发一种具有较强鲁棒性的通用计算模型，下面我们给出进化算法的统一算法描述i l l 。算法e v o l u t i o n a r ya l g o r i t h m7 7( 1 ) 随机给定一组初始群体p ( t ) ，t 是进化代数。( 2 ) 评价群体p ( t ) 的适应值。( 3 ) 根据( 2 ) 的评价结果，从当前解中选择一定数量的个体作为基因操作对象。( 4 ) 对所选的基因进行操作( 交叉、变异) ，得到一组新的个体。( 5 ) 返回( 2 ) ，对该组新个体进行评价。( 6 ) 若满足终止条件，计算结束：否则转( 3 ) 。进化算法的几个分支虽然着眼于自然界中生物进化的不同背景，但它们之问有很多相似之处，都具有下述一些基本特点：( 1 )算法的搜索过程是从一群初始点开始，而不是从单一的初始点开始搜索。( 2 )算法使用的是目标函数的评价信息，其具有良好的普适性。( 3 )算法具有显著的隐式并行性。( 4 )算法具有很强的鲁棒性。一目前，进化算法作为一种具有自适应调节功能的寻优技术，其独特的性能已在众多领域内获得了成功的应用，着重用于解决结构性优化、非线性优化、并行计算等复杂问题，其中遗传算法的研究最为深入、持久、应用面也最广。但是，78遗传算法在分配问题中的应用应用实践表明，遗传算法也有一些缺点，其中最主要的缺点是它易产生早熟现象、局部搜索能力较差。为了克服这些不足，一些研究者在遗传算法中融入了一些局部搜索能力较强的算法，以提高遗传算法的效率，比如梯度法、爬山法、模拟退火算法、列表寻优法、局部搜索算法等，其中运用较多的是遗传算算法和模拟退火算法的混合，在本章也介绍了模拟退火算法的相关知识。2 1 遗传算法概述遗传算法是从代表问题可能潜在解集的一个种群( p o p u l a t i o n ) 开始的，该种群由一些经过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个体( i n d i v i d u a l ) 组成。按照问题特点，确定适应度函数( f i m e 嚣f u n c t i o n ) ，对每一代种群，根据个体的适应度( f i t n e s s ) 大小选择( s e l e c t i o n ) 个体，利用遗传算子( g e n e t i co p e r a t o r )进行杂交( c i o s s o v c i ) 和变异( m u t a t i o n ) ，从而产生代表新解集的下一代种群。这样一代一代的不断进化，最后在种群中将会得到一个优良的个体，它所对应的表现型将达到或接近于问题的最优解。遗传算法涉及六大要素；遗传编码、初始种群的生成方法、适应度函数的设计、杂交算子和变异算子的设计、控制参数的制定以及算法终止条件。1 遗传编码编码是应用遗传算法时要解决的首要问题，也是设计算法时的一个关键步骤，编码实际上就是在优化问题的实际表示与遗传算法的编码空间的点之间建立一个对应关系，它既包括编码方法( e n c o d i n g ) 又包括解码方法( d e c o d i n g ) ，编码方法也影响到杂交算子、变异算子等遗传算子的运算方法。因此，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。问题编码一般应满足一下三个原则：完备性( c o m p l e t e n e s s ) ：问题空间中的所有点都能成为编码后空间中的点。健全性( s o u n d n e s s ) ：编码空间的点必须对应问题空间中的某一潜在解。非冗余性( n o n - r e d u n d a n c y ) ：编码后的点和潜在解必须一一对应。按照遗传算法模式定理，d e j o n g 进一步提出了较为客观明确的操作性较强的实用编码原则：( 1 )应使用能易于产生与所求问题相关的低阶、短定义长度模式的编码方案。( ”。应使用能使问题得到自然表述的具有最小编码字符集的编码方案。实际中，重要的编码方式有：二进制编码、大字符集编码、格雷码编码、序列编码、实数编码、树编码、自适应编码、乱序编码和多参数交叉编码等，其中二进制编码是最基础的编码方式。第二章进化算法概述2 初始种群的生成一定数量的个体组成了群体( p o p u l a t i o n ) ，群体中的个体的数目称为种群规模( p o p u l a t i o ns i z e ) 。由于遗传算法的群体性操作需要，所以在执行遗传操作之前，必须已经有一个由若干初始解组成的初始种群。由于现实工程问题的复杂性，往往并不具关于问题解空间的先验知识，所以很难确定最优解的数量及其在可行解空间中的分布状况。所以我们往往希望在问题的解空间中均匀布点，随机生成一定数目的个体( 个体数目等于种群规模) 。初始种群中的每个个体一般是随机产生。种群的规模是遗传算法的控制参数之一，其选取对遗传算法的效能有影响。一般情况下种群规模在几十到几百之间取值，可根据问题的复杂程度不同而取值不同，问题越难，维数越高，种群的规模越大，反之则小。初始种群的设定可采取下面的策略：1 ) 设法把握最优解在整个问题空间的分布范围，然后在此分布范围内均匀设定初始种群。2 ) 先随机生成一定数目的个体，然后从中选出最好的个体加入种群中，不断重复这一过程，直到达到种群规模。另外，对于带约束域的问题，还需要考虑到随机初始化的点是否在可行域范围之内，所以产生初始种群一般必须借助问题领域的相关知识。3 适应度函数：在研究自然界中生物的遗传和进化现象是，生物学家使用适应度来度量个体对其生存环境的适应程度。适应度较高的个体其生存的机会就高，反之就小一些。与此类似，遗传算法中也使用适应度来度量种群中各个个体在优化计算中有可能达到或接近或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就大；适应度较低的个体遗传到下一代的概率就小一些。度量个体适应度的函数称为适应度函数( f i t n e s sf u n c t i o n ) 。1 ) 目标函数与适应度函数遗传算法的一个特点是它仅使用所求问题的目标函数值就可得到下一代的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来实现的。评价个体的适应度的一般过程是：对个体编码串进行解码处理后，可得个体的表现型。由个体的表现型可计算出对应个体的目标函数值。根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。适应度函数的设计一般主要满足以下条件：a解析性质：单值、连续、非负。b合理性：要求适应度函数值能够反映对应解的优劣程度。c计算量小：要求适应度函数的设计应尽可能简单。9l o遗传算法在分配问题中的应用d通用性强：适应度函数对某一类具体问题，应尽可能通用。当然对于特别设计的遗传算法，可以不必完全遵守上述规则。最优化问题可分为两类：一类为求目标函数的全局最大值，另一类为求目标函数的全局最小值。对于这两类优化问题，一般有下面由解空间中某一点的目标函数值f ( x ) 到搜索空间中对应个体的适应度函数值f ( x ) 的转换方法：对于求最大值的问题，作下述的转换：胂p 。4 - 茏麓：。式中，c | 叫为一个适当地相对较小的数。对于求最小值的问题，作下述转换：胂卜0o 嬲f ( x ) 。这两种进化策略中，都采用重组、突变、选择三种算子，其中重组算子类似于( + 1 ) 一e s ，而突变操作则有了新的发展，标准差作自适应调整：呵卸憎州枷( 2 - 2 )卜= 石+ ( o ，盯)。其中( x , o r ) 表示父代个体，( x ，口) 表示子代个体，a o r 是参数，n o , o r ) 是独立服从正态分布的随机变量，其均值为0 ，标准差为盯。相比( 芦+ a ) 一e s1 8遗传算法在分配问题中的应用而言( ，名) 一e s 进化更快，特别适用于目标函数有噪声或优化程度明显受迭代影响的课题，因而其得到广泛的应用。2 进化策略的主要构成技术1 ) 个体的表示进化策略采用传统的十进制实数表达问题，它有两种表达方式。( 1 ) 二元表达方式。这种表达方式中的个体由目标变量x 和标准差两部分组成，每部分又可有行个分量，即( x ，盯) = “而，如，h ) ，( c 5 ，a j9 e 9 a i ) )( 2 ) 三元表达方式。为了改善进化策略的收敛速度，三元表达方式引入了坐标旋转角口，即( x ，o r , t ) = “而，而，毛) ，( q ，0 2 ，a j ) ，( o q ，t 2 ，口。”三元表达方式使新个体的发展更自由，加快了收敛速度。2 ) 适应度评价。在进化策略中，设定每个个体的适应度就等于其对应的目标函数值。因此适应度的计算就更直观、简便。3 ) 重组。进化策略中的重组( r e c o m b i n a t i o n ) 算子相当于遗传算法中的交换，都是以两个父代个体为基础进行信息交换。进化策略中，重组方式主要有三种：( 1 ) 离散种族就是先随机选两个父代，然后将其分量进行随即交换，构成子代新个体的各个分量，从而得到重组后的新个体。( 2 ) 中值重组就是将两个父代个体各分量的平均值作为子代新个体的分量。( 3 ) 混杂重组就是先随机选一个固定的父代个体，然后针对子代个体每个分量再从父代群体中随机选第二个父代个体，然后再采用离散重组或中值重组的方式加以处理。4 ) 突变。在进化策略中，突变是产生新个体的主要方式，它是在旧个体的基础上添加一个随机量，从而形成一个新个体。其过程可表述如下：一= q e x p ( r 。n ( 0 ，1 ) + f t o , ( o ，l ”a i - - - - 0 i 七9 nl q 沁x l = x i + z t( 2 - 3 )式中系数f 、f 为全局步长系数和局部步长系数，系数口涉及旋转角度。5 ) 选择。和遗传算法不同的是，在进化策略中，选择操作是按照一种确定的方式来进行的。目前在进化策略中所使用的选择方法主要有：一类是从五个父代个体中选出( 1 a ) 个适应度最高的个体，将它们保留到子代群体中。另一类第二章进化算法概述1 9是将个父代个体和其所产生的五个子代个体合并在一起，并从这合并而成的+ a 个个体中选取个适应度最高的个体，将它们保留到子代群体中。3 进化策略的特点与遗传算法相比，进化策略具有下面一些主要特点：1 ) 进化策略以行维实数空间上的优化问题为主要处理对象。2 ) 进化策略的个体含有随机扰动因素。3 ) 进化策略中各个个体的适应度直接取自它所对应的目标函数值。4 ) 个体的变异运算是进化策略中所采用的主要搜索技术，而个体之间的重组运算只是进化策略中所采用的辅助搜索技术。5 ) 进化策略中的选择运算是按照确定的方式来进行的，每次都是从群体中选取最好的几个个体，将它们保留到下一代群体中。2 4 2 进化规划进化规划是2 0 世纪6 0 年代由美国的l j f o g e l 等口3 1 为求解预测问题而提出的一种有限状态机进化模型，在这个进化模型中，机器的状态基于均匀随机分布的规律来进行变异。9 0 年代，d b f o g e l 刚又将进化规划的思想拓宽到实数空间，并在其变异运算中引入正态分布的技术，这样，进化规划就成为一种优化搜索技术，并在很多实际领域得到了应用。1 ) 进化规划的主要构成技术进化规划的基本思想也是来源于对自然界中生物进化过程的一种模拟。其构成技术与进化策略的构成技术相类似，主要是：( 1 ) 个体的表示方法。在进化规划中，搜索空间是一个以维空间，与此对应，搜索点就是一个n 维向量x r ”，个体x 就直接用这个以维向量来表示，即：z = x r 4( 2 ) 适应度评价。在进化规划中，个体的适应度f ( x ) 是由它所对应的目标函数厂( z ) 通过某种比例变换而得到的，这种比例变换是为了既保证各个个体的适应度总取正值，由维持各个个体之间的竞争关系。设j 为某种比例变换函数，则f ( x ) = 占l 厂( j ) j( 3 ) 变异算子。变异是进化规划产生新群体的唯一方法，它不使用重组算子或杂交算子。对标准进化规划，其变异操作为：x l = x i 七p l f q n 七y l n t u k b其中x l 表示旧个体目标变量x 的第f 个分量x l 表示新个体目标变量x 。的第i 个分量遗传算法在分配问题中的应用八x ) 表示旧个体的适应度函数l ( o ，1 ) 表示针对第f 个分量产生的随机数，它服从标准正态分布屈是系数，常取1九是系数，常取0这种变异使个体变动比较剧烈，不利于算法收敛于全局最优解。还有一种变异方法，它增加了一个控制因子，使得个体的个分量在一个小的范围内变动，有利于算法的收敛，具体如下：，一l 而= 而+ q 。( o 1 )i o s = q + 玎吼n j ( o ，1 )( 4 ) 选择算子。在进化规划中，选择操作是按照一种随机竞争的方式来进行的。其基本过程是：将个父代个体p o ) 和经过一次变异运算后产生的个予代个体p ( f ) 合并在一起，组成含2 个个体的集合 p ( t ) u p 。o ) ；对这个个体集合中的每一个个体k e ( t ) u e ( f ) ，再从这个个体集合中随机选取其它g 个个体( 其中q l 是选择运算的参数) ，比较这口个个体和个体砭之间的适应度大小，以其中适应度比以的适应度还要高的个体的数目作为个体k 的得分吸。按个体集合中每个个体的得分对个体集合进行降序排列，选择前个个体作为下一代种群p ( ，+ 1 ) 。2 ) 进化规划的特点与遗传算法和进化策略相比，进化规划主要具有下面几个特点：( 1 ) 进化规划对生物进化过程的模拟主要着眼于物种的进化过程，不使用个体重组方面的算子。( 2 ) 进化规划中的选择着重于群体中各个个体之间的竞争选择。( 3 ) 进化规划直接以问题的可行解作为个体的表现形式，无需再对个体进行编码处理，也无需在考虑随机扰动因素对个体的影响，便于应用。( 4 ) 进化规划以栉维实数空间上的优化问题为主要处理对象。2 4 3 三种典型进化算法的比较遗传算法、进化策略、进化规划这三种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象，所以它们有很大的相似性。但由于它们分别从不完全相同的角度出发来模拟生物的进化过程，所以它们之间又有差异。下表比较了这三种进化算法的主要特点。第二章进化算法概述比较项目遗传算法( g a )进化策略( e s )进化规划( e p )个体表现型离散值连续值连续值参数调整法无标准偏差、协方差方差适应度评价变换目标函数直接使用目标函数变换目标函数变异辅助搜索方法主要搜索方法唯一搜索方法重组主要搜索方法辅助搜索方法不使用选择概率的、保存的确定的、不保存的概率的、不保存的2 5 混合遗传算法在遗传算法的研究中，主要的目标之一就是设计使设计的算法是稳健的，即广泛适用于多种问题。尽管传统的遗传算法是稳健的，但是就任何一个特殊领域