遗传算法

简介

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。

基本原理

遗传算法（GA）是一种元启发式自然选择的过程，属于进化算法（EA）大类。遗传算法通常是利用生物启发算子，如变异、交叉和选择来生成高质量的优化和搜索问题的解决方案。

借鉴生物进化理论，遗传算法将问题模拟成一个生物进化过程，通过遗传、交叉、突变、自然选择等操作产生下一代的解，并逐步淘汰适应度函数值低的解，增加适应度函数高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。

遗传算法的实现与目的

实现 ：在计算机上模拟生物的进化过程和基因的操作（选择、交叉、变异）。

目的 ：抽象和严谨地解释自然界的适应过程和将自然生物系统的重要机理运用到人工系统的设计中。

算法流程

（1）流程图

（2）自然语言解释
常用的遗传编码算法有二进制码、实数编码。
① 二进制编码（Binary encoding） 二进制编码是将原问题的结构变换为染色体的位串结构。在 二进制编码中，首先要确定二进制字符串的长度l，该长度与 变量的定义域和所求问题的计算精度有关。
例 假设变量x的定义域为[4，10]，要求的计算精度为10-5， 则需要将[4，10]至少分为600000个等长小区间，每个小区间 用一个二进制串表示。于是，串长至少等于20，原因是： 524288=219<600000<220=1048576 这样，对应于区间[4，10]内满足精度要求的每个值x，都可用 一个20位编码的二进制串<b19,b18,…,b0>来表示。
② 实数编码（Real encoding） 实数编码是将每个个体的染色体都用某一范围的一个实 数（浮点数）来表示，其编码长度等于该问题变量的个数。 这种编码方法是将问题的解空间映射到实数空间上，然后在实数空间上进行遗传操作。由于实数编码使用的是变量的真实值，因此这种编码方法也叫做真值编码方法。 实数编码适应于那种多维、高精度要求的连续函数优化问题。
3）本次实验使用粒子群算法
与大多数基于梯度的应用优化算法不同，群智能 依靠的是概率搜索算法。优点主要表现在以下几 个方面：
1 无集中控制约束，不会因个别个体的故障影响整个问题 的求解，确保了系统具备更强的鲁棒性（抗干扰能力）
2 以非直接的信息交流方式确保了系统的扩展性
3 并行分布式算法模型，可充分利用多处理器
4 对问题定义的连续性无特殊要求
5 算法实现简单

Ga函数

群体：遗传算法中初始给定的解的集合（群体规模N）
种群：在本算法中认为每一代解的集合都是一个种群（N）
个体：种群中的每一个解都是一个个体
适应能力：个体的适应值
染色体：个体的二进制编码
基因：个体二进制编码的每一个位都是一个基因
基因重组：二进制编码（在pc概率下的）基因交换
基因突变：二进制编码（在pmx编码长度x种群大小概率下）一个基因点的改变
pc：设置的交叉率
pm：设置的基因突变率

代码实现

matlab实例
2维空间搜索，群体规模为80：

2维空间搜索，群体规模为100：

2维空间搜索，群体规模为200：

3维空间搜索，群体规模为80：

5维空间搜索，群体规模为80：

5维空间搜索，群体规模为100：

5维空间搜索，群体规模为200：

8维空间搜索，群体规模为80：

总结

（1）遗传算法是一个反复迭代的过程，每次迭代期间，要执行适应度计算、复制、交换、突变等操作，直至满足终止条件。
（2）个体的适应度值越大，被选中的可能性也越大。群体规模数越大，可行解的集合也就越大。