9

我正在尝试实现遗传算法以最大化 n 个变量的函数。然而问题是适应度值可能是负数，我不确定在进行选择时如何处理负值。我阅读了这篇文章遗传算法中的线性适应度缩放会产生负适应度值 ，但我不清楚如何处理负适应度值以及如何计算缩放因子 a 和 b。

另外，从文章中我知道轮盘赌选择只适用于正适应值。锦标赛选择也一样吗？

4

5 回答 5

8

当您有负值时，您可以尝试在您的群体中找到最小的适应度值，并将其相反的值添加到每个值中。这样，您将不再有负值，而适应度值之间的差异将保持不变。

于 2013-04-24T08:16:02.723 回答
6

比赛选择不受此问题的影响。它只是比较总体大小为 n 的均匀采样子集的适应度值，并取具有最佳值的那个。当然，这仍然意味着，如果您不重复抽样，那么最差的 n-1 个人将永远不会被选中。如果您重复采样，他们就有机会被选中。

与比例选择一样：它不适用于负适应度值。您只能应用健身值的“窗口化”或“缩放”，在这种情况下它们会再次起作用。

我曾经编写了一些采样方法作为 C# 的 IEnumerable 的扩展方法，其中有一个 SampleProportional 和 SampleProportionalWithoutRepetition 扩展方法。它们是 GPL 许可下 HeuristicLab 的一部分。

于 2013-04-24T10:59:10.937 回答
1

好的，现在回答已经很晚了，但仍然有人可以谷歌它。

首先 - 是的，您可以使用负适应度。但是我完全不建议你这样做，因为我已经这样做了并且遇到了很多问题（仍然可行，但完全不推荐）。所以这里是解释：

假设你有 N 个生物的种群。经过模拟，它们都有一些适应度值 f(n)，其中 f(n) 是适应度，n 是生物数量。在此之后，您想要建立一些概率分布来确定应该杀死哪些生物（当然您可以删除 40% 的最差生物，但如果您使用分布会更好）。你如何建立这样的分布？假设 f(a) = 50，并且 f(b) = 100，所以生物 b 比生物 a 好 2 倍，所以可能你想让生物 a 的生存概率比生物 b 高 2 倍（如果你的健身值是线性的）。如果您想知道如何操作：

假设 sum( f (n) ) 是所有适应度值的总和。那么生物 a 的生存概率 p(a) 为：

p(a) = f(a) / sum( f(n) )

这会成功的。

但是现在让我们允许负适应度。假设 f(a) = 50，f(b) = 100，f(c) = -1000。b 再次比 a 好 2 倍，这是有道理的，但它比 c 好 -10 倍？没有意义。上面的绅士建议你添加最差健身值的反对，这有点可以“解决”你的情况，但实际上并没有（我之前犯过同样的错误）。好的，让我们将所有健身值加 1000：

f(a) = 1050, f(b) = 1100, f(c) = 0，所以现在c的生存概率为零，好吧，我们可以接受。但是现在让我们比较 a 和 b：

b现在比a好1.05，这意味着a和b的适应度几乎相同，这是完全不能接受的，因为它显然比a好2倍（当然假设适应度是线性的，但这会搞砸非线性适应度）！你无法逃避这个问题，它会不断地妨碍你，因为概率不可能是负数，所以你可以从进化中移除概率（这不是很好的事情）或者你可以做一些例外和技巧。

由于在我的场景中消除负面适应性为时已晚，因此这是我解决问题的方法：

再一次，你有 N 个生物的种群。假设 neg(N) 为您提供所有负适应度生物和 pos(N) 正适应度生物（在这种情况下，您可以选择将零设为负数或正数，这无关紧要）。假设你需要 D 个生物去死。现在这是诀窍：

f( c ) ( c 是 pos 生物) 值越高，生物越好，所以我们可以用它的适应度来确定生存的概率。但是 f( m ) 越低（负数越大）（m 是 neg 生物），生物越差，因此我们可以使用它的适应度来确定死亡的概率。

