背景
本篇是人工智能系列文章的第三篇，前两篇是 [人工神经网络算法入门] 和 [蚁群算法的简要分析]
没看过前两篇的同学也不用紧张，本篇比较简单且和之前没有太大关系。
本文所使用的代码位于 https:// github.com/wu-yu-xuan/w ordle-genetic-algorithm
欢迎感兴趣的同学阅读源码来学习。
Wordle
简介
Wordle 是一种猜字游戏，对于某个位置的字来说，如果完全正确则展示绿色，如果单词中有这个字但是位置不正确则展示橙色，如果错误则展示红色或者灰色
比如对于这个例子来说，玩家先猜“ARISE”，结果是两个错误，三个位置错误。根据这个信息玩家继续猜“ROUTE”，显示第一个字已经完全猜中了，剩下两个错误和两个位置错误。以此类推，最后猜中答案“REBUS”。
更多详情可以参考维基百科： https:// zh.wikipedia.org/wiki/W ordle
实现
接下来我们实现一个简单的 wordle
class WordleGusser {
constructor({ answer }: WordleGuesserOptions) {
this.answer = answer;
this.value = new Array(answer.length).fill("").map(() => getRandomAlpha());
this.updateScore();
}
}
其中，answer 指问题的答案，value 指当前正在猜测的值，在初始化的时候全部随机即可，这个 value 就是遗传算法中的基因。
然后根据这两个变量来更新得分和是否猜中的数组。
在这里，得分 = 100 * 猜中的个数 + 1 * 位置错误的个数。
是否猜中的数组的长度等于 value 的长度，每一项有三种可能的取值：正确、位置错误、错误。
得分和猜中数组会在遗传算法中用到。
遗传算法
遗传算法 Genetic Algorithm 是灵感来自于达尔文进化论的算法。
比如说出名的长颈鹿的例子，因为脖子短吃不到高处树叶的长颈鹿更容易被自然淘汰，因为脖子长更容易吃到高处树叶的长颈鹿更容易留下后代，同时也会存在一定的基因突变概率来随机改变包括脖子长短在内的其他性状。
和生物学上的遗传一样，遗传算法的基本单位也是“种群”，“种群”由一个个“个体”组成，在这里，每个个体就是上文提到的 wordle 个体。
class WordleGame {
constructor({ wordleGuesserLength = 50, answer }: WordleGameOptions) {
this.wordleGuesserLength = wordleGuesserLength;
this.answer = answer;
this.guesserArray = new Array(this.wordleGuesserLength).fill(0).map(() => {
return new WordleGuesser({ answer });
});
}
}
和自然一样，遗传算法分为四步： 淘汰、选种、杂交、变异 ，通过不断重复这四步，劣质的基因就会淘汰，优秀的基因就会保留，从而能够解决我们的问题。
下文只是举一个例子，事实上这四步具体需要怎幺做都可以进行调整。
淘汰
把这些个体按照得分排序，淘汰掉大约一半分数最低的个体。淘汰的方式是把 killed 字段设为 true。
我这里示例选择的是淘汰一半，这个参数是可以灵活调整的。
/**
* 第一步，淘汰
*/ kill() {
const scoreArray = Array.from(
new Set(this.guesserArray.map((x) => x.score))
).sort((a, b) => a - b);
if (scoreArray.length === 1) {
return;
}
/**
* 淘汰一半
*/ const killScoreArray = scoreArray.slice(
0,
Math.floor(0.5 * scoreArray.length)
);
this.guesserArray.forEach((x) => {
if (killScoreArray.includes(x.score)) {
x.killed = true;
}
});
}
选种
和淘汰步骤类似，把个体按照得分排序，选出得分最高的若干个个体。
到底是多少个呢？也是可以视情况灵活调整。
在这里，我先选择最高分的个体，如果最高分的个体不足两个，再选择次最高分的个体。
选中的个体会把 chosen 字段设为 true，以备后用。
/**
* 第二步，选种
*/ choose() {
const maxScore = Math.max(...this.guesserArray.map((x) => x.score));
const maxArray = this.guesserArray.filter((x) => x.score === maxScore);
maxArray.forEach((x) => x.chosen = true);
if (maxArray.length < 2) {
const secondMaxScore = Math.max(
...this.guesserArray
.filter((x) => x.score !== maxScore)
.map((x) => x.score)
);
const maxArray = this.guesserArray.filter(
(x) => x.score === secondMaxScore
);
maxArray.forEach((x) => x.chosen = true);
}
}
杂交
把选中的个体挑出来，组合它们的优质基因，替代被淘汰的个体
import { crossover } from './ga.ts'
/**
* 第三步，杂交
*/ crossover() {
const parents = this.guesserArray.filter((x) => x.chosen);
if (!parents.length) {
return;
}
for (let index = 0; index < this.guesserArray.length; index++) {
if (this.guesserArray[index].killed) {
this.guesserArray[index].setValue(crossover(parents));
}
}
}
具体来说，对于每个优质基因：
• 如果已经猜对了，则选择已经猜对的字。
• 把位置错误的父母挑选出来，如果有位置错误的父母，则在其中随机一个
• 否则在所有父母的该位基因中进行随机挑选
在对个体进行重新设置的时候，需要重置killed、chosen以及分数等参数
class WordleGuesser {
setValue(value: string[]) {
this.value = value;
this.killed = false;
this.chosen = false;
this.updateScore();
}
}
变异
变异和杂交有点类似，但是是针对所有个体，而非被淘汰的个体。
对于个体中的每个基因来说：
• 如果答对了，则不做变异
• 如果位置错误，则随机更改位置
• 如果错误，则随机生成一个字母
Be First to Comment