4

我想知道以下内容：如何使用值编码有效地生成具有高多样性的染色体？一种方法是网格初始化，但它太慢了。

到目前为止，我一直在使用 .NET 中的 Random 类在值编码中选择随机值，但是，尽管值是均匀分布的，但从这些染色体计算出的适应度函数值却不是。这是染色体初始化的代码：

 public Chromosome(Random rand) 
        {
            Alele = new List<double>();
            for (int i = 0; i < ChromosomeLength; i++)
            {
                Alele.Add(rand.NextDouble() * 2000 - 1000);
            }
        }

因此，我开发了一个从新的、随机生成的染色体（上码）计算适应度的函数，如果适应度与染色体列表中已经存在的任何其他染色体相似，则随机生成一个新染色体并计算其适应度并重复此过程直到他的健康状况与列表中的其他人没有足够的差异。

这是这部分的代码：

private bool CheckSimilarFitnes(List<Chromosome> chromosome, Chromosome newCandidate) 
    {
     Boolean flag=false;
     double fitFromList, fitFromCandidate;
     double fitBigger,fitSmaller;

     foreach (var listElement in chromosome)
      {  
      fitFromList = listElement.CalculateChromosomeFitness(listElement.Alele);
      fitFromCandidate = newCandidate.CalculateChromosomeFitness(newCandidate.Alele);
      fitBigger = fitFromList >= fitFromCandidate ? fitFromList : fitFromCandidate;
      fitSmaller =  fitFromList < fitFromCandidate ? fitFromList : fitFromCandidate;

            if ((fitFromList / fitFromCandidate) < 1.5) 
                return false
      }

     else return true;

    }

但是，我在列表中拥有的染色体越多，添加一个新的染色体就越需要更长的时间，其适应度与已经存在的其他染色体有足够的不同。

那么，有没有办法让这个网格初始化更快，像这样制作 80 条染色体需要几天时间？

4

5 回答 5

2

这里的基本问题是大多数随机生成的染色体具有相似的适应度，对吧？没关系; 这个想法并不是让您的初始染色体具有截然不同的适应度；这是因为染色体本身不同，而且可能它们是不同的。事实上，您应该期望大多数第一代的初始适应度接近于零，因为您还没有运行算法。

这就是您的代码如此缓慢的原因。假设第一个候选人很糟糕，基本上是零适应度。如果第二个必须有 1.5 倍的不同，那真的只是意味着它必须要好 1.5 倍，因为它不会变得更糟。然后下一个必须比那个好 1.5 倍，以此类推到 80 倍。所以你真正要做的是通过生成完全随机的染色体并将它们与你拥有的染色体进行比较来寻找越来越好的染色体。我敢打赌，如果您记录进度，您会发现找到后续候选者需要越来越多的时间，因为很难找到真正好的染色体。但是寻找更好的染色体是遗传算法的目的！基本上你所做的是之前手动优化了一些染色体，嗯，实际上优化了它们。

如果你想确保你的染色体是多样化的，那就比较它们的内容，不要比较它们的适合度。比较适应度是算法的工作。

于 2012-09-22T01:02:36.470 回答
2

这里有一些可能有帮助的代码（我刚刚写的）：GA for ordering 10 values spaced by 1.0。它从 100 个完全随机的等位基因群开始，这正是您的代码开始的方式。

我给 GA 解决的目标是以 1.0 的间隔按递增顺序排列值。它Eval_OrderedDistance通过从 1.0 计算每对样本的标准差来在适应度函数中做到这一点。随着适应度趋于 0.0，等位基因应该开始按顺序出现。

第 0 代最适合的染色体是完全随机的，其他染色体也是如此。可以看到适应度值非常高（即不好）：

GEN: fitness   (allele, ...)
  0: 375.47460 (583.640, -4.215, -78.418, 164.228, -243.982, -250.237, 354.559, 374.306, 709.859, 115.323)

随着世代的继续，适应度（与 1.0 的标准差）会下降，直到在第 100,000 代时接近完美：

  100: 68.11683 (-154.818, -173.378, -170.846, -193.750, -198.722, -396.502, -464.710, -450.014, -422.194, -407.162)
  ...
10000:  6.01724 (-269.681, -267.947, -273.282, -281.582, -287.407, -293.622, -302.050, -307.582, -308.198, -308.648)
  ...
99999:  0.67262 (-294.746, -293.906, -293.114, -292.632, -292.596, -292.911, -292.808, -292.039, -291.112, -290.928)

代码中有趣的部分是适应度函数：

// try to pack the aleles together spaced apart by 1.0
// returns the standard deviation of the samples from 1.0
static float Eval_OrderedDistance(Chromosome c) {
    float sum = 0;
    int n = c.alele.Length;
    for(int i=1; i<n; i++) {
        float diff = (c.alele[i] - c.alele[i-1]) - 1.0f; 
        sum += diff*diff; // variance from 1.0
    }

    return (float)Math.Sqrt(sum/n);
}

