A Genetic and Simulated Annealing Based Algorithms for Solving the Flow Assignment Problem in Computer Networks

Authors: Tarek M. Mahmoud

Abstract:

Selecting the routes and the assignment of link flow in a computer communication networks are extremely complex combinatorial optimization problems. Metaheuristics, such as genetic or simulated annealing algorithms, are widely applicable heuristic optimization strategies that have shown encouraging results for a large number of difficult combinatorial optimization problems. This paper considers the route selection and hence the flow assignment problem. A genetic algorithm and simulated annealing algorithm are used to solve this problem. A new hybrid algorithm combining the genetic with the simulated annealing algorithm is introduced. A modification of the genetic algorithm is also introduced. Computational experiments with sample networks are reported. The results show that the proposed modified genetic algorithm is efficient in finding good solutions of the flow assignment problem compared with other techniques.

Keywords: Genetic Algorithms, Flow Assignment, Routing, Computer network, Simulated Annealing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077997

References:

[1] D. Berttsekas, and R. Gallager. "Data Networks", Second Edition, Prentice Hall, Englwood Cliffs, New Jersey (1992).
[2] H. Chang, and P. Jung, "SA-selection-based Genetic Algorithm for the Design of Fuzzy Controller", International Journal of Control, Automation, and Systems, Vol. 3, no. 2, pp. 236-243, June (2005).
[3] W. Chang and R. S. Ramakrishna, "A genetic algorithm for shortest path routing problem and the sizing of populations", IEEE Transaction on Evolutionary Computation, Vol.6, No. 6, December (2002).
[4] M. Gen and R. Cheng, "Genetic algorithms and engineering optimization", John Wiley&Sons, Inc., (2000).
[5] Y.,Habib, M. Sait and H. Adiche, "Evolutionary algorithms, simulated annealing and tabu search: a comparative study", Engineering Applications of Artificial Intelligence 14, pp. 167-181, (2001).
[6] K. Ko, K. Tang, C. Chan, K. Man and S. Kwong, "Using genetic algorithms to design mesh networks", IEEE Computer, pp 56-61, (1997).
[7] X. Lin, Y. Kwok and V. Lau, "A genetic algorithm based approach to route selection and capacity flow assignment", Computer Communications 26, pp 961-974, (2003).
[8] Z. Michalewicz, "Genetic algorithms + data structure = evolution programs", 3rd edition, Springer Verlag, New York, USA, (1996).
[9] P. Mills, E. Tsang, Q. Zhang and J. Ford, "A survey of AI-based metaheuristics for dealing with local optima in local search", Technical Report Series, Report No. CSM-416, September (2004).
[10] J. Shen, F. Xu and P. Zheng,"A tabu search algorithm for routing and capacity assignment problem in computer networks", Computers & Operations Research 32, pp 2785- 2800, (2005).
[11] K. Walkowiak, "Ant algorithm for flow assignment in connectionoriented networks", International Journal of Applied Mathematics and Computer Science, 15, pp 205-220, (2005).
[12] Z. Wang, D. Browning, "An Optimal Distributed Routing Algorithm", IEEE Transaction on Communication, vol.39, no. 9, (1991).