遗传算法可视化

遗传算法（Genetic Algorithm）作为一种优化算法，其本质是经过对多个个别的基因穿插、变异、挑选等操作来实现对问题求解的优化进程。为了便利直观地调查算法的演化进程，咱们能够经过可视化的方法展现遗传算法中每个过程的履行情况。详细实现进程如下：

1. 确认遗传算法所要处理的问题，并挑选相应的编码方法和习惯度函数进行建模。一般而言，遗传算法所处理的问题需求转化为一个数学模型，例如最大化某一方针函数或最小化某一成本项。
2. 对于给定的问题，确认需求优化的参数以及它们的取值规模。这些参数被称作基因（Gene），具有习惯度（Fitness）值。
3. 初始化种群（Population），即初始时包含若干个基因的集合。初始种群的巨细应该足够大，以确保能够找到比较优的处理方案。
4. 经过穿插（Crossover）和变异（Mutation）操作，生成新的个别。穿插操作是指将两个个别互相交换一部分基因序列，从而得到一对新的个别；变异操作则是指随机改变某些基因的取值，从而使得新的个别具有一定的随机性。
5. 核算新生成的个别的习惯度，并按照一定的规则进行挑选（Selection）。在挑选进程中，能够选用轮盘赌算法、锦标赛算法等多种方法，从而确保优秀的基因能够被更好地保留下来，并不断进化。
6. 重复履行第4-5步，直到到达指定的停止条件。常见的停止条件包含到达最大迭代次数、到达方针习惯度值等。
7. 制作可视化图表，展现遗传算法的履行进程和成果。常见的图表类型包含折线图、散点图、柱状图等，经过这些图表能够直观地调查算法的演化进程和最终的优化成果。

首要，在网页中引入 p5.js 库，创立画布，并定义一些变量：

let population; // 种群方针
let lifespan = 300; // 每个个别的寿数
let lifeP; // 显示寿数的HTML元素
let count = 0; // 计数器，每到lifespan就增加1
let target; // 方针字符串
let maxFitness = 0; // 习惯度最高值，即与方针字符串彻底匹配时的习惯度
let bestPhrase; // 最佳个别（与方针字符串最接近的个别）
let mutationRate = 0.01; // 基因突变率
function setup() {
  createCanvas(640, 360);
  population = new Population(mutationRate, lifespan);
  lifeP = createP();
  target = "To be or not to be.";
}
function draw() {
  background(220);
  population.run();
  lifeP.html("Generation #" + population.getGenerations() + "<br>" + "Best phrase: " + bestPhrase);
  if (population.isFinished()) {
    noLoop();
  }
  count++;
  if (count == lifespan) {
    population.evaluate(target);
    population.selection();
    count = 0;
  }
}

紧接着，创立一个结构函数 Population，用来初始化种群，并实现遗传算法的各个过程：

function Population(mutationRate, lifespan) {
  this.mutationRate = mutationRate;
  this.lifespan = lifespan;
  this.population = [];
  this.matingPool = [];
  this.generations = 0;
  // 初始化种群，随机生成每个个别的基因
  for (let i = 0; i < 100; i++) {
    this.population[i] = new DNA(this.lifespan);
  }
  // 核算每个个别的习惯度，并挑选出习惯度最高的个别
  this.evaluate = function(target) {
    let maxFitness = 0;
    for (let i = 0; i < this.population.length; i++) {
      this.population[i].calcFitness(target);
      if (this.population[i].fitness > maxFitness) {
        maxFitness = this.population[i].fitness;
        bestPhrase = this.population[i].getPhrase();
      }
    }
    // 将习惯度高的个别添加到交配池中
    this.matingPool = [];
    for (let i = 0; i < this.population.length; i++) {
      let fitness = map(this.population[i].fitness, 0, maxFitness, 0, 1);
      let n = floor(fitness * 100);
      for (let j = 0; j < n; j++) {
        this.matingPool.push(this.population[i]);
      }
    }
    this.generations++;
  }
  // 从交配池中挑选两个个别进行交配，并产生新的个别
  this.selection = function() {
    let newPopulation = [];
    for (let i = 0; i < this.population.length; i++) {
      let a = random(this.matingPool).dna;
      let b = random(this.matingPool).dna;
      let child = a.crossover(b);
      child.mutate(this.mutationRate);
      newPopulation[i] = new DNA(this.lifespan, child);
    }
    this.population = newPopulation;
  }
  this.getGenerations = function() {
    return this.generations;
  }
  this.isFinished = function() {
    return bestPhrase == target;
  }
  // 在画布上显示每个个别的基因序列
  this.run = function() {
    for (let i = 0; i < this.population.length; i++) {
      this.population[i].show(map(i, 0, this.population.length, 0, width), 50);
    }
  }
}

最终，创立一个结构函数 DNA，用来生成、交配和变异个别的基因：

function DNA(num) {
  this.genes = [];
  for (let i = 0; i < num; i++) {
    this.genes[i] = newChar();
  }
  this.fitness = 0;
  // 核算个别的习惯度值
  this.calcFitness = function(target) {
    let score = 0;
    for (let i = 0; i < this.genes.length; i++) {
      if (this.genes[i] == target.charAt(i)) {
        score++;
      }
    }
    this.fitness = score / target.length;
  }
  // 在画布上显示个别的基因序列
  this.show = function(x, y) {
    let phrase = "";
    for (let i = 0; i < this.genes.length; i++) {
      phrase += this.genes[i];
    }
    text(phrase, x, y);
  }
  // 经过穿插操作生成新的基因序列
  this.crossover = function(partner) {
    let child = new Array(this.genes.length);
    let midpoint = floor(random(this.genes.length));
    for (let i = 0; i < this.genes.length; i++) {
      if (i > midpoint) {
        child[i] = this.genes[i];
      } else {
        child[i] = partner.genes[i];
      }
    }
    return child;
  }
  // 随机突变个别的基因
  this.mutate = function(mutationRate) {
    for (let i = 0; i < this.genes.length; i++) {
      if (random(1) < mutationRate) {
        this.genes[i] = newChar();
      }
    }
  }
  // 将基因序列转换为字符串
  this.getPhrase = function() {
    let phrase = "";
    for (let i = 0; i < this.genes.length; i++) {
      phrase += this.genes[i];
    }
    return phrase;
  }
}
// 随机生成一个字符（包含空格和标点符号）
function newChar() {
  let c = floor(random(63, 122));
  if (c == 63) {
    c = 32;
  } else if (c == 64) {
    c = 46;
  }
  return String.fromCharCode(c);
}

这样，咱们就完成了一个简单的遗传算法可视化程序。当咱们在浏览器中翻开该网页时，能够看到一系列随机生成的字符串，它们会不断地进化、交配和变异，直到其间一个个别与方针字符串彻底匹配。在不断的进化进程中，咱们能够调查到种群的习惯度不断提高，最终到达与方针字符串彻底匹配的状况。