2d小车的演变

       高清演示：http://www.acfun.cn/v/ac4658690
遗传算法
  进化过程中优胜劣汰，但不要过早失去多样性(算法早熟，造成局部最优)。宛如各...

算法重点
  设计汽车：车体不变，改变的是各个轮胎的位置，大小，转速。

每辆车代表一条染色体(数据)，其中一个格子表示一个基因(变量)，每个变量表示为具有一定变化范围的实数(或整数)。

  选择：

赌徒轮盘：每一个色块代表一辆车，色块的大小代表这一代中这辆车行驶的距离，所以行驶越远被选中的概率也就越高。

  交叉(由交叉率控制)：

单点交叉：随机确定染色体中的任一点，交换点左边或者右边所有内容（如上面的颜色所示）

  突变(由突变率控制)：每一代染色体都经历突变。这意味着汽车的每个方面(染色体中的变量)可能变的更好或更差。

AB表示变异前，ABm表示AB变异后。一个变量发生了变异(蓝色)

伪代码
参数

交叉率 pc 
变异率 pm 
车子集合 car[]
新一代车子集合 newCar[]
车子数量 numberOfCar
每辆车行驶距离 distance
组成染色体的基因数量 numberOfGene

初始化

1. class Chromosome//创建染色体类定义
2.     gene[]
3.     disdance

1. Chromosome.car
2. Chromosome.newcar

1. for i = 0 to numberOfCar- 1
2.     car[i] = 随机生成的车子

开始

1. while true
2.     GENETIC-ALGORITHM()

GENETIC-ALGORITHM()
1. if i++ < numberOfCar
2.     car[i].distance= 游戏中行驶距离//记录
3. if i == numberOfCar//遗传操作 
4.     SELECTION()//选择
5.     CROSSOVER()//交叉
6.     MUTATION()//变异
7.     i = 0//开始新的轮回

SELECTION()
//单个个体被选择的概率
1. totalDistance= 0;
2. for i = 0 to numberOfCar- 1
3.     totalDistance += pop[i].fitness
4. for i = 0 to numberOfCar- 1
5.     car[i].disdance = car[i].disdance/ totalDistance
//创建赌徒转盘
6. x = 0
7. y = x + 1
8. while y ≠ numberOfCar
9.     car[y].disdance  = car[x].disdance + car[y].disdance 
10.    x++
11.    y++
//旋转转盘
12. ms[numberOfCar]
13. for i = 0 to numberOfCar- 1
14.    ms[i] = 0%~100%之间随机数
//优胜劣汰,数值越高选中几率越大
15. curin = 0
16. newin = 0
17. while newin < numberOfCar
18.    if ms[newin] < car[curin].disdance 
19.        for i = 0 to numberOfGene - 1
20.            newcar[newin].gene[i] = car[curin].gene[i]
21.        newin++
22.        curin = 0//转盘指针回到原点
23.    else
24.        curin++

CROSSOVER()
1. for i = 0 to numberOfCar- 1
2.     r = 0%~100%之间随机数
3.     cPoint = 0~(numberOfGene - 1)之间的随机数
4.     if r <= pc //成功交配
5.         for j = 0 to cPoint
6.             car[i].gene[j] = newcar[i].gene[j]
7.         for j = cPoint + 1 to numberOfGene - 1
8.             if i + 1 == numberOfCar
9.                 i = 0
10.            car[i].gene[j] = newcar[i + 1].gene[j];
11.    else//单身狗
12.        for j = 0 to numberOfGene - 1
13.            car[i].gene[j] = newcar[i].gene[j];

MUTATION()
1. for i = 0 to numberOfCar- 1
2.     r = 0%~100%之间随机数
3.     mPoint = 0~(numberOfGene - 1)之间的随机数
4.     if r <= pm
5.         switch mPoint
6.             case 0:
7.             to//中奖的基因值，重新随机一个数值
8.             case numberOfGene - 1: