artificial-intelligence - 优胜劣汰与遗传算法结合？

Question

我正在实现我心爱的“遗传算法”。很明显，每次选择、交叉和变异迭代后，种群数量都会大幅增加。但生物也会死亡，对吧？然而，我们都知道算法中并没有这样的规定。

所以我的问题是，为什么我们不简单地从种群本身中消除一些适应性较低的生物(并合并适者生存理论)？为什么要承担他们的负担并浪费资源(在我们的例子中是内存)？

另外，我所有的想法都是基于 Peter Norvig 的 AI 书中给出的 3 页算法解释，所以也许我的问题已经得到解决。我需要了解这些发生的事情。

另外这是我在这个平台上的第一个问题，所以社区请不要对我严厉!

Answer 1

遗传算法按照设计，通过简单地不将其基因包含在后代中来消除集合中最弱的解决方案。

遗传算法如何选择谁生谁死

摘要:想象一下算法正在选择为下一代选择、组合和变异哪些解决方案。每个解都被放在飞镖盘上，但更好的解会占用飞镖盘上更多的空间，因此当算法扔飞镖时，更有可能击中更合适的解。事实上，它甚至可能多次遇到同一个解决方案。

一旦它从飞镖板上获得了它的解决方案集(通常与原始集的群体大小相同，但可能包含来自多个飞镖击中相同解决方案的重复项)，您就可以获取该集，并通过随机切换来“变异”它们解决方案的一部分。然后，您可以“配对”解决方案，这是一个非常性感的过程，您可以在新一代中随机选择部分解决方案，并将它们组合起来形成最终的生成集。

然后重复此过程。

没有飞镖击中的解决方案会发生什么？这完全取决于您的语言和数据结构，但它们可能是刚刚被垃圾收集的对象。

实际代码

这是我在处理(Java)中编写的一些代码，用于模拟 throw 飞镖的过程

我只是将生物体称为 float 组列表，但它们可以是任何东西

 ArrayList<Float> normalize(ArrayList<Float> inputArray){
   float sum = 0; 
   ArrayList<Float> outputArray = new ArrayList<Float>();
   for(int i = 0; i < inputArray.size(); i++){
    sum += inputArray.get(i); 
   }
   for(int i = 0; i < inputArray.size(); i++){
    outputArray.add(inputArray.get(i)/sum); 
   }
   return outputArray;
  }

ArrayList<Float> pick(ArrayList<ArrayList> parents, ArrayList<Float> fitness){
   float searchVal = random(0, 1);
   float fitTotal = 0;
   int fitIndex = 0;
   while(searchVal > fitTotal && fitIndex < fitness.size()){
    fitTotal += fitness.get(fitIndex); 
    fitIndex++;
   }
   if(fitIndex != 0){
    return parents.get(fitIndex-1); 
   }
   else{
    return parents.get(0); 
   }
  }

它是如何工作的

这段代码包含两个方法；标准化方法和选择方法。

归一化方法获取每个解决方案的适应度级别，并将其“归一化”为一个数组，其中每个适应度级别除以总数。这将导致每个健身水平占总水平的百分比。它们加起来都是一。

然后，pick 方法将接受这个标准化数组以及父解决方案数组(必须与健身级别的顺序相同)，并选择一个随机数 0-1，并且该数字将与特定的匹配健身水平和算法将“选择”该 parent 进行繁殖。

您会注意到，适应度较高的解决方案被“选择”的机会较高

应该对下一代想要的每个生物体重复这种“挑选”方法。

编辑

OP 提到他们理解飞镖盘的类比，并且想知道是否有必要将坏的东西从飞镖盘上完全清除。一开始挑出坏后代的机会就很低，但像这样的手动修剪也能起到作用。

我认为这在您不希望解决方案具有非常糟糕的特征的情况下非常有用，并且您不希望将它们放入下一组中。