Computational Intelligence - May 2014 - 62

Conf(v)

0 1 1

2 1 1

0 1 0 1

Parent 1

v0 v4 v6

v2 v7 v8

v9 v1 v5 v3

Conf(v)

2 2 2

3 1 1 1

1 1 0

Parent 2

v3 v6 v4 v2 v7 v8v5 v0 v1 v9

Conf(v)

0 1 1

1 1

0

Parent 1

v0 v4 v6 v2 v8

v3

Conf(v)

2 2 2

0

Parent 2

v3 v6 v4 v2 v8

Conf(v)

0
v6

0
v8

1 1
v3 v6

0
v8

Parent 1
Conf(v)
Parent 2

1 1

Conf(v)

Conf(v)

Conf(v) 0 0 0 0
Offspring v9 v1 v5 v7

Conf(v) 0 0 0 0 0 0 0
Offspring v9 v1 v5 v7 v0 v4 v2

v0
0
v3
Conf(v) 0 0 0 0 0 0 0
Offspring v9 v1 v5 v7 v0 v4 v2

0
v6

Parent 1

conflict in resource class R i,
move v j into another resource
class, then a neighbor chromosome is obtained. Based on the
fitness of an individual calculated by (4), the neighbor
chromosome is better than the
offspring if its fitness is less
than that of the offspring. The
procedure of the local search is
described as follows.
Step 1: Select a node to
move. The spill factor introduced
by Topcuoglu et al. in [16] is
used here,

Conf(v) 0 0 0 0 0 0 0
Offspring v9 v1 v5 v7 v0 v4 v2

Parent 2

0
v6

Conf(v)

0 1 1

2 1 1

0 1 0 1

Parent 1

v0 v4 v6

v2 v7 v8

v9 v1 v5 v3

Conf(v)

2 2 2

3 1 1 1

1 1 0

Parent 2

v3 v6 v4 v2 v7 v8v5 v0 v1 v9

0 0
v8 v3

0 0
v8 v3

v6

(a)

Conf(v)

0

0 0

0 1 0 1

Parent 1

v6

v7 v8

v9 v1 v5 v3

Conf(v)
Parent 2

1

0 0 0

0 0

v3 v6

v7 v8 v5

v1 v9

1

Conf(v)

0

0

0

Parent 1

v6

v8

v3

Conf(v)
Parent 2

1

1

0

v3 v6

v8

Conf(v)

0

Parent 1

v3

Conf(v)

0

Parent 2

v3

Conf(v) 0 0 0
Offspring v0 v4 v2

Conf(v) 0 0 0
Offspring v0 v4 v2

0 0 0 0
v9 v1v5 v7

Conf(v) 0 0 0
Offspring v0 v4 v2

0 0 0 0

0

0

v9 v1 v5 v7 v6 v8

Then, the node with the maximum spill factor is selected to
move.
Step 2: Select a target
resource class for the selected
node v j ! R m . For i = 1, f, k,
compute the difference between
Fitness v j ! Ri (R i) and Fitness v j g Ri
(R i), where Fitness v j ! Ri (R i) is
the fitness of R i when v j is
added into R i and Fitness v j g Ri
(R i) is the fitness of R i when v j
is removed from R i .
- Fitness v j z Ri (R i),
i = 1, f, k.
(9)
Then select the target resource
class R n, which satisfies

Conf(v) 0 0 0
Offspring v0 v4 v2

0 0 0 0

0

0

v9 v1 v5 v7 v6 v8
v3

Figure 3 Comparison of the CFPX and COPX on the interference graph shown in Fig. 2, where
is the number of conflicts of each node in its resource class. (a) CFPX. (b) COPX.

62

(8)

9Fitness (R i) = Fitness v j ! Ri (R i)

(b)

variables, but the COPX aims at reducing the total cost of the spilled variables.
It is observed that the COMA may produce smaller number of spilled variables
(see Table 1 in Section III) due to the
decoding scheme in the COMA.

S_Factor (v j) = Cost (v j),
# Conf (v j)
v j ! V.

C. Local Search

After an offspring is generated by the
COPX from two parents, a local
search technique is usually applied to
find a better chromosome in the space
near the offspring [44]. If node v j is in

IEEE ComputatIonal IntEllIgEnCE magazInE | may 2014

9Fitness (R n) =
min (9Fitness (R i)) .
i =1, g, k
(10)

Node v j is moved from R m to
R n if n ! m.
Step 3: Repeat steps 1 and 2
Conf ^v h
until no node can be moved
by (10).
After several repetitions, the selected
target resource class for the selected
node v j ! R m will be R m itself. Until
then, no node can be further moved.
Thus the local search operation ends
naturally. In other words, the search



Table of Contents for the Digital Edition of Computational Intelligence - May 2014

Computational Intelligence - May 2014 - Cover1
Computational Intelligence - May 2014 - Cover2
Computational Intelligence - May 2014 - 1
Computational Intelligence - May 2014 - 2
Computational Intelligence - May 2014 - 3
Computational Intelligence - May 2014 - 4
Computational Intelligence - May 2014 - 5
Computational Intelligence - May 2014 - 6
Computational Intelligence - May 2014 - 7
Computational Intelligence - May 2014 - 8
Computational Intelligence - May 2014 - 9
Computational Intelligence - May 2014 - 10
Computational Intelligence - May 2014 - 11
Computational Intelligence - May 2014 - 12
Computational Intelligence - May 2014 - 13
Computational Intelligence - May 2014 - 14
Computational Intelligence - May 2014 - 15
Computational Intelligence - May 2014 - 16
Computational Intelligence - May 2014 - 17
Computational Intelligence - May 2014 - 18
Computational Intelligence - May 2014 - 19
Computational Intelligence - May 2014 - 20
Computational Intelligence - May 2014 - 21
Computational Intelligence - May 2014 - 22
Computational Intelligence - May 2014 - 23
Computational Intelligence - May 2014 - 24
Computational Intelligence - May 2014 - 25
Computational Intelligence - May 2014 - 26
Computational Intelligence - May 2014 - 27
Computational Intelligence - May 2014 - 28
Computational Intelligence - May 2014 - 29
Computational Intelligence - May 2014 - 30
Computational Intelligence - May 2014 - 31
Computational Intelligence - May 2014 - 32
Computational Intelligence - May 2014 - 33
Computational Intelligence - May 2014 - 34
Computational Intelligence - May 2014 - 35
Computational Intelligence - May 2014 - 36
Computational Intelligence - May 2014 - 37
Computational Intelligence - May 2014 - 38
Computational Intelligence - May 2014 - 39
Computational Intelligence - May 2014 - 40
Computational Intelligence - May 2014 - 41
Computational Intelligence - May 2014 - 42
Computational Intelligence - May 2014 - 43
Computational Intelligence - May 2014 - 44
Computational Intelligence - May 2014 - 45
Computational Intelligence - May 2014 - 46
Computational Intelligence - May 2014 - 47
Computational Intelligence - May 2014 - 48
Computational Intelligence - May 2014 - 49
Computational Intelligence - May 2014 - 50
Computational Intelligence - May 2014 - 51
Computational Intelligence - May 2014 - 52
Computational Intelligence - May 2014 - 53
Computational Intelligence - May 2014 - 54
Computational Intelligence - May 2014 - 55
Computational Intelligence - May 2014 - 56
Computational Intelligence - May 2014 - 57
Computational Intelligence - May 2014 - 58
Computational Intelligence - May 2014 - 59
Computational Intelligence - May 2014 - 60
Computational Intelligence - May 2014 - 61
Computational Intelligence - May 2014 - 62
Computational Intelligence - May 2014 - 63
Computational Intelligence - May 2014 - 64
Computational Intelligence - May 2014 - 65
Computational Intelligence - May 2014 - 66
Computational Intelligence - May 2014 - 67
Computational Intelligence - May 2014 - 68
Computational Intelligence - May 2014 - 69
Computational Intelligence - May 2014 - 70
Computational Intelligence - May 2014 - 71
Computational Intelligence - May 2014 - 72
Computational Intelligence - May 2014 - Cover3
Computational Intelligence - May 2014 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com