Information Technology Reference
In-Depth Information
In the above pseudo-code, the first step is to rank the population of clones
and parents into ordered classes, according to the “quality” of each individual.
This measure of “quality” of each individual can be given by the concept of
constrained -dominance
, originally proposed by [8].
The term
-dominance is a modification of the concept of Pareto Dominance
presented in Section 3. A vector
u
=(
u
1
,...,u
k
)issaidto
-dominate a vector
v
=(
v
1
,...,v
k
) if and only if
∀
i
∈{
1
,...,k
}
,u
i
≤
v
i
and
∃
i
∈{
1
,...,k
}
:
u
i
<v
i
−
i
. The parameter
is calculated from a user-defined parameter
δ
as
in
i
=
δ
minV alue
i
), where
maxV alue
i
is the maximum value
for coordinate
i
and
minV alue
i
is the minimum value for coordinate
i
.Inthis
context, it is said that a solution
i
constrained -dominates
asolution
j
if any of
the following conditions are true: (
i
)solution
i
is feasible and solution
j
is not
feasible; (
ii
) both solutions
i
and
j
are NOT feasible but solution
i
has a smaller
constraint violation
than solution
j
;and(
iii
) both solutions
i
and
j
are feasible
and solution
i
-dominates solution
j
.
The
constraint violation
for a solution
a
is given by
CV
(
a
)=
j
=1
γ
(
g
j
(
a
)) +
k
=1
|
×
(
maxV alue
i
−
,where
h
k
(
a
) is the value of the
k
-th equality constraint for solution
a
,
g
j
(
a
) is the value of the
j
-th inequality constraint for solution
a
,
γ
(
g
j
(
a
)) = 0
if
g
j
(
a
)
>
0and
γ
(
g
j
(
a
)) =
h
k
(
a
)
|
0.
In this context, the
ranking
procedure divides the population allocating to
Class one the solutions in the population that are not constrained
-dominated
by any other solution, to Class two the solutions constrained
-dominated only
by the solutions in Class one, and so on. Given that the ranking is made over the
parents and mutated clones, and the best classes are defined first, the algorithm is
then capable of implementing an elitism within a single population, without the
need of an auxiliary population as many multi-objective optimization algorithms
do.
Frequently in the selection process, the number of individuals in the class
to be inserted into the population is greater than the remaining “vacancies”
(the number of individuals that are still allowed to enter the population). Under
these circumstances, the algorithm must find another way to select individuals
expressing the same performance according to the ranking mechanism. In omni-
aiNet, a
grid
procedure is proposed. This procedure selects
N
r
solutions from
a given class
F
L
. To do so, it detects the kind of problem being optimized
(single or multi-objective) and works on each axis (dimension) of the variable
space (for single-objective problems) or of the objective space (for multi-objective
problems), selecting the
N
a
=
N
r
/N
axis
(where
N
axis
is the dimension of the
variable or objective space) more spaced solutions. For each axis, the procedure
finds the maximum and minimum solutions and divides the interval between
these extreme values into
N
a
cells
and selects the
N
a
solutions closest to the
center of each cell. This procedure tries to keep the solutions spread in the
variable or objective space, therefore contributing to the diversity of solutions
in the population.
|
g
j
(
a
)
|
if
g
j
(
a
)
≤
