有人能提供轮盘选择函数的伪代码吗？我该如何实现它：我真的不理解如何阅读这个数学符号。我想要一个通用算法。
可以有人提供轮盘选择函数的伪代码吗？我不太理解如何读取这个数学符号，因此需要一个通用算法。轮盘赌选择算法
24
- swati
2
1编辑了标签。有人从这个问题的第一个修订版本中删除了“遗传”标签，使得问题的内容变得不太清楚。 - Dan Dyer
1无符号整数 num = ::rand() % 37; - Viktor Sehr
12个回答
49
其他答案似乎假设您正在尝试实现轮盘游戏。 我认为您在询问进化算法中的轮盘赌选择。
这里有一些Java代码可用于实现轮盘赌选择。
假设您有10个要选择的项目，并通过生成0到1之间的随机数进行选择。 您将0到1范围划分为十个不重叠的段，每个部分与十个项目中一个项目的适应度成比例。 例如，可能看起来像这样：
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。
- Dan Dyer
3
1这是我遇到的最快的一个。非常不错。 - Parrish Husband
有没有人讨论过如何替换已选项目，以免再次选择该项目？有什么解决方案吗？ - Anik Islam Abhi
1就我而言，轮盘赌选择假定每个项目可以被选择多次。如果您随机化N次（其中N是种群计数），则在选择后将取得完全相同的种群。 - Sebastian Budka
10
def roulette_select(population, fitnesses, num):
""" Roulette selection, implemented according to:
<https://dev59.com/1HVC5IYBdhLWcg3wz0l9
-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
- noio
6
1这会起作用吗，即使一些适应度值为负数？ - mkuse
不会的。但你必须想一想，由于适应度对应着抽取样本的概率，不存在抽取样本的负概率，那么你会期望出现什么样的行为呢？ - noio
我的意思是，我有一个健身函数，会给出负值。假设我正在解决一个需要使用GA的问题，其中适应度是“误差”，即目标值与GA获得值之间的差异。在这种情况下，适应度函数将生成负值。那么我如何将其制定成Routtle轮？ - mkuse
就像我说的那样，你必须考虑一下你想用这些负值做什么！轮盘赌不会将“适应度”值作为输入，而是（未归一化的）“概率”。你必须想出一种方法将这些可能为负的误差值转换为概率。如果你可以有负的“误差”值，那么你正在做一些奇怪的事情，但也许你可以只是取反它们（
error = -error），然后我通常会这样做：fitness = 1/(1+error)。 - noio轮盘赌选择在负适应度值下无法正常工作。请尝试锦标赛选择。 - fangmobile
您没有替换所选个体。这难道不会为在种群中再次选择同一项留下空缺吗？ - Anik Islam Abhi
5
首先，生成一个百分比数组，假设为
然后获取一个介于1到总和之间的随机数，假设为
现在，lua算法如下：
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
- gray
4
这个有两个步骤：首先创建一个包含轮盘上所有值的数组。这可以是一个二维数组，包括颜色和数字，或者您可以选择将100添加到红色数字中。
然后只需生成0到数组中最后一个元素之间的随机数（取决于您的语言是否从0或1开始编号数组索引）。
大多数语言都有内置的随机数函数。在VB和VBScript中，该函数为RND()。在Javascript中，它是Math.random()。
从数组中的那个位置获取值，就可以得到您的随机轮盘数字。
最后注意：不要忘记种子化随机数生成器，否则每次运行程序时都会得到相同的抽奖序列。
然后只需生成0到数组中最后一个元素之间的随机数（取决于您的语言是否从0或1开始编号数组索引）。
大多数语言都有内置的随机数函数。在VB和VBScript中，该函数为RND()。在Javascript中，它是Math.random()。
从数组中的那个位置获取值，就可以得到您的随机轮盘数字。
最后注意：不要忘记种子化随机数生成器，否则每次运行程序时都会得到相同的抽奖序列。
- Bork Blatt
3
以下是使用Java中的流选择来快速完成此操作的方法。它使用值作为权重来选择数组的索引。由于数学属性，不需要累积权重。
static int selectRandomWeighted(double[] wts, Random rnd) {
int selected = 0;
double total = wts[0];
for( int i = 1; i < wts.length; i++ ) {
total += wts[i];
if( rnd.nextDouble() <= (wts[i] / total)) selected = i;
}
return selected;
}
这可以进一步改进，使用Kahan求和算法或将双精度浮点数作为可迭代对象进行读取，如果数组太大而无法一次性初始化。
- Andrew Mao
5
1那看起来是一个有趣的解决方案。我也在你发表回答的同一小时内给出了答案，尽管这个问题已经存在多年了（也许你看到了我的帖子）。无论如何，我喜欢你的答案，因为它非常简短，但我认为我的答案可能更有效率，因为它具有O(log2 n)的效率，而不是你的O(n)。 - Dan W
1我觉得你的问题让我不得不发布我的答案。无论如何，你最初的累加总和仍然需要
O(n) 的时间复杂度。我认为这绝对是一个下限 :) - Andrew Mao1只在构造函数中执行一次。在实际情况下，你会执行很多次“轮盘旋转”（即寻找许多不同的父母对）。这就是O(log2 n)发挥作用的地方，之后只调用spin()方法。 - Dan W
1如果您想从相同的分布中重复绘制，则这是正确的。但我认为在实践中并不经常发生，根据我的经验；例如，在遗传算法中，适应度权重总是在变化。此外，如果您要从这样的分布中绘制大量样本，则根本不需要真正随机化，因为分数将收敛到归一化权重。 - Andrew Mao
也许像你说的那样，GA可以胜任。但对于我需要的情况（模拟数百万或数十亿次赌注以测试风险/利润），我的O(log2 n)答案代码是一种改进。我相信还有其他情况也是如此。 - Dan W
2
我想要相同的功能，所以创建了这个自包含的轮盘赌类。您可以给它一系列权重（以双精度数组的形式），然后它将根据加权随机选择从该数组返回一个索引。
我创建了一个类，因为通过构造函数仅执行累积加法一次可以获得大幅加速。这是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.0权重，第二名=0.5，第三名=0.333，第四名=0.25等等。
- Dan W
1
对于美式轮盘赌，您需要生成一个介于1和38之间的随机整数。有36个数字，一个0和一个00。
但需要考虑的一件大事是，在美式轮盘赌中，有许多不同的投注方式。单个投注可以覆盖1、2、3、4、5、6、两个不同的12或18。您可能希望创建一个列表的列表，其中每个数字都有附加标志以简化操作，或者在编程中完成所有操作。
如果我要在Python中实现它，我只需创建一个元组，包括0、00和1到36，并为每次旋转使用random.choice()。
- J.T. Hurley
1
这假设有一个名为“分类器”的类，它只有一个字符串条件、一个字符串消息和一个双精度强度。只需按照逻辑操作即可。
-- Paul
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;
}
- Paul
1
您可以使用这样的数据结构：
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;
}
- d9daniel
0
我已经编写了一个类似于之前提到的Dan Dyer的Java代码。然而，我的轮盘根据概率向量（输入）选择单个元素并返回所选元素的索引。 话虽如此，如果选择大小为1且您不假设如何计算概率且允许零概率值，则以下代码更为适用。该代码是自包含的，并包括20次轮盘旋转的测试（可运行）。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;
/**
* Roulette-wheel Test version.
* Features a probability vector input with possibly null probability values.
* Appropriate for adaptive operator selection such as Probability Matching
* or Adaptive Pursuit, (Dynamic) Multi-armed Bandit.
* @version October 2015.
* @author Hakim Mitiche
*/
public class RouletteWheel {
/**
* Selects an element probabilistically.
* @param wheelProbabilities elements probability vector.
* @param rng random generator object
* @return selected element index
* @throws java.lang.Exception
*/
public int select(List<Double> wheelProbabilities, Random rng)
throws Exception{
double[] cumulativeProba = new double[wheelProbabilities.size()];
cumulativeProba[0] = wheelProbabilities.get(0);
for (int i = 1; i < wheelProbabilities.size(); i++)
{
double proba = wheelProbabilities.get(i);
cumulativeProba[i] = cumulativeProba[i - 1] + proba;
}
int last = wheelProbabilities.size()-1;
if (cumulativeProba[last] != 1.0)
{
throw new Exception("The probabilities does not sum up to one ("
+ "sum="+cumulativeProba[last]);
}
double r = rng.nextDouble();
int selected = Arrays.binarySearch(cumulativeProba, r);
if (selected < 0)
{
/* Convert negative insertion point to array index.
to find the correct cumulative proba range index.
*/
selected = Math.abs(selected + 1);
}
/* skip indexes of elements with Zero probability,
go backward to matching index*/
int i = selected;
while (wheelProbabilities.get(i) == 0.0){
System.out.print(i+" selected, correction");
i--;
if (i<0) i=last;
}
selected = i;
return selected;
}
public static void main(String[] args){
RouletteWheel rw = new RouletteWheel();
int rept = 20;
List<Double> P = new ArrayList<>(4);
P.add(0.2);
P.add(0.1);
P.add(0.6);
P.add(0.1);
Random rng = new Random();
for (int i = 0 ; i < rept; i++){
try {
int s = rw.select(P, rng);
System.out.println("Element selected "+s+ ", P(s)="+P.get(s));
} catch (Exception ex) {
Logger.getLogger(RouletteWheel.class.getName()).log(Level.SEVERE, null, ex);
}
}
P.clear();
P.add(0.2);
P.add(0.0);
P.add(0.5);
P.add(0.0);
P.add(0.1);
P.add(0.2);
//rng = new Random();
for (int i = 0 ; i < rept; i++){
try {
int s = rw.select(P, rng);
System.out.println("Element selected "+s+ ", P(s)="+P.get(s));
} catch (Exception ex) {
Logger.getLogger(RouletteWheel.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
/**
* {@inheritDoc}
* @return
*/
@Override
public String toString()
{
return "Roulette Wheel Selection";
}
}
以下是一个概率向量P=[0.2,0.1,0.6,0.1]和WheelElements=[0,1,2,3]的执行示例：
选择元素3，P(s)=0.1
选择元素2，P(s)=0.6
选择元素3，P(s)=0.1
选择元素2，P(s)=0.6
选择元素1，P(s)=0.1
选择元素2，P(s)=0.6
选择元素3，P(s)=0.1
选择元素2，P(s)=0.6
选择元素2，P(s)=0.6
选择元素2，P(s)=0.6
选择元素2，P(s)=0.6
选择元素2，P(s)=0.6
选择元素3，P(s)=0.1
选择元素2，P(s)=0.6
选择元素2，P(s)=0.6
选择元素2，P(s)=0.6
选择元素0，P(s)=0.2
选择元素2，P(s)=0.6
选择元素2，P(s)=0.6
选择元素2，P(s)=0.6
代码还测试了一个概率为零的轮盘赌。
- hmitcs
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接