光网络组播路由多目标进化算法研究
发布时间：2020-10-20 09:03
【摘要】：在科学研究和工程领域中许多问题都是由多个相互冲突的目标组成,一般称这一类问题为多目标优化问题。基于种群的进化算法在单次运行中能得到一个近似的Pareto解集,因此多目标进化算法已经成为一种较为普遍且有效的求解多目标优化问题的方法。带精英策略的非支配排序算法NSGA-Ⅱ(Elitist Non-dominated Sorting Genetic Algorithm)是2002年Deb等人对算法NSGA的改进,引入了快速非支配排序算法、精英策略以及拥挤度和拥挤度比较算子,是迄今为止最优秀的进化多目标优化算法之一。本文以稳态NSGA-Ⅱ算法为框架,在非支配层的更新策略方面、自适应算子选择策略(Adaptive Operator Selection,AOS)的信用分配策略以及算子选择策略等方面对稳态NSGA-Ⅱ算法进行了改进,提出基于自适应选择策略的稳态NSGA-Ⅱ算法AOS_SSNSGA-Ⅱ。同时针对光网络的特性,基于稳态NSGA-Ⅱ框架提出了 MRWA_AOSNSGA-Ⅱ-SD算法用于求解光网络组播路由波长分配问题。本文的主要工作如下:(1)针对稳态NSGA-Ⅱ算法的改进,提出了一种基于自适应算子选择策略的稳态NSGA-Ⅱ算法AOS_SSNSGA-Ⅱ。该算法采用稳态NSGA-Ⅱ作为框架,使种群能够在产生全部子种群之前被立即更新,从而精英信息能够被及时的利用,克服了传统NSGA-Ⅱ算法收敛速度慢的缺点。与此同时,为了减少稳态NSGA-Ⅱ算法维护非支配层结构的开销,提出了一种改进型非支配层更新策略,通过从当前非支配层结构中提取的有效信息,仅在算法开始时进行一次非支配排序,此后只需要对有限数量的非支配层结构进行更新,从而避免了大量不必要的比较操作。为提高算法对问题公式的鲁棒性,克服由参数调整带来的成本高、耗时长等问题,本文在稳态NSGA-Ⅱ算法中加入自适应算子选择策略。对于信用分配方式,提出基于适应率排序的信用分配策略,使用一个滑动窗口来记录算子最近几次迭代的适应度增长率,从而动态跟踪搜索过程,同时引用衰退机制来增加最佳算子的选择概率;对于算子选择策略,由于算子的性能可能会随着种群的演化而出现很小或较大的波动,而算子所收到的信用值的动态分布会极大地影响算子选择器的效率,因此提出基于多臂赌博机的算子选择策略。与经典进化多目标算法NSGA-Ⅱ、MOEA/D-DRA与R2-IBEA以及经典的多目标信用分配策略OP-Do、SI-Do、CS-Do以及算子选择方式PM和AP相结合的方式相比,本文提出的算法AOS-SSNSGA-Ⅱ在ZDT和DTLZ系列标准的测试函数上有更好的收敛性和多样性。(2)针对WDM网络组播路由波长分配问题中存在多个相互冲突的QoS性能指标,本文提出光网络组播路由的多目标优化数学模型MOMRWA,优化的目标包括组播网络资源使用代价、端到端延迟、信道利用率,同时满足端到端时延、可用带宽、丢包率等QoS约束。为解决提出的MOMRWA问题,本文提出自适应算子选择策略与序贯分解机制相结合的稳态NSGA-Ⅱ算法MRWA_AOSNSGA-Ⅱ-SD。对于组播波长分配子问题,本文采用动态波长分配算法中 的波长随机分配法,对于组播路由子问题,本文提出备用选路策略;针对算法搜索过程中由于环路形成的不可行光树,提出了一种基于MPH算法的光树修复机制。实验结果表明提出的MRWA_AOSNSGA-Ⅱ-SD算法与其他算法相比在减少计算开销的情况下能够获得更优的Pareto解集,从而达到在减少组播路由时延与网络资源使用费用的情况下提高信道的利用率。
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18
【图文】：
ＮＳＧＡ－ＩＩ，差分进化的选择，而ＡＯＳ是算子的选择，除此以外在其他方面类??似。??有ＡＯＳ策略的多目标进化算法的一般流程如图１．１所示。在第ｔ次迭代中，??ＡＯＳ选择一个算子来生成后代解，对后代进行评估，并将其插入种群中，并根据??基本多目标进化算法进行更新。如果算子对搜索过程有积极的影响，则会获得奖??励信用，这将增加其在后续迭代中被算子选择器选择的机会，搜索将继续进行，??直到达到终止标准为止。??ＡＯＳ策略的两个主要组成部分是信用分配策略和算子选择方式，信用分配策??略定义了如何根据算子在搜索过程中产生的影响来奖励它，算子选择方式将通过??上一步产生的奖励来决定在后续优化中选择何种算子来应用［５１］。??（１）信用分配策略??最常见的信用分配策略会奖励那些能够产生比父代的适应度高的子代的算子??［４５］。其他的信用分配策略也会奖励那些能够产生高质量子代的祖先的算子［５２］，但??这种信用分配策略是否有效还尚不清楚［５３］。Ｆｉａｌｈｏ等人建议，应该奖励那些做出??了罕见但大的改进的算子
图２．１多目标优化过程??多目标优化问题常用的两个求解方法为使川多目标优化算法和将多目标优化??问题转换成单口标优化问题。如图２．１左边部分为一个理想的多０标优化问题求??解的步骤流程图，在步骤１中，多个权衡解被找到，然后在步骤２中更高层信息??用于从权衡解中选择一个解，将这个步骤记住后，很容易可以意识到单目标优化??是多目标优化的一种简单情况。在仅仅只有一个全局最优解的单目标优化的情况??下，步骤１将只会找到一个解，因此不需要执行步骤２。在有多个全局最优解的??多目标优化的情况下，两个步骤都是必要的，首先找到所有的全局最优解，然后??通过问题的更高层信息并从其中选择一个解。如图２．１右边部分是将多目标优化??问题转换成单目标优化问题称之为基于偏好的多目标优化，基于更高层信息，首??先选定了偏好向量ｍ然后偏好向量用于构造复合函数，最后通过一个单目标优??化算法求得一个单一的最优解。??１１??
ｘ＝（ｘ／，Ｘ２，．．．ｖＸｗ）是决策空间中一个ｎ维的向量，Ｚ７：?是ｍ维的目??标向量，它是一个从／７维决策空间到ｍ维目标空间０的映射。如图２．２所示。??ｆＡ?ｅ＝｛Ｆｅ?ｒｗ｝??ｘｉ?＇?ｉｌ?＝?｛ｘｅ?Ｒｎ）????????决策空问?ｆｙ?（１？宁间??图２．２决策空间到目标空间的映射示意图??２．１．２多目标中Ｐａｒｅｔｏ解的相关定义??在求解多目标优化问题时，各个目标函数得到的解可能是相悖的，很难找到??一个解使得所有目标函数的值是最优的。因此在求解时应该尽可能的找到一些妥??协解，这些妥协解尽可能满足多个目标函数达到较优。这一组解我们称之为Ｐａｒｅｔｏ??最优解或非支配解集。Ｐａｒｅｔｏ解的相关定义如下。??定义２．１：Ｐａｒｅｔｏ支配??给定两个决策向量ＡＶＶＳＱ，如果；ｃ支配ｙ，则表示为ｉ＇ｖ，当且仅当解；ｃ在??所有目标上不差于解且解ｘ至少在一个目标上严格好于解??定义２．２：?Ｐａｒｅｔｏ最优解??如果解当且仅当不存在解ｊｃｅｎ使得．ｘｘｘ＊，则称Ｘ＊为Ｐａｒｅｔｏ最优解。??定义２．３：?Ｐａｒｅｔｏ最优解集??Ｐａｒｅｔｏ最优解集（Ｐａｒｅｔｏｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ），简称ＰＳ１。对于在决策空间??中所有最优解组成的集合。Ｓ卩，ＰＳ＝｛ｘｅ｜ｘ是Ｐａｒｅｔｏ最优解丨。多目标进化算法中??所求得解集就是Ｐａｒｅｔｏ最优解集。??定义２．４：?Ｐａｒｅｔｏ前沿面??Ｐａｒｅｔｏ前沿面（Ｐａｒｅｔｏ?ｆｒｏｎｔ），简称ＰＦ。Ｐａｒｅｔｏ最优解集中每个最优解对应的??目标向量组成的曲面。??如图２．３所示
【参考文献】
本文编号：2848487
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18
【图文】：
ＮＳＧＡ－ＩＩ，差分进化的选择，而ＡＯＳ是算子的选择，除此以外在其他方面类??似。??有ＡＯＳ策略的多目标进化算法的一般流程如图１．１所示。在第ｔ次迭代中，??ＡＯＳ选择一个算子来生成后代解，对后代进行评估，并将其插入种群中，并根据??基本多目标进化算法进行更新。如果算子对搜索过程有积极的影响，则会获得奖??励信用，这将增加其在后续迭代中被算子选择器选择的机会，搜索将继续进行，??直到达到终止标准为止。??ＡＯＳ策略的两个主要组成部分是信用分配策略和算子选择方式，信用分配策??略定义了如何根据算子在搜索过程中产生的影响来奖励它，算子选择方式将通过??上一步产生的奖励来决定在后续优化中选择何种算子来应用［５１］。??（１）信用分配策略??最常见的信用分配策略会奖励那些能够产生比父代的适应度高的子代的算子??［４５］。其他的信用分配策略也会奖励那些能够产生高质量子代的祖先的算子［５２］，但??这种信用分配策略是否有效还尚不清楚［５３］。Ｆｉａｌｈｏ等人建议，应该奖励那些做出??了罕见但大的改进的算子
图２．１多目标优化过程??多目标优化问题常用的两个求解方法为使川多目标优化算法和将多目标优化??问题转换成单口标优化问题。如图２．１左边部分为一个理想的多０标优化问题求??解的步骤流程图，在步骤１中，多个权衡解被找到，然后在步骤２中更高层信息??用于从权衡解中选择一个解，将这个步骤记住后，很容易可以意识到单目标优化??是多目标优化的一种简单情况。在仅仅只有一个全局最优解的单目标优化的情况??下，步骤１将只会找到一个解，因此不需要执行步骤２。在有多个全局最优解的??多目标优化的情况下，两个步骤都是必要的，首先找到所有的全局最优解，然后??通过问题的更高层信息并从其中选择一个解。如图２．１右边部分是将多目标优化??问题转换成单目标优化问题称之为基于偏好的多目标优化，基于更高层信息，首??先选定了偏好向量ｍ然后偏好向量用于构造复合函数，最后通过一个单目标优??化算法求得一个单一的最优解。??１１??
ｘ＝（ｘ／，Ｘ２，．．．ｖＸｗ）是决策空间中一个ｎ维的向量，Ｚ７：?是ｍ维的目??标向量，它是一个从／７维决策空间到ｍ维目标空间０的映射。如图２．２所示。??ｆＡ?ｅ＝｛Ｆｅ?ｒｗ｝??ｘｉ?＇?ｉｌ?＝?｛ｘｅ?Ｒｎ）????????决策空问?ｆｙ?（１？宁间??图２．２决策空间到目标空间的映射示意图??２．１．２多目标中Ｐａｒｅｔｏ解的相关定义??在求解多目标优化问题时，各个目标函数得到的解可能是相悖的，很难找到??一个解使得所有目标函数的值是最优的。因此在求解时应该尽可能的找到一些妥??协解，这些妥协解尽可能满足多个目标函数达到较优。这一组解我们称之为Ｐａｒｅｔｏ??最优解或非支配解集。Ｐａｒｅｔｏ解的相关定义如下。??定义２．１：Ｐａｒｅｔｏ支配??给定两个决策向量ＡＶＶＳＱ，如果；ｃ支配ｙ，则表示为ｉ＇ｖ，当且仅当解；ｃ在??所有目标上不差于解且解ｘ至少在一个目标上严格好于解??定义２．２：?Ｐａｒｅｔｏ最优解??如果解当且仅当不存在解ｊｃｅｎ使得．ｘｘｘ＊，则称Ｘ＊为Ｐａｒｅｔｏ最优解。??定义２．３：?Ｐａｒｅｔｏ最优解集??Ｐａｒｅｔｏ最优解集（Ｐａｒｅｔｏｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ），简称ＰＳ１。对于在决策空间??中所有最优解组成的集合。Ｓ卩，ＰＳ＝｛ｘｅ｜ｘ是Ｐａｒｅｔｏ最优解丨。多目标进化算法中??所求得解集就是Ｐａｒｅｔｏ最优解集。??定义２．４：?Ｐａｒｅｔｏ前沿面??Ｐａｒｅｔｏ前沿面（Ｐａｒｅｔｏ?ｆｒｏｎｔ），简称ＰＦ。Ｐａｒｅｔｏ最优解集中每个最优解对应的??目标向量组成的曲面。??如图２．３所示
【参考文献】
中国期刊全文数据库 前3条
1 吴启武;王建萍;周贤伟;;WDM光网络中的组播路由算法研究[J];电信科学;2009年09期
2 公茂果;焦李成;杨咚咚;马文萍;;进化多目标优化算法研究[J];软件学报;2009年02期
3 李昌兵;曹长修;余义斌;;基于混合遗传算法的多播路由多目标优化[J];计算机仿真;2007年09期
中国硕士学位论文全文数据库 前1条
1 刘文娟;基于分解的多目标量子差分进化算法研究[D];山西财经大学;2015年
本文编号：2848487
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/2848487.html
