Database Reference
In-Depth Information
DAG). In this solution,
ms
represents the mapping string, e.g., abstract service S
1
is
mapped to application service S
11
, S
11
is further deployed on virtual machine
v
m
1
and database db
1
. The network service for a transferred data is determined when the
source service and the destination service are mapped to the corresponding virtual
machine and database services.
ss
represents the scheduling string of the solution,
e.g., the execution order of this solution in Fig.
8.5
is S
11
;S
23
;S
31
;S
41
;S
54
;S
71
;S
71
.
Genetic Algorithm Based Approach
In the first step, a predefined number of chromosomes are generated to form the
initial generation. The chromosomes in a generation are first ordered by their fitness
values (explained later) from the best to worst. These having the same fitness value
are ranked arbitrarily among themselves. Then a rank-based roulette wheel selection
schema is used to implement the selection step [
213
]. There is a higher probability
that one or more copies of the better solution will be included in the next generation,
since a better solution has a larger sector angle than that of a worse solution. In this
way, the chromosomes formed the next generation are determined. Notice that the
population size of each generation is always P .
The crossover operator for a matching string randomly chooses some pairs of the
matching strings. For each pair, it randomly generates a cut-off point to divide both
matching strings into two parts. Then the bottom parts are exchanged. The crossover
operator for a scheduling string randomly chooses some pairs of the scheduling
strings. For each pair, it randomly generates a cut-off point, which divides the
scheduling strings into top and bottom parts. The abstract application services in
each bottom part are reordered. The new ordering of the services in one bottom
part is the relative positions of these services in the other original scheduling string
in the pair. This guarantees that the newly generated scheduling strings are valid
schedules. Figure
8.6
a demonstrates the crossover operator for a scheduling string.
The mutation operator for a matching string randomly selects an abstract service
and randomly replaces the corresponding concrete service and other utility comput-
ing services. The mutation operator for a scheduling string randomly chooses some
scheduling strings. It then randomly selects a target service. The
valid range
of this
target service is the set of the positions in the scheduling string at which the target
service can be placed without violating any data dependency constraints. The valid
range is after all source services of the target service and before any destination
service of the target service. The mutation operator can move this target service
randomly to another position in the scheduling string within its valid range. Figure
8.6
b demonstrates the mutation operator for a scheduling string. s
v
is between s
b
and s
c
before the mutation, it is between s
a
and s
b
after the mutation operator.
After crossover and mutation operators, GA will evaluate the chromosomes using
fitness function
. The fitness function needs to maximize some QoS attributes (i.e.
ascending attributes), minimize some other attributes (i.e. descending attributes)
and satisfy other QoS attributes (i.e. equal QoS attributes). In addition, the fitness
