（运筹学与控制论专业论文）求解两类特殊双层规划问题的遗传算法.pdf

摘要 近年来，随着科学技术的日益发展，决策变得越来越复杂、上下级的交互决 策越来越普遍，因此，双层规划在生活中得到广泛的应用，引起了人们的极大关 注。本文主要研究双层规划闻题的理论和算法。双层规划的n p 难性、j # 跫性和不 可微性给其数值求解带来极大困难，特别是求解非线性双层规划问题的全局最优 解就更加网难。遗传算法是一种求解复杂非线性优化问题的新型有效的现代智能 优化方法，它酶优点是不受目标函数的凸性、霹微性、连续性等的限制，与传统 优化方法相比，特别对一些大型复杂优化问题，具有独特的优越性。 本文主要考虑了双层规划的复杂性和遗传算法的优点，用遗传算法来求解双 层规划问题。在利用遗传算法来解决双层规划闽题时，充分考虑了双层规划问题 的结构特点，通过适当的处理，降低维数，缩小搜索空闻，使得用遗传算法的求 解更加快速。 首先，对两类特殊结构的非线性双层规划问题，将下层的最优解用上层的决 策变量或l a g 鼹l g e 乘子表示，并将下层的最优解代入上层中，便可将双层规划阀 题转化为含有上层决策变量l a g r a n g e 乘子的单层规划问题。其次，分别设计了一 个改进的凸交叉算子和一个新的交叉算子，在此基础上，分别设计了求解这两类 特殊的非线性双层规划问题的遗传算法。进一步，分析了算法的全局收敛性。最 后，对所提出的两个算法进行了数值仿真，结果表明这两个算法是有效的。 关键词：双层规划二次规划遗传算法全局优化 a b s t r a c t w i t ht h l ef a s td e v e l o p m e n to fs c i e n c oa n dt e c l l n o l o g yi nr e c e n ty c a r s ，m o r ea n dm o r e d e e i s i o nm a k i n gp b l e m sw i 也也e 撼e 斌c h i c a ls t 挪c t u f eh a v ea 戚s e ni n 璜a n y 蠡e l d s 。 髓l e s e 弘静麟。氆s 蠡轮l l yb e c 凇e 毯i 棼v 嚣lp 鼯g 怒撒黻i 器gp 街纛l e 趱sa l 薹莲辩s u l 溆m o 瓣 d i f j f i c u l 够硒rd e c i s i o nm a k e r s b i l e v e lp r o g r 锄m i n gp r o b l e m sa r ew i d e l yu s e di no u r l i f e m u c ha 讹n t i o nh a sb e e np a i dt ot h i s6 e l di n c e n ty e a r s h o ，e v e r ，t h es o 】u t i o no f 毯k v e lp 鳓踟螨n gi sv e 碜d i 臻e u l 毫埝g e 鼍酶c a n s e 醴i l s 魏一e v e x i 镟n p 囊a 通 e h a f a e t e 蝣s l i ca n dn o n d i 重琵r e n 毫主a 毯l i t y 酗p a n i c u l a 如i li sm o r e 崩掰c u l tt og e ti 量sg l o b a i o p t i m a ls o l u t i o n g e n e t i ca l g o r i t h m sa 心an e wk i n do fe f f e c t i v ea l g o r i t l l r l l sf o rc o m p l e x o p l i m i z a o 稳p r o 琰锄s 。弧e yh a v e 致om h e hf e s 城c l i o 琏o nr e l a l o d n e l i o n s ，s 獬羲8 s 蕊陵糯n 熏至豳i l i 移，e o 鑫v e x i 毋，e o 蛾i 鞠a 鼍主o n 勰ds oo n e 蹲撼越l y ，如r m el 皴鬈e s c 鑫酶 c o m p l e xn o n l i n e a ro p t 椭i z a t i o np r o b l e m s ，t h e ya r eu s u a n ys u p e d o rt ot r a d i t i o n a l o p t i m i z a t i o n8 p p r o a c h e s ， c 鳓s i d e 蠢耀氇e 硪箍e u l 碜o f 琰l 粼e lp 秘群猢m i 箍g 鞠d 落e 鬈莲函煳鞠o f g e n e t i ea l g o r i t h 王l l ，g e n e t i ca l g o f i t 量1 m sa 1 ea p p l i e dt os o l v eb i l e v e lp r o g r a m l n i n g t h e s t m c t u r e 曲a r a c t e r i s t i co fb i l e v ep r o g 粉m m i n gi sf u l l yc o n s i d e r e di nt h ep r o c e s so f s o l v i n g 糯霉b i l e v e lp 糊g r 黼m i n gb ya d o p t i n gp 姻p e rs 甄l l s ，瓣婊a sd e e r e a s i n g 也e p b l e m 魏稳e n s i 油s 鑫n 娃s e a 幽s p a e e a saf e s u l 鼍，鳓。s 挥e 莲甜诋；g 蔽i c 采舻砖l h 搭 w i l lb em o r eq u i c k l y i nt h i st h e s i s ，蜀r s t ，f o rt 、约8 p e c i a le l a s s e s 靠n o n 】i n e a rb 谴e v e l p r o g r a m m i n g p 羚b | e 璐s ，娅礞l i 璎a 差s o l 避i 潍o fl h el 鳓嘴r 1 e v e lp 羚b l e 璎i s 阉笋e s e 蹴db yt k u p p e r l e v e lv a r i a b l e so rl a g r a n g em u l 邱玎e f s ，i e ，t h e1 0 w e e v e lv a r i a b l e sa r ea f u n c t i o no fu p p e r l e v e lv a r i a b l e s 1 e nt h eb i l e v e lp r o g r 咖m i n gp r o b l e mc a nb e 瓣n s 内燃艇i 奶鑫 s i n g l e l e v e lo p t i m i z a l i 强p f o b l e me o n l a 赫罐 壤e嘲e r l e v e l v 碰曲l e s 黻l a 蓼孤g em 毛l l i p l i e f s 翻黔珏醇愆p l a c i 蜷l h el o 硪静l e v e lv 描曲l e sb y 氇i s 如n c t i o n s e c o n d ，a 1 1i m l ) r 0 v e dc o n v e xc r o s s o v e ro p e r a t o ra 1 1 dan o v e lm u t a t i o no p e r a t o r a f ed e s i g n e d ，r e s p e c t i v e l y b a s e do n 搬e s e ，t w on e 、 ，g e n e t i ca l g o r i t l l m sa r ep r o p o s e df o r 毛& 辩翩e l a s s e so f 纛。魁l i 黼嚣黾i | e w lp r o g 勰m i 甥p b e 趣s 羚蹲e e 矗v e l y ，m 雠w 毛 t h eg l o b a l n v e 毽e n c e0 ft h ep r o p o s 砌a l g o r i t h m si sp r o v e d a tl a s t ，t h ee x p e r i m e n t a l s i m u l a t i o n sa r em a d e 蝴dt h er e s u l t si n d i c a t et h ep r o p o s e da l g o r i t h m sa r ee f f e c t i v e x 句恻。蝴s ：g 锺e l i e 建l g o 确囊mb i l e v e lp r o g r 冀m 黼i 珏gq 毯矬d r 8 耄i ep 硒g 薹i 建搬m 泌g g l o b a lo p t i m i z a t i o n 剖薪性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特裂烟以标注和致谢中所罗列静蠹容以外，论文中不 包含其他入已经发表或撰写过静研究成果；也不包禽为获得嚣安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 孛请学位论文与资瓣若喜不实之处，本人丞挝切相关责证。 本人签名：匿糕；略| 2t 落。 关于论文使用授权的说明 本人完全了解嚣安魄子辩技大学霄关僳鍪帮馊臃学位论文的溉定，霹：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保整送交论文的复印件，允许查阅和借阕论文；学校可以公布论文盼全 部或部分蠹容，可以兔诲采霜影霹、缩窜或其它复制手段保存论文。( 保密麴论 文在解密后遵守此规定) 本人签名： 导师签名： 爨期： 蹬斓：兰翌盘：z 星：星笸 第一章绪论 第一章绪论 1 1 引言 本文主要是应用现代智能优化算法一遗传算法( g e n e t i ca l g o r i t h m ，g a ) 来求解 两类复杂优化问题一双层规划问题( b i l e v e lp r o g r a m m i n gp r o b l e m ) 。 双层规划问题是一种具有两级递阶结构的复杂系统，结构分为上下两层，即 上层规划和下层规划。上层规划问题的目标函数和约束条件不仅与上层决策变量 有关，而且还依赖于下层规划的最优解，而下层规划的最优解又受上层决策变量 的影响。它具有层次性，上层规划首先做出决策，确定上层决策变量，然后下层规 划在上层规划确定上层决策变量的基础上，做出自己的决策，求出下层规划的最 优解，然后将该最优决策反馈给上层，下层的决策也影响上层规划的目标函数和 可行域。上层规划根据下层规划的决策，再对其决策进行调整，最终找到使上层 目标函数达到最优的决策。双层规划分为两类：一类是不合作的双层规划，即上 层规划在确定自己的最优值时，完全不考虑下层规划的最优值；另一类是合作的 双层规划，上层规划在做出决策时，考虑下层规划的最优值。双层规划问题比熟 知的单层数学规划复杂得多，主要表现在：( 1 ) 约束的嵌套本性；在双层规划中， 因为下层问题的介入，由其隐含的互补条件决定了约束的嵌套本性。( 2 ) 非凸性； 可行集一般不具备凸性和闭性，有上层约束有时还可能不连通。( 3 ) 内在的非光滑 性；( 4 ) 计算复杂性；双层规划是一种n p 难问题。由于双层规划问题的嵌套性， 非凸性，非光滑性，n p 难等，造成了用传统优化方法求解双层规划问题比较困难， 求其全局最优解更就加困难。 遗传算法是模拟生物界的进化过程而产生的一种现代智能优化方法，它使用 随机概率搜索技术，具有操作简单、通用性强、鲁棒性强和便于并行处理等特点， 被广泛应用于众多领域。遗传算法将问题的所有可行解集看作解空间，从代表问 题的潜在可行解的一个初始种群开始，通过对种群( 潜在可行解的子集) 施加选择、 交叉和变异等一系列遗传操作，从而产生新的解集( 潜在可行解的新子集) ，并逐 渐使种群进化到问题的最优解状态。遗传算法在整个进化过程中，它是直接以目 标函数值作为搜索信息，它仅需要目标函数，不像传统优化方法，往往需要目标 函数的导数值或梯度，而遗传算法在求解的过程中不受目标函数的连续或可微， 多峰等性质的限制。因此遗传算法特别对于求解一些离散的、大规模的、n p 难的、 高维的、非光滑的、不具有凸性和可微性的函数，多峰函数，复杂非线性系统等 问题，具有比其他传统优化算法更加独特的优越性。遗传算在使用时具有很大的 灵活性，在实际应用中，灵活使用和设计遗传算子( 选择，交叉，变异) 对解决问题 2 求解两类特殊双层规划问题的遗传算法 有很大的影响。 本文鉴于双层规划问题有嵌套型、非凸性、n p 难性、而且往往不连续或约束 不连通、非光滑等复杂性，用传统优化方法求其全局最优解有很大困难，而现代 优化方法遗传算法具有不受非凸性、不连续，菲光滑等限制，它采用全局随机搜 索，可求得全局最好解。这样，应用遗传算法对双层规划问题进行求解，可以克 服传统优化的缺点，可求得双层规划的全局最优解。因此，本文用遗传算法求解 双层规划问题。 1 2 双层规划的研究概况 l 。2 1 双层规划的背景和应用 随着经济、科技和社会的不断发展，人们在实际生活中遴到问题的规模越来 越大，结构越来越复杂，也逐渐显示出了层次性。在经济全球化的今天，竞争越 来越激烈，决策问题显得越来越重要，它影响着企业的经济效益和竞争力，在社 会经济、社会管理、企业管理，工程技术、工业设计、制造业、经济决策、系统 管理、政策制定、交通旒划、军事指挥等众多领域中存在着各种形式的具有递阶 特征的层次系统优化问题，其中最麓单的多层优化问题双层规划，存在于我们的 日常生活中，例如资源分配问题，它是类比较复杂的管理问题，上层部门将资 源分配给多个下层部门，下层部门根据分配到的资源组织生产，使自己的利益最 大。由予上层部门拥有有限的资源，各部门的生产效益又不同，如何使用有限的 资源产生最大的效益是上层部门面临的最大问题；许多跨国公司和它的许多子公 司之间的决策问题；在管理机构中的上下级关系；经济活动中的供销关系；企业 中的总公司与分公司关系等；企业和市场之间的价格决策关系；总批发商和代理 商，对这种递阶结构的决策问题进行数学抽象和数学建模，得到的数学模型就是 双层规划问题。双层规划在生活中的广泛应用，影响着人们的生产和生活，促使 了人们最它的研究和探索。 1 9 7 3 年，b 豫e l ( e n 和m e g i l l 提出了双层规划问题的模型n 3 ，1 9 7 7 年，c 蠲d l e f 和 n o n o n 首次在报告中首次提出了双层规划和多层规划的概念瞻】。s 妣k e l b e f g 研究市 场经济建立了s t a c k e l b e r g 博弈模型，该模型在经济中得到广泛的应用，使得双层规 划得到了人们的充分的重视。近年来，双层规划受到了应用数学、运筹学、管理 科学、决策科学、系统科学、经济学等众多领域的广泛关注，从瑟也罨| 起了许多 学者的研究兴趣，许多学者对双层规划和多层规划问题深入了研究，使用不同的 思想和方法提出了许多有效的算法，为人们的生活做出了巨大的贡献。 第一章绪论 1 2 2 双层规划问题基本模型： 双层规划的基本模型： ( b l p ) m i n f ( x ，y ) 一g 哆亍o ( 1 1 ) m i n 厂( x ，y ) 、 s jg ( x ，y ) s o 其中：x r ”，y r ”分别称为上层规划问题和下层规划问题的决策变量， f ，厂： 月肿”专尼，g ：r 肿”专r 尸， g ：r ”脚专r 9 。 从上面的模型中可以看出作为两层决策问题的双层规划是一种具有两层递阶 结构的系统优化问题，并且上层规划问题和下层规划问题都有各自的目标函数和 约束条件，上层规划问题的目标函数和约束条件不仅与上层规划问题的决策变量 有关，而且还依赖于下层规划问题的最优解，而下层规划问题的最优解又受上层 决策变量的影响 1 2 3 双层规划的定义及其概念： 对于问题( b l p ) 定义如下概念： 问题( b l p ) 的容许集：q = ( x ，j ，) x 】，l g ( x ，y ) s 0 ，g ( x ，y ) 0 ) 对于上层给定的x x ，下层规划问题的约束域：q ( x ) = 抄ig ( x ，y ) 0 ) q 在上层决策空间的投影：元= x i j y ，使得( x ，y ) q 对给定的x 叉，下层规划的合理反应集： m ( x ) = yiy a r gm i n 厂( x ，y ) ly q ( x ) ) 下层合理反应集是隐映射，它表示下层规划对上层决策的反应。有时对于上层 的某些x x ，下层可能有多个反应j ，与之对应，即下层规划问题的最优解不唯一， 有时对于某些x x ，下层问题可能是不可行，因此，有时对于一些x ，下层合理反 应集是空集。 对于任意给定的x 和相应的y m ( x ) ，问题( b l p ) 的下层规划问题的最优值： 1 ，( x ) = ( x ，y ) 。 4 求解两类特殊双层规划问题的遮传算法 对给定的x 贾，问题( b l p ) 的诱导域：缓【( 麓y ) | x z 罗掰( 曲 则问题 ( b l p ) 就转化为如下形式的优化问题：睁 f o ，j ，) l ( x ，j ，) 皿 。 定义1 1 ：如果( 为少) 豫，则称点( 墨力为双层规划问题( b l p ) 的可行解。 定义1 2 ：如果存在( f ，) 豫，对于任意0 ，y ) 豫有f ( 0 ，) f ( x ，y ) ，则称 点( x + ，y 。) 为双层规划问题( b l p ) 的最优解。 1 2 4 约束优化的最优性条件 全局最优解嘲：设，：掣一定为毯标函数，s 篓美”为可行域，i s 。 ( 1 ) 对于一切x s ，都有厂( i ) 墨( x ) ，则称i 为厂( x ) 在s 上的全局最优解( 极 小化问题) 。 ( 2 ) 若对于一切x s 但x i ，都有，( 西 八x ) ，则称；为( x ) 在s 主的严格 全局最优解。 1 等式约束优化问题： 仨莴) ”地， ( 1 2 ) i j j 办，( x ) = o = 1 ，2 ， 、 其中，：露”一震，恐：定4 一定，歹= l ，2 ，。 定理1 1 嘲：设厂：r ”一r 在i 鼹r ”处可微，_ ：r “_ 尺( ，= l ，2 ，z ) 在点i 处 具有一阶连续偏导数，向量组v 盔( i ) ，v 魄( ；) ，v 趣( ；) 线性无关。若i 是问题 ( 卜2 ) 的局部极小点，则存在实数e ，= l ，2 ，使得， ， 夥( i ) 一e v 哆( ；) = o ( 1 - 3 ) l 定理1 2 陵：对于闷题( 卜2 ) 中，是凸函数，哆( 歹= l ，2 ，) 是线性函数，i 可行点，并且在点茹可微，若i 是问题( 卜2 ) 的局部极小点，则；是问题( 卜2 ) 的 全局极小点，厂( 动为闯题( 1 2 ) 的全局极小值。 2 不等式约束优化问题： 第一帮绪论 陋纛，茗) ( 1 嘞 l s 0 舅( x ) o = l ，2 ，磁 其中：( x ) ：火”岭r ，吕( 搿) ：尺”一r ，( f = l ，2 ，聊) 。 k u 妇t 珏e k f 条件： 用，( i ) 表示在可行点茹处起作用约束的指标集，即 z 6 一 f l 臻( 动= o ，f = l ，2 ，搬 定理羔。3 雠：设i 是阍题( 董一4 ) 的可行点，秘藏( i 芒f ( i ) ) 在点；处可微， 蕊( 彗j 动) 在点；处连续，并且魄( ；) ( 芒j ( ；) ) 线性无关。若；是随题( p 4 ) 熬局 部极小点，则存在菲负数麓( 建j ( ；) ) ，使得 叭；) 一m 魄( i ) = o 挺艇 如果g ( 堙，( 动) 在点；处也可微，则存在咎o ( = l ，2 ，磁) ，使得 l 蹦动一萋辑吲动一s ) ，。lti 一 ， i 够爱并) 一执江l ，2 ，掰 称i 为问题( 卜4 ) 的k - t 点。 定理蔓。唾瀚：设在润题( 卜毒) 中，秘一警，f = | ，2 ，搬) 是瑟龋数，i 是霹符 点，并且，和畿( 堙歹；) ) 在点；处可微，若蔓是阕题( 卜4 ) 的k t 点，测i 为闷题 ( 卜4 ) 的全局极小点。 l 。2 。s 双瑟规划酶主要特点： ( 1 ) 层次健；双层规划分为两层，瑟上层规划和下层规划，下层服从主层，僵 有一定的是主权，下层规划在上层决策变量的基础土，来优化爨邑的目标函数， 求其全局最优解。 ( 2 ) 独立性：上层和下层分别控制着自己的决策变量，独自优化自己的目标函 数值，确定其决策变量。 ( 3 优先性：上层规划苔先优化照己的酱标蘧数，确定上层决策变量，然麓下 层规划根据上层给出的决策变量，优化目标函数，求其最优解。 ( 4 ) 冲突性：由于上层规划首先做出决策，然后下层规划做躜决策，再反馈给 6 求解两类特殊双层规划问题的遗传算法 上层规划，然丽这些嗣挺往往是相互冲突的。 ( 5 ) 良主性：上层麓决策可能影螭下层鲍决策，宅只是部分的影响，下屡规划 可以在上层规划给出的决策变量的基础上可以优化自己的目标函数值。 ( 6 ) 制约性：下层规划不但可以优化自融的网标函数值，而且做出的决策反馈 给上层觏划爵，影响上莹酶西赫醋数值，因就，上层篾划在徽惠决策时，也要考 虑下层的决策对翻己的影响。 ( 7 ) 依赖性：由上面的定义可以看出，约束域般是不可分离的，形成个相 关的整体。 1 2 6 酲前求解双层规划的主要算法融3 ： 双层规划是多层次规划中最简单一种，辍然双层规划从模型和概念的提出到 现在仅3 e 多年发展煎历史，缀是它褥到了重视，嚷雩| 了人稍斡兴趣，人们徽了大 量的研究，从而提出了许多有效的算法，大致有：极点搜索法、分枝定界算法、 互补旋转法、下降方向法、罚函数法、模糊数法、k 。k - t 法、遗传算法和其他一些 饶纯方法等。 ( 王) 极点搜索法 极点搜索算法最早、由b a r d 等人瞄1 在约束集有界的假设下，证明了线性双层规 划最优解豹个数为有限个，在约束集的极点处，至少存在一个极点是最优解，于是 基于这个牲覆，提掰了授点搜索法。其中比较著名的极点接索法有k 次最好法帮播 搜索法。s h ic h e n g g e n 和z h a n gg u a n g q u a i l 阳3 在新定义双层线性规划的基础上，提出 了推广的k 次最好法求解双层线性规划问题，而且还提出了求解下层具有多个决策 者的双层线性规划润题麴k 次最好法。极点算法主要簿决双层线性规划，其基本愚 路是，线性双层规划问题的任何解都出现在下层规划的约束集合的极点处，首先 可以利用各种方法来找到约束空间的极点，然后从中找出双层规划问题的局部最 优解或全麓最貔解。 ( 2 ) 分被定界法 分枝定界法在数学规划中被广泛的应用，它般可以收敛到全局最优解，主 要用于求解整数规划，也被广泛应用于求解双层问题中。f o m m y a m a tm c c 甜1 1 首 先把双层二次撬划藏题转纯势单层混合整数的二次规翔阗题，然蜃蹋分授定秀求 解，来求得全局最优解；b a r d 和嚣d m u n d s 等秘提出了求解二次双层规划的分枝定界 法和求解整数线性双层规划的分枝定界法，w e n 和y a n g 等阻3 提出了求解整数线性二 层规矧的分技定赛法。分枝定赛法主要应翔予求解双层整数援划当中，分技定界法 的基本思路是报据事先选定的分棱准则，将所求解的闻题分成一系列子阏题，并 从中选取个子问题进行检验，决定其取舍。分枝定界法计算量很大，但它能求 篇一章绪论 7 得全局最傀解。 3 ) 互孝 旋转法 b i a l a s 等h 们最早提出了互补旋转法来求解线性双层规划。此算法可以看作是下 层最优基的隐迭代，并且算法的所有计算像单纯形表的框架中进行。后来b i a l a s 和 k 鑫测- 鼹n 蝣指露这种互补旋转法不麓求凄全局最优解，后来由j u d i e 尊和f 勰s l i 瀚稚砖改 进了互补旋转法，使得能够得到全髑簸优的互补旋转法，提出了序列线性嚣补算 法，求得线性双层规划和线性二次双层规划的s 全局最优解。豆补旋转法主要思想 是将闭题转化为一个带参数酶线性互补闯题，然蜃耀受限基算法，也就是带参数 熬互替主元算法进行求解。该方法是种疟发式算法，有时不畿确保牧敛于全焉 最优解。后来对此算法进行修正，提出了连续线性互补旋转算法，确保了算法的 全局收敛性。 4 ) 下降方向法 下降方向法有主要有三种：第一种算法是最速下降方向法，s a v 莉轴用最速下 降来求解双层非线性规划。v i c e n t e 等n 削针对双层严凸二次规划和凸二次规划，这 特殊的结构提出了两张下降算法，释基于旋转尺度下降方法，但是它不麓保证 鼹帮最键。第二释是改良的最速下降滋，在其中学| 入了计算精确步静薪规则，并 且提出了结合这两种策略的混合方法，但这种方法缺乏收敛性。后来我国数学学 者韩继业，划豳山和汪寿阳n 硼提出了一祧具有收敛性的新的下降算法，可以用来求 解双层二次规划和线髅二次双层规划瓣题。第三释方法是k o l s 灏帮勰莲微驺硝提箍 的下降算法来求解非线性双层规划。 ( 5 ) k k 。t 法 k 矗法黧基本思路是褥双层规划阏题中的下层援划用k ，k 曩条彳譬代瞽，姨嚣 将双层规划阀题纯秀单层菲线性规剿阀遂求解，这种算法仅对于下层是凸勰鲻有 效，但是它的决策变量较多和约束较多时，计算量也较大。 ( 6 ) 罚函数方法 嚣溺数法是数学瓶划中常雳的一种方法。a 鼗鑫蕊遘采赫窑8 越靼w 歉i 绝翻提斑了对偶 间隙作为惩罚项的罚函数方法。y l vn 硝等提出了求解弱价格控制问题的罚函数方 法和基于k u h n t u c k e r 条件求解双层线性规划的罚函数方法n 9 1 。l i u 等咖1 为凸双层规 划提出了一耱薪的约寨掇格，在此约柬规格下给蹴了凸双层规划阍题的局部和全 局的一阶精确弱蠡数法。万缔平和溺树民疆琏把罚函数法和近似双层规划结合起来 提出了近似罚函数法来求解带有线性约束的双层规划问题，并得到了收敛的罚函 数方法。罚霸数方法主要应用非线憔规划理论中的蹯函数原理，利用各种不同形 式麓惩罚顼，把下层瓣题转纯为一个秃约束数学规划翔题，然蜃援惩嚣顼加别主 层目标函数中，将问题转化为一个带惩罚参数的单层问题，稃通过求解系列非 线性规划来求得问题的全局最优解。 8 求解两类特殊双层规划问题的遗传算法 ( 7 ) 模糊数学算法 裴峥、黄天民疆2 针对上层有约束条件、下层有n 个独立的决策单元的线嬖耋双层 规划问题，提出了一种模糊数学解法。刘新旺、达庆利盘3 1 针对多人递阶资源分配 问题提出了对决策者模糊满意度进行两步折衷的求解算法。其基本思路是充分利 用模糊数学中隶属函数及模糊算子的概念和性质，分别建立土层决策变量的隶属 函数和上、下层决策者目标函数的偏好隶属函数，将双层规划问题转化为单层规 划问题，分别对各单层规划的解进行讨论，最终把双层规划问题转化为求解单层 规划问题，求得两层决策闻题的满意解。 ( 8 ) 遗传算法方法 m a t h i e u 等嘲1 提出了解线性双层规划问题的遗传算法，将上层的决策变量随机 生成，然后通过求解一个线性规划得到下层的反应，而且在其遗传算法中仅使用了 变异算予，然而在该方法中由于每一个霹行的个体不一定代表一个极值点，焉是代 表一个可达的解，这样扩大了搜索空间。因此，h e j a z i 等汹提出了一种遗传算法， 在该算法中每个可行个体代表可行域的一个顶点，因而大大减小了搜索空间，l i u 啪 提出了求解多层规划s t a c 惫e l b e r g - n a s h 平衡的遗传算法。n i w a 等3 应用二进制编码 的遗传算法来求解分布式双层o l 规划问题。0 d u g u w a 和r o y 汹1 提出了一种求解双 层规划遗传算法，通过两个参与者之间有限的非对称合作从而在单一框架中来求 解不同类型的双层规划问题。其基本思想是通过对决策变量进行编码，然后利用 遗传算法的随机全蜀搜索，来褥到润题的全局最铙解。 此外，还有模拟退火、粒子群算法、割平面方法、禁忌搜索算法、信赖域算 法，同伦算法等求解双层规划的方法。 以上是入们提出的一些算法，其实也有不少学者积极研究双层规划闷题的最 优性条件。总体上人们主要通过各种不同的方法，将双层规翊转化为单层规划闻 题来研究。 l 。3 本文的主要工作与内容安排 本文主要研究了两类具有特殊结构的双层规划问题，并针对这两类特殊双层 规划，设计遗传算法进行求解，并进行数值试验，实验结果表明了遗传算法的有 效性。全文共分为四章，具体安排如下： 第一章为绪论部分，主要简单的介绍了双层规划问题的基本概念和基础知识， 以及研究现状。 第二章较为详细的篱绍了遗传算法的基本概念、主要特点、基本框架及其广 泛的应用。 第三章深入研究了上层规划的目标函数和约束没有凸性和可微性要求，下层 第一章绪论9 规划为关于下层决策变量为正定二次规划的这一特殊结构的双层规划问题。基本 思想为首先利用k k t 条件对下层规划问题进行求解，将下层规划的最优解表示为 关于上层决策变量和l a 黟a n g e 乘子五的表达式，针对问题的特点设计了一个改进的 凸交叉算子，并应用遗传算法对这类双层规划进行求解，证明了算法的收敛性，最 后进行数值实验取得了良好的效果。 第四章主要研究了对上层规划的目标函数和约束没有凸性和可微性要求，下 层规划为关于下层决策变量为带有线性等式约束的正定二次规划的这一特殊结构 的双层规划。其基本思想为先应用k k t 条件对下层规划进行求解，将下层规划的 最优解表示为仅关于上层决策变量的表达式，然后将下该最优解代入上层规划， 使双层规划转化为仅关于上层决策变量的单层规划，从而降低了搜索的维数，最 后，设计一个新的交叉算子，应用新的遗传算法对这类双层规划进行快速求解， 最后证明算法的收敛性，并进行数值实验，验证了算法的有效性。 第二章遗传算法简介 第二章遗传算法简介 2 1 遗传算法概述 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种概率搜索 算法。它以达尔文自然进化论“物竞天择，适者生存”和孟德尔的生物遗传变异 理论为基础，借鉴生物界自然选择和自然遗传机制，以概率为基础，在解空间中 进行随机搜索，最终找到问题全局最优解。2 0 世纪6 0 年代，美国m i c h i g a n 大学的 h o l l a n d 教授提出了遗传算法，它起源于6 0 年代对生物系统所进行的计算机模拟的 研究。7 0 年代h o l l a n d 教授提出了遗传算法的基本定理一模式定理，从而奠定了遗传 算法的理论基础；同时d ej o n g 基于遗传算法的思想在计算机上进行了大量的纯数 值函数优化计算实验。在一系列研究工作的基础上，g o l d b e r g 进行归纳总结，形成 了遗传算法的基本框架，并出版专著搜索、优化和机器学习中的遗传算法( g e n e t i c a 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 m i n g ) 啪1 ，从此遗传算法受到了 人们的关注，并使它得到迅速的发展，逐渐发展成了计算智能的一个重要的方向， 并应用于科研和工程等众多领域。 2 2 遗传算法的基础理论研究概述 遗传算法是一种群体型操作，它以种群中的所有个体为操作对象。遗传算法 主要使用选择、交叉和变异三个基本遗传算子。遗传算法包括6 个基本因素：( 1 ) 参数的编码；( 2 ) 初始种群的设定；( 3 ) 适应度函数的设计；( 4 ) 遗传算子的设计； ( 5 ) 停止运行准则及结果的解码；( 6 ) 控制参数设定，包括群体规模，交叉概率、 变异概率，停止运行准则的参数等。 2 2 1 遗传编码 在使用遗传算法求解实际问题时，由于遗传算法不能直接处理解空问的数据 上，所以必须在实际问题的解空间与遗传算法的编码空间的点之间建立一个对应 关系，将实际问题中解的形式转换为遗传算法能够处理的解的表达形式，即进行 编码运算，把问题空间中的解转换成遗传空间中的染色体或个体，称作编码；与 其相逆的过程为译码运算。遗传算法的编码可以根据问题灵活设计，但编码对遗 传算法的搜索效果和效率产生非常重要的影响。对特定的问题确定合适的编码是 非常重要的，所以问题的编码一般应满足如下3 个原则： ( 1 ) 完备性( c o m p l e t e n e s s ) ：问题空间中的所有点都能成为编码后空间中的点。 1 2 求解两类特殊双藤规划问题的遗传算法 2 ) 健全性s o u n d 懿e s 站：编玛詹空间的点能对成原闯题空间的所有点。 ( 3 嚣冗余性爨蛰融e d 黼d a 辩势：编码矮空瓣的点与霖囊题空间瓣点一一对应。 d e j o n 甓提出了以下两条操作性较强的使用编褥原则： ( a ) 有意义积木块编妈规则：应使用能易于产生与所求阕越棚关的具有低阶、 短定义长度模式豹编码方案。 ( b ) 最小字符集编码规娜：应使用能使闻邀褥戮自然、简肇表示和描述的鼹有 最小字符集酶编码方案。 编码熬优劣程度对遗传算子设计的难易和润趱的求解效攀产生菲鬻重癸的影 响，所以在实际应用遗传算法求耨闯题时，登须瓣编码方法、交叉算子的设诗、 变异算子的设计、译码方法等统一考虑，来寻求种对问题的描述最为简荤、且 使遗传算法求解效率最寒的编码方案。 在实际巍耀孛，壶于的阑题麴不固或者瓣予圈闯题都有各种不弱的编码方 式，常用的编码方式有：二进制编码、实数编码、格雷编码、符号编码、序列编 码、树编码、自适应编码、多参数联编码、多参数交叉编码等。 2 。2 2 初始群体蘸垒藏 一定数量朐个体缀戏了种群，群体巾个体麴数謦称鸯种群艘模。盘于遗赞算法 的群体性操作的需要，所以在执行遗传操作之前，必须已经有个由若干的钢始 解缀藏的初始种群。由乎实际阕题的复杂性，往往并不具有关予阏题解空闻的先 验舞识，所毅穰难确定最撬辩酶数量及箕在蜀行解空闯中韵分蠢。霞就我翻一般 希望生成一定数尽的个体( 个体数强等于种群规模) ，使得这些个体所对应的解在 解空间均匀分靠。初始种群中的每个个体一般都是通过随机方法产生，也称为进 纯懿裙始代。耱群规模怒遗传算法的控翎参数之一，其选取对遗传算法酶效率霸 速度有影蛹。一般群体溉模在死十到凡嚣之闻取毽，根据润题的复杂程度不丽而 取值不同，闷题越难，维数越高，种群规模应越大，反之则小。 初贻群体的设定一般霹袋敢翔下方法： ( 1 ) 设法确定最优篇在整个舞题空阕酶分布范围，然螽在就范围蠹产生均匀分 布的初始种群。 ( 2 ) 先髓规生成定数目的个体，然后从中选出最好的个体加入种群中，不断 重簸这一过程，直剿达到耱群巍摸。男辨，对于带约束翡褥题，还需要考虑戮随 机初始纯酶点是否在可符区域中，如果不在麓趱韵可行域中，霹戬使熏与间题相 关的领域的知识对其修j 琶使其至少对戚所求问题的一个可行解。 2 。2 。3 适应发遗数； 种群中个体对环境的适应程度叫做适应度。为了执行适者生存的原则，遗传 算法必须对个体的适应性进行评价。因此，需要度量个体的适应度，度量个体适 第二章遗传算法简介 应度的函数称为适应度函数。遗传算法在搜索进化过程中一般不需要其他外部信 息，只根据个体适应度，就可以决定它在此环境下的生存能力。好的个体具有较 高的适应度函数值，具有较好的生存能力。差的个体一般适应度函数值较小，所 以生存能力相对弱。由于适应度是群体中个体生存机会选择的唯一确定性指标， 所以适应函数的形式直接决定着群体的进化行为。为了能够直接将适应度函数与 群体中的个体优劣度量相联系，在遗传算法中规定适应度为非负，并且在任何情 况下总是希望越大越好。一般而言，适应度函数是通过对目标函数的转化而形成 的。 ( 1 ) 评价个体适应度的一般过程是： ( a ) 对个体编码串进行解码处理后，可得到个体的表现型； ( b ) 由个体的表现型可计算出对应个体的目标函数值； ( c ) 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应 度； ( 2 ) 适应度函数的设计一般主要满足以下条件： ( a ) 函数性质：单值、连续、非负； ( b ) 合理性、一致性：要求适应度函数值能够反映出对应解的优劣程度； ( c ) 计算量小：要求适应函数设计应尽可能简单； ( d ) 通用性强：适应函数对某一类具体问题，应尽可能通用； 在实际应用中，根据问题的不同和特殊性，可以设计特殊的遗传算法，可以 不必完全遵守上述规则。 2 2 4 适应度尺度变换： 遗传算法中，在进化过程是以种群中各个个体的适应度为依据，各个个体被 遗传到下一代群体中的概率是由个体的适应度来确定的，通过一个迭代过程，不 断的寻求出适应度较大的个体，最终就可得到问题的最优解或近似最优解。在进 化的初期，为避免早熟收敛，应缩小个体间差异，从而限制其选择数量，从而， 维护了种群的多样性；在进化的最后阶段，为了加快收敛，应放大个体间的差异， 因此，在遗传算法运行的不同阶段还需要对个体的适应度进行适当地扩大或缩小， 这种对个体适应度所做的扩大或缩小的变换称为适应度尺度变换。适应函数的常 用尺度变换法有如下几种：线形尺度变换法、幂尺度变换法、指数尺度变换法。 ( 1 ) 线性变换： 线性尺度变换公式：，= 卵+ 6 式中，为原适应度；f 是经尺度变换的后的适应度；口，6 是系数。 ( 2 ) 乘幂尺度变换： 乘幂变换公式：，= f 1 4 求解两类特殊双层规划问题的遗传算法 即新的适应度是原有适应度的某个指定乘幂。幂指数七与所求解的问题有关，并 在算法的执行过程中霈不断对其进行修正菇1 能使尺度变换满足一定的伸缩要求。 ( 3 ) 指数尺度变换： 指数尺度换公式为：，= e x p ( 一，) ，式中系数决定了选择的强制性，越 小，原有适应度较高的个体与其德的新适应度相差较大，也即越增加了选择个体， 的强制性。 2 2 5 遗传算法的基本遗传算子跚啪1 ： 遗传算法是模拟生物进化过程的仿生算法，它主要有三个遗传算子分别是： 选择算子；交叉算子；变异算子； ( 1 ) 选择算子 选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下 一代群体的遗传运算。它是根据适瘴度函数值选择适应值高的个体以形成交配池 的过程。在被选种群中按照一定的选择概率进行操作，这个概率取决于种群中个 体的适应度及其分布。其主要作用是避免基因缺失，提高全局收敛性和计算效率。 爱前常用的选择方法主要有：赌轮选择、最饶保存策略选择、捧序选择、联 赛选择、精英选择、稳态选择、确定式采样选择、无放回随机选择、无放回余数 选择、期望值选择等方法。 ( 2 ) 交叉算子 遗传算法交叉算子是模仿自然界有性繁殖，两个同源染色体通过交配两重组， 形成新的染色体，从而产生出新的个体或物种。对两个父代个体进行基因操作， 其作用在于把原有优良基因遗传给下一代个体，并生成包含更复杂基因结构的新 个体。交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因， 从而形成两个新的个体。 目前，一般经常使用的交叉算子有：单点交叉、两点交叉、多点交叉、一致 交叉、算术交叉等形式。针对特定的问题，还可以设计其他类型的交叉算予，而 且对于不同的编码方式，交叉算子也不同。 交叉算子是遗传算法运行过程中的一个重要的操作，交叉算子的设计一般主 要考虑以下两个原则： ( a ) 必须保涯优良基因能够在下一代中有一定的遗传和继承的祝会； ( b ) 必须通过交叉操作有一定的生成优良基因的机会； 交叉方式的设计与问题编码紧密有关，必须结合编码位串的结构来设计高效 的交叉算子。在实际应用时，可根据问题的特殊性应灵活设计和应用交叉算子， 可以大大提高遗传算法求解的效率。 ( 3 ) 变异算予 第二章遗传算法简介 1 5 变异操作是模拟自然界生物进化中染色体上某位基因发生突变现象，从而改 变染色体的结构和物理性状。在遗传算法中，变异运算是指将个体染色体编码串 中的某些基因座上的基因值用基因座的其他等位基因来替换，从而形成一个新个 体。变异算子通过变异概率p 。随机对个体染色体中的基因进行突变来实现。遗传 算法中使用变异算子的作用主要为了改善遗传算法的局部搜索能力和维持群体的 多样性，抑制了出现早熟的现象。为了保证个体变异后不会与其父体产生太大差 异，变异概率p 。一般取值较小值，以保证种群发展得稳定性。交叉操作是产生新 个体的主要方法，它决定了遗传算法的全局搜索能力；而变异操作只是产生新个 体的辅助方法，它决定遗传算法的局部搜索能力，使用变异算子可以维持群体的 多样性，防止出现早熟现象和提高算法的局部搜索效率。 目前一般常用的变异算子有：基本位变异、均匀变异、边界变异、非均匀变 异、插入变异、对换变异、高斯变异等。 2 2 6 遗传算法的参数设定口们 在遗传算法的运行过程中，存在对其性能产生重大影响的一组参数。这组参 数在初始化阶段或群体进化过程中如果能有合理的选择和控制，就能使遗传算法 将能够发挥最佳作用，在随机搜索中迅速达到最优解。主要参数包括染色体长度 ，群体规模，交叉概率p r ，以及变异概率p 。在经典遗传算法和一些简单遗 传算法中，这些参数是不变的。然而，随着研究的深入和经验的积累，许多学者 发现如果这些参数能够随着遗传算法进程而变化，这种有自适应性能的遗传算法 具有更高的鲁棒性、全局最优性，但其缺点在于将增加算法复杂性和计算量等。 还有一些参数的改进方法，比如，模糊控制参数法、基于均匀设计的参