Digital data networks design using genetic algorithms. (English) Zbl 0979.90015
Summary: Communication networks have witnessed significant growth in the last decade due to the dramatic growth in the use of Internet. The reliability and service quality requirements of modern data communication networks and the large investments in communications infrastructure have made it critical to design optimized networks that meet the performance parameters. Digital Data Service (DDS) is a popular communication service that provides users with a digital connection. The design of a DDS network is a special case of the classic Steiner-tree problem of finding the minimum cost tree connecting a set of nodes, using Steiner nodes. Since it is a combinatorial optimization problem several heuristic algorithms have been developed including tabu search, and branch and cut algorithm. In this paper, a new approach using genetic algorithms (GAs) is proposed to solve the problem. The results from GA are compared with the tabu search method. The results indicate that GA performs as well as tabu search in terms of solution quality but has lower computation time. However, reducing the number of iterations in tabu search makes it faster than GA and comparable in solution quality with GA.
MSC:
| 90B18 | Communication networks in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90B40 | Search theory |
References:
| [1] | Abuali, F. N.; Schoenefeld, D. A.; Wainwright, R. L., The design of a multipoint line topology for a communication network using genetic algorithms, Proceedings of the Seventh Oklahoma Conference on Artificial BL Intelligence, 101-110 (1993) |
| [2] | Abuali, F. N.; Wainwright, R. L.; Schoenefeld, D. A., Determinant factorization: A new encoding scheme for spanning trees applied to the probabilistic minimum spanning tree problem, Proceedings of the Sixth International Conference on Genetic Algorithms, 470-477 (1995) |
| [3] | Aggarwal, C. C.; Orlin, J. B.; Tai, R. P., Optimized crossover for the independent set problem, Operations Research, 45, 226-234 (1997) · Zbl 0891.90140 |
| [4] | Ahuja, R. K.; Orlin, J. B., Developing fitter genetic algorithms, INFORMS Journal of Computing, 9, 5, 251-253 (1997) |
| [5] | Ahuja, R.K., Magnauti, T.L., Orlin, J.B., 1993. Network Flows: Theory Algorithms Applications. Prentice-Hall, Englewood Cliffs, NJ; Ahuja, R.K., Magnauti, T.L., Orlin, J.B., 1993. Network Flows: Theory Algorithms Applications. Prentice-Hall, Englewood Cliffs, NJ · Zbl 1201.90001 |
| [6] | Anderson, C.; Fraughnaugh, K.; Parker, M.; Ryan, J., Path assignment for call routing: An application of Tabu search, Annals of Operations Research, 43, 301-312 (1993) · Zbl 0775.90144 |
| [7] | Back, T.; Hoffmeister, F., Extended selection mechanism in genetic algorithms, Proceedings of the Fourth International Conference on Genetic Algorithms, 92-99 (1991) |
| [8] | Back, T., Fogel, D., Michalawecz, Z. (Eds.), 1997. Handbook of Evolutionary Computation. Oxford University Press, Oxford; Back, T., Fogel, D., Michalawecz, Z. (Eds.), 1997. Handbook of Evolutionary Computation. Oxford University Press, Oxford · Zbl 0883.68001 |
| [9] | Beasley, J.E., 1990. OR Library, Imperial College, UK. URL: mscmga.ms.ic.ac.uk/info.html; Beasley, J.E., 1990. OR Library, Imperial College, UK. URL: mscmga.ms.ic.ac.uk/info.html |
| [10] | Chang, C.-C.; Wu, W.-B., Efficient path and vertex exchange in Steiner tree algorithms, Networks, 29, 2, 81-92 (1997) |
| [11] | Charddaire, P.; Kapsalis, A.; Mann, J. W.; Rayward-Smith, V. J.; Smith, G. D., Applications of genetic algorithms in telecommunications, Proceedings of the Second International Workshop on Applications of Neural Networks to Telecommunications, 290-299 (1995) |
| [12] | Chopra, S., Rao, M.R., 1989. On the Steiner tree problem I & II. Working Paper, New York University; Chopra, S., Rao, M.R., 1989. On the Steiner tree problem I & II. Working Paper, New York University |
| [13] | Coombs, S., Davis, L., 1987. Genetic algorithms and communication link speed design: Constraints and operators. In: Grefenstette, J.J. (Ed.), Proceedings of the Second International Conference on Genetic Algorithms and their Applications, pp. 257-260; Coombs, S., Davis, L., 1987. Genetic algorithms and communication link speed design: Constraints and operators. In: Grefenstette, J.J. (Ed.), Proceedings of the Second International Conference on Genetic Algorithms and their Applications, pp. 257-260 |
| [14] | Cuppinim, M., A genetic algorithm for channel assignment problems, European Transactions on Telecommunications Related Technologies, 285-294 (1994) |
| [15] | Davis, L.; Coombs, S., Optimizing network link sizes with genetic algorithms, Modeling and Simulation Methodology, 317-331 (1989) |
| [16] | Esbensen, H., Computing near-optimal solutions to the Steiner problem in a graph using genetic algorithm, Networks, 26, 4, 173-185 (1985) · Zbl 0856.90115 |
| [17] | Gen, M., Cheng, R., 1997. Genetic Algorithms and Engineering Design. Wiley, New York, 1997; Gen, M., Cheng, R., 1997. Genetic Algorithms and Engineering Design. Wiley, New York, 1997 |
| [18] | Glover, F., Tabu search – part I, ORSA Journal of Computing, 3, 190-206 (1989) · Zbl 0753.90054 |
| [19] | Glover, F., Genetic algorithms and scatter search: Unsuspected potentials, Statistics and Computing, 4, 131-140 (1994) |
| [20] | Glover, F.; Lee, M.; Ryan, J., Least cost network topology design for a new service: An application of Tabu search, Annals of Operations Research, 33, 351-362 (1991) · Zbl 0736.90031 |
| [21] | Glover, F.; Kelly, P. J.; Laguna, M., Genetic algorithms and Tabu search, Computers and Operations Research, 22, 1, 111-134 (1995) · Zbl 0813.90093 |
| [22] | Glover, F., Laguna, M., 1993. Tabu search. In: Reeves, C. (Ed.), Modern Heuristic Techniques for Combinatorial Problems, Basil Blackwell, Oxford; Glover, F., Laguna, M., 1993. Tabu search. In: Reeves, C. (Ed.), Modern Heuristic Techniques for Combinatorial Problems, Basil Blackwell, Oxford · Zbl 0774.90033 |
| [23] | Glover, F., Laguna, M., 1997. Tabu Search. Kluwer Academic Publishers, Boston, MA; Glover, F., Laguna, M., 1997. Tabu Search. Kluwer Academic Publishers, Boston, MA · Zbl 0930.90083 |
| [24] | Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA; Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA · Zbl 0721.68056 |
| [25] | Hansen, P., 1986. The steepest ascent mildest descent heuristic for combinatorial programming. Numerical Methods in Combinatorial Optimization, Capri, Italy; Hansen, P., 1986. The steepest ascent mildest descent heuristic for combinatorial programming. Numerical Methods in Combinatorial Optimization, Capri, Italy |
| [26] | Hertz, A., Taillard, E., de Werra, D., 1996. Tabu Search, Local Search in Combinatorial Optimization. Wiley, Chichester; Hertz, A., Taillard, E., de Werra, D., 1996. Tabu Search, Local Search in Combinatorial Optimization. Wiley, Chichester · Zbl 0932.90031 |
| [27] | Hesser, J.; Manner, R.; Stucky, O., Optimization of Steiner trees using genetic algorithms, Proceedings of the Third International Conference on Genetic Algorithms, 231-236 (1989) |
| [28] | Holland, J., 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI; Holland, J., 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI · Zbl 0317.68006 |
| [29] | Hoelting, C.; Schoenfeld, D.; Wainwright, R., A genetic algorithm for the minimum broadcast time problem using a global precedence vector, Proceedings of the ACM Symposium on Applied Computing, 258-262 (1996) |
| [30] | Hwang, F. K.; Richard, D. S.; Winter, P., The Steiner tree problem, Annals of Discrete Mathematics, 53, 59-85 (1992) · Zbl 0774.05001 |
| [31] | Kapsalis, A.; Rayward-Smith, V. J.; Smith, G. D., Solving the graphical Steiner tree problem using genetic algorithms, Journal of the Operations Research Society, 44, 4, 397-406 (1993) · Zbl 0774.90083 |
| [32] | Karunanithi, N., Carpenter, T., 1993. A ring loading application of genetic algorithms. Technical Report TM-ARH-023337, Bellcore, Bell Communication Research, Red Bank, NJ; Karunanithi, N., Carpenter, T., 1993. A ring loading application of genetic algorithms. Technical Report TM-ARH-023337, Bellcore, Bell Communication Research, Red Bank, NJ · Zbl 0882.90043 |
| [33] | Kershenbaum, A., When genetic algorithms work best, INFORMS Journal of Computing, 9, 3, 254-255 (1997) |
| [34] | Kruskal, J. B., On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, 7, 48-50 (1956) · Zbl 0070.18404 |
| [35] | Kumar, G. P.; Babu, G. P., Optimal network partitioning for fault-tolerant network management using evolutionary programming, Information Processing Letters, 25, 145-149 (1994) · Zbl 0807.68010 |
| [36] | Laguna, M. J.; Glover, F., Bandwidth packing: A Tabu search approach, Management Science, 39, 4, 492-500 (1993) · Zbl 0774.90033 |
| [37] | Lee, Y.; Chiu, S. Y.; Ryan, J., A branch and cut algorithm for Steiner tree-star problem, INFORMS Journal on Computing, 8, 3, 100-120 (1996) |
| [38] | Lee, Y.; Lu, L.; Qiu, Y.; Glover, F., Strong formulations and cutting planes for designing digital data networks, Telecommunication Systems, 2, 261-274 (1994) |
| [39] | Liu, X.; Sakamoto, A.; Shimamoto, T., Genetic channel router, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 3, 492-501 (1994) |
| [40] | Marin, F. J.; Gonzalez, F. J.; Sandoval, F., The routing problem in traffic control using genetic algorithms, Proceedings of the Second IFAC Symposium on Intelligent Components and Instruments for Control Application, 8-10 (1994) |
| [41] | Michalawecz, Z., 1992. Genetic Algorithms; Michalawecz, Z., 1992. Genetic Algorithms |
| [42] | Murgu, A.; Lahdelma, R., Tracking statistics in communication traffic control using a genetic algorithm, Proceedings of the First Nordic Workshop on Genetic Algorithms and Their Applications, 241-258 (1995) |
| [43] | Oyman, A. I.; Solvinf, C. E., Concentrator location-problems using genetic algorithms, Proceedings of the Seventh Mediterranean Electrotechnical Conference, 3, 1341-1344 (1994) |
| [44] | Palmer, C. C.; Kershenbaum, A., An approach to a problem in network design using genetic algorithms, Networks, 26, 3, 151-163 (1995) · Zbl 0856.90049 |
| [45] | Prim, R. C., Shortest connection networks and some generalizations, Bell System Technical Journal, 36, 1389-1401 (1957) |
| [46] | Sharaiha, Y. M.; Gendreau, M.; Laporte, G.; Osman, I. H., A Tabu search algorithm for the capacitated shortest spanning tree problem, Networks, 29, 161-171 (1997) · Zbl 0874.68243 |
| [47] | Shimamoto, N.; Hiramatsu, A.; Yamasaki, K., Dynamic routing control based on a genetic algorithm, Proceedings of IEEE International Conference on Neural Networks, 1123-1128 (1993) |
| [48] | Sinclair, M. C., The application of a genetic algorithm to trunk network routing table optimization, Proceedings of the Tenth UK Teletraffic Symposium, 2-6 (1993) |
| [49] | Skorin-Kapov, J., Tabu search applied to the quadratic assignment problem, ORSA Journal on Computing, 2, 33-45 (1990) · Zbl 0752.90054 |
| [50] | Skorin-Kapov, D.; Skorin-Kapov, J., On Tabu search for the location of interacting hub facilities, European Journal of Operational Research, 73, 502-509 (1994) · Zbl 0806.90075 |
| [51] | Smith, J. M.; Lee, D. T.; Liebman, J. S., An \(O(n\) log \(n)\) Heuristic for Steiner minimal tree problems on the Euclidean metric, Networks, 11, 1, 23-39 (1981) · Zbl 0459.68032 |
| [52] | Tan, T. K.; Pollard, J. K., Determination of minimum number of wavelength required for all-optical WDM networks using graph coloring, Electronic Letters, 1895-1897 (1995) |
| [53] | UEA CALMA Group, 1994. Genetic algorithms approaches to solving the radio link frequency assignment problem. Technical Report 56, University of East Anglia, Norwich; UEA CALMA Group, 1994. Genetic algorithms approaches to solving the radio link frequency assignment problem. Technical Report 56, University of East Anglia, Norwich |
| [54] | Winter, P., Steiner problem in networks: A survey, Networks, 17, 2, 129-167 (1987) · Zbl 0646.90028 |
| [55] | Winter, P.; Zachariasen, M., Euclidean Steiner minimum trees: an improved exact algorithm, Networks, 30, 3, 149-166 (1997) · Zbl 0893.90170 |
| [56] | Xu, J.; Chiu, S. Y.; Glover, F., Using Tabu search to solve the Steiner tree-star problem in telecommunication networks design, Telecommunication Systems, 6, 2, 117-127 (1996) |
| [57] | Zelikovsky, A. Z., A faster approximation algorithm for the Steiner tree problem in graph, Information Processing Letters, 46, 79-83 (1993) · Zbl 0770.68078 |
| [58] | Zhou, G.; Gen, M., A note in genetic algorithms for degree constrained spanning tree problems, Networks, 30, 2, 91-97 (1996) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
