1.遗传算法与生物进化学说
1885年年，达尔文用自然选择来解释物种的起源和生物的进化。
达尔文的自然选择学说包括三个方面：
- 遗传
- 变异
- 生存斗争和适者生存
上世纪20年代，一些学者用统计生物学和种群遗传学重新解释达尔文自然选择理论，形成现代综合进化论。
种群遗传学认为：
- 在一定地域中一个物种的全体成员构成一个种群；
- 生物的进化是种群的进化，每一代个体基因型的改变会影响种群基因库的组成，而种群基因库组成的变化就是这一种群的进化。
遗传算法中与生物学相关的概念和术语与优化问题中的描述的关系：
- 个体：解
- 种群：解集/解空间
- 适应度：评价/目标/寻优函数
- 选择、交叉、变异：产生新解的方法
2.遗传算法的计算机实现
上世纪60年代中期，Holland提出位串编码技术。
这种技术适用于变异和交叉操作，而且强调将交叉作为主要的遗传操作。
Holland将该算法用于自然和人工系统的自适应行为研究中，在1975出版了开创性著作“Adaptation in Natural and Artifical System”。
之后，他将算法应用到优化以及学习中，并将其命名为遗传算法（简称GA）。
遗传算法基本思路：
-
计算开始时，随机初始化一定数目的个体，并计算每个个体的适应度值，产生第一代（初始种群）。
-
如果不满足优化准则，开始新一代的计算：
按照适应度值选择个体，产生下一代；
父代按一定概率进行交叉操作，产生子代；
所有的子代按一定概率变异，形成新的一代。
计算新子代的适应度值。 -
这一过程循环执行，直到满足优化准则为止。
流程图：
遗传算法流程图
3.遗传算法解决TSP问题思路
3.1 编码
最常用策略：路径编码
直接采用城市在路径中的位置来构造用于优化的状态。
例：九城市TSP问题，路径：5-4-1-7-9-8-6-2-3
路径编码：(5 4 1 7 9 8 6 2 3)
3.2 交叉
交叉操作
3.3 变异
多种可行的变异操作
4.遗传算法解决TSP问题编程实现
输入：
10城市坐标为：
(41, 94)；(37, 84)；(54, 67)；(25, 62)；(7, 64)； (2, 99)；(68, 58)；(71, 44)；(54, 62)； (83, 69)
运行结果：
算法运行结果
python源码：https://github.com/wangjiosw/GA-TSP
5.遗传算法的特点
GA是一种通用的优化算法，它的优点有：
- 编码技术和遗传操作比较简单；
- 优化不受限制性条件的约束；
- 隐含并行性和全局解空间搜索。
随着计算机技术的发展，GA愈来愈得到人们的重视，并在机器学习、模式识别、图像处理、神经网络、优化控制、组合优化、VLSI设计、遗传学等领域得到了成功应用。
网友评论