Information Technology Reference
In-Depth Information
random second parent. Said mutation is in turn given as a difference of two other random
chromosomes. These operations are all done at the genotype level. It is in translating the
chromosome to a combinatorial object e.g. a permutation, that one encounters the phe-
notype. This refers, roughly, to the
expression
of the chromosome as something we can
use for objective function evaluation. Said slightly differently, one
decodes
a genotype
to obtain a phenotype. We want genotypes that are amenable to the mutation and mat-
ing operations of Differential Evolution, and phenotypes that will respond well to the
genotype, in the sense of allowing for reasonable improvement of objective function.
Discussion of these matters, with respect to the particulars of Differential Evolution,
may be found in [11]. Early discussion of these issues, and methods for handling them,
appear in [4] and [3].
4.2
Two Simple Examples
I like to start discussion of Differential Evolution in discrete optimization by presenting
two fairly straightforward examples. They serve to get the reader acclimated to how we
might set up simple problems, and also to how they look as input to
Mathematica
.These
are relatively simple examples of discrete optimization, not involving combinatorial
problems, and hence are good for easing into the main material of this chapter.
4.2.1
Pythagorean Triples
First we will search for Pythagorian triples. These, as one may recall from high school,
are integer triples (
x
,
y
,
z
) such that
x
2
+
y
2
=
z
2
. So we wish to find integer triples that
satisfy this equation. One way to set up such a problem is to form the square of the
difference,
x
2
+
y
2
z
2
. We seek integer triples that make this vanish, and moreover this
vanishing is a minimization condition (because we have a square). Note that this is to
some extent arbitrary, and minimizing the absolute value rather than the square would
suffice just as well for our purpose.
We constrain all variables to be between 5 and 25 inclusive. We also specify explicitly
that the variables are integer valued. We will say a bit more about this in a moment.
−
(
x
2
+
y
2
(
x
2
+
y
2
(
x
2
+
y
2
z
2
)
2
,
Element[
z
2
)
2
,
Element[
z
2
)
2
,
Element[
NMinimize[
NMinimize[
NMinimize[
{
{
{
−
−
−
{
{
{
x
,
y
,
z
x
,
y
,
z
x
,
y
,
z
}
}
}
,
Integers]
,
,
Integers]
,
,
Integers]
,
5
5
5
≤
≤
≤
x
x
x
≤
≤
≤
25
,
5
25
,
5
25
,
5
≤
≤
≤
y
y
y
≤
≤
≤
25
,
5
25
,
5
25
,
5
≤
≤
≤
z
z
z
≤
≤
≤
25
,
x
25
,
x
25
,
x
≤
≤
≤
y
y
y
}
}
}
,
,
,
{
{
{
x
,
y
,
z
x
,
y
,
z
x
,
y
,
z
}
}
}
]
]
]
{
0
.,
{
x
→
7
,
y
→
24
,
z
→
25
}}
We s e e t h a t
NMinimize
is able to pick an appropriate method by default. Indeed,
it uses
DifferentialEvolution
when variables are specified as discrete, that is,
integer valued.
Now we show how to obtain different solutions by specifying that the random seed
used by the
DifferentialEvolution
method change for each run. We will sup-
press warning messages (the algorithm mistakenly believes it is not converging). After
all, we are only interested in the results; we can decide for ourselves quite easily if they
work.
Search WWH ::
Custom Search