Computational Intelligence - May 2014 - 60

where Fitness C (R i) and Fitness S
(R i) are the fitness calculated by
1: Generate an initial population composed of
the conflict-based and cost-based
P individuals, set krun = 1.
techniques respectively. Precisely,
2: while the number of runs less than Nrun
they are calculated as follows:
(krun # Nrun) do
Fitness C (R i) . Fo r a g ive n
3: Randomly select two parents S1 and S2
resource class R i, Conf (v j) for
from the population.
each v j ! R i is obtained firstly, and
4: Apply the crossover operator to the two
then the node which has the largindividuals and generate a child.
est value of Conf ( ) is moved into
5: Apply the local search to the child to
SS Ri . This operation is repeated
optimize it.
until R i becomes conflict-free. If
6: The child and the parent with lower value
two or more nodes have identical
of Fitness() will be two individuals of the
number of conflicts, the one with
next generation. Remove the two parents
the minimum cost is moved into
C
from the population.
SS Ri . Then Fitness (R i) is the
7:
Repeat from 3 until P individuals of the
sum of costs of the nodes in SS Ri .
C
next generation population are generated.
That is, Fitness (R i) = Cost (SS Ri) .
Start the next run (krun = krun + 1).
Fitness S (R i) . For the nodes in
8: end while
conflict, they are moved into SS Ri
9: return the best solution found.
in increasing order of their costs,
until R i becomes conflict-free. If
two or more nodes have identical Figure 1 Pseudo code for the COMA.
value of costs, the one with the
maximum number of conflicts is moved
repetition, then compute the Metric of
into SS Ri . Then Fitness S (R i) is the sum
the remaining nodes again, until R i
of costs of the nodes in SS Ri:
becomes conflict-free. The sum of costs
of the nodes in SS Ri gives a new method
Fitness S (R i) = Cost (SS Ri) .
To our knowledge, Fitness C (R i) and
to calculate the fitness of R i, named
Fitness S (R i) are the first definitions of
Fitness M (R i) . If the nodes in R i have
fitness for a resource class to the resource
identical Conf ( ), one has Fitness M
allocation problem in EAs. The authors
(R i) = Fitness S (R i); or if the nodes in
intended to apply both the conflict and
R i have identical Cost( ), one has
cost information to decrease the total
Fitness M (R i) = Fitness C (R i) . In Section
cost of the register allocation problem. In
III: experimental evaluation, it is shown
fact, if all the nodes have identical value
that the advantage of the COMA upon
of costs, then Fitness C (R i) is the best
the HEA is small on uniform graphs. The
reason is that Fitness M (R i). Fitness S(R i)
approach to find the optimum SS Ri to
in uniform graphs. But in scale-free
spill; or if all the nodes have identical
graphs and modular graphs, the advannumber of conflicts, then Fitness S (R i) is
tage is evident.
the best approach to find the optimum
In many cases, but not all, Fitness M
SS Ri to spill. In a general case, both
S
C
Fitness (R i) and Fitness (R i) are diffi(R i) can give smaller value than both
cult to find the optimum SS Ri to spill.
Fitness C (R i) and Fitness S (R i) . So the
The second motivation of this paper
following equation is given to calculate
is to use a combination of the conflict
the fitness of a resource class,
and cost information to compute the
fitness of a resource class. The following
Fitness (R i) = min {Fitness C (R i),
metric is defined to move nodes into
Fitness S (R i),
SS Ri for a given resource class R i .
Fitness M (R i)}, i = 1, f, k.
(3)
Cost (v j)
Metric(v j) =
,
v j ! R i . (2)
Conf(v j)
Theoretically speaking, the fitness
obtained by (3) is always smaller than or
The node in R i with the smallest value
equal to that obtained by (1). That will
of Metric is moved into SS Ri in each

60

IEEE ComputatIonal IntEllIgEnCE magazInE | may 2014

improve the performance of the
algorithm. The fitness of an individual S p is then calculated by
k

Fitness (S p) = / Fitness (R i), (4)
i =1

which is the total cost of the solution.
The procedure of the COMA
is as follows. Generate an initial
population. Randomly select two
parents to generate an offspring by
the crossover operator. Apply the
local search operation to optimize
the offspring. The offspring and
the one of the two parents with
smaller value of Fitness ( ) calculated by (4) are selected as two
individuals of the population of
the next generation. The other
parent is eliminated. Repeat to
select two individuals from the rest
P - 2 chromosomes as parents to
create offspring, ..., until all the P
individuals of the next-generation population are created. The pseudo code of
the COMA is shown in Fig. 1, each part
of it will be described in detail in what
follows.
A. Initial Population Generation

The method to generate an initial population presented in [16] is used in this
paper. Topcuoglu et al. proposed a metric called the spill degree to order the
nodes. The spill degree of a node v i is
defined by one of the three equations:
S_Degree 1 (v i) = Cost (v i) # Degree (v i),
(5)
S_Degree 2 (v i) = Cost (v i) # Degree 2 (v i),
(6)
S_Degree 3 (v i) = Cost (v i) .

(7)

The spill degree of a node may be generated by (5), (6), or (7) with probability,
that may enhance the diversity of the
population. In the experiments of [16],
40% of the nodes in an initial individual
are set by (5), another 40% are set by (6),
and the remaining nodes are set by (7).
In the experiments of this paper, the
same proportion is applied to generate
the initial population.



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