二、Genetic Algorithm
Algorithm
Genetic algorithm is a population-based probabilistic search and
optimization techniques, which works based on the mechanisms of
natural genetics and natural selection
1
2
Encoding Encoding precision
10
Binary encoding
3
Real value encoding
4
Order Encoding for TSP
9
5
6
7
8
Fitness
适应度函数是一种特殊类型的目标函数，用于量化解的最优性。
比如 求最小值 函数值越小 适应度就越高
Selection ( Roulette-Wheel selection)
选择体现了适者生存的原则，这为遗传算法提供了一种驱动力。It is based on
the fitness of the individuals.
Roulette-Wheel selection
11
轮盘赌基本思想：适应度越高的解，按道理应该高概率的进行复制，且复制的份
数应该越多
轮盘赌算法实现是累计概率，生成0-1之间的随机数，如果小于某个累计概率，则
选择该概率所对应的个体
Crossover
交叉是在随机选择的两条父染色体之间交换信息，并产生两个新的后代。
Mutation
实现变异算子的一种常见方法是为序列中的每一位生成一个称为变异概率的随机
变量。
这种突变概率告诉我们是否会对特定位进行突变（即修改01）。
Reinsertion
如果产生的后代少于原始种群的数量，则为了保持原始种群的数量，必须将后代
重新插入老年种群
Produce less offspring than parents and replace the worst parents (elitist
reinsertion).把父代中差的八个全部替换成子代
12
备注：
1. 遗传算法是一种基于种群的概率搜索和优化技术，其工作原理基于自然遗传和自然选择机制
2. converge 汇聚于一点 即找到最优解
3. 二进制编码 用01表示基因
4. 实值编码 用值表示基因
5. 代沟 子代数目为父代的百分之80
6. 交叉概率 只有70的概率进行交叉重组
7. 变异概率 每位只有百分之一的概率变异
8. 终止进化代数
9. 种群规模
10. 编码 编码精度
11. 轮盘赌选择法
12. 生育的子女比父母少，并替换最差的父母（精英重新插入）。
- 1
- 2
- 3
- 4
- 5
前往页