Summary
Terminal assignment is an NP-hard problem in communications networks. It involves assigning a set of terminals to a set of concentrators with a cost for each assignment. The objective is to minimize the total cost of the assignment and the number of concentrators used. A number of heuristic algorithms, including genetic algorithms, have been proposed for solving this problem. This chapter studies several evolutionary and hybrid approaches to terminal assignment. Firstly, a novel chromosome representation scheme based on concentrators is proposed. This representation compares favourably against the existing terminal-based representation, which scales poorly for large problems. Extensive experiments have been carried out. The results show that our evolutionary algorithms using the concentrator-based representation outperform significantly existing genetic algorithms using the terminal-based representation. Secondly, a number of new search operators used in our algorithms are also investigated empirically in order to evaluate their effectiveness for the terminal assignment problem. Finally, different combinations of evolutionary algorithms and local search are studied in this chapter. Both Lamarckian evolution and Baldwin effect have been examined in combining an evolutionary algorithm and local search. Our results show that hybrid algorithms perform better than either evolutionary algorithms or local search. However, there is no significant difference between Lamarckian-evolution-style combination and Baldwin-effect-style combination.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abuali, F., Schoenefeld, D. and Wainwright, R. (1994). Terminal assignment in a Communications Network Using Genetic Algorithms. Proceedings of the 22nd Annual ACM Computer Science Conference, pages 74–81. ACM Press.
Aggarwal, K.K., Chopra, Y.C. and Bajwa, J.S. (1982). Reliability evaluation by network decomposition. IEEE Transactions on Reliability, R-31:355–358.
Atiqullah, M.M. and Rao, S.S. (1993). Reliability optimization of communication networks using simulated annealing. Microelectronics and Reliability, 33:1303–1319.
Falkenauer, E. (1996). A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2(l):5–30.
Fleming, P.J. (1985). Computer aided control systems using a multi-objective optimization approach. Proceedings of IEE Control’85 Conference, pages 174–179.
Fonseca, C.M. and Flemming, P.J. (2000). Multiobjective optimisation. In Back, T., Fogel, D.B. and Michalewicz, Z., editors, Evolutionary computation, volume 2, pages 25–27. Institute of Physics Publishing, Bristol.
Glover, F., Lee, M. and Ryan, J. (1991). Least-cost network topology design for a new service: and application of a tabu search. Annals of Operations Research, 33:351–362.
Hinton, G.E. and Nolan, S.J. (1987). How learning can guide evolution. Complex Systems, 1:495–502.
Jin, Y., Olhofer, M. and Sendhoff, B. (2001). Dynamic Weighted Aggregation for Evolutionary Multi-Objective Optimization: Why Does It Work and How? Proceedings of the Genetic and Evolutionary Computation Conference GECCO, pages 1042–1049. Morgan Kaufmann.
Joines, A.J. and Kay, M.G. (2002). Utilizing Hybrid Genetic Algorithms. In Sarker, R., Mohammadian, M and Yao, X., editors, Evolutionary Optimisation. Kluwer Academic Publishers. pp.199–228.
Kershenbhaum, A. (1993). Telecommunications Network Design Algorithms. McGraw-Hill.
Khuri, S. and Chiu, T. (1997). Heuristic Algorithms for the Terminal Assignment Problem. Proceedings of the 1997 ACM Symposium on Applied Computing, pages 247–251. ACM Press.
Koh, S.J. and Lee, C.Y. (1995). A tabu search for the survivable fiber optic communication network design. Computers and Industrial Engineering, 28:689–700.
Kumar, A., Pathak, R.M., Gupta, Y.P. and Parsaei, H.R. (1995). A genetic algorithm for distributed system topology design. Computers and Industrial Engineering, 28:659–670.
Pierre, S., Hyppolite, M.A., Bourjolly, J.M. and Dioume, O. (1995). Topological design of computer communication networks using simulated annealing. Engineering Applications of Artificial Intelligence, 8:61–69.
Whitley, D., Gordon, V.S. and Mathias, K. (1994). Lamarckian evolution, the Baldwin effect and function optimization. In Davidor, Y., Schwefel, H.-P. and Mnner R., editors, Lecture Notes in Computer Science, 866:6–15, Springer-Verlag.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Yao, X., Wang, F., Padmanabhan, K., Salcedo-Sanz, S. (2005). Hybrid Evolutionary Approaches to Terminal Assignment in Communications Networks. In: Hart, W.E., Smith, J.E., Krasnogor, N. (eds) Recent Advances in Memetic Algorithms. Studies in Fuzziness and Soft Computing, vol 166. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-32363-5_7
Download citation
DOI: https://doi.org/10.1007/3-540-32363-5_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22904-9
Online ISBN: 978-3-540-32363-1
eBook Packages: EngineeringEngineering (R0)