Abstract
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 parallel hybrid genetic algorithm/heuristic based algorithm. Parallel genetic algorithms represent a new kind of meta-heuristics of higher efficiency and efficacy thanks to their structured population and parallel execution. 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 parallel GA/Heuristic hybrid approach provides promising results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Holland, J.H.: Adaptation in Natural and Artificial Sys. U. of Michigan Pr., Ann Arbor (1975)
Gorges-Schleuter, M.: ASPARAGOS: An Asynchronous Parallel Genetic Optimisation Strategy. In: Schaffer, J.D. (ed.) Proc. of the 3rd ICGA, Morgan Kaufmann, San Francisco (1989)
Spiessens, P., Manderick, B.: A Massively Parallel Genetic Algorithm. In: Belew, R.K. (ed.) Proceedings of the 4th Int. Conf. on Genetic Algorithms, Morgan Kaufmann, San Francisco (1991)
Gordon, V.S., Whitley, D.: Serial and Parallel Genetic Algorithms as Function Optimizers. In: Forrest, S. (ed.) Proc. of the 5th ICGA, Morgan Kaufmann, San Francisco (1993)
Stender, J. (ed.): Parallel Genetic Algorithms: Theory and Applications. IOS Press, Amsterdam (1993)
Lin, S., Punch, W.F., Goodman, E.D.: Coarse-grain Parallel Genetic Algorithms: Categorization and New approach. Parallel & Distributed Processing (1994)
Belding, T.C.: The Distributed Genetic Algorithm Revisited. In: Eshelman, L.J. (ed.) Proc. of the 6th ICGA, Morgan Kaufmann, San Francisco (1995)
Herrera, F., Lozano, M.: Gradual Distributed Real-coded Genetic Algorithms. Technical Report #DECSAI-97-01-03 (1997) (Revised version 1998)
Tanese, R.: Distributed Genetic Algorithms. In: Schaffer, J.D. (ed.) Proc. of 3rd ICGA (1989)
Alba, E., Aldana, J.F., Troya, J.M.: A Genetic Algorithm for Load Balancing in Parallel Query Evaluation for Deductive Relational Databases. In: Pearson, D.W., Steele, N.C., Albrecht, R.F. (eds.) Procs. of the I. C. on ANNs and GAs, Springer, Heidelberg (1995)
Lozano, M.: Application of Fuzzy Logic Based Techniques for Improving the Behavior of GAs with Floating Point Encoding. Ph.D. Thesis. University of Granada (1996)
Alba, E., Aldana, J.F., Troya, J.M.: Full Automatic ANN Design: A Genetic Approach. In: Mira, J., Cabestany, J., Prieto, A. (eds.) IWANN 1993. LNCS, vol. 686, Springer, Heidelberg (1993)
Alba, E., Cotta, C.: Evolution of Complex Data Structures. Informatica y Automatica 30(3), 42–60 (1997)
Cantu-Paz, E.: A Summary of Research on Parallel Genetic Algorithms. R. 95007 (1995). Also revised version, IlliGAL R. 97003 (1997)
Ribeiro Filho, J.L., Alippi, C., Treleaven, P.: Genetic Algorithm Programming Environments. In: Stender, J. (ed.) Parallel Genetic Algorithms: Theory & Applications, IOS Press, Amsterdam (1993)
Zang, H., Jue, J.P., Mukherjee, B.: A Review of Routing and Wavelength Assignment Approaches for Wavelength-routed Optical WDM networks. Optical Networks 1(1) (2000)
Nagatsu, N., Hamazumi, Y., Sato, K.I.: Number of Wavelengths Required for Constructing Large-scale Optical Path Networks. El. Com. Jpn. 1, Com. 78, 1–11 (1995)
Nagatsu, N., Hamazumi, Y., Sato, K.I.: Optical Path Accommodation Designs Applicable to Large Scale Networks. IEICE Trans. Commun. E78-B 4, 597–607 (1995)
Wuttisittikulkij, L., O’Mahony, M.J.: A Simple Algorithm for Wavelength Assignment in Optical networks. In: Proc. 21st European conf. on Optical Commun, Brussels, pp. 859–862 (1995)
Tan, L.G., Sinclair, M.C.: Wavelength Assignment Between the Central Nodes of the COST239 European Optical Network. In: Proc. of 11th UK Perf. Eng., pp. 235–247. W. Liverpool, UK (1995)
Talay, A.C., Oktug, S.: A GA/Heuristic Based Hybrid Technique for Routing and Wavelength Assignment in WDM Networks. In: Raidl, G.R., Cagnoni, S., Branke, J., Corne, D.W., Drechsler, R., Jin, Y., Johnson, C.G., Machado, P., Marchiori, E., Rothlauf, F., Smith, G.D., Squillero, G. (eds.) EvoWorkshops 2004. LNCS, vol. 3005, pp. 150–159. Springer, Heidelberg (2004)
Davis, L. (ed.): Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York (1991)
Wauters, N., Demeester, P.: Design of the Optical Path Layer in Multiwavelength Crossconnected Networks. IEEE J. Sel. Areas Commun. 14(5), 881–892 (1996)
Mikac, B., Inkret, R.: Application of a Genetic Algorithm to the Availability-Cost Optimization of a Transmission Network Topology. In: Proc. 3rd Intl. Conf. on Artificial Neural Networks and GAs (ICANNGA 1997), pp. 304–307. Univ.of East Anglia, Norwich (1997)
Griffith, P.S., Proestaki, A., Sinclair, M.C.: Heuristic Topological Design of Low-Cost Pptical Telecommunication Networks. In: Proc. of the 12th UK Perf. Eng. Workshop, Edinburgh, UK, pp. 129–140 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Talay, A.C. (2004). A Parallel Genetic Algorithm/Heuristic Based Hybrid Technique for Routing and Wavelength Assignment in WDM Networks. In: Aykanat, C., Dayar, T., Körpeoğlu, İ. (eds) Computer and Information Sciences - ISCIS 2004. ISCIS 2004. Lecture Notes in Computer Science, vol 3280. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30182-0_82
Download citation
DOI: https://doi.org/10.1007/978-3-540-30182-0_82
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23526-2
Online ISBN: 978-3-540-30182-0
eBook Packages: Springer Book Archive