还有突变。我使用了一个简单的交叉和“完全突变一个等位基因”：

Chromosome ChangeOne(Chromosome c) {
    Chromosome d = c.Clone();
    int i = rand.Next() % d.alele.Length;
    d.alele[i] = (float)(rand.NextDouble()*2000-1000);
    return d;
}

我使用精英主义来始终保留一份最好的染色体的精确副本。然后使用突变和交叉生成 100 条新染色体。

听起来您确实在计算适应度的方差，这当然会告诉您总体中的适应度几乎相同。我发现如何定义健身功能非常重要。适应度函数越精细，您就越能区分染色体。显然，您的适应度函数为完全不同的染色体返回相似的值，因为您的第 0 代返回的适应度方差为 68e-19。

你能分享你的健身计算吗？或者您要求 GA 解决什么问题？我认为这可能会帮助我们帮助你。

[编辑：添加明确的健身分享/利基]

我重新考虑了一下并更新了我的代码。如果你想保持独特的染色体，你必须比较它们的内容（正如其他人提到的那样）。一种方法是计算它们之间的标准偏差。如果它小于某个阈值，则可以将它们视为相同。从染色体类：

// compute the population standard deviation
public float StdDev(Chromosome other) {
    float sum = 0.0f;
    for(int i=0; i<alele.Length; i++) {
        float diff = other.alele[i] - alele[i];
        sum += diff*diff;
    }
    return (float)Math.Sqrt(sum);
}

我认为Niching会给你你想要的。它比较群体中的所有染色体以确定它们的相似性，并为每个染色体分配一个“利基”值。然后使用一种称为“显式健身共享”的技术对染色体进行“惩罚”，因为它们属于某个生态位。适应度值除以每个生态位中的染色体数量。因此，如果您在利基组 A (A,A,A) 中有三个而不是该利基被选择的可能性是其 3 倍，则它被视为单个实体。

我将我的样本与 Explicit Fitness Sharing 开启和关闭进行了比较。最大 STDDEV 为 500 且 Niching 关闭时，大约有 18-20 个壁龛（所以基本上 100 人口中每个项目有 5 个重复）。启用 Niching 后，大约有 85 个壁龛。那是人口中 85% 的独特染色体。在我的测试输出中，您可以看到17000 代后的多样性。

这是利基代码：

// returns: total number of niches in this population
// max_stddev -- any two chromosomes with population stddev less than this max
//               will be grouped together
int ComputeNiches(float max_stddev) {
    List<int> niches = new List<int>();

    // clear niches
    foreach(var c in population) {
        c.niche = -1;
    }

    // calculate niches
    for(int i=0; i<population.Count; i++) {
        var c = population[i];
        if( c.niche != -1) continue; // niche already set

        // compute the niche by finding the stddev between the two chromosomes 
        c.niche = niches.Count;
        int count_in_niche = 1; // includes the curent Chromosome
        for(int j=i+1; j<population.Count; j++) {
            var d = population[j];
            float stddev = c.StdDev(d);
            if(stddev < max_stddev) {
                d.niche = c.niche; // same niche
                ++count_in_niche;
            }
        }
        niches.Add(count_in_niche);
    }

    // penalize Chromosomes by their niche size
    foreach(var c in population) {
        c.niche_scaled_fitness = c.scaled_fitness / niches[c.niche];
    }

    return niches.Count;
}

[编辑：安东代码的后期分析和更新]

我知道这可能不是解决家庭作业问题的正确论坛，但由于我在知道这一点之前就做了努力，而且我从中获得了很多乐趣，我认为它只会对 Anton 有所帮助。

Genotip.cs , Kromosom.cs , KromoMain.cs

这段代码保持了良好的多样性，我能够在一次运行中将“原始适应度”降低到 47，在你的情况下，这是平均平方误差。那是相当接近！

正如我在评论中指出的那样，我想尝试帮助您进行编程，而不仅仅是帮助您完成作业。请阅读这些对您工作的分析。

  1. 正如我们所料，没有必要从一开始就制造“更加多样化”的人口。只需生成一些完全随机的 Kromosomes。

  2. 你的突变和交叉具有很强的破坏性，而你只有其中的几个。我添加了几个似乎更适合解决此问题的新运算符。

  3. 你扔掉了最好的解决方案。当我让您的代码仅使用 Tournament Selection 运行时，将会有一个 Kromo 比其他所有的要好 99%。通过锦标赛选择，这个最佳价值很可能被遗忘。我添加了一些“精英主义”，为下一代保留了该价值的副本。

  4. 考虑面向对象的技术。将我发送给您的重写代码与我的原始代码进行比较。

  5. 不要重复代码。您有两个不同类别的采样参数。

  6. 保持代码干净。有几个未使用的代码部分。特别是在向 SO 提交问题时，尝试缩小范围，删除未使用的代码，并进行一些清理。

  7. 评论你的代码！我对重做的工作发表了重要的评论。我知道这是塞尔维亚语，但即使是一些评论也会帮助其他人了解你在做什么以及你打算做什么。

  8. 总的来说，很好地实现了一些更复杂的东西，比如锦标赛选择

  9. 更喜欢 double[] 数组而不是 List。开销更少。此外，甚至不需要您的几个 List 临时变量。你的结构

    列表临时 = 新列表（）；for(...) { temp.add(value); } for(temp 中的每个值) { sum += value } average = sum / temp.Count

