Article Preview
TopIntroduction
Wireless communication networks, which employ radio frequencies to establish communication links, have undergone a dramatic expansion over the past two decades. Since the available radio spectrum is very limited, to meet the demand of today’s radio communication, this resource has to be administered and reused carefully in order to control mutual interference. Thus, given the continuing rapid growth in demand for wireless services, frequency assignment problems (FAPs) play a key role in the planning of such networks (Galinier, Gendreau, Soriano, & Bisaillon, 2005), which are concerned with the assignment of discrete channels to the transmitters of a radio network. FAPs are difficult in terms of complexity theory. Deciding whether a mobile network allows a feasible assignment is NP-complete, and the corresponding optimization problems are strongly NP-hard (Martin, 2000).
There has been a considerable research effort for solving FAPs. Valenzuela et al. (1998) proposed a permutation based genetic algorithm for solving minimum span FAPs (MSFAPs). Won-Young et al. (2006) proposed a heuristic method, namely frequency insertion strategy (FIS), which starts with a narrow enough frequency bands so as to provoke violations of constraints and then resolve the violations by inserting frequencies. Several neural network algorithms have been also proposed for FAPs. For example, Kunz (1993) used Hopfield neural network and obtained optimal solutions for some special instances of MSFAPs Idoumghar et al. (2009) proposed two distributed algorithms for the FAP in the field of radio braodcasing.
In FAPs, separation of the frequencies assigned to the transmitters is necessary to avoid the interference. However, unnecessary separation causes an excess requirement of spectrum, the cost of which may be very high. From this viewpoint, FAPs are closely related to T-coloring problems (TCPs) where the vertices of a graph represent the transmitters and adjacencies indicate possible interferences (Riihijärvi, Petrova, & Mähönen, 2005; Hurley & Smith, 1997; Bodlaender, Kloks, Tan, & van Leeuwen, 2000). TCPs are a generalized version of classical graph coloring problems (GCPs), which are one of the most studied NP-hard problems and can be defined informally as follows (Costa, 1993): Given an undirected graph, one wishes to color the vertices of the graph with a minimum number of colors in such a way that two colors assigned to any two adjacent vertices must be different. That is to say, they must have a minimum distance greater than zero. These classical GCPs are just a special case of TCPs. Unfortunately, due to the difficulty and complexity of TCPs, there has rather few researches on this problem. Some classical methods were proposed several years ago, such as tabu search (Dorne & Hao, 1998) and Dsatur (Janczewski & Kubale, 1998). Until now, there is no benchmark available for evaluating and comparing different algorithms for TCPs.
To solve TCPs, optimizing algorithms with strong searching ability are required. In our previous work, based on multiagent systems, a new numerical optimization algorithm, multiagent genetic algorithm (MAGA), has been proposed in Zhong, Liu, Xue, and Jiao (2004) to handle large-scale global numerical optimization problems. The experimental results shown that MAGA can solve numerical optimization problems with 1000 dimensions. The method was also extended to handle constraint satisfaction problems (Liu, Zhong, & Jiao, 2006) and combinatorial optimization problems (Liu, Zhong, & Jiao, 2010), which illustrated the potential of the combination of multiagent systems and evolutionary algorithms in solving complex problems. Thus, on the basis of TCPs, we extended MAGA to solve minimum span FAPs, which is labeled as MAEA-MSFAPs. In experiments, TCP with different sizes and Philadelphia benchmark for FAPs are used to validate the performance of MAEA-MSFAPs.