Hybrid Evolutionary Approaches to Terminal Assignment in Communications Networks

X. YAO, F. WANG, K. PADMANABHAN, S. SALCEDO-SANZ

Research output: Book Chapters | Papers in Conference ProceedingsBook ChapterResearchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationRecent Advances in Memetic Algorithms
EditorsWilliam E. HART, J. E. SMITH, N. KRASNOGOR
PublisherSpringer-Verlag Italia Srl
Chapter7
Pages129-159
Number of pages31
ISBN (Electronic)9783540323631
ISBN (Print)9783540229049
DOIs
Publication statusPublished - 2005
Externally publishedYes

Publication series

NameStudies in Fuzziness and Soft Computing
PublisherSpringer, Berlin
Volume166
ISSN (Print)1434-9922
ISSN (Electronic)1860-0808

Keywords

  • Local Search
  • Multiobjective Optimisation
  • Search Operator
  • Uniform Crossover
  • Baldwin Effect

Fingerprint

Dive into the research topics of 'Hybrid Evolutionary Approaches to Terminal Assignment in Communications Networks'. Together they form a unique fingerprint.

Cite this