轮盘赌算法个体的选择概率为什么不是取决于顺序和累积概率分布

avatar 2024年05月26日19:26:11 0 77 views
博主分享免费Java教学视频,B站账号:Java刘哥 ,长期提供技术问题解决、项目定制:本站商品点此

一、什么是轮盘赌算法

1、先看一段代码

我在ABC中使用的

% 适应度越高(目标值越小),最终选中概率越高
fitness = [18 19 20]; 
roulette_wheel = cumsum((1 ./ fitness) / sum(1 ./ fitness)) % 推荐写法
% roulette_wheel = cumsum(1 ./ fitness) / sum(1 ./ fitness) % 也可以,结果完全一样
selected_index = find(roulette_wheel >= rand(), 1);

简单解释下代码:

1)1 ./ fitness 表示数组里每个元素都调用[1/18, 1/19, 1/20]

2)sum() 即数组求和

3)cumsum 表示逐个累加,比如 cumsum([10 20 30]) = [10 10+20 10+20+30] = [10 30 60]

4)roulette_wheel >= rand(),首先rand()为0-1的随机数,假设为0.32, roulette_wheel 假设是 [0.35 0.33 0.31]

则 roulette_wheel >= rand() = [1 1 0]

find([1 1 0], 1) 表示从数组里找第一个不是0的数的下标,返回 1 

 

另外

无论是 fitness = [18 19 20] 或 [20 19 18];   选择18的概率都是最高的,也就是与顺序无关

 

2、公式如下

公式1、选择概率(归一化适应度倒数)

即 1 ./ fitness) / sum(1 ./ fitness

即最后一行 selected_index 等于1,2,3的概率

 

公式2、累加概率分布

即调用 cumsum 函数

 

 

3、计算逻辑如下

累计概率分布即 roulette_wheel 的值

 

二、对比一下不同顺序的影响

我好奇为什么这两个顺序不同,生成的累计概率分布也不同,但是最终获得的概率Pi是基本相同的。

即适应度越高(目标值小的)概率更大

1、查看下累计概率分布

 

2、概率比较

r = rand()

选择 roulette_wheel >= r 中第一个个体

情况 1: 

fitness = [18, 19, 20]
roulette_wheel = [0.352, 0.684, 1.0]

1)当 0     <= r < 0.352 时,命中第一个,即选18的概率为 0.352
2)当 0.352 <= r < 0.684 时,命中第二个,即选19的概率为 0.684-0.352=0.332
3)当 0.684 <= r < 1.0   时,命中第三个,即选20的概率为 1.0-0.684=0.316

 

情况 2: 

fitness = [20, 19, 18]
roulette_wheel = [0.316, 0.648, 1.0]

1)当 0     <= r < 0.316 时,命中第一个,即选20的概率为 0.316
2)当 0.316 <= r < 0.648 时,命中第二个,即选19的概率为 0.648-0.316=0.332
3)当 0.648 <= r < 1.0   时,命中第三个,即选18的概率为 1.0-0.648=0.352

综上比较,发现无论什么顺序,18,19,20的取值概率都是一样的

 

三、总结

尽管累积概率分布不同,但每个个体的选择概率(归一化后的适应度值)保持一致。

这说明轮盘赌选择法的公平性不受个体顺序的影响,而是由适应度值决定的。

 

 

  • 微信
  • 交流学习,有偿服务
  • weinxin
  • 编程爱好者交流群
  • 资源分享,问题解决,技术交流。QQ群:424285828(新群)
  • weinxin
avatar

发表评论

avatar 登录者:匿名
匿名评论,评论回复后会有邮件通知

  

已通过评论:0   待审核评论数:0