Research On Multi-Objective Evolutionary Algorithms For Multicast Routing In Optical Networks

In the field of scientific research and engineering,many problems are composed of multiple conflicting goals.We call this problem as a multi-objective optimization problem.The population-based evolutionary algorithm can obtain an approximate Pareto solution set in a single run,so the multi-objective evolutionary algorithm has become a more general and effective method to solve the multi-objective optimization problem.The Non-dminated Sorting Genetic Algorithm NSGA-? is an improvement of the Non-dminated Sorting Genetic Algorithm NSGA in 2002 by Deb et al.It introduces fast non-dominated sorting algorithm,elite strategy,crowding distance and crowding distance comparison operator.It is one of the best evolutionary multi-objective optimization algorithms so far.However,the NSGA-? algorithm still has the shortcomings of diversity loss and slow convergence rate in solving multi-objective optimization problems.In this paper,we improve the steady-state NSGA-? algorithm in three aspects,such as the updating strategy of the non-dominated layer,the credit assignment strategy and the operator selection strategy of adaptive operator selection strategy,and propose an improved algorithm named AOS_SSNSGA-?.At the same time,according to the characteristics of optical networks,a MRWA_AOSNSGA-?-SD algorithm based on steady-state NSGA-? framework has been proposed to solve the problem of multicast routing wavelength assignment in optical networks.The main work of this paper is as follows:(1)An improved steady-state NSGA-? algorithm based on adaptive operator selection strategy,named AOS-SSNSGA-?,is proposed.The algorithm uses steady-state NSGA-? as the framework,the population can be updated immediately before all the sub-populations are generated,and the elite information can be used in a timely manner,which overcomes the shortcoming of the traditional NSGA-? algorithm that the convergence rate is slow.At the same time,in order to reduce the cost of maintaining the non-dominant layer structure by the steady-state NSGA-? algorithm,an improved non-dominant layer update strategy is proposed.By extracting valid information from the current non-dominant layer structure,only one non-dominant ordering is performed at the beginning of the algorithm,then only a limited number of non-dominant layer structures need to be updated,so that a large amount of unnecessary comparison operations are avoided.In order to improve the robustness of the algorithm to the problem formula and overcome the problems of high cost and long time consuming brought by the parameter adjustment,the adaptive operator selection strategy has been applied to the steady-state NSGA-? algorithm in this paper.For credit assignment,a credit assignment strategy based on fitness rate ranking is proposed.In order to track the search process dynamically,a sliding window is used to record the growth rate of fitness in the most recent iterations of the operator.At the same time,the decay mechanism has been used to increase the selection probability of the optimal operator.For the operator selection strategy,the performance of the operator may fluctuate very little or large with the evolution of the population,and the dynamic distribution of the credit value received by the operator will greatly affect the efficiency of the operator selector.Therefore,an operator selection strategy based on multi-armed bandit is proposed.Compared with the classical evolutionary multi?objective algorithm NSGA-?,MOEA-D-DRA,R2-IBEA,and the combination of classic multi-objective credit assignment strategy OP-Do,SI-Do,CS-Do and operator selection PM and AP,the algorithm AOS-SSNSGA-? proposed in this paper has better convergence and diversity on the test functions of ZDT and DTLZ series standards.(2)In view of the existence of multiple conflicting QoS performance indexes in the wavelength assignment problem of multicast routing in WDM networks,a multi?objective optimization mathematical model for multicast routing in optical networks,named MOMRWA,is proposed in this paper.The objectives of optimization include minimizing the resource cost,minimizing the end-to-end delay and minimizing the used channels.Some Quality of Service metrics have also been considered in MOMRWA.In order to solve the proposed MOMRWA problem,a steady-state NSGA-? algorithm MRWA_AOSNSGA-?-SD,which combines adaptive operator selection strategy with sequential decomposition mechanism,has been proposed.For the multicast wavelength assignment subproblem,this paper adopts the wavelength random assignment method in the dynamic wavelength assignment algorithm.A backup routing strategy has been proposed to solve the multicast routing sub-problem.Due to infeasible solutions generated during the search process,a light tree recovery mechanism based on Minimum Path Cost Heuristic(MPH)algorithm has been proposed to eliminate the loop caused by the gene recombination operation.The experimental results show that compared with other algorithms,the proposed MRWA_AOSNSGA-?-SD algorithm can obtain more optimal Pareto solution set than other algorithms,so as to improve the channel utilization rate while reducing multicast routing delay and network resource costs.