基于正交设计的动态多目标优化算法研究-硕士论文

学校代号： 学号： 密级： 1 0 5 3 2 S 1 l1 0 W 1 3 6 普通 湖南大学工程硕士学位论文 基于正交设计的动态多目标优化算法 研究 T h eR e s e a r c ho nO r t h o g o n a lD e s i g n - b a s e dD y n a m i c M u l t i O b je c t i v e O p t i m i z a t i o nA l g o r i t h m b y C H E NH e n g y o n g B E ( C h e n g d uU n i v e r s i t yo fI n f o r m a t i o nT e c h n o l o g y ) 2 0 1 1 At h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e R e q u i r e m e n t sf o rt h ed e g r e eo f M a s t e ro fE n g i n e e r i n g C o m p u t e rT e c h n o l o g y i nt h e G r a d u a t eS c h o o l o f H u n a nU n i v e r s i t y S u p e r v i s o r P r o f e s s o rL IZ h i y o n g S e n i o rE n g i n e e rL I UH o n g l i M a y ，2 0 1 4 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 神勋 日期：卯伴年否月r 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 日期：卯f 够年乡月r 日 日期： 伊f1 年6 月r 日 基于正交设计的动态多目标优化算法研究 摘要 在人们的日常生活之中，总会遇到一些需要做决策的问题，这些问题可能是 静态优化问题，也可能是动态优化问题。人们对于静态优化问题的研究已经有了 很多的成果，但对于动态优化问题的研究还不够深入，成熟的求解动态优化问题 的算法还比较少，而动态优化问题又是现实生活中普遍存在的基础性问题，解决 该类问题，能够加快该领域研究的发展，所以，近年来吸引了不少学者对这类问 题进行分析和求解。由于动态优化问题中，存在着多个与时间或环境相关的目标 向量和决策向量，其最优解集也会随时间或环境的变化而变化，因此很难设计出 一种针对所有问题的通用的方法。本文提出了一种基于正交设计的动态多目标优 化算法( O D M O A ) ，利用历史信息对新环境下的P a r e t o 最优解集进行快速、有效 的预测，并建立一个新的预测种群，以解决连续动态多目标优化问题。本文在最 后进行了多组对比试验，并获得了一些试验结果，证明了算法的有效性。 论文的主要工作包括： ( 1 ) 动态优化问题及算法综述。主要对动态优化问题的研究背景及意义进 行了简要的说明，并描述了优化问题的相关定义，其中包括对优化算法的研究综 述，阐述了一般的动态多目标优化算法的框架。 ( 2 ) 提出了基于正交设计的动态多目标优化算法。本文提出的优化算法包 含了五个模块：正交多目标优化算法模块，记忆集模块，预测模块，自回归模块 和环境检测模块。正交多目标优化算法模块在环境没有发生变化的时候用来对种 群进行进化操作；记忆集模块保存了历史最优解，在环境发生变化以后，就可以 利用记忆集中的非支配解来预测新的种群；预测模块负责管理整个算法的运作； 自回归模块是本文的预测算子，该算子利用历史的P a r e t o 解集来预测新的P a r e t o 解集的位置；环境检测模块用来检测环境什么时候发生了变化。 ( 3 ) 实验分析。本文提出的基于正交设计的动态多目标优化算法，在与 F P S ，D N S G A I I A 和R I S 进行多组对比实验之后，仿真结果表明，基于正交设计 的动态多目标优化算法在整体性能上要优于其他三种算法，解的收敛性更好。 关键词：动态多目标优化算法；P a r e t o 最优解集；正交设计；环境检测； I I 硕士学位论文 A b s t r a c t I no u rd a i l yl i f e ，t h e r ea r em a n yd e c i s i o n m a k i n gp r o b l e m s S o m eo ft h e p r o b l e m s a r es t a t i c o p t i m i z a t i o np r o b l e m s ( S O P s ) ；t h eo t h e r s a r e d y n a m i c o p t i m i z a t i o np r o b l e m s ( D O P s ) N o w a d a y s ，r e s e a r c h e r sh a v eg o tal o to fa c h i e v e m e n t s o nS O P s ，b u tt h e r ea r es t i l ls e l d o mc l a s s i c a ld y n a m i cm u l t i - o b j e c t i v eo p t i m i z a t i o n a l g o r i t h m s I na d d i t i o n ，D O P sa r eo n eo ft h eb a s i ci s s u e sc o m m o n l yi nr e a ll i f e I t w o u l ds p e e du pt h ed e v e l o p m e n to ft h i sr e s e a r c hf i e l di ft h e s ep r o b l e m sc a nb es o l v e d I nr e c e n ty e a r s ，r e s e a r c h e r sd e v o t et h e m s e l v e st oa n a l y z i n ga n ds o l v i n gt h i sk i n do f p r o b l e m s T h eo b j e c t i v e s v e c t o r sa n d o rd e c i s i o nv e c t o r so fD O P sa r e u s u a l l y c o r r e l a t i o nw i t ht h ee n v i r o n m e n to rt h et i m e H e n c e ，t h eP a r e t oo p t i m a ls o l u t i o ns e t w i l lb ec h a n g e do v e rt i m e I ti sd i f f i c u l tf o rr e s e a r c h e r st od e s i g na na l g o r i t h mw h i c h c a nb eu s e dt os o l v ea l lt h i sk i n do fp r o b l e m s T h i sp a p e rp r e s e n t sa nO r t h o g o n a l D e s i g n b a s e dD y n a m i cM u l t i - 0 b je c t i v eO p t i m i z a t i o nA l g o r i t h m T h i sa l g o r i t h m m a k e su s eo ft h eh i s t o r i c a lo p t i m a ls o l u t i o n ，a n dt h e np r e d i c t san e wp o p u l a t i o nb y c o n s i d e r i n gt h ep r o p e r t i e so fc o n t i n u o u sD O P sw h e na ne n v i r o n m e n t a lc h a n g ei s d e t e c t e d A tt h ee n do ft h ep a p e r ，s o m ec o n t r a s te x p e r i m e n t sa r ec a r r i e do u ta n dt h e r e s u l t sp r o v e st 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 T h em a i n w o r ko ft h ep a p e ri sa sf o l l o w s ： ( 1 ) As u r v e yo nD O P sa n d D O A s B r i e fi n t r o d u c t i o n sa r em a d eo nt h eb a c k g r o u n d a n ds i g n i f i c a n c eo ft h eD O P s A n dt h ed e t a i l e dd e f i n i t i o n so ft h eS O P sa n dD O P sa r e d e s c r i b e d T h er e l a t e do p t i m i z a t i o na l g o r i t h m sa r er e v i e w e d ( 2 ) O r t h o g o n a ld e s i g n b a s e dD M O A T h e r ea r ef i v em o d u l e si no u ra l g o r i t h m A n dt h ef u n c t i o no ft h e s em o d u l e si ss h o w na sf o l l o w s ：t h eo r t h o g o n a ld e s i g n - b a s e d m u l t i o b je c t i v eo p t i m i z a t i o na l g o r i t h mm o d u l ei su s e dt oe v o l v et h ep o p u l a t i o nw h e n t h ee n v i r o n m e n ti sn o t c h a n g e d T h em e m o r ym o d u l ei su s e dt o s t o r eu s e f u l i n f o r m a t i o nf r o mt h ep a s tt h a tw i l lb eu s e di nf u t u r e A n t i c i p a t i o nm o d u l ei su s e dt o m a n a g et h ei n f o r m a t i o np r o v i d e db yt h et w op r e d i c t o r sa n dd e c i d e sw h e nt ou s ei t A u t o r e g r e s s i o nm o d u l ei su s e dt op r e d i c tan e wp o p u l a t i o na n dt h ee n v i r o n m e n t d e t e c t i o nm o d u l ei su s e dt of i n dw h e nt h ee n v i r o n m e n tc h a n g s ( 3 ) E x p e r i m e n t a la n a l y s i s T h i sp a p e rp r o p o s e s a no r t h o g o n a l d e s i g n b a s e d d y n a m i cm u l t i o b j e c t i v eo p t i m i z a t i o na l g o r i t h m ( O D M O A ) C o m p a r e d t h e o p t i m i z a t i o nr e s u l t so f0 D M O Aw i t ht h er e s u l t so ft h ef e e d f o r w a r dp r e d i c t i o n I I I S t r a t e g y ( F P S ) ，D N S G A I I Aa n dR I S ，t h ep e r f o r m a n c eo fO D M O Ai sm u c hb e t t e r t h a nt h eo t h e rt h r e ea l g o r i t h m s W h a t Sm o r e ，t h ec o n v e r g e n c eo ft h es o l u t i o n si s b e t t e r K e yw o r d ：D y n a m i cM u l t i O b j e c t i v e O p t i m i z a t i o nA l g o r i t h m ；P a r e t oO p t i m a l S o l u t i o nS e t ；O r t h o g o n a lD e s i g n ；E n v i r o n m e n tD e t e c t i o n ； I V 硕：i 二学位论文 目录 学位论文原创性声明和学位论文版权使用授权书I 摘要I I A b s t r a c t I I I 插图索引V I I 第1 章绪论1 1 1 研究背景与意义1 1 2 国内外研究现状2 1 3 本文主要研究内容5 1 4 本文组织结构6 第2 章 动态优化问题及相关理论一7 2 1 静态优化问题8 2 1 1 静态单目标优化问题8 2 1 2 静态多目标优化问题9 2 2 动态优化问题1 9 2 2 1 动态单目标优化问题2 0 2 2 2 动态多目标优化问题2 2 2 3 小结2 5 第3 章基于正交设计的动态多目标优化算法2 6 3 10 D M O A 设计思路与描述一2 6 3 2O D M O A 基本原理一2 9 3 2 1 正交多目标优化算法3 0 3 2 2 预测机制的相关理论3 5 3 3O D M O A 算法流程一3 7 3 4 小结3 8 第4 章算法仿真实验及分析3 9 4 1 实验环境3 9 4 2 测试函数3 9 4 3 对比算法4 3 4 4 实验结果及分析4 3 4 4 1 评价指标4 3 4 4 2 实验参数4 4 V 4 4 3 实验结果及分析4 5 4 5 小结5 0 结 论51 参考文献5 3 附录A ( 攻读学位期间所发表的学术论文目录) 5 8 附录B ( 攻读学位期间所参与的项目目录) 5 9 致j 射6 0 V I 硕士学位论文 插图索引 2 1 最小化问题的P a r e t o 最优解和最优前沿1 0 2 2 蚁群算法流程图15 2 3 粒子群算法流程图1 7 2 4 粒子群优化算法的伪代码1 8 2 5 动态多目标优化算法的流程图2 4 3 1 动态多目标进化算法的伪代码2 6 3 2 双目标优化问题在2 维决策空间下的P S s 移动轨迹2 8 3 3 基于正交设计的动态多目标优化算法体系结构2 9 3 4 构建正交数组k ( Q P ) 的算法31 3 5 平均值的计算算法3 2 3 6 最好组合的计算算法( 对于最小化问题) 3 2 3 7 维决策变量的子空间日3 3 4 1F D A l 的P S 和P F 的直观图4 0 4 2F D A 2 的P S 和P F 的直观图4 l 4 3F D A 3 的P S 和P F 的直观图4 2 4 4 四种算法在函数F D A l 上的效果4 5 4 5O D M O A 在不同t 下优化F D A l 函数的收敛效果图4 7 4 6 四种算法在函数F D A 2 上的效果4 7 4 7O D M O A 在不同t 下优化F D A 2 函数的收敛效果图4 8 4 8 四种算法在函数F D A 3 上的效果4 9 4 9O D M O A 在不同t 下优化F D A 3 函数的收敛效果图5 0 V I I 图图图图图图图图图图图图图图图图图图图图图 硕士学位论文 1 1 研究背景与意义 第1 章绪论 优化理论由来已久，最早可追溯到古希腊时期。当时德莫克利提出了穷竭法， 而我国庄子的天下篇中也有“一尺之锤，日取其半，万世不竭 的极限思想， 公元2 6 3 年，刘徽为九章算术作注时提出了“割圆术 ，用正多边形来逼近圆 周，这是极限论思想的成功运用。求极限的思想就是早期解决函数优化问题的一 般思想。1 9 7 5 年，美国M i c h i g a n 大学的J o h nH o l l a n d 与其同事、学生们从自然 系统中复杂适应过程入手，模拟生物进化机制来构造人工系统模型，并提出了一 个较为完整的理论和方法一一遗传算法( G e n e t i cA l g o r i t h m s ，G A ) 。遗传算法是一 种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。 正是遗传算法的提出，为人工智能的发展奠定了基石。随后，智能优化算法的发 展进入了一个百花齐放的时代。1 9 7 7 年F r e dG l o v e r t l J 提出了禁忌搜索算法( T a b u S e a r c h ) ，1 9 7 8 年J e r n e 提出了免疫网络学说为免疫算法提供了理论基础，1 9 8 3 年 K i r k p a t r i c k t 2 J 提出了模拟退火算法( S i m u l a t e dA n n e a l i n g ) ，1 9 9 2 年D o r i g o t 3 】在他的 博士论文中提出了蚁群算法( A n tC o l o n yO p t i m i z a t i o n ，A C O ) ，1 9 9 5 年K e n n e d y 4 】 提出了粒子群优化算法( P a r t i c l eS w a r mO p t i m i z a t i o n ，P S O ) ，1 9 9 9 年L i n h a r e s t 5 J 提 出了捕食搜索( P r e d a t o r yS e a r c h ) ，2 0 0 2 年H a n 等1 6 J 提出了量子衍生进化算法 ( Q u a n t u m i n s p i r e de v o l u t i o n a r ya l g o r i t h m ，Q E A ) 等等。这些智能优化算法在解决传 统的静态优化问题上引起了广泛的关注，并取得了一些成绩。 然而，在这个信息爆炸的社会，无处不存在着一些时变的复杂问题需要解决， 将现实问题中这些优化目标与时间因素相关的问题抽象成对应的数学模型，这个 模型就是动态优化问题。D O P s 根据目标的多少通常可以分为动态单目标优化问 题( D y n a m i cS 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 s ，D S O P s ) 与动态多目标优化 问题( D y n a m i cM 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 ，D M O P s ) 。目前国际上对于 D O P s 的研究尚处于起步阶段，可参考的理论与研究成果并不多。并且对于D O P s 的研究也主要集中于D S O P s ，对D M O P s 的研究成果还比较少。典型的动态多目 标优化问题例如网络通信领域，研究如何在通信网络不断变化的环境中综合考虑 带宽、噪声、节能等目标的情况下实现有效的平衡，这就是一个D M O P s ；交通管 理领域，研究如何在综合考虑道路状况、车辆多少、紧急情况等各种交通变化的 情况下，提高道路的通信量并实现社会效益的最大化，这也是一个典型的D M O P s ； 节能环保领域，研究如何综合考虑能源的消耗量、污染物排放量和产能的最大化， 基于正交设计的动态多目标优化算法研究 这也是一个D M O P s ，相关的生产科研类的动态多目标优化问题更是不胜枚举。研 究面向动态多目标优化的计算策略与算法，具有非常重要的科研与工程价值。 动态优化问题是一类极其重要且应用广泛的问题，它同时也是一类非常有挑 战性的问题。在解决这类优化问题上，通常不仅要求算法能发现其最优解，而且 还要尽可能紧密地跟踪最优解在搜索空间内的运行轨迹。也就是说，算法能够持 续适应动态环境下问题的解的变化。 传统的针对D O M P s 的算法，往往是直接将已有的静态优化算法进行某些改 进，然后推广到D O M P s 的求解。这些算法一般采用提高种群搜索的随机性，降 低算法的收敛速度为代价。难以取得很好的结果。目前，研究者们已经设计出了 一些有效的动态多目标优化算法。然而，这些算法大多还是集中在如何得到尽可 能满足问题条件的最优解或近似最优解，对算法的有效性、收敛性、及解的质量 等考虑的较少。因此，针对D M O P s 的特点，设计一个新的针对问题特性的动态 多目标优化算法显得尤为重要。 1 2 国内外研究现状 在现实社会中，不管是科学研究领域，还是工程应用领域，都存在着大量的 随时间变化的多目标优化问题。这类问题通常被叫做动态多目标优化问题。近期 的研究表明，在各个领域里，对于动态多目标优化问题的研究都有着快速的增长， 例如：工程应用领域包括调度问题7 1 、管理问题8 1 、规划问题9 1 、设计问题【1 0 1 和 控制问题1 1 1 1 。另一方面，在科学研究领域，一些问题包括机器学习【1 2 】、双层优化 【1 3 1 和约束优化1 4 1 等，都能依据动态多目标优化问题来处理。动态多目标优化算法 的目标就是跟踪最优值的运动轨迹，所以，算法需要对环境进行精确地检测，并 且能准确地检测到环境的变化。环境的变化可以是规律的或无序的、连续的或者 离散的、剧烈的或者轻微的。R u s s e l lC E b e r h a r t 和Y u h u iS h i t l 5J 提出了动态环境 的四种类型： ( 1 ) 在问题域内，最优值的位置发生变化； ( 2 ) 最优值的位置不发生变化，但是最优值发生变化； ( 3 ) 最优值和最优值的位置都发生变化； ( 4 ) 在一个多维系统内，最优值和最优值位置可能发生单独的或者同时的 变化，也可能在单维空间或者多维空间中发生变化。 从上世纪九十年代开始，广大学者便开始关注和研究进化算法，并且已经成 为了智能优化算法领域的研究热点之一。但是，绝大多数关于进化算法的研究还 仅仅围绕在静态多目标优化问题上。经典的进化算法包括N S G A 、N S G AI I 、S P E A 、 S P E AI I 等，研究者们或直接或间接的在它们的基础上进行改进，对科研及工程 类问题进行了有效的求解，并取得了一些成果。与静态优化问题相比，动态优化 2 硕士学位论文 问题的研究难度更大，特别是动态多目标优化问题，就更加复杂。现在还缺乏比 较经典的、鲁棒的动态多目标优化算法，近年来该领域的研究热度也在不断攀升， 动态多目标优化是当前多目标进化优化研究领域的重点与难点之一。 目前，国际上针对动态多目标优化问题的研究，涌现出了一批突出的团队。 譬如，由I E E EC o m p u t a t i o n a lI n t e l l i g e n c eS o c i e t y 的演化计算委员会组成了一个研 究小组，团队的主席是来自英国伯明翰大学计算智能与应用卓越研究中心的X i n Y a o 博士，其核心人员一共有8 名，来自多个国家和地区。该团队以不确定环境 下的动态问题的演化计算( E C i D U E ) 为主要研究内容。另外一个团队由英国莱斯特 大学、伯明翰大学以及本田欧洲研发公司( H o n d aR & DE u r o p e ，德国) 组成，该 组织主要分析设计动态环境下的优化方法和理论。还有许多高级别的国际会议如 G E C C 0 2 0 13 ，W C C l 2 0 1 4 和C E C 2 0 l3 等都有在动态优化( 动态环境) 方面的论 文发表，特别是2 0 l3 年在墨西哥召开的C E C 2 0 13 会议上，动态优化问题是一个 焦点性的问题，学者们提出了多个解决办法。R o h a 和S h a n t a n a 1 6 J 等人提出了一个 基于位置交叉的自适应差分进化动态优化算法，该算法通过采用一个基于位置的 策略，改进了传统差分进化算法中的变异算子，并且运用混合局部最优交叉策略 来加强种群的多样性，在环境变化的时候，采用历史信息来对环境变化进行预测。 M i c h a e lG 和X i a o d o n gL i t l 7J 等人针对多峰问题设计了一个动态小生境差分进化算 法，该算法混合了两个机制：一个是自适应的参数控制技术，另一个是外部动态 归档集与重新初始化机制。该算法体现出了良好的鲁棒性和稳定性，在解决多峰 问题方面体现出了比较好的结果。K a m i l 和J a v i e r 1 8 J 等人提出了一个解决动态P 2 P 网络的基于传播的蚁群优化资源探索框架。通过建立一个通用的知识传播机制， 延展了传统蚁群算法在解决动态P 2 P 网络上的优化能力。S h u Y uK u o ，C h u nK u o 和Y a o H s i nC h o u 1 9 J 将基于量子衍生的禁忌搜索算法成功运用到了动态期货交易 系统中，是动态优化算法解决金融问题的一个实例。期货交易就是对什么时候买 入，什么时候售出的一个决策问题，最大化收益和最小化风险就是解决这类问题 的目标。首先，提出的量子衍生禁忌搜索算法用来找到最优的交易规则，然后使 用滑动窗来规避主要的过度学习问题。 国内目前研究动态优化问题的学者不是很多，西安电子科技大学的焦李成【2 0 】 教授及其团队提出了基于量子协同免疫的动态优化算法。该算法采用量子比特编 码的方式，增强了算法的稳定性和收敛性，同时协同策略也增强了子群体之间的 信息交流，提高了种群多样性。太原理工大学的曾建潮【2 1 】教授及其团队提出了一 个适用于动态环境的改进R S S I 定位方法，在原R S S I 的基础上加入了动态路径衰 落指数获取策略，利用它来对距离进行估算，提高了算法对动态环境的适应性。 胡静和曾建潮【2 2 J 还针对动态环境检测的不足，提出了一个动态环境下一种改进的 微粒群算法，该算法利用环境变化前后全局最好解的距离和种群多样性作为响应 基于正交设计的动态多目标优化算法研究 变化环境的依据，并与改进的响应方法结合，为环境变化的检测工作作出了一定 贡献。宝鸡文理学院数学院的刘淳安教授及其团队在动态优化问题及动态优化算 法方面做出了很多的工作，2 0 11 年，刘淳安拉3 j 教授提出了一种针对动态非线性约 束优化问题的改进算法。首先从问题约束条件出发构造了一个新的动态熵函数， 然后改进了进化算法中的杂交算子和带局部搜索的变异算子。该算法为解决动态 非线性优化问题提供了新的解决办法。2 0 12 年 2 4 1 提出了一类带约束的动态多目标 优化问题的进化算法。该算法在解决环境变量取值于正整数集的动态优化问题方 面具有比较好的效果。北京邮电大学的方滨兴【25 J 教授与其团队在2 0 13 年提出了 一个针对云计算环境下的数据容灾策略，运用动态多目标微粒群算法成功使数据 容灾成本降低，并缩短了灾难出现后的恢复时间。还有已故的康立山教授及其团 队在动态T S P 问题的研究中做出了较大的贡献，2 0 0 8 年，杨鸣，康立山和吴燕来 口6 j 提出了动态多目标T S P 中动态程度和目标冲突程度的度量方法，对动态多目标 T S P 的算法设计具有重要的指导意义。 早期学者们解决动态多目标优化问题所采取的方法，大多是基于传统静态优 化算法，忽略问题的动态特性，将每一次环境变化看成是一个新的优化问题，然 后重新优化，这显然是不切实际的。1 9 6 6 年，F o g e l 27 J 等第一次将进化算法应用 到动态优化，一直过了2 0 年，G o l d b e r g 和S m i t h 2 8 J 于1 9 8 9 年发表了采用非支配 排序方法和小生境技术求解多目标优化问题，在这之后，进化算法才真正广泛地 应用来解决这类问题。随着研究者们对动态问题研究的深入，一些其它的静态问 题优化方法也应用来解决动态优化问题。2 0 0 0 年以来，B r a n k eJ ，K a u b e rT ，S c h m I D T HC 【2 9 J 等提出用多种群的方法来解决动态多目标优化问题。2 0 0 1 年，G u n t s c h 3 0 】 等人将蚁群算法应用来求解动态优化问题。2 0 0 6 年，M e y e r 3 l J 等将随机扩散搜索 应用到解决动态优化问题。D e b 等【3 2 】在N S G A I I 的基础上进行改进，提出了动态 N S G A I I 。该算法采用非支配解排序，以及拥挤距离进行个体评价，通过S B S 交 叉、联赛选择、最优保留和P o l y n o m i a l 变异等操作进行群体进化。2 0 0 9 年，P e l t a p 3 J 等人将粒子群协同优化策略应用来解决动态多目标优化问题。T r o j a n o w s k i 和 W i e r z c h o n 【3 4 J 将基于免疫的优化算法用来解决动态优化问题等等。国内的一些学 者如尚荣华和焦李成【3 5 】等改进了现有的克隆策略，采用整体克隆的方式，提出了 动态多目标免疫克隆优化算法。刘宝碇教授【36 J 对不确定环境下的优化理论做出了 重要的研究工作。刘敏和曾文华【3 7 】提出了一种记忆增强的动态多目标分解进化算 法。将动态多目标问题分解成若干个动态单目标优化问题进行求解。刘淳安教授 【38 】针对时间变量取值于正有理数集，自变量的维数随时间可发生变化的一类动态 多目标优化问题提出了一种改进的粒子群算法。该算法通过引入新的变异算子和 自适应动态变化惯性因子，以及一种判断环境变化的有效规则，极大地增强了粒 子群算法跟踪问题环境变化的能力。王宇平1 39 J 等提出了新的解决动态多目标优化 4 硕士学位论文 问题的进化算法以及动态多目标优化算法的收敛性分析。Z h a n gZ h u h o n g 4 0 提出 了一种动态环境下的多目标免疫算法，并把其成功应用于温室控制。Z h o uA i m i n 【4 l J 等提出了一种基于种群重启的动态多目标优化算法，该算法引进了两个预测策略， 一个是利用历史信息的种群重启策略，一个是加入白噪声的随机扰动种群重启策 略。胡成玉【4 2 】等提出了一个基于多粒子群协同的动态多目标优化算法，采用多种 群竞争与协作两种模式，加快了求解问题的速度。当竞争失效后，可以自适应切 换到协作模式来进行搜索。 1 3 本文主要研究内容 本论文来源于国家自然科学基金项目：面向动态多目标优化的量子M e m e t i c 计算策略与算法研究中，对于动态环境下的多目标优化算法的研究。 本文针对传统动态多目标优化算法在解决动态问题上收敛性差、计算复杂度 高的问题，提出了一个基于正交设计的动态多目标优化算法。通过研究正交多目 标优化算法、预测策略和环境检测中的若干关键技术，并按照“分析问题一一设 计算法一一实验设计一一问题求解”四个步骤，提出了一个有效地解决动态多目 标优化问题的方法。主要研究内容如下： ( 1 ) 传统动态优化问题及算法研究。从静态优化问题及其解决方法入手， 再到传统动态优化问题及其算法的研究做了系统地梳理。在解决动态优化问题的 时候，传统的动态优化算法取得了一些成果，但是在保持种群多样性、提高算法 收敛性和减少算法计算复杂度方面的能力还比较差，有些算法甚至难以检测到环 境变化，丢失了算法的准确性。本文针对以上问题，将设计一个有效地针对连续 动态多目标优化问题的解决办法。 ( 2 ) 提出了基于正交设计的动态多目标优化算法。针对连续动态多目标优 化问题的特点，以及传统动态优化算法上的缺陷，本文提出了一个提出了基于正 交设计的动态多目标优化算法。该算法包含了五个模块：正交多目标优化算法模 块，记忆集模块，预测模块，自回归模块和环境检测模块。正交多目标优化算法 模块吸取了N S G A I I 和S P E A I I 的优点，提高传统正交算法的多样性和收敛性。 当环境检测模块检测到环境发生变化后，带记忆集的预测策略通过学习历史最优 点，只用预测一个新的点，就能对下一个P S 做出预测，降低了算法的计算复杂 度。 ( 3 ) 实验结果与分析。本文提出算法在与F P S ，D N S G A I I A 和R I S 进行 多组对比实验之后，仿真结果表明，基于正交设计的动态多目标优化算法在整体 性能上要优于其他三种算法，解的收敛性更好。 基于正交设计的动态多目标优化算法研究 1 4 本文组织结构 本文的主要组成结构如下： 第1 章：绪论。这一章首先介绍了动态多目标优化问题的研究背景及意义， 然后概述了动态多目标优化问题的研究现状，并介绍了本文的主要内容和工作安 排。 第2 章：动态优化问题及相关理论。这一章总结了优化问题及优化算法的相 关理论。首先从常规的静态优化问题入手，分析了静态单目标优化问题和静态多 目标优化问题，详细介绍了问题的定义及相关算法的研究。接下来，介绍了动态 优化问题，从动态单目标优化问题的定义和相关算法研究延伸到动态多目标优化 问题的定义到相关算法的理论研究。 第3 章：基于正交设计的动态多目标优化算法。本章首先介绍动态多目标优 化算法的一般框架，然后引入本文的算法设计思路。基于正交设计的动态多目标 优化算法包括五个模块，分别为正交多目标优化算法模块、记忆集模块、预测管 理模块、自回归模块和环境检测模块。正交多目标优化算法模块和预测模块是本 文的研究重点和难点，本章详细介绍了这五个模块的设计思路。 第4 章：基于正交设计的动态多目标优化算法的实验分析。本章针对本文提 出的基于正交设计的动态多目标优化算法进行了仿真实验，搭建了实验的仿真平 台，并对三种不同的测试函数进行了优化，并将优化结果与F P S 、D N S G A I I A 和R I S 算法的优化结果进行了对比及分析，讨论了本文提出的动态多目标优化算 法的优化性能是否有理想的优化效果。 最后，对本文所做的主要工作进行了总结，并针对文中提出的基于正交设计 的动态多目标优化算法，提出了下一步的研究方向和展望。 6 硕士学位论文 第2 章动态优化问题及相关理论 多目标优化问题( M 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 ，M O P s ) ，又叫多准则 优化问题( M u l t i c r i t e r i aO p t i m i z a t i o nP r o b l e m s ) ，它广泛存在于人们的生产生活中。 平常人们接触最多的，例如出行安排，从城市的A 地到B 地，如果走环线或高速， 可以更快的到达，但是一般环线或高速道路要绕行数十公里，所以要付出更多的 油费，如果走城市内道路，可以少走很多路，但是一般城市内的道路拥堵状况严 重，特别是早晚高峰期。这时往往就需要做一个决策：如何少耗油，更快到达。 这个案例就是一个典型的多目标优化问题。其它的还有通信网络优化、金融投资 优化、云计算资源调度优化、生产车间任务调度优化等等。多目标优化问题的各 个目标在大多数情况下是相互冲突的，一个目标的改善，往往会使另外一个目标 性能降低。如果要使得多个目标都能同时达到最优化的结果，也就是单目标意义 上的最优解，基本是不现实的。多目标优化问题的最优解通常是在多个目标之间 进行折中处理，它所获得的解，一般是一组最优解集( 非支配解集) 即P a r e t o 最 优解集。一般一个多目标优化问题，具有多个P a r e t o 最优解。在实际应用中，必 须根据问题的实际情况，以及决策者的偏好，从P a r e t o 最优解集合中选择一个或 者多个解做为问题的最优解。 优化问题通常可以分为以下5 类： ( 1 ) 有无约束优化问题。没有约束条件限制的最优化问题称为无约束优化 问题，有约束条件的称为约束优化问题，约束条件又可分为等式约束条件和不等 式约束条件； ( 2 ) 随时间变化与否的优化问题。如果问题的最优解不随时间变化，这种 优化问题称为静态优化问题。如果问题的最优解随时间动态变化，那么就称它为 动态优化问题； ( 3 ) 单目标和多目标优化问题。当问题中的目标函数只有一个时，这种优 化问题就称为单目标优化问题。当问题中的目标函数多于一个，则称为多目标优 化问题。 ( 4 ) 线性与非线性的优化问题。如果目标函数和所有约束条件中的函数都 是决策变量的线性函数，这种优化问题就称为线性优化问题( L i n e a rO p t i m i z a t i o n P r o b l e m s ) 。如果目标函数或约束条件中至少有一个是决策变量的非线性函数，这 种优化问题就称为非线性优化问题( N o n l i n e a rO p t i m i z a t i o nP r o b l e m l 。 ( 5 ) 确定性和随机性优化问题。如果每个决策变量取值都是确定的，那么 这种优化问题就叫做确定性优化问题( D e t e r m i n i s t i cO p t i m i z a t i o nP r o b l e m ) ；如果某 基于正交设计的动态多目标优化算法研究 些决策变