随机通用采样中指针之间的距离是如何确定的?

人工智能 遗传算法 选择运算符 随机通用抽样
2021-10-28 04:16:58

我正在研究遗传算法中的不同选择方法。我的问题是关于随机通用抽样 (SUS) 选择方法。我知道每个人将根据其适应度值占据一条线,然后等间距的指针将放置在这条线上。

我想知道指针之间的距离是如何确定的。我已经看到 1/6 和 1/4 作为指针之间的距离。我想根据情况动态选择指针的数量。我想知道什么条件或因素会影响这个距离的确定。例如,我们什么时候决定选择 1/4 作为距离?我想知道是否可以根据不同的条件或情况改变每次迭代中的样本数。如果有,这些条件是什么?

1个回答

正如 James Baker 1989 年在减少选择算法中的偏差和效率低下的论文中最初设想的那样,随机通用抽样接受包含以下内容的总体N个人,以及一些要抽样的父母,表示n. 假设适应度值被归一化,因此它们总和为N,在每一步,一个新的指针被放置在一个与分数大小相等的步长上Nn在前一个指针的位置之前(并且第一个指针的位置设置为范围 [0,Nn))。因此,例如,如果您想从大小为 10 的总体中抽取 6 个个体,您需要设置大小步长106, 将指针间隔均匀106.

现代的实现,比如维基百科上的实现,有时并没有清楚地记录这一事实,尽管如果你已经理解了这个方法,那么它的意图是显而易见的。他们经常将步长写为Fn, 在哪里F是人口的总适应度,没有讨论它与人口规模的关系。额外的规范化步骤实际上并不是必需的,因此现代实现通常似乎跳过了它。

总而言之,步长Fn如果种群的适应度值总和为F,并且您要选择n个人。如果要选择更多个体,请使用更高的值n. 如果您想选择更少,请使用较低的值n,它会相应地更新您的步长。

这个参数的值14或者16建议实现可能是将适应度值的总和归一化为 N,然后自动使用参数作为乘法因子。这是一个相当合理的设计。您可以将这些值解释为“选择14人口”和“选择16人口”。

请注意,这种方式将您的问题提升了一个层次:您如何选择要保留的人口比例?这个问题没有一个明确的答案,而选择它通常是专家通过实践开发的艺术。它与探索/开发权衡非常密切相关

您可能会选择的一些方法n

  1. 使用固定值,例如,在每个步骤中保留一半的人口。您想要选择的确切比例不是您可以提前知道的。专家从业者可以做出有效的猜测。其他人只需要使用交叉验证等技术尝试不同的值,然后选择看起来效果最好的一个。
  2. 您可以使用随时间变化的值。一个常见的策略是使用模拟退火文献中开发的温度计划之一,并保留与温度成反比的一部分人口。也就是说,在早期,你会使用一个大的n,并保留大部分人口(可能有突变)。以后,你会用一个小的n并且只保留最优秀的人才。
  3. 你可以使用一个值n这会随着人口的适应性而变化。这很像某些算法中用于训练神经网络的自适应学习率(最值得注意的是:ADAM 优化器)。当健康水平有很多变化时,使用较低的值n鼓励更多的剥削。当适应度水平都在一个窄带内时,使用较高的值n鼓励更多的探索。