1.传统遗传算法： 随着猜测答案的迭代次数增加，答案可以发生进化（如二分法猜数） 2.交互式选择 用户点击过A后，程序根据A自动产生（进化出）与A相似的搜索结果 3.生态系统模拟
尽管计算机对进化过程的模拟可以追溯到20世纪50年代，但大部分人认为当今的遗传算法（Genetic Algorithm，GA）是由密歇根大学的约翰·霍兰德教授率先提出的。
求解答案已知的问题有助于我们验证算法的正确性。一旦遗传算法成功地解决了这个问题，它的有效性就能得到证明。我 们就能以更自信的心态用它求解答案未知的问题。所以，第一个示例的目的仅仅在于 演示遗传算法的工作原理。如果GA算出的结果和已知结果相同，就代表它已被正确地实现。
遗传领域有两个重要概念：基因型和表现型，两者之间有重要区别。基因型 （genotype）就是遗传密码，也就是本例的字符串，它会从父代传给子代；表现型 （phenotype）就是基因型的表达。
1.评估适应度 为了让遗传算法有效，我们需要设计一个适应度函数。这个函数会产生一个描述个体 适应度的分值。 再一次简化这个问题，假设我们只想进化出单词“cat”,“car”有两个正确字符，它的适应度最高。“hut”只有一个正 确字符，“box”没有正确字符。 因此，适应度函数如下： 适应度 = 正确字符的数量
2.创建交配池 概率方法，我们称为“命运之轮” 假设种群中有5个个体，它们都有自己的适应度分值。
1.交叉
2.突变 突变的作用就是在进化过程中不断引入多样性。 一个遗传算法可能有5%、1%或0.1%的突变率。假设交叉完成后，某子代个体是“FORY”，如果突变率为1%，这意味着每个字符有1%的突变概 率。而字符怎么发生突变呢？
在本例中，我们把突变定义为用一个随机的字符替换原字符。
在获得新种群之前，我们会不断地进行选择（选择两个父本）和繁殖（交叉和突变） 操作。一旦子代种群代替了当前种群，我们还会回到之前的步骤：再次评估适应度， 再次进行选择和繁殖操作。
SETUP 第1步：初始化 创建由N个个体组成的种群，随机确定个体的DNA。
LOOP 第2步：选择 评估个体的适应度，创建交配池。 第3步：繁殖 重复N次。 a) 根据相对适应度，概率性地选择两个父本。 b) 杂交——结合父本的DNA，创建出一个“子代个体”。 c) 突变——以一定的概率使子代的DNA发生突变。 d) 将这个子代加入新种群。 第4步：用新种群替换旧种群，再回到第2步。
class DNA { char[] genes = new char[18]; DNA() { for (int i = 0; i < genes.lenght; i++) { genes[i] = (char) random(32,128); //从编号为32~128的ASCII字符中随机选择一系列字 } } } String target = "to be or not to be"; class DNA { float fitness; //在DNA类中加入一个适应度变量 void fitness () //该函数的作用是计算适应度 { int score = 0; for (int i = 0; i < genes.length; i++) { if (genes[i] == target.charAt(i)) //字符是否正确 { score++; //如果正确，增加分值 } } fitness = float(score)/target.length(); //适应度就是正确字符的百分比 } } void mutate() { for (int i = 0; i < genes.length; i++) //遍历数组中的每个基因 { if(random(1) < mutationRate) { genes[i] = (char) random(32,128); //突变，产生随机字符 } } }遗传算法：进化出莎士比亚名言
float mutationRate; //突变率 int totalPopulation = 150; //个体总数 DNA[] population; //个体数组 ArrayList<DNA> matingPool; //交配池数组 String target; //目标答案 void setup() { size(200, 200); target = "to be or not to be"; //初始化目标答案和突变率 mutationRate = 0.01; population = new DNA[totalPopulation]; //步骤1：初始化种群 for (int i = 0; i < population.length; i++) { //步骤2a：计算适应度 population[i] = new DNA(); } } void draw() { for (int i = 0; i < population.length; i++) { //步骤2：选择 population[i].fitness(); } ArrayList<DNA> matingPool = new ArrayList<DNA>(); //步骤2b：创建交配池 for (int i = 0; i < population.length; i++) { int n = int(population[i].fitness * 100); //根据适应度分值将个体加入交配池 for (int j = 0; j < n; j++) { matingPool.add(population[i]); } } for (int i = 0; i < population.length; i++) { //步骤3：繁殖 int a = int(random(matingPool.size())); int b = int(random(matingPool.size())); DNA partnerA = matingPool.get(a); DNA partnerB = matingPool.get(b); DNA child = partnerA.crossover(partnerB); //步骤3a：交叉 child.mutate(mutationRate); //步骤3b：变异 population[i] = child; //用新的子代覆盖种群draw()循环会重复执行这些步骤 } } class DNA { char[] genes; float fitness; DNA() { //随机地创建DNA genes = new char[target.length()]; for (int i = 0; i < genes.length; i++) { genes[i] = (char) random(32,128); } } void fitness() { //计算适应度 int score = 0; for (int i = 0; i < genes.length; i++) { if (genes[i] == target.charAt(i)) { score++; } } fitness = float(score)/target.length(); } DNA crossover(DNA partner) { //交叉 DNA child = new DNA(genes.length); int midpoint = int(random(genes.length)); for (int i = 0; i < genes.length; i++) { if (i > midpoint) child.genes[i] = genes[i]; else child.genes[i] = partner.genes[i]; } return child; } void mutate(float mutationRate) { //突变 for (int i = 0; i < genes.length; i++) { if (random(1) < mutationRate) { genes[i] = (char) random(32,128); } } } String getPhrase() { //转化为字符串——表现型 return new String(genes); } }*突变率的意义 在没有突变（突变率为0%）的情况下，能否得到正确的结果还要靠运气。 如果所有正确的字符都出现在种群的初始个体中，你就能很快进化出正确结果。 如果初始个体 不包含所有的正确字符，你永远也得不到正确结果。 如果突变率高于某个值（假如是10%），进化过程将会 出现很高的随机性（在每个子代个体中，1/10的字符是随机确定的），因此模拟过程 就变成了纯粹的随机枚举。从理论上讲，它最终会得到正确的答案，但你可能要等很 久，甚至等待时间远远超出合理值。
*适应度函数的意义 如果无法定义问题的目标或无法用数 值衡量目标的完成度，你就不能正确地实现遗传算法。
一组火箭从屏幕底部开始发射，目标是击中屏幕中的靶子（绕过直线前进路线中的障 碍物）。
class Rocket { PVector location; //火箭有3个向量：位置、速度和加速度 PVector velocity; PVector acceleration; void applyForce(PVector f) { //将力转化为加速度（牛顿第二定律） acceleration.add(f); } void update() { //简单的物理模型（欧拉积分） velocity.add(acceleration); //速度根据加速度变化 location.add(veloctiry); //位置根据速度变化 acceleration.mult(0); } }每个火箭都有一个推进器。推进器会在每一帧产生方向和大小皆可变的推力。
class DNA { PVector[] genes; //基因序列是一组向量 float maxforce = 0.1; //推进器的推力大小 DNA() { genes = new PVector[lifetime]; //火箭生命期的每一帧分别对应一个向量对象 for (int i = 0; i < genes.length; i++) { genes[i] = PVector.random2D(); genes[i].mult(random(0, maxforce)); //用随机的方式改变向量长度，但不要超过最大推 } } } class Rocket { DNA dna; //火箭的DNA float fitness; //火箭的适应度 PVector location; PVector velocity; PVector acceleration; } int geneCounter = 0; void run() { applyForce(dna.genes[geneCounter]); //将基因数组中的力向量作用在火箭上 geneCounter++; //转到基因数组的下一个力向量 update(); //更新火箭的物理属性 }1.创建火箭种群 2.让所有火箭运行N帧 3.进化出下一代 a.选择 b.繁殖 4.回到步骤2
int lifetime; //每一代生命期的帧数 int lifeCounter; //我们位于哪一帧 Population population; //种群对象 void setup() { size(640, 480); lifetime = 500; lifeCounter = 0; float mutationRate = 0.01; population = new Population(mutationRate, 50); //第一步：创建种群。我们在这里指定突变率和} void draw() { background(255); if (lifeCounter < lifetime) { //修改后的遗传算法 population.live(); //第二步：只要lifeCounter小于lifetime，火箭就一直存活 lifeCounter++; } else { lifeCounter = 0; //一旦生命期结束，就重置`lifeCounter`，开始下一轮进化（步骤3和4，选population.fitness(); population.selection(); population.reproduction(); } } }*改进：障碍物 如果火箭撞到障碍物，它应该停止运动，不再更新位置，火箭的适应度应该大大降低。
class Obstacle { PVector location; //障碍物有位置（矩形的左上角）、宽度和高度 float w,h; boolean contains(PVector v) { if (v.x > location.x && v.x < location.x + w && v.y > location.y && v.y < location.y + h){ return true; } else { return false; } } void obstacles() { //这是Rocket类的成员函数，检查火箭是否撞到障碍物 for (Obstacle obs : obstacles) { if (obs.contains(location)) { stopped = true; } } } void run() { if (!stopped) { //如果火箭不会撞到障碍物，就执行run()函数的操作 applyForce(dna.genes[geneCounter]); geneCounter = (geneCounter + 1) % dna.genes.length; update(); obstacles(); } } void fitness() { float d = dist(location.x, location.y, target.location.x, target.location.y); fitness = pow(1/d, 2); if (stopped) fitness *= 0.1; } }*改进2：更快地击中靶子 适应度函数的唯一变量是火箭与靶子之间的距离。实际上，某些火箭在运动过程中曾经非 常接近靶子，但由于其运动速度过快，最终超越了靶子。因此，火箭的运动应该更加 缓慢而平稳。 1.选取一个最大接近距离，而不是0 2.火箭到达靶子所花费的时间应该成为奖赏因素。
void checkTarget() { float d = dist(location.x, location.y, target.location.x, target.location.y); if (d < recordDist) //对每一帧，我们都要检查这个距离，查看它是否比“记录” recordDist = d; } if (target.contains(location)) { //如果对象到达目标位置，将布尔标志设为true hitTarget = true; } else if (!hitTarget) { finishTime++; //如果火箭没有达到目标位置，则继续递增计数器 } void fitness() { fitness = (1/(finishTime*recordDist)); //完成时间和最短距离 fitness = pow(fitness, 2); //创建指数关系 if (stopped) fitness = 0.1; //如果火箭撞到障碍物，则适应度大大降低 if (hitTarget) fitness = 2; //如果火箭能到达目标位置，则提高适应度 }图像的适应度由用户的欣赏时间确定。这就是所谓的交互式选择：适应度由用户确定的遗传算法。
class DNA { float[] genes; int len = 20; //为了画出这张脸，我们需要20个基因 DNA() { genes = new float[len]; for (int i = 0; i < genes.length; i++) { genes[i] = random(0,1); //每个基因都是介于0~1的随机浮点数 } } } void display() { float r = map(dna.genes[0],0,1,0,70); //用map()函数将基因转化为绘制参数 color c = color(dna.genes[1],dna.genes[2],dna.genes[3]); float eye_y = map(dna.genes[4],0,1,0,5); float eye_x = map(dna.genes[5],0,1,0,10); float eye_size = map(dna.genes[5],0,1,0,10); color eyecolor = color(dna.genes[4],dna.genes[5],dna.genes[6]); color mouthColor = color(dna.genes[7],dna.genes[8],dna.genes[9]); float mouth_y = map(dna.genes[5],0,1,0,25); float mouth_x = map(dna.genes[5],0,1,-25,25); float mouthw = map(dna.genes[5],0,1,0,50); float mouthh = map(dna.genes[5],0,1,0,10); }适应度由鼠标操作决定，下一代的创建由按钮触发。 1.为了实现简单的演示功能，我们打算用以下方式获取适应度分值：当鼠标在某个表情上停留越久，它的适应度就越高。 2.当用户点击“evolve next generation”按钮时，我们就 为他创建下一代表情。
Population population; Button button; void setup() { size(780,200); float mutationRate = 0.05; population = new Population(mutationRate,10); button = new Button(15,150,160,20, "evolve new generation"); } void draw() { population.display(); population.rollover(mouseX,mouseY); //将鼠标位置传入population对象的rollover() } void mousePressed() { if (button.clicked(mouseX,mouseY)) { //一旦按钮被按下，就通过选择和繁殖创建下一代 population.selection(); population.reproduction(); } }