ルーレット選択関数の擬似コードを提供できる人はいますか? これをどのように実装しますか: この数学表記の読み方がよくわかりません。これには一般的なアルゴリズムが必要です。
12 に答える
他の回答は、ルーレット ゲームを実装しようとしていると仮定しているようです。進化的アルゴリズムにおけるルーレット盤の選択について質問されていると思います。
ルーレット ホイールの選択を実装する Java コードを次に示します。
選択するアイテムが 10 個あり、0 から 1 の間の乱数を生成して選択するとします。0 から 1 の範囲を 10 個の重複しないセグメントに分割し、それぞれが 10 個のアイテムのいずれかの適合度に比例します。たとえば、これは次のようになります。
0 - 0.3 is item 1
0.3 - 0.4 is item 2
0.4 - 0.5 is item 3
0.5 - 0.57 is item 4
0.57 - 0.63 is item 5
0.63 - 0.68 is item 6
0.68 - 0.8 is item 7
0.8 - 0.85 is item 8
0.85 - 0.98 is item 9
0.98 - 1 is item 10
これがあなたのルーレット盤です。0 から 1 までの乱数がスピンです。乱数が 0.46 の場合、選択された項目は項目 3 です。0.92 の場合、項目 9 です。
ここに少しのpythonコードがあります:
def roulette_select(population, fitnesses, num):
""" Roulette selection, implemented according to:
<http://stackoverflow.com/questions/177271/roulette
-selection-in-genetic-algorithms/177278#177278>
"""
total_fitness = float(sum(fitnesses))
rel_fitness = [f/total_fitness for f in fitnesses]
# Generate probability intervals for each individual
probs = [sum(rel_fitness[:i+1]) for i in range(len(rel_fitness))]
# Draw new population
new_population = []
for n in xrange(num):
r = rand()
for (i, individual) in enumerate(population):
if r <= probs[i]:
new_population.append(individual)
break
return new_population
まず、割り当てたパーセンテージの配列を生成します。たとえばp[1..n]
、合計がすべてのパーセンテージの合計であるとします。
次に、1から合計までの乱数を取得します。r
さて、lua のアルゴリズム:
local c = 0
for i = 1,n do
c = c + p[i]
if r <= c then
return i
end
end
これには 2 つの手順があります。まず、ホイール上のすべての値を含む配列を作成します。これは、色と数値を含む 2 次元配列にするか、赤の数値に 100 を追加することを選択できます。
次に、0 または 1 (言語が配列インデックスの番号付けを 0 または 1 から開始するかによって異なります) と配列の最後の要素の間の乱数を生成します。
ほとんどの言語には、乱数関数が組み込まれています。VBVBScript
では、関数はRND()
. JavascriptではMath.random()
配列内のその位置から値を取得すると、ランダムなルーレット番号が得られます。
最後の注意: 乱数ジェネレーターをシードすることを忘れないでください。そうしないと、プログラムを実行するたびに同じ一連の描画が得られます。
私は同じことが欲しかったので、この自己完結型のルーレット クラスを作成しました。一連の重みを (double 配列の形式で) 与えると、重み付けされたランダム ピックに従って、その配列から単純にインデックスが返されます。
クラスを作成したのは、コンストラクターを介して累積加算を 1 回実行するだけで大幅に高速化できるためです。これは C# コードですが、C のようなスピードとシンプルさをお楽しみください。
class Roulette
{
double[] c;
double total;
Random random;
public Roulette(double[] n) {
random = new Random();
total = 0;
c = new double[n.Length+1];
c[0] = 0;
// Create cumulative values for later:
for (int i = 0; i < n.Length; i++) {
c[i+1] = c[i] + n[i];
total += n[i];
}
}
public int spin() {
double r = random.NextDouble() * total; // Create a random number between 0 and 1 and times by the total we calculated earlier.
//int j; for (j = 0; j < c.Length; j++) if (c[j] > r) break; return j-1; // Don't use this - it's slower than the binary search below.
//// Binary search for efficiency. Objective is to find index of the number just above r:
int a = 0;
int b = c.Length - 1;
while (b - a > 1) {
int mid = (a + b) / 2;
if (c[mid] > r) b = mid;
else a = mid;
}
return a;
}
}
最初の重みはあなた次第です。おそらく、各メンバーのフィットネス、または「上位 50」でのメンバーの位置に反比例する値である可能性があります。例: 1 位 = 1.0 の重み付け、2 位 = 0.5、3 位 = 0.333、4 位 = 0.25 の重み付けなど。
アメリカン ルーレット ホイールの場合、1 から 38 までのランダムな整数を生成する必要があります。36 個の数字、0、および 00 があります。
ただし、考慮すべき重要なことの 1 つは、アメリカン ルーレットでは、さまざまな賭けを行うことができるということです。1 回のベットで 1、2、3、4、5、6、2 つの異なる 12、または 18 をカバーできます。単純化するために、各数字に追加のフラグがあるリストのリストを作成するか、プログラミングですべて実行することをお勧めします。 .
Python で実装する場合は、0、00、1 ~ 36 のタプルを作成し、各スピンに random.choice() を使用します。
次のようなデータ構造を使用できます。
Map<A, B> roulette_wheel_schema = new LinkedHashMap<A, B>()
ここで、A はルーレットのポケットを表す整数で、B は母集団内の染色体を識別するインデックスです。ポケットの数は、各染色体の適合度に比例します。
ポケットの数 = (フィットネス比例) · (倍率)
次に、0 と選択スキーマのサイズの間で乱数を生成し、この乱数を使用してルーレットから染色体のインデックスを取得します。
各染色体の適合度比例と選択スキームによって選択される確率との間の相対誤差を計算します。
メソッドgetRouletteWheelは、前のデータ構造に基づいて選択スキームを返します。
private Map<Integer, Integer> getRouletteWheel(
ArrayList<Chromosome_fitnessProportionate> chromosomes,
int precision) {
/*
* The number of pockets on the wheel
*
* number of pockets in roulette_wheel_schema = probability ·
* (10^precision)
*/
Map<Integer, Integer> roulette_wheel_schema = new LinkedHashMap<Integer, Integer>();
double fitness_proportionate = 0.0D;
double pockets = 0.0D;
int key_counter = -1;
double scale_factor = Math
.pow(new Double(10.0D), new Double(precision));
for (int index_cromosome = 0; index_cromosome < chromosomes.size(); index_cromosome++){
Chromosome_fitnessProportionate chromosome = chromosomes
.get(index_cromosome);
fitness_proportionate = chromosome.getFitness_proportionate();
fitness_proportionate *= scale_factor;
pockets = Math.rint(fitness_proportionate);
System.out.println("... " + index_cromosome + " : " + pockets);
for (int j = 0; j < pockets; j++) {
roulette_wheel_schema.put(Integer.valueOf(++key_counter),
Integer.valueOf(index_cromosome));
}
}
return roulette_wheel_schema;
}
これは、文字列条件、文字列メッセージ、および二重強度を持つクラス「分類子」を想定しています。ロジックに従うだけです。
-- ポール
public static List<Classifier> rouletteSelection(int classifiers) {
List<Classifier> classifierList = new LinkedList<Classifier>();
double strengthSum = 0.0;
double probabilitySum = 0.0;
// add up the strengths of the map
Set<String> keySet = ClassifierMap.CLASSIFIER_MAP.keySet();
for (String key : keySet) {
/* used for debug to make sure wheel is working.
if (strengthSum == 0.0) {
ClassifierMap.CLASSIFIER_MAP.get(key).setStrength(8000.0);
}
*/
Classifier classifier = ClassifierMap.CLASSIFIER_MAP.get(key);
double strength = classifier.getStrength();
strengthSum = strengthSum + strength;
}
System.out.println("strengthSum: " + strengthSum);
// compute the total probability. this will be 1.00 or close to it.
for (String key : keySet) {
Classifier classifier = ClassifierMap.CLASSIFIER_MAP.get(key);
double probability = (classifier.getStrength() / strengthSum);
probabilitySum = probabilitySum + probability;
}
System.out.println("probabilitySum: " + probabilitySum);
while (classifierList.size() < classifiers) {
boolean winnerFound = false;
double rouletteRandom = random.nextDouble();
double rouletteSum = 0.0;
for (String key : keySet) {
Classifier classifier = ClassifierMap.CLASSIFIER_MAP.get(key);
double probability = (classifier.getStrength() / strengthSum);
rouletteSum = rouletteSum + probability;
if (rouletteSum > rouletteRandom && (winnerFound == false)) {
System.out.println("Winner found: " + probability);
classifierList.add(classifier);
winnerFound = true;
}
}
}
return classifierList;
}
残念ながら、すべてのプログラミング言語で組み込みの乱数ジェネレーターを使用している人は、生成された数値が 100% ランダムではないことに注意する必要があります。そのため、注意して使用する必要があります。
乱数発生器の擬似コード
- シーケンシャル カウンターに 1 を加算する
- シーケンシャル カウンタの現在の値を取得する
- コンピューターのティックカウントまたはその他の小さなインターバルタイマー値でカウンター値を追加します
- 必要に応じて、プラズマ発生器などの外部ハードウェアからの数値や、その他の種類のややランダムな現象のような追加の数値を追加します
- 結果を非常に大きな素数 359334085968622831041960188598043661065388726959079837 で割ります。
- 結果の小数点の右端から数桁を取得する
- これらの数字を乱数として使用します
乱数の数字を使用して、ルーレット用に 1 ~ 38 (または 37 ヨーロッパ) の乱数を作成します。