（管理科学与工程专业论文）遗传算法求解多模态优化问题的研究.pdf

中文摘要 如何应用遗传算法求解多模态优化问题已经成为遗传算法乃至进化计算领 域的一个广受关注的问题，它也是遗传算法理论和实际应用的基础。这方面的成 果层出不穷，但理论研究相对薄弱。特别是研究外部参数如何影响遗传算法求解 多模态优化问题的性能这方面仍然是个空白，本文着重进行了这方面的理论研究 并对相应结论进行了推广。推广后的理论结果被用于改进遗传算法对多模态优化 问题的搜索性能。本文的主要研究内容包括： 1 对多模态优化问题和遗传算法进行了简单回顾，对应用遗传算法解决多 模态优化问题的研究现状进行了分析，介绍了遗传算法的基础理论及其发展趋 势。 2 对经w a l s h 变换后的基因池遗传算法的无限种群模型进行了分析，刻画 了“双峰函数”局部极值解的适值差与基因池遗传算法的搜索性能之间的关系， 对上述理论结果进行了理论推广和实验验证。最后，根据所得结论设计出了针对 多模态优化问题的两阶段遗传算法，并得到了满意的实验结果，这也从侧面说明 了上述理论结果的正确性。 3 讨论了局部极值解的吸引域对遗传算法收敛结果的影响，以及参数搜索 空间规模对遗传算法搜索性能的影响，所得结论充分说明了对解空间进行合理划 分的必要性。结合正交设计法，提出了基于解空间合理划分的遗传算法，通过仿 真实验验证了该算法对多模态优化问题的有效性。 4 分析了两类基于遗传算法无限种群模型的复杂进化系统，在此基础上构 造了两类新的种群进化系统，并推导出了它们在单基因位情况下的动力方程。对 新系统在稳态情况下的复杂动力行为进行了分析，通过相图、分岔图和l y a p u n o v 指数谱图，严格地证明了其中一类系统具有混沌特性，而另一类系统具有复杂的 周期特性。根据以上结论，提出了一种能够持续保持遗传算法的种群多样性的方 法，它对求解多模态优化问题很有帮助。 关键词：遗传算法，多模态优化问题，适值差，搜索空间规模，混沌 a b s t r a c t h o wt oa p p l yg e n e t i ca l g o r i t h m st os o l v em u l t i m o d a lo p t i m i z a t i o np r o b l e m sh a s b e e naf o e l l si nt h er e s e a r c hc o m m u n i t yo fg e n e t i ca l g o r i t h ma n de v o l u t i o n a r y c o m p u t a t i o n i ti sa l s of u n d a m e n t a lt ot h eb a s i c 山e o r ya n di n d u s t r i a la p p l i c a t i o n so f g e n e t i ca l g o r i t h m s t h e r eh a v eb e e nm a n ys u c c e s s f u lc a s e si n r e a lw o r l 正b u tt h e e x i s t i n gt h e o r e t i ca n a l y s e sa r ef a rf r o mp e r f e c t t h ei n f l u e n c eo ft h ee x t e r n a l p a r a m e t e r so nt h ee 伍c i e n c yo fg e n e t i ca l g o r i t h m si se s p e c i a l l yi n v e s t i g a t e d a n dt h e t h e o r e t i ca n a l y s e sa r em a d ea n de x t e n d e dc o r o l l a r i e sa r ed e r i v e d t h et h e o r e t i c a l a c h i e v e m e n t sa r eu s e dt ot h ed e s i g no f h i 曲一e f f i c i e n c yg e n e t i ca l g o r i t h m sf o rs o l v i n g m u l t i m o d a lo p t i m i z a t i o np r o b l e m s t h em a i nc o n t e n t so ft h ed i s s e r t a t i o na r ea s f o l l o w s ： 1 t h ed e v e l o p m e n to ft h em u l t i m o d a lo p t i m i z a t i o na n dg e n e t i ca l g o r i t h m si s s u m m a r i z e d a n dt h ec u r r e n tl i t e r a t u r e so ft h ea p p l i c a t i o no fg e n e t i ca l g o r i t h m st ot h e m u l t i m o d a lo p t i m i z a t i o np r o b l e m sa l er e v i e w e d t h eb a s i ct h e o r i e so fg e n e t i c a l g o r i t h m sa r ei n t r o d u c e d , a n dt h ed e v e l o p m e n tt r e n d so fg e n e t i ca l g o r i t h m sa r e e v a l u a t e d 2 t h ei n f i n i t ep o p u l a t i o nm o d e lo ft h eg e n ep o o lg e n e t i ca l g o r i t h m ( g p g a ) i s b u i l tb a s e do nt h e 鼢l s ht r a n s f o r m a n dt h er e l a t i o nb e t w e e nt h ef i 国e s sd i f f e r e n c eo f l o c a lo p t i m a o ft h eb i n e e d l ef i t n e s sf u n c t i o na n dt h ee f f i c i e n c yo fg p g ai s d e f i n e d t h ea p p l i c a t i o ns c o p eo ft h et h e o r e t i c a lc o r o l l a r i e sa r ea n a l y z e da n dp r o v e d v i as i m u l a t i o nt e s t s a c c o r d i n gt ot l l et h e o r e t i c a lp r o p o s i t i o n s w ei n v e n tt h et w o s t e p g e n e t i ca l g o r i t h mf o rt h em u l t i m o d a lo p t i m i z a t i o np r o b l e m s ，a n dg e ts a t i s f a c t o r y e m p i r i c a lr e s u l t s i ta l s op r o v e st h et h e o r e t i cc o r o l l a r i e si n d i r e c t l y 3 b o t ht h ei n f l u e n c eo ft h ea t t r a c t i o nb a s i n so ft h el o c a lo p t i m ao nt h e c o n v e r g e n c eo fg e n e t i ca l g o r i t h m sa n dt h ei n f l u e n c eo ft h es o l u t i o ns p a c es p e c t r u mo n t h ee 伍c i e n c yo fg p g aa r ei n v e s t i g a t e d w h i c hi l l u s t r a t e st h es i g n i f i c a n c eo fp a r t i t i o n o ft h es o l u t i o ns p a c e a c c o r d i n gt ot h eo n h o g o n a ld e s i g n w ep r o p o s ean e wg e n e t i c a l g o r i t h mb a s e do nt h er a t i o n a lp a r t i t i o no ft h es o l u t i o ns p a c e t h es i m u l a t i o n e x p e r i m e n t ss h o wt h a tt h ei m p r o v e da l g o r i t h mc o n v e r g e st ot h eg l o b a lo p t i m u mm o r e q u i c k l y , a n dc a l lf m dm o r el o c a lo p t i m at h a nt r a d i t i o n a lm e t h o d so nm u l t i m o d a l o p t i m i z a t i o np r o b l e m s 4 t w oc o m p l e xe v o l u t i o ns y s t e m sa r ea n a l y z e db a s e do ni n f i n i t ep o p u l a t i o n m o d e lo ft h eg e n e t i ca l g o r i t h m a c c o r d i n gt ot h ea n a l y t i c a lr e s u l t s t w on e we v o l u t i o n s y s t e m sa r ec o n s t r u c t e d a n dt h ei t e r a t i v ee q u a t i o n so ft h ed y n a m i c a ls y s t e mm o d e l s o fb o t he v o l u t i o ns y s t e m si sd e r i v e di no n e - b i tc a s e t h ec o m p l e xb e h a v i o r so fb o t h s y s t e m si ns t e a d ys t a t ea r ei n v e s t i g a t e db yp h a s ep o r t r a i t s ，b i f u r c a t i o nd i a g r a m sa n d l y a p u n o v e x p o n e n ts p e c t r u m s w h i c hs h o wt h a tt h ef i r s te v o l u t i o ns y s t e mi sac h a o t i c s y s t e ma n dt h es e c o n d e v o l u t i o ns y s t e r nc o n t a i n sc o m p l e xp e r i o d i cb e h a v i o r s a c c o r d i n gt ot h e s ec o n c l u s i o n s ，w ep r e s e n tt h em e t h o dt ok e e pt h ed i v e r s i t yo ft h e p o p u l a t i o no ft h eg e n e t i ca l g o r i t h m w h i c hi sg o o df o rf i n d i n gm o r eu s e f u ls o l u t i o n s o fm u l t i m o d a lo p t i m i z a t i o np r o b l e m s k e yw o r d s ：g e n e t i ca l g o r i t h m s ，m u l t i - m o d a lo p t i m i z a t i o n , t h ef i t n e s s d i f f e r e n c eo fl o c a lo p t i m a , s p e c t r u mo ft h es o l u t i o ns p a c e ，c h a o s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨壅盘堂或其他教育机构的学位或证 书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：巷囊：b 签字日期：丑7 p 7 年月多日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂 有关保留、使用学位论文的规定。 特授权鑫洼盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：巷轲砧 签字日期：2 们年 月is 日 导师签名： 鼬炉 签字日期：年月日 天津大学博：l ：学位论文遗传算法求解多模态优化问题的研究 第一章绪论 从无到有，从弱到强，以遗传算法为代表的进化计算方法及其理论研究至今 已经有四十多年的历史了。在这期间，诸如模拟退火算法、蚁群算法、免疫算法 和微粒群算法等启发式优化算法层出不穷，在某些问题的求解中甚至取得了比进 化算法更好的效果，但对比各时期研究成果的统计数字可以发现，无论从论文数 量或是研究深度上来看，进化计算始终占有绝对的统治地位。如果仅作为一种数 值和系统设计优化方法，不会有那么多的学者对之给以如此长时间的关注，进化 算法的研究之所以能长盛不衰，原因之一就在于它本身就是对生物进化和遗传过 程的模拟，对进化算法的研究能够使我们更好的了解生物进化的本质。正因为如 此，使我们对它的一些细节特征也报有浓厚的兴趣，诸如“交叉多一点好，还是 变异多一点好”的问题至今仍然争论不休，不同的看法就衍生出不同的研究分支， 使得进化计算领域枝繁叶茂。长期的积累已经为进化算法的后续研究打下了坚实 的理论基础，这也是其能够不断发展的重要原因。 好的方法和理论如果没有找到合适的应用领域，没有较强的实效性，那也只 使少数研究者沉浸其中，纵然其乐无穷，却难免曲高和寡。进化计算方法之所以 在8 0 年代后期有了飞速的发展，就在于它找到了合适的应用领域，即作为一种 优化算法而存在，并且取得了十分显著的效果。虽然新的算法不断涌现，但相比 而言，进化计算有着如下的优势：首先，进化计算有着强大的理论基础，可以更 好的对算法的收敛性和效率进行分析，这为算法的改进提供了依据；其次，进化 算法有很好的通用性，并且能将其它算法的优点很好地嫁接过来；最后，进化算 法形式灵活多样，对各种问题总能找到合适的解决方法。随着社会的不断向前发 展，现实生活中需要解决的问题越来越多，其复杂程度越来越高，对求解算法也 提出了更高的要求。为了提高算法的性能，必须不断加深对进化算法工作机理的 研究。目前的算法形式通用性过强，难以有效地处理不同的实际问题，需要对特 殊问题有针对性的进行算法的理论研究，以指导算法的改进。本论文的主要工作 就是针对求解多模态优化问题的遗传算法进行理论研究，并将所得结论用以指导 算法的设计。 第一章绪论 1 1 多模态优化问题的提出和传统解决方法 在大量实际问题中，往往存在不止一个全局最优解和多个局部极值解，如何 构造一种优化算法，使之能够求出所有全局最优解和尽可能多的局部极值解，这 类问题就称为多模态优化问题( m u l t i m o d a lo p t i m i z a t i o n ) 或多峰函数优化问题 ( m u l t i p l eh u m pf u n c t i o no p t i m i z a t i o n ) 【1 1 。 多模态优化问题存在于实际生产生活中的方方面面，但真正单独作为一个课 题受到人们的重视和研究却是在近一二十年间。决策科学的发展明确了这类问题 的存在价值。以往人们只需要求得其中一个全局最优解决方案，但人们日益认识 到系统分析工作者和决策者所掌握的信息是不对称的，系统分析工作者需要向决 策者提供尽可能多的备选方案，由决策者根据所掌握的特殊信息来进行判吲2 1 。 另外，由于种种客观条件的限制，有些全局最优解在实际中往往并不适用，因此 需要求出更多的全局最优解和局部极值解备选。大量非经典算法的提出为这类问 题的解决提供了条件。以往经典的数学方法往往只能搜索到单个局部极值解，缺 乏全局搜索能力，遗传算法等启发式搜索算法的提出弥补了这一缺陷。总而言之， 伴随着运筹学和系统科学的发展以及在实际问题中的大量应用，多模态优化问题 日益受到人们的关注。 1 1 1 多模态优化问题的现实意义 多模态优化问题在生产实践中大量存在，如神经网络的结构及其权值的优化 问题，最优控制律的设计，复杂系统参数及结构辨识问题等归根结底都可以化为 多模态函数的求极值问趔3 1 。某些投资组合问题也可以看成是多模态优化问题， 文献 4 】中提出了一种新的投资组合模型，该模型需要得到一组不同风险水平的 最优解，以供不同风险偏好的投资者选择。应用多模态优化模型求解，该问题取 得了满意的效果。类似地，数学问题中也存在具有多个极值点的多模态函数需要 求解。文献 5 】提出“在反问题中，目标函数往往具有多模态性( 反映在算法上， 即为多解性) ，什么样的解最接近真实? 是否目标函数的全局最优解一定就最接 近真实? 上述问题一直是人们研究的方向。由于地质g - c v 的复杂性和测试手段 各种因素，全局最优解并不一定就是所需要的满意解，有时可能局部极值解才真 正与实际模型吻合。这样，在实际资料的处理过程中，找到解空间的全部全局最 优解和尽量多的局部极值解，由解释工作者根据先验知识分析得到真正满意的 解，是完全有必要的”。综上所述，研究快速、有效的多模态优化算法具有重 要的应用价值。 2 天津大学博士学位论文 遗传算法求解多模态优化问题的研究 1 1 2 多模态优化问题的数学描述 研究遗传算法求解多模态优化问题的机理，就要建立模型对之进行分析，因 此有必要用数学的语言对多模态优化问题的诸多概念加以描述【6 - 7 1 。 问题描述1 1 1 函数最大化问题可描述为：m a x 。鹤f ( x ) 。设r 为实数集， 其中x r ”称为实变量，s c r ”称为参数搜索空间，厂：s r 称为目标函数。 s = x f x r ”；x j 辑，i = 1 ，2 ， ，通常s 是一个拧维长方体。 定义1 1 1 设x 幸s ，若存在万 0 ，使得当x s 且i i x x * l i 万时，总有 f ( x ) s f ( x ) ，则称x 奉为厂在s 上的局部极值解，厂( x 囊) 称为一个局部极值。 定义1 1 2 若存在x s ，使得对于任意x s 都有f ( x ) ( x ) ，则称x 宰为 厂在s 上的全局最优解，厂( x ) 称为一个全局最优值。 定义1 1 3 已知厂幸是厂在s 上的全局最优值，若存在且仅存在一个x 幸s ， 使得厂( x 木) = 厂，则称函数f ( x ) 是一个单峰值函数。 定义1 1 4 已知厂是在s 上的全局最优值，若存在互不相同的 x ，x ：，x 。s ，使得f ( x ，) 均为全局最优值或局部极值，则称函数f ( x ) 是一个 多峰函数，也称多模态函数。 遗传算法在实际应用中主要使用的编码方式有：二进制编码、实数编码、大 字符集编码和组合编码等。本文研究的遗传算法主要采用二进制编码方式，这是 因为：各种不同的编码形式对遗传算法的求解机制并不产生本质上的影响，只是 影响进化算子的效率【l 】，而且二进制编码作为一种常用的重要编码方式，在理论 分析过程中有着不可比拟的优势。二进制编码情况下，多模态优化问题可作如下 描述。 问题描述1 1 2 多模态优化问题可描述为：求解 bf ( b ) 为极大值，b i b 7 ， 其中f ( b ) 是一个多模态函数，对所有的b i b 7 = o ，l 。，都有0 f ( b ) + 0 3 ，并 且厂( b ) c o n s 。 一一“在研究过程中，建立多模态优化算法收敛性的理论基础十分重要。不同于只 收敛到一个全局最优解的“全局收敛”( g l o b a lc o n v e r g e n c e ) 概念，多模态优 化算法的收敛性应理解为：随着进化代数的增大，算法最终能够以概率“l 找 到定义域内所有的极值解。这种能收敛到定义域内所有极值解的收敛性被称为 “完全收敛”( c o m p l e t ec o n v e r g e n c e ) i s 】。 定义1 1 5 对于问题描述1 1 2 中提到的多峰函数厂( b ) ，在定义域中假设 共有m 个极值解，分别记为。，西：，。，第t 代种群记为z ( t ) 。称算法是完全 收敛的，当且仅当下列条件成立： j l l i m iip ( ，z ( f ) ) = 1 。 第一章绪论 1 1 3 求解多模态优化问题的传统方法 对于多模态优化问题，传统的解析方法有牛顿法、d f p 变尺度法等睁l l 】；传 统的数值优化方法有梯度下降法、h o o k e j e e v e s 方法、混沌优化方法和改进的 p o w e u 方法等【9 。j ；近些年来又涌现出一大批启发式算法，如梯度爬山法、模拟 退火算法、蚁群算法、免疫算法和微粒群算法，当然还有进化算法 1 2 - 1 5 1 。传统的 解析和数值方法往往需要知道函数的导数信息，而启发式算法往往根据某些启发 式信息引导算法的搜索方向。 相比而言，传统的解析和数值方法存在以下一些缺陷： 1 一般对目标函数都有较强的限制性要求，如连续性、可微性等； 2 多数该类方法都是根据目标函数的局部展开性质来确定下一步搜索的方向， 这与求函数的全局最优解的目标有一定的抵触； 3 在实现算法之前，要进行大量的准备工作，如求函数的一阶或二阶导数及某 些矩阵的逆等。在目标函数较为复杂的情况下，这一工作是很困难的，甚至 是不可能的； 4 算法结果一般与初始值的选取有较大关系，不同的初值可能导致不同的结 果。初始值的选取较大地依赖于对问题背景的认识及所掌握的知识。 5 算法缺乏简单性和通用性。针对一个问题需要有相当的知识去判断哪一种方 法较为合适。 启发式算法很好地弥补了这些缺陷。首先，它们对目标函数一般要求不高， 只要能够求出确定的函数值即可；其次，对初值的依赖性大大减弱，具有全局搜 索能力；最后，启发式算法往往具有很好的简单性和通用性。然而启发式算法也 存在着一些亟待解决的问题，例如：如何避免陷于局部极值解而发现全局最优解 的问题，如何寻找到全部全局最优解和更多的局部极值解的问题，某些基于遗传 算法的改进方法还存在着种群个数较多、算法过于复杂的问题，还有一些算法需 要诸如“局部极值解的个数”、“局部极值点的间距”等一些苛刻的先验条件等 等。 综上所述，启发式算法较传统的解析和数值方法已经有了很大的进步，但本 身仍存在着一些问题，需要我们对之进行进一步地改进。 各种启发式算法也都有各自不同的优缺点，求解多模态优化问题的能力也不 同【1 6 - 2 0 。一般认为梯度爬山法和模拟退火算法的局部搜索能力更强一些，相比上 述提到的其他启发式算法，其全局搜索能力要差一些。蚁群算法利用随机策略， 因此得进化速度较慢，收敛速度也不理想。当蚁群算法采用正反馈强化策略时能 够得到较好的解，但会导致当前不被选用的路径在之后被选用的概率越来越小， 4 天津大学博士学位论文遗传算法求解多模态优化问题的研究 使算法在某些局部最优解的附近徘徊，出现停滞现象。a n g e l i n e 的研究表明1 2 1 j ， 尽管微粒群算法能比其他进化算法更快地得到相当有质量的解，但当代数增加 时，并不能进行更精确的搜索；另外，微粒群算法执行的是一种有“意识 ( c o n s c i e n c e ) 的变异，这使它有更多的机会更快地飞到有更好解的区域，但 降低了它在优化点附近开发的能力，而且不能保证这种“意识”提供的一定是有 用信息【2 2 1 。免疫算法作为一种求解多模态优化问题的方法与遗传算中的“排挤模 型”有着异曲同工之妙，可以说是在此基础上的发展。微粒群算法和免疫算法或 多或少的借鉴了进化算法的思想和技巧，并且后来的研究工作者将它们与进化算 法进行了很多结合，产生了很好的效果。相比之下，进化算法有着良好的全局搜 索性，针对算法容易陷入局部极值解的缺陷，研究工作者作了大量的改进，采用 了多种策略避免算法过早收敛，使之能够找到更多的全局或局部最优解。进化算 法在避免过早收敛的手段上较免疫算法和微粒群算法更加丰富而有效。另外，进 化算法研究有着雄厚的理论基础，算法本身有良好的嫁接性能，这也是其它启发 式算法不可比拟的。因此，继续研究和发展进化算法，改进其求解多模态优化问 题的性能是十分必要的。 1 2 进化计算的特点与发展 遗传算法是进化算法中产生最早、影响最大、应用也最为广泛的一个研究方 向和领域，它包含了进化算法的基本形式和全部优点，遗传算法与进化策略、进 化规划和遗传规划共同构成了进化计算方法【2 3 】。它们殊途同归的原因之一是具有 相同的仿生学基础生物进化思想。随着学术交流的进一步加深，不同分支相 互融合、互相借鉴，共同向前发展。 1 2 1 遗传算法的提出与发展 h o l l a n d 被公认为遗传算法的创立剖2 4 。二十世纪六十年代初期，h o l l a n d 在 研究生物学、人类社会及控制领域中动态系统的适应性问题时，采用简单的模拟 机制在计算机上模拟复杂的适应性现象，这就是最初的遗传算法。在这之后， b r e m e r m a n n 和d ej o n g 等人将这种方法应用于参数优化问题 2 5 - 2 6 。可以说起初遗 传算法首先是一种自然进化系统的计算模型，然后才是一种通用的求解优化问题 的适应性搜索方法，目前人们更关心后者。1 9 6 7 年，b a g l e y l 2 7 】首先提出了“遗传 算法”一词并发表了第一篇关于遗传算法应用的论文。与此同时，r o s e n b e r g z t 2 8 1 、 c a v i c c h i o 2 9 1 和w e i n b e r g 3 0 】等人都作出了一定的奠基工作，确立了遗传算法的基 本操作，还注意到了保持种群多样性的问题。1 9 6 8 1 9 7 1 年，h o l l a i l d 【3 1 教授提出 第一章绪论 了重要的模式定理，建议采用二进制编码来进行函数优化，指出了运用g - r a y 码的 一些优点，并研究了从生物系统引申出的不同的选择和配对策略。1 9 7 5 年竖立了 遗传算法发展史上的两块里程碑。一是h o l l a n d 3 2 出版了经典著作 a d a p t a t i o ni n n a t u r a la n da r t i f i c i a ls y s t e m s ) ) ，该书详细阐述了遗传算法的理论，并为其奠定 了数学基础，发展了一整套模拟生物自适应系统的理论。- - 是d e j o n g t 2 6 】完成了 具有指导意义的博士论文a na n a l y s i so ft h eb e h a v i o ro fac l a s so fg e n e t i c a d a p t i v es y s t e m s ) ) ，他深入地领会了模式定理并做了大量严格的实验，给出了 明确的结论，还建立了著名的五个函数测试平台，给出了性能评价标准。他的工 作为遗传算法的广泛应用奠定了坚实的基础，所得的结论至今仍具有普遍的指导 意义。因此，该年被认为是遗传算法的诞生年。 8 0 年代以来，随着以符号系统模仿人类智能的传统人工智能暂时陷入困境， 神经网络、机器学习和遗传算法等从生物系统底层模拟智能行为的研究重新复活 并获得空前的繁荣。g o l d b e r g 3 3 】在遗传算法的研究中起着继往开来的作用。1 9 8 3 年，他在博士论文中第一次把遗传算法应用到实际的工程系统一煤气管道的优化 中，从此遗传算法的理论研究更为深入和丰富，应用更为广泛和完善。1 9 8 9 年， g o l d b e r g 总结了遗传算法的主要研究成果，出版了第一本遗传算法的专著【蚓 ( ( g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o n ，a n dm a c h i n el e a r n i n g ) ) ，该书对遗 传算法进行了系统全面地论述，成为遗传算法的经典著作之一。与此同时，自1 9 8 5 年起，遗传算法及其应用国际学术会议( i c g a ) 每二年召开一次，有关人工智 能的会议和刊物上出现了不少关于遗传算法研究的论文，这些都有力地推动了遗 传算法的传播和发展。进入9 0 年代以来，遗传算法迎来了兴盛发展的时期。1 9 9 1 年，d a v i s 等【3 5 j 编辑出版了( h a n d b o o ko fg e n e t i ca l g o r i t h m s ) ) ；同年，i s g a ( i n t e r n a t i o n a ls o c i e t yf o rg e n e t i ca l g o r i t h m s ) 举办了国际会议( f o u n d a t i o n so f g e n e t i ca l g o r i t h m s ，f o g a ) ，此会议也是两年举行一次，其会议论文集收录的文 章主要以遗传算法理论性研究为主。1 9 9 2 年，进化规划、进化策略和遗传算法三 种思想极为相似的仿生算法被统一起来，统称为“进化计算”。1 9 9 3 年春，国际 第一本 e v o l u t i o n a r yc o m p u t a t i o n ) ) 杂志在m i t 创刊。1 9 9 4 年，i e e e $ 0 经网络委 员会( i e e en e u r a ln e t w o r kc o u n c i l ) 召开了第一届进化计算国际会议( i e e e i n t e r n a t i o n a lc o n f e r e n c ee v o l u t i o n a r yc o m p u t a t i o n ，i c e c ) ，该会议每年举办一次。 1 9 9 9 年该会议与进化规划的会议合并为一个新的国际会议c e c ( c o n g r e s so n e v o l u t i o n a r yc o m p u t a t i o n ) ，该会议由i e e e 0 经网络委员会和遗传规划团体( t h e e v o l u t i o n a r yp r o g r a m m i n gs o c i e t y ) 等几家团体合办，该会议的范围广泛，几乎 包括进化计算的所有领域。与遗传算法相关的重要会议还有i c n c 和b i t - c a 等 等。 6 天津大学博士学位论文 遗传算法求解多模态优化问题的研究 随着i n t e m e t 的迅速发展和日益普及，许多学校和研究中心建立了自己的遗传 算法站点，通过它人们可迅速了解最新的科技动态，进行广泛的学术交流。最著 名的遗传算法站点有e v o l u t i o n a r yc o m p u t a t i o nr e p o s i t i o nn e t w o r k 检索网站 ( h t t p ：a l i f e 。s a n t a f e c d u ) 、g aa r c h i v e s 检索网站( h t t p ：w w w a i c n r l n a v y m i l g a l i s t ) 等。它们为遗传算法的研究和发展创造了良好的机会。 目前，以不确定性、非线性、时间不可逆为内涵，以复杂问题为研究对象的 科学新方式得到了学术界的普遍认可。由于遗传算法能有效地求解属于n p 完全 类型的组合优化问题以及非线性多模态、多目标的函数优化问题，从而得到了许 多学科的广泛重视。因此，它在人工智能、计算机科学、生物工程、社会科学和 金融等各个领域中得到了广泛地应用。 1 2 2 遗传算法的特点总结 遗传算法具有以下主要特点： ( 1 ) 遗传算法对优化对象限制很宽。由于遗传算法在选定编码方式后，处理 的是参数的编码集而不是函数本身，所以对优化函数的性质没有具体的要求。这 与传统优化方法对优化函数在连续性、可导性方面的要求不同。 ( 2 ) 遗传算法的搜索初始点是初始群体，而不是单一的初始点，这种方式有 利于搜索过程以较大的概率跳出局部极值点，提高了算法搜索到问题全局最优解 的能力【2 9 1 。 ( 3 ) 遗传算法具有显著的隐并行性。从模式的角度考虑遗传算法的求解过程， 算法在处理群体中个体的同时，也在对此个体所在的模式进行处理，具有并行处 理的性质。 ( 4 ) 遗传算法构造简单、易于实现，对具体的运行环境没有过多的限制，可 以在不同的软硬件平台上实现。 ( 5 ) 遗传算法的搜索过程采用的是概率转换准则，而不是确定性准则。这 种准则仅仅作为一种工具来引导其搜索过程朝着搜索空间的更优的区域移动。看 起来它似乎是一种盲目搜索，但实际上它有明确的搜索方向。 ( 6 ) 遗传算法具有典型的动力学特征。遗传算子在算法运行过程中会产生复 杂的动力行为，遗传算法在求解一些问题时会表现出拟周期和混沌特性。 以上这些特点使得遗传算法使用简单，鲁棒性强，易于并行化并且易于理论 分析，从而在实际中能够得到广泛应用。 1 2 3 遗传算法的应用领域 进化算法作为一种操作简单、适应性强、鲁棒性好的全局优化技术，已经被 第一章绪论 广泛应用于科技、工程、经济和社会生活等各个领域。它对那些复杂的优化问题 具有广阔的应用前景。在一些多模态优化问题较集中的领域，进化计算有着广泛 的应用。下面分类加以介绍： ( 1 ) 进化计算方法在控制方面的应用 控制领域存在着大量多模态优化问题，不同时期的研究工作者在这方面作了 大量的工作：1 9 8 0 年，d ej o n g 3 6 】将遗传算法和规则学习应用于复杂动态系统实 时控制器的研究中；1 9 8 3 年，g o l d b e r g ”1 使用同样的方法对输气管道的运行控制 问题进行了深入的研究，建立了一个实时控制系统：1 9 9 3 年，f o n s e c a 明等人将 进化计算应用到气体涡轮发动机控制器的研究中，主要是优化多个气体燃烧炉的 工作；1 9 9 5 年，k i m 3 8 】等人使用进化规划来优化机器人的运动系统；1 9 9 7 年， k e y m e u l e n 3 9 】研究了离线情况下的机器人导航系统的优化问题；进化计算在控制 方面的应用一直未曾间断，如z h a n g 和t a n g 等人将遗传算法用于日。输出反馈控制 器的最优设计中删。由此可见，进化计算在控制领域的应用正在不断深入。 ( 2 ) 进化计算在组合优化方面的应用 组合优化问题中也存在着大量多模态优化问题，不同时期的研究工作者在这 方面作了大量的工作：这方面比较著名的工作有：g o l d b e r g 和l i n g l e 于1 9 8 5 年 使用遗传算法研究了经典的t s p ( t r a v e l i n gs a l e s p e r s o np r o b l e m ) 问题【4 l 】；同年 g r e f e n s t e t t e 等人研究了同一问题【4 2 1 ；从1 9 8 8 年到1 9 9 3 年间，f o g e l 发表了多篇 应用进化规划求解t s p 问题的文章 4 3 - 4 5 】：进化算法在该类问题上表现出超出其 它算法的求解能力，目前能够给出4 3 1 个城市t s p 问题的最优解【1j 。d a v i s 在1 9 8 5 年使用遗传算法对另一个经典的组合优化问题j s s ( j o bs h o ps c h e d u l i n g ) 问题进 行了研刭矧，随后y a m a d a 、c a r t w r i g h t 等人在这一问题上不断取得进剧4 7 1 ，19 9 6 年f o g e l 父子使用进化规划在异类多处理器的计算机上研究了该问题【4 引。1 9 9 5 年，t h a n g i a h 将进化算法与其他启发式算法相结合，来解决v r p 问题( v e h i c l e r o u t i n gp r o b l e m ) 问题，其结果优于单纯的任一种算法【4 9 】。2 0 0 2 年，m a c h a d o 等人分别使用遗传算法、协同进化方法和带有启发性的协同进化方法分别解决 v r p 问题，并加以对比，其结果表明对进化计算方法辅以启发信息可以得到v r p 问题的满意解1 5 0 。 ( 3 ) 进化计算在经济、金融方面的应用 投资组合等经济和金融领域的问题往往也是多模态的，研究工作者在这方面 的主要工作有：1 9 9 4 年，b a u e r t 5 1 】撰写了g e n e t i ca l g o r i t h m sa n di n v e s t m e n t s t r a t e g i e s ) ) 一书，在该书中b a u e r 以遗传算法为工具，成功的解决了金融投资问 题，证明了进化计算在投资优化问题上的有效性；1 9 9 9 年，a l l e n 5 2 】等人在技术 交易规则学习方面成功地应用了遗传算法，并将之应用于证券市场的行为解释。 天津大学博士学位论文 遗传算法求解多模态优化问题的研究 ( 4 ) 工程领域的应用 工程领域也包含着大量多模态优化问题，进化计算的研究工作者在这些方面 也作了大量的工作，这些工作涵盖结构可靠性分析1 5 引，结构优化【3 4 5 4 铡，地基 工程【5 6 】，施工规划【5 7 1 ，水网优化【5 8 1 ，水电站优化调度【5 9 1 ，铁轨维修工序制定1 6 0 1 等众多领域。 可以说遗传算法在实际的多模态优化问题中有着广泛的应用。除了上述所提 到的，进化计算在神经网络权重及结构确定【6 1 1 、模式识别【6 2 1 等领域的应用也日 益受到人们关注。 1 2 4 进化计算的其它分支 除了遗传算法，进化计算方法还包括进化策略、进化规划和遗传规划三个主 要分支。这四种方法是由不同领域的研究人员独立提出的，相互之间的交流始于 上世纪9 0 年代，目前越来越呈现出相互融合的趋势。 1 9 6 4 年，r e c h e n b e r g 在设计评测风洞中三维物体最小变形的设备中首先提 出进化策略的概念旧】。s c h w e f e l 和b i e n e r t 将r e c h e n b e r g 的算法付诸实施1 6 4 1 ，并 成功应用到具有工业意义的具体问题上【6 5 】。随后，r e c h e n b e r g 进一步改进了迸化 规划，提出( + 1 ) 进化策略【删以及( a + 兄) 进化策略和( ，兄) 进化策略【6 7 】，对进化 策略的进一步发展起到了决定性的作用。在理论研究方面，b e y e r 6 8 , 6 9 】首先建立 了进化策略的数学模型，并以微分几何为工具研究了( ，旯) 等多种进化策略的收 敛性质和算法的动力学性质，为进化策略的发展打下了坚实的基础。在求解多模 态优化问题方面，进化策略引入了并行和协同等概念并取得了一定的成功。进化 策略采用自适应机制并且比较强调变异的作用，这与遗传算法强调交叉的作用有 很大不同。 1 9 6 0 年，l j f o g e l 在研究有限状态机( f i l l i t e s t a t em a c h i n e s ) 的过程中首先 提出进化规划的思想。1 9 6 6 年l j f o g e l 、o w e n s 和w a l s h 合著了 a r t i f i c i a l i n t e l l i g e n c et h r o u g hs i m u l a t e de v o l u t i o n 一书，系统地阐述了进化规划的基本思 想 7 0 1 。l u t t e r 、h u n t s i n g e r 和d e a r h o l t 等人则有力推动了进化规划在实际问题中 的应用