（控制科学与工程专业论文）进化计算在优化问题中的应用.pdf

摘要 在科学技术和工程实践等诸多领域，许多问题都可归结为某种函数的最优 化这类数学模型。进化算法作为处理复杂函数最优化、多目标最优化问题的一 种有效算法，正目益受到人们的重视。本文对带约束的单目标、多目标进化算 法进行了研究。 在进化过程中，可能会出现过早收敛现象，这主要是因为种群中出现了超 级个体，按照一定的选择策略，该个体很快会在种群中占据绝对优势，从而使 算法过早的收敛于一个局部的最优解，本文中有对超级个体的适应函数进行调 整，从而控制该个体的选择概率，或增加个体的变异率来增加种群的多样性。 同时，不同的群体规模和选择策略对算法性能的影响起到举足轻重作用。 本文通过对进化计算中交叉算子和变异算子产生新个体的机理，以及实际 问题的特征进行分析后，对不同的交叉算子，和变异算子进行组合，并结合模 拟退火算子相结合，该算子的主要优点在于：能够使种群个体的基因值更加有 效地保持多样性，克服传统交叉算子下算法易于陷入局部最优解的缺陷；并且 能够引导遗传算法在最优解邻域内搜索，从而提高算法的优化速度。 旅行商问题是典型的n p 难问题。在实际应用中具有广泛的代表性。因此本 文中将旅行商问题作为测试本文改进的遗传算法，对不固定起点和终点的旅行 商问题的进化算法进行改进。这种算法将不固定起点和终点的旅行商问题化简， 根据化简以后的问题，设计了一种新的编码方法和解码方法针对编码的特点， 设计了一种新的直接产生可行后代的杂交算子和变异算子。为提高算法的收敛 速度，结合了一个局部搜索算子改进杂交后得到的个体并且证明了算法的全局 收敛性，计算机仿真结果表明算法是有效的。 关键词：进化计算；函数优化；组合优化；遗传算法；t s p a bs t r a c t i nm a n yf i e l d so fs c i e n c ea n dt e c h n o l o g y , i n d u s t r i e sa n dp r a c t i c ee t c ，t h e r ea r ea 1 0 to fp r o b l e m sc a nb ec o n v e r t e di n t ot h ek i n do fm a t h e m a t i c a lm o d e lo ff u n c t i o n o p t i m i z a t i o n e v o l u t i o n a r ya l g o r i t h mi so n eo ft h em o s te f f e c t i v ea l g o r i t h m sf o rh a r d o p t i m i z a t i o na n dm 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 s ，w h i c ha r ea t t a c h e dm o r e a n dm o r ei m p o r t a n c et o t h i sp a p e rs t u d i e se v o l u t i o n a r ya l g o r i t h m sf o rs i n g l e o b j e c t i v ea n dm u l t i - o b j e c t i v eo p t i m i z a t i o n i nt h ec o u r s eo fe v o l u t i o n ，t h e r em a yb ep r e m a t u r ec o n v e r g e n c e i ti sm a i n l y b e c a u s et h es u p e ri n d i v i d u a lh a sa p p e a r e di nt h ep o p u l a t i o n ，a c c o r d i n gt oac e r t a i n s e l e c t i o ns t r a t e g y , t h i si n d i v i d u a lw i l lo c c u p yt h ea b s o l u t ep r e d o m i n a n c ei nt h e p o p u l a t i o ns o o n ，a n dt h i sm a k e st h ea l g o r i t h mt oc o n v e r g ee x p l o i t a t i o nt o oe a r l y i n t h i sp a p e r , t h es o l u t i o na b o u tt h i sq u e s t i o ni st oa d j u s tt h ef i t n e s sf u n c t i o no ft h e s u p e ri n d i v i d u a lt oc o n t r o li t s e l e c t i o np r o b a b i l i t y , o rt oi n c r e a s et h em u t a t i o n p r o b a b i l i t yo ft h ei n d i v i d u a lt oi n c r e a s et h ed i v e r s i t yo ft h ep o p u l a t i o n m e a n w h i l e ， d i f f e r e n tp o p u l a t i o ns c a l ea n ds e l e c t i o ns t r a t e g yp l a yav e r yi m p o r t a n tr o l ei nt h e a l g o r i t h mf u n c t i o n i nt h i sp a p e rd i f f e r e n tc r o s s o v e ra n dm u t a t i o no p e r a t o ra r eu s e d ，a n dc o m b i n e d w i t hs i m u l a t e da n n e a l i n g t h ea b i l i t yt om a k et h eg e n e t i cv a l u eo fi n d i v i d u a ls t o c k s i sm o r ee f f e c t i v ei nm a i n t a i n i n gd i v e r s i t yo fp o p u l a t i o n ，u n d e rt h et r a d i t i o n a l c r o s s o v e ra l g o r i t h mi se a s yt of a l li n t ol o c a lo p t i m a ls o l u t i o no ft h ed e f e c t ；a n dc a n g u i d et h eg e n e t i ca l g o r i t h mi no p t i m a ln e i g h b o r h o o ds e a r c h , t h e r e b ye n h a n c i n gt h e s p e e do fo p t i m i z a t i o n t h et s pi ss t u d i e da n dan o v e lg e n e t i ca p p r o a c hf o rt s pw i t h o u tf i x e ds t a r t i n g p o i n ta n de n dp o i n ti sp r o p o s e d t om a k et h ep r o p o s ea l g o r i t h me f f e c t i v e l y , t h e s o l u t i o nr e p r e s e n t a t i o ni ss i m p l i f i e df i r s t a sar e s u l las i m p l i f i e de n c o d i n gs c h e m e i sp r e s e n t e d ，a n da ne f f i c i e n td e c o d i n gs c h e m ei sd e s i g n e d t h e nb a s e do nt h e s p e c i f i ce n c o d i n gs c h e m e ，t h ee f f i c i e n tc 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 e p r o p o s e d i tc a na l w a y sg e n e r a t ev a l i dt o u r i no r d e rt oe n h a n c ei t sa b i l i t yo f e x p l o r a t i o n ，al o c a ls e a r c hs c h e m ei si n t e g r a t e di n t ot h ec r o s s o v e ro p e r a t o r b a s e do n t h e s e ，an o v e la n de f f e c t i v eg e n e t i ca l g o r i t h mf o rt s pi sp r e s e n t e da n di t s c o n v e r g e n c et og l o b a lo p t i m a ls o l u t i o ni sp r o v e d t h es i m u l a t i o nr e s u l t ss h o wt h e e f f e c t i v e n e s so ft 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 ：e v o l u t i o n a r yc o m p u t a t i o n ；f u n c t i o no p t i m i z a t i o n ；c o m b i n a t o r i a l o 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 m s ；t s p i i 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：j 堕_ 生 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部 内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：隧堡2 导师签名： 辞 日期：、鲨! ! ： 日期：! ! ：兰 武汉理j 亡人学硕十学位论文 1 1 进化计算概述 第1 章绪论 二十世纪五十年代末，国内外一些科学家尝试性地在计算机中模拟生物进 化过程，将生物进化的思想引入到工程问题中，成为一种解决优化问题的工具， 这些创造性的工作成了进化计算的雏形。但在当时进化计算的研究进展十分缓 慢，收到的效果也不甚理想。其根本原因是缺乏一种通用的编码方式，由于算 法本身需要一定的计算量，尤其是最初只能通过变异改变基因结构，而不能通 过交叉的方式，这样增加了算法的迭代次数，由于当时的硬件还无法满足要求， 因而早期的算法取得的效果并不明显。 1 9 6 3 年，德国科学家i r e c h e n b e r g 教授等把生物变异的思想应用到优化物 体形状中并逐渐形成进化策略( e v o l u t i o n a r ys t r a t e g i e s ，e s ) 。利用生物基因突变 的思想来随机改变参数值，从而获得了较好的效果。随后，他们对这种方法进 行了深入地研究，在后来的发展中形成了此算法。e s 是专门为求解参数优化问 题而设计的，隐含并行性和群体全局搜索性是它的两个显著特征，对于一些复 杂的非线性系统求解具有很好的性能。e s 使用突变算子，其较强的分散性能够 较好，能够跳出局部极值点的能力比较强，但是以此付出的代价是收敛速度有 所降低。提高e s 的收敛速度和全局搜索能力，一直是e s 研究的主要内容之一。 理论分析表明突变算子具有较强的局部搜索能力，而均匀突变算子和突变算子 具有较强的局部逃逸能力。1 9 7 5 年，美国密歇根大学的j h o l l a n d 教授提出了遗 传算法( g e n e t i ca l g o t h r 锄， g a ) 和位串编码方式。开辟了进化计算的先驱，这 种位串编码既适用于变异操作，也可适用于交叉操作，并且强调把交叉操作作 为主要的遗传操作。j h o l l a n d 早期的工作为遗传算法乃至进化计算的发展奠定 了基础，这种思想逐渐为人们所接受。 随后，出现了进化规j z i ( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 、遗传编程( g e n e t i c p r o g r a m m i n g ，g p ) 。后来，把这一类算法统称进化计算( e v o l u t i o n a r y c o m p u t a t i o n ， e c ) 或进化算法( e v o l u t i o n a r ya l g o r i t h m s ，e a ) 。【l 】进化计算与其它 优化算法相比，具有十分鲜明的特色，进化计算模拟生物的进化过程，发展成 为一类通用的算法，广范适用于科学计算，工程应用，经济预测，模糊控制等 武汉理工人学硕士学位论文 多个领域。由于它的独特的原理和极强的解决问题能力，获得了许多学者的重 视与研究。 进化计算e c 有以下几个主要特点：1 、自适应性，自适应方法具有很强的 鲁棒性，对问题几乎没有要求，适用于多种问题；2 、随机性，随机优化算法可 以解决许多非线性系统的全局最优化问题；3 、潜在的并行性，有着非常高的 计算效率。这三个特点使得e c 的研究和应用迅速成为国际学术界和工程界关注 的热点。【2 】 2 0 世纪8 0 年代后，进化计算和遗传算法进入了快速发展期。很多以进化计 算，遗传算法为主题的国际会议在世界各地定期召开。同时，关于进化计算的 学术活动也非常活跃，随着计算机硬件的发展，进化计算对计算机速度的要求 不再是制约其发展的因素。 在二十世纪的9 0 年代，e c 在国内外被关注的程度空前之高。其原因不仅 是e c 有与众不同的特色、广阔的发展前景；也是因为e c 存在的缺陷及发展余 地。进入了二十一世纪，不断有e c 的各种算法的改进算法提出，e c 一直没有 停止发展的脚步。 但是，e c 存在的问题和缺陷也不能忽视。在早期人们就注意到进化计算过 早收敛即俗称“早熟 的问题，也是许多学者关注、研究的问题。另一个重要 问题是e c 的计算效率的问题。针对这些问题，许多学者提出了改进的算法，如 采用的层次结构对染色体进行编码的结构遗传算法，允许冗余基因存在，因而 使g a 具有避免“早熟”的能力和适应环境变化的能力；如在遗传算法中采用 多个群体，对某些问题来说，可以提高计算效率，缓解早熟问题。【3 】改进的g a 还有很多，如模拟退火与g a 结合，遗传算法与免疫相结合等，此类的算法数 量之多，以致无法一一列出。据此，可以期望，进化计算效率要明显高于其它 方法。 在新世纪，进化计算如雨后春笋一样在各个领域得到广泛的应用。进化计 算在人工智能、机器学习、经济学、控制与决策、工程优化等领域获得了巨大 的成功。进化计算与神经网络一起成为对认知过程研究的重要工具。进化计算 具有求解的有效性，易于实现模拟仿真，并且容易与其它方法相合等优点。可 以预料，在不远的将来，随着理论研究的深入，进化计算的领域必定会不断拓 广，进化计算将会取得长足的发展。 2 武汉理：r = 大学硕十学位论文 1 2 三种进化算法的主要区别与联系 三种算法都是通过模拟生物种群的进化现象，并且可以解决复杂优化问题 和非线性优化问题，三种算法虽然相似之处很多，但在具体实现上却有较大的 差别： 1 ) 进化规划和进化策略都把变异操作作为主要的搜索算子，而在标准遗传 算法中，变异只处于次要地位； 2 ) 交叉算子在标准遗传算法中起着重要作用，而在交叉算子进化规划中则 被完全忽略掉，变异算子完全取代交叉算子； 3 1 标准遗传算法和进化规划都强调随机选择机制的重要性，而对于进化策 略来讲，选择是完全确定的，并不是随机选择的。进化规划和进化策略一般会 把某些个体确定性地排除在选择复制之外，而标准遗传算法一般对每个个体都 指定一个非零选择概率，任何个体都有机会被选中；在解的编码策略上，遗传 算法一般将原问题的解空间进行编码，然后再施行遗传操作，它强调基因结构 的变化对适应度的影响，而进化策略和进化规划一般直接在解空间上进行操作， 强调进化过程中搜索方向和步长的调节。实际上，这些算法都是对生物进化过 程的模拟，强调了自然进化的不同方面：遗传算法强调染色体的操作，即个体 基因结构的变化对其适应度的影响，进化策略强调个体级的行为变化，进化规 划则强调种群上的行为变化。一般认为，遗传算法是一种较为通用的求解方法， 而进化策略和进化规划更适宜于求解数值优化问题。在实际应用中，这些算法 互相借鉴，并且有着相互融合的趋势，在某些情况下，其界限并不明显。 1 3 研究目的和意义 1 3 1 研究目的 传统的解析计算，工作在纯数学基础之上，适用于较容易建立出数学模型 的应用，并且能用数学方程式把输入输出关系用传递函数的形式表示出来，而 且需要这个方程容易用解析方法较快的求出其精确解。总而言之，就是待解的 问题能够精确的进行数学形式化。 武汉理工大学硕十学位论文 然而，解析计算来解决某些现实中的复杂问题并不总是可行的，通常会出 现各种各样的困难。这是因为，大部分现实的问题非常的复杂，有时甚至复杂 到难以准确地定义出来，以致于基本不可能建立出数学模型，即便能建立出数 学模型，或者是所建立的数学模型呈现出高度的非线性。对某些问题而言，问 题本身就是不确定或者不精确的。 对于解析计算，虽然可以利用某些策略减小计算量，比如分支界定法等策 略，但是最坏的情况时间复杂度是指数级别的，计算量相当大。当问题规模达 到一定的程度的时候，现有的计算机性能根本达不到如此大的计算量。 相比之下，可以采取近似算法，近似算法的时间复杂度比较低，而且对于 大多数问题，要求输出结果不需要全局最值，而只是较优值。对于随机算法， 如果针对的是判定问题，我们可以以较大的概率得到正确输出。若针对的是优 化问题，输出的解依赖于算法的多个方面，输出解的性能不太稳定，但是能以 相对较大概率得到性能较好的解。 进化计算本身就是一种近似算法，进化计算对于这些复杂的问题具有明显 的优势，它不依赖求解问题的精确数学表达式。对于某些应用，或许不需要产 生太精确的解，只需要得到一个相对于精确解误差不大的近似解。一般说来， 基于进化计算开发出来的算法其本质上是自适应的，因此，进化计算能适应环 境和问题的变化，这也是达尔文进化理论的精髓所在。t 3 】 进化计算为复杂的系统优化问题提供了通用框架，它不依赖于问题的具体 领域，对不同的问题有着相当强的鲁棒性，特别是在优化问题上，函数优化， 组合优化，以及生产调度优化以及控制系统的优化。这些都是进化计算的经典 应用领域，也是对进化计算进行性能评价的实例。 进化计算的算法设计是研究和应用的核心，而进化计算其中最基本并且最 具代表性的就遗传算法莫属了。而进化策略则侧重于数值分析，偏向计算机程 式表现以及人工智能行为仿真的则是属于遗传程序设计的范畴了。 1 3 2 国内外研究现状。 进化算法的研究近年来有了很大的发展，不仅是理论，还有算法和应用的 发展。进入8 0 年代，进化计算得到了蓬勃发展，无论是理论研究还是应用研究， 都已经成为非常热门的课题，尤其是遗传算法的应用研究显得格外活跃，不但 它的应用领域扩大，而且利用遗传算法进行优化和规划的性能也明显提高，同 4 武汉理工人学硕士学位论文 时遗传算法在产业应用方面的研究也在不停的探索之中，表1 1 中总结了目前进 化计算的应用领域。尽管如此，一些新理论和新方法在应用研究中也得到了快 速的发展，这无疑给遗传算法的发展增添了新的血液，促进了理论本身的加速 发展。 表1 - 1 遗传算法的主要应用领域 应用领域说明 控制过程控制，运动控制 规划 生产调度，港口作业 组合优化旅行商问题，背包问题 设计通信网络拓扑设计，建筑布局优化设计 图像处理模式识别， 信号处理滤波器设计 机器人路径规划 人工智能模拟人的操作行为 随着在应用领域的不断发展，遗传算法的研究不断呈现出新动向和新特点。 基于遗传算法的机器学习( g e n e t i cb a s em a c h i n el e a r n i n g ) 是一个新的课题，其特 点是把遗传算法从历来的离散搜索空间的优化搜索扩展到具有规则生成功能的 机器学习算法。这一新的学习机制为解决人工智能中的若干问题，如知识获取， 知识总结和优化带来了希望。【4 】 遗传算法与神经网络、模糊理论、混沌理论和其它智能计算方法相互渗透 和结合是进化计算发展的一个新的趋势。随着理论不断的发展，将对2 l 世纪的 智能计算的发展具有十分重要的意义。并行计算和多目标优化的进化计算研究 也十分活跃，这一研究不仅是进化计算本身的发展进步，而且对于智能计算的 体系结构研究都是十分重要的。 1 4 论文架构 本文对进化计算进行了探索，首先回顾了进化算法的研究起源，研究目的， 及国内外研究现状。其次，详细分析了进化算法中的遗传算法，包括s g a 、m o g a 等，并指出这一代算法研究的成绩与不足；然后，对多目标进化算法作了全面 分析，指出其特征是强调效率，以精英保留策略实现机制，对多目标进化算法 5 武汉理丁大学硕士学位论文 的研究趋势作了展望和预测。 论文第二章对约束优化和数值优化作了概述，在科学技术和经济管理等诸 多领域，许多问题都可归结为某种函数的最优化这类数学模型。进化算法作为 处理复杂函数最优化、全局最优化和多目标最优化问题的一种有效算法，已被 普遍应用。本文对带约束的单目标、多目标、约束优化进化算法进行了研究， 提出了新的改进算法并进行实验仿真。 针对进化算法计算量大、局部搜索能力弱的不足，把一种数学试验方法 适应度函数的改变，使新的进化算子具有相似于传统最优化算法的局部搜索特 性，提高了算法的搜索效率。遗传算子的混合改进是本文的研究方向，其中适 应度函数的选择非常重要，它必须具有较好的鲁棒性，为此，本文深入的分析 与研究了适应度函数的各种变换的特点和遗传过程中种群变化的特点，提出了 新的适应度函数：即目标函数映射、适应度函数定标等，并给出了采用改进的 适应度函数求解最大化问题或最小化问题的实现方法。试验结果表明该适应度 函数和其他算子的配合，极大地提高了算法的性能。本文还提出了将进化算法 与模拟退火算法相结合的方法，适应度函数进化代数增加而逐渐增加的动态变 化的适应度函数，对于某些优化问题具有较好的效果。 对于多目标最优化问题，本文提出了求解约束最优化问题的一种新的进化 算法。算法通过把约束优化问题转化为多目标规划，对于多目标优化，构造了 一个同进化代数有关的变适应值函数。这样定义的变适应值函数能使种群中的 潜在解逐渐增加并且保持其多样性。该方法能有效处理约束问题，特别是紧约 束问题。用类似的思想给出了解决约束多目标最优化的一种新的进化算法，计 算机仿真显示这种处理单目标、多目标的方法是有效的。该算法把约束问题转 化为多目标最优化，用决定约束的重要性来确定选择算子，利用求解多目标最 优化类似的方法，直接求出问题的解而不用逐层求解。 本文第三章对n p 问题作了深入的探讨，尤其是t s p 问题。在t s p 问题中，深 入对遗传算法的各种编码方式，和遗传策略进行详细地描述，最后进行了实验 仿真。 本文第四章介绍了目前主流的进化计算框架，采用计算计算框架大大提高 了研究效率，对创建自己的算法也大大减少了编码量，这些进化计算框架经过 以前许多科学家的努力，已经具备一定的规模，而且稳定性和有性效方面都已 经符合要求。本文中，采用了m i t 的进化计算框架o a l i b 仓j j 建新的算法，并总结 了根据此进化计算框架创建一般进化算法的步骤。 6 武汉理工人学硕士学位论文 本文第五章对进化算法进行实验，把结果与传统的优化方法对比，用直观 的图形和表格显示，并对算法的搜索过程进行分析，还对算法收敛性作了分析。 而且对全文进行了总结，从理论、方法、应用等不同层面，综述了进化计算一 些重要研究领域的研究进展，主要包括数值优化、组合优化，指出了一些有待 研究的重要问题和改进之处，对其未来的发展作了展望。 7 武汉理工大学硕十学位论文 第2 章。遗传算法与数值优化 2 1 数值优化问题的数学模型 2 1 1 优化问题的一些传统方法 所谓优化，就是在已知问题的可行解中搜寻出最优解的过程，一个好的优 化方法可以更有效地解决问题，并且解决问题所花费的成本更低。 优化问题一般分为两类，根据目标函数的性质，优化问题可分为线性优化 问题和非线性优化问题。顾名思义，若目标函数是线性函数，则该优化问题就 是线性的；相反，若目标函数是非线性函数，则该优化问题就是非线性的。根 据目标函数是否显示包含或者隐式约束条件，可以把优化问题分为无约束优化 问题和约束优化问题，约束优化问题至少有一个参数被约束，对于无约束优化 问题，这类问题的求解往往比较容易，在现实生活中，大多数优化问题往往都 是约束优化问题。【5 】本文着重讨论约束优化问题。 约束优化问题是在自变量满足约束条件的情况下，目标函数最小化的问题， 其中约束条件既可以是等式约束也可以是不等式约束。在现实生活中，大多数 实际问题是包含约束条件的，这使得约束优化问题与实际息息相关。实际上， 很多难于处理的问题都是包含约束条件的，这使得约束优化问题在理论上非常 具有挑战性。 表2 - 1 传统优化方法 传统优化方法 线性规划方法嘲非线性规划 解析法无约束优化算法约束优化算法 随机搜索法复合方法 图解法 快速下降法罚函数法 共轭梯度法 武汉理t 大学硕+ 学位论文 表2 - 1 列出了一些传统的优化方法。传统的优化方法通用性较差，某种传 统优化可能只对一类问题有效，不适合解决多种类型的问题。对于优化问题， 用传统优化方法得到的解依赖于随机选择的初始解，如果最开始选择的初始解 不太理想，得到的最终的解可能会陷入局部最优。只有最初选择的初始解在最 优解可能的区域内，才可能得到全局最优解，并且，传统的优化方法很难处理 离散变量和非连续性问题。也不能用于并行计算，但是，并行计算能够显著提 高算法的效率。因此，有必要采用一种高效的优化方法来解决优化问题。有许 多优化问题已经用进化算法得到了很好的解决，事实表明，进化算法在解决优化 问题是非常有效的。 2 1 2 最优化问题数学模型 最优化问题是遗传算法的经典应用领域，采用传统的方法对于解决大规模， 多峰值及多态函数或者含有离散变量问题的有效性存在许多困难。遗传算法简 单，高效以及鲁棒性普遍适用于数值优化问题。目前已经有很多数值优化问题 用遗传算法取得相当好的效果，普遍应用于各种工程问题，并取得了长足的发 展。 一般地，数值优化问题与目标函数和约束条件两部分组成，用数学方程式 表达如下： 目标函数： o p t i m i z e f ( x ) ，f ( x ) = ( ，而，吒) 约束条件： 解空间 z = ( ，x 2 ，x ) r ” g i ( x ) o ，i = 1 ，m 乃( 力o ，= 1 ， 玉吩 工= ( ，x 2 ，吒) s c x 9 武汉理工人学硕士学位论文 其中，x 为变量的定义域，s 为满足所有约束条件的可行解的集合，称为可 行域，可行域中的目标函数最小或者最大解称为最优解，通常来说，采用最小 解的形式。对于最大值问题，可以将目标函数乘以( 一1 ) 即g ( x ) = 一f ( x ) ，或者对 1 目标函数求倒，令g ( 力= _ 来转化为最小值问题求解。 jt x ) 当x r 4 ，即x 为实数空间，目标函数和约束条件均为线性表达式，最优 化问题是线性规化问题，反之，则为最优化问题为非线性规化问题。实践证明， 遗传算法作为现代最优化手段，有着对目标函数要求低，并且容易实现、稳定 性好、求得全局极值的概率高等诸多优点。遗传算法和其衍生出来的其它方法 应用于大规模、多峰值函数。即使目标函数含有离散变量，遗传算法也仍然能 够适用。遗传算法对全局优化问题是非常适合的，求解速度和质量超过一般的 传统算法，是一种高速快速算法。 2 2 适应度函数 2 2 1 适应度函数的创建 遗传算法在搜索的过程中几乎不用来自外部的其它信息，而是靠算法本身 的一些机制来完成搜索的，即靠目标函数的适应度作为评价的依据。遗传算法 的目标函数可以是不连续的，甚至是不可微的，而且定义域可以为任意集合。 对目标函数的唯一要求是，对不同的输入变量产生的结果，可以比较其结果的 性能。因此，遗传算法对环境的要求不高，这一特点使得遗传算法的应用范围 非常之广。 7 1 在具体应用中，要根据具体问题的本身特点和要求来设计适应度函数。适 应度函数是评估选择操作的依据，它的设计将直接影响到遗传算法的性能。通 常来讲，适应度函数要在比较排序的基础之上计算选择概率，因此，适应度函 数的值最好取正值，并且在一定的区间之内。 适应度函数的设计通常有几下几种类型： 1 ) 目标函数映射 如上节所讲的，把最大值问题转化为最小值问题，如求取效能函数或者利 l o 武汉理工大学硕士学位论文 润函数的最大值，上节提到把问题数学模式函数乘以1 ，但这种方法对于某些问 题来说还不足以保证目标函数的值为非负，可以采用以下方法来改造目标函数 m ，= 1 黧籍 协， 显然，存在多种方式来选择，l 可以是一个合适的输入值，也可以 采用进化过程中g ( x ) 的最大值，最好与群体无关。 2 ) 适应度线性定标 遗传算法在处理小规模群体时经常会出一些不利于优化的现象和结果。在 算法进行的初期，往往会出现一些异常的个体，若按照比例选择，这些异常个 体可能占据很大的比例，可导致算法的“早熟 现象，不利于算法的进行。显 然，应该想办法降低这些异常个体的竞争力，可以通过缩小相应的适应度函数 值来实现。采用对适应度的放大或缩小调整，这种方法被称作适应度定标。【8 】 原适应度函数为( 工) ，定标后的适应度函数为厂t ( 功，则线性定标为： ( z ) = a f ( x ) + b ( 2 2 ) 同时，改变参数后的适应度函数必须满足以下两个条件。 i = ni = n 厂b ) 厂( 薯) 生l 一= 上l 一 ( 2 3 ) 以疗 即定标后的适应度平均值要等于原适应度值。 厂一= c 岫厶( 2 - 4 ) 定标后的适应度函数最大值厂一要等于原适应度函数平均值厂( 功所指定 的倍数。其中。是为得到所期待的最优群体的个体复制数。实验表明，对于一 个不大的群体而言，通常情况下。一般取值范围为( 1 0 2 0 ) 。 9 1 图2 1 是 适应图定标的示意图。 武汉理工大学硕士学位论文 ，i n o 2 f i 啦 f i 甜氅 o 厂m 轴 ， r 一 o 加n 呕向积 图2 - 1 适应度定标 此外，还有盯截断法和乘冥法对适应度函数做出相应的处理。 其公式如下： f f - 一( 厂一c ) f = f 置 2 2 2 适应度函数对算法性能的影响 ( 2 5 ) ( 2 6 ) 可以采用上面描述的适应度函数的设计方法来抑制算法的过早收敛现象以 及随机漫游现象，从而提高遗传算法的优化搜索性能。适应度函数虽然与遗传 算法操作中的选择操作直接相关，但它对遗传算法性能的影响还表现在其它方 面。 1 ) 适应度函数影响遗传算法迭代的终止条件。当适应度函数的最小值或者 已知最优解的下限已经确定时，通常情况下，以已知最优解作为算法迭代终止 条件。但是，许多优化问题中，适应度最大值往往并不明确，其本身就是搜索 对象，因此适应度下限很难确定，所以，若发现算法中个体进化已经趋于稳定， 则可以作为算法迭代终止的条件。u o 2 ) 由于遗传算法仅靠适应度函数值来评估个体和引导搜索，但是实际问题 中，问题的约束条件并不能明确地在适应度函数中表示出来，因此，求解约束 问题需要采用一些对策。从理论上讲，我们完全可以在进化过程中，每进化一 次，就对下一代新的个体是否违背约束条件进行检测，如果违背约束条件，则 1 2 t；。喝；i|l， 扔 武汉理工大学硕士学位论文 放弃此个体，相反，则此个体作为有效个体参与算法的继续进行，实验表明， 此方法只对约束限制不是很多的问题有效。对于约束较强的问题，寻找一个有 效个体的难度很大，甚至几乎找不到合适的个体参与算法的继续进行，从而导 致算法失败。 作为对策，我们可以采用处罚方法，针对个体违背约束条件的不同程度给 予惩罚，使得违背约束条件严重的个体适应值快速下降，降低此类个体的竞争 力。通过惩罚方法，约束问题可以转化为非约束类问题。 i l l 其公式如下： 厂t ( z ) = ，毗包( x ) ( 2 7 ) 1 = i 为惩罚函数，f 为惩罚系数。在实际应用中，r 通常根据不同的问题取不 同的值，这样可以使违背约束的个体惩罚适到好处。 2 - 3 线性约束问题的数学模型 对于只含上下限的最优化问题可以描述为： m i n i m i z e f ( x l ，恐，吒) 约束条件为： 玉u i ，f = 1 ，2 ，刀 上述优化算法用遗传算法是很容易实现的。 m i n i m i z e f ( x l ，x 2 ，) 约束条件： a l i + + 口l 。x = 岛 ； a m l 五+ + 。= 吃 c l l 五+ + c 1 。x = d l c f l + + 毛= 磊 u if = l ，2 ，疗 以上问题的矩阵形式为： m i n i m i z e f ( x ) 武汉理工人学硕+ 学位论文 约束函数： a x = b c x d ，z u 式中， x = ( _ ，) r ，m = ( a j ) ，6 = ( 和，包) 7 ，c - - ( ) ，d - ( d i ，一，d 。) r ， ，= ( ，) r ，“= ( ，) r ，( f = 1 ，力；= 1 ，聊；后= 1 ，j ) 。 上述约束优化的目标函数f ( x ) 不仅可以是线性函数，还可以是非线性函数。 通常情况下，对约束条件的处理步骤如下： 1 由矩阵原理消除等式约束。 假设a x = b 中有n 1 个独立等式，则其中m 个变量 ，气，气( ，) 1 ，2 ，刀) ) 可以由剩下的n - m 个变量表示。具体操作方法 如下： 将矩阵a 在第jy u ( j ，乙) ) 处分割成两个分矩阵4 ，4 ，类似地，分 割向量，。对应分矩阵和向量加下标表示。这样，等式约束成为： 4 x 1 + 4 x 2 = 6 ( 2 8 ) 由于4 的逆矩阵4 - 1 存在，x 1 = 4 b 一4 - 1 4 x 2 ，这样，变量，气，_ , - l - 用 剩余的变量线性表示。对于变量( 歹= 1 ，m ) 的上下限约束勺，去掉 其中所有的薯，则变换成下列新的不等式： 五4 - 1 b - 4 _ 4 ，“i ( 2 - 9 ) 原问题中的不等式c x d 变换成： c l 石1 + c 2 2 2 d ( 2 1 0 ) 将x 1 代入上式转化为： c l ( 4 1 6 4 1 4 x 2 ) + c 2 x 2 d ( 2 - 1 1 ) 1 4 武汉理工人学硕+ 学位论文 将m 个变量，x i , ，气消除后，最终的约束有以下的不等式组成： 1 ) 原上下限约束乞石2 2 ) 新增加不等式约束4 o ， 七 羔：1 k = l 若已知两个可行解五和屯，并且五 x 2 ，则k k ，即： 童心 v ( x i - - v ( 吼) 恐 0 ( 2 1 8 ) 另一可行解为毛，欲判断毛与五之优劣，只需要求解下面的线性规划问题： 最小化 约束条件 z ：兰 v ( 以) 毛一v ( 吼) 屯 ( 2 - 1 9 ) 羔 v ( 吼) 五一v ( 吼) 而 0 ( 2 2 0 ) 丘= i 心 0 ，圭：1 ( 2 2 1 ) k = l 2 6 0 ，毛 玉 o ，毛一五 0 ，毛 f i ，j、 口 ： 有则在存解题问划规 匕 以若 武汉理工大学硕十学位论文 在上述判断中权得作比睁1 ，2 ，q ) 为一种非精确的偏好信息，包含 在可行解的比较之中，称之为非精确偏好包含。我们按照以上的数学模型构造 一种交互式多目标遗传算法： 1 ) 随机产生若干个可行解的初始种群，将群体中个体的目标值做正规化处 理。 2 ) 有差异地挑选几个个体，由决策者进行比较判别优劣性，产生一组非精 确偏好包含的约束。若不能进行有差异的挑选，即认为已经获得一组满意解， 算法终止。 3 ) 建立线性规划模型进行个体比较，对当前种群的个体进行排序。 4 ) 依据个体的p a r e t o 秩，计算适应度值，并进行分享操作。 5 ) 选择个体，完成交叉、变异等遗传操作，产生新一代个体。 6 ) 世代更迭，每隔一定的代数，需要执行非精确偏好包含，转向步骤2 7 ) 若迭代次数超过设定值，则终止算法；否则转向步骤3 。 2 6 小结 本章对约束优化和数值优化作了概述。进化算法作为处理复杂函数最优化、 全局最优化和多目标最优化问题的一种有效算法，已被普遍应用。本章对带约 束的单目标、多目标、约束优化进化算法进行了研究，提出了新的改进算法并 进行实验仿真。 针对进化算法计算量大、局部搜索能力弱的不足，把一种数学试验方法 适应度函数的改变，使新的进化算子具有相似于传统最优化算法的局部搜索特 性，提高了算法的搜索效率。遗传算子的混合改进是本文的研究方向，其中适 应度函数的选择非常重要，它必须具有较好的鲁棒性，为此，本文深入的分析 与研究了适应度函数的各种变换的特点和遗传过程中种群变化的特点，提出了 新的适应度函数：即目标函数映射、适应度函数定标等，并给出了采用改进的 适应度函数求解最大化问题或最小化问题的实现方法。试验结果表明该适应度 函数和其他算子的配合，极大地提高了算法的性能。本文还提出了将进化算法 与模拟退火算法相结合的方法，适应度函数进化代数增加而逐渐增加的动态变 化的适应度函数，对于某些优化问题具有较好的效果。 武汉理工人学硕士学位论文 第3 章遗传算法与组合优化 3 1 1 组合优化问题概述 3 1 1n p 幂口n p g 概念 在说明n p 问题之前，先说明一下时间复杂度。时间复杂度并不是表示某个 程序解决问题需要花费的时间，而是当问题的规模扩大后，程序需要的时间长 度随着问题规模增长而增长的速度。如果说程序处理花费的时间随着数据量的 增大始终是不变的，也称常数级复杂度；如果数据规模变得大，花的时间也跟 着呈线性增长，这个程序的时间复杂度就是o ( n ) ，比如找n 个数中的最大值； 而像冒泡排序、插入排序等，其算法复杂度为o ( n ! ) ，称为阶乘级复杂度。还有 一些穷举类的算法，所需时间长度成几何阶数上涨，这就是o ( a n ) 的指数级复 杂度。容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论 如何都远远大于前者：一种是o ( 1 ) 、o ( 1 0 9 ( n ) ) 、0 ( n a ) 等，我们把它叫做多项 式级的复杂度；另一种是0 ( 如) 和o ( n ! ) 型复杂度，它是非多项式级的，其复杂 度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需 要多项式级的复杂度，非多项式级的复杂度求解往往会花费相当长的时间，除 非数据的规模非常小【2 5 1 。 如果一个判定性问题的复杂度是该问题的一个实例的规模为n 的多项式函 数，则我们说这种可以在多项式时间内解决的判定性问题属于p 类问题。p 类问 题就是所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式 时间的算法，也许根本不存在，比如找出无向图中的哈米尔顿回路问题，但是 我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个 答案是否正确。比如说对于哈米尔顿( h a m i l t o n ) 回路问题，对于一个任意的回路， 我们很容易判断它是否是哈米尔顿回路，只要判断是否所有的顶点都在回路中 就可以了。这种可以在多项式时间内验证一个解正确与否的问题称为n p 问题， 换句话就，n p 就是能够在给定正确信息下在多项时间内验证的判定问题。显然， 所有的p 类问题都是属于n p 问题。但是，并非所有n p 问题不一定都是难解的 武汉理工人学硕士学位论文 问题，比如简单的数组排序问题是p 类问题，虽然方法容易，但是无论用什么 方法，都是阶乘级复杂度，因为打印出结果总得用阶乘级的时间。但是p 属于 n p ，所以也是n p 问题【2 引。 对于某些