Transcript java.util

Some Uses of Probability
• Randomized algorithms
– for CS in general
– for games and robotics in particular
• Testing
• Simulation
• Solving probabilistic problems by
simulation
Random Number Generators
• Random Number Generators
– Actually pseudo-random
– Seed
• Same sequence from same seed
• Often time is used.
• Many examples on web.
• Custom random number generators exist.
• Can be used in algorithms.
A Simple Random Number
Generator
random_seed =
random_seed * 1103515245 +12345;
r = (int)(random_seed / 65536) % 32768;
Java Random Numbers
• double x= Math.random()
– Generates a random double value in the
range from 0.0 up to, but not including 1.
– That calculation uses the current time of day
to seed the random number generator such
that each execution of a program yields a
different sequence of random values.
Scaling
• double x = (B – A) * Math.random + A
– Gives double value A  num < B
• int n = (int) ((B – A) * Math.random()) + A
– Gives integer value A  num < B
Java Random Class
•
•
•
•
import java.util.Random;
Random g = new Random();
Random g2 = new Random(19580427);
int r = g.nextInt();
– value any int
• int r = g.nextInt(n);
– value 0  r < n
• double r = g.nextDouble()
– value 0  r < 1
Quality of Generators
• Java implementation so so.
– Careful about successive calls using time to
set seed if calls will be within 1 millisecond of
each other
• Best probably Mersenne Twister
– available on net to replace Random
Actions Based on Probabilities
• Assign probabilities to each action.
• Probabilities must add to 1.
• Roulette wheel method
– Range of random number generator is size of
roulette wheel.
– Give each action a section of the roulette
wheel proportional to its probability.
– Generate a random number. (Run the wheel.)
Example
•
•
•
•
•
P(go straight) = 50%
P(turn left) = 30%
P(turn right) = 20%
Use random numbers from 0 – 1.000
Roulette wheel
– 0 ≤ Go straight < .50
– .50 ≤ turn left < .80
– .80 ≤ turn right < 1.00
Random Sequence
Java Shuffle
• The Collections class which can be found
within the java.util namespace provides
two methods which suffle the elements of
a Collection.
– static void shuffle(List<?> list) static void
shuffle(List<?> list, Random rnd)
• Collections.shuffle(sl);
Example
import java.util.*;
public class ShuffleTest{
public static void main(String[] args){
List<String> sl = new ArrayList<String>();
sl.add("One");
sl.add("Two");
sl.add("Three");
Collections.shuffle(sl); } }
Sampling (Polling)
• Use random sequence but stop after
needed number.
• Generate random numbers but check for
repetition
Basic Approaches
• Monte Carlo
– the resources used are bounded but the final
result may not be 100% accurate.
• Las Vegas
– always produces the correct result or it
informs about the failure. In other words, it
does not gamble with the verity of the result -- it only gambles with the resources used for
the computation.
Simulated Annealing
• A meta-algorithm for global optimization.
• Meta– details differ for different problems
• Tries to avoid getting stuck in local
optimum.
• Probablistic
• Jumping frog analogy
– frog tires and gets caught by deepest pit
Simulated Annealing (2)
• Use a parameter called the temperature
– Start with a high temperature (frog is fresh)
• Jump
– Replace current solution with a “nearby”
solution that is chosen based on a
temperature dependent transition probability.
• Keep jumping as the temperature is
decreased
– The frog gets tired
Minimizing f
• Transition probability depends on
temperature and the difference of the f
values of the original and the new state.
• For high temperatures, the jump to higher f
is about as likely as the jump to lower f.
(frog is fresh)
• As temperatures lower, the jump to lower f
is much more likely (frog tires)
Simulated Annealing
s := s0; e := E(s) // Initial state, energy.
k := 0 // Energy evaluation count.
while k < kmax and e > emax // While time remains & not
// good enough:
sn := neighbour(s) // Pick some neighbour.
en := E(sn) // Compute its energy.
if random() < P(e, en, temp(k/kmax)) then // Should we
// move to it?
s := sn; e := en // Yes, change state.
k := k + 1 // One more evaluation done
return s // Return current solution