Computational Intelligence - February 2017 - 34

6) Adjacent cells not sharing a boundary crossing should be
assigned to different TAs.
If m ij = 0 and y ij = 1,
then / l ih l jh = 0,

(9)

where m ij is the traffic flow between cell i and cell j. It is worth
noting that rationality of this constraint is based on the assumption that each cell has at least one road connected to other cells.
IV. An EMO Algorithm Based on the M2M
Decomposition for the Multi-objective
TA Planning Model
A. Encoding Method

When applying an EMO algorithm to the proposed model, we
first need to properly encode the solutions (TA configurations).
The encoding scheme (or representation) is an important
aspect of an EMO algorithm, especially for a discrete optimization problem. The crossover, mutation and selection of the
individuals are realized in terms of representations. In this
paper, a new encoding scheme inspired by the four-color theorem is designed to encode and decode the solutions. In mathe-

Cell Number 1
Code

Figure 3 An example of the representation.

11
16

18
22

19
23

1
6

20
24

7
11

16
25

8
12

17
21

Before Merging

9
13

18
22

10
14

19
23

20
24

After Merging

2
7

11
16

8
12

17
21

3
9
13
18

5
10

14
19

Before Splitting

15
20

16
25

7
11
17

8
12

18
22

9
13

10
14

15
20

19
23

After Splitting

Figure 5 Illustration of the splitting process.

B. Decoding Method

To support the consideration of the trade-off between location
update cost and paging cost in the multi-objective TA planning
model, a two-step decoding method is designed to decode the
representations. First, the cells are roughly grouped according
to their codes. To be specific, cells with the same code are
assigned into the same TA without considering any other constraints. This step is called merging, which tends to merge several small TAs into a big one. The second step is splitting. In this
step, we check for situations in which TAs contain cells that are
separated from others. If there are any, the group should be
split. This process will continue until this situation no longer
exists. As we can see, the first step tends to increase the size of a
TA, while the second step tends to decrease the size of a TA.
An example of merging and splitting is shown in Figs. 4 and 5
respectively. In Fig. 4, cell 5, 10, 14, 15 and cell 19, 20, 24 do
not belong to the same TA at first and are marked by two
different colors, but after crossover and mutation they have the
same code and are merged to form a bigger TA marked by the
same color. In Fig. 5, cell 6, 7, 11, 16 and cell 20, 24, 25 are
assigned into the same TA by the first step of decoding, but
there are two separated parts in this TA. Therefore, the splitting
process is conducted and the TA is divided into two TAs
marked by two different colors.
C. Initialization Based on Fuzzy Clustering

Figure 4 Illustration of the merging process.

matics, the four-color theorem can be stated as: no more than
four colors are needed to color all the regions of the plane so
that no two adjacent regions have the same color for any given
contiguous regions [33]. According to this theorem, a fixed
length representation vector, which is encoded by only four
numbers {1, 2, 3, 4}, with a size equal to the number of cells in
the network, are used to encode the solutions. The ith code in
the representation represents the ith cell in the network. Cells
with the same code should be grouped together when decoding the representations. Fig. 3 gives an example of the representation for a network with ten cells.
This representation corresponds to a rough TA configuration in an LTE network without considering any constraints. It
means that cells 1, 2, 10, cells 3, 5, 7, cells 4, 6, and cells 8, 9
should be grouped respectively, to form four different TAs.

IEEE ComputatIonal IntEllIgEnCE magazInE | FEbruary 2017

The initialization of an EMO algorithm plays an important
role in finding the optimal solutions effectively. This paper integrates fuzzy clustering into the initialization process. The fuzzy
clustering algorithm is very simple and easy to implement [36].
First, the fuzzy similarity matrix is defined; second, the fuzzy
equivalence matrix is calculated; and finally, a threshold for the
fuzzy equivalence matrix is set to get the partition. In fuzzy
clustering, the similarity matrix is used to measure the similarity of different terms. The more similar two terms are, the more
likely they are to be assigned to the same cluster. In this paper,
we try to assign cells with large traffic flows between them into
the same TA. Therefore, it is reasonable to use the traffic flow as
the measure of 'similarity' among cells. The element rij of the

Table of Contents for the Digital Edition of Computational Intelligence - February 2017