2

I am trying to implement non-uniform probability distribution in genetic algorithm.

In the implementation of genetic program, I have an experiment which has 3 outcomes, where each outcome has different probabilities. Let say, probablity of one outcome is 0.85, other is 0.01 and last one is 0.14?

P.S: i recently came to know that it is called non-uniform distribution of probability. I'm implementing it in Java, can anyone tell the theory behind non-uniform prob. distribution & also any Java packages implementing it.

Feel free to ask me know, if u need any more information on the problem!

Thanks in advance!

Ben S
  • 68,394
  • 30
  • 171
  • 212
Reddy
  • 1,620
  • 6
  • 26
  • 33
  • can you clarify why you need the non-uniform probability distribution? Are you trying to predict the random valeus that your computer generates? Furthermore, in your first sentence you say you're creating a genetic algorithm, while in your second sentence you say you're creating a genetic program... there is a slight difference between the two so it may be good to clarify which one are you implementing. – Kiril Jun 22 '10 at 17:04
  • I mean i am writing a java program implementing genetic Algorithm. I need to implement non-uniform prob is because i need to make a decision on the operation to execute. The operartions here are crossover, mutation & reproduction with 0.85, 0.01 & 0.14 respectively. I think lucas & nailxx answered it! I am assuming their answers as right. Please feel free to let me know if you have another one... – Reddy Jun 23 '10 at 18:30
  • My answer is better http://stackoverflow.com/a/15237795/1698887 – Daniel Williams Mar 07 '13 at 17:44

3 Answers3

9

For a simple discrete distribution, you can write a sampler that will return your outcomes with the desired frequency by using the cumulative probabilities.

Random r = new Random();
double v = r.nextDouble();

if (v <= 0.85) { return 0; }
if (v <= 0.86) { return 1; }
return 2;

This will return the numbers 0, 1 and 2 with a probability of 0.85, 0.01 and 0.14.

As far as the theory on non-uniform probability distributions, you can start with this Wikipedia article on probability distributions; take special note of the collapsible sections at the bottom of the page. You will find that there are dozens of non-uniform distribution (both continuous and discrete) with different properties.

Lucas
  • 8,035
  • 2
  • 32
  • 45
  • Hey lucas! Can you please justify ur answer? Not coding but logic stuff! – Reddy Jun 22 '10 at 17:01
  • 2
    You start with a value from a uniform distribution on [0.0, 1.0) and then slice up the interval into sections that are proportional to your probabilities. – Lucas Jun 22 '10 at 17:25
  • 1
    @Reddy Did you click on the wiki link provided by Lucas? If you dig through the links you will understand why it works. You could also run the algorithm suggested by Lucas and satisfy yourself that Prob(draw = 0) = 0.85 and so on. – vad Jun 22 '10 at 18:31
  • wonderful guys! Just learnt that random functions are deisgned based on randomized algorithms, whose output is based on uniform probabilistic choices. Didn't realize that! It was intitutive, but tricky. THANKS LUCAS! and also ANON! bye – Reddy Jun 23 '10 at 21:52
4

In your particular case it is better to get a random value in [0; 100) using uniform distribution and then check what range it falls in: [0; 85), [85;99), [99, 100)

nkrkv
  • 7,030
  • 4
  • 28
  • 36
2

Based on your description it seems to me that you are talking about fitness proportionate selection (also known as roulette wheel selection).
http://en.wikipedia.org/wiki/Roulette-wheel_selection

I think nailxx' answer is a pretty compact description what you need to do.

see also Roulette Selection in Genetic Algorithms
Roulette wheel selection algorithm

If I'm wrong here are some libraries that you may find useful:
http://www.ee.ucl.ac.uk/~mflanaga/java/Stat.html
http://commons.apache.org/math/apidocs/org/apache/commons/math/random/package-summary.html

Community
  • 1
  • 1
Sandor Murakozi
  • 4,372
  • 25
  • 27