java - 这种选择 `parent`像 `gambling roulette `的方法可行吗？

Question

我突然想到，使用随机数来选择 parent 就像赌博轮盘赌可能是可行的。让我用一个例子来解释求函数的最大值。示例如下:

• 1.假设我们已经生成了n个随机个体并计算了它们的函数值。我们将个体命名为'j'Xj，其函数值名称为f(Xj)。我们找到并命名最大函数值maxValue。
• 2.显然个体j的适应度为f(Xj)/maxValue。我们可以将其命名为g(Xj).然后我们计算个体的所有适应度。
• 3.下一步是寻找 parent 。(我们放弃适应度值小于0的个体)。一个经典的方式是赌博轮盘赌。选择Xj和Xk的几率是g(Xj)*g(Xk)/[g(X1)+g(X2)+...+g (Xn)]^2.

我的想法是

• 1.选择两个随机个体Xj和Xk
• 2.生成一个0~1范围内的随机数rn。
• 3.如果rn小于g(Xj)和g(Xk)(适应度 Xj 和 Xk), 则它们能够繁殖。然后交叉和变异。
• 4.判断我们是否生成了足够多的子个体，如果是，结束。否则，重复 1-3。

选择Xj和Xk的几率是g(Xj)*g(Xk)/n^2，类似于赌博轮盘赌。考虑两个机会的分母都是常数值，它们在某种程度上是相等的。

            double randomNumToJudge=Math.random();//generate a random number to judge with the fitness 
            int randomMother=(int)(Math.random()*1000);
            int randomFather=(int)(Math.random()*1000);//random generate parents
            if((randomNumToJudge<=individualArray[generation][randomFather].fitnessValue)
            &&(randomNumToJudge<=individualArray[generation][randomMother].fitnessValue))
            //if the number is less than both fitness of parents,they are permited to reproduce.
            {
                Individual childIndividual=individualArray[generation][randomFather].crossOverAndMutate(individualArray[generation][randomFather], individualArray[generation][randomMother]);
                //Crossover and mutate and generate child individual
                individualArray[generation+1][counter]=childIndividual;//add childIndividual to tha Array.
                counter++;//the count of individual number in child generation
            }

我在java代码中这样测试。函数是x + 10sin(5x) + 7cos(4x), x∈[0,10)。我生成100代和个体数在一代人中是 1000。

它的结果是正确的。

在某次执行中，在第100代中，我发现最好的个体是7.856744175554171，最好的函数值是24.855362868957645。我测试了10次，每100代结果都精确到小数点后10位。

那么这种方式可行吗？这种方式是否已经被其他人想到了？

如有任何意见，我们将不胜感激^@^

PS:请原谅我糟糕的英语-_-

Answer 1

请注意我已经编辑了这个答案。

从第 2 点开始，我假设您的目标适应度为 1。您的算法可能永远不会完全收敛(找到局部最小值)。这是因为即使您的适应度发生变化，您的随机值范围 (0~>1) 也不会发生变化。

请注意，这并不意味着没有创建更好的适应性；他们会。但是由于您正在检查适应度(随机 0~>1)，因此创建更好适应度的速度会急剧下降。

考虑这个例子，其中所有适应度都收敛为高:

[0.95555, 0.98888, 0.92345, 0.92366]

这里，所有的值都极有可能满足randomNumToJudge<=fitness .这意味着任何值被选为父值的可能性相同。您不希望这样 - 您希望最佳值有更高的机会被选中。

如果您设置randomNumToJudge，您的算法可以被修改以正确收敛有一个范围(人口中的适应度中值 ~> 1)，尽管这仍然不是最优的。

替代方法

我建议实现经典 roulette wheel方法。

轮盘赌方法根据每个人的“适合度”为他们分配被选为 parent 的概率。从本质上讲，适应度越大，个体占据的轮子的切片就越大，随机数在轮子上选择这个位置的机会就越大。

Example Java code for roulette wheel selection