（运筹学与控制论专业论文）解非线性两层规划问题的遗传算法.pdf

摘要 摘要 对两层规划问题进行算法研究具有现实意义和应用前景，近年来受到众多领 域的广泛关注。然而，两层规划的本质非凸性和不可微性给其数值求解带来极大 困难，特别是求非线性两层规划问题的全局最优解。遗传算法是一种解决复杂非 线性优化问题的新型的有效方法，它不受目标函数的可微性、凸性、连续性等的 限制，与传统优化方法相比，对一些大型复杂非线性优化问题，它却具有独特的 优越性。 本文在利用遗传算法解决非线性两层规划问题时，充分考虑了两层规划问题 的结构和特点，使得算法具有有效性和高效性。本文设计了两种遗传算法，一种 是混合遗传算法，把遗传算法和梯度投影法相结合，充分发挥遗传算法的全局搜 索能力和梯度投影法的局部搜索功能，并使搜索始终在容许集中进行，而且使得 后代有所改进。另一种是自适应遗传算法，给出了一种基于上层目标函数的适应 度函数，它能有效辨别不同潜在解的质量好坏，而且我们设计了一种有效的变异 算子，它具有方向变异和边界变异的功能，使得后代能很快向全局最优解靠近， 这种自适应遗传算法，使种群在开始时，从容许集内部和外部进化，逐渐集中在 容许集内部进行全局搜索。 第二章用所设计的混合遗传算法求解了凸两层规划问题，包括二次线性，及 二次二次两层规划，通过数值模拟，结果表明该算法是有效的。第三章对于一类 特殊非线性两层规划问题，将下层规划问题用与之等价的k k t 最优性条件来代替， 给出了基于自适应遗传算法的求解方法， 行数值仿真，结果表明该算法是高效的。 分析了算法的全局收敛性，并对算法进 第四章对一般的非线性两层规划问题， 其上层问题采用所设计的自适应遗传算法，下层问题根据其不同的形式，利用一 些高效的决定性算法如信赖域法等来求下层问题的最优解，给出了一般非线性两 层规划问题的两种算法。分别给出了两种算法的全局收敛性分析和数值仿真，结 果表明两种算法都有效。最后对两种算法的性能进行了比较，说明它们各有优缺 点。 关键词：遗传算法两层规划全局优化 a b s t r a c t a b s t r a c t b i l e v e lp r o g r a m m i n g p r o b l e m ，b r i e f l yd e n o t e db yb l p p , h a sw i d ea p p l i c a t i o n s ，t h u s t h er e s e a r c ho l la l g o r i t h m sf o rb l p pi so fr e a ls i g n i f i c a n c e ，a n dm u c ha t t e n t i o nh a sb e e n p a i dt oi n r e c e n ty e a r s u n f o r t u n a t e l y , i ti s v e r yd i f f i c u l tt od e t e r m i n ei t ss o l u t i o no f b l p pb e c a u s eo fi t si n h e r e n tn o n c o n v e x i t ya n dn o n d i f f e r e n t i a b i l i t y i np a r t i c u l a r , i ti s m o r ed i f f i c u l tt og e tt h eg l o b a lo p t i m a ls o l u t i o no fn o n l i n e a rb l p eg e n e t i ca l g o r i t h m ， b r i e f l yd e n o t e db yg a ，i san e wk i n do fe f f e c t i v ea l g o r i t h mf o rv e r yc o m p l e xn o n l i n e a r p r o g r a m m i n g i t h a sn or e s t r i c t i o n so nf u n c t i o n s i n v o l v e ds u c ha s r e q u i r i n g d i f f e r e n t i a b i l i t y , c o n v e x i t 5c o n t i n u a t i o n a n ds o o n e s p e c i a l l y , t os o m el a r g e - s c a l e c o m p l e x n o n l i n e a r o p t i m i z a t i o np r o b l e m ，i th a s m o r e s u p e r i o r i t y o v e rt r a d i t i o n a l o p t i m i z a t i o ns c h e m e s t h es t r u c t u r ea n dc h a r a c t e r i s t i co ft h eb l p pa r et a k e ns u f f i c i e n t l yi n t oa c c o u n ti n d e s i g n i n gg a ，t w ok i n d so fg a s b a s e do nt h e s ec o n s i d e r a t i o n sa r ep r o p o s e d o n ei s h y b r i dg a ，i nw h i c ht h eg a i sc o m b i n e dw i t ht h eg r a d i e n tp r o j e c t i o nm e t h o d ，t h u s ， b o t ht h eg l o b a l s e a r c ha b i l i t yo fg aa n dl o c a l - s e a r c ha b i l i t yo ft h eg r a d i e n tp r o j e c t i o n m e t h o da r ea d o p t e d ，a sar e s u l t ，t h es e a r c hi se x e c u t e di nt h ec o n s t r a i n tr e g i o n ，a n dt h e o f f s p r i n gc a nb eg e n e r a t e db e t t e ra n db e t t e r a n o t h e ri sa d a p t i v eg a ，i nw h i c han e w f i t n e s sf u n c t i o ni sp r o p o s e db a s e de x p l i c i t l yo n l yo nt h el e a d e r so b j e c t i v ef u n c t i o n i t c a nb ee a s i l yc a l c u l a t e da n dc a n e f f e c t i v e l yd i s t i n g u i s hp o t e n t i a ls o l u t i o n sw i t hd i f f e r e n t q u a l i t i e s f u r t h e r m o r e ，a n e f f i c i e n tm u t a t i o n o p e r a t o r w i t hd i r e c t i o nm u t a t i o na n d b o u n d a r ym u t a t i o n i s p r e s e n t e ds u c h t h a tt h e o f f s p r i n g c a l l a p p r o a c ht o t h eg l o b a l o p t i m a l s o l u t i o n q u i c k l y t h i sa d a p t i v e g am a k e sp o p u l a t i o n se v o l v ei n s i d et h e c o n s t r a i n tr e g i o ng r a d u a l l y i n c h a p t e r2 ，t h ep r e s e n t e dh y b r i d g ai s a p p l i e d t oc o n v e xb l p pi n c l u d i n g q u a d r a t i c l i n e a rb l p pa n dq u a d r a t i c q u a d r a t i cb l p et h en u m e r i c a ls i m u l a t i o n sa r e d o n ea n dt h er e s u l t ss h o wt h ee f f e c t i v e n e s so ft h ea l g o r i t h m i nc h a p t e r3 ，f o rac l a s so f s p e c i a ln o n l i n e a rb l p p , t h el o w e rl e v e lo p t i m i z a t i o np r o b l e mi sr e p l a c e dw i t hi t sk k t o p t i m a l i t yc o n d i t i o n s ，a ne f f i c i e n ta l g o r i t h mb a s e do nt h ea d a p t i v eg a i sp r o p o s e da n d t h e g l o b a lc o n v e r g e n c e i s a n a l y z e dt h e o r e t i c a l l y b y t h en u m e r i c a ls i m u l a t i o n ，t h e r e s u l t ss h o wt h a tt h ea l g o r i t h mf o rt h i sk i n do f s p e c i a ln o n l i n e a rb l p p i se f f i c i e n t i n c h a p t e r4 ，f o rg e n e r a ln o n l i n e a rb l p p , t w ok i n d so fa l g o r i t h m sb a s e do nt h ea d a p t i v e g aa r ep r e s e n t e d t h e i rg l o b a lc o n v e r g e n c e so ft w oa l g o r i t h m sa r ep r o v e d n u m e r i c a l e x p e r i m e n t sa r ed o n e ，a n dt h er e s u l t ss h o wt h a tt h et w oa l g o r i t h m sa r ea l le f f e c t i v e b y c o m p a r i s o no ft h ep e r f o r m a n c eo ft h et w oa l g o r i t h m s ，i ti sc o n c l u d e dt h a tt w ok i n d so f a l g o r i t h m sh a v ea d v a n t a g e sa n dd i s a d v a n t a g e sr e s p e c t i v e l y k e y w o r d s ：g e n e t i ca l g o r i t h m b i l e v e lp r o g r a m m i n gg l o b a lo p t i m i z a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为西安电子科技大学或其 他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中做了明确的说明并表示了谢意。 本人签名：壅宏 日期知。弓。， 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印或其他复制手段保存论文。 本人签名_ 签芸 导师签名：三皇翌 日期2p p 3_ t - 第一章绪论 第一章绪论 1 1 引言 本文主要是用现代优化技术遗传算法( g e n e t i ca l g o r i t h m ，g a ) 来解决复 杂优化问题非线性两层规划问题( n o n l i n e a rb i l e v e lp r o g r a m m i n g p r o b l e m ) 。 遗传算法【l _ 4 l _ 2 7 - 3 0 l 是模拟生物进化及生物智能的信息处理机制而发展起来的 仿生算法，它使用群体搜索技术，通过对当前群体施加选择、交又、变异等一系 列遗传操作从而产生出新一代的群体，并逐渐使得群体进化到包含或接近最优解 的状念。遗传算法给我们呈现出的是一种通用的算法框架，该框架不依赖于问题 的种类。特别是对于一些大型、高维、复杂非线性系统，它表现出了比其他传统 优化算法更加独特和优越的性能。遗传算法不受其搜索空间限制性条件( 如可微、 连续、单峰等) 约束，也不需要其他辅助信息( 如梯度) ，因此，在传统优化方法 不能解决或难以解决的复杂、高维、大规模、非线性优化问题上，它具有独特的 优势。虽然，遗传算法已经有了很大的发展，但目前还存在很多问题，如理论不 完善，存在早熟收敛，收敛速度较馒等缺点。实践证明，要想有效地使用遗传算 法解决实际问题，那么根据具体问题设计一个恰当的遗传算法至关重要。我们设 计了合适的遗传算法来解决非线性两层规划问题，在设计遗传算法时，充分考虑 了两层规划问题的结构特点，使得算法具有有效性和高效性。 非线性两层规划1 3 5 。”】问题是具有两级递阶结构的复杂系统，它是将另一个优 化问题作为约束条件的优化问题。上层问题的瞬标函数和约束条件不仅与上层决 策变量有关，而且还依赖于下层问题的最优解，丽下层问题的最优解又受上层决 策变量的影响。这个决策问题包括一个上层决策者和一个下层决策者，其中上层 决策者起协调、主导作用。当两个独立决策者，在递阶结构中，有互相冲突的目 标时，就出现这种数学模型。其决策机制是：上层决策者首先向下层宣布一个决 策，陔决策直接影响下层的决策空间和目标函数，下层决策者在浚限制下根据自 身的利益( 使下层目标达到最优) 对此做出合理的反应，将自己的最优决策反应 给上层，下层的决策也影响上层的可行性和目标函数，根据下层决策者的反应， 上层决策者对其宣布的决策进行修正，最终使上层决策者找到使上层目标达到最 优的决策。值得注意的是，上层决策者只是通过有限的影响，而不是对下层结果 进行控制。由于两层规划问题本质上的非凸性和不可微性，解决起来比较困难， 而遗传算法不受这些因素的限制，因此，我们采用启发式算法遗传算法来解 决非线性两层规划问题。 第一章绪论 7 对于较大规模的遗传算法，只能借助于遍历性考察而得出粗糙的结论。 二是v o s e 模型：其思想是：用两个矩阵算子分别刻画比例选择与组合算子( 杂 交算子与变异算子的复合) ，通过研究这两个算子不动点的存在性与稳定性来刻画 遗传算法的渐进行为。在无限种群假设下，v o s e 模型可精确刻画遗传算法，但解 释实际有限种群遗传算法行为的能力相对差一些，而且该模型只适用于简单遗传 算法，对变异、杂交概率随时间变化的情形不易处理。 三是公理化模型：徐宗本等发展了一个既可用于分析时齐又可用于分析非时齐 遗传算法的公理化模型，其思想是：通过公理化描述遗传算法的选择算子与重组 算子。并利用所引进的参量分析遗传算法的收敛性。 四是连续( 积分算予) 模型：这是对采用实数编码的连续变量遗传算法的收 敛性分析，但分析连续遗传算法的框架与方法均不完善，存在着这样或那样的限 制与不足。没有一个好的方法可用于准确描述连续遗传算法的动念行为，并在不 强加任何严格的或人为条件下给出相关的收敛性结果。 1 3 两层规划的研究概况 1 3 1 两层规划的背景和应用 在社会经济、工程技术、管理部门及军事指挥等许多领域中存在着各种形式 的两层决策问题，如管理机构中的上下级关系，经济活动中的供销关系，军事系 统中的防御与反防御关系，企业中的公司与分公司关系等，对它们进行数学建模， 使整个系统发挥最大效益，即得两层规划问题p ”。两层规划问题的模型首先出现 在b r a c k e n 和m c g i l l 的论文中，有关资源分配问题以及攻击和防御同时进行时的 武器优化问题的研究。然而，c a n d l e r 和n o r t o n 在描述政策发展问题时，首次使用 “两层”或“多层”这样的术语。从那时起，两层规划模型就一直在具有递阶决 策系统的各种领域中使用，例如，在中央集权制下的经济计划中，由政府调节的 瓷源分配问题、农业信贷分配问题、电力部门的价格和计划问题以及税收信 贷决策问题，这些问题很自然形成两层规划问题。在国内工程中，为解决两层运 输网络设计问题，已经进行了广泛的研究。在化学工程中，两层规划问题应用在 化学过程平衡设计、在不确定条件下的设备设计以及带有控制问题的过程设计问 题i = ；7 1 。在危险性废品的管n k t 38 1 ，不精确的顾客需求下的生产计划安排| 3 6 l ，都用 两层舰划建模。 两层规划被广泛地应用在具有递阶特征的系统的数学建模中，如交通规划和城 市能源网络设计、经济决策和系统管理、政策制定、工程设计、军事指挥等。 解1 f 线性两层规划问题的遗传算法 由于两层规划问题具有鲜明的实际背景和广泛的应用前景，近年来受到应用 数学、运筹学、管理科学、决策科学、系统科学、经济学等众多领域的广泛关注。 1 3 2 两层规划的基本模型和延伸【3 5 - 3 8 1 设置f ，g ，x 分别是上层决策变量、目标函数、约束函数和约束集，_ ) ，g ，y 分 别是下层决策变量、目标函数、约束函数和约束集，则两层规划( b i l e v e l p r o g r a 唧i n gp r o b l e m ，b l p p ) 模型如下： 喈f ( x ，y ) s t o ( x ，y ) 0 ，其中y 求解， ( 1 i ) r a 。i n ，( x ，y ) s 1 g ( x ，y ) s0 其中，f ，f ：r ”“：一r ，g ：r ”“：_ r “，g ：r ”4 ：- r “，z e r “，y e r “2 分别 是石，y 的界约束。对问题( 1 - 1 ) 定义如下集合： 问题( 1 - 1 ) 的容许集( c o n s t r a i n tr e g i o n ) ： q - 缸，y ) 茗x y l o ( 工，) ，) o ，g g ，_ ) ，) o 。 容许集是上层和下层所能做出的全部选择的可能组合。 对给定的x e x 下层可行集( f e a s i b l es e t f o r t h e f o l l o w e r ) ： q b ) - y e r t g ( x ，y ) o 。 当然，上层必须选择这样的一个决策，使它不能与下层可行集有冲突。 q 在上层决策空间的投影( p r o j e c t i o no f qo n t ot h el e a d e r sd e c i s i o ns p a c e ) ： i 一仁并i 砂，s _ t g ，y ) e q 。 对给定的工j ，下层合理反应集( f o l l o w e r sr a t i o n a lr e a c t i o ns e t ) ： m g ) - ，l y e a r g m i n f ( x ，y ) l y e q b ) ) 。 下层合理反应集是隐映射，它表示下层对上层决策的反应。应注意的是，对某些 工x ，下层问题可能不可行，因此，对一些x ，合理反应集可能是空集。 第一章绪论 对给定的z 牙，下层最优值函数( t h eo p t i m a l v a l u ef u n c t i o no f t h e l o w e r - p r o b l e m ) v b ) t m i n f ( x ，) ，) i y q b ) 。 对给定的x 牙，问题( 1 - 1 ) 的诱导域( i n d u c i b l e r e g i o n ) 侬一妣，y ) l x x ，y e m ( x ) 。 上层通过给予各种决策x ，从下层诱出不同的合理反应。上层选择的所有可能的决 策x 和下层相应的合理反应_ ) m b ) 的并，就是诱导域。 因此，根据以上的定义，问题( 1 - 1 ) 可写成以下的等价形式： m i n f ( x ，_ ) ，) jb ，y ) - i r 。 ( 1 - 1 ) 是最简单、最基本的模型，在( 1 - 1 ) 中，当f ，g ，f ，g 都是线性函数时， 则( 1 - 1 ) 是线性两层规划：当f ，g ，g 中至少有一个是非线性函数时，则( 1 - 1 ) 是非线性两层规划。 当下层以最优值反应上层时，即得下层以最优值反应上层的两层规划，其模型 如下： 唑f b ，v b ) ) ( 1 2 ) s 。g 0 ，v b ) ) 0 ，v b ) 一r 渺 ，b ，y ) l g ( x ，y ) s o 其中，f ：r ”1 一r ，g ：r ”1 一只“，g , x ，y 同( 卜1 ) 。 问题( 卜2 ) 的求解方法与问题( 卜1 ) 类似，我们以下只讨论问题( 1 - 1 ) 。 此外，当下层有多个平行子问题时，即得下层有多个平行子问题的两层规划， 这类两层规划叱可仿照问题( 1 - 1 ) 的方法来解；在( 卜1 ) 中，当上层或下层，或 两者的目标多于一个时，即得多目标两层规划，这类两层规划求解更复杂，国内 有人研究【7 1 1 ，但限于简单情形，没有见到国外研究文献，本文没有讨论。 1 3 3 两层规划的研究现状： 两层规划问题是复杂的优化问题，主要表现在：约束的嵌套本性。下层问 题作为上层的约束条件之一，其隐含的互补条件决定约束的嵌套本性。诱导域 一般不具备凸性和闭性，有上层约束时还可能不连通。内在的非光滑性。因下 解非线性两层规划问题的遗传算法 屡合理反应集一般非f r e c h e t 可微，导致两层规划的非光滑性。对于上层问题 给出的某些参数下层问题可能是不可行的，或者可行，但有多个最优解，加大 了两层规划的研究难度。n p 一难的计算复杂性。 两层规划中对线性两层规划的研究比较完善。线性两层规划有重要的几何性 质：其诱导域由容许集的若干面组成，最优解出现在诱导域的极点处。该结论是 极点枚举法的基础。在计算复杂性方面，j e r o s l o w 证明线性两层规划问题是n p 一 难的，b a r d l 5 2 l 和b l a i r 等也相继确认此结论并给出简短证明，h a n 等给出最强结论： 线性两层规划问题是强n p 一难问题。求解线性两层规划问题的算法有：极点枚举法， 其睡型算法是“第k 最好算法”：k k t 法，其代表性算法有“分支定界算法”及其 变形“变量消除算法”、“互补转轴算法”，但互补转轴算法不能求出全局最优解； 罚函数法，w h i t e 等提出的基于下层对偶间隙的精确罚函数法等。 非线性两层规划的大多数仅限于下层是凸规划的情形，算法设计也是针对特 殊结构的问题，而且有些算法只能求局部最优解。 解非线性两层规划问题的一种思路是：把下层规划问题用它的k k t 最优性条 件来代替，将两层规划转化为如下形式的单层规划： 。m ，i 。n f ( x ，y ) ( 卜3 a ) s v ，g ，) ，) + 卢v ，g g ，y ) - 0 ， ( 1 3 b ) 腾，y ) - o ， ( 卜3 c ) g ( x ，y ) 量0 ， ( 卜3 d ) g ( x ，y ) 车0 ， ( 卜3 e ) “0( 1 3 f ) 其中e r m 是k k t 乘子向量。 当下层问题非凸时，k k t 条件仅是必要条件，这样解( 1 - 3 ) 只能得到问题( 卜1 ) 的局部最优解，甚至是次最优解。即使下层问题在凸性条件和一阶约束规格满足 的条件下，k k t 最优性条件是充要条件，但是，求单层问题( 卜3 ) 的全局最优解 也有困难，因为互补条件( 1 - 3 c ) 具有非凸性，而且当下层问题是非线性时，表示 平衡约束的等式( 1 - 3 b ) 也是非凸的。 另一种思路是：将两层规划问题转化为等价的d c ( d i f f e r e n c eo ft w oc o n v e x f u n c t i o n s ) 问题： d m ，i 目n f ( x ，y j 第一章绪论 i ( x ，y ) 一v ( x ) 。0 x ，) ，) q ( 卜4 ) 其中，v b ) t m i n f ( x ，_ ) ，) i g g ，y ) so ，y l ， ， q 一 “，y ) e xx y i c ( x ，y ) so ，g g ，y ) s0 。 还有一种思路是：用隐规划将两层规划问题转化为关于上层变量的单层问题。 m i n f ( x ，肘b ) ) s t g ( x ，m b ) ) s 0 ( 卜5 ) 其中，m 0 ) 一a r g m i n f ( x ，y ) l g ( x ，) ，) s o , y y 。 求解非线性两层规划问题的主要算法有： ( 1 ) 分支定界法。把下层问题用k k t 条件代替，将两层规划转化为单层规划问 题( 1 _ 3 ) ，用隐枚举法来处理互补条件，同时结合分支定界来解单层问题。此方法 主要解凸两层规划。b a r d 和m o o r e1 4 0 l 求解线性_ - 次两层规划：b a r d 【4 1 1 ，e d m u n d s 和b a r d l 4 2 1 求解二次两层规划问题：z h g t l m t l s 3 7 i 等提出基于可行集的松弛和分支 定界的框架来解非线性两层规划问题。 ( 2 ) 隐规划法。解问题( 1 - 5 ) ，v i c e n t e 等f 4 3 i 提出最速下降法。k o l s t a d 和l a s d o n i “l 把梯度信息用到问题( 1 - 5 ) ，来求无约束两层规划问题。 ( 3 ) 罚函数法。这种方法限于计算两层规划的平衡点或局部最优解。a i y o s h i 和s h i m i z u 4 5 j 【4 6 1 【4 7 】提出的算法的罚项与下层目标函数有关，i s h i z u k a 和a i y o s h i 删 提出双罚函数算法，将两层规划转化为无约束单层规划。 ( 4 ) 全局优化法。a m o u z e g a r l 3 8 1 ，s h i m i z u 和m i nl u 4 9 j 都将问题( i - i ) 转化为 问题( 卜4 ) ，分别提出不同的全局优化法来解非线性两层规划。 ( 5 ) 现代优化方法。用遗传算法【5 l i ，模拟退火算法【6 3 】来求解问题( 卜5 ) 从而 求解问题( 卜1 ) 。 1 4 本文的主要工作 两层规划的本质非凸性和非处处可微性给其数值求解带来极大困难，特别是 求非线性两层规划问题的全局最优解。遗传算法是求解此类问题的非常有效的启 发式算法。f 如此，我们充分考虑了两层规划问题的结构特点，设计了快速、高 效的遗传算法，来解决非线性两层规划问题。主要工作包括： 1 设计了两种实数编码的遗传算法，一是混合遗传算法，为了增强遗传算法 解1 f 线性两层规划问题的遗传算法 的快速进化能力，提高进化效率，把传统优化技术梯度投影法引入到遗传算 法中，充分利用遗传算法的全局搜索能力和梯度投影法的局部搜索能力，明显改 善了遗传算法的进化速度，克服了早熟收敛；二是自适应遗传算法，设计了合理 的适应度函数及有效的进化算子，其变异算子具有方向变异和边界变异的双重功 能，使得种群在算法开始时，从容许集的内部和外部搜索，逐渐使进化在容许集 中快速进行，搜索效率明显提高。 2 用所设计的混合遗传算法，解决了类凸两层规划问题，这类问题包括： 二次二次两层规划，二次线性两层规划，通过数值模拟，结果表明算法的有效性。 3 利用k k t 最优性条件把一类特殊的非线性两层规划问题转化为单层形式， 并用所设计的自适应遗传算法加以解决，并给出了收敛性证明。数值仿真结果表 明解此类非线性两层规划问题的算法是高效的。 4 对于一般形式的非线性两层规划问题，给出了基于自适应遗传算法的两种 不同的求解方法，对它们进行了收敛性分析，并比较了两种算法的优缺点。最后 通过数值模拟，结果表明算法是有效的。 本文的安排如下： 第一章绪论主要介绍遗传算法的概况，包括遗传算法的基本框架、执行策略 的改进、算法步骤以及基础理论研究概况：介绍两层规划的研究概况，包括背景 与应用、基本概念及研究现状；最后是本文的研究工作，并对全文各章节作了总 体安排。第二章我们设计了一种混合遗传算法，并用它来解凸两层规划问题，并 对算法进行了数值模拟。第三章我们设计了一种自适应遗传算法，把一类特殊非 线性两层规划的下层用k k t 最优性条件来等价代替，绘出了基于进化算法的求鼹 方法，最后给出了算法的收敛性分析和数值仿真。第四章我们对般非线性两层 规划进行了基于遗传算法的两种不同的算法设计，分别给出了它们的收敛性分析 和数值仿真，最后对两种算法进行了性能比较。 第二章用混合遗传算法解凸两层规划问题 第二章用混合遗传算法解凸两层规划问题 2 1 问题表述 考虑如f 形式的非线性两层规划： m a x f ( x ，y ) 琏x s a xsb ，其中y 求解 ( 2 - 1 ) 瞀，( x y ) “c x + d y s d 其中工r “，y r m ，f ，f ：r “，+ ”：r ，a e r m ，c e r 汹，d r 椭：，b e r ， d 尺。x ，y 分别是上、下层变量的界约束。 假设2 1 ，0 ，_ ，) 是二次连续可微凸函数，r ( x ，y ) 是关于岁的连续、严格凸函数。 给出以下基本概念： 定义2 1 称q = 戤，y ) e x y l a xs b , c x + b ys d 为问题( 2 - 1 ) 的容许集。 定义2 2 给定上层决策变量z 盖，称q g ) = y y i o y s d d 为下层可行集。 定义2 3 称牙t 仁x i ：l y y ，a x 6 ，c x + b y d 为q 在上层决策空间的投影。 定义2 4 给定上层变量x j ，称m 0 ) 侈y i y 仨a r g m a x f ( x ，y ) l _ ) ，q b 为下 层的合理反应集。 定义2 5 称侬a 缸，y ) l ( x ，y ) q ，_ ) ，m b ) 为问题( 2 1 ) 的诱导域。 定义2 6 , 称m a x f ( x ，y ) i ( x ，_ ) ，) 侬l 的最优解为问题( 2 1 ) 的最优解。 2 2 预备知识 出于上层约束只与上层决策变量x 有关，属于可分离约束，由两层规划的相关 定义可知，问题( 2 1 ) 等价于如下形式的两层规划： 解1 | 线性两层规划问题的遗传算法 m a x f ( x ，) ，) iy a r g m a x f ( x ，y ) i a xs b ，c x + o ys d ，z x ，y y t 。( 2 2 ) 定理2 1 问题( 2 - 1 ) 和问题( 2 - 2 ) 有相同的诱导域和最优解。 定理2 2 在假设2 1 下，诱导域侬是有界闭连通集。 证明：显然，q g ) 是有界闭凸集，由假设2 1 ，厂0 ，y ) 是连续、严格凸函数，于是 列每一个给定的z 牙，下层规划问题将有唯一的最优解，则b ) 是一个点对点 映射且连续，那么，诱导域能被唯一的连续的反映函数代替，f 扫 7 8 ，推论8 1 】知，r 是连通的。 显然，q 是凸多面集，且是有界闭集，那么q 在上层决策空间的投影牙也是 有界闭集。由假设2 1 ，f ( x ，) ，) 是连续、严格凸函数，而q g ) 是有界闭集，所以m g ) 是有界闭集。因此炽是有界闭集。 由上述可知，结论成立。 证毕 由于问题( 2 1 ) 的诱导域豫是有界闭连通集，而由假设2 1 ，f b ，y ) 是l r 上 的连续函数，显然，f ( x ，y ) 在r 上存在最大值，因此问题( 2 1 ) 的最优解存在。 问题( 2 1 ) 的松弛问题是： m 醒 f b ，) ，) ig ，y ) e n 。 ( 2 3 ) 问题( 2 3 ) 的最优值是问题( 2 1 ) 的最优值的上界 3 9 j 。 2 3 混合遗传算法 为了解决经典遗传算法在实际应用中存在的早熟收敛，全局优化速度缓慢和 解的精度差等缺点，在设计变异算子时引入了梯度投影法，可以充分利用遗传算 法的全局搜索能力和梯度投影法的局部搜索能力，使变异更加有效并能产生更好 的后代。 1 个体编码方案： 由于实数编码具有可表示的数域范围广，求解精度高，搜索速度快等优点， 也不存在二进制编码时的h a m m i n g 悬崖问题，非常适合求解连续变量的优化问题， 因此，我们采用实数编码形式来表示上、下层变量。假设第k 代种群为 b ， i y 。妊) 】， ) 月“，y l q , ) e n “。i 一1 , 2 ，p o p ，p o p 为种群规模。 第二章用混合遗传算法解凸两层规划问题 2 仞始化过程： 先确定出z 的取值范围，即解线性规划： m i n x m a x x j d s a xs b 求出上层决策变量x 的下界和上界。然后，在上层变量的取值范围中，随机均匀产 生p o p 个上层变量t ( 0 ) ，i ；1 , 2 ，p o p 。对每一个上层变量一( o ) ，解下层规划： 臀x r ( x ( o l y ) 眠d ys d c x 。( o ) 解得最优解y 。( 0 ) ，组成初始种群k ，( o i y 。( o ) ，ft 1 ，2 ，p o p 。 3 适应度函数： f i t n e s s ( x 。皓l y 。似) ) 一f ( x ，忙x y ，忙) ) 。 4 杂交策略： 设p 。是杂交概率，为了确定参加杂交操作的父代，从f 一1 到p o p 重复以下操 作：对每一个父代l 。忙l _ ) ，忙) 】，在区间【o ，1 】上产生一个随机数r ，若rt p 。，则选 择其为杂交个体。 假设在第k 代中任取一对父代为l ，( 七l y ，任) 和( 七l yj 似) 】，在开区间( o ，1 ) 上产生一个随机数口，对它们作算术杂交，杂交后的两个子代分别为k ；忙l u 忙) 】和 b 肛l v ，以) j i t ，。 卜( 七) - 似似) + ( 1 一口b ，( 七)卜，皓) - ( 1 一a k k ) + 饿，( 七) 1 q 忙) 。c r y 。犯) + ( 1 一a ) y ，任) 1 v ，忙) t ( 1 一a ) y 。忙) + 掣，忙) 。 由于容许集是凸多面集，所以所有杂交后代在容许集中。 5 变异策略： 设变异概率为p 。，为了确定参加变异操作的杂交后代，从f - 1 到p o p 重复以 下步骤：对每一个杂交后代k ，任l u ( 七) ，在区间【o ，1 】上产生一个随机数r ，若 ，c p 。，则选择其为变异个体。 对每一个被选择的变异个体，记为k 扯) - i n i 任) 7 ，v ，证) 7 r ，k ( ) r ” 。作 解1 r 线性两层规划问题的遗传算法 如f 变异操作得到后代d j ( ) u 1 r “”： o ? 扯) - k 扯) 十九d ( k 取) ) ，其中d ( k ( 七) ) 是k 取) 处的可行上升方向， d ( 任) ) 。l ，一爿j 0 。爿j ) - 爿。扣f 取) ) ，爿。为k ) 处所有积极约束的系数矩阵，q 表示积极约束个数1 7 9 】f 。a 。是搜索步长，为简单起见，可以先取定某一定值 ，0 ， 逐次验证f ( d j ( 女) ) 是否大于f ( 七) ) ，若大于，则取。舷) 为变异后的新个体，否 则取九t 必，再进行验证，一般经有限次后总可保证大于号成立。否则取 0 i 取) = ( ) 。 若爿。中，即k 扯) 在容许集的内部，则d 伍) ) - v f ( v ( k ) ) 。这样做的目的 是始终保持变异个体处于容许集内，并且个体有所改进。当个体在容许集内部时， 沿梯度方向进化；当个体在某些约束的边界上时，将该个体处的梯度投影到a 。的 零空问，a 。是以积极约束或部分积极约束的梯度为行构成的矩阵，这样的投影是 上升可行方向，沿此方向个体既可以进化，也处于容许集内。 为了防止出现早熟收敛，在变异策略中加入随机搜索。从i - 1 到p o p 重复以 下步骤：对每一个杂交后代k 似) 。b 。( 七) ，u ( 七) 7 7 ，k 扯) r n ”：在区间【o ，1 】上产 生一个随机数r ，若rcp 。，贝l 选择其为变异个体。对每个被选择的变异个体， 作如下变异操作得到后代d 舡) r ”“： 0 7 ( k ) - k 皓) + 帜妖) ) 。其中a 售) ) 一( ( o n ，( o ，：1 ) ) r ，( o 1 ) 表示标准正 态分布。且取) ) 的起，+ 以：个分量相互独立。检验变异后代c 舷) 是否属于容许集 q ，取掉不属于容许集的变异后代。、 将两种变异后代合在一起，组成第i 代的变异后代d 取) 一 d ( k ) u o ( 七) q 。 6 选择策略： 为保持种群的多样性，按比例选择一定量的父本，杂交体及变异体作为新种 种，种群规模保持不变。父本，杂交体及变异体分别按适应度大小来选择。 7 最优保留策略： 最好的个体不一定出现在最后一代，所以在进化开始时必须把最好的个体保 第二章州混合遗传算法解凸两层规划问题 1 7 留下来，如果在新种群中又发现更好的个体，则用它代替前面保留的个体，在进 化完成之后，保留下来的个体就看作问题的最优解。 8 终止条件选择： 由于求解问题( 2 - 1 ) 时，最优解事先无法知道，所以只能采用给定一个最大 进化( 迭代) 次数作为终止判据。 2 4 双层决策问题( 2 - 1 ) 的算法思想及步骤 2 , 4 1 算法的基本思想 在第k 代，设种群为i x 。忙l y ，忙) ，i ；1 , 2 ，p o p ，把每一个上层决策变量 忙) ，i t l , 2 ，p o p ，代入下层规划中，求出下层规划问题的最优解，记为 只忙) ，f 一1 ，2 ，p o p ，再把k 忙1 只伍) ，i - 1 , 2 ，p d p 作为第k 代中间种群反馈给 上层，求出并且保留最好解a r g m a x f ( x 。妊x 只任) ) i f - 1 ，p d p ，然后对中间种群 b ；( 七l 罗。( ) ，it 1 ，2 ，p o p ，利用混合遗传算法得出第t + 1 代种群。如此反复操 作直至满足终止条件。输出最好解。 2 4 2 算法步骤 s t e p l 确定杂交概率p 。，变异概率p 。，种群规模p o p ，最大进化代数j v 。置k = o ， 由自h 述的方法，产生初始种群户扯) 一k ( 七l _ ) ，忙) 】i 。1 , 2 ，p o p 。 s t e p 2 把一似) ，代入下层，解下层规划问题，求得最优解只( 七) ，i 一1 , 2 ，p o p 。 s t e p 3 把k ，忙1 只忙) 作为中间种群，求每个个体的适应度，并保留最好解。 s t e p 4 对中问币申群迸行杂交，变异，选择操作，得出下一代种群 p 忙+ 1 ) t b 忙+ l x y 。伍+ 1 ) 】，i - 1 , 2 ，p o p 。 s t e p 5 若满足终止条件，则停，输出保留的最好解。否则，令k = k + l ，转s t e p 2 。 解非线性两层规划问题的遗传算法 2 5 1 数值模拟 图2 1 计算程序框图 2 5 数值模拟及结论 为了验证本算法的有效性，我们用m a t l a b 5 3 编制了仿真程序，并在p c 兼 第二章用混合遗传算法解凸两层规划问题 1 9 容机上进行测试。算例1 、3 、4 的下层规划，我们调用了m a t l a b 5 3 的