现在，如果 D > neg(N) 那么所有 neg(N) 都会死亡，并且 pos(N) 的 (D-neg(N)) 将使用基于所有正生物适应度的概率分布（生存概率 p (a) = f(a) / sum(pos(n)))。但是如果 D < neg(N)，那么所有 pos(N) 都将存活，并且使用基于所有负生物适应度的概率分布（死亡概率p(a) = f( a) / sum( neg(n) ) (f(a) 将是负数，但 sum( neg(n) ) 也将是负数，因此概率将为正数）。

于 2019-03-30T17:23:01.520 回答
0

我知道这个问题已经存在很长时间了，但是如果新人想知道处理负值的最佳方法，那么你的问题也是最小的。这是它的代码。

from numpy import min, sum, ptp, array 
from numpy.random import uniform 

list_fitness1 = array([-12, -45, 0, 72.1, -32.3])
list_fitness2 = array([0.5, 6.32, 988.2, 1.23])

def get_index_roulette_wheel_selection(list_fitness=None):
    """ It can handle negative also. Make sure your list fitness is 1D-numpy array"""
    scaled_fitness = (list_fitness - min(list_fitness)) / ptp(list_fitness)
    minimized_fitness = 1.0 - scaled_fitness
    total_sum = sum(minimized_fitness)
    r = uniform(low=0, high=total_sum)
    for idx, f in enumerate(minimized_fitness):
        r = r + f
        if r > total_sum:
            return idx

get_index_roulette_wheel_selection(list_fitness1)
get_index_roulette_wheel_selection(list_fitness2)
  1. 确保您的健身列表是 1D-numpy 数组
  2. 将适应度列表缩放到范围 [0, 1]
  3. 将最大问题转换为最小问题 1.0 - scaled_fitness_list
  4. 随机一个介于 0 和 sum(minimizzed_fitness_list) 之间的数字
  5. 继续在最小化适应度列表中添加元素，直到我们得到大于总和的值
  6. 你可以看到适应度是否小 --> 它在最小化的适应度中具有更大的价值 --> 它有更大的机会相加并使值大于总和。
于 2020-05-22T12:23:16.613 回答
0

我认为人们在这里遇到的主要问题是他们对健身分数的处理不当。让我们考虑一个示例健身分数，例如运输冷冻货物的卡车内部的温度。卡车的内部温度应该是 -2 摄氏度……但这也是 28.4 华氏度。相对于保持冷冻的食物，它们的适合度完全相同，但是 2 * -2 = -4，而 2 * 28.4 是 56.8。“冷两倍”在这里没有任何意义（-4 C！= 14.2 F）。与健身分数相同。

在Volot 的例子中 -1000 的情况下，50 和 100 之间的差异实际上是相对较低的：重要的是你会选择 -1000 以上的任何一个/两个，如果你只是减去 - 你肯定会这样做 - 1000 从一切。那么下一代孩子的体能分数可能是 50、100、200 和 10，比方说。现在 50 和 100 之间的差异更加明显，50 被选中的机会要低得多。请记住，遗传算法是迭代的。这也让我想起了一句话：你不必跑得比熊还快。你只需要跑得比你旁边的人快。50只需要超过-1000就可以生存繁殖。

也可以避免减去最小值导致 0 的问题。在估计概率分布时，人们会在每个（已知的）可能结果中添加 1 次，这样仍然可以捕获极其罕见的事件。健身分数变得有些棘手。你不能只加 1。如果你的健康分数是 0.01、0.02 和 -0.01 怎么办？1.03、1.02 和 1.00 将导致选择低相对适应度。您可以改为将最低的非零值添加到所有内容中，得到 0.04、0.05 和 0.02。对于 -1000 的情况，它会产生 2150、2100 和 1050（因此，以前为 0 的所有内容将始终是被选中的下一个最低适应度的一半）

尽管如此，为了使事情尽可能与更典型的 GA 采样方法保持一致，我只会在存在负值时减去最小值并添加少量的适应度。当一切都是积极的，没有理由这样做。

于 2020-10-10T16:38:59.090 回答