（运筹学与控制论专业论文）基于平滑技术及一维搜索的全局优化遗传算法.pdf

摘要 摘要 进化算法是模拟生物界的进化过程而产生的一种现代优化方法，作为种有 效的随机搜索方法，在优化方法中具有独特的优越性，有着非常重要的意义和及 其广泛的应用。传统优化方法对目标函数解析性质要求较高，进化算法不需要目 标函数的导数信息，具有隐式并行性，所以常用于解决一些复杂的、大规模的、 非线性、不可微的优化问题。 首先，本文对无约束优化问题提出了一个新的进化算法，这种算法利用平滑 技术构造了一个新的适应度函数，并适时结合一维搜索去解决无约束优化问题。 新的适应度函数具有有效去除部分局部极小点的优越性能，使得整个算法大大减 小了陷入局部最优的可能性；而新的杂交箅子和适时一维搜索使得算法更迅速有 效的找到全局最优。 其次，把原约束优化问题转换为只有两个目标函数的多目标优化问题，并针 对新的模型设计了新的遗传算子，在此基础上对新的模型设计了一个新的遗传算 法。通过求解多目标优化问题而得到约束优化问题的最优解。数值试验表明算法 是有效的。 关键词：全局优化遗传算法多目标优化 a b s t r a c t a b s t r a c t e v o l u t i o n a r ya l g o r i t h m sa r ef l e wk i n d so fm o d e r no 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 y p r i n c i p l eo fn a t u r ee v o l u t i o na s n e wk i n d so fr a n d o ms e a r c ha l g o r i t h m s ，t h e yh a v es o m e a d v a n t a g e s o v e rt 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 s ，a n da r eo ft h eg r e a ti m p o r t a n c ea n dh a v eaw i d er a n g e o f a p p l i c a t i o n s t h e t r a d i t i o n a l o p t i m i z a t i o na l g o r i t h m su s u a l l y h a v es t r i c tl i m i t a t i o n so nt h e f u n c t i o n ss u c ha st h e i r d i f f e r e n t i a b i l i t y , h o w e v e re v o l u t i o n a r ya l g o r i t h m s d on o t r e q u i r e t h e d i f f e r e n t i a b i l i t yo ft h ef u n c t i o n sa n dh a v ep a r a l l e lp r o p e r t 弘t h e r e f o r e ，t h e ya r eo f t e nb eu s e dt o s o l v es 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 ，an e we v o l u t i o n a r ya l g o r i t h mf o ru n c o n s t r a i n e do p t i m i z a t i o np r o b l e m si sp r o p o s e di nt h i s p a p c li nt h ep r o p o s e da l g o r i t h man e w f i t n e s sf u n c t i o nb a s e do ns m o o t h i n gt e c h n i q u ei s d e s i g n e d ， a n dan o v e ll i n es e a r c hs c h e m ei si n t e g r a t e di n t ot h ea l g o r i t h md e s i g nt oi m p r o v et h ee f f i c i e n c yo f t h ea l g o r i t h m t h en e wf i t n e s sf u n c t i o nh a st h ea d v a n t a g e st h a tt h em a n yl o c a lo p t i m a ls o l u t i o n sc a n b er e m o v e db yu s i n gt h i sf i t n e s sf u n c t i o n a sar e s u l t ，i ti sl e s sp o s s i b l ef o rt h ep r o p o s e da l g o r i t h mt o t r a pi n t ot h el o c a lo p t i m a ls o l u t i o n s m o r e o v e r , t h en e wc r o s s o v e ro p e r a t o rd e s i g n e di nt h i sp a p e r a n dt h en e wl i n es e a r c hs c h e m ec a nm a k et h ep r o p o s e da l g o r i t h mf i n dt h e 醛o b a lo p t i m a ls o l u t i o n s m o r eq u i c k l g s e c o n d ，t h ec o n s t r a i n e do p t i m i z a t i o np r o b l e mc o n s i d e r e di st r a n s f o r m e di n t oam u l t i o b j e c t i v e o p t i m i z a t i o np r o b l e mw i t h t w o o b j e c t i v e s ，a n d n e wg e n e t i c o p e r a t o r s a r e d e s i g n e d f o rt h e m u l t i - o b j e c t i v eo p t i m i z a t i o np r o b l e m m o d e l b a s e do i lt h e s ean e wg e n e t i ca l g o r i t h mi sp r o p o s e df o r t h en e wm o d e l b ys o l v i n gt h em u l “一o b j e c t i v eo p t i m i z a t i o np r o b l e mw ec a ng e tt h eo p t i m a l s o l u t i o n sf o rt h ec o n s t r a i n e do p t i m i z a t i o np r o b l e m t h es i m u l a t i o nm s u l t ss h o wt h ee f f e c t i v e n e s so f t h ep r o p o s e da l g o r i t h m k e y w o r d s ：g l o b a lo p t i m i z a t i o n g e n e t i ca l g o r i t h mm u l t i o b j e c t i v eo p t i m i z a t i o n 创新性声明 y $ 8 3 47 , 5 本人声明所呈交的论文是我个人在导师指导下进行的研究工作以及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的浇明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名 动室垂 日期出碰： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。 本人签名： 导师签名： 壹登 虹 日期乎切乒、一3 - 日期丝丛：! ： 第一章绪论 第一章绪论 1 1 引言 本文主要是用智能优化技术遗传算法( g e n e t i c a l g o r i t h m ，g a ) ，通过对遗 传算法中相关算子的改进以及引进一些其他相关技术来有效的处理单目标多峰函 数优化问题：包括无约束优化问题和约束优化问题。 遗传算法l 卜5 】是由美国密歇根大学教授j o h n h h o l l a n d 及其学生首先提出的一 种有效的全局搜索方法。它是模拟生物界的进化过程而产生的一种现代优化方法。 达尔文的进化论指出，自然界进化遵循“优胜劣汰，适者生存”的原则，在遗传 ( h e r e d i t y ) 、变异( v a r i a t i o n ) 以及自然界的选择( n a t u r a ls e l e c t i o n ) 下，适应大自然 的个体得以生存，不适应的就会被大自然所淘汰。所以从整体上看，大自然进化 的过程其实就是一个大型的优化过程。仿照这一过程，遗传算法就应用而生。它 是一类随机优化算法，但不是简单的随机比较搜索，而是通过对染色体的评价和 对染色体中基因的作用利用已有的信息来指导搜索有希望改善优化质量的状态。 与传统的启发式优化算法相比，遗传算法的主要本质特征在于群体搜索策略和简 单的遗传算子。群体搜索使遗传算法得以突破邻域搜索的限制，可以实现整个解 空间上的分布式信息探索，采集和继承；遗传算子仅仅利用适应值度量作为运算指 标进行染色体的随机操作，降低了一般启发式算法在搜索过程中对人机交互的依 赖。这样就使得遗传算法获得了强大的全局最优解搜索能力，问题域的独立性， 信息处理的隐并行性，应用的鲁棒性，操作的简明性，成为一种具有良好普适性 和可规模化的优化方法。但遗传算法也有其自身的缺点，比如容易产生早熟收敛 以及收敛速度慢等。 本文在利用遗传算法众多的优点的同时，又适时的引进一维搜索技术，设计 了不同的遗传算子，使得针对无约束优化问题能够迅速有效的找到全局最优点， 又不象传统方法那样容易陷入局部极小。而且本文还对约束优化问题做了处理， 通过模式转换，使问题转化为只有两个目标的多目标优化问题，并针对这一新的 模型设计了相应的遗传算子，使得约束优化问题跳出传统的罚函数方法，新颖而 有效的找到全局最优。 基于平滑技术及一维搜索的全局优化遗传算法 1 2 最优化问题的研究概况 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。 作为一门重要的科学，优化技术得到人们的诸多重视并在诸多工程领域被迅速推 广和广泛应用，如计算机工程、人工智能、模式识别、系统控制、生产调度、等 等。在实际的生产过程中，结合运用最优化技术，使各项指标得到最优，有利于 提高效率，节省资源，这使得最优化理论有了实际的意义。因此，优化方法的理 沦研究即改进算法性能、拓宽算法应用领域、完善算法体系是具有理论意义和实 用价值的。 优化方法涉及的工程领域很广，问题种类繁多，总的可以分为函数优化问题 和组合优化问题两大类。本文主要解决函数优化问题。 1 2 1 问题描述 函数优化问题通常可以描述为：令s 为尺4 上的有界子集( 即变量的定义域】， ，：s 一月为, 1 维实值函数，所谓函数，在s 域上全局最小化就是寻求点 x 。e s 使得，( x 。) 在s 域上全局最小，即v y e s ：f ( x 。f ( x ) 一般地，最优化问题( o p t i m i z a t i o np r o b l e m )目标函数( o b j e c t i v 导f u n c t i o n 琊约 束条件( c o n s t r a i n t s ) 两部分构成： m i n i m i z e f ( x ) i ， ”工2 ，z ) s u b j e c tt oz ；0 l ，z 2 ，一，z 。) sc r ” 将满足所有约束条件的解空间s 称为可行域( 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 l ；将可行域中使目标函数达到最小的解称为最优解 ( o p t i m a ls o l u t i o n ) 。对于最大化问题，可将目标函数乘以( 一1 ) ，转化为最小化问题 求解。 目标函数和约束条件均为线性表达式，则该最优化问题称为线性规划问题 ( 1 i n e a rp r o g r a m m i n gp r o b l e m ) ；否则称为非线性规划问题( n o n l i n e a rp r o g r a m m i n g p r o b l e m ) ；对于没有约束条件的函数优化问题，称为无约束优化问题0 m c o n s t r a i n e d o p t i m i z a t i o np r o b l e m ) ，否则称为约束优化问题( c o n s t r a i n e do p t i m i z a t i o np r o b l e m ) 。 1 2 2 现有优化算法及其分类 所谓优化算法，其实就是一种搜索过程或规则，根据现有优化问题的特点， 利用某种思想或机制，按照相应的某种途径和方法来得到满足现实要求的问题的 解。现有的优化算法大致可以分为以下几类： f 1 1 经典算法：包括线性规划、动态规划、整数规划和分枝定界等传统算法。它 们对目标函数的解析性质要求较高，而且计算复杂性一般很大，所以只适应 于求解小规模的简单问题，在工程中往往不能广泛应用； 第一章绪论3 ( 2 ) 构造型算法：通过对问题的分析，希望用构造的方法快速建立问题的解。通 常这样的算法不是很有效，对于庞大复杂的问题，很难满足需要。比如调度 问题中的典型构造方法有：j o h n s o n 法、g u p t a 法、c d s 法、p a l m e r 法、 d a u n e n b r i n g 的快速接近法等： ( 3 ) 基于系统动态演化的方法：将优化的过程转换为系统动态的演化过程，如神 经网络和混沌搜索等： ( 4 ) 改进型算法：这种算法从任意解出发，通过对其邻域的不断搜索，用得到的 更好解来替换当前找到的最好解，层层迭代，不断提高当前最好解的质量， 从而达到全局最优。代表性的方法有进化算法及归于其中的遗传算法等： ( 5 ) 混合型算法：指根据不同问题的具体需要，利用上述各种算法的优点，克服 其弊端，从结构或操作上混合而产生的各种算法。实践证明这种方法往往是 快捷有效的。 求解无约束优化问题的算法： 现有的众多算法大致可分为确定性方法和随机方法两类： 确定性算法往往对目标函数的解析性质要求比较高，要用到目标函数的梯度 信息或者高维导数信息，代表性的方法如l e v y 的隧道法【6 l 和r ，g e 的填充函数法【7 i 以及b r i a n i n 的下降轨线法等： f 1 1 隧道算法：隧道算法的思想是从当前最好点出发，通过在该点建立一个隧道函 数，希望能打通一条隧道，从而进入另一个深谷里，找到相应的具有下降方向 的点，再通过局部搜索，找到新的深谷里的局部最小点，这样层层迭代，直到 全局最优。其思想可阱通过下面图形形象的表示： 图1 _ 1 ：一元函数隧道方法示意图 假设图中x 1 为当前最好点，那么通过建立隧道函数，打通隧道( 图中t u n n e l ) 然后最小化之( m i n ) ，希望得到更好的点x 2 + ，依此类推，得x 3 + 。对于得到得 各点，有以下关系式成立： 基于平滑技术及一维搜索的全局优化遗传算法 厂( z ：) z 厂扛i ) z z ，( x ：) 其中x g + 为全局最优点 ( 2 ) 填充函数法：填充函数法也是基于当前最好点，根据该点建立一个相应的辅助 函数，该函数能够填平当前最好点所在的深谷，帮助搜索跳出局部极小，转移 到一个“地势更低的深谷”，获取该深谷的一个点，从该点重新搜索，希望能 找到比当前点更好的点。该方法的关键在于如何去建立一个合适的填充函数。 随机性方法对目标函数要求低，稳定性好，但收敛速度慢。代表性的方法有 遗传算法、m o n t e c a r l o 随机试验法、模拟退火法( s i m u l a t e da n n e a l i n g ) 等： ( 1 ) m o n t e c a r l o 随机试验法：m o n t e c a r l o 随机试验法是按均匀分布在搜索空间随 机产生大量的试验点，然后找出其在可行域中最好点作为最优解的一种随机近 似方法。 ( 2 ) 模拟退火法：模拟退火法( s i m u l a t e da n n e a l i n g ) 是基于固体冷却过程和一般组合 优化问题之间相似的特点而产生的- - g e 优化算法。固体物质退火的物理模型与 随机过程的理论结合形成了模拟退火法的基本思想。事实证明，对离散变量的 组合优化问题和连续变量函数的极小化问题模拟退火算法都是有效可行的。模 拟退火法求解极小化问题的基本步骤【8 】为： 1 ) 定义极小化的目标函数f ( x ) ； 2 ) 给定初始解x 。和初始温度0 0 ，0 ； 3 、循环直到满足结束条件： i ) 循环工次。任选一个x 的邻近值x ，求出；f 暖。) 一f ( x ) ： 虫口果s0 ，贝4 x = x ； 如果? o ，则x = x 的概率是e x p ( 一a c ) ； i i ) 令c m = r c t ，( 0 r l ，即降低温度) 。 4 1 输出最终解爿。 求解约束优化问题的算法 约束优化问题的求解方法众多，最常见最基本的是罚函数法。它把约束优化 问题转化为无约束优化问题，再用无约束问题的方法去解。和众多的方法相比较， 罚函数法是一种相当有效，成功率较高的方法。另有些是改进无约束优化问题 的方法，通过对处理无约束优化问题的方法的改进，使之能用于约束优化的情况。 下而对几种方法进行简单介绍： f 1 1 基于罚函数的方法： 静态罚函数法【9 】：考虑如下非线性规划问题 m i n f 0 ) s t g 。x ) s 0 i = 1 , 2 ，m ； 适应度函数为：p ( x ) ；f ( x ) + p o ) ； 第一章绪论 惩罚项p ( z ) 定义为：若x 可行，则p ) = o ；否则p 0 ) = y l g 。( z ) 由于对于每个约束又可分为几个违反级，所以按照违反级，崖相应变化的约束 i 的惩罚系数。 动态罚函数法【1 。】：该方法使用了与代数t 有关的罚函数，在第t 代个体的适 应度函数设置为： f ) ；，o ) + ( “) 。f 吖g )其中c ，a ，卢分别为可调参数( 确定后取常数) d 在x 为可行解时取o ，在x 不可行时取约束违反量的绝对值。 f 2 1 基于搜索容许解的方法： 如行为记忆法【l l 】：该方法逐步处理约束，每次处理一个，使得种群中满足 该约束的个体达到预先规定的比例，如在处理第，个约束的时候，要保持前卜1 个 约束均满足，这样使得最后种群中有足够多的可行解。相关的方法还有容许点优 先法等。 ( 3 ) 混合方法： 基于各种处理约束问题的方法，涌现出大量的混合算法，代表性的有把进化算 法与其他传统方法结合。1 9 7 9 年，j a n p a r e d i s 提出了协同进化算法( c o e v o l u t i o n a r y g 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 t p o p u l a t i o n ) 。这两个神群协同进化，年中群问的相互作用通过适应度评价来实现。作 为一种混合方法，协同进化算法是一种有效的优化算法。 1 3 本文的主要工作及安排 本文共分为四章，利用遗传算法分别研究了无约束优化问题及约束优化问题 的求解方法。针对遗传算法的优缺点，通过设计新的算子，使得整个算法对于解 决无约束优化问题及约束优化问题取得了很好的效果。具体安排如下： 第一章简单介绍了本文所处理的问题为全局优化问题；所做工作的基本思想 是基于遗传算法的改进以及结合其他新颖有效的技术对无约束和约束优化问题进 行处理：并且对全局优化问题的发展概况及已有的解决方法做了大概的介绍。 第二章对在文章中占重要位置的遗传算法做了颇为详细的介绍。给出遗传的 特点所在和算法的算法步骤以及当前的理论研究状况。该章还给出了现有的用来 解决优化问题的遗传算法的一些方法及其改进状况并展望了遗传算法的将来。 第三章是对无约束优化问题的处理。本章首先引进了平滑技术理论，给出了 一个新设计的适应度函数并分析了它的特点和在算法中的作用。另外还设计了新 的交叉算子，根据函数在该点的函数值及其近似梯度的信息来判断点的好坏，从 基于平滑技术及一维搜索的全局优化遗传算法 而产生新的不劣于父代点的子代点。在算法中为了使算法能够迅速收敛，我们还 引进了一维搜索机制，使得整个算法迅速有效的找到全局最优。文章还给出了算 法收敛性的证明，后面的数值仿真表明算法的有效性。 第四章主要针对约束优化问题设计了新的算法。该算法的思想是把约束优化 问题转化为目标函数只有两个的多目标优化问题，第一个目标函数为原目标函数， 第二个则为违反约束量最大的约束函数与零相比较取较大者，显然，同时对这两 个目标极小化其实就是求原约束优化问题的最优解。针对上述的目标模式，算法 还相应设计了新的杂交算子，变异算子以及选择算子：杂交算子利用均匀设计【1 2 1 的思想然在父辈点周围产生数个均匀分布的点，然后按照一定规则择优选择子代 点；选择中利用了多目标偏好的方法，根据解的情况使适应度函数偏向于某个目 标函数。后面算法应用证明了该算法的可行性及有效性。 第二章遗传算法的基本理论 第二章遗传算法的基本理论 遗传算法是2 0 世纪6 0 年代末期到7 0 年代初期主要由美国m i c h i g a n 大学 的j o h nh o l l a n d 与其同事、学生们研究形成的一个较为完整的理论和方法。遗传 算法是模拟生物进化及生物智能的信息处理机制而发展起来的仿生算法，它使用 群体搜索技术，通过对当前群体施加选择、交叉、变异等一系列遗传操作从而产 生出新一代的群体，并逐渐使得群体进化到包含或接近最优解的状态。遗传算法 不受其搜索空间限制性条件( 如可微、连续、单峰等) 约束，也不需要其他辅助 信息( 如梯度) ，因此，是一种高度并行、随机、自适应搜索算法，能够解决传统 方法感到困难的许多复杂、高维、大规模、非线性优化问题。 遗传算法经过了2 0 多年的发展，取得了丰硕的应用成果和理论研究的进展。 而且随着时间推移，全世界范围掀起进化计算的热潮，计算智能己成为人工智能 的一个重要研究方向。后来的人工生命研究兴起，遗传算法以其独特的优势受到 广泛的关注。从1 9 8 5 年在美国卡耐基梅隆大学召开的第一届遗传算法会议 ( i n t e r n a t i o n a l c o n f e r e n c eo i lg e n e t i c a l g o r i t h m s ：i c g a 8 5 1 到1 9 9 7 年5 月i e e e 的 t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 创刊，遗传算法作为高性能优化方法逐渐 成熟起来。但是，目前遗传算法也还存在很多问题，如理论不完善，存在早熟收 敛，收敛速度较慢等缺点。 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 t n e s sf 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 s ) 进行杂交( 或称交叉) ( c r o s s o v e r ) 和变异( m u t a t i o n ) ，从而 产生出代表新的解集的下一代种群。这样一代一代的不断进化，最后收敛到一个 最适应环境的个体上，求得问题的最优解。遗传算法所涉及的六大要素：参数编 码、初始群体的产生、适应度函数的设计，遗传操作的设计、控制参数的设定以 及算法终j 上条件。 1 、遗传编码 当用遗传算法求解问题时，必须在优化问题的实际表示与遗传算法的编码空 基于平滑技术及一维搜索的全局优化遗传算法 间的点之| 1 ；i j 建立一个关系，将实际问题中解的形式转换为遗传算法能够辨认的解 的表达形式，即确定编码( e n c o d i n g ) 和解码( d e c o d i n g ) 运算。由于遗传算法的鲁棒 性，它对编码的要求并不苛刻，但编码对遗传算法的搜索效果和效率有却是非常 重要的。对特定的问题确定合适的编码是非常重要的步骤。 问题编码一般应满足以下3 个原则： 1 ) 完备性( c o m p l e t e n e s s ) ：问题空间中的所有点都能成为编码后空间的点。 2 ) 健全性( s o u n d n e s s ) ：编码空间的点必须对应问题空间中的某一潜在解。 3 ) 非冗余性( n o n - r e d u n d a n c y ) ：编码后的点和潜在解必须一一对应。 按照遗传算法的模式定理，d ej o n g 进一步提出了较为客观明确的编码评估 原则。具体可以概括为两条： 1 )有意义建筑模块编码规则：编码应当易于生成与所有问题相关的短距和 低阶的建筑模块( b u i l d i n g n e c k s ) 。 2 ) 最小字符集编码规则：编码应采用最小字符集以使问题得到自然、简单的 表示和描述。 在实际的操作中，二进制编码是最基础的编码方式，他的应用范围非常广泛。 其他编码还有：大字符集编码、格雷码编码、序列编码、实数编码、树编码、自 适应编码、乱序编码、多参数交叉编码等。 2 、初始群体的生成 一定数量的个体组成了群体( p c p u i 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 s ) 。为了执行适者生存的原则，遗 传算法必须个体的适应性进行评价。因此，适应度函数( f i t n e s sf u n c t i o n ) 就构成 了个体的生存环境。遗传算法在搜索进化过程中一般不需要其他外部信息，只根 据个体适应值，就可以决定它在此环境下的生存能力。好的个体具有较高的适应 函数值，即可以获得较高的评价，具有较好的生存能力。差的个体一般适应度函 数值较小，所以生存能力相对弱。由于适应值是群体中个体生存机会选择的唯一 确定陛指标，所以适应函数的形式直接决定着群体的进化行为。为了能够直接将 适应函数与群体中的个体优劣度量相联系，在遗传算法中适应值规定为非负，并 且在任何情况下总是希望越大越好。一般而言，适应度函数是通过对目标函数的 转化而形成的。 适应度函数的设计般主要满足以下条件： f 1 ) 解析性质：单值、连续、非负； 合理性：要求适应函数值能够反映对应解的优劣程度； ( 3 ) 计算量小：要求适应函数设计应尽可能简单； f 4 ) 通用性强：适应函数对某一类具体问题，应尽可能通用。 当然对于特别设计的遗传算法，可以不必完全遵守上述规则。 适应度尺度变换 遗传算法中，群体的进化过程是以群体中各个个体的适应度为依据，通过 个迭代过程，不断的寻求出适应度较大的个体，最终就可得到问题的最优解或近 似最优解。在遗传算法运行的不同阶段还需要对个体的适应度进行适当地扩大或 缩小，这就是适应度尺度变换。在进化的初期，为避免未成熟收敛，应缩小个体 间差异；在进化的最后阶段，为了加快收敛，应放大个体间的差异。适应函数的 常用尺度变换法有一下几种：线形变换法、幂函数变换法、指数变换法。 4 、遗传操作 标准的遗传算法的操作算子一般都包括选择( s e l e c t i o n ，或者复制 r e p r o d u c t i o n ) 、交叉( c r o s s o v e r ，或称交) 和变异( m u t a t i o n ) 三种基本形式，它 们作为自然选择过程以及遗传过程发生的生殖，杂交和变异的主要载体构成了遗 传算法具的核心，使得算法具有强大的搜索能力。 1 1 选择算子 选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下 一代群体的遗传运算。它是根据适应度函数值选择适值高的个体以形成交配池 ( m a t i n gd 0 0 1 ) 的过程。在被选集中按照一定的选择的概率进行操作，这个概率取 决于种群中个体的适应度及其分布。其主要作用是避免了基因缺失，提高全局收 敛性和计算效率。 基于平滑技术及一维搜索的全局优化遗传算法 目前主要有适应值比例选择( f i t n e s s p r o p o t t i o n a t es e l e c t i o n ) 、b o l t z m a n n 选择、 排序选择( r a n ks e l e c t i o n ) 、联赛选择( t o u r n a m e n ts e l e c t i o n ) 、精英选择( e l i t s t s e l e c t i o n ) 、稳态选择( s t e a d y s t a t es e l e c t i o n ) 等形式。 2 ) 杂交算予 杂交操作是遗传算法中最主要的遗传操作之一。它是模仿自然界有性繁殖的基因 重组过程，对两个父代个体进行基因操作，其作用在于把原有优良基因遗传给下 一代个体，并生成包含更复杂基因结构的新个体。 常使用的遗传算子包括一点交y - ( o n e p o i n tc r o s s o v e r ) ，多点交叉( m u l t i p o i n t c r o s s o v e r ) ，一致交3 l ( u n i f o r mc r o s s o v e r ) 等形式。针对特定问题，还可以设计其他 类型的交叉算子，而且对于不同的编码方式，交叉算子也不同，比如m e s s yg a 中的交叉算子【1 3 l 、基于树形结构表示的染色体位串的交叉【1 4 , 1 5 】、t s p 问题中的部 分匹配交叉( o x ) 、周期交叉( c x ) 等形式【1 6 】等。 3 ) 逆转算子 在自然遗传学中有一种现象称作倒位现象，在染色体中有两个点，在这两点 问的基因位置倒换，称这样的两个点为似位点。倒位点使德那些在父代中离得很 远的基因位在后代中紧靠在一起。在遗传算法中相当于重新定义基因，使编码后 的体位中重要基因更加紧凑，更加不易被其他遗传操作分裂。逆转算子就是仿照 这一现象提出的。逆转操作的具体实施如下：首先在个体编码后的编码串上随机 选择两点，那么个体编码串就被这两个点分成三段，将其中中间段的左右顺序倒 转过来与另两段相连，从而形成新得个体。需要指出的是，这种遗传操作在普通 的遗传算法中并布常用。 4 ) 变异算子 变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的 其他等位基因来替换，从而形成一个新个体。在遗传算法中，变异算子通过按变 异概率p 。随机对个体染色体中的基因进行突变来实现。为了保证个体变异后不会 与其父体产生太大差异，变异概率一般取值较小( o 0 1 0 0 3 ) ，以保证种群发展得稳 定性。交叉操作是产生新个体的主要方法，它决定了遗传算法的全局搜索能力： 而变异操作只是产生新个体的辅助方法，它决定遗传算法的局部搜索能力，维持 群体的多样性，防止出现早熟现象。当种群规模较大时，在交叉操作的基础上引 入适度的变异，也能够提高遗传算法的局部搜索效率。 常用的变异算子有：位点变异、插入变异、对换变异、均匀变异、边界变异、 非均匀变异、高斯变异等。 5 、参数设定 在遗传算法的运行过程中，存在对其性能产生重大影响的一组参数。这组参数 第二章遗传算法的基本理论 在初始化阶段或群体进化过程中如果能有合理的选择和控制，那么遗传算法将能 够发挥以最佳作用，在随机搜索中迅速达到最优解。主要参数包括染色体长度l ， 群体规模，交叉概率p 。，以及变异概率p 。 在标准遗传算法( c g a ) 和一些简单遗传算法( s g a ) 中，这些参数是不变 的。然而，随着研究的深入，许多学者发现如果这些参数能够随着遗传算法进程 而变化，这种有自适应性能的遗传算法具有更高的鲁棒性、全局最优性，但其弊 端在于会增加算法复杂性和计算量等。还有一些参数的改进方法，比如，模糊控 制参数、模拟退火方法、基于均匀设计的参数设定等。 经过大量研究和经验总结，一些学者给出了如下最优参数建议： 1 ) 长度：位串长度取决于特定问题的精度。要求精度越高，位串长度越长， 单需要更多的计算时间。为了提高运算效率，变长度位串或者在当前达到的较小 可行域内重新编码是一种可行的方法，并显示出良好的性能。 2 ) 群体规模：大群体含有较多的模式，为遗传算法提供了足够的模式采样容 量，可以改进遗传算法的搜索的质量，防止成熟前收敛。但大群体增加了个体适 应性评价的计算量，从而使收敛速度降低。一般情况下n = 2 0 2 0 0 。 3 ) 交叉概率p ，：交叉概率控制着交叉算子的应用概率。交叉概率越高，群体中 新结构引入的越快，已获得改良基因的丢失速度也相应升高。而交叉概率太低则 可能导致搜索阻滞。一般取p ，= o 6 0 - 1 0 0 4 ) 变异概率p 。：变异操作使保持群体多样性的有效手段，每代中大约发生 口m l 此变异。变异概率太小，可能使某些基因位过早丢失的信息无法恢复； 而变异概率过高，则遗传搜索将变成随机搜索。一般取p 。= o 0 0 5 - 0 1 。 实际上，上述参数与问题的类型有着直接的关系。问题的目标函数越复杂， 参数选择越困难。从理论上讲，不存在一组适用于所有问题的最佳参数值，随着 问题特征变化，有效参数的差异往往非常显著。如何设定遗传算法的控制参数以 使遗传算法的性能得到改善，还需要结合实际问题深入研究，以及有赖于遗传算 法理论研究的进展。 6 、终止循环的条件 关于遗传算法的迭代过程如何终止，般采用设定最大代数的方法。该方法 简单易行但需要多次调试才能找到现对合适的代数，所以不准确。其次，可以根 据群体的收敛程度来判定，通过计算种群中基因多样性程度，即所有基因位的相 似程度来进行控制。第三，根据算法的最优解连续多少代没有新的改进来确定。 最后，可在采用精英保留选择策略的情况下，按每代最佳个体的适应值变化情况 确定。 遗传算法的性能评估 遗传算法的性能好坏的判断与很多因素有关。最直观也是最重要的因素是看 基于平滑技术及一维搜索的全局优化遗传算法 它能否收敛到全局最优点。关于搜索类算法的性能评估，基本可以归纳为算法的 求解效率和求解质量两个方面。算法的求解效率是比较获得同样的可行解所需要 的计算时问。算法的求解质量是在规定时问内所获得的可行解的优劣。常用和通 用的指标有 1 ) 目标函数值计算次数； 2 ) 在线和离线性能函数”1 ； 3 ) 最优解搜索能力。 2 2 遗传算法的步骤 步骤一：初始化种群。令k = 0 ：设置遗传算法中各参数值；随机生成p o p 个个体作 为初始群体p ( o ) 。 步骤二：适应度评价。计算群体p ) 中各个个体的适应度。 步骤三：选择操作。将选择算子作用于群体。 步骤四：交叉操作。根据选择概率以将交叉算子作用于群体。 步骤五：变异操作。根据变异概率p 。将变异算子作用于群体。群体p ) 经过选择、 交叉、变异操作后得到下一代群体p ( t + 1 ) 。 步骤六：终止条件判断。若终止条件不满足，则转到步骤二：否则，以进化过程 中所得到的具有最大适应度的个体作为最优解输出，终止计算。 2 3 基础理论研究概遗传算法的述 在遗传算法的基础理论研究上，它的相关性质可以通过模式定理和构造块假设 等分析加以讨论，m a r k o v 链也是分析遗传算法的一个有效工具。 2 4 1 模式( s c h e m a ) 理论： ( 1 ) 模式定理 模式表示一些相似的模块，它描述了在某些位嚣上具有相似结构特征的个体 编码串的一个子集，以及了该集合中位串上共同的基因特征。模式的阶是指模式 中所包含有0 、1 确定基因位的个数。模式的定义长度是指模式中从左到右第一个 无关符和最后一个无关符之间的距离。模式的维数是指模式中所包含的位串的个 数，也称为模式的容量。 模式定理：在遗传算子选择、交叉、变异的作用下，那些低阶、定义长度短、 超过群体平均适应值的模式的生存数量， 该定理反映了重要基因的发现过程。 将随着迭代次数的增加以指数规律增长。 重要基因的联结对应于较高的适应值， 第二章遗传算法的基本理论 2 4 遗传算法的现状与展望 遗传算法作为一种对生物进化现象进行仿真的程序，取得了人工遗传的模拟 效果，具有白适应性。在遗传算法的结构中遗传操作和选择机制是两个重要的因 素，其联系可用”遗传算法= 遗传操作+ 选择过程”这个逻辑关系来表示。 从遗传算法被提出，随着研究和应用的不断深入与扩展，1 9 8 5 年在美国召开了 第一届遗传算法国际会议，即i c g a ( i n t e r n a t i o n a lc o n f e r e n c eo r lg e n e t i c a l g o r i t h m ) 。之后，相关的会议杂志层出不穷。在欧洲，1 9 9 0 年起每隔一年举办 一次p p s n ( p a r a l l e lp r o b l e ms o l v i n gf r o mn a t u r e ) 会议；1 9 9 4 年一月，i e e e $ * 经网络委员会( i e e en e u r a ln e t w o r kc o u n c i l ) 出版了第一本“进化计算”专集； 1 9 9 7 年该委员会创办了i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 杂志。 随着i n t e r n e t 技术的发展和普及应用，遗传算法的有关单位建立了大量的专题g a 网站，其中最为著名的是由美国海军人工智能研究中心建立的g a a r c h i v e s 检索网 站( h ! l b ；! ! ! ：i i ! ：j ! ! ：! i ! y ：里i ! g i ! i ! ) 。 遗传算法的商业应用五花八门，覆盖面甚广，比如通用电器公司的计算机辅助 设计系统e n g e n e o u s ，这是一个采用了遗传算法以及其他传统的优化技术做为寻优 手段的混合系统( h y b r i ds y s t e m ) 。e n g e n e o u s 已成功地应用于汽轮机设计，并改善 了新的波音7 7 7 发动机的性能，这是目前正在研究和应用的一个重要方面。 所有这些都表明了遗传算法的学术意义和应用价