Biomedical Engineering Reference
In-Depth Information
scalene polyhedron with variable side lengths or via addition with an appropriate
value to generate an equilateral polyhedron. In the latter case, i.e. an equilateral
triangle in R
2
and a tetrahedron R
3
, cf. Fig.
3.27
may be generated. Apart from
setting up the initial simplex and the initial point respectively, all further steps are
deterministic and do not involve random elements.
In Fig.
3.27
the dashed triangle Dp
B
p
W
p
G
denotes the current simplex config-
uration, the vertex positions correspond to the objective function values U, e.g. U
W
is equivalent to the largest (or worst, index W) function value, U
B
and U
G
represent
the best and the second best (good) function values, respectively. They derive from
their corresponding parameter vectors:
U
B
:
¼
U
ð
p
B
Þ¼
min
f
U
ð
p
Þg
;
U
G
¼
U
ð
p
G
Þ
;
U
W
:
¼
U
ð
p
W
Þ¼
max
f
U
ð
p
Þg
ð
3
:
369
Þ
where U
W
[ U
G
[ U
B
:
In the minimum problem, the objective function value is evaluated in each
vertex, and the inherent heuristic follows the basic scheme: replace the vertex with
the largest function value, i.e. U
w
in Fig.
3.27
a, with the one situated at twice the
distance from the 'worst' vertex to the geometrical centre, i.e. centroid m, of all
other points in extension from the worst vertex to the centre point, i.e. replace p
W
with r. A possible rotation of the simplex around the vertex with the best function
value, p
B
, may result from this approach if, at each iteration, the reflected new
vertex retains the worst function value. This may especially be true if the search
advances towards a minimum where each new trial may not reduce the function
value. Thus, to avoid stagnation, the simplex edge lengths must be changed
appropriately depending on the evaluated objective function values at the poten-
tially new vertices. The possible simplex changes are described in the following,
starting from initial simplex generation and using the two-dimensional example
depicted in Fig.
3.27
.
1. Step: (Random) choice of the initial point p
i
;
k
¼
p
1
;
1
(with i denoting the
vertex index and k the iteration counter) and an appropriate side length s
len
and side length factor s
fac
, respectively.
2. Step:
R
2
Generation
of
the
initial
simplex
in
comprising
(n ? 1 = 3)
vertices.
p
2
;
1
¼
s
len
þ
p
12
;
1
p
1
;
1
¼
p
11
;
1
p
13
;
1
s
len
þ
p
23
;
1
p
3
;
1
¼
ð
3
:
370
Þ
p
21
;
1
p
22
;
1
3. Step: 3.1-Determination of the best, second best (good) and worst objective
function value and vertex respectively, by evaluating the model and the
objective functions at all P
i, 1
and subsequent sorting of U according to size
(e.g. via Bubble Sort).
