（应用数学专业论文）基于遗传算法的多目标优化问题的研究与应用.pdf

摘要多目标优化问题一直是科学和工程研究领域的一个难题和热点问题，在遗传算法应用到这一领域以前，己经产生了许多经典的方法。经典方法在处理大维数、多模态等复杂问题上存在许多不足。多目标遗传算法具有处理大的问题空间的能力，在一个进化步内可以得到多个可行解曲面，对问题域的先验知识没有要求，对函数定义域的凸性不敏感。这正是经典算法所不具备的。所以，应用遗传算法求解多目标优化问题，是这一领域的发展趋势。本文在广泛深入地查阅国内外文献的基础上，对遗传算法及其面向多目标优化问题的基础理论和基本方法进行了深入的理论研究和实验分析。主要内容如下：首先，对多目标优化的理论做了介绍，提出了多目标优化模型，并且阐述了多目标优化问题的p a r e t o 最优解的概念和传统的多目标优化方法及其存在局限性；介绍遗传算法的基本原理和流程，以及常用的技术，对遗传算法的理论基础：模式定理和积木块假设分别做了阐述。然后，介绍现今已有的经典的多目标遗传算法：v e g a ，m o g a ，n p g a ，n s g a 和n s g a i i ，s p e a 。重点介绍了个体的适应度分配、选择机制和种群的多样性保持技术。最后，分别从免疫、协同进化和博弈论三个方面对遗传算法做改进，使之能够运用到多目标优化中。将模拟的免疫系统引入遗传算法，使用s h a n n o n 的信息熵理论来评价抗体的适应度，调节抗体的浓度来保持种群的多样性。并且根据当前种群的多样性状况来自适应调节种群的交叉与变异概率。最后将免疫遗传算法求解通讯网中的q o s 多播路由问题，取得了很好的结果。使用协同进化的理论，在进化群体中保持两个子种群，进化过程分为两个部分：子种群内部相互独立的进化和子种群之间的协同进化。将n a s h 均衡的思想运用到了多目标优化的遗传算法中，结合n s g a ，提出了一种基于博弈论的多目标优化遗传算法。关键词：遗传算法，多日标，免疫，协同进化，博弈论a b s t r a c tm u l t i o b j e c t i v eo p t i m i z a t i o nh a sb e e nad i f f i c u l tp r o b l e ma n df o c u sf o rr e s e a r c hi nf i e l d so fs c i e n c ea n de n g i n e e r i n g t h e r ea l r e a d yh a v eal o to fc l a s s i c a lm e t h o d sf o rs o l v i n gm 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 sb e f o r ee v o l u t i o n a r y a l g o r i t h m sw e r ei n t r o d u c e di n19 8 5 c l a s s i c a lm u l t i o b j e c t i v eo p t i m i z m i o nm e t h o d sh a v eb e e nt h o r o u g h l yd e v e l o p e d ，b u tt h e r ea r es t i l ll o t so fs h o r t c o m i n g si ns o l v i n gh i g hd i m e n s i o n ，m u l t i m o d a lp r o b l e m s g a sc a nh a n d l el a r g es p a c eo fp r o b l e ma n dg e tal o to ft r a d e o ff r o n t s ( p o s s i b l es o l u t i o n s ) i no n ee v o l u t i o n ag ad o e sn o tn e e dm u c hi n f o r m a t i o na b o u tt h ep r o b l e mb e f o r es t a r t i n gt h eo p t i m i z a t i o np r o c e s s ，a l s oi ti sn o ts e n s i t i v et ot h ec o n v e xo ft h ed e f i n e df i e l d so ft h eo b j e c t i v ef u n c t i o n s s ou s i n gg a si ns o l v i n gm 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 si st h em o s ti m p o r t a n tr e s e a r c hd i r e c t i o ni nt h ef u t u r e b a s e d0 1 1e x t e n s i v ea n dd e e pr e v i e wo fl i t e r a t u r e ，at h o r o u g ha n a l y s i sa n dr e s e a r c ho nm a n yt h e o r e t i c a la n da p p l i c a t i o no r i e n t e dp r o b l e m si sp r e s e n t e d 。t h em a i nc o n t e n t sa r ea sf o l l o w s ：f i r s t l y , w ei n t r o d u c et h em u l t i - o b j e c t i v eo p t i m i z a t i o nt h e o r y , b r i n gf o r w a r dt h em o d e lo fm u l t i o b j e c t i v eo p t i m i z a t i o na n de x p l a i nt h ec o n c e p to ft h ep a r e t oo p t i m i z a t i o ns o l u t i o n s w es u m m a r i z es o m ec l a s s i c a lm u l t i o b j e c t i v e so p t i m i z a t i o nm e t h o d sa n ds h o wt h el i m i t so ft h e m i nt h i sp a p e r , w ea l s oi n t r o d u c et h eb a s i ct h e o r yo fg e n e t i ca l g o r i t h m , i n c l u d i n gi t sw o r k i n gf l o wa n dt h ec o m m o nt e c h n o l o g yt h a th a sb e e nu s e di nt h eo p t i m i z a t i o np r o c e s s t h es c h e m a t et h e o r e ma n db u i l d i n gb l o c kh y p o t h e s i sa r ea l s oe x p a t i a t e di nt h i sp a p e r s e c o n d l y , w es u m m a r i z es o m ec l a s s i c a lm u l t i o b j e c t i v e so p t i m i z a t i o nm e t h o d sb a s e do ng e n e t i ca l g o r i t h m ：v e g a ，m o g a ，n f g a , n s g a , n s g a i i ，s p e aa n di n t r o d u c et h em e t h o d so fa l l o c a t i n gf i t n e s sa n dk e e p i n gt h ev a r i e t yo f p o p u l a t i o n f i n a l l y , w ei m p o gk n o w l e d g eo fi m m u n e ，c o - e v o l u t i o na n dg a m et h e o r yi n t og e n e t i ca l g o d t h mt oi m p r o v et h ep e r f o r m a n c eo ns o l v i n gt h em 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 t h er e s u l t so ft h ee x p e r i m e n t ss h o wt h a ta l lo f t h c mc a ng e tb e t t e rr e s u l t st h a nt h eo r i g i n a la l g o r i t h m k e yw o r d s ：g e n e t i ca l g o r i t h m , m u l t i o b j e c t i v e , i m m u n e ,原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。作者签名：i 盆茏日期：l 月一日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位论文。日期：尘立年- 羔月日硕士学位论文第一章绪论第一章绪论多目标优化问题( m u l t i - o b j e c t i v e o p t i m i z a t i o n p r o b l e m ，m o p ) 起源于许多实际复杂系统的设计、建模和规划问题，这些系统所在的领域包括工业制造、城市运输、资本预算、森林管理、水库管理、新城市的布局和美化、能量分配等等。几乎每个重要的现实生活中的决策问题都要在考虑不同的约束的同时处理若干相互冲突的目标，这些问题都涉及多个目标的优化，这些目标并不是独立存在的，它们往往是耦合在一起的互相竞争的目标，每个目标具有不同的物理意义和量纲。它们的竞争性和复杂性使得对其优化变得困难。多目标最优化是近2 0 多年来迅速发展起来的应用数学的一门新兴学科。它研究向量目标函数满足一定约束条件时在某种意义下的最优化问题。由于现实世界的大量问题，都可归结为含有多个目标的最优化问题，自7 0 年代以来，对于多目标最优化的研究，在国内和国际上都引起了人们极大的关注和重视。特别是近l o 多年来，理论探索不断深入，应用范围日益广泛，研究队伍迅速壮大，显示出勃勃生机。同时，随着对社会经济和工程设计中大型复杂系统研究的深入，多目标最优化的理论和方法也不断地受到严峻挑战并得到快速发展。近几年来，将遗传算法( g e n e t i ca l g o r i t h m , g a ) 应用于多目标优化问题成为研究热点，这种算法通常称作多目标优化进化算法或多目标优化遗传算法。由于遗传算法的基本特点是多方向和全局搜索，这使得带有潜在解的种群能够一代一代地维持下来从种群到种群的方法对于搜索p a r e t o 解来说是十分有益的。本章首先介绍多目标优化问题领域的研究发展历史，多目标优化的基本概念，多目标优化问题的传统方法以及这些方法的优缺点。然后，对遗传算法的产生发展历史、当前主要的基于遗传算法的多目标优化算法做一些简单的会绍。最后明确本论文的研究目的、内容和安排1 1 多目标优化综述一般说来，科学研究与工程实践中许多优化问题大都是多目标优化问题。多目标优化问题中各目标之间通过决策变量相互制约，对其中一个目标优化必须以其它目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性与单目标优化问题的本质区别在于，多目标优化问题的解不是唯一的，而是存在一个最优解集合，集合中元素称为p a , e t o 最优或菲劣最优所谓p a r e t o 最优就是，不存在比其中至少一个目标好而其它目标不劣的更好的解，也就是不可能通过优化其中部分目标而其它目标不至劣化。p a r e t o 最优解集中的元素就所有目标而言是彼此不可比较的硕士学位论文第一章绪论正是由于多目标问题的广泛存在性与求解的困难性，该问题一直是富有吸引力与挑战性的。它的最早出现，应追溯到1 7 7 2 年，当时f r a n k l i n 就提出了多目标矛盾如何协调的问题。但国际上一般认为多目标最优问题最早由法国经济学家v p a r e t o 在1 8 9 6 年提出【1 1 ，当时他从政治经济学的角度出发，把很多不好比较的目标归纳成多目标最优化问题。1 9 2 7 年数学家f h a u s d o r f f 关于有序空间理论的研究【2 l ，为多目标规划的发展提供了理论工具。此后这方面的工作方兴未艾：1 9 4 4年，v o n n e u m a n n 和j m o r g e n s t e r n 从对策论的角度【3 l ，提出了彼此互相矛盾的多目标决策问题；1 9 5 1 年，t c k o o p m a n s 从生产与分配的活动分析中第一次提出了p a r e t o 最优解的概念。同年，h w k u l m 和a w t t u c k e r 从数学规划的角度给出了向量极值问题的p a r e t o 最优解概, 念e 4 ；1 9 5 3 年，a n o n 等人对凸集提出了有效点的概念，从此多目标优化逐渐受到人们的关注；1 9 6 3 年，l a z a d e h 又从控制论的角度提出多目标控制问题：这期间，c h a r n e s ，k a r l i n ，k l i n g e r ，p o l a k ，k e e n e y ，g e o i f r i o n 等人先后都作出了较有影响的工作。l e o n i dh u t w i c z 于上世纪6 0 年代推广了h w - l 如l l i i 和a w t t u c k e r 的拓扑向量空间的结论，从纯数学的角度巩固了多目标最优化；1 9 6 8 年，z j o h n s e n 系统地提出了多目标优化问题的研究报告，这是多目标优化这门学科发展的一个转折。1 1 1 多目标优化的基本概念嘲下面从严格的数学描述角度介绍多目标优化问题的含义。通常在多目标优化领域中广泛采用并普遍接受的m o p 问题的数学定义如下：定义1 1 ( m o p ) ：一般m o p 由 个决策变量参数、k 个目标函数和m 个约束条件组成，目标函数、约束条件与决策变量之间是函数关系。最优化目标如下：m a x i m 拓ey = f ( 功= “( 砷，以( 碛，五( 砷)s j “砷= 编( 曲，e 2 ( x g ，( 曲) 0其中工= ( 五，x 29 1 9 ) e x( 1 1 )y = o l y 2 ，y j ) y这里x 表示决策向量，y 表示目标向量，表示决策向量工形成的决策空间，y 表示目标向量y 形成的目标空间，约束条件e ( s o 确定决策向量的可行的取值范围。当有多个目标函数存在的时候，“最优解”概念产生了新的变化因为在解决多目标问题时，实际上是求一组均衡解，而不是单个的全局最优解。这个被普遍采用的最优解的概念是f r a n c i sy s i d r oe d g e w o r t h 早在1 8 8 1 年提出来的。随后2硕士学位论文第一章绪论著名的法国经济学家和社会学家帕雷托( v i l f r e d op a r e t o ) 在1 8 9 6 年推广了这个概念【1 1 ，他从经济学的角度将本质上不可比较的多个目标转化成单个指标进行优化求解，这里就涉及到多目标的概念。帕雷托首次提出向量优化的概念，即现在广泛使用的p a r e t o 最优。m o p 的本质在于大多情况下各子目标可能是相互冲突的，某予目标的改善可能引起其它子目标性能的降低，即同时使多个子目标均达到最优一般是不可能的，否则就不属于多目标优化研究的范畴。解决m o p 的最终手段只能是在各予目标之间进行协调权衡和折衷处理，使各子目标函数均尽可能达到最优。因此，m o p 的最优解与单目标优化问题的最优解有着本质上的区别，为了正确求解m o p ，必须对其解的概念进行定义。定义1 2 ( 可行解集) ：可行解集x ，定义为满足式( 1 1 ) 中的约束条件“力的决策向量并的集合，即x ，= 缸岳x i p ( 功so ( 1 2 )j ，的可行区域所对应的目标空间的表达式为：弓= 八工，) = k t ，矿( ( 1 3 对于式( 1 3 ) ，表示可行解集工，中的所有并，经优化函数映射形成目标空间中的一个子空闻，该子空间的决策向量均属于可行解集。对于极小化问题，可以很容易转化为上述的最大化问题来进行求解。单目标优化问题的可行解集能够通过它的唯一的目标函数厂来确定方案之闻的优劣关系和程度。对于m o p 问题来说，情况则有所不同，因为一般来说，x ，中的决策向量是无法进行全部排序的，而只能对某个指标进行排序，即部分排序f 1 1 为此，定义决策向量之间的数学关系一一，一y ，”矽如下；定义1 3 ：对于向量”，u牡；v ：当且仅当v i e 1 ，2 ，七) ，；玎，：当且仅当v j e l 2 ，七) ，蚝h ( 1 4 )埘 ，：当且仅当v f e 仉2 ，七 ，吩) 一。类似可以定义数学关系* 夕和一一”接下来定义决策向量之间的数学关系”一，”f ，。j定义1 4 ( p a r e t o 优胜) ：对于决策向量口。b ，4 卜b ( a 优于b ) ：当且仅当以口) ，( 4 曲( a 弱优于b ) ：当且仅当( 4 ) ，( 6 ) ( 1 5 )a 一厶( 4 无差别于b ) ：当且仅当八4 ) z ，( 6 ) 且以4 ) i ，( 。如果向量a ，b 之间是p a r e t o 优胜关系，则其中一个向量的所有子目标函数值均大于另一个向量对应的数值。接下来定义p a r e t o 最优解的概念：硕士学位论文第一章绪论定义1 5 ( p a r c t o 最优解) ：决策向量石e x ，称为p a r e t o 最优解，当且仅当：习口e 工r ：( d ) 卜厂( 工)( 1 6 )p a r e t o 最优解又称为非劣解、非支配解( n o nd o m i n a t e ds o l u t i o n s ) 。如果决策向量x 为p a r e t o 最优解，这就是说工无法在改进任何目标函数的同时不削弱至少一个其他目标函数。对于一个给定的目标空问y 中的p a r e t o 最优解，它在决策空间中的原象点称作有效的( e f f i c i e n t ) 或非劣的( n o n i n f c r i o r ) 。x ，中的一点是有效的当且仅当它的象在y 中是非支配的。与单目标优化问题( s i n g l e - 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 p 不存在唯一的最优解，而是存在p a r e t o 最优解集。定义p a r e t o 最优解集的概念如下；定义1 6 ( p a r e t o 最优解集) ：对于给定的m o p 问题，p a r e t o 最优解集彳定义为：a = 工x r i j 彤，厂( ，) 卜，( )( 1 7 )大多数情况下，类似于单目标优化的最优解在多目标优化问题中是不存在的，只存在p a r e t o 最优解【5 】。多目标优化问题的p a r e t o 最优解仅仅只是它的一个可以接受的非劣解或满意解，并且通常的多目标优化问题大多具有很多个p a r e t o最优解。若一个多目标优化问题存在所谓的最优解，则该最优解必定是p a r c t o最优解，并且p a r c t o 最优解也只由这些最优解组成，再不包含其它解。因此p a r c t o最优解是多目标优化问题的合理的解集合。通常多目标优化问题的p a r c t o 最优解是一个集合。对于实际应用问题，必须根据对问题的了解程度和决策人员的个人偏好，从多目标优化问题的p a r e t o 最优解中挑选出一个或多个解作为所求多目标优化问题的最优解。因此求解多目标优化问题的首要步骤和关键是求出尽可能多的p a r c t o 最优解 1 2 传统的多目标优化方法大多数传统的多目标优化方法将多个目标减少为一个，然后用数学规划工具求解问题。为了用数学规划工具求解问题，首先需要用数字的形式来表明偏好。数字越大，偏好越强。这种需求促成了各种标量化方法的发展。采用这些方法将多目标优化问题转换为单目标或一系列单目标优化问题，然后可以求解变换后的问题。传统的多目标优化方法有多种。本文选取约束法、加权法、距离函数法、最小最大法这四种多目标优化方法来进行简单的介绍。1 1 2 1 约束法嘲在m o p 问题中，从七个目标函数石( 曲，五( 破，以( 功中，若能够确定一个主硕士学位论文第一章绪论要的目标，例如z ( 曲，而对于其他的目标函数石( n ，五( 功只要求满足一定的条件即可，例如要求：a z ( 力6 ，i = 2 ，3 ，k这样我们就可以把其他目标当作约束来处理，则m o p 问题可以转换为求解如下的单目标优化问题：m a x i m i z e 上( 力鼬“力= ( q ( 力，e 2 ( x ) ，气( 工) ) 0a z ( 力s 6 ，i 皇2 , 3 ，七1 1 2 2 加权法加权法将为每个目标函数分配权重并将其组合成为一个目标函数，加权法的基本思想是由z a d e h 首先提出，加权方法可以表示如下：tm a x i m i z ez ( 力= yc o , f , c x )翻sjxex|tq 称为权重，不失一般性，通常权重可以正则化后使得q = l ，求解上述不同权重的优化问题则能够输出一组解。这种方法的最大缺熊是不能在非凸性的均衡曲面上得到所有的p a r c t o 最优解。 1 2 3 距离函数法跏距离函数法需要使用理想点，定义理想点如下：定义1 7 ( 理想点) ：理想点用y + = ( 片，正，藏) 来表示，其中订= s u p 饼( 功l 工e x ，) - j = 2 a ，k 点y 称为理想点( i d e a lp o i n t ) 是因为通常该点无法达到。对于每个目标来说，寻找理想点y 是可能的距离函数法寻找与理想点最近的解，根据理想点y 。的定义，对于目标空间的每一个元素，我们无法得到比理想解更好的结果。给定y l ，y 与j ，的距离函数来近似：力= p y 8其* f l y - y 0 是在某种特定范数意义上从y 到y 的距离。由于0 范数比较清晰，因此经常采用。对于一个给定的正数p 1 ，有：r - i t p，2y - y l | ，；l 骞一巧i is硕士学位论文第一章绪论l p 范数意义下的最优解就是最小化，( ) ，；p ) 的点距离函数r ( ) ，；p ) 对于每一个阮一e i 的值的重视程度相同。如果具有不同的重要性，可以指派一个权重向量= ( q ，0 ) 2 ，q ) 来表明不同的重要程度，在这种情况下，有下面的加权。r ( y 范；p 数, t ：o t o ) = y - y i | ： 套叼b z l = l 叼l 乃一硝i1 1 2 4 分层序列法瑚分层序列法是把m o p 问题的k 个目标函数，按其重要程度排一个次序。例骆如，不妨设m o p 问题的后个目标函数已经排好次序：石( 功最重要，五( 帕次之，五( 功再次之，最后一个目标为以( 砷。先求出问题：m a x i m i z e ( 曲7s j e ( 功= ( 岛( 工) ，e 2 ( x ) ，( 砌0的最优解善1 及最优值z 。即；z 2 9 。a m 3 9z ( x )其中玛= 一再求解问题m a x i m i z e 五( 功肌j 马问题的最优解，2 及最优值即：= m 。a 如x 五o )其中马= 焉n 扛i 石( 功2 _ ，；继续求解问题m a x i m i z e 五( 力s j x 焉问题的最优解一及最优值f 即：= m 。a 焉x 六其中焉= 马n 扛i 五( 曲z )如此继续下去，直到求出第七个问题朋a 砌i 韶五( 功硕士学位论文第一章绪论s i x c - 问题的最优解一”及最优值彳。即：式= m 譬f 。艇血其中r i = r hn x l l l ( 力2 疋i 这样求得的就是m o p 问题在分层序列意义下的最优解，即，= j ( ”，而f + = ( z ( x + ) ，a ( x ) ，l ( x + ) )为m o p 问题的最优值。1 1 3 传统优化方法的局限性慨q传统方法的优点在于它继承了求解单目标优化问题的一些成熟算法的机理。但是经典方法如加权法求解多目标优化问题时，对p a r e t o 最优前沿的形状很敏感，不能处理前沿的凹部，并且求解问题所需的与应用背景相关的启发式知识信息获得很少，导致无法正常实施优化或优化效果差，特别对于大规模问题，这些多目标优化方法很少真正能被使用。前面介绍的传统的多目标优化方法存在一些局限性，主要包括一下几点：( 1 ) 一些古典方法如加权法求解多目标优化问题时，对p a r e t o 最优前端的形状很敏感，不能处理前端的凹部。( 2 ) 只能得到一个解。然而，在实际决策中决策者通常需要多种可供选择的方案。( 3 ) 传统方法共同存在的一个关键问题就是为了获得p a r e t o 最优集须运行多次优化过程，由于各次优化过程相互独立，往往得到的结果很不一致令决策者很难有效地决策，而且要花费巨额时间开销。( 4 ) 多个目标函数之间量纲不同，难以统一为了避免其中的一个目标函数支配其他目标函数，精确的给出所有目标函数的标量信息，就必须有每一个目标的全局先验知识，计算量巨大，很难实现( 5 ) 加权值的分配带有较强的主观性。由于是人为规定各个目标函数的权值，因此带有很大的主观性。最近遗传算法己经作为一种多目标优化方法崭露头角。它的优点在于可处理大规模的搜索空间、在单轮优化期间产生多个均衡解，可有效克服古典方法的局限性。1 2 遗传算法的产生和发展嘲7硕士学位论文第一章绪论遗传算法g a ( g e n e t i ca l g o r i t h m ) 是受生物学进化学说和遗传学理论的启发而发展起来的，是一类模拟自然生物进化过程与机制求解问题的自组织与自适应的人工智能技术，是一种借鉴生物界自然选择和自然遗传机制的随机的搜索算法，由h o l l a n d 教授于1 9 7 5 年提出【9 】。遗传算法起源于6 0 年代对自然和人工自适应系统的研究，最早的雏形出现在生物学家f r a s e r 的1 9 6 2 年的论文中 1 0 l ，他尝试使用仿真来模拟带有突变和选择交互作用的进化过程。1 9 6 7 年，b a g l e y 在他的博士论文中首次提出了遗传算法( g e n e t i ca l g o r i t h m ) - - 词，发表了遗传算法应用方面的第一篇论文，讨论了遗传算法在自动博弈中的应用。他提出的选择、交叉和变异等操作己经与目前的遗传算法中的操作十分相近。他还注意到在遗传算法进化过程的不同阶段应采用不同的选择概率，有利于防止遗传算法的早熟现象。同时，他提出了遗传算法自动调整的概念，交叉和变异的概率融入染色体本身的编码中，随着进化的进行自动调整算法。他还引入了适应度定标( s c a l i n g ) 的概念，这也是目前遗传算法中常用的技术1 9 7 5 年美国密执根大学h a l l a n d 教授出版了他的第一本关于遗传算法的专著 a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t o n ”，同年d el o n g 发表的博士论文 a na n a l y s i so f b e h a v i o ro f ac l a s so f g e n e t i ca d a p t i v es y s t e m 一起被公认为是遗传算法的基础【l l l 。h o l l a n d 的著作系统地阐述了遗传算法的基本理论和方法，并提出了奠定遗传算法理论基础的模式定理( s c h e m a t at h e o r y ) 和隐形并行性原理。模式定理揭示了群体中的优良个体的样本数将以指数级规律增长，从理论上保证了遗传算法是可以用来寻求最优可行解的一种优化方法，该理论也首次确认了结构重组遗传操作对以后的隐并行性的重要性。d el o n g 的论文中结合模式定理进行大量的数值函数优化计算试验，建立了遗传算法的工作框架，并提出了代沟( g e n e r a t i o ng a p ) 等新的遗传操作技术，定义了评价遗传算法的性能指标。他建立的一组测试函数至今仍被广泛应用，其中包括非凸函数、不连续函数、带有随机变量的函数以及高维函数，被称作d e l o n g 五函数测试平台。他所作的工作可以看成是遗传算法发展过程中的一个里程碑。到了8 0 年代早期，遗传算法己经广泛的应用于各个领域当中。1 9 8 3 年g o l d b e r g 将遗传算法应用于管道系统的优化和机器学习问题 1 2 , 1 3 】。1 9 8 4 年f i t z p a t r i c k , c - r e f e n s t e t e 和v a ng u c h t 利用遗传算法处理了医学图像变换问题。8 0年代中期，a x e l o r d 和f o r r e s t 合作研究了博弈论中的经典问题一一囚徒困境问题 1 4 , l s 。到了踟年代末，遗传算法的发展达到了高潮【l c , - 2 a 。人们对遗传算法的兴趣日益增长，其原因有二：其一是工程领域中不断涌现出超大规模的非线性系统。特l硕士学位论文第一章绪论别是人工智能与控制领域。经典的优化方法不能够有效的求解这些系统中存在的优化问题，而这些问题恰恰是大量存在并亟需解决的，如神经网络连接权重及网络拓扑结构的优化、模糊系统中模糊规则的选取等等。其二，遗传算法本身就是一种模拟自然演化这一学习过程的求解问题的方法，它能够以独立的或与其它方法相结合的形式用于智能机器学习系统的设计中。1 9 8 9 年g o l 曲e r g 首先提出了基于p a t i o 最优概念计算个体适应度的方法，借助非支配等级概念和相应的选择算子使种群在优化过程中朝p a r e t o 最优解的方向进化并出版了专著搜索、优化和机器学习中的遗传算法( 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 na n dm a c h i n el e a r n i n g ) 渊。该书全面的论述了遗传算法的原理及其应用，奠定了现代遗传算法的科学基础。1 9 9 1 年，d a v i s 编辑出版了遗传算法手册( h a n d b o o ko f g e n e t i ca l g o f i t h m s ) 一书，书中涵盖了遗传算法在工程技术和科学计算等方面的大量应用实例阅，为推广遗传算法的应用作出了贡献。1 9 9 2 年，k o z a 将遗传算法应用计算机程序的优化设计及自动生成，提出了遗传编程( g e n e t i cp r o g r a m m i n g ，简称g p ) 的概念，并成功的应用于人工智能、机器学习等方面。经过十几年的努力，遗传算法不论是在应用研究上，算法设计上，还是在基础理论上，均取得了长足的发展，己经成为信息科学、计算机科学、运筹学和应用科学等诸多学科所共同关注的热点研究领域。遗传算法虽然在过去的2 0 年中得到了广泛的应用，但研究人员己经意识烈，遗传算法采用简单的、固定不变的进化策略对复杂应用场合的效果并不理想，传统的遗传算法逐渐暴露出一些缺点。所以，为了提高遗传算法的性能，使其更好地应用于实际问题的解决中，研究者们开始对基本遗传算法进行改进，通过不同的遗传基因表达方式，不同的交叉和变异算子的选择。特殊算子的引用，以及不同的再生和选择方法，产生了以基本遗传算法为核心的各种算法遗传算法的这些扩展和改进给一般问题特别是工业工程中的难以求解的优化问题带来了新的希望和方向1 3 多目标遗传算法概述在过去的2 0 年中，遗传算法作为多目标优化问题的新求解方法受到了相当程度的关注这就诞生了遗传多目标优化。这个主题已经由f o n s e c a 和f l e m i n g 、h o m 、t a m a k i 、k i t a 和k o b a y a s h i 进行了综述本节将简要的描述多目标遗传算法的发展过程在多目标优化闯题中首次应用遗传算法的思想可以追溯到1 9 6 7 年，硕士学位论文第一章绪论r o s e n b e r g 在他的研究中提出了在模拟单细胞有机物的化学遗传特性中采用多属性研究方法【2 6 】，也提到了可以考虑用遗传的搜索算法求解多目标优化问题。虽然他最终只应用了单一属性方法，他的研究却开创了遗传算法应用于多目标优化领域的研究。直到9 0 年代，遗传算法才真正地应用于多目标优化领域。这些多目标遗传算法通常分为两类，一类是采用p a r c t o 机制的多目标演化算法，也是目前的研究热点，一类是非p a r c t o 机制的多目标演化算法。1 9 8 5 年，为了克服整合方法的缺点，d a v i d s c h a f f e r 在g r e f e n s t e t t e 的单目标优化程序g e n e s i s 的基础上提出了基于向量评估的遗传算法( v e g a ) 。这是第一个多目标演化算法( m o e a ) ，但并不是基于p a r e t o 。最优概念的演化算法。虽然v e g a 本质上与传统加权法一样不适合求解折衷且标具有凹面的多目标问题，但是与普通固定加权和算法相比，v e g a 对不同物种能够维持比较多的种群代数，因而增强了种群的多样性【2 7 1 。然而，在经过一定代数的进化以后，v e g a 通常会偏好收敛于某一区域的解，丽不是均匀的收敛于整个p a r e t o 域，因此只能求的局部意义上的非支配解。1 9 9 3 年，f o n s e c a 和f l e m i n g 提出了多目标优化算法( m o g a ) f 1 4 郐- 3 0 1 ，其主要思想是每个个体排序的序号由当前种群中支配它的个体的数量决定，采用共享函数和小生境技术实现种群的多样化。m o g a 易于执行且效率较高，因而在多目标优化领域得到了广泛的应用。如：1 9 9 5 年，用于解决喷气发动机的多变量控制系统优化问题【3 ”，1 9 9 7 年。t o d d 和s e n 采用改进的m o g a 解决了大规模组合优化问题一集装箱布局( c o n t a i n c r s h i pl a y o u t s1 问题等等d 2 。然而，m o g a 也存在缺点小生境的大小对算法的影响较大。1 9 9 3 年，h o r n 和n a f p l i o t i s 提出了一种基于p a r o t o 支配定义的锦标赛选择机制方法一小组决胜遗传算法( n p g a ) 。算法从种群中随机选取多个个体( 一般为l o 个渗与，共同决定支配关系。当两个个体之间没有明显的支配或被支配关系时，称作雠，通过适应度共享来决定锦标赛选择的结剁”州。因为该算法的非劣最优解的选择是基于种群的部分而非全体，因此其优点是能很快找到一些好的非劣最优解域，并能维持一个较长的种群更新期，缺点是除了设置共享参数外还需要选择一个适当的锦标赛规模，限制了该算法的实际应用效果【2 7 】。1 9 9 5 年，由s r i n i v u 和d e b 提出了非支配排序遗传算法n s g a( n o n - d o m i n a t e d s o r t i n g g e n e t i c a l g o d t h t m ) 。算法是根据个体之间的支配与非支配关系分层实现的【3 7 1 。n s g a 的优点是优化目标个数任选，非劣最优解分布均匀，并允许存在多个不同的等价解：缺点是算法计算复杂度较高，缺乏精英策略，并对共享参数盯。的依赖性较大唧。n s g a 在现实问题的求解中也得到了广泛的硕士学位论文第一章绪论应用，v e d a r a j a n 等人于1 9 9 7 年采用n s g a 进行投资利润的最优化跚；m i c h i e l s s e n 和w e i l e 于1 9 9 5 年采用n s g a 设计电磁系统。1 9 9 9 年，e c k a r tz i t z l e r 提出了s u e n g t hp a r e t oe v o l u t i o n a r ya l g o r i t h m ，简称s p e a l 3 5 1 ，在他的论文中解决了计算任务在不同体系结构的系统上的调度问题，并和其他算法的解进行了详尽的比较。2 0 0 0 年，d e b 等人针对n s g a 存在的缺点，提出了改进算法n s g a - i i ，降低了算法的计算复杂度，引入精英策略，并不再需要指定共享参数盯。n s g a - i i保持了n s g a 具有的优点，改进了不足，在算法应用上取得了极好的效果。在这些算法当中，多目标遗传算法( m o g a ) ，非支配排序遗传算法( n s g a )和小组决胜遗传算法( n p ( 讽) ，己成为采用p a r e t o 机制的多目标演化算法研究工作的奠基石1 2 7 1 。此外，还存在一些非p a r e t o 机制的多目标演化算法，如多性别遗传算法、目标向量方法、权重极小极大法、变化权重的极小极大法，无后代遗传算法等等。随着多目标演化算法越来越多的应用于各个领域，对它的研究也将直接受到实际工程问题的推动。目前，多目标优化技术仍面临着许多困难，存在很多有待研究的问题，如非劣最优解域收敛性分析、适应值赋值方法、种群更新终止条件及其稳定性分析，以及实际多目标优化问题的演化求解等，这些都是目前的研究热点【2 7 1 1 4 本文组织结构及所做的工作 4 1 本文的组织结构本文一共分为七章，第一章绪论为总述，提出多目标优化的模型和要解决的问题。介绍遗传算法以及多目标遗传算法的基本概念和发展的状况。第二章的主要内容是介绍遗传算法，介绍s g a 的基本结构和流程，介绍遗传算法中使用到的选择技术、交叉技术和变异技术以及遗传算法的理论基础：模式定理和积木块假设第三章介绍经典的多目标遗传算法：v e g a ，m o g a ，n i g a ，n s g a和n s g a - i i ，s p e a 。重点阐述这些算法个体的适应度分配、选择机制和种群的多样性保持技术。第四章的内容是基于免疫遗传算法的多目标优化算法，介绍生物界的免疫系统，并将其应用到遗传算法中，改进算法。第五章为基于协同进化机制的多目标优化算法，将生物界的协同进化的思想加入遗传算法，使用两予种群协同进化来求解多目标优化问题。第六章为基于博弈论的多目标优化算法，介绍博弈论领域的n a s h 均衡的概念，并将其应用到遗传算法的寻优过程，通过和n s g a 的结合，来求解多目标优化闯题。硕士学位论文第一章绪论1 4 2 本文所做的工作本文通过三种来自自然界的技术一人工免疫、协同进化和博弈论来改进多目标优化遗传算法：将模拟的免疫系统引入遗传算法，使用s h a n n o n 的信息熵理论来评价抗体的适应度，调节抗体的浓度来保持种群的多样性。并且根据当前种群的多样性状况来自适应调节种群的交叉与变异概率；使用了协同进化的理论，在进化群体中保持两个子种群，进化过程分为两个部分，子种群内部相互独立的进化，和子种群之间的协同进化。将n a s h 均衡的思想运用到了多目标优化的遗产算法中，结合n s g a ，提出了一种基于博弈论的多目标优化遗传算法。算法将优化对象中的每一个目标，对应于博弈中的一个参与人，而所有的自变量在这些参与人之间分配，其中每个参与人分配的是自变量的一个子集。在优化过程中。每个局中人同时利用遗传算法来优化自己对应的目标。每种改进方法均使用实际的多目标优化问题进行检验求解，并将求解的结果与性能与传统的多目标优化遗传算法进行比较。均能起到加速收敛的性能，在缩短算法求解的时间上也起到了一定的作用硕士学位论文第二章遗传算法的基本原理和方法第二章遗传算法的基本原理和方法达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。遗传算法( g 龃c t i ca l g o r i t h m ) 是一类借鉴生物界的进化规律( 适者生存，优胜劣汰遗