Information Technology Reference
In-Depth Information
IR
N
f
(
x
)
→
min
,
x
∈
with subject to
inequalities
g
i
(
x
)
≤
0
,i
=1
,...,n
1
,
and
(7.1)
equalities
h
j
(
x
)=0
,j
=1
,...,n
2
A feasible solution
x
satisfies all
n
1
inequality and
n
2
equality constraints. Many
constraint-handling techniques like penalty functions make use of a constraints
violation measurement
G
:
n
1
j
=1
|
n
2
max[0
,g
i
(
x
)]
β
+
γ
G
(
x
)=
h
j
(
x
)
|
(7.2)
i
=1
The parameters
β
and
γ
are usually chosen as one or two. In the following,
only inequality constraints are taken into account. Equality constraints can be
transformed into inequality constraints as shown in section 7.4.2.
7.2
A Short Survey of Constraint-Handling Methods
There exists a variety of constraint-handling techniques for EA. Most of them
can be classified into four main types of concepts.
•
Penalty functions
decrease the fitness of infeasible solutions by taking the
number of infeasible constraints or the distance to feasibility into account.
•
Repair algorithms
produce feasible solutions from infeasible ones and replace
them or use their fitness for evaluation.
•
Decoder functions
map genotypes to phenotypes which are guaranteed to be
feasible.
•
Feasibility preserving representations
or
genetic operators
force candidate
solutions to be feasible.
The methods are described in more detail in the following.
7.2.1
Penalty Functions
Most of the constraint handling methods are based on penalty functions. An
early, rather general penalty approach is the SUMT (sequential unconstrained
minimization technique) by Fiacco and McCormick [40]. The constrained prob-
lem is solved by a sequence of unconstrained optimizations in which the penalty
factors are stepwise intensified. In other penalty approaches penalty factors can
be defined statically [60] or depending on the number of satisfied constraints
[79]. They can dynamically depend on the number of generations of the EA as
Joines and Houck propose [66]:
f
(
x
)=
f
(
x
)+(
C
t
)
α
·
·
G
(
x
)
(7.3)
Search WWH ::
Custom Search