论文部分内容阅读
在科学研究和工程领域中许多问题都是由多个相互冲突的目标组成,一般称这一类问题为多目标优化问题。基于种群的进化算法在单次运行中能得到一个近似的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解集,从而达到在减少组播路由时延与网络资源使用费用的情况下提高信道的利用率。