一、問題定義：
問下有一個數組，這些數組中的值都有自己的權重，怎樣設計才能高效的優先取出權重高的數？ ？
例如：
複製代碼代碼如下:
權重: 8 2 11 79
權重返回的值: 0 1 2 3
二、分析問題：
思路一：創建一個數組數組大小為權重和的大小，如值0的權重是8，則放入8個0值，值1的權重是2，則放入2個1值，依次類推。
然後用用一個權重和大小的隨機數，產生隨機數，即可。缺點要佔用過多的內存。
思路二：
權重和數組w[i]存儲的是[0,i]元素的所有元素的權重和時間複雜度O(n) 空間複雜度O(n)
隨機[0,W[399]] 看隨機數落在哪個Wi 內就選哪個時間複雜度O(longn)
所以總的時間複雜度時間複雜度O(n) 空間複雜度O(n)
虛擬程式碼:
輪盤賭並不是一種特別好的選擇算子,但它容易實現。
首先要明白一點,由於交叉、變異等算子,並不能控制進化方向,所以進化的重任落在選擇算子上。
如果明白了這一點,就好辦了。
輪盤賭,就是積累概率來實現的,通常適應度大的被選擇的機率較高。
假如:fit為適應度數組,共m個複制代碼代碼如下:
for i=1 to m '先求和
sum=sum+fit(i)
next i
For i = 1 To n 'n-是要生成多少個個體
temp = temp + fit(i)
If rnd <= temp / sum Then
輸出i 就是結果
Exit Function
End If
Next i
三、解決問題：
複製代碼代碼如下:
package datastruct;
import java.util.HashMap;
import java.util.Map;
/**
權重隨機數：
如權重:8 2 11 79
權重返回的值:0 1 2 3
@author ajian005 [email protected]
2014-2-16 21:12
輸出結果：{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}; // 數組下標是要返回的值，數組值為數組下標的權重
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 = weightRandom.getWeightRandom(weightArrays);
if (weightValue < 0) {
continue;
}
System.out.println("按權重返回的隨機數：" + weightValue);
if (stat.get(weightArrays[weightValue]) == null) {
stat.put(weightArrays[weightValue], 1);
} else {
stat.put(weightArrays[weightValue], stat.get(weightArrays[weightValue])+1);
}
}
System.out.println(stat);
}
}
class WeightRandom {
java.util.Random r = new java.util.Random();
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 < weightArrays.length; i++) {
stepWeightSum += weightArrays[i];
if (Math.random() <= stepWeightSum/weightSum) {
//System.out.println(i);
return i;
}
}
System.out.println("出錯誤了");
return -1;
}
}
四、歸納總結：
俄羅斯輪盤賭就是積累概率來實現
按權重負載調度等