How to implement the Gaussian mutation operator fo

问题:

I try to learn and implement a simple genetic algorithm library for my project. At this time, evolution, selection of population is ready, and I'm trying to implement a simple good mutation operator like the Gaussian mutation operator (GMO) for my genetic evolution engine in Java and Scala.

I find some information on Gaussian mutation operator (GMO) into the paper A mutation operator based on a Pareto ranking for multi-objective evolutionary algorithms (P.M. Mateo, I. Alberto), page 6 and 7.

But I have some problem to find other information on how to implement this Gaussian mutation operator and other useful variants of this operator in Java. What should I do?

I'm using the random.nextGaussian() function of random Java util, but this method only returns a random number between 0 and 1.

So,

a) How can I modify the precision of the return number in this case? (For example, I want to get a random double number between 0 and 1 with step equal to 0.00001.)

b) and how can I specify mu and sigma for this function, because I want to search locally about a value of my genome, not between -1 and 1. How can I ajust that local research around my genome value?

After research, I found an answer for the b) question. It seems I can displace the Gaussian random number like this:

 newGenomeValue = oldGenomeValue + (( gaussiandRndNumber * sigma ) + mean )

where mean = my genome value.

(Cf. method of bottom page in How can I generate random numbers with a normal or Gaussian distribution?.)

回答1:

To answer question a, all you have to do is round to the nearest 0.00001 to get your answer in those units. For example:

  step = 0.00001;
  quantized_x = step * Math.rint(x / step);

Now for part b, you have the right idea and the code you presented should work. All you need to do is rescale your variable to the desired range. The only thing I can add is that the underlying reason this works is the change of variables theorem from calculus: http://en.wikipedia.org/wiki/Integration_by_substitution

If you work out this formula in the case of a Gaussian distribution with 0 mean and standard deviation 1 being transformed by a linear shift and a rescaling, then you will see that what you wrote out was indeed correct.

Putting it all together, here is some code that should do the trick:

double next_gaussian()
{
    double x = rng.nextGaussian();  //Use whichever method you like 
                                    //here to generate an initial [-1,1] gaussian distribution

    y = (x * 0.5) + 0.5;                //Rescale to [0,1]

    return Math.rint(y * 100000.0) * 0.00001; //Quantize to step size 0.00001
}

回答2:

I strongly suggest to DO NOT use the Java's random number generator. It uses the linear congruential generator, which has known limitations:

If higher quality random numbers are needed, and sufficient memory is available (~ 2 kilobytes), then the Mersenne twister algorithm provides a vastly longer period (219937-1) and variate uniformity.[9] The Mersenne twister generates higher-quality deviates than almost any LCG.[citation needed] A common Mersenne twister implementation, interestingly enough, uses an LCG to generate seed data.* (From Wikipedia)

Accordingly, I suggest you to consider a Mersenne twister implementation. In particular, I'm using the ECJ's implementation, which also has the ability to generate Gaussian numbers.

If you need compatibility with Java's Random interface use http://code.google.com/p/ecj/source/browse/trunk/ecj/ec/util/MersenneTwister.java.

http://code.google.com/p/ecj/source/browse/trunk/ecj/ec/util/MersenneTwisterFast.java is faster, but it does not implement the Random interface.

回答3:

To change the "precision" of the number, do something like:

((int)(100*rand))/100.0

This will round the variable rand to 2 decimal places. Of course, you'll have to be careful about small floating point rounding errors so it won't necessarily be exact.

As for the implementing the GMO, the paper describes how to do it pretty precisely. I'm not sure how it could be explained any clearer. I'm assuming you have an x and a sigma somewhere in your code and you just transform it using the mathematical operation described.

回答4:

Here's how you can generate a random number between 0 and n:

public static double random(int n)
{
    return Math.random() * n;
}

If you need an integer, cast it to int but add one to n, ie (int)random(n + 1)