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

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.

Authors:

• Tarek M. Mahmoud

Keywords:

• Genetic Algorithms
• Flow Assignment
• Routing
• Computer network
• Simulated Annealing.

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).