遗传算法：创建自己的遗传算法

书名：代码本色：用编程模拟自然系统
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
第9章目录

9.9　遗传算法：创建自己的遗传算法

使用遗传算法有一个好处：可以将示例代码轻易地移植到另一个应用中，因为选择和繁殖的核心代码可以保持不变。
定制遗传算法的关键点有3个，这3点都非常重要，它们能帮你跳出示例程序，在Processing或其他开发环境中创造性地使用遗传算法。

第1点：更改变量

遗传算法并没有多少变量。仔细看前面的例子，你只能发现两个全局变量（不包括存放种群的数组和存放交配池的ArrayList）。

float mutationRate = 0.01;
int totalPopulation = 150;

这两个变量能显著地影响系统行为，不建议随意地给它们赋值（尽管不断地试错也能得到最优解，且不失为一种合理方法）。
在莎士比亚名言示例程序中，选择的参数值能算出正确答案，但是计算速度不够快（平均为1000代左右），这么做是为了用一段合理的时间演示计算过程。随着种群个体数量的增多，遗传算法的计算速度也会变得更快。
下表列出了不同规模种群的效率：

个体数量	突变率	解决问题所需代数	解决问题所需时间(秒）
150	1%	1089	18.8
300	1%	448	8.2
1000	1%	71	1.8
50 000	1%	27	4.3

注意：随着种群规模不断增大，求解问题所需的代数急剧减少。
然而，这不一定能减少总时间。
一旦种群中个体数量超过50 000，Sketch的运行速度会变得很慢，因为随
着个体数量增加，适应度计算和交配池构建所需的时间也会变长。（当然，你可以为大规模的种群做更多优化。）
除了种群规模，突变率也能显著影响性能。
在没有突变（突变率为0%）的情况下，能否得到正确的结果还要靠运气。
如果所有正确的字符都出现在种群的初始个体中，你就能很快进化出正确结果。
如果初始个体不包含所有的正确字符，你永远也得不到正确结果。
重复运行几次以上程序，你就能碰到这两种情况。
除此之外，如果突变率高于某个值（假如是10%），进化过程将会出现很高的随机性（在每个子代个体中，1/10的字符是随机确定的），因此模拟过程就变成了纯粹的随机枚举。从理论上讲，它最终会得到正确的答案，但你可能要等很久，甚至等待时间远远超出合理值。

第2点：适应度函数

1）重点

更改突变率或种群规模是一件很容易的事，你只需要在Sketch中输入几个数字。对遗传算法而言，真正的困难在于实现适应度函数。
如果无法定义问题的目标或无法用数值衡量目标的完成度，你就不能正确地实现遗传算法。

2）适应度分值

在讨论其他适应度函数之前，让我们看看莎士比亚适应度函数中的几个缺陷。
假如目标短语的字符数不是19个，而是上千个。
如果种群中有两个个体，其中某个个体的正确字符数是800，而另一个个体的正确字符数是801。它们的适应度分值如下：

句子B	801个正确字符	适应度 = 80.1%
句子A	800个正确字符	适应度 = 80%

这里存在几个问题。
首先，我们要在交配池中多次添加某一个体，假设添加次数为N，N等于适应度乘以100。
对象只能在ArrayList中添加整数次，因此，A和B对象的添加次数都是80次，也就是说它们被选中的概率相等。
尽管我们可以用浮点概率改进这个问题，但是80.1%的概率只比80%多出0.1%。
但在进化场景中，801个正确字符的效果比800个正确字符好很多。我们需要让多出来的那个字符产生应有的效果，让前者的适应度分值明显高于后者。
换一种方式，让我们用图形表示适应度函数。

这是一个线性函数，在正确字符数增加的过程中，适应度分值也随之增大。

适应度随着正确字符的增加呈指数性增长
正确字符的数量越多，适应度的增长越快。
我们可以用多种方法实现这一效果，比如以下方式：
适应度 = 正确字符数 × 正确字符数
假如种群中有2个个体，个体A有5个正确字符，个体B有6个正确字符。A的正确字符数比B多20%。进行平方计算后，得到的适应度分值如下表所示。

正确字符数	适应度
5	25
6	36

随着正确字符数的增加，适应度分值呈指数性增长。B的适应度分值比A高44%。

还有另一个公式：
$适应度分值 = 2^{正确字符的数量}$
在这个公式中，适应度分值的增长速度更快，每增加一个字符，分值就翻倍。

3）定制

请设计你自己的适应度函数！并不是所有用到的遗传算法项目都涉及字符的计数。
你可能会在粒子系统中使用遗传算法，让其中的粒子发生进化；
或在自治智能体中用遗传算法优化转向行为的权重，让个体可以避开障碍或走出迷宫。
在设计适应度函数之前，你要先问自己想评估哪些参数。
假如你正在模拟竞速，需要用遗传算法求解小车的最佳速度。
适应度函数可以这么设计：
适应度 = 小车到达目标需要的帧数
假如你要用遗传算法求解导弹的最佳发射轨迹。
适应度函数可以这么设计：
适应度 = 导弹和靶子之间的距离
在电脑游戏中，NPC角色（由电脑控制的角色）的设计也常常用到遗传算法。
假如你正在设计足球游戏，在这个游戏中，守门员由用户操纵，其他球员由程序操纵。程序要通过一系列的射门参数控制这些球员，我们可以用以下方式设计适应度函数：
适应度 = 总进球数
对足球游戏来说，这是再简单不过的一种实现方式，但它恰好说明了问题的关键：球员的进球数越多，适应度越高，进入下一轮游戏的概率也越大。虽然这个适应度函数很简单，但它展现了遗传算法的强大之处——系统的适应能力。
在球员进化过程中，如果突然换了一个新人类玩家（和完全不同的策略），系统会马上发现原先的适应度分值变低，需要进化出新的策略。
也就是说，系统有适应能力！（不要担心，由此产生的机器人并不会奴役人类。）

最后，如果适应度函数不能有效地评估个体的表现，你将无法使系统发生进化。
某个特定程序的适应度函数并不适合用在其他项目上。
因此，你需要发挥自己的才智，重新设计自己的适应度函数。
fitness()函数的功能就是计算适应度分值，你只需修改它的实现就能创建自己的适应度函数。

void fitness() {
    ????????????
    ????????????
    fitness = ??????????
}

第3点：基因型和表现型

最后一个关键点和系统属性的编码方式有关。
在设计遗传算法之前，你需要问自己几个问题。
你想表达什么？如何把要表达的东西转化为一串数字？什么是系统的基因型和表现型？
在足球游戏的讨论中，我们假定电脑控制的球员有“一系列控制射门方式的参数”。
这些参数和它们的编码方式就是对应的基因型，我们应该设计这些参数。
我们之所以从莎士比亚名言的示例开始讨论遗传算法，很大一部分原因在于它的基因型（字符数组）和表现型（显示在窗口上的字符串）很容易设计。
设计基因型和表现型。
当你在实现某个类时，需要加入一系列变量。

class Vehicle {
    float maxspeed;
    float maxforce;
    float size;
    float separationWeight;
    //……

为了进化这些变量，我们需要将它们转化为数组。
这样一来，我们就可以在数组上使用DNA类的crossover()、mutate()等函数。对此，一种常用的方案是用介于0~1的浮点数填充整个数组。

class DNA {
    float[] genes; 浮点数组
    DNA(int num) {
        genes = new float[num];
        for (int i = 0; i < genes.length; i++) {
                genes[i] = float(1); 挑选介于0~1的浮点数
        }
    }
}

注意我们如何将遗传信息（基因型）和表达（表达型）放到两个不同的类中。
DNA类就是基因型，Vehicle类需要用DNA对象驱动自身行为，还要用可视化方式表达遗传信息，因此Vehicle类就是表现型。
只要在Vehicle类内部放入一个DNA实例，就可以在两者之间建立联系。

class Vehicle {
    DNA dna; 在Vehicle类中添加DNA对象
    float maxspeed;
    float maxforce;
    float size;
    float separationWeight;
    Vehicle() {
        DNA = new DNA(4);
        maxspeed = dna.genes[0]; 用基因设置变量
        maxforce = dna.genes[1];
        size = dna.genes[2];
        separationWeight = dna.genes[3];
        }
}

当然，你并不希望所有变量都落在0~1。
我们可以用Processing的map()函数把遗传信息映射到合适的范围，比起在DNA类中维护范围，用map()函数映射范围更简单。举个例子，如果你想获得一个介于10~72的长度变量，可以这么做：

size = map(dna.genes[2], 0, 1, 10, 72);

在某些情况下，你会把基因型设计成一个对象数组。
考虑火箭模型的设计：火箭中有一组“推进器”引擎，你可以用PVector对象描述每个推进器的推进方向和动力强度。

class DNA {
    PVector[] genes; 基因型是向量数组
    DNA(int num) {
    genes = new float[num];
    for (int i = 0; i < genes.length; i++) {
        genes[i] = PVector.random2D(); 指向随机方向的向量
        genes[i].mult(random(10)); 将向量设为随机长度
        }
    }
}

我们用一个Rocket类实现表现型，让它参与物理系统的模拟。

class Rocket {
    DNA dna;
    //……
}

把基因型和表现型实现为不同的类（如DNA和Rocket），这么做有一个很大的好处：
之前开发的DNA类可以保持不变，你只需要更改基因数组的数据类型（float、PVector对象等），并在表现型中实现数据的表达。
在下一节，我们会按照这些思路继续往下走，用具体的实例讲解这些步骤。以下实例同时包含了运动物体和由向量数组描述的DNA对象。