快捷導(dǎo)航

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

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

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

一、問題定義：

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

例如：

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

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

二、分析問題：

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

思路二：

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

偽代碼：

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

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

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

for i=1 to m '先求和

sum=sum+fit(i)

next i

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

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)重隨機(jī)數(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)重返回的隨機(jī)數(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("出錯(cuò)誤了");
        return -1;
    }
}

四、歸納總結(jié)：

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

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

您可能感興趣的文章: