A Research On The Meta-Heuristics For The Optimizations On Optical Networks

With the drastic expanding of the traffics on the communication networks,the planning and the construction of the optical networks have absorbed more and more attentions.Due to its close correlation to the cost of construction and management for the networks,the optimization on optical networks becomes one of the most important issues in the optical network communication field.Several sub-problems of the optimization problem in optical networks have been proved to be NP-hard,and there is no perfect match between these problems and the classical NP-hard problems.Therefore,the optimization of optical networks becomes a challenging subject both in academia and industry.Because of its high complexity,even a small scale instance in the optical optimization is hard to be solved by an exact algorithm within a short time limit.Thus,the heuristic algorithm or the combination of the heuristic and exact algorithms is the only effective method.The meta-heuristic algorithm,which is widely used in solving kinds of complexed combinatorial optimizations,is one of the most powerful tools to solve NP-hard problems.This thesis studies effective meta-heuristic algorithms tackling optimization problems in optical networks.The important features of the algorithms are well illustrated and analyzed.The contributions of this thesis are listed as follows:1.This thesis gives for the first time the general mathematic models for the Network Design Problem With Traffic Grooming and the Traffic Grooming Problem With Simple Path Constraints,which are the two problems urgently needing to be answered in the real industry,thus to lay the foundation of the research of these problems.2.A Hybrid Exact Tabu Search(HETS)algorithm with following features is proposed for tackling the network design problem with traffic grooming.2.1 The HETS algorithm uses the mixed integer programming procedure and the linear programming procedure as slave sub-algorithms and embeds them into a master algorithm which is an iterated tabu search.The accuracy of the exact algorithms and the high efficiency of the heuristic are inherited by the HETS algorithm.2.2 The proposed integer programming model for the sub-problem,the grooming problem,can be solved easily.The gap between the linear relaxation and the integer solution is extremely small.2.3 The edge twist neighborhood structure is proposed.The neighborhood structure selects proper edges to be operated on in order to reduce the computation thus to boost the efficiency of the search procedure.A fast evaluation technique is also proposed for the neighborhood structure to augment the effectiveness.2.4 For the 22 public instances of the network design problem with traffic grooming,the HETS updates the best-known result for 21 of them while gets the same best result for the rest instance.Moreover,HETS uses less CPU time than the referenced algorithm.3.A greedy randomized adopted search procedure(GRASP)with the following characteristics is proposed for the traffic grooming problem with the simple path constraints.3.1 The algorithm is composed of a construction phase and an optimization phase iteratively.The optimization phase is a hierarchical algorithm with several sub local search algorithms in a nested structure.3.2 A compound objective function for the upper local search algorithm is proposed providing better connections between each sub-algorithms and making the algorithm more effective.3.3 The proposed algorithm is tested on the random instances which are generated respecting to the real world characteristics.By comparing to the public optimization solver software CPLEX and Local Sovler,GRASP shows much better performance.And also,only the proposed GRASP can solve the large scale instances in which the public solvers fail.4.A multi-neighborhood iterated tabu search(MN-ITS)algorithm is proposed for tackling the routing and wavelength assignment(RWA)problem.4.1 Three different neighborhood structures,which expand the searching ability greatly,are introduced to the algorithm.A uniformed fast incremental evaluation method is implemented for the three neighborhood structures giving the proposed algorithm an ability to switch among the neighborhoods smoothly.4.2 The proposed algorithm is tested on the 88 public instances for the RWA problem.MN-ITS is able to get the optimal solution for all the instances in the W set and 42 instances in the Y set.MN-ITS also updates the best-known result for 5 instances in the Y set.5.The proposed algorithms are analyzed with the logical proof and comparison experiments.The core ideas of the algorithms are properly illustrated and the efficacy and the efficiency are well proved.This research provides the guide for the mathematical modeling of the problems with a network structure.Meanwhile,it lights the path to how to design the meta-heuristics for the complexed optimization problems.The following enlightenment is provided: how to design the neighborhood structure for a complexed optimization problem;how to evaluate the neighborhood effectively;how to divide the complexed problem into simpler ones;how to coordinate the relationship among each neighborhood making the algorithm more effective;and how to combine the exact algorithm and the heuristic to form a hybrid algorithm in order to get the advantages from the two algorithm.The proposed techniques can be extended to other algorithms for the NP-hard problems with the similar structure to obtain similar improvements.A professional system can be developed by combining the proposed algorithms to solve a whole optical network project.