A GA/Heuristic hybrid technique for routing and wavelength assignment in WDM networks

Talay A., Oktug S. F.

APPLICATIONS OF EVOLUTIONARY COMPUTING, vol.3005, pp.150-159, 2004 (SCI-Expanded) identifier identifier


The routing and wavelength assignment problem which is known to be NP-hard, in all-optical transport networks is considered. The present literature on this topic contains a lot of heuristics. These heuristics, however, have limited applicability because they have a number of fundamental problems including high time complexity, and lack of scalability with respect to optimal solutions. We propose a hybrid genetic algorithm/heuristic based algorithm. A cost model that incorporates a dependency on link wavelength requirements is adopted. The hybrid algorithm presented uses an object-oriented representation of networks, and incorporates four operators: semi-adaptive path mutation, single-point crossover, reroute, and shift-out. Experimental results of the test networks make clear that, when the network cost depends on heavily wavelength assignment, the proposed GA/Heuristic hybrid approach provides promising results compared to recent wavelength assignment heuristics.