Topological optimization of communication networks using genetic algorithms

TOPOLOGICAL OPTIMIZATION OF COMMUNICATION NETWORKS USING GENETIC ALGORITHMS (Ph.D. Thesis) Fulya ALTIPARMAK GAZI UNIVERSITY INSTITUTE OF SCIENCE AND TECHNOLOGY JUNE 1996 ABSTRACT The use of computer communication networks has been rapidly increasing recently. There are two important reasons for this: a) they provide an economical means of sharing expensive computer resources, and b) they provide access to users from remote locations. As the use of these networks increases rapidly, there is a growing concern about their reliability and cost. The objective of this study is to design a rriinimum cost network, satisfying specified reliability constraint. Computation time of the classical optimization methods that are used to design these networks increases exponentially as the scale of the networks increases. There are two different algorithms in the literature for topological design of the communication networks subject to reliability constraint which is a NP-hard problem. One of them is a branch and bound algorithm based on the decomposition method. In this algorithm, stochastic reliability criterion was used as a reliability measure. Second algorithm based on the branch and bound method is a heuristic method and use different reliability measure. In this thesis, a new algorithm was developed for topological optimization of large scale networks under reliability constraint which is not solved by using current methods. Evolution process of the developed algorithm based on the Genetic Algorithms (GA) consits of two steps. In the first algorithm developed in the first step, binary coding and classical genetic operators were used. In the second algorithm, problem specific coding was used, new genetic operators and repair algorithm for this coding were developed. These two algorithms and the classical optimization method were compared in terms of computation time, size of the problem, and deviation from the optimum value of the solutions obtained from these two algorithms. This developed genetic operators and the GA which is firstly used for solving the problem described above, are important in terms of the contribution to the literature.