×

zbMATH — the first resource for mathematics

A memetic algorithm for channel assignment in wireless FDMA systems. (English) Zbl 1159.90486
Summary: A new problem encoding is devised for the minimum span frequency assignment problem in wireless communications networks which is compact and general. Using the new encoding, which reduces search space dramatically over previous problem encodings, an optimization algorithm is developed which combines a genetic algorithm global search with a computationally efficient local search method from the literature. This memetic algorithm is shown to be more effective than six previous approaches in the literature on a suite of established test problems. Further, it shown that the integration of the global search with the local search is important; neither component by itself is nearly as effective.

MSC:
90C30 Nonlinear programming
90B20 Traffic problems in operations research
90B25 Reliability, availability, maintenance, inspection in operations research
Software:
CALMA; FASoft
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Wang, W.; Rushforth, C.K., An adaptive local-search algorithm for the channel-assignment problem (CAP), IEEE transactions on vehicular technology, 45, 3, 459-466, (1996)
[2] \(\langle\)http://fap.zib.de/⟩.
[3] Gamst, A., Some lower bounds for a class of frequency assignment problems, IEEE transactions on vehicular technology, 35, 8-14, (1986)
[4] Sung, C.W.; Wong, W.S., Sequential packing algorithm for channel assignment under cochannel and adjacent channel interference constraint, IEEE transactions on vehicular technology, 46, 676-685, (1997)
[5] Aardal, K.I.; van Hoesel, C.P.M.; Koster, A.M.C.A.; Mannino, C.; Sassano, A., Models and solution techniques for frequency assignment problems, 4or, 1, 261-317, (2003) · Zbl 1042.90049
[6] Allen SM, Hurley S, Smith DH, Thiel SU. Using lower bounds in minimum span frequency assignment. Meta-heuristics: advances and trends in local search paradigms for optimization. Dordrecht: Kluwer; 1999. p. 191-204.
[7] Avenali, A.; Mannino, C.; Sassano, A., Minimizing the span of d-walks to compute optimum frequency assignments, Mathematical programming, 91, 2, 357-374, (2002) · Zbl 1049.90012
[8] Beckmann, D.; Killat, U., A new strategy for the application of genetic algorithms to the channel-assignment problem, IEEE transactions on vehicular technology, 48, 4, 1261-1269, (1999)
[9] Hao, J.-K.; Dorne, R.; Galinier, P., Tabu search for frequency assignment in mobile radio networks, Journal of heuristics, 4, 47-62, (1998) · Zbl 1071.90578
[10] Hurley, S.; Smith, D.H.; Thiel, S.U., Fasoft: a system for discrete channel frequency assignment, Radio science, 32, 1921-1939, (1997)
[11] Janssen, J.; Kilakos, K., An optimal solution to the “philadelphia” channel assignment problem, IEEE transactions on vehicular technology, 48, 3, 1012-1014, (1999)
[12] Janssen, J.; Kilakos, K.; Marcotte, O., Fixed preference channel assignment for cellular telephone systems, IEEE transactions on vehicular technology, 48, 533-541, (1999)
[13] Tcha, D.; Chung, Y.; Choi, T., A new lower bound for the frequency assignment problem, IEEE/ACM transactions on networking, 5, 34-39, (1997)
[14] Song, Y.H.; Irving, M.R., Optimization techniques for electrical power systems: part 2 heuristic optimization methods, IEE power engineering journal, 15, 3, 151-160, (2001)
[15] Radcliffe NJ. Formal memetic algorithms. In: Fogarty T, editor. Evolutionary computing. Springer lecture notes in computer science, vol. 865. Berlin: Springer; 1994. p. 250-263.
[16] Sivarajan KN, McEliece RJ, Ketchum JW. Channel assignment in cellular radio. Proceedings of the IEEE vehicular technology conference, 1989. p. 846-50.
[17] Battiti, R.; Bertossi, A.; Cavallaro, D., A randomized saturation degree heuristic for channel assignment in cellular radio networks, IEEE transactions on vehicular technology, 50, 2, 364-374, (2001)
[18] Chakraborty, G., An efficient heuristic algorithm for channel assignment problem in cellular radio networks, IEEE transactions on vehicular technology, 50, 6, 1528-1539, (2001)
[19] Ghosh, S.C.; Sinha, B.P.; Das, N., Channel assignment using genetic algorithm based on geometric symmetry, IEEE transactions on vehicular technology, 52, 4, 860-875, (2003)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.