Database Reference
In-Depth Information
to as a
Population
. The first step of a GA is to derive an initial population.
A random set of chromosomes is often used as the initial population. This initial
population is the first generation from which the evolution starts. The second step
is
selection
. Each chromosome is eliminated or duplicated (one or more times)
based on its relative quality. The population size is typically kept constant. The
next step is
Crossover
. Some pairs of chromosomes are selected from the current
population and some of their corresponding components are exchanged to form
two valid chromosome. After crossover, each chromosome in the population may
be
mutated
with some probability. The mutation process transforms a chromosome
into another valid one. The new population is then
evaluated
. Each chromosome is
associated with a
fitness value
, which is a value obtained from the objective function
(details will be discussed in Sect.
8.2
). The objective of the evaluation is to find a
chromosome that has the optimal fitness value. If the stopping criterion is not met,
the new population goes through another cycle (iteration) of selection, crossover,
mutation, and evaluation. These cycles continue until the stopping criterion is met.
8.2
QoS-Aware Service Composition in Cloud Computing
Assume there are m VM UCSs (
v
m
1
;
v
m
2
;:::;
v
m
m
), p database UCSs (db
1
, db
2
,
:::, db
p
) and q network UCSs (
net
1
;
net
2
;:::;
net
q
) in different cloud systems.
Each composition solution (chromosome) consists of two parts, the matching string
(
ms
) and the scheduling string (
ss
). ms is a vector of length n, such that ms.i/
D
s
j
v
m
x
db
y
net
z
, where 1
i
n, 1
j
k
n
, 1
x
m, 1
y
p and
1
z
q. A matching string means that abstract service S
i
is assigned to concrete
service s
ij
which is lodged on virtual machine
v
m
x
and has database service db
y
,
network service net
z
. The scheduling string is a topological sort of the data-flow
graph. ss.k/
D
i , where 1
i; k
n; i.e. service S
i
is the kth running service
in the scheduling string. Thus, a chromosome represents the mapping from each
abstract service to concrete service and UCSs, together with the execution order
of the application services. Figure
8.5
shows a solution to the composite problem
that has the control-flow shown in Fig.
8.2
, and the data-flow shown in Fig.
8.3
(left
Fig. 8.5
Composition solution
