【进化算法】遗传与基因

引言

遗传算法是基于达尔文进化论和孟德尔遗传学说的模拟生物进化过程的计算模型。遗传算法通过对染色体的选择、交叉和变异 3 种基本操作,仿效生物遗传过程遗传物质基因的重组、突变和变异3 种方式。控制生物遗传的物质单位称为基因，因此，遗传算法是在基因的水平上模拟生物的进化行为。

遗传算法能够应用于各种优化问题，如工程优化、调度问题、机器学习中的超参数优化、函数优化、组合优化、生产调度问题、自动控制、机器人学图像处理、多机器人路径规划等领域。

遗传算法的优点在于可以在大规模搜索空间中寻找最优解，但也存在着对问题的参数设置敏感、收敛速度慢等缺点。

不同类型的遗传算法在个体表示、选择策略、交叉和突变操作等方面可能略有不同，但都遵循了模拟生物进化的基本原则。

---

遗传算法

遗传算法 (Genetic Algorithm,GA) 是 1975 年由霍兰 (J.H.Holland) 教授提出。它是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，其目的：一是抽取和解释自然系统的自适应过程；二是设计具有自然系统机理的人工系统。

遗传算法的基本思想是借鉴生物进化的规律，通过繁殖-竞争-再繁殖-再竞争实现优胜劣汰，使问题一步步逼近最优解；或者说进化算法是仿照生物进化过程，按照优胜劣汰的自然选择优化的规律和方法，来解决科学研究、工程技术及管理等领域用传统的优化方法难以解决的优化问题。

相关概念

概念	含义
染色体	遗传物质的主要载体,是多个遗传因子的集合
基因	遗传操作的最小单元,基因以一定排列方式构成染色体
个体	染色体带有特征的实体
种群	多个个体组成群体,进化之初的原始群体称为初始种群
适应度	用来估计个体好坏程度的解的目标函数值
编码	用二进制码字符串表达所研究问题的过(除二进制编码外,还有浮点数编码等)
解码	将二进制码字符串还原成实际问题解的过程
选择	以一定的概率从种群中选择若干对个体的操作
交叉	把两个染色体换组的操作,又称重组
变异	让遗传因子以一定的概率变化的操作

遗传的三个操作

• 选择：从种群中按一定标准选定适合做亲本的个体,通过交配后复制出子代。
  • 适应度比例法：利用比例于各个个体适应度的概率决定于其子孙遗留的可能性
  • 期望值法：计算各个个体遗留后代的期望值,然后减去 0.5
  • 排位次法：按个体适应度排序，对各位次预先已被确定的概率决定遗留为后代
  • 精华保存法：无条件保留适应度大的个体,不受交叉和变异的影响
  • 轮盘赌法：类似于博采中的轮盘赌，按个体的适应度比例转化为选中的概率
• 交叉：把两个染色体换组 (重组) 的操作
  • 单点交叉：在两个父代个体染色体的随机位置选择一个交叉点，然后交换两个个体在交叉点后的基因片段，从而产生两个新个体
  • 多点交叉：选择多个交叉点，会有多个区域的基因片段进行交叉
  • 部分映射交叉：PMX交叉操作定义了一个映射规则，通过选择两个交叉点来交换父代个体的基因片段。然后根据映射规则将交叉点之间的基因进行映射，并确保产生的子代不含重复的基因
  • 顺序交叉：OX交叉操作首先随机选择两个交叉点，然后保留第一个交叉点和其之间的基因片段，并从第二个交叉点开始，按照另一个父代个体中未包含的顺序填充缺失的基因
  • 循环交叉：CX交叉操作从两个父代个体中随机选择一个基因开始，并按照一个环路来交换两个个体的基因
  • 基于位置的交叉
  • 基于顺序的交叉
  • 启发式交叉：基于问题本身特点的交叉策略，使用了问题特定的启发式信息来指导交叉操作
• 变异： 基因 0、1 以一定的概率施行 0?1、1?0 的操作。

PS：变异有局部随机搜索的功能相对变异而言，交叉具有全局随机搜索的功能。交叉和变异实质上都是得到新个体的过程。

算法流程图