×

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems. (English) Zbl 1271.90015

Summary: This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.

MSC:

90B06 Transportation, logistics and supply chain management
90B18 Communication networks in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

SMS-EMOA; HypE; MOEA/D
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bader, J., & Zitzler, E. (2011). HypE: an algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation, 19(1), 45–76. · Zbl 05890633
[2] Betsekas, D., & Gallager, R. (1992). Data networks (2nd ed.). Englewood Cliffs: Prentice-Hall.
[3] Beume, N., Naujoks, B., & Emmerich, M. (2007). SMS-EMOA: multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653–1669. · Zbl 1123.90064
[4] Chen, S., & Nahrestedt, K. (1998). An overview of quality of service routing for next-generation high-speed networks: problems and solutions. IEEE Network Magazine, 12(6), 64–79. Special issue on transmission and distribution of digital video.
[5] Cui, X., Lin, C., & Wei, Y. (2003). A multiobjective model for QoS multicast routing based on genetic algorithm. In Proceedings of 2003 international conference on computer networks and mobile computing (ICCNMC’03) (pp. 49–53).
[6] Crichigno, J., & Baran, B. (2004a). Multiobjective multicast routing algorithm for traffic engineering. In Proceedings of the 13th international conference on computer communications and networks (pp. 301–306). Heidelberg: Springer.
[7] Crichigno, J., & Baran, B. (2004b). Multiobjective multicast routing algorithm. In Lecture notes in computer science (Vol. 3124, pp. 1029–1034).
[8] Czyzzak, P., & Jaszkiewicz, A. (1998). Pareto simulated annealing–a meta-heuristic technique for multiobjective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–37. · Zbl 0904.90146
[9] Diot, C., Dabbous, W., & Crowcroft, J. (1997). Multipoint communication: a survey of protocols, functions, and mechanisms. IEEE Journal on Selected Areas in Communications, 15, 277–290.
[10] Diego, P., & Baran, B. (2005). Solving multiobjective MRP with a new ant colony optimization approach. In Proceedings of the 3rd international IFIP/ACM Latin American conference on networking, Columbia (pp. 11–19).
[11] Deb, K. (2005). Multi-objective optimisation. In E. K. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimisation and decision support methodologies (pp. 273–316). Berlin: Springer.
[12] Eppstein, D. (1998). Finding the k shortest paths. SIAM Journal on Computing, 28, 652–673. · Zbl 0912.05057
[13] Ehrgott, M., & Gandibleux, X. (2000). A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum, 22, 425–460. · Zbl 1017.90096
[14] Fabregat, R., Donoso, Y., Baran, B., Solano, F., & Marzo, J. L. (2005). Multi-objective optimization scheme for multicast flows: a survey, a model and a MOEA solution. In Proceedings of the 3rd international IFIP/ACM Latin American conference on networking (LANC’05). New York: ACM.
[15] Goldberg, D. (1989). Genetic algorithm in search, optimization & machine learning. Reading: Addison-Wesley. · Zbl 0721.68056
[16] Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman. · Zbl 0411.68039
[17] Haghighat, A. T., Faez, K., Dehghan, M., Mowlaei, A., & Ghahremani, Y. (2004). GA-based heuristic algorithms for bandwidth-delay-constrained least-cost multicast routing. Computer Communications, 27, 111–127. · Zbl 05396496
[18] Huang, J., & Liu, Y. (2010). MOEAQ: a QoS-aware multicast routing algorithm for MANET. Expert Systems with Applications, 37, 1391–1399. · Zbl 05884151
[19] Hwang, F. K., & Richards, D. S. (1992). Steiner tree problems. Networks, 22, 55–89. · Zbl 0749.90082
[20] Ishibuchi, H., & Murata, T. (1998). A Multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Systems, Man and Cybernetics. Part C, Applications and Reviews, 28(3), 392–403.
[21] Ishibuchi, H., Hitotsuyanagi, Y., Wakamatsu, Y., & Nojima, Y. (2010). How to choose solutions for local search in multiobjective combinatorial memetic algorithms. In Proc. of 11th international conference on parallel problem solving from nature (pp. 516–525).
[22] Ishibuchi, H., Akedo, N., Ohyanagi, H., & Nojima, Y. (2011). Behavior of EMO algorithms on many-objective optimization problems with correlated objectives. In Proc. of 2011 IEEE congress on evolutionary computation, New Orleans, USA, June 5–8, 2011 (pp. 1465–1472).
[23] Jaszkiewicz, A. (2002). Genetic local search for multi-objective combinatorial optimization. European Journal of Operational Research, 137, 50–71. · Zbl 1002.90051
[24] Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. · Zbl 1225.90162
[25] Kompella, V. P., Pasquale, J. C., & Polyzos, G. C. (1993). Multicast routing for multimedia communication. IEEE/ACM Transactions on Networking, 1(3), 286–292.
[26] Koyama, A., Barolli, L., Matsumoto, K., & Apduhan, B. O. (2004). A GA-based multi-purpose optimization algorithm for QoS routing. In Proceedings of the 18th international conference on advanced information networking and applications (AINA 2004) (Vol. 1(1), pp. 23–28).
[27] Kun, Z., Heng, W., & Feng-Yu, L. (2005). Distributed multicast routing for delay variation-bounded Steiner tree using simulated annealing. Computer Communications, 28, 1356–1370. · Zbl 05396709
[28] Landa-Silva, J. D., Burke, E. K., & Petrovic, S. (2004). An introduction to multiobjective metaheuristics for scheduling and timetabling. In X. Gandibleux, M. Sevaux, K. Sorensen, & V. T’kindt (Eds.), Lecture notes in economics and mathematical systems: Vol. 535. Metaheuristic for multiobjective optimisation (pp. 91–129). Berlin: Springer. · Zbl 1139.90420
[29] Li, C., Cao, C., Li, Y., & Yu, Y. (2007). Hybrid of genetic algorithm and particle swarm optimization for multicast QoS routing. In IEEE international conference on control and automation, Guangzhou, China.
[30] Li, H., & Landa-Silva, J. D. (2008). Evolutionary multi-objective simulated annealing with adaptive and competitive search direction. In Proceedings of the 2008 IEEE congress on evolutionary computation (CEC 2008) (pp. 3310–3317). Hong Kong: IEEE Press.
[31] Li, H., & Zhang, Q. (2009). Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Transactions on Evolutionary Computation, 13(2), 284–302.
[32] Martins, F., & Costa, C. A. V. (2010). Multiobjective optimization with economic and environmental objective functions using modified simulated annealing. Computer-Aided Chemical Engineering, 28, 919–924.
[33] Mendoza, J. E., Castanier, B., Guéret, C., Medaglia, A. L., & Velasco, N. (2010). A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Computers & Operations Research, 37(11), 1886–1898. · Zbl 1188.90035
[34] Miettinen, K. (1999). Nonlinear multiobjective optimization. Boston: Kluwer Academic. · Zbl 0949.90082
[35] Oliveira, C. A. S., & Pardalos, P. M. (2005). A Survey of combinatorial optimization problems in multicast routing. Computers & Operations Research, 32(8), 1953–1981. · Zbl 1068.90027
[36] Qu, R., Xu, Y., & Kendall, G. (2009). A variable descent search algorithm for delay-constrained least-cost multicast routing. In Lecture notes in computer science (Vol. 5851, pp. 15–29).
[37] Rai, S. C., Misra, B. B., Nayak, A. K., Mall, R., & Pradhan, S. K. (2010). A multi-objective QoS optimization with fuzzy based parameter setting for real time multicasting. International Journal of Communications, Network and System Sciences, 3, 530–539.
[38] Roy, A., & Das, S. K. (2004). QM2RP: a QoS-based mobile multicast routing protocol using multi-objective genetic algorithm. Wireless Networks, 10(3), 271–286.
[39] Roy, A., Banerjee, N., & Das, S. K. (2002). An efficient multi-objective QoS-routing algorithm for wireless-multicasting. In IEEE 55th vehicular technology conference (pp. 1160–1164).
[40] Salama, H. F., Reeves, D. S., & Viniotis, Y. (1997). Evaluation of multicast routing algorithms for real-time communication on high-speed networks. IEEE Journal on Selected Areas in Communications, 15, 332–345.
[41] Skorin-Kapov, N., & Kos, M. (2003). The application of Steiner trees to delay constrained multicast routing: a tabu search approach. In Proceedings of the seventh international conference on telecommunications, Zagreb, Croatia.
[42] Skorin-Kapov, N., & Kos, M. (2006). A GRASP heuristic for the delay-constrained MRP. Telecommunications Systems, 32(1), 55–69. · Zbl 05075827
[43] Srinivas, N., & Deb, K. (1994). Multiobjective optimization using non-dominated sorting in genetic algorithms. Evolutionary Computation, 2(3), 221–248. · Zbl 05412883
[44] Wang, J. Q., Qin, J., & Kang, L. S. (2006). A new QoS mutlicast routing model and its immune optimization algorithm. In J. Ma et al. (Eds.), Lecture notes in computer science: Vol. 4159. Ubiquitous intelligence and computing (pp. 369–378).
[45] Waxman, B. M. (1988). Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 6, 1617–1622.
[46] Xu, Y., & Qu, R. (2011). Solving multi-objective multicast routing problems by evolutionary multi-objective simulated annealing algorithms with variable neighbourhoods. Journal of the Operational Research Society, 62, 313–325.
[47] Xu, Y., & Qu, R. (2012). An iterative local search approach based on fitness landscapes analysis for the delay-constrained multicast routing problem. Computer Communications, 35, 352–365.
[48] Yeo, C. K., Lee, B. S., & Er, M. H. (2004). A survey of application level multicast techniques. Computer Communications, 27(15), 1547–1568. · Zbl 05397437
[49] Zahrani, M. S., Loomes, M. J., Malcolm, J. A., Dayem Ullah, A. Z. M., Steinhofel, K., & Albrecht, A. A. (2008). Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing. Computers & Operations Research, 35, 2049–2070. · Zbl 1139.90035
[50] Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithms: a comprehensive case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 3(4), 257–271. · Zbl 05452215
[51] Zhang, Q., & Li, H. (2007). MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712–731. · Zbl 05516207
[52] Zhang, L., Cai, L. B., Li, M., & Wang, F. H. (2009). A method for least-cost QoS multicast routing based on genetic simulated annealing algorithm. Computer Communications, 32, 105–110. · Zbl 05745795
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.