遗传算法-2d小车的演变
2018-10-20 本文已影响0人
我_7
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:
