556
G. Filippi and M. Vasile
algorithm the relaxation procedure could be activated if the condition expressed in
line 13 is satisfied: a fixed number of iterations—arbitrarily lower that the maximum
allowed—has to be reached and none of the solution saved in the whole archive
A = A F ∪ A C has to be feasible in all the uncertainty domain U . If this happens, a
small violation of the constraint C is accepted and increased as long as a feasible
solution is obtained. The relaxation procedure is helped by the elimination from
the archive A C of all the vectors u previously saved with to a constraint violation
smaller than the actual (line 17).
Algorithm 1 Constrained minmax
1: Initialise ¯
d at random and run u a = argmaxF ( ¯
d, u) s.t. C(d min , u) ≤ 0
2: A u = A u ∪ {u a }; A c = ∅; A d = ∅
3: while N f val < N max
f val do
4:
Outer loop:
5:
d min = argmin d∈D {max u∈Au∪Ac F (d, u)} s.t.
max u∈Au∪Ac C(d, u) ≤ 0
6:
A d = A d ∪ {d min }
7:
Inner loop:
8:
u a,F = argmax u∈U F (d min , u) s.t. C(d min , u) ≤ 0
9:
u a,C = argmax u∈U C(d min , u)
10:
A u = A u ∪ {u a,F }
11:
if N f val < N relaxation
f val
∨ ∃d ∈ A d t.c. max u∈U C(d, u) ≤ 0 then
12:
if max u∈U C(d min , u) > 0 then
13:
A c = A c ∪ {u a,C }
14:
end if
15:
else
16:
update
17:
A c = {A c \ u a,C | C(d min , u) ≤ }
18:
if max u∈U C(d min , u) > > then
19:
A c = A c ∪ {u a,C }
20:
end if
21:
end if
22: end while
17.4 Belief Curve Reconstruction
The solution of the worst case scenario provides some key information on the system
under investigation. It defines the range of variability of ν for problem (17.26), it
provides a quantification of the extreme case and a possible countermeasure and
explores the space of the maxima over U which represents the set of extreme cases
for f and C. However, the most robust solution is also the most conservative and
does not account for the belief associated to each event. The solution of (17.26)
requires, instead, an efficient calculation of Bel for events different from the worst
case. In this section we consider a few approaches to calculate an approximated
value of Bel for a range of values of ν. We can group these approaches in
G. Filippi and M. Vasile
algorithm the relaxation procedure could be activated if the condition expressed in
line 13 is satisfied: a fixed number of iterations—arbitrarily lower that the maximum
allowed—has to be reached and none of the solution saved in the whole archive
A = A F ∪ A C has to be feasible in all the uncertainty domain U . If this happens, a
small violation of the constraint C is accepted and increased as long as a feasible
solution is obtained. The relaxation procedure is helped by the elimination from
the archive A C of all the vectors u previously saved with to a constraint violation
smaller than the actual (line 17).
Algorithm 1 Constrained minmax
1: Initialise ¯
d at random and run u a = argmaxF ( ¯
d, u) s.t. C(d min , u) ≤ 0
2: A u = A u ∪ {u a }; A c = ∅; A d = ∅
3: while N f val < N max
f val do
4:
Outer loop:
5:
d min = argmin d∈D {max u∈Au∪Ac F (d, u)} s.t.
max u∈Au∪Ac C(d, u) ≤ 0
6:
A d = A d ∪ {d min }
7:
Inner loop:
8:
u a,F = argmax u∈U F (d min , u) s.t. C(d min , u) ≤ 0
9:
u a,C = argmax u∈U C(d min , u)
10:
A u = A u ∪ {u a,F }
11:
if N f val < N relaxation
f val
∨ ∃d ∈ A d t.c. max u∈U C(d, u) ≤ 0 then
12:
if max u∈U C(d min , u) > 0 then
13:
A c = A c ∪ {u a,C }
14:
end if
15:
else
16:
update
17:
A c = {A c \ u a,C | C(d min , u) ≤ }
18:
if max u∈U C(d min , u) > > then
19:
A c = A c ∪ {u a,C }
20:
end if
21:
end if
22: end while
17.4 Belief Curve Reconstruction
The solution of the worst case scenario provides some key information on the system
under investigation. It defines the range of variability of ν for problem (17.26), it
provides a quantification of the extreme case and a possible countermeasure and
explores the space of the maxima over U which represents the set of extreme cases
for f and C. However, the most robust solution is also the most conservative and
does not account for the belief associated to each event. The solution of (17.26)
requires, instead, an efficient calculation of Bel for events different from the worst
case. In this section we consider a few approaches to calculate an approximated
value of Bel for a range of values of ν. We can group these approaches in