遗传算法中的线性适应度缩放会产生负适应度值

发布于 2024-11-19 14:12:14 字数 966 浏览 2 评论 0原文

我有一个具有适应度函数的 GA，可以评估负值或正值。为了解决这个问题，我们假设函数

u = 5 - (x^2 + y^2)

x in [-5.12 .. 5.12]
y in [-5.12 .. 5.12]

img src="https://i.sstatic.net/jRtYP.png" alt="Example Fitness function">

现在处于选择阶段我正在使用的 GA 简单轮盘赌轮。由于为了能够使用简单的轮盘赌轮，我的适应度函数对于人群中的具体情况必须是积极的，因此我开始寻找扩展解决方案。最自然的似乎是线性健身缩放。它应该非常简单，例如查看 this实施。但是，我即使在线性缩放后也得到负值。

例如，对于上述函数和这些适应度值：

-9.734897  -7.479017 -22.834280  -9.868979 -13.180669   4.898595

在线性缩放之后，我得到这些值

-9.6766040 -11.1755111  -0.9727897  -9.5875139  -7.3870793 -19.3997490

相反，我想将它们缩放为正值，这样我就可以在下一阶段进行轮盘赌选择。

我一定在这里做了一些根本性错误的事情。我应该如何解决这个问题？

原文

I have a GA with a fitness function that can evaluate to negative or positive values. For the sake of this question let's assume the function

u = 5 - (x^2 + y^2)

where

x in [-5.12 .. 5.12]
y in [-5.12 .. 5.12]

Example fitness function

Now in the selection phase of GA I am using simple roulette wheel. Since to be able to use simple roulette wheel my fitness function must be positive for concrete cases in a population, I started looking for scaling solutions. The most natural seems to be linear fitness scaling. It should be pretty straightforward, for example look at this implementation. However, I am getting negative values even after linear scaling.

For example for the above mentioned function and these fitness values:

-9.734897  -7.479017 -22.834280  -9.868979 -13.180669   4.898595

after linear scaling I am getting these values

-9.6766040 -11.1755111  -0.9727897  -9.5875139  -7.3870793 -19.3997490

Instead, I would like to scale them to positive values, so I can do roulette wheel selection in the next phase.

I must be doing something fundamentally wrong here. How should I approach this problem?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

烏雲後面有陽光 2024-11-26 14:12:14

主要错误是线性缩放的输入必须已经是正值（根据定义），而我获取的也是负值。

关于负值的讨论不是关于算法的输入，而是关于算法的输出（缩放值）。检查的目的是处理这种情况，然后纠正它，以免产生负缩放值。

  if(p->min > (p->scaleFactor * p->avg - p->max)/
     (p->scaleFactor - 1.0)) { /* if nonnegative smin */
    d = p->max - p->avg;
    p->scaleConstA = (p->scaleFactor - 1.0) * p->avg / d;
    p->scaleConstB = p->avg * (p->max - (p->scaleFactor * p->avg))/d;
  } else {  /* if smin becomes negative on scaling */
    d = p->avg - p->min;
    p->scaleConstA = p->avg/d;
    p->scaleConstB = -p->min * p->avg/d;
  }

下图中，如果 f'min 为负数，则转到 else 子句并处理这种情况。

那么解决方案是对上述函数进行预缩放，因此它只给出正值。正如 Hyperboreus 所建议的，这可以通过添加尽可能小的值来完成。

u = 5 - (2*5.12^2)

最好将我们试图最大化的真实适应度值与输入的缩放适应度值分开。到遗传算法的选择阶段。

在此处输入图像描述

The main mistake was that the input to linear scaling must already be positive (by definition), whereas I was fetching it also negative values.

The talk about negative values is not about input to the algorithm, but about output (scaled values) from the algorithm. The check is to handle this case and then correct it so as not to produce negative scaled values.

  if(p->min > (p->scaleFactor * p->avg - p->max)/
     (p->scaleFactor - 1.0)) { /* if nonnegative smin */
    d = p->max - p->avg;
    p->scaleConstA = (p->scaleFactor - 1.0) * p->avg / d;
    p->scaleConstB = p->avg * (p->max - (p->scaleFactor * p->avg))/d;
  } else {  /* if smin becomes negative on scaling */
    d = p->avg - p->min;
    p->scaleConstA = p->avg/d;
    p->scaleConstB = -p->min * p->avg/d;
  }

On the image below, if f'min is negative, go to else clause and handle this case.

Well the solution is then to prescale above mentioned function, so it gives only positive values. As Hyperboreus suggested, this can be done by adding the smallest possible value

u = 5 - (2*5.12^2)

It is best if we separate real fitness values that we are trying to maximize from scaled fitness values that are input to selection phase of GA.

enter image description here

回复收藏 0 原文