I. Problem definition:
Q. There is an array of values which have their own weights, how to design it to prioritize and take out the high weighted numbers efficiently?
Example:
Weight: 8 2 11 79
Values returned for weights: 0 1 2 3
II. Analyzing the problem:
Idea 1: Create an array array size for the size of the weights and, if the value 0 weight is 8, then put 8 0 values, the value 1 weight is 2, then put 2 1 values, and so on.
Then just generate random numbers with using a random number of weights and sizes. Disadvantage to take up too much memory.
Thought two:
Weight sum array w[i] stores the weight sum of all elements of [0,i] element Time complexity O(n) Space complexity O(n)
Random[0,W[399]] See which random number falls within Wi and pick it Time complexity O(longn)
So total time complexity time complexity O(n) space complexity O(n)
Pseudocode:
Roulette is not a particularly good choice operator, but it is easy to implement.
First of all, it is important to understand that since crossover and mutation operators do not control the direction of evolution, the burden of evolution falls on the selection operator.
If you understand that, it's a good thing.
Roulette, which is realized by accumulating probabilities, usually has a higher chance of being chosen for its greater adaptability.
Suppose: fit is an array of fitnesses, m in total.
for i=1 to m 'Sum first
sum=sum+fit(i)
next i
For i = 1 To n 'n- is how many individuals to generate
temp = temp + fit(i)
If rnd <= temp / sum Then
The output i is the result
Exit Function
End If
Next i
III. Problem solving:
package datastruct;
import ;
import ;
/**
Weighted random numbers:
e.g. Weight: 8 2 11 79
Value returned by weight:0 1 2 3
@author ajian005 79331356@
2014-2-16 21:12
Output: {2.0=184128, 11.0=348551, 79.0=1308100, 8.0=159221}
*/
public class WeightRandomTest {
private static double[] weightArrays = {8.0,2.0,11.0,79.0}; // array subscripts are the values to be returned, array values are the weights of the array subscripts
public static void main(String[] args) {
WeightRandom weightRandom = new WeightRandom();
Map<Double, Integer> stat = new HashMap<Double, Integer>();
for (int i = 0; i < 2000000; i++) {
int weightValue = (weightArrays);
if (weightValue < 0) {
continue;
}
("Randomized number returned by weight: " + weightValue);
if ((weightArrays[weightValue]) == null) {
(weightArrays[weightValue], 1);
} else {
(weightArrays[weightValue], (weightArrays[weightValue])+1);
}
}
(stat);
}
}
class WeightRandom {
r = new ();
private double weightArraySum(double [] weightArrays) {
double weightSum = 0;
for (double weightValue : weightArrays) {
weightSum += weightValue;
}
return weightSum;
}
public int getWeightRandom(double [] weightArrays) {
double weightSum = weightArraySum(weightArrays);
double stepWeightSum = 0;
for (int i = 0; i < ; i++) {
stepWeightSum += weightArrays[i];
if (() <= stepWeightSum/weightSum) {
//(i);
return i;
}
}
("There's been an error").
return -1;
}
}
IV. Summarizing:
Russian roulette is all about accumulating probabilities to achieve
Weighted load scheduling, etc.