快捷導(dǎo)航

Java實現(xiàn)按權(quán)重隨機數(shù)

更新時間：2015年04月28日 10:06:29 投稿：junjie

這篇文章主要介紹了Java實現(xiàn)按權(quán)重隨機數(shù),本文給出了提出問題、分析問題、解決問題三個步驟,需要的朋友可以參考下

一、問題定義：

問下有一個數(shù)組，這些數(shù)組中的值都有自己的權(quán)重，怎樣設(shè)計才能高效的優(yōu)先取出權(quán)重高的數(shù)？？

例如：

權(quán)重: 8  2  11  79

權(quán)重返回的值: 0  1  2   3

二、分析問題：

思路一：創(chuàng)建一個數(shù)組數(shù)組大小為權(quán)重和的大小，如值0的權(quán)重是8，則放入8個0值，值1的權(quán)重是2，則放入2個1值，依次類推。
然后用用一個權(quán)重和大小的隨機數(shù)，產(chǎn)生隨機數(shù)，即可。缺點要占用過多的內(nèi)存。

思路二：

權(quán)重和數(shù)組 w[i]存儲的是[0,i]元素的所有元素的權(quán)重和時間復(fù)雜度O(n) 空間復(fù)雜度O(n)
隨機[0,W[399]] 看隨機數(shù) 落在哪個Wi 內(nèi)就選哪個時間復(fù)雜度 O(longn)
所以總的時間復(fù)雜度時間復(fù)雜度O(n) 空間復(fù)雜度O(n)

偽代碼：

輪盤賭并不是一種特別好的選擇算子,但它容易實現(xiàn)。
首先要明白一點,由于交叉、變異等算子,并不能控制進化方向,所以進化的重任落在選擇算子上。
如果明白了這一點,就好辦了。

輪盤賭,就是積累概率來實現(xiàn)的,通常適應(yīng)度大的被選擇的幾率較高。
假如:fit為適應(yīng)度數(shù)組,共m個

復(fù)制代碼代碼如下:

for i=1 to m '先求和

sum=sum+fit(i)

next i

For i = 1 To n ‘n-是要生成多少個個體

temp = temp + fit(i)

If rnd &lt;= temp / sum Then

   輸出 i 就是結(jié)果

Exit Function

End If

Next i

三、解決問題：

復(fù)制代碼代碼如下:

package datastruct;

import java.util.HashMap;
import java.util.Map;

/**
權(quán)重隨機數(shù)：
如              權(quán)重:8 2 11 79
        權(quán)重返回的值:0 1 2   3
@author ajian005 79331356@qq.com
2014-2-16 21:12
輸出結(jié)果：{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}; // 數(shù)組下標(biāo)是要返回的值，數(shù)組值為數(shù)組下標(biāo)的權(quán)重
    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("按權(quán)重返回的隨機數(shù)：" + 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;
    }
}

四、歸納總結(jié)：

俄羅斯輪盤賭就是積累概率來實現(xiàn)

按權(quán)重負(fù)載調(diào)度等

您可能感興趣的文章: