我有一个加权对象列表,即:
A->1 B->1 C->3 D->2 E->3
C++中是否有一种根据随机元素的权重来挑选随机元素的有效算法?
例如,选择权重较低的元素A或B的可能性(30%(高于算法选择元素C E(10%(或D(20%(的可能性
正如@Dukeling所说,我们需要更多信息。喜欢你如何解读和利用选择机会。
至少在进化算法领域,适应度缩放(或选择机会缩放(是一个相当大的主题。
假设你从坏开始得分
B[i] = how badly you don't want to select the i-th item
目标是计算适合度/选择分数S[i]
,我假设您将以轮盘赌的方式使用它。
正如你所说,一个明显的方法是使用乘法逆:
S[i] = 1 / B[i]
然而,这可能会有一个小问题。与CCD_ 4已经具有高值时的相同变化量相比,具有低值的CCD_。
问问自己:
Say
B[1] = 1 -> S[1] = 1
B[2] = 2 -> S[2] = 0.5
So item 1 is twice times as likely to be selected compared to item 2
But with the same amount of change
B[3] = 1000 -> S[3] = 0.001
B[4] = 1001 -> S[4] = 0.000999001
Item 3 is only 1.001 times as likely to be selected compared to item 4
我现在只提出一个可能的替代方案。
S[i] = max(B) - B[i] + 1
+ 1
部分有助于使任何项目都没有被选中的机会。
计算选择分数的部分到此结束。
接下来,让我们来了解如何在轮盘游戏中使用选择分数。假设我们决定使用加性逆方案。
B[1] = 1 -> S[1] = 1001
B[2] = 2 -> S[2] = 1000
B[3] = 1000 -> S[3] = 2
B[4] = 1001 -> S[4] = 1
然后想象得分中的每一分都对应一张彩票。让我们给票分配一个运行ID。
| Item | Score = #ticket | ticket ID | win chance |
| 1 | 1001 | 0 to 1000 | 1001/2004 ~ 0.499500998 |
| 2 | 1000 | 1001 to 2000 | 1000/2004 ~ 0.499001996 |
| 3 | 2 | 2001 to 2002 | 2/2004 ~ 0.000998004 |
| 4 | 1 | 2003 to 2003 | 1/2004 ~ 0.000499002 |
总共有2004张票。
要进行选择,请随机选择中奖彩票ID,即随机范围为[00204(。二进制搜索可用于快速查找哪个物品拥有中奖彩票,正如您在本问题中已经看到的那样。需要使用二进制搜索查找的是票证ID的边界值,这些值是1001,2001,2003
,而不是分数本身。
为了进行比较,这里是在使用乘性逆方案的情况下的选择机会。
| Item | win chance |
| 1 | 1/1.501999001 ~ 0.665779404 |
| 2 | 0.5/1.501999001 ~ 0.332889702 |
| 3 | 0.001/1.501999001 ~ 0.000665779 |
| 4 | 0.000999001/1.501999001 ~ 0.000665114 |
您可以注意到,在加性逆方案中,1个单位的不良始终对应于0.0005左右的选择机会差。
而在乘法逆格式中,1个单位的不良导致选择机会的差异变化。