可以很容易地写成：

sum = 0
for(...) {
    sum += value;
}
average = sum / count;

  1. 在几个地方，您忘记初始化循环变量，这很容易添加到您的问题中。这样的事情会导致严重的问题，而且它在你的健身代码中以及其他一两个地方

    双重拟合 = 0; for(每个染色体) { // 你应该在循环内初始化 fit 这里for(each allele) { fit += ...; } 适合 /= 计数；}

祝编程好运！

于 2012-09-22T14:16:44.537 回答
1

我要快速解决这个问题，但 Isaac 是非常正确的。你需要让 GA 完成它的工作。你有一代人（染色体，等等），而且他们在健康方面都在规模上（或者也许他们都是相同的）。

你选择一些好的来变异（自己）和交叉（彼此）。您可能会使用前 10% 来生成另一个完整的人口，并丢弃底部的 90%。也许你总是把头号人物留在身边（精英主义）。

您在此迭代一段时间，直到您的 GA 停止改进，因为每个人都非常相似。你最终的人口多样性很少。

可能对您有所帮助的是 1) 使您的突变更有效，2) 找到更好的方法来选择个体进行突变。在我的评论中，我向游戏程序员推荐了 AI 技术。这是一本很棒的书。非常容易阅读。

要列出书中的一些标题，您要查找的内容是：

轮盘选择（在 stackoveflow 上）（在wikipedia上）和Stochastic Universal Sampling等选择技术，它们控制您选择个人的方式。我一直很喜欢轮盘赌选择。您设置个人被选中的概率。这不仅仅是简单的白噪声随机抽样。

我在 GA 之外使用它从罗马字母中随机选择 4 个字母。我为每个字母分配了一个从 0.0 到 1.0 的值。每次用户（孩子）正确选择字母时，我都会将该值降低，例如 0.1。这将增加选择其他字母的可能性。如果 10 次后，用户选择了正确的字母，则该值为 0.0，并且（几乎）没有机会再次显示该字母。

Fitness Scaling技术，如 Rank Scaling、Sigma Scaling 和Boltzmann Scaling（ftp 上的 pdf 文件！！！）可让您修改原始健身值以得出调整后的健身值。其中一些是动态的，例如玻尔兹曼缩放，它允许您设置随时间变化的“压力”或“温度”。增加的“压力”意味着选择了更健康的个体。压力降低意味着可以选择人群中的任何个体。

我是这样想的：您正在多维空间中寻找解决方案。你达到了一个“高峰”并努力进入它。适合的压力非常大。你紧贴当地的最大值。现在你的体能不能改变。你的突变不会让你走出高峰。所以你开始减少压力，哦，随机选择项目。你的健康水平开始下降，这在一段时间内是可以的。然后你又开始增加压力，惊喜！您已经跳过了局部最大值，并找到了一个可爱的新局部最大值。再次加大压力！

Niching（我从未使用过，但似乎是将相似的人组合在一起的一种方式）。假设你有两个非常好的人，但他们完全不同。他们不断被选中。他们不断地发生轻微的变异，并没有变得更好。现在你有一半的人口是 A 的次要变体，一半的人口是 B 的次要变体。这似乎是一种说法，嘿，整个 A 组的平均适应度是多少？B呢？以及您拥有的所有其他利基市场。然后根据每个利基的平均适应度进行选择。选择您的利基市场，然后从该利基市场中随机选择一个人。也许我会开始使用它。我喜欢！

希望您能从中找到一些帮助！

于 2012-09-22T02:21:43.113 回答
0

如果您的应用程序需要真正的随机数，我建议您查看Random.org。他们有一个免费的 HTTP API，以及几乎所有语言的客户端。

随机性来自大气噪声，在许多方面它优于计算机程序中通常使用的伪随机数算法。

（我与 Random.org 无关，尽管我确实贡献了 PHP 客户端）。

于 2012-09-22T00:31:55.113 回答
0

我认为您的问题在于您的适应度函数如何以及如何选择候选人，而不是随机值的多少。您的过滤感觉过于严格，甚至可能不允许接受足够的元素。

样本

  • 值：随机浮点 0-10000。
  • 适应度函数平方根(n)
  • 所需的适应度分布 - 与距离至少为 1 呈线性关系。

使用此适应度功能，您将快速获得大部分 1 宽“点”（因为您最多有 100 个位置），因此每个下一个将花费更长的时间。在某些时候，会留下几个很小的范围，并且大多数结果都会被拒绝，更糟糕的是，在您获得大约 50 个数字位置之后，下一个数字很可能根本无法拟合。

于 2012-09-22T01:09:40.307 回答