To tackle the QoS based routing and wavelength allocation problem, a self-adaptive multi-objective genetic algorithm based on decomposition is presented. The chromosome coding scheme, crossover and mutation operators are redefined, and a repair method is proposed to guarantee the generated offspring are valid. The proposed algorithm was evaluated on a set of different scale test problems and compared with the recently proposed related algorithms. The experimental results revealed encouraging results in terms of the solution quality and the processing time.
In WDM network, the routing and wavelength assignment (RWA) is a well-known NP-completer problem [9]. But, with the development of network transmission business, many emerging network services require specialized Quality of Service (QoS). The provisioning of QoS based network routing and wavelength assignment is becoming more and more demanding, which is in general terms a more complex problem [17]. Since the QoS is multidimensional concept and usually more than one QoS related objectives and constraints will be considered during setting up light-path by routing and assigning a wavelength to each connection, the QoS based routing and wavelength allocation problem (QRWA) is an intrinsically multi-objective optimization problem.
Due to the computational complexity, the most related researches are concentrated on heuristic-based algorithms [1], [11] and [13] especially the meta-heuristic approaches [4], [7], [9], [10] and [15] aiming to find near-optimal solutions. Furthermore, the most existing methods divide this problem into two separate single objective sub-problems and include two consecutive optimization phases, one phase for the routing process, and the other for the wavelength allocation process. Several multi-objective optimizing methods are not applied for this problem until recently, which tackle multiple objectives simultaneously. In [18], the SPEA algorithm [5] is applied to solve the QRWA problem. In [9], a hybrid evolutionary computation approach consisting of genetic algorithm for routing allocation with minimum degree first for wavelength assignment (GA-MDF) and the fast non-dominated sorting genetic algorithm to search for non-dominated solutions is applied for solving the multi-objective RWA network design problem. In [4], a multi-objective genetic algorithm (MOGA) that uses classical multi-objective optimization strategies to jointly solve the static impairment aware RWA (IA-RWA) problem. We can see that the most existing researches take the RWA as a single objective optimization problem, and few researches has been done for the multi-objective QRAW problem.
As a novel meta-heuristic approach, the GA algorithm was proposed in the 1970s by John Holland at University of Michigan, motivated by the process of natural evolution. It has been extensively studied and successfully applied to solve many multi-objective optimization problems [2], [3], [5], [12], [14] and [16]. In this paper, a novel self-adaptive multi-objective genetic algorithm called QRWA_DMGA is proposed to tackle the multi-objective QRWA problem, which is based on the ideas of self-adaptive decomposing a multi-objective optimization problem into a number of scalar optimization sub-problems and optimizing them simultaneously. In this algorithm, a variable-length node chromosome encoding scheme is defined and used to represent the candidates, and the crossover and mutation schemes are redefined to adapt to this problem. In order to efficiently construct a valid candidate, a repair process based on depth first search approach is proposed. To show the effectiveness of this algorithm, it is evaluated on a set of different scale test problems and compared with the recently related GA based multi-objective optimization algorithms. This paper is organized as follows. In Section 2, we give the model definition of QRWA problem, including the considered QoS indicators and their definitions. The detail of the QRWA_DMGA algorithm is provided in Section 3. The experiments and comparative studies are given in Section 4. Finally, Section 5 summarizes the contribution of this paper along with some future research directions.
In this paper, a self-adaptive multi-objective genetic algorithm based on decomposition is presented and compared with the recently proposed related algorithms for the QRWA problem. The experimental results reveal very encouraging results in terms of the solving efficiency and quality. It not only provides a useful way to solve the QRWA problem, but also can give a reference for solving other MOPs. There is a number of research directions that can be considered as useful extensions of this research. We can combine them with some local search strategy, hybrid them with other meta-heuristic algorithms properly, or use it to solve other problems.
