JavaScript 中的遗传算法

什么是遗传算法？

我的第一个遗传算法

遗传算法赛车

最后

由 Mux 主办的 DEV 全球展示挑战赛：展示你的项目！

这周我一直在尝试使用遗传算法，玩得非常开心。

什么是遗传算法？

遗传算法的灵感来源于查尔斯·达尔文的进化论。其基本原理是，最成功的个体能够繁殖并将其遗传特征传递给后代，即自然选择。

该算法包含 5 个步骤：

1. 创造新一代
2. 评估个人
3. 选拔
4. 生殖
5. 突变

重复这些步骤，直到找到目标为止。下面的示例将更详细地解释这些步骤。

我的第一个遗传算法

理解算法的最佳方法莫过于亲手编写，所以我正是这么做的。我的第一个遗传算法是用 JavaScript 和p5.js库编写的。

这个算法的目标很简单：从一个点到达另一个点，速度越快越好。所以我将生成一个圆，并对其施加一组随机的力，这些力会按顺序作用于圆上——这就是它的基因。

 createGenes() {
    let s = [];
    for (let j = 0; j < GENE_LENGTH; j++) {
       s[j] = p5.Vector.random2D();
    }
    return s;
  }

现在我们来创建一些这样的个体，这就是我们的人口：

现在，经过一段时间或某个个体达到目标后，我需要选择种群中最成功的个体进行繁殖。为此，我们需要计算其适应度函数。适应度是一个代表个体成功程度的值，通常该值会被归一化——适应度为 0.9 的个体比适应度为 0.3 的个体更优秀。

因此，要计算我示例中的适应度，我需要确定他们距离目标有多远，他们离目标越近，适应度就越高：

 calcFitness(pos) {
    const distanceToGoal = dist(pos.x, pos.y, goal.x, goal.y);
    let normalised = distanceToGoal / height;
    this.fitness = 1 - normalised;
  }

倒数第二步是选择，选择的目的是让成功的个体有更高的繁殖机会。为此，我会根据个体的适应度得分，将它们放入一个数组中。例如，适应度为 0.9 的个体将被放入数组 90 次，适应度为 0.5 的个体将被放入数组 50 次。下一代将从这个数组中随机选择，因此理论上，每一代都会变得更强。

function naturalSelection() {
  matingPool = [];
  for (let pop of population) {
    let n = floor(pop.fitness() * 100); 
    for (let i = 0; i < n; i++) {
      matingPool.push(pop);
    }
  }
}

最后一步是繁殖，所以我们将利用刚刚创建的数组找到两个随机个体，并将他们的遗传物质杂交以创造一个孩子。

function reproduce() {
  for (let i = 0; i < population.length; i++) {
    let mummyIndex = floor(random(matingPool.length));
    let daddyIndex = floor(random(matingPool.length));

    let mummy = matingPool[mummyIndex];
    let daddy = matingPool[daddyIndex];

    let child = mummy.crossover(daddy);
    child.mutate(mutationRate);
    population[i] = child;
  }
}

基因混合的术语是交叉，可以通过多种方式实现，我采用的方法是简单地组合基因，使每个元素在母系基因和父系基因之间交替：

[M,D,M,D,M,D,M,D,M,D,M,D]

 crossover(partner) {
    let child = new DNA();
    child.genes = [];
    for (let i = 0; i < this.genes.length; i++) {
      if (i % 2 ==0) {
        child.genes.push(this.genes[i]);
      } else {
        child.genes.push(partner.genes[i]);
      }
    }
    return child;
  }

交叉的另一个例子是将基因一分为二，因此孩子的基因前半部分来自父亲，后半部分来自母亲。

你会注意到，在最后一段代码之前有一行调用了mutate函数，这是最后一步——mutate 步骤使我们能够像生物突变一样维持遗传多样性。该函数接受一个参数，mutationRate该参数是一个百分比（在我的示例中为 2%）。

所以这里的代码很简单，我遍历每个基因，如果随机值小于某个阈值mutationRate，我就创建一个随机向量。

 mutate(mutationRate) {
    for (let i = 0; i < this.genes.length; i++) {
      if (random(1) < mutationRate) {
         this.genes[i] = p5.Vector.random2D(); 
      }
    }
  }

让我们看看它的实际应用：

第0代

所有动作都是完全随机的，没有任何人能够到达终点。

20世代

所有人似乎都在朝着正确的方向——向上——前进​​。不过，左右摇摆的幅度仍然很大。但至少他们最终都到达了目的地！

第五十代

现在它正以相当快的速度接近目标！不过还有很大的改进空间，我会让它再运行一段时间！

第550代

现在我们来谈谈正事⏩⏩⏩

遗传算法赛车

让一个圆飞起来其实很简单，我想增加一些难度，做一个赛车游戏，让赛车自己找到绕赛道行驶的路线。注意，以下遗传算法的所有代码都可以在这里找到。

好的，我应该添加一些碰撞检测功能和计算车辆适应度的方法。我先从最简单的开始，假设车辆存活时间越长，适应度就越高。

 calcFitness(timeAlive) {    
    this.fitness = map(timeAlive, 0, 10000, 0, 1);
  }

除了个体的基因代码代表汽车转弯的角度之外，其他一切都与之前的遗传算法基本相同——它们以恒定的速度行驶，唯一改变的是方向盘。

让我们看看他们开车！

第0代

第十代

我们已经通过了第一个弯道（绿色的车代表上一辆最成功的车，我每次迭代都会把它添加到基因库中，这样情况就不会变得更糟了！）

第五十代

我们已经绕过了第二个弯道——差不多了。似乎没多少车能到达终点，或许3%的突变率有点高。

适应度函数不足

我使用的适应度函数非常糟糕，看看下面的例子就知道了。行驶距离最远的车并不被认为是最好的，因为它存活时间并不长。所以我的适应度函数实际上是在鼓励糟糕的驾驶行为！

更好的健身功能

我相信，只要有足够的时间，我的旧健身功能或许能在几百万代之后完成它的使命，但我没有耐心看到那一幕。

检查点

我打算更新赛道，增加检查点。如果车辆通过检查点，就会增加其得分，得分就是车辆的适应度函数。这种方法应该可以避免之前出现的问题。

圆圈代表检查点（它们不可见）。

我还添加了一些代码来改变突变机制，使其只突变车辆祖先坠毁地点附近的基因。所以基本上，我不会在游戏初期损失任何车辆。

mutate(mutationRate) {

    for (let i = ancestorDiePoint-buffer; i < this.genes.length; i++) {

      if (random(1) < mutationRate) {

         this.genes[i] = random(-TURN_MAX, TURN_MAX);

      }

    }

  }

第五十代：

到了第50代，似乎末日就要到了！

第 250 代 🥳：

最后

耶，车子成功了！我创建了一个可以自主绕赛道行驶的遗传算法，太棒了！但是，如果我想把这辆到达终点的车的基因导出，放到另一条赛道上呢？那就没用了。为什么？因为转向系统/DNA是针对特定赛道的。如果我们想打造一辆可以适应任何赛道的通用自动驾驶赛车，那么我们需要的就不仅仅是遗传算法了，我们需要神经网络，我将在下周的博客中详细介绍！

这篇博客很大程度上受到了 Daniel Shiffman 在 YouTube 上开设的遗传算法课程的启发，非常感谢他！

希望您喜欢这篇博客。如果您奇迹般地喜欢上了我的絮叨，那就去我的博客网站codeheir.com看看吧，我每周都会在那里写博客，内容涵盖编程世界中所有吸引我注意力的话题！