download here bleach episode 224
http://www.megaupload.com/?d=839PFPVP
Selasa, 23 Juni 2009
Dragon Ball Kai Episode 12
Download here Dragon Ball Kai Episode 12
http://www.megaupload.com/?d=M2TQ5D2K
Sabtu, 20 Juni 2009
Dynamic Stochastic Optimal Path A Useful Tool From Probability Theory Rasteiro, Deolinda D. M. L Departamento de F´ isica Matem´ atica Instituto Super
Dynamic Stochastic Optimal Path
A Useful Tool From Probability Theory
Rasteiro, Deolinda D. M. L
Departamento de F´ isica Matem´ atica
Instituto Superior de Engenharia de Coimbra
Coimbra - Portugal
dml@mail.isec.pt
Anjo, Ant´ onio J. B.
Departamento de Matem´ atica - Universidade de Aveiro
Aveiro - Portugal
batel@ua.pt
March 10, 2005
Abstract
In this paper we prove a theorem that become very useful to design
algorithms for solving the dynamic stochastic optimal path.
We also prove that the solution for the deterministic shortest path
is always an upper bound for the dynamic stochastic optimal path.
Keywords: Probability Networks, Expected Value of an Op-
timal Path, Expected value of the minimum of two real random
variables, Dynamic paths
AMS Subject Classi?cation: 90B15
1 Introduction
Suppose we want to obtain de optimal route in a directed random network,
where the parameters associated to the arcs are real random variables fol-
lowing discrete distributions. The criteria that has been chosen by us to
decide which route is optimal is the one that minimizes the expected value
of an utility function over the considered network.
This methodology can be used in di?erent applications, as energy net-
work or data network, where real on time optimal solutions are necessary.
1
2 PROBLEM 2
For the special case of acyclic networks Cheung and Muralidharan [1]
developed a polynomial time algorithm (in terms of the number of realiza-
tions per arc cost and the number of emerging arcs per node) to compute
the expected cost of the dynamic stochastic shortest path.
In this paper we de?ne the problem of which consists in obtaining the
loopless path that minimizes the expected value of an utility function over a
dynamic probabilistic network with discrete real random variables (param-
eters) associated to each emerging arc. Then we prove a theorem, which is
useful tool from probability theory, used to design the algorithm that solves
the problem referred above.
We also prove that the optimal value of the deterministic shortest path,
obtained using the expected values of the real random variables, is always
an upper bound to the dynamic stochastic shortest path.
2 Problem
In the stochastic shortest path problem a directed probabilistic network
(N,A) is given where each arc (i, j) ? A is associated with the real random
variable X ij which is called the random parameter of the arc (i, j) ? A. We
assume that the real random variables X ij have discrete distributions and
are independent. The variables X ij are sometimes referred as cost, time or
distance.
1 2 r
The set of outcomes of X ij will be denoted by S X ij= d ij, d ij, . . . , d ij .
We will assume that the dimension of S X ij, i.e, r is always a ?nite value.
l l
The probability of X ij assume the value d ij is denoted by p ij.
If an appropriate utility is assigned to each possible consequence and
the expected utility of each alternative is calculated, then the best action is
to consider the alternative with the highest expected utility (which can be
the smallest expected value). Di?erent axioms that imply the existence of
utilities with the property that expected utility is an appropriate guide to
consistent decision making are presented in [6, 5, 3, 4, 2]. The choice of the
adequate utility function for a speci?c type of problem can be taken using
direct methods presented in Keeney and Rai?a’s book.
The utility of arc (i, j) ? A to be present in the optimal loopless path is
measured calculating the minimum of the real random variables X iwwhere
1
w is such that the arc (i,w) ? A, i.e, w belongs to the forward star of i.
1
The forward star of node i is the set formed by the terminal nodes of its outgoing
arcs.
2 PROBLEM 3
Thus U((i, j)) = min X iw.
w?F(i)
Associated to the path p, we de?ne the real random variable
X p = min X iw representing the random parameter of the loopless
w?F(i)
(i,j)?p
path p ? P.
With the objective of determine the optimal path, we consider a real
function U : P -? IR, called utility function, such that for each loopless
path p, U(p) depends on the random variables associated to the arcs of p
and is de?ned as
? ?
U(p) = E? min X iw?.
w?F(i)
(i,j)?p
In the dynamic stochastic shortest path, we want to determine the loop-
?
less path p ? P that minimizes the expected value of the utility function.
?
The loopless path p is called optimal solution of the referred problem.
The problem can then be mathematically de?ned as
? ?
minU(p) = min E? min X iw?
p?P p?P w?F(i)
(i,j)?A
? ?
= min E? min X iw?Y ij (1)
w?F(i)
(i,j)?A
s.t
?
1 , i = s
?
Y ij- Y ji = 0 , i / ? {s, t}
?
(i,j)?A -1 , i = t
Y ij ? {0, 1}
Since the constraint matrix is totally unimodular, by the integrality prop-
erty, the solution of the previous problem is equal to the solution of its linear
relaxation.
Example 2.1 In order to exemplify the problem consider the following net-
work
2 PROBLEM 4
Figure 1: Network Example
The solution for the referred example is
Figure 2: Example Solution
which means that the dynamic stochastic optimal loopless path is the
following < 1, (1, 2), 2, (2, 3), 3 > with value 5.5.
Theorem 2.1 Let X and Y be two random variables with ?nite mean value.
Then the following inequality holds E(min(X, Y )) = min(E(X),E(Y )).
Proof: Suppose that X and Y have the following set of outcomes S X=
{x 1, . . . , x n}, S Y = {y 1, . . . , ym}, respectively with P(X = x i) = p i, ?i =
1, . . . , n and P(Y = y j) = q j, ?j = 1, . . . ,m. The expected value of the
minimum between X and Y is given by
2 PROBLEM 5
n m
E(min(X, Y )) = min(x i, y j)p iq j
i=1 j=1
n mx i+ y j- |x i- y j|
= p iq j
2
i=1 j=1
n mx ip iq j+ y jp iq j- |x ip iq j- y jp iq j|
=
2
i=1 j=1
? ?
n m n m
= min? x ip iq j, y jq jp i?
i=1 j=1 i=1 j=1
= min (E(X),E(Y ))
From this theorem it follows a very important result which is
Theorem 2.2 The optimal value of the shortest deterministic path using
the expectations of the real random variables associated to the network arcs
is an upper bound to the optimal value of the dynamic stochastic shortest
path.
Proof: Consider the problem de?ned in section 2, (DSSP), and the let (SP)
be the problem of determining the optimal deterministic shortest loopless
path when we consider associated to each arc the parameter µ ij = E(X ij).
Assume that the optimal solutions of problems (SP) and (DSSP) are the
? ? ? ?
paths p , with value µ , and the path p , with value µ , respectively. We
1 1
? ?
will prove that µ = µ , ? p ? P.
1
By de?nition we obtain,
? ?
?
µ 1 = minE? min X iw?
p?P w?F(i)
(i,j)?p
= min E min X iw
p?P w?F(i)
(i,j)?p
If the set F(i) has only two elements, w 1 and w 2, then it follows that
?
µ 1 = min min E(X iw) (2)
p?P w?F(i)
(i,j)?p
= min min(µ iw 1 , µ iw 2 )
p?P
(i,j)?p
REFERENCES 6
only one of the arcs (i,w 1), (i,w 2) belongs to the path p ? P, i.e, j = w 1 or
j = w 2, thus
?
µ 1 = min min(µ iw 1 , µ iw 2 )
p?P
(i,j)?p
= min µ ij
p?P
(i,j)?p
?
= µ
which is the desired result. If the set F(i) has more than two elements then,
the same conclusion can be obtain by induction in the step (2).
References
[1] R. K. Cheung and B. Muralidharan, Dynamic routing of priority ship-
ments on a less-thantruckload service network, Tech. report, Department
of Industrial and Manufacturing Systems Engineering, Iowa State Uni-
versity, 1995.
[2] P. C Fishburn, Utility theory for decision making, Wiley, New York,
1970.
[3] R. D. Luce and H. Rai?a, Games and decisions, Wiley, New York, 1957.
[4] J. W. Pratt, H. Rai?a, and R. O. Schlaifer, Introduction to statistical
decision theory, McGraw-Hill, New York, 1965.
[5] L. J. Savage, The foundations of statistics, Wiley, New York, 1954.
[6] J. von Neumann and O. Mogenstern, Theory of games and economic
behavior, Princeton University Press, Princeton, N.J., 1947.
A Useful Tool From Probability Theory
Rasteiro, Deolinda D. M. L
Departamento de F´ isica Matem´ atica
Instituto Superior de Engenharia de Coimbra
Coimbra - Portugal
dml@mail.isec.pt
Anjo, Ant´ onio J. B.
Departamento de Matem´ atica - Universidade de Aveiro
Aveiro - Portugal
batel@ua.pt
March 10, 2005
Abstract
In this paper we prove a theorem that become very useful to design
algorithms for solving the dynamic stochastic optimal path.
We also prove that the solution for the deterministic shortest path
is always an upper bound for the dynamic stochastic optimal path.
Keywords: Probability Networks, Expected Value of an Op-
timal Path, Expected value of the minimum of two real random
variables, Dynamic paths
AMS Subject Classi?cation: 90B15
1 Introduction
Suppose we want to obtain de optimal route in a directed random network,
where the parameters associated to the arcs are real random variables fol-
lowing discrete distributions. The criteria that has been chosen by us to
decide which route is optimal is the one that minimizes the expected value
of an utility function over the considered network.
This methodology can be used in di?erent applications, as energy net-
work or data network, where real on time optimal solutions are necessary.
1
2 PROBLEM 2
For the special case of acyclic networks Cheung and Muralidharan [1]
developed a polynomial time algorithm (in terms of the number of realiza-
tions per arc cost and the number of emerging arcs per node) to compute
the expected cost of the dynamic stochastic shortest path.
In this paper we de?ne the problem of which consists in obtaining the
loopless path that minimizes the expected value of an utility function over a
dynamic probabilistic network with discrete real random variables (param-
eters) associated to each emerging arc. Then we prove a theorem, which is
useful tool from probability theory, used to design the algorithm that solves
the problem referred above.
We also prove that the optimal value of the deterministic shortest path,
obtained using the expected values of the real random variables, is always
an upper bound to the dynamic stochastic shortest path.
2 Problem
In the stochastic shortest path problem a directed probabilistic network
(N,A) is given where each arc (i, j) ? A is associated with the real random
variable X ij which is called the random parameter of the arc (i, j) ? A. We
assume that the real random variables X ij have discrete distributions and
are independent. The variables X ij are sometimes referred as cost, time or
distance.
1 2 r
The set of outcomes of X ij will be denoted by S X ij= d ij, d ij, . . . , d ij .
We will assume that the dimension of S X ij, i.e, r is always a ?nite value.
l l
The probability of X ij assume the value d ij is denoted by p ij.
If an appropriate utility is assigned to each possible consequence and
the expected utility of each alternative is calculated, then the best action is
to consider the alternative with the highest expected utility (which can be
the smallest expected value). Di?erent axioms that imply the existence of
utilities with the property that expected utility is an appropriate guide to
consistent decision making are presented in [6, 5, 3, 4, 2]. The choice of the
adequate utility function for a speci?c type of problem can be taken using
direct methods presented in Keeney and Rai?a’s book.
The utility of arc (i, j) ? A to be present in the optimal loopless path is
measured calculating the minimum of the real random variables X iwwhere
1
w is such that the arc (i,w) ? A, i.e, w belongs to the forward star of i.
1
The forward star of node i is the set formed by the terminal nodes of its outgoing
arcs.
2 PROBLEM 3
Thus U((i, j)) = min X iw.
w?F(i)
Associated to the path p, we de?ne the real random variable
X p = min X iw representing the random parameter of the loopless
w?F(i)
(i,j)?p
path p ? P.
With the objective of determine the optimal path, we consider a real
function U : P -? IR, called utility function, such that for each loopless
path p, U(p) depends on the random variables associated to the arcs of p
and is de?ned as
? ?
U(p) = E? min X iw?.
w?F(i)
(i,j)?p
In the dynamic stochastic shortest path, we want to determine the loop-
?
less path p ? P that minimizes the expected value of the utility function.
?
The loopless path p is called optimal solution of the referred problem.
The problem can then be mathematically de?ned as
? ?
minU(p) = min E? min X iw?
p?P p?P w?F(i)
(i,j)?A
? ?
= min E? min X iw?Y ij (1)
w?F(i)
(i,j)?A
s.t
?
1 , i = s
?
Y ij- Y ji = 0 , i / ? {s, t}
?
(i,j)?A -1 , i = t
Y ij ? {0, 1}
Since the constraint matrix is totally unimodular, by the integrality prop-
erty, the solution of the previous problem is equal to the solution of its linear
relaxation.
Example 2.1 In order to exemplify the problem consider the following net-
work
2 PROBLEM 4
Figure 1: Network Example
The solution for the referred example is
Figure 2: Example Solution
which means that the dynamic stochastic optimal loopless path is the
following < 1, (1, 2), 2, (2, 3), 3 > with value 5.5.
Theorem 2.1 Let X and Y be two random variables with ?nite mean value.
Then the following inequality holds E(min(X, Y )) = min(E(X),E(Y )).
Proof: Suppose that X and Y have the following set of outcomes S X=
{x 1, . . . , x n}, S Y = {y 1, . . . , ym}, respectively with P(X = x i) = p i, ?i =
1, . . . , n and P(Y = y j) = q j, ?j = 1, . . . ,m. The expected value of the
minimum between X and Y is given by
2 PROBLEM 5
n m
E(min(X, Y )) = min(x i, y j)p iq j
i=1 j=1
n mx i+ y j- |x i- y j|
= p iq j
2
i=1 j=1
n mx ip iq j+ y jp iq j- |x ip iq j- y jp iq j|
=
2
i=1 j=1
? ?
n m n m
= min? x ip iq j, y jq jp i?
i=1 j=1 i=1 j=1
= min (E(X),E(Y ))
From this theorem it follows a very important result which is
Theorem 2.2 The optimal value of the shortest deterministic path using
the expectations of the real random variables associated to the network arcs
is an upper bound to the optimal value of the dynamic stochastic shortest
path.
Proof: Consider the problem de?ned in section 2, (DSSP), and the let (SP)
be the problem of determining the optimal deterministic shortest loopless
path when we consider associated to each arc the parameter µ ij = E(X ij).
Assume that the optimal solutions of problems (SP) and (DSSP) are the
? ? ? ?
paths p , with value µ , and the path p , with value µ , respectively. We
1 1
? ?
will prove that µ = µ , ? p ? P.
1
By de?nition we obtain,
? ?
?
µ 1 = minE? min X iw?
p?P w?F(i)
(i,j)?p
= min E min X iw
p?P w?F(i)
(i,j)?p
If the set F(i) has only two elements, w 1 and w 2, then it follows that
?
µ 1 = min min E(X iw) (2)
p?P w?F(i)
(i,j)?p
= min min(µ iw 1 , µ iw 2 )
p?P
(i,j)?p
REFERENCES 6
only one of the arcs (i,w 1), (i,w 2) belongs to the path p ? P, i.e, j = w 1 or
j = w 2, thus
?
µ 1 = min min(µ iw 1 , µ iw 2 )
p?P
(i,j)?p
= min µ ij
p?P
(i,j)?p
?
= µ
which is the desired result. If the set F(i) has more than two elements then,
the same conclusion can be obtain by induction in the step (2).
References
[1] R. K. Cheung and B. Muralidharan, Dynamic routing of priority ship-
ments on a less-thantruckload service network, Tech. report, Department
of Industrial and Manufacturing Systems Engineering, Iowa State Uni-
versity, 1995.
[2] P. C Fishburn, Utility theory for decision making, Wiley, New York,
1970.
[3] R. D. Luce and H. Rai?a, Games and decisions, Wiley, New York, 1957.
[4] J. W. Pratt, H. Rai?a, and R. O. Schlaifer, Introduction to statistical
decision theory, McGraw-Hill, New York, 1965.
[5] L. J. Savage, The foundations of statistics, Wiley, New York, 1954.
[6] J. von Neumann and O. Mogenstern, Theory of games and economic
behavior, Princeton University Press, Princeton, N.J., 1947.
Robust goal programming by Dorota Kuchta
Robust goal programming
by
Dorota Kuchta
Institute of Industrial Engineering
Wroclaw University of Technology
Smoluchowskiego 25, 50-371 Wroc
Abstract: In the paper a new approach to goal programming is
presented: the robust approach, applied so far to a single-objective
linear programming. It is a ”pessimistic” approach, meant to ?nd
a solution which will be reasonably good even in a bad case, but it
is based on the assumption that almost never everything goes bad -
the decision maker can control and simulate the pessimistic aspect
of the decision situation. The pessimism refers here to uncertain
coe?cients in the goal functions. It is assumed that in each case only
a certain number of them can take on unfavourable values - but we
do not know which ones. A robust solution, i.e. the one which will
be good even in the most pessimistic case among those considered
to be possible - is determined, using only the linear programming
methods.
Keywords: multiobjective programming, robust solution, inter-
val optimisation.
1. Introduction
Goal programming has been known in the literature and has been applied suc-
cessfully in practice for many years. But like in case of any other modelling
and optimisation technique, its application encounters some problems when the
decision situation is marked by uncertainty and/or is likely to change. In such
a case the model has to be rede?ned and adopted to a given situation, to the
needs of the de?nite decision maker.
There are several possible approaches to modelling uncertainty and change.
The best known are the stochastic approach and the fuzzy approach. The
author, together with the late Stefan Chanas, has dealt quite a lot with the
fuzzy approach to goal programming. Chanas and Kuchta (2002) carried out
an overview of the existing approaches and their systematisation and categori-
sation. Chanas and Kuchta (2001, 2002) o?er three new fuzzy approaches to
goal programming, which ?ll up several of the existing gaps.
502 D. KUCHTA
The present paper is the ?rst - to the author’s knowledge - attempt to apply
another quite promising approach, called robust approach, to goal programming
and to multicriteria programming in general. The term ”robust solution” refers
in the literature to several di?erent notions and here we concentrate only on
one of them. But, generally, ”robust optimal solution” means such a solution,
which will be optimal even if there are changes in the parameters of the decision
situation. Of course, it has to be clari?ed each time what kind of changes is
meant here.
We start with a short review of the goal programming itself and de?ne what
kind of uncertainty in goal programming we will consider here. Then we present
the robust approach known in the literature and ?nally we apply it to the goal
programming in a situation of uncertainty.
2. The goal programming problem considered
If we were to provide a general de?nition of goal programming, it might be
formulated e.g. as follows: goal programming comprises decision problems in
which we have classical mathematical programming constraints and more than
one objective function (more than one goal), while for each objective function
the decision maker gives a target value (a goal) and its type (maximisation,
minimisation, equality). In case of maximisation objective function the decision
maker will be totally satis?ed if the objective function value is equal or greater
than the corresponding target value, for minimisation objective functions the
total satisfaction will be achieved for objective function values equal or less than
the corresponding target value, for objective functions of equality type - only
for objective function equal to the target value. However, as it is often impossi-
ble to attain fully the satisfactory values simultaneously, undesirable objective
function values (less than the target value for maximisation, greater that the
target value for maximisation, di?erent than the target value for equality) are
also accepted by the decision maker, but only to a certain extent.
In the following general goal programming formulation, (1) corresponds to
the objective functions (of minimisation, maximisation and equality type re-
spectively), and (2) to the classical constraints.
C i(x) = d i (i = 1, ..., k 1)
C i(x) = d i (i = k 1+ 1, ..., k 2) (1)
C i(x) = d i (i = k 2+ 1, ..., k 3)
A(x) = B (2)
x = 0.
n
In the above formulation x = (x j) 1 is a vector of non-negative decision vari-
ables, C i is the objective function (non necessarily linear) representing the j-th
goal, (2) is the canonical representation of the classical mathematical program-
Robust goal programming 503
ming constraints (not necessarily linear ones), and d i (i = 1, ..., k 3) stand for
the target values.
The inequality and equality signs in (1) have the “ ” sign over them, which
means that the corresponding relation does not have to be ful?lled completely,
that certain deviations in the undesired direction(s) are allowed.
The deviations from the target values (all of them, for the moment we do
not di?erentiate between the undesired and desired deviations) will be denoted
in the following way:
+ -
d = max(C (x) - d , 0), d = max(d - C (x), 0) (i = 1, ..., k ). (3)
i i i i i i 3
In the classical approach to goal programming it is assumed that the decision
maker wants to minimise the sum (possibly a weighted one) of all the undesired
deviations. Thus, the following objective function is formulated:
k i k 2 k 3
+ + ' - -
w id i + (w id i + w id i ) + w id i ? min (4)
i=1 i=k 1+1 i=k 2+2
'
where w i (i = 1, ..., k 3) and w i (i = k 1+ 1, ..., k 2) are positive weights.
Then, the problem with the objective function (4) and the constraints (2)
and (3) is solved, or rather its equivalent form with n + 2k 3 positive decision
variables:
k i k 2 k 3
+ + ' - -
w id i + (w id i + w id i ) + w id i ? min
i=1 i=k 1+1 i=k 2+2
+ -
C i(x) - d + d = d i, i = 1, ..., k 3 (5)
i i
A(x) = B
+ -
x = 0, d , d = 0 (i = 1, ..., k 3).
i i
Classical goal programming includes also problems with a hierarchy of goals.
Dennis and Dennis (1991) discuss the problem, we will not do it here.
In the paper we will consider a special case of the general model (1). The
limitations introduced to this special case are as follows:
a) we consider only goals of the minimisation type (which comprises the
maximisation case because of the possibility of multiplication by -1)
b) we consider only linear objective functions.
Thus, we consider the following model:
n
c ijx j= d j (i = 1, ..., k 1)
j=1
A(x) = B (6)
x = 0.
504 D. KUCHTA
The corresponding one-objective formulation is:
k i
+
w id i ? min
i=1
j
+ -
c ijx j- d i + d i = d i, i = 1, ..., k 1 (7)
i=1
A(x) = B
+ -
x = 0, d , d = 0 (i = 1, ..., k ).
i i 1
As for the uncertainty, we consider that the coe?cients c ij, i = 1, ..., k 1;
j = 1, ..., n may vary, in?uencing the attainment of goals in a negative way: the
coe?cient of the j-th variable in the i -th constraint will probably take on an
assumed value c , (i = 1, ..., k ; j = 1, ..., n), but it may also happen that it
ij 1
¯
will take on any value from the interval ?c ijc ¯ij?, (i = 1, ..., k 1; j = 1, ..., n). Let
¯
? ij = ¯ c ij, (i = 1, ..., k 1; j = 1, ..., n).
Before we pass on to the next point, let us present an example, based in its
crisp version on an example presented by Dennis and Dennis (1991), which will
accompany us throughout the paper.
Example 2.1 A company manufactures three divisible products. Let x j, j =
1, 2, 3 denote the amount of the respective products to be manufactured in the
coming period. Here is the matrix c ij, i = 1, ..., 4; j = 1, ..., 3, where
a) c 1 (j = 1, ..., 3) represent the most possible (normal) amount of material
j
¯
needed to manufacture the j-th product
b) c 2 (j = 1, ....3) represent the most possible (normal) amount of human
j
¯
work needed to manufacture the j-th product
c) c (j = 1, ..., 3) represent the most possible (normal) amount of machine
3 j
¯
time needed to manufacture the j-th product
d) c 4 (j = 1, ..., 3) represent the most possible (normal) selling price of the
j
¯
j-th product multiplied by -1.
j=1,2,3
Table 1. Matrix [c ij] i=1,2,3,4 for the example
¯
j=1 j=2 j=3
i=1 3 7 5
i=2 6 5 7
i=3 3 6 5
i=4 -28 -40 -32
The right-hand sides of the constraints (7), i.e. the goals (target values)
for the total amount of material used, the total amount of human work used,
the total amount of machine time used and the total turnover multiplied by -1
are, respectively, as follows: 200, 200, 200, -1500. These values should not be
Robust goal programming 505
exceeded, and thus we get the following one-objective problem (we assume that
the weights are equal to 1):
+ + + +
d + d + d + d ? min
1 2 3 4
- +
3x 1+ 7x + 5x 3+ d 1 - d 1 = 200
- +
6x 1+ 5x 2+ 7x 3+ d 2 - d 2 = 200
- +
3x 1+ 6x 2+ 5x 3+ d 3 - d 3 = 200
- +
-28x 1- 40x 2- 32x 3+ d 4 - d 4 = -1500
- +
x 1, x 2, x 3= 0; d , d = 0 (i = 1, 2, 3, 4).
i i
The optimal solution of this problem is as follows: x 1=20.8, x 2=23, x 3=0,
+ + + +
d =23, d =39.5, d =0, d =0.
1 2 3 4
Let us assume that the possible variations of the coe?cients are equal ap-
proximately to 10% of the ”normal” value (see Table 2).
j=1,2,3 j=1,2,3
Table 2. Matrices [¯ c ij] i=1,2,3,4 and [? ij] i=1,2,3,4 for the example
j = 1 j = 1 j = 1
c ¯ij ? ij c ¯ij ? ij c ¯ij ? ij
i = 1 3.3 0.3 7.7 0.7 5.5 0.5
i = 2 6.6 0.6 5.5 0.5 7.7 0.7
i = 3 3.3 0.3 6.6 0.6 5.5 0.5
i = 4 -25.2 2.8 -36 4 28.8 3.2
In case of materials’ usage, the variations may be due to material quality or
the workers’ experience (inexperienced workers produce more waste). In case of
human work the ”normal” values can change because of the lack of experience
or of motivation, and the machine hours needed to manufacture one product
may be in?uenced by the machine failure frequency. The unit prices may go
down (which means an increase of the numbers multiplied by -1) because of the
uncertain market situation.
Now we will present the proposal for a robust optimal solution of the goal
programming problem (6) with variations ? ij (i = 1, ..., k 1; j = 1, ...n) in the
left-hand sides of the goals. These variations can be called ”negative” in the
sense that they in?uence negatively the achievement of goals.
3. Robust solution of the goal programming problem with
possible negative variations in the left-hand sides of
goals
We adopt here the concept of robustness of an optimal solution proposed by
Bertsimas and Sim (2003). They apply it to a mixed integer linear programming
problem with possible variations in the objective function coe?cients and in the
506 D. KUCHTA
left-hand side coe?cients of the constraints. Their idea can be summarized as
follows:
a) A robust optimal solution is such a solution which would be optimal for
the worst possible values of the coe?cients within the assumed variation
possibilities (intervals) - where the worst means minimal for the maximi-
sation of the objective function and for the ”greater-or-equal” constraints
and maximal in the other cases.
b) By applying strictly the above de?nition, we would obtain a ”pessimistic”
case, which would reduce to solving the corresponding problem with coef-
?cients being set at their worst possible values; such a robust solution is
of course very easy to obtain, but its quality (the value of the objective
function) may be not very good; in many cases such an approach may be
too pessimistic, as it assumes that everything may go wrong, that all the
coe?cients may vary in the negative direction simultaneously.
c) Thus, the authors propose, justifying their approach with the behaviour
of nature, to assume that only some coe?cients will indeed change (e.g.
the price of only some products will go down, not of all of them); of
course, we cannot know which ones and in the proposed approach it is
not necessary to choose the coe?cients which we suspect to change; the
only thing required is to say, for the objective function and for each of
the constraints individually, what is in our opinion the maximal number
of coe?cients that may change with respect to the ”normal” value.
By applying this approach to problem (6), with c ij ? ?c ij, c ¯ij?, (i = 1, ..., k 1;
¯
j = 1, ..., n), c being the ”normal” value, we can introduce the notion of the
ij
¯
M-robust solution, where
k 1
M = (m i) i=1 and m i (i = 1, ..., k 1) is an integer number not exceeding n,
chosen by the decision maker, which expresses how many coe?cients in the i -th
constraint can change at the most. If m i = 0 (i = 1, ..., k 1), we assume that
nothing will go wrong and obtain the normal optimal solution. On the other
hand, if m i = n (i = 1, ..., k 1), we get the pessimistic, ”fully robust” solution
mentioned above.
Now we will show how to determine the M-robust solution of (6) for a given
vector M.
4. The single-criterion linear programming problem for
the M-robust solution of the goal programming prob-
lem
As we adopt the model from Bertsimas and Sim (2003) to our needs, we obtain
the following model whose solution will constitute the M-robust solution of (6)
Robust goal programming 507
(|X| denotes the power of set X)
n
c x + max ? x =d (i = 1, ..., k ) (8)
ij j ij j i 1
¯ S i ? {1, ..., n}
j=1 j?S j
|S i| = m i
A(x) = B.
By reformulating the problem (8) in the same way as in the classical goal
programming, we can arrive at the following problem:
k 1
+
w id i ? min
j=1
n
+ -
c ijx j+ max ? ijx j- d i + d i = d i (i = 1, ..., k 1) (9)
¯ S i ? {1, ...n}
j=1 j?S j
|S i| = m i
A(x) = B
+ -
x = 0, d , d = 0 (i = 1, ..., k 1).
i i
The optimal value of the objective function obtained in this way will be the
worst optimal value of the total deviation - when in each goal i (i = 1, ...k 1)
the m i coe?cients are allowed to take on the least favourable (the maximal
possible) values. By changing the values of m i, we can see how this in?uences
the optimal value of the total deviation.
Of course, the above problem is not linear. However, we will transform it
to a linear problem by means of the following lemma proved by Bertsimas and
Sim (2003).
Lemma 4.1 Let ß i(x 1, x 2, ..., x n) = max ? ijx j(i = 1, ...k 1). For each
S i ? { , ...n} 1
j?S j
|S i| = m i
vector (x 1, x 2, ..., x n) and i = 1, 2, ..., k 1, ß i(x 1, x 2, ..., x n), is the optimal objec-
tive function value of the following linear programming problem
n
p ij+ m iz i? min
j=1
z i+ p ij = ? ijx j (j = 1, ..., n) (10)
p ij = 0 (j = 1, ..., n), z i = 0 .
Let us now formulate the following linear programming problem, which, as
we will show afterwards, will give us the M-robust solution of (6):
k 1
+
w 1d i ? min
j=1
508 D. KUCHTA
n n
+ -
c x + p + m z - d + d = d (i = 1, ..., k )
ij j ij i i i i i 1
¯
j=1 j=1
z i+ p ij = ? ijx j (j = 1, ..., n) (i = 1, ..., k 1) (11)
p ij = 0 (j = 1, ..., n), z i = 0 (i = 1, ..., k 1)
A(x) = B
+ -
x = 0, d , d = 0 (i = 1, ..., k ).
i i 1
Theorem 4.1 The optimal function values of (9) i (11) coincide.
-
n + k 1
Proof. If (x j) j=1, (d i , d i ) i=1 is a feasible solution of (9), it is obviously also
(together with the corresponding values of p ij (j = 1, ..., n), z i) a feasible so-
lution of (11). This shows that the objective function value of (11) does not
exceed the objective function value of (9).
n
n
On the other hand, for a ?xed (x j) j=1, from the obvious relation ijc ijx j+
¯
n n
max ? ijx j = c ijx j+ p ij+m iz i, i = 1, ..., k 1, p ij > 0, z i > 0,
S i ? { , ...n} 1 ¯
j?S j j=1 j=1
|S i| = m i
-
n + k 1
it follows that for each feasible solution (x j) j=1, (d i,0, d i,0) i=1 of (9) and for
-
n + k 1 n + +
each feasible solution (x j) j=1, (d i,1, d i,1) i=1, (p ij, z j) j=1 we have (d i,0 = d i,1
(i = 1, ..., k 1).
From this it follows that the optimal function value of (9) does not exceed
the optimal function value of (11), which completes the proof.
5. Computational example
Now we will apply the proposed approach to Example 1. Problem (11) for the
example becomes:
+ + + +
d + d + d + d ? min
1 2 3 4
- +
3x 1+ 7x 2+ 5x 3+ p 11+ p 12+ p 13+ m 1z 1+ d 1 - d 1 = 200
- +
6x 1+ 5x 2+ 7x 3+ p 21+ p 22+ p 23+ m 2z 2+ d 2 - d 2 = 200
- +
3x 1+ 6x 2+ 5x 3+ p 31+ p 32+ p 33+ m 3z 3+ d 3 - d 1 = 200
- +
-28x 1- 40x 2- 32x 3+ p 41+ p 42+ p 43+ m 4z 4+ d 4 - d 4 = -1500
z 1+ p 11= 0.3x 1; z 1+ p 12= 0.7x 2; z 1+ p 13= 0.5x 3;
z 2+ p 21= 0.6x 1; z 2+ p 22= 0.5x 2; z 2+ p 23= 0.7x 3;
z 3+ p 31= 0.3x 1; z 3+ p 32= 0.6x 2; z 3+ p 33= 0.5x 3;
z 4+ p 41= 2.8x 1; z 4+ p 42= 4x 2; z 4+ p 43= 3.2x 3;
-
x i, z i, d i , p ij = 0 (i = 1, 2, 3, 4; j = 1, 2, 3)
where m 1,m 2,m 3,m 4 are parameters - integer numbers less than or equal 3,
selected by the decision maker to ?x his degree of pessimism with respect to
each goal. For the i -th goal, m i expresses how many of the left hand side
Robust goal programming 509
coe?cients of this goal can reach their least favourable value. Here are the
results - the worst optimal value of the total deviation for various values of
m 1,m 2,m 3,m 4, see Table 3.
Table 3. Computational results for the example
m 1,m 2,m 3,m 4 0,0,0,0 0,0,0,3 1,1,1,1 1,1,1,3 2,2,2,2 3,3,3,3
the worst optimal
62.5 125 136.18 172.15 187.33 187.5
total deviation
This approach allows us to evaluate what is the worst possible optimal value
of the total deviation from the goals according to the given situation, i.e. ac-
cording to how ”malicious” the market (the 4th goal) or the machines (the 3rd
goal) may happen to be or how uncertain the material (the 1st goal) or the
human being (the 2nd) goal may turn out. In our example we can see e.g. that
if the market is very uncertain, this in?uences the worst optimal total deviation
very strongly (compare the ?rst two columns of Table 3).
6. Conclusions
To the author’s knowledge, the paper presents the ?rst approach to multiob-
jective programming making use of one of the robust models proposed in the
literature. The approach proposed here might also be called a pessimistic ap-
proach, as it searches for the worst possible optimal value of the total deviation
from the goal - the worst in the assumed (by the decision maker) framework of
possible variations. In other words, the decision maker can ?nd solutions for
various degrees of pessimism or uncertainty, simply by changing one parame-
ter per goal. The solution can be obtained by means of a linear programming
problem, if the goal functions and the other constraints of the original model
are linear.
The research will continue to examine other models of goal programming,
not considered in this paper, but it would be very interesting to see what other
robust approaches (e.g. the one proposed by Ben-Tal and Nemirovsky, 1999
might contribute to multiple objective optimisation.
References
Ben-Tal, A. and Nemirovsky, A. (1999) Robust solutions to uncertain pro-
grams. Oper. Res. Lett. 25, 1-13.
Bertsimas, D. and Sim, M. (2003) Robust discrete optimization and net-
work ?ows. Math. Program. Ser. B 98, 49-71.
Dennis, T.L. and Dennis, L.B. (1991) Management Science. West Publish-
ing Company, St. Paul.
510 D. KUCHTA
Chanas, S. and Kuchta, D. (2002) On a certain approach to fuzzy goal pro-
gramming. In: Trzaskalik T., Michnik J., eds., Multiple Objective and Goal
Programming, Recent Developments. Physica-Verlag, 15-30.
Chanas, S. and Kuchta, D. (2001) A new approach to fuzzy goal program-
ming. In: Proceedings Eus?at 2001 An International Conference in Fuzzy
Logic and Technology, Leicester, UK.
Chanas, S. and Kuchta, D. (2002) Fuzzy goals and crisp deviations - a new
approach to fuzzy goal programming. In: Trzaskalik T., ed., Modelowanie
Preferencji a ryzyko. Akademia Ekonomiczna, Katowice, 61-74.
Chanas, S. and Kuchta, D. (2002) Fuzzy Goal Programming - one notion,
many meanings. Control and Cybernetics 31, 4, 871-890.
Lilliefors/Van Soest’ s test of normality 1 Hervé Abdi & PaulMolin
Lilliefors/Van Soest’ s test of normality 1 Hervé Abdi & PaulMolin
Overview
The normality assumption is at the core of a majority of standard
statistical procedures, and it is important to be able to test this
assumption. In addition, showing that a sample does not come
from a normally distributed population is sometimes of impor-
tance per se. Among the many procedures used to test this as-
sumption, one of the most well-known is a modi?cation of the
Kolomogorov-Smirnov test of goodness of ?t, generally referred to
as the Lilliefors test for normality (or Lilliefors test, for short). This
test was developed independently by Lilliefors (1967) and by Van
Soest (1967). The null hypothesis for this test is that the error is
normally distributed (i.e., there is no difference between the ob-
served distribution of the error and a normal distribution). The
alternative hypothesis is that the error is not normally distributed.
Like most statistical tests, this test of normality de?nes a cri-
terion and gives its sampling distribution. When the probability
associated with the criterion is smaller than a given a-level, the
1
In: Neil Salkind (Ed.) (2007). Encyclopedia of Measurement and Statistics.
Thousand Oaks (CA): Sage.
Address correspondence to: Hervé Abdi
Programin Cognition and Neurosciences,MS: Gr.4.1,
The University of Texas at Dallas,
Richardson, TX 75083–0688, USA
E-mail: herve@utdallas.edu http://www.utd.edu/~herve
1
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
alternative hypothesis is accepted (i.e., we conclude that the sam-
ple does not come from a normal distribution). An interesting pe-
culiarity of the Lilliefors’ test is the technique used to derive the
sampling distribution of the criterion. In general, mathematical
statisticians derive the sampling distribution of the criterion us-
ing analytical techniques. However in this case, this approach fails
and consequently, Lilliefors decided to calculate an approximation
of the sampling distribution by using the Monte-Carlo technique.
Essentially, the procedure consists of extracting a large number of
samples fromaNormal Population and computing the value of the
criterion for each of these samples. The empirical distribution of
the values of the criterion gives an approximation of the sampling
distribution of the criterion under the null hypothesis.
Speci?cally, both Lilliefors and Van Soest used, for each sample
size chosen, 1000 random samples derived from a standardized
normal distribution to approximate the sampling distribution of a
Kolmogorov-Smirnov criterion of goodness of ?t. The critical val-
ues given by Lilliefors and Van Soest are quite similar, the relative
2
error being of the order of 10- .
According to Lilliefors (1967) this test of normality ismore pow-
erful than others procedures for a wide range of nonnormal con-
ditions. Dagnelie (1968) indicated, in addition, that the critical
values reported by Lilliefors can be approximated by an analyti-
cal formula. Such a formula facilitates writing computer routines
because it eliminates the risk of creating errors when keying in the
values of the table. Recently, Molin and Abdi (1998), re?ned the
approximation given by Dagnelie and computed new tables using
a larger number of runs (i.e., K = 100,000) in their simulations.
2 Notation
The sample for the test ismade of N scores, each of themdenoted
X i. The samplemean is denoted M X is computed as
N
1
M X = X i, (1)
N
i
2
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
the sample variance is denoted
N 2
(X i -M X)
2 i
S , (2)
X = N -1
and the standard deviation of the sample denoted S X is equal to
the square root of the sample variance.
The ?rst step of the test is to transform each of the X i scores
into Z-scores as follows:
X i M X
Z i = - . (3)
S X
For each Z i-score we compute the proportion of score smaller
or equal to its value: This is called the frequency associated with
this score and it is denoted S (Z i). For each Z i-score we also com-
pute the probability associated with this score if is comes from a
“standard” normal distribution with a mean of 0 and a standard
deviation of 1. We denote this probability byN (Z i), and it is equal
to Z 1 1
i
2
N (Z i) = exp - Z i . (4)
-8 2p 2
The criterion for the Lilliefors’ test is denoted . It is calculated L
fromthe Z-scores, and it is equal to
L =max{|S (Z i)-N (Z i)|, |S (Z i)-N (Z i 1) } . (5)
i - |
So is the absolute value of the biggest split between the proba- L
bility associated to Z i when Z i is normally distributed, and the fre-
quencies actually observed. The term|S (Z i)-N (Z i-1)| is needed
to take into account that, because the empirical distribution is dis-
crete, the maximum absolute difference can occur at either end-
points of the empirical distribution.
The critical values are given by Table 2. critical is the critical L
value. TheNull hypothesis is rejectedwhen the criterion is greater L
than or equal to the critical value critical. L
3
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
3 Numerical example
As an illustration, we will look at an analysis of variance exam-
ple for which we want to test the so-called “normality assump-
tion” that states that the within group deviations (i.e., the “resid-
uals”) are normally distributed. The data are from Abdi (1987, p.
93ff.) and correspond to memory scores obtained by 20 subjects
who were assigned to one of 4 experimental groups (hence 5 sub-
jects per group). The score of the sth subject in the ath group is
denoted Y a,s, and the mean of each group is denoted M a.. The
within-group mean square MS S(A) is equal to 2.35, it correspond
to the best estimation of the population error variance.
G. 1 G. 2 G. 3 G. 4
3 5 2 5
3 9 4 4
2 8 5 3
4 4 4 5
3 9 1 4
Y a. 15 35 16 21
M a. 3 7 3.2 4.2
TheNormality assumption states that the error is normally dis-
tributed. In the analysis of variance framework, the error corre-
sponds to the residuals which are equal to the deviations of the
scores to themean of their group. So in order to test the normality
assumption for the analysis of variance, the ?rst step is to com-
pute the residuals from the scores. We denote X i the residual cor-
responding to the i th observation (with i going from 1 to 20). The
residuals are given in the following table:
Y as 3 3 2 4 3 5 9 8 4 9
X i 0 0 -1 1 0 -2 2 1 -3 2
Y as 2 4 5 4 1 5 4 3 5 4
X i -1.2 .8 1.8 .8 -2.2 .8 -.2 -1.2 .8 -.2
4
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
Next we transform the X i values into Z i values using the fol-
lowing formula:
X i
Z i = (6)
MS S(A)
because MS S(A) is the best estimate of the population variance,
and the mean of X i is zero. Then, for each Z i value, the frequency
associated with S (Z i) and the probability associated with Z i un-
der the Normality condition N (Z i) are computed [we use a table
of the Normal Distribution to obtain N (Z i)]. The results are pre-
sented in Table 1.
The value of the criterion is (see Table 1)
L =max{|S (Z i)-N (Z i)|, |S (Z i)-N (Z i 1) } .250 . (7)
i - | =
Taking an a level of a = .05, with N = 20, we ?nd (from Table 2)
that the critical value is equal critical = .192. Because is larger L L
than critical, the null hypothesis is rejected and we conclude that L
the residuals in our experiment are not distributed normally.
4 Numerical approximation
The available tables for the Lilliefors’ test of normality typically re-
port the critical values for a small set of alpha values. For example,
the present table reports the critical values for
a = [.20, .15, .10, .05, .01].
These values correspond to the alpha values used for most tests
involving only one null hypothesis, as this was the standard pro-
cedure in the late sixties. The current statistical practice, however,
favors multiple tests (maybe as a consequence of the availability
of statistical packages). Because usingmultiple tests increases the
overall Type I error (i.e., the Familywise Type I error or a PF), it has
become customary to recommend testing each hypothesis with a
corrected a level (i.e., the Type I error per comparison, or a PC)
such as the Bonferonni or Sidák corrections. For example, using ?
a Bonferonni approach with a familywise value of a PF = .05, and
5
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
Table 1: How to compute the criterion for the Lilliefors’ test of
normality. N i stands for the absolute frequency of a given value
of X i, F i stands for the absolute frequency associated with a given
value of X i (i.e., the number of scores smaller or equal to X i),
Z i is the Z-score corresponding to X i, S (Z i) is the proportion of
scores smaller than Z i, N (Z i) is the probability associated with
Z i for the standard normal distribution, D 0 =| S (Z i) -N (Z i) |,
D -1=| S (Z i)-N (Z i-1) |, and max is the maximum of {D 0,D -1}.
The value of the criterion is = .250. L
X i N i F i Z i S (Z i) N (Z i) D 0 D -1 max
-3.0 1 1 -1.96 .05 .025 .025 .050 .050
-2.2 1 2 -1.44 .10 .075 .025 .075 .075
-2.0 1 3 -1.30 .15 .097 .053 .074 .074
-1.2 2 5 -.78 .25 .218 .032 .154 .154
-1.0 1 6 -.65 .30 .258 .052 .083 .083
-.2 2 8 -.13 .40 .449 .049 .143 .143
.0 3 11 .00 .55 .500 .050 .102 .102
.8 4 15 .52 .75 .699 .051 .250 .250
1.0 2 17 .65 .85 .742 .108 .151 .151
1.8 1 18 1.17 .90 .879 .021 .157 .157
2.0 2 20 1.30 1.00 .903 .097 .120 .120
testing J = 3 hypotheses requires that each hypothesis is tested at
the level of
1 1
a a
PC= J PF = 3×.05 = .0167 . (8)
With a Sidák approach, each hypothesis will be tested at the level ?
of
1 1
J 3
a a
PC= 1-(1- PF) = 1-(1-.05) = .0170 . (9)
As this example illustrates, both procedures are likely to require us-
ing different a levels than the ones given by the tables. In fact, it is
rather unlikely that a table could be precise enough to provide the
wide range of alpha values needed formultiple testing purposes. A
6
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
more practical solution is to generate the critical values for any al-
pha value, or, alternatively, to obtain the probability associated to
any value of the Kolmogorov-Smirnov criterion. Such an approach
can be implemented by approximating the sampling distribution
“on the ?y" for each speci?c problemand deriving the critical val-
ues for unusual values of a.
Another approach to ?nding critical values for unusual values
of a, is to ?nd a numerical approximation for the sampling distri-
butions. Molin and Abdi (1998) proposed such an approximation
and showed that it was accurate for at least the ?rst two signi?-
cant digits. Their procedure, somewhat complex, is better imple-
mented with a computer and comprises two steps.
The ?rst step is to compute a quantity called A obtained from
the following formula:
2 L 2
-(b 1+N)+ (b 1+N) -4b 2 b 0- -
A = , (10)
2b 2
with
b 2= 0.08861783849346
b 1= 1.30748185078790
b 0= 0.37872256037043 . (11)
The second step implements a polynomial approximation and
estimates the probability associated to a given value as: L
Pr( ) ˜ -.37782822932809+1.67819837908004A L
2 3
-3.02959249450445A +2.80015798142101A
4 5
-1.39874347510845A +0.40466213484419A
6 7
-0.06353440854207A +0.00287462087623A
8 9
+0.00069650013110A -0.00011872227037A
10
+0.00000575586834A . (12)
For example, suppose that we have obtained a value of = L
.1030 froma sample of size N = 50. (Table 2 shows that Pr( ) = .20.) L
7
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
To estimate Pr( ) we need ?rst to compute A, and then use this L
value in Equation 12. FromEquation 10, we compute the estimate
of A as:
2 L 2
-(b 1+N)+ (b 1+N) -4b 2 b 0- -
A =
2b 2
2 2
-(b 1+50)+ (b 1+50) -4b 2 b 0-.1030-
=
2b 2
= 1.82402308769590 . (13)
Plugging in this value of A in Equation 12 gives
Pr( ) = .19840103775379 ˜ .20 . (14) L
As illustrated by this example, the approximated value of Pr( ) is L
correct for the ?rst two decimal values.
References
[1] Abdi, H. (1987). Introduction au traitement statistique des
données expérimentales. Grenoble: Presses Universitaires de
Grenoble.
[2] Dagnelie, P . (1968). A propos de l’emploi du test de
Kolmogorov-Smirnov comme test de normalité, Biométrie et
Praximétrie 9, 3–13.
[3] Lilliefors, H. W. (1967). On the Kolmogorov-Smirnov test for
normality with mean and variance unknown, Journal of the
American Statistical Association, 62, 399–402.
[4] Molin, P ., Abdi H. (1998). New Tables and nu-
merical approximation for the Kolmogorov-
Smirnov/Lillierfors/Van Soest test of normality. Tech-
nical report, University of Bourgogne. Available from
www.utd.edu/~herve/MA_Lilliefors98.pdf.
[5] Van Soest, J. (1967). Some experimental results concerning
tests of normality. Statistica. Neerlandica, 21, 91–97, 1967.
8
Table 2: Table of the critical values for the Kolmogorov-Smir-
nov/Lillefors test of normality obtained with K = 100,000 samples
for each sample size. The intersection of a given row and column
shows the critical value critical for the sample size labelling the row L
and the alpha level labelling the column. For N > 50 the critical
.83 N
value can be found by using f N=+ -.01.
N
N a = .20 a = .15 a = .10 a = .05 a = .01
4 .3027 .3216 .3456 .3754 .4129
5 .2893 .3027 .3188 .3427 .3959
6 .2694 .2816 .2982 .3245 .3728
7 .2521 .2641 .2802 .3041 .3504
8 .2387 .2502 .2649 .2875 .3331
9 .2273 .2382 .2522 .2744 .3162
10 .2171 .2273 .2410 .2616 .3037
11 .2080 .2179 .2306 .2506 .2905
12 .2004 .2101 .2228 .2426 .2812
13 .1932 .2025 .2147 .2337 .2714
14 .1869 .1959 .2077 .2257 .2627
15 .1811 .1899 .2016 .2196 .2545
16 .1758 .1843 .1956 .2128 .2477
17 .1711 .1794 .1902 .2071 .2408
18 .1666 .1747 .1852 .2018 .2345
19 .1624 .1700 .1803 .1965 .2285
20 .1589 .1666 .1764 .1920 .2226
21 .1553 .1629 .1726 .1881 .2190
22 .1517 .1592 .1690 .1840 .2141
23 .1484 .1555 .1650 .1798 .2090
24 .1458 .1527 .1619 .1766 .2053
25 .1429 .1498 .1589 .1726 .2010
26 .1406 .1472 .1562 .1699 .1985
27 .1381 .1448 .1533 .1665 .1941
28 .1358 .1423 .1509 .1641 .1911
Table continues on the following page . . .
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
Table 3: . . . Continued. Table of the critical values for the Kolmogo-
rov-Smirnov/Lillefors test of normality obtained with K = 100,000
samples for each sample size. The intersection of a given row and
column shows the critical value critical for the sample size labelling L
the row and the alpha level labelling the column. For N > 50 the
.83 N
critical value can be found by using f N=+ -.01.
N
N a = .20 a = .15 a = .10 a = .05 a = .01
29 .1334 .1398 .1483 .1614 .1886
30 .1315 .1378 .1460 .1590 .1848
31 .1291 .1353 .1432 .1559 .1820
32 .1274 .1336 .1415 .1542 .1798
33 .1254 .1314 .1392 .1518 .1770
34 .1236 .1295 .1373 .1497 .1747
35 .1220 .1278 .1356 .1478 .1720
36 .1203 .1260 .1336 .1454 .1695
37 .1188 .1245 .1320 .1436 .1677
38 .1174 .1230 .1303 .1421 .1653
39 .1159 .1214 .1288 .1402 .1634
40 .1147 .1204 .1275 .1386 .1616
41 .1131 .1186 .1258 .1373 .1599
42 .1119 .1172 .1244 .1353 .1573
43 .1106 .1159 .1228 .1339 .1556
44 .1095 .1148 .1216 .1322 .1542
45 .1083 .1134 .1204 .1309 .1525
46 .1071 .1123 .1189 .1293 .1512
47 .1062 .1113 .1180 .1282 .1499
48 .1047 .1098 .1165 .1269 .1476
49 .1040 .1089 .1153 .1256 .1463
50 .1030 .1079 .1142 .1246 .1457
0.741 0.775 0.819 0.895 1.035
> 50
f N f N f N f N f N
10
Overview
The normality assumption is at the core of a majority of standard
statistical procedures, and it is important to be able to test this
assumption. In addition, showing that a sample does not come
from a normally distributed population is sometimes of impor-
tance per se. Among the many procedures used to test this as-
sumption, one of the most well-known is a modi?cation of the
Kolomogorov-Smirnov test of goodness of ?t, generally referred to
as the Lilliefors test for normality (or Lilliefors test, for short). This
test was developed independently by Lilliefors (1967) and by Van
Soest (1967). The null hypothesis for this test is that the error is
normally distributed (i.e., there is no difference between the ob-
served distribution of the error and a normal distribution). The
alternative hypothesis is that the error is not normally distributed.
Like most statistical tests, this test of normality de?nes a cri-
terion and gives its sampling distribution. When the probability
associated with the criterion is smaller than a given a-level, the
1
In: Neil Salkind (Ed.) (2007). Encyclopedia of Measurement and Statistics.
Thousand Oaks (CA): Sage.
Address correspondence to: Hervé Abdi
Programin Cognition and Neurosciences,MS: Gr.4.1,
The University of Texas at Dallas,
Richardson, TX 75083–0688, USA
E-mail: herve@utdallas.edu http://www.utd.edu/~herve
1
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
alternative hypothesis is accepted (i.e., we conclude that the sam-
ple does not come from a normal distribution). An interesting pe-
culiarity of the Lilliefors’ test is the technique used to derive the
sampling distribution of the criterion. In general, mathematical
statisticians derive the sampling distribution of the criterion us-
ing analytical techniques. However in this case, this approach fails
and consequently, Lilliefors decided to calculate an approximation
of the sampling distribution by using the Monte-Carlo technique.
Essentially, the procedure consists of extracting a large number of
samples fromaNormal Population and computing the value of the
criterion for each of these samples. The empirical distribution of
the values of the criterion gives an approximation of the sampling
distribution of the criterion under the null hypothesis.
Speci?cally, both Lilliefors and Van Soest used, for each sample
size chosen, 1000 random samples derived from a standardized
normal distribution to approximate the sampling distribution of a
Kolmogorov-Smirnov criterion of goodness of ?t. The critical val-
ues given by Lilliefors and Van Soest are quite similar, the relative
2
error being of the order of 10- .
According to Lilliefors (1967) this test of normality ismore pow-
erful than others procedures for a wide range of nonnormal con-
ditions. Dagnelie (1968) indicated, in addition, that the critical
values reported by Lilliefors can be approximated by an analyti-
cal formula. Such a formula facilitates writing computer routines
because it eliminates the risk of creating errors when keying in the
values of the table. Recently, Molin and Abdi (1998), re?ned the
approximation given by Dagnelie and computed new tables using
a larger number of runs (i.e., K = 100,000) in their simulations.
2 Notation
The sample for the test ismade of N scores, each of themdenoted
X i. The samplemean is denoted M X is computed as
N
1
M X = X i, (1)
N
i
2
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
the sample variance is denoted
N 2
(X i -M X)
2 i
S , (2)
X = N -1
and the standard deviation of the sample denoted S X is equal to
the square root of the sample variance.
The ?rst step of the test is to transform each of the X i scores
into Z-scores as follows:
X i M X
Z i = - . (3)
S X
For each Z i-score we compute the proportion of score smaller
or equal to its value: This is called the frequency associated with
this score and it is denoted S (Z i). For each Z i-score we also com-
pute the probability associated with this score if is comes from a
“standard” normal distribution with a mean of 0 and a standard
deviation of 1. We denote this probability byN (Z i), and it is equal
to Z 1 1
i
2
N (Z i) = exp - Z i . (4)
-8 2p 2
The criterion for the Lilliefors’ test is denoted . It is calculated L
fromthe Z-scores, and it is equal to
L =max{|S (Z i)-N (Z i)|, |S (Z i)-N (Z i 1) } . (5)
i - |
So is the absolute value of the biggest split between the proba- L
bility associated to Z i when Z i is normally distributed, and the fre-
quencies actually observed. The term|S (Z i)-N (Z i-1)| is needed
to take into account that, because the empirical distribution is dis-
crete, the maximum absolute difference can occur at either end-
points of the empirical distribution.
The critical values are given by Table 2. critical is the critical L
value. TheNull hypothesis is rejectedwhen the criterion is greater L
than or equal to the critical value critical. L
3
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
3 Numerical example
As an illustration, we will look at an analysis of variance exam-
ple for which we want to test the so-called “normality assump-
tion” that states that the within group deviations (i.e., the “resid-
uals”) are normally distributed. The data are from Abdi (1987, p.
93ff.) and correspond to memory scores obtained by 20 subjects
who were assigned to one of 4 experimental groups (hence 5 sub-
jects per group). The score of the sth subject in the ath group is
denoted Y a,s, and the mean of each group is denoted M a.. The
within-group mean square MS S(A) is equal to 2.35, it correspond
to the best estimation of the population error variance.
G. 1 G. 2 G. 3 G. 4
3 5 2 5
3 9 4 4
2 8 5 3
4 4 4 5
3 9 1 4
Y a. 15 35 16 21
M a. 3 7 3.2 4.2
TheNormality assumption states that the error is normally dis-
tributed. In the analysis of variance framework, the error corre-
sponds to the residuals which are equal to the deviations of the
scores to themean of their group. So in order to test the normality
assumption for the analysis of variance, the ?rst step is to com-
pute the residuals from the scores. We denote X i the residual cor-
responding to the i th observation (with i going from 1 to 20). The
residuals are given in the following table:
Y as 3 3 2 4 3 5 9 8 4 9
X i 0 0 -1 1 0 -2 2 1 -3 2
Y as 2 4 5 4 1 5 4 3 5 4
X i -1.2 .8 1.8 .8 -2.2 .8 -.2 -1.2 .8 -.2
4
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
Next we transform the X i values into Z i values using the fol-
lowing formula:
X i
Z i = (6)
MS S(A)
because MS S(A) is the best estimate of the population variance,
and the mean of X i is zero. Then, for each Z i value, the frequency
associated with S (Z i) and the probability associated with Z i un-
der the Normality condition N (Z i) are computed [we use a table
of the Normal Distribution to obtain N (Z i)]. The results are pre-
sented in Table 1.
The value of the criterion is (see Table 1)
L =max{|S (Z i)-N (Z i)|, |S (Z i)-N (Z i 1) } .250 . (7)
i - | =
Taking an a level of a = .05, with N = 20, we ?nd (from Table 2)
that the critical value is equal critical = .192. Because is larger L L
than critical, the null hypothesis is rejected and we conclude that L
the residuals in our experiment are not distributed normally.
4 Numerical approximation
The available tables for the Lilliefors’ test of normality typically re-
port the critical values for a small set of alpha values. For example,
the present table reports the critical values for
a = [.20, .15, .10, .05, .01].
These values correspond to the alpha values used for most tests
involving only one null hypothesis, as this was the standard pro-
cedure in the late sixties. The current statistical practice, however,
favors multiple tests (maybe as a consequence of the availability
of statistical packages). Because usingmultiple tests increases the
overall Type I error (i.e., the Familywise Type I error or a PF), it has
become customary to recommend testing each hypothesis with a
corrected a level (i.e., the Type I error per comparison, or a PC)
such as the Bonferonni or Sidák corrections. For example, using ?
a Bonferonni approach with a familywise value of a PF = .05, and
5
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
Table 1: How to compute the criterion for the Lilliefors’ test of
normality. N i stands for the absolute frequency of a given value
of X i, F i stands for the absolute frequency associated with a given
value of X i (i.e., the number of scores smaller or equal to X i),
Z i is the Z-score corresponding to X i, S (Z i) is the proportion of
scores smaller than Z i, N (Z i) is the probability associated with
Z i for the standard normal distribution, D 0 =| S (Z i) -N (Z i) |,
D -1=| S (Z i)-N (Z i-1) |, and max is the maximum of {D 0,D -1}.
The value of the criterion is = .250. L
X i N i F i Z i S (Z i) N (Z i) D 0 D -1 max
-3.0 1 1 -1.96 .05 .025 .025 .050 .050
-2.2 1 2 -1.44 .10 .075 .025 .075 .075
-2.0 1 3 -1.30 .15 .097 .053 .074 .074
-1.2 2 5 -.78 .25 .218 .032 .154 .154
-1.0 1 6 -.65 .30 .258 .052 .083 .083
-.2 2 8 -.13 .40 .449 .049 .143 .143
.0 3 11 .00 .55 .500 .050 .102 .102
.8 4 15 .52 .75 .699 .051 .250 .250
1.0 2 17 .65 .85 .742 .108 .151 .151
1.8 1 18 1.17 .90 .879 .021 .157 .157
2.0 2 20 1.30 1.00 .903 .097 .120 .120
testing J = 3 hypotheses requires that each hypothesis is tested at
the level of
1 1
a a
PC= J PF = 3×.05 = .0167 . (8)
With a Sidák approach, each hypothesis will be tested at the level ?
of
1 1
J 3
a a
PC= 1-(1- PF) = 1-(1-.05) = .0170 . (9)
As this example illustrates, both procedures are likely to require us-
ing different a levels than the ones given by the tables. In fact, it is
rather unlikely that a table could be precise enough to provide the
wide range of alpha values needed formultiple testing purposes. A
6
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
more practical solution is to generate the critical values for any al-
pha value, or, alternatively, to obtain the probability associated to
any value of the Kolmogorov-Smirnov criterion. Such an approach
can be implemented by approximating the sampling distribution
“on the ?y" for each speci?c problemand deriving the critical val-
ues for unusual values of a.
Another approach to ?nding critical values for unusual values
of a, is to ?nd a numerical approximation for the sampling distri-
butions. Molin and Abdi (1998) proposed such an approximation
and showed that it was accurate for at least the ?rst two signi?-
cant digits. Their procedure, somewhat complex, is better imple-
mented with a computer and comprises two steps.
The ?rst step is to compute a quantity called A obtained from
the following formula:
2 L 2
-(b 1+N)+ (b 1+N) -4b 2 b 0- -
A = , (10)
2b 2
with
b 2= 0.08861783849346
b 1= 1.30748185078790
b 0= 0.37872256037043 . (11)
The second step implements a polynomial approximation and
estimates the probability associated to a given value as: L
Pr( ) ˜ -.37782822932809+1.67819837908004A L
2 3
-3.02959249450445A +2.80015798142101A
4 5
-1.39874347510845A +0.40466213484419A
6 7
-0.06353440854207A +0.00287462087623A
8 9
+0.00069650013110A -0.00011872227037A
10
+0.00000575586834A . (12)
For example, suppose that we have obtained a value of = L
.1030 froma sample of size N = 50. (Table 2 shows that Pr( ) = .20.) L
7
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
To estimate Pr( ) we need ?rst to compute A, and then use this L
value in Equation 12. FromEquation 10, we compute the estimate
of A as:
2 L 2
-(b 1+N)+ (b 1+N) -4b 2 b 0- -
A =
2b 2
2 2
-(b 1+50)+ (b 1+50) -4b 2 b 0-.1030-
=
2b 2
= 1.82402308769590 . (13)
Plugging in this value of A in Equation 12 gives
Pr( ) = .19840103775379 ˜ .20 . (14) L
As illustrated by this example, the approximated value of Pr( ) is L
correct for the ?rst two decimal values.
References
[1] Abdi, H. (1987). Introduction au traitement statistique des
données expérimentales. Grenoble: Presses Universitaires de
Grenoble.
[2] Dagnelie, P . (1968). A propos de l’emploi du test de
Kolmogorov-Smirnov comme test de normalité, Biométrie et
Praximétrie 9, 3–13.
[3] Lilliefors, H. W. (1967). On the Kolmogorov-Smirnov test for
normality with mean and variance unknown, Journal of the
American Statistical Association, 62, 399–402.
[4] Molin, P ., Abdi H. (1998). New Tables and nu-
merical approximation for the Kolmogorov-
Smirnov/Lillierfors/Van Soest test of normality. Tech-
nical report, University of Bourgogne. Available from
www.utd.edu/~herve/MA_Lilliefors98.pdf.
[5] Van Soest, J. (1967). Some experimental results concerning
tests of normality. Statistica. Neerlandica, 21, 91–97, 1967.
8
Table 2: Table of the critical values for the Kolmogorov-Smir-
nov/Lillefors test of normality obtained with K = 100,000 samples
for each sample size. The intersection of a given row and column
shows the critical value critical for the sample size labelling the row L
and the alpha level labelling the column. For N > 50 the critical
.83 N
value can be found by using f N=+ -.01.
N
N a = .20 a = .15 a = .10 a = .05 a = .01
4 .3027 .3216 .3456 .3754 .4129
5 .2893 .3027 .3188 .3427 .3959
6 .2694 .2816 .2982 .3245 .3728
7 .2521 .2641 .2802 .3041 .3504
8 .2387 .2502 .2649 .2875 .3331
9 .2273 .2382 .2522 .2744 .3162
10 .2171 .2273 .2410 .2616 .3037
11 .2080 .2179 .2306 .2506 .2905
12 .2004 .2101 .2228 .2426 .2812
13 .1932 .2025 .2147 .2337 .2714
14 .1869 .1959 .2077 .2257 .2627
15 .1811 .1899 .2016 .2196 .2545
16 .1758 .1843 .1956 .2128 .2477
17 .1711 .1794 .1902 .2071 .2408
18 .1666 .1747 .1852 .2018 .2345
19 .1624 .1700 .1803 .1965 .2285
20 .1589 .1666 .1764 .1920 .2226
21 .1553 .1629 .1726 .1881 .2190
22 .1517 .1592 .1690 .1840 .2141
23 .1484 .1555 .1650 .1798 .2090
24 .1458 .1527 .1619 .1766 .2053
25 .1429 .1498 .1589 .1726 .2010
26 .1406 .1472 .1562 .1699 .1985
27 .1381 .1448 .1533 .1665 .1941
28 .1358 .1423 .1509 .1641 .1911
Table continues on the following page . . .
H. Abdi & P .Molin: Lilliefors / Van Soest Normality Test
Table 3: . . . Continued. Table of the critical values for the Kolmogo-
rov-Smirnov/Lillefors test of normality obtained with K = 100,000
samples for each sample size. The intersection of a given row and
column shows the critical value critical for the sample size labelling L
the row and the alpha level labelling the column. For N > 50 the
.83 N
critical value can be found by using f N=+ -.01.
N
N a = .20 a = .15 a = .10 a = .05 a = .01
29 .1334 .1398 .1483 .1614 .1886
30 .1315 .1378 .1460 .1590 .1848
31 .1291 .1353 .1432 .1559 .1820
32 .1274 .1336 .1415 .1542 .1798
33 .1254 .1314 .1392 .1518 .1770
34 .1236 .1295 .1373 .1497 .1747
35 .1220 .1278 .1356 .1478 .1720
36 .1203 .1260 .1336 .1454 .1695
37 .1188 .1245 .1320 .1436 .1677
38 .1174 .1230 .1303 .1421 .1653
39 .1159 .1214 .1288 .1402 .1634
40 .1147 .1204 .1275 .1386 .1616
41 .1131 .1186 .1258 .1373 .1599
42 .1119 .1172 .1244 .1353 .1573
43 .1106 .1159 .1228 .1339 .1556
44 .1095 .1148 .1216 .1322 .1542
45 .1083 .1134 .1204 .1309 .1525
46 .1071 .1123 .1189 .1293 .1512
47 .1062 .1113 .1180 .1282 .1499
48 .1047 .1098 .1165 .1269 .1476
49 .1040 .1089 .1153 .1256 .1463
50 .1030 .1079 .1142 .1246 .1457
0.741 0.775 0.819 0.895 1.035
> 50
f N f N f N f N f N
10
Learning to Solve Stochastic Shortest Path Problems
Learning to Solve
Stochastic Shortest Path Problems
Mohsen Jamali
Semantic Web Research Laboratory,
Computer Engineering Department,
Sharif University Of Technology, Tehran, Iran
m jamali@ce.sharif.edu
Abstract.
Di?erent classes of Stochastic Shortest Path (SSP) problems
are considered in literatue. In this paper we’ll consider a special case
in which edges’ costs have probabilistic distribution. We try to learn the
expectes cost for each cost and so we learn the shortest path from a node
v s to a destination node v d. Our algorithm is somehow like Dijkstra’s
algorithm, but it just uses local knowledges.
1 Introduction
The class of Stochastic Shortest Path (SSP) problems is a subset of Markov
Decision Processes (MDPs) that is of central importance to AI: they are the
natural generalization of the classic search model to the case of stochastic tran-
sitions and general cost functions. SSPs had been recently used to model a broad
range of problems going from robot navigation and control of non-deterministic
systems to stochastic game-playing and planning under uncertainty and partial
information. [1]
The theory of MDPs had received great attention from the AI community for
three important reasons. First, it provides an easy framework for modeling com-
plex real-life problems that have large state-space (even in?nite) and complex dy-
namics and cost functions. Second, MDPs provide mathematical foundation for
independently-developed learning algorithms in Reinforcement Learning. And
third, general and e?cient algorithms for solving MDPs had been developed,
the most important being Value Iteration and Policy Iteration.
As the name suggests, an SSP problem is an MDP problem that has positive
costs and an absorbing goal state. A solution for an SSP is a strategy that leads
to the goal with minimum expected cost from any other state. Quite often, we
are only interested in how to get to the goal from a ?xed initial state instead
of knowing the general solution; the reason being that the state space usually
contains many states that are irrelevant.
2 Problem De?nition
A stochastic graph G is de?ned by triple G = (V,E, F) where V = {1, 2, . . . , n} is
set of nodes, E subset V ×V , and n×n matrix F is the probability distribution
2
describing the statistics of edge costs. In particular, cost C ij of edge (i, j) is
assumed to be a random variable with f ij as it probability density function,
which is assumed to be unknown. It is assumed that distribution f ij is not known
a priori. In stochastic graph G, a path p i with length of n i nodes and expected
cost of L p i from source node v s to destination node v d is de?ned as an ordering
{p i,1, p i,2, . . . , p i,n i } ? V in such a way that v p i,1 = v s and v p i,ni = v d are
source and destination nodes, respectively and (p i,j, p i,j+1) ? E for 1 = j < n i,
th
where p i,j is the j node in the path p i. Assume that there are r distinct paths
? = {p 1, p 2, . . . , p r} between v s and v d. The shortest path between source node
v s and destination node v d denoted by v s v d is de?ned as a path with minimum
*
expected cost. In other word, the shortest path p has cost of L p *= min p??L p.
In our problem we want to ?nd such shortest paths.
3 Related Works
Di?erent classes of stochastic optimal path problems are considered in the liter-
ature. The ?rst work known in this area is due to Frank [2] where the shortest
optimal path over a probabilistic graph is determined. The most common crite-
rion to determine the optimal path is the one that maximizes the expected value
of an utility function. This criterion stems from the formulation presented by
Von-Newman-Morgenstern where evaluations should be made under uncertainty
[3]. Algorithms for the linear and quadratic utility functions have been presented
by Mirchandini and Soroush [3], Murthy and Sarkar [4, 5] and more recently by
Deolinda Dias Rasteiro, Antonio Batel Anjo anf Helena Ramalhinho Lourenco
[6].
3.1 Solving Stochastic Shortest-Path Problems with RTDP
Formally, an MDP is de?ned by :
– A ?nite state space S = {1, . . . , n}
– A ?nite set of controls U(i) for each state i ? S,
– Transition probabilities p(i, u, j) for all u ? U(i) that are equal to the prob-
ability of the next state being j after applying control u in state i,
– A cost g(i, u) associated to u ? U(i) and i ? S [7]
Blai Bonet and Hector Ge?ner [7] used Real-Time Dynamic Programming (RTDP)
to solve SSP. Their problem de?nition is somehow di?erent from our prob-
lem, but generally, they also solve SSP problems. In their problem, A sto-
chastic shortest-path problem is an MDP problem in which the state space
S = {1, . . . , n, t} is such that t is a goal (target) state that is absorbing (i.e.,
p(t, u, t) = 1 and g(t, u) = 0 for all u ? U(t)), and the discount factor a = 1. In
this case, the existence of optimal policies (and optimal stationary policies) is a
major mathematical problem.
Real-Time Dynamic Programming (RTDP) [8] is an algorithm for ?nding short-
est paths. However, RTDP is a probabilistic algorithm that only converges symp-
totically. Hence, although there has been experimental results showing that
3
RTDP converges faster than other algorithms, it cannot be used as an o?-line
algorithm.
RTDP is a probabilistic algorithm that computes a partial optimal policy by
performing successive walks (also called trials) on the state space. Each trial
starts at the initial state 1 and ?nishes at the goal state t. At all times k, the
*
RTDP algorithm maintains an approximation J k to J that is used to greedly
select a control u k to apply in the current state x k. Initially, J 0 is implicitly
stored as an heuristic function h(.). Then, every time a control u k is selected in
state x k, a new approximation J k+1 is computed as J k+1(x) = J k(x) if x= x k,
and n
J k+1(x k) = g(x k, u k) p(x k, u k, i)J k(i)
i=1
3.2 Stochastic Shortest Path Problems with Piecewise-Linear
Concave Utility Functions
Ishwar Murthy and Sumit Sarkar [5] considered a stochastic shortest path prob-
lem where the arc lengths are independent random variables following a normal
distribution. In this problem, the optimal path is one that maximizes the ex-
pected utility, with the utility function being piecewise-linear and concave. Such
a utility function can be used to approximate nonlinear utility functions that
capture risk adverse behavior for a wide class of problems. The principal con-
tribution of their work is the development of exact algorithms to solve large
problem instances. Two algorithms are developed and incorporated in labelling
procedures. Computational testing is done to evaluate the performance of the
algorithms. Overall, both algorithms are very e?ective in solving large problems
quickly. The relative performance of the two algorithms is found to depend on
the ”curvature” of the piecewise linear utility function.
3.3 Shortest Paths’ Probability Distribution in Probabilistic
Graphs
H. Frank [2] also considers the problem of ?nding shortest-path probability dis-
tribution in graphs whose branches are weighted with random lengths, examines
the consequences of various assumptions concerning the nature of the available
statistical information, and gives an exact method for computing the probabil-
ity distribution, as well as methods based on hypothesis testing and statistical
estimation.
4 Our Proposed Algorithm
In our problem, we do not have the probability distributions for edges’ cost. If we
had these distributions the solution was trivial, we just calculated the expected
value of each edge’s cost from its probability distribution, and then we used
Dijkstra’s algorithm to ?nd the shortest path. The algorithm we propose tries
to solve the problem de?ned in section 2 by learning about estimations of each
4
edge’s cost. Our algorithm learns these estimations iteratively. Each node in the
graph has edges to its neighbors, except for the destination node. Each edge’s
cost has its own probability distribution. Each node also has estimations of the
shortest path’s length(cost) to the destination node which should be learned an
updated, and also the node learns the estimated cost of its edges to the neighbors.
In our algorithm a walker starts to traverse the graph from the source node to the
destination node. The walker, at each node n selects the edge (n,m) which leads
to the smallest estimated cost from node n to the destination node according to
node’s knowledge about costs’ estimate in this step.
*
m = arg min {C + est } (1)
nj j
j?V,(n,j)?E
*
where C is the estimated(learned) cost about the edge (n, j) and est is the
nj j
estimation learned about the least cost to reach destination node from node j.
V and E are respectively the set of nodes and edge as de?ned in section 2. We
use - Greedy algorithm so that in each node there is probability to select a
random node in neighborhood. The probability of randomly selecting a neighbor
decreases in each step as cost estimations are learned.
While traversing the graph, each edge’s estimated cost will be updated and
learned. When passing an edge we would have a cost with a probability distrib-
ution assigned to it. So we update our estimation about edge’s cost as following
*
k × C (k) + C ij
* ij
C (k + 1) = (2)
ij
k + 1
* th
C (k) represents our estimation for the cost of edge (i, j) in k step. C is
ij ij
the cost paid after traversing the edge (i, j) which has probabilistic distribution.
Actually we replace our estimated cost with the weighted mean of the previous
estimated cost and the newly paid cost.
The walker, ?nally, reaches the destination node (we do not let it to traverse
visited nodes to avoid falling in loops, so we always reach the ?nal destination).
When the walker arrives to the destination node we update the estimated cost
for each node to reach the destination node:
*
est i = min C ij+ est j (3)
(i,j)?E
We continue iterations until there is no change or the mean amount of change is
less than a constant.
5 Experimental Results
In order to evaluate the performance of our algorithm, we simulated our algo-
rithm on the following four stochastic graphs.
– Graph 1 which is shown in ?gure 1 is a graph with 10 nodes and 23 edges,
v s = 1, and v d = 10. The cost of each edge is a random variable with
exponential distribution. The label given to each edge of graph given in
?gure 1 is the mean of its exponential distribution.
5
– Graph 2 is a graph with 10 nodes, 23 edges, v s= 1, and v d= 10. Edge cost
distribution is given in table 1.
– Graph 3 is a graph with 10 nodes, 23 edges, v s= 1, and v d= 10. Edge cost
distribution is given in table 2.
– Graph 2 is a graph with 15 nodes, 42 edges, v s= 1, and v d= 15. Edge cost
distribution is given in table 3.
Fig. 1. Graph 1 to be used in experiments
We evaluate each run of the algorithm on the above graphs by comparing
the result with the results using Dijkstra’s algorithm. In fact the best estimate
for the shortest path algorithm is the Dijkstra’s algorithm, but we assume that
we don not have the distributions and try to learn the expected costs by local
knowledges. In our experiments we assigned a default number (10) to all esti-
mations (estimations for edge’s cost and estimations for a node’s cost to reach
the destination node). The number of iterations for each run is set to 1000.
We ran the algorithm 10 times for each Graph. Table 4 shows the results of our
experiments. Each row of the table shows the results of each graph. Columns
contain paths identi?ed by our Algorithm and Dijkstra’s algorithm. Also there
are two columns for residuals. The values in colums are mean of the values in 10
runs of the algorithm. Edge Cost residual is the error in ?nding the edges’ costs * 2
(C - C ij)
(i,j)?E ij
Edge Cost Residual = (4)
|E|
*
where C is our learned cost for the edge (i, j) and C is the expected value of
ij ij
the edge’s cost according to its distribution. Path Length Residual is the error
6
Edge Lengths(Costs) Probabilities
( 1 , 2 ) 7 7.3 9.4 0.2 0.5 0.3
( 1 , 3 ) 2.5 3.5 8.2 0.5 0.4 0.1
( 1 , 4 ) 4.2 4.8 6.1 0.2 0.3 0.5
( 2 , 5 ) 2.6 3.1 5.5 8.8 9 0.1 0.2 0.4 0.2 0.1
( 2 , 6 ) 5.8 7 9.5 0.3 0.3 0.4
( 3 , 2 ) 1.5 7.3 0.4 0.6
( 3 , 7 ) 6.5 7.4 7.5 0.4 0.5 0.1
( 3 , 8 ) 5.9 7.2 9.8 0.6 0.3 0.1
( 4 , 3 ) 2.1 3.2 8.5 9.8 0.3 0.2 0.3 0.2
( 4 , 9 ) 8.9 9.6 0.7 0.3
( 5 , 7 ) 3.2 4.8 6.7 0.2 0.2 0.6
( 8 , 4 ) 9 9.6 0.5 0.5
( 5 , 10 ) 6.3 6.9 0.5 0.5
( 6 , 5 ) 0.6 1.5 3.9 5.8 0.1 0.4 0.3 0.2
( 7 , 8 ) 1.6 1.8 4 5.2 0.2 0.3 0.3 0.2
( 8 , 9 ) 1.7 4.9 5.3 6.5 0.1 0.4 0.4 0.1
( 9 , 10 ) 0.6 1.2 5.4 6.6 0.1 0.1 0.3 0.5
( 7 , 6 ) 6.1 6.3 8.5 0.2 0.3 0.5
( 6 , 3 ) 6.5 8.5 9.8 0.8 0.1 0.1
( 7 , 10 ) 1.6 3.4 7.1 0.1 0.5 0.4
( 8 , 7 ) 2.1 4.6 8.5 0.3 0.4 0.3
( 7 , 9 ) 0.3 0.3 5 0.1 0.1 0.5
Table 1. Weight Distribution of Graph 2 with v s= 1 and v d= 10
in ?nding the cost to reach destination node from di?erent start nodes: * 2
(est - est i)
i?V i
Path Length Residual = (5)
|V |
*
est is our learned cost for the shortest path from node i to the destination
i
v d, and est i is the expected cost for the shortest path computed by Dijkstra’s
algorithm.
Comparing the results shows that our algorithm’s results are very similar to the
Dijkstra’s algorithm. The shortest path identi?ed by our algorithm are exactly
the same as paths identi?ed by Dijkstra’s algorithm. So our algorithm learns
well and results are satisfying (Precisions for ?nding the shortest path is 100%,
and the errors are usually low for edges’ expected costs).
Figure 2 shows the rate of convergence of our algorithm to the results of Dijk-
stra’s algorithm in di?erent iteratios. After each iteration we compute the ratio
of our algorithm’s estimation for the shortest path to the Dijkstra’s results (
est v s / est v s). Figure 2 shows just the rate for the ?st 100 iterations. After the
100the iteration the variance of the rate is nearly 0 and we didn’t show the rest
of the Diagram.
7
Edge Lengths(Costs) Probabilities
( 1 , 2 ) 3 5.3 7.4 9.4 0.2 0.2 0.3 0.2
( 1 , 3 ) 3.5 6.2 7.9 8.5 0.3 0.3 0.2 0.2
( 1 , 4 ) 4.2 6.1 6.9 8.9 0.2 0.3 0.2 0.3
( 2 , 5 ) 2.6 4.1 5.5 9 0.2 0.2 0.4 0.2
( 2 , 6 ) 5.8 7 8.5 9.6 0.3 0.3 0.2 0.2
( 3 , 2 ) 1.5 2.3 3.6 4.5 0.2 0.2 0.3 0.3
( 3 , 7 ) 6.5 7.2 8.3 9.4 0.5 0.2 0.2 0.1
( 3 , 8 ) 5.9 7.8 8.6 9.9 0.4 0.3 0.1 0.2
( 4 , 3 ) 2.1 3.2 4.5 6.8 0.2 0.2 0.3 0.3
( 4 , 9 ) 1.1 2.2 3.5 4.3 0.2 0.3 0.4 0.1
( 5 , 7 ) 3.2 4.8 6.7 8.2 0.2 0.2 0.3 0.3
( 5 , 10 ) 6.3 7.8 8.4 9.1 0.2 0.2 0.4 0.2
( 6 , 3 ) 6.8 7.7 8.5 9.6 0.4 0.1 0.1 0.4
( 6 , 5 ) 0.6 1.5 3.9 5.8 0.2 0.2 0.3 0.3
( 6 , 7 ) 2.1 4.8 6.6 7.5 0.2 0.4 0.2 0.2
( 7 , 6 ) 4.1 6.3 8.5 9.3 0.2 0.3 0.3 0.2
( 7 , 8 ) 1.6 2.8 5.2 6 0.2 0.3 0.3 0.2
( 7 , 10 ) 1.6 3.4 8.2 9.3 0.2 0.3 0.3 0.2
( 8 , 4 ) 7 8 8.8 9.4 0.2 0.2 0.2 0.4
( 8 , 7 ) 2.1 4.6 8.5 9.6 0.4 0.2 0.2 0.2
( 8 , 9 ) 1.7 4.9 6.5 7.8 0.2 0.2 0.2 0.4
( 7 , 9 ) 3.5 4 5 7.7 0.1 0.2 0.4 0.3
( 9 , 10 ) 4.6 6.4 7.6 8.9 0.4 0.1 0.2 0.3
Table 2. Weight Distribution of Graph 3 with v s= 1 and v d= 10
6 Conclusion
In this paper we tried to learn estimation for each edge’s cost in stochastic
weighted graph from local knowledges. The results show that our experiment is
satisfyig and the walker learns successfully. I’d like to thank H. Beigy for his
comments on the problem.
References
1. Bonet, B., Ge?ner, H.: Planning with incomplete information as heuristic search in
belief space. In: Proceedings of AIPS-2000, (Breckenridge, CO, USA)
2. Frank, H.: Shortest paths in probabilistic graphs. Operations Research 17 (1969)
583–599
3. Loui, R.P.: Optimal paths in graphs with stochastic or multidimensional weights.
Communications of the ACM 26 (1983) 670–676
4. Murthy, I., Sarkar, S.: A relaxation based prunning technique for a class of stochastic
shortest path problems. Transportation Science 30(3) (1996) 220–236
5. Murthy, I., Sarkar, S.: Stochastic shortest path problems with piecewise linear
concave utility functions. Management Science 44(11) (1998) 125–136
8
Fig. 2. Convergence Rate of Our Algorithm to Dijkstra’s Algorithm
6. Rasteiro, D.M., Anjo, A.B.: Metaheuristics for stochastic shortest path problem.
In: Proceedings of 4th MetaHeuristics International Conference (MIC2001), (Porto,
Portugal)
7. Bonet, B., Ge?ner, H.: Solving stochastic shortest-path problems with rtdp. Tech-
nical report, Universidad Simon Bolivar (2002)
8. Barto, A., Bradtke, S., Singh, S.: Learning to act using real-time dynamic program-
ming. Arti?cial Intelligence 72 (1995) 81–138
9
Edges Lengths(Costs) Probabilities
( 1 , 2 ) 16 25 36 0.6 0.3 0.1
( 1 , 4 ) 11 13 26 0.4 0.4 0.2
( 2 , 11 ) 24 28 31 0.5 0.3 0.2
( 2 , 6 ) 13 37 39 0.6 0.2 0.2
( 3 , 2 ) 11 20 24 0.6 0.3 0.1
( 3 , 7 ) 23 30 34 0.4 0.3 0.3
( 3 , 8 ) 14 23 34 0.5 0.4 0.1
( 6 , 7 ) 11 31 37 0.5 0.4 0.1
( 6 , 5 ) 18 25 29 0.5 0.3 0.2
( 5 , 10 ) 27 33 40 0.4 0.3 0.3
( 4 , 12 ) 16 25 37 0.5 0.4 0.1
( 13 , 15 ) 12 31 0.9 0.1
( 2 , 5 ) 11 30 0.7 0.3
( 10 , 14 ) 23 34 0.9 0.1
( 4 , 3 ) 22 30 0.7 0.3
( 4 , 9 ) 35 40 0.6 0.4
( 12 , 9 ) 16 22 0.7 0.3
( 5 , 15 ) 25 32 0.7 0.3
( 6 , 13 ) 21 23 0.5 0.5
( 6 , 3 ) 18 24 0.7 0.3
( 7 , 10 ) 19 23 37 0.6 0.2 0.2
( 7 , 6 ) 12 23 31 0.5 0.3 0.2
( 8 , 7 ) 14 34 39 0.6 0.2 0.2
( 8 , 9 ) 13 31 32 0.8 0.1 0.1
( 8 , 4 ) 13 23 34 0.4 0.3 0.3
( 9 , 7 ) 10 17 20 0.6 0.3 0.1
( 9 , 14 ) 19 24 29 0.4 0.3 0.3
( 10 , 15 ) 15 19 25 0.4 0.3 0.3
( 11 , 13 ) 13 31 25 0.6 0.3 0.1
( 11 , 6 ) 10 19 39 0.5 0.4 0.1
( 14 , 15 ) 14 19 32 0.5 0.3 0.2
( 12 , 8 ) 15 36 39 0.5 0.3 0.2
( 7 , 8 ) 12 15 22 24 0.3 0.3 0.2 0.2
( 10 , 13 ) 14 20 25 32 0.3 0.3 0.2 0.2
( 5 , 7 ) 15 17 19 26 0.3 0.3 0.3 0.1
( 8 , 14 ) 14 15 27 32 0.3 0.3 0.2 0.2
( 9 , 15 ) 12 13 25 32 0.4 0.3 0.2 0.1
( 9 , 10 ) 16 18 36 39 0.3 0.3 0.2 0.2
( 11 , 5 ) 18 19 29 23 0.3 0.3 0.3 0.1
( 5 , 13 ) 28 35 37 40 0.4 0.3 0.2 0.1
( 1 , 3 ) 21 24 25 39 0.5 0.2 0.2 0.1
( 12 , 14 ) 10 13 18 34 0.3 0.3 0.3 0.1
Table 3. Weight Distribution of Graph 4 with v s= 1 and v d= 15
10
Graph Learned Learned Shortest Path Dijkstra’s Edge Cost Path
Shortest Path Shortest Cost By Dijkstra Shortest Residual Length
Length Residual
Graph 1 1 3 8 10 35.12 1 3 8 10 34 0.15 0.51
Graph 2 1 3 7 10 15.24 1 3 7 10 14.57 0.16 0.21
Graph 3 1 4 9 10 16.23 1 4 9 10 16.1 0.16 0.11
Graph 4 1 2 5 15 64.98 1 2 5 15 64.5 0.75 0.37
Table 4. Results of our algorithm with Dijkstra’s algorithm
Langganan:
Postingan (Atom)