Ant Metaheuristic Algorithm for the Frequency Assignment Problem
KHALED ALRAJHI
King Khaled Military Academy, Riyadh, SAUDI ARABIA
Abstract: This study proposes the ant metaheuristic algorithm to solve the frequency assignment problem. In this approach, the descent
method constructed as three ants which each of which appling a metaheuristics algorithm. Several novel and existing techniques are
used to improve the performance of this algorithm. One of these techniques is applying the concept of a well-known graph colouring
algorithm, namely recursive largest first. Furthermore, this study compares this algorithm using two visibility definitions. The first
definition is based on the number of feasible frequencies and the second one is based on the degree. Additionally, we compare this
algorithm using two trail definitions. The first one is between requests and frequencies. The second is between requests and requests.
This study considers real and randomly generated benchmark datasets of the static problem and our algorithm achieved competitive
results comparing with other ant colony optimization algorithms in the literature.
Keywords: ant colony optimization, graph colouring algorithm, frequency assignment problem.
Received: July 7, 2022. Revised: September 5, 2023. Accepted: October 6, 2023. Published: November 6, 2023.
1 Introduction
The frequency assignment problem (FAP) is related to
wireless communication networks, which are used in
many applications such as mobile phones, TV broadcast-
ing and Wi-Fi. The aim of the FAP is to assign frequen-
cies to wireless communication connections (also known
as requests) while satisfying a set of constraints, which
are usually related to prevention of a loss of signal qual-
ity. Note that the FAP is not a single problem. Rather,
there are variants of the FAP that are encountered in prac-
tice. The minimum order FAP (MO-FAP) is the first var-
iant of the FAP that was discussed in the literature, and
was brought to the attention of researchers by [1]. In the
MO-FAP, the aim is to assign frequencies to requests in
such a way that no interference occurs, and the number
of used frequencies is minimized. As the MO-FAP is NP-
complete [2], it is usually solved by meta-heuristics.
Many meta-heuristics have been proposed to solve the
MO-FAP including genetic algorithm (GA) [3], evolu-
tionary search (ES) [4], ant colony optimization (ACO)
[5], simulated annealing (SA) [6] and tabu search (TS)
[6, 7, 8, 9]. It can be seen from literature that there are
relatively few papers concerning the application of ACO
to solve the FAP. However, existing ACO algorithms in
the literature are unable to find a feasible solution in
some instances of the MO-FAP. Hence, this study inves-
tigates whether ACO can be improved to be an effective
solution method for the MO-FAP.
In this study, Ant Metaheuristics Algorithm (AMA) is
mainly designed to solve MO-FAP. Several novel and
existing techniques are used in this study to improve the
performance of AMA. One of these techniques is apply-
ing the concept of a well-known graph colouring algo-
rithm, namely Recursive Largest First (RLF) [15]. Fur-
thermore, this study compares AMA using two visibility
definitions (see Section 3.3). The first definition is based
on the number of feasible frequencies [10]. The second
one is based on the degree [12]. Additionally, we com-
pare AMA using two trail definitions (see Section 4.2.4).
The first one is between requests and frequencies [13].
The second trail definition considered in this study is be-
tween requests and requests [12].
This paper is organised as follows: the next section
gives an overview of the MO-FAP. Section 3 presents the
main components of our AMA algorithm for the MO-
FAP. Results of this algorithm are given and discussed in
Section 4 before this study finishes with conclusions.
2 Overview of the MO-FAP
The main concept of the MO-FAP is assigning a fre-
quency to each request while satisfying a set of con-
straints and minimizing the number of used frequencies.
The MO-FAP can be defined formally as follows: given
a set of requests , where NR is the
number of requests,
a set of frequencies , where NF
is the number of frequencies,
a set of constraints related to the requests and frequencies
(described below),
the goal is to assign one frequency to each request so that
the given set of constraints are satisfied and the objective
function is minimized, where the objective function is
minimizing the number of used frequencies. Note that the
frequency that is assigned to requests is denoted
asthroughout of this study. The MO-FAP has four
variants of constraints as follows:
1. Bidirectional Constraints: this type of constraint forms
a link between each pair of requests ,
where . In these constraints, the fre-
quencies and that are assigned to
International Journal of Computational and Applied Mathematics & Computer Science
DOI: 10.37394/232028.2023.3.11
Khaled Alrajhi
E-ISSN: 2769-2477
98
Volume 3, 2023
and, respectively, should be distance apart. In
the datasets considered here, is always equal to a
constant value (238). These constraints can be written
as follows:
for
(1)
2. Interference Constraints: this type of constraint forms
a link between a pair of requests, where the pair
of frequenciesandthat is assigned to the pair
of requests and , respectively, should be more
than distance apart. These constraints can be
written as follows:
for
(2)
3. Domain Constraints: the available frequencies for
each request are denoted by the domain ,
where . Hence, the frequency which is
assigned to must belong to. For the datasets
considered in this study, there are 7 available domains.
4. Pre-assignment Constraints: for certain requests, the
frequencies have already been pre-assigned to given
values i.e. , where is given value.
3 Components of the Ant
Metaheuristics Algorithm
The components of AMA include solution space and
cost function, visibility definitions, trail definitions and
descent method.
3.1 Solution Space and Cost Function
The solution space of AMA is defined as the set
of all possible feasible assignments, that is, satisfying
all of the constraints. The corresponding cost function
is defined as the number of unassigned requests.
3.2 Request and Frequency Selection
AMA selects a frequency greedily by selecting the
one which can be assigned feasibly to the most requests.
If there is more than one candidate frequency, then one
of them is randomly selected. After that, the frequency
is sequentially feasibly assigned to all possible re-
quests until no more can be feasibly assigned. The order
of selecting requests from among those that are feasible
for is based on probability given by Formula 3.
if
0 oth-
erwise
where is the set of frequencies which can be feasi-
bly assigned by an artificial ant to the request , The vis-
ibility of a request to be assigned a frequency
is defined in Section 3.3 and the trailis defined in
Section 3.4. The parameters control the relative
significance of the pheromone trail against the visi-
bility
After that, a different frequency is selected in the same
way and this process is repeated until all requests are fea-
sibly assigned, if possible. This process is inherited from
a well-known graph colouring algorithm, namely recur-
sive largest first. In fact, applying recursive largest first
aims to improve the performance of selecting frequencies
and requests to be assigned. In contrast, ACO for the
MO-FAP in the literature (see e.g. [13]) frequently se-
lects a request based on probability and then assign it to
a feasible frequency.
3.3 Visibility Definitions
The visibility gives some indication of the desirability
of choosing a request based on the experience of previous
ants. Hence, the visibility of a request acts as a greedy
heuristic. In this study, two types of visibility definition
are applied and compared. These two visibilities are de-
fined as follows:
i) Visibility of a request to be assigned a fre-
quency is based on the number of feasible frequencies
for (), which is given by Formula 4.
(4)
This definition prioritises those requests that have
fewer feasible frequencies. This type of visibility defini-
tion was previously used in ACO for the graph colouring
problem (GCP) [10].
ii) Visibility of a request to be assigned a fre-
quency is based on the degree of (), which is
defined as the numbers of unassigned requests that can-
not be assigned feasibly toand have a common inter-
ference constraint with. This visibility is given by For-
mula 5.
(5)
This visibility looks ahead and prioritises requests that
have more constraints in common with other requests
(3)
International Journal of Computational and Applied Mathematics & Computer Science
DOI: 10.37394/232028.2023.3.11
Khaled Alrajhi
E-ISSN: 2769-2477
99
Volume 3, 2023
that cannot be assigned to the frequencies being consid-
ered currently. This visibility definition was previously
used in ACO for the GCP [12].
Example 1 clarifies the probability of selecting a re-
quest based on the two different visibility definitions.
3.4 Trail Definitions
The purpose of the trail within AMA is to provide in-
formation about previous construction solutions to influ-
ence future constructions. In this study, two different
trails are defined, where the initial values of these trails
are set to one. Moreover, evaporation and updating of
these trails are discussed. The definitions of these trails
are given as follows:
i) Trail between requests and frequencies (: the
key component of a solution is to decide to which fre-
quency each request is assigned. Therefore, the most ob-
vious trail definition is between each request and each
frequency [14]. The value of the trail indicates the quality
of previous solutions when a request is assigned to a fre-
quency.
ii) Trail between requests and requests (): pre-
vious work on the graph colouring problem (GCP) in
[12] found that a trail between nodes and nodes was more
successful than a trail between nodes and colours. This is
because the important aspect of a graph colouring solu-
tion is not in which colour each node is placed, as the
colours are interchangeable. The important aspect is
which nodes are placed together in the same colour class.
When considering the static FAP, clearly the actual fre-
quency to which each request is assigned is important.
However, given the static FAP has the same underlying
model as the GCP, we decided to investigate whether a
trail based on which requests are assigned to the same
frequencies could be advantageous.
This trail measures the success of previous solutions
when requests are assigned to the same frequency us-
ing, which is the average trail between
the prospective request and all requests already assigned
to the candidate frequency, which is defined by For-
mula 6.
(6)
where is the set of requests already assigned to fre-
quencies .
3.4.1 Trail Evaporation
Both types of trail are evaporated after each genera-
tion by multiplying the trail by the evaporation parame-
ter, which will be determined experimentally The trail
evaporation can be defined by Formula 7.
.
(7) where the evaporation parameter is in the range [0,
1).
3.4.2 Trail Updates
The trails are updated using two reward functions,
namely Cost1 and Cost2, which are defined as follows:
- Cost1: counts the number of used frequencies in
the current solution. This is appropriate when a
solution is feasible.
- Cost2: counts the number of unassigned re-
quests in the current solution. This is appropri-
ate when a solution is infeasible.
The values of could have been updated using For-
mula 8.
(8)
where is the best minimum number of used fre-
quencies found so far in the search. Note that
can be equal to 0 when
and . Thus, we add 1 to the denominator of the
last term in Formula 8. A similar trail update function
was previously used in ACO for the GCP [12].
Similarly, the values of are updated using For-
mula 9.
(9)
Another problem of trail updates is that only requests
that have been assigned to frequencies are updated.
Therefore, the trail values on any unassigned requests are
not increased, meaning such requests are likely to be se-
lected even later in the following construction processes.
As we would prefer to consider them earlier in the con-
struction process, the trail is increased on each unas-
signed request for all available frequencies. This idea
was previously used in ACO for the examination sched-
uling problem [11].
3.5 Descent Method
This method is executed only when no feasible solu-
tion can be found by all ants in a generation. In such gen-
erations, the descent method is executed only for one ant
which constructs the infeasible solution with the mini-
mum number of unassigned requests. First, these re-
quests are assigned to the frequencies which lead to the
least number of violations. Then, the descent method
aims to reduce the number of violations with a fixed
number of frequencies to find a feasible solution, if pos-
sible, by going three ants:
Ant 1: applying local search [6]
Ant 2: applying evolutionary search [4]
Ant 3: applying tabu search [8]
3.6 The AMA Algorithm Implementation
AMA consists of a given number of generations, each
of which contains a given number of ants, where each ant
individually constructs a solution. Each ant starts con-
International Journal of Computational and Applied Mathematics & Computer Science
DOI: 10.37394/232028.2023.3.11
Khaled Alrajhi
E-ISSN: 2769-2477
100
Volume 3, 2023
structing a solution by selecting a frequency to be as-
signed to all possible feasible requests. The process is re-
peated until no frequencies can be selected (see Section
3.2). After all ants in the current generation construct
their solutions, if no feasible solution can be found, then
the descent method (see Section 3.5) is used to attempt
to achieve a feasible solution. Then, the trail is evapo-
rated and updated (see Section 3.4.1 and 3.4.2). After
that, the next generation is executed by the same process.
The overall structure of the AMA algorithm is illustrated
in Figure 1.
Fig. 1. Overall structure of our ACO algorithm for the MO-FAP.
N
Y
N
Y
N
Y
Y
es
Initialize the pheromone trail and parameters
Set number of generations = 0
Stop
Return the best solution
number of generations = number of generations + 1
Set number of ants = 0
Is the number of gen-
erations > a given num-
ber?
number of ants = number of ants + 1
Is the number of
ants > a given number?
Choose a request (Section 3.2)
N
Y
es
N
Choose a frequency (Section 3.2)
Can a request
be chosen?
Can a feasible
solution be found?
Descent method (Section 3.5)
Can a frequency be
chosen?
Assign the chosen frequency to the
chosen request
Trail evaporation (Section 3.4.1)
Trail updates (Section 3.4.2)
International Journal of Computational and Applied Mathematics & Computer Science
DOI: 10.37394/232028.2023.3.11
Khaled Alrajhi
E-ISSN: 2769-2477
101
Volume 3, 2023
4 Experiments and Results
This section presents and compared the performance
of AMA in three sections. The first section gives the re-
sults of AMA for the static FAP. The second section
compares the performance of AMA with existing ACO
algorithms in the literature. Finally, the performance of
AMA is compared with other algorithms in the literature.
AMA is implemented in FORTRAN 95 and all exper-
iments were conducted on a 3.0 GHz Intel Core I3-2120
Processor (2nd Generation) with 8GB RAM and a 1TB
Hard Drive.
4.1 Results Comparison of the AMA
In this study, the number of generation of AMA is
200, where this number is selected based on experiments.
Moreover, the performance of ACO is compared based
on several options of the following components:
1. The number of ants,
2. The trail definition,
3. The visibility definition,
4. The parameters
Different values of the number of ants, two options of
the trail definition and two options for visibility defini-
tion are compared. For the parametersand, three
values of each parameter are tested. By considering all
these options, there are 756 versions of AMA to be com-
pared. Moreover, each version is tested on 10 instances
with 5 runs being performed on each instance. Therefore,
considering all the versions of AMA take excessive time.
Hence, the comparison is made for each component
while fixing the others; i.e. first, different numbers of
ants are compared while fixing the remaining compo-
nents. After selecting the best number of ants, the two
different trail definitions are compared. After that, two
definitions of the visibility are compared and finally, dif-
ferent values of the parameters (and) are compared
in the same way. Based on experiments, the best values
of the parameters and number of ants given in Table 3.
Table 3. The best values of the parameters and number of ants
based on experiments.
4
3
0.85
30
Moreover, the performance of AMA using is
better than using . The performance of AMA using
the two types of trail definitions. It is found by the
Wilcoxon signed-rank test at the 0.05 significance level
that there is a significant difference between the perfor-
mances of ACO using and. Moreover, the
performance of AMA using the first definition of visibil-
ity better than the second one.
4.2 Results Comparison with Existing ACO
Algorithms
The performance of our AMA is compared with existing
ACO in the literature. To the best of my knowledge, only
one published research [13] applied ACO for the MO-
FAP using CELAR and GRAPH datasets. Table 4 shows
the results in the form given in [13], i.e. in the form of
(y) where y is the number of violations. Note that y is
equal to 0 means a feasible solution is found.
Table 4. Results of AMA and existing ACO algorithm in the litera-
ture.
Instance
ACO [13]
Our AMA
CELAR 01
(0)
(0)
CELAR 02
(0)
(0)
CELAR 03
(0)
(0)
CELAR 04
(8)
(0)
CELAR 11
(2)
(2)
GRAPH 01
(0)
(0)
GRAPH 02
(0)
(0)
GRAPH 08
(0)
(0)
GRAPH 09
(0)
(0)
GRAPH 14
(0)
(0)
Table 4 shows that both of the algorithms struggled to
find a feasible solution for CELAR 11. Moreover, ACO
in [13] could not achieve a feasible solution for CELAR
04, whereas our AMA could. Overall, our AMA algo-
rithms performing better than AMA in [13].
5 Conclusions
In this study, an improved AMA was introduced to
solve the MO-FAP by using different techniques. One of
the techniques which was applied to improve the perfor-
mance of AMA is improve the descent method by apply-
ing local search [6], evolutionary search [4] and tabu
search [8]. This will be applied only when no feasible
solution can be found in a generation. In such genera-
tions, the descent method is executed for only one ant
which constructs the infeasible solution with the mini-
mum number of unassigned requests. Moreover, apply-
ing the recursive largest first. Also, AMA was compared
using two trail definitions and two visibility definitions.
It was found that using the trail between requests and fre-
quencies led to better performance than the other trail
definition. Moreover, using the visibility definition based
on the number of feasible frequencies resulted in better
performance than another visibility definition. Further-
more, several values for the parameters were
compared and the best values are 4, 3 and 0.85, respec-
tively. Overall, our AMA performed better than ACO in
the literature.
International Journal of Computational and Applied Mathematics & Computer Science
DOI: 10.37394/232028.2023.3.11
Khaled Alrajhi
E-ISSN: 2769-2477
102
Volume 3, 2023
References
[1]. Metzger, B. (1970), Spectrum Management
Tech-nique, Presentation at 38th National
ORSA meeting (Detroit, MI).
[2]. Garey, M. and Johnson, D. (1979), Computers
and Intractability: A Guide to the Theory of NP-
Completeness, Freeman W.H. and Company,
San Francisco, California.
[3]. Kapsalis, A., Chardaire, P., Rayward-Smith, V.
and Smith, G. (1995), The Radio Link
Frequency As-signment Problem: A Case
Study Using Genetic Al-gorithms, Lecture
Notes on Computer Science, pp. 117-131.
[4]. Crisan, C. and Mühenbein, H. (1998), The
Frequen-cy Assignment Problem: A Look at the
Perfor-mance of Evolutionary Search, Lecture
Notes in Computer Science, Vol. 1363, pp. 263-
274.
[5]. Parsapoor, M. and Bilstrup, U. (2013), Ant
Colony Optimization for Channel Assignment
Problem in a Clustered Mobile Ad Hoc
Network, International Conference on Swarm
Intelligence (ICSI), Vol. 1, pp. 314-322.
[6]. Tiourine, S., Hurkens, C. and Lenstra, J. K.
(1999), Local Search Algorithm for the Radio
Link Fre-quency Assignment Problem,
Telecommunication System, Vol. 13, pp. 293-
314.
[7]. Bouju, A., Boyce, J., Dimitropoulos, C., Vom
Scheidt, G. and Taylor, J. (1995), Tabu Search
for the Radio Links Frequency Assignment
Problem, In Applied Decision Technologies,
London, [ADT'95]. UNICOM Conference.
[8]. Hao, J., Dorne, R. and Galinier, P. (1998),
Tabu Search for Frequency Assignment in
Mobile Radio Networks, Journal of Heuristics
Vol. 4, pp. 47-62.
[9]. Bouju, A., Boyce, J., Dimitropoulos, C., Vom
Scheidt, G. and Taylor, J. (1995), Intelligent
Search for the Radio Links Frequency
Assignment Prob-lem, Proceedings of the
International Conference on Digital Signal
Processing.
[10]. Costa, D. and Hertz, A., 1997. Ants can
colour graphs. Journal of the Operational
Research Socie-ty, 48(3), pp.295-305.
[11]. Dowsland, K.A. and Thompson, J.M.,
2005. Ant col-ony optimization for the
examination scheduling problem. Journal of the
Operational Research Soci-ety, pp.426-438.
[12]. Dowsland, K.A. and Thompson, J.M.,
2008. An im-proved ant colony optimisation
heuristic for graph colouring. Discrete Applied
Mathematics, 156(3), pp.313-324.
[13]. Maniezzo, V. and Carbonaro, A., 2000. An
ANTS heuristic for the frequency assignment
problem. Fu-ture Generation Computer
Systems, 16(8), pp.927-935.
[14]. Parsapoor, M. and Bilstrup, U., 2013. Ant
colony op-timization for channel assignment
problem in a clus-tered mobile ad hoc network.
In Advances in Swarm Intelligence, pp. 314-
322. Springer Berlin Heidelberg.
[15]. Leighton, F.T., 1979. A graph coloring
algorithm for large scheduling problems.
Journal of Research of the National Bureau of
Standards, 84(6), pp.489-506.
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
The author contributed in the present research, at all
stages from the formulation of the problem to the
final findings and solution.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
No funding was received for conducting this study.
Conflict of Interest
The author has no conflict of interest to declare that
is relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
International Journal of Computational and Applied Mathematics & Computer Science
DOI: 10.37394/232028.2023.3.11
Khaled Alrajhi
E-ISSN: 2769-2477
103
Volume 3, 2023
