PhD Thesis - Evolutionary Algorithms for Optical Network Design: A Genetic-algorithm/Heuristic Hybrid Approach

Summary

Multi-wavelength all-optical transport networks can potentially provide the huge bandwidths necessary for broadband services. However, they present a challenging range of difficult network design and optimisation problems. Recently, evolutionary algorithms (EAs) have attracted growing interest for use on similar complex problems in many fields, including telecommunications. However, while EAs are good general-purpose search and optimisation procedures, they are almost never the best approach for any specific problem. A powerful alternative is the development of problem-specific EAs---genetic-algorithm (GA)/heuristic hybrids. These employ both problem-specific encoding and operators, combining the best existing heuristics for the problem within an overall GA framework. Moreover, operator-probability adaptation is used so that the most appropriate blend of operators is applied at each stage in a run.

This thesis describes the application of GA/heuristic hybrids to two of the main problems in the design of multi-wavelength all-optical transport networks: mesh network topology design, and wavelength-path routing, fibre choice and wavelength allocation. It starts with an overview of EAs, a tutorial on GAs, a near-exhaustive survey of evolutionary telecommunications, and surveys of both GA/heuristic hybrids and operator-probability adaptation. A software toolset for optical network optimisation, modelling and design (NOMaD), implementing the author's GA/heuristic hybrid approach, is described, including the design-assessment metrics, overall GA framework, genetic operators and the operator-probability adaptation mechanism. Experimental results for both mesh network topology design, and wavelength-path routing, fibre and wavelength allocation are reported. An investigation into NOMaD's operator-probability adaptation mechanism is described. Finally, the successes and limitations of the research are discussed, and numerous suggestions for further work made. Overall, the hybrid approach is shown to provide excellent solutions, of comparable or higher quality than those obtained with either heuristics or simple GAs alone, and requiring less computational effort than GAs.

Download

All the files on this page are available in gzip-ed PostScript. They should be unpacked after downloading using GNU gunzip. Download gzip for Unix (tar file) or MSDOS.

	Full Thesis (1.46 Mb)
	Chapter 1: Introduction (177 Kb)
	Chapter 2: Evolutionary Algorithms (282 Kb)
	Chapter 3: NOMaD (295 Kb)
	Chapter 4: GA/Heuristic Hybrid Network Design (298 Kb)
	Chapter 5: Experimental Results (244 Kb)
	Chapter 6: Discussion & Conclusions (173 Kb)
	Contents/References (203 Kb)
	Appendices (894 Kb)