本次回答将引用腾讯高级工程师tracyyma在腾讯内部发表的一篇原创文章。
内容索引
· Chapter 1 算法简介
· Chapter 2 算法应用
· Chapter 3 算法原理
· Chapter 4 实例说明
Chapter 1 遗传算法的简介
说到遗传算法,貌似很复杂呢,是不是跟生物遗传有关呢?没错,遗传算法就是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法,它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应的控制搜索过程以求得最优解。
遗传算法操作使用适者生存的原则,在潜在的解决方案种群中逐次产生一个近似最优解的方案,在遗传算法的每一代中,根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择,产生一个新的近似解。这个过程导致种群中个体的进化,得到的新个体比原来个体更能适应环境,就像自然界中的改造一样。
Chapter 2 遗传算法的应用场景
需求拉到消费嘛,笔者以前接触过这个算法早在学校还给老师了,之所以想在此记下,主要是同事提出了一个问题:能否根据一堆变量的数据来预测一个变量,简单地说,"能给出一个公式吗,让我用用",想想貌似这比较接近一个优化问题,可以用遗传编程来解决。没错,是遗传编程,它是遗传算法的一个沿伸,下章会具体介绍这个算法。本章先打基础。当然另一个原因还是由于笔者本人还是有点遗传学的工作背景的。
提出上一堆废话,无非就想引入一个问题:“优化问题”;遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法,是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等。
比如:旅游航班优化问题、物流系统设计、生产调度、时间表安排等问题上。遗传算法的主要有以下八方面的应用:
(1)组合优化 (2)函数优化 (3)自动控制 (4)生产调度
(5)图像处理 (6)机器学习 (7)人工生命 (8)数据挖掘
Chapter 3 遗传算法的原理
说了这么多,重点就只有一个:达尔文、孟德尔,开个小玩笑,先来复习下我们高中课本,待会说应用。达尔文的进化论强调的是自然选择:适者生存,优胜劣汰;孟德尔种了八年豌豆,人家不也发现了遗传定理了吗?(基因的分离规律和基因的自由组合规律);遗传算法就是模仿自然界的生物进化机制而来的,基础的遗传算法主要有三个算子:选择算子(自然选择,适者生存)、交叉算子(自由组合规律)、突变算子(适者生存)
先看一个大概的算法实现流程:
图1: 遗传算法原理
当然在算法中选择、交叉、变异算子可选择进行,也可交叉进行,也可顺序进行(蓝虚线)并无特别的要求。
所以遗传算法的组成可分为:
1) 编码
遗传算法(GA)通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。
正如研究生物遗传是从染色体着手,而染色体则是由基因排成的串,基本遗传算法(SGA)使用二进制串进行编码。
2) 适应度函数
评价一个个体(解)的好坏程度,适应度函数是遗传算法进化过程的驱动力,也是
进行自然选择的唯一标准,它的设计应结合求解问题本身的要求而定。
3) 遗传算子(选择、交叉、变异)
选择算子:适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体,被遗传到下一代群体中的概率小。选择操作的任务就是从父代群体中选取一些个体,遗传到下一代群体。
基本的遗传算法采用轮赌法进行,举个例子通谷易懂,有助于理解选择算子。其基本的思想是各个个体被选中的概率与其适应度函数值大小成正比。
轮盘赌选择法可用如下过程模拟来实现:
交叉算子
交叉运算,是指对两个相互配对的染色体依据交叉概率PC按某种方式相互交换其部分基因,从而形成两个新的个体。基本的遗传算法采用单点交叉。如下所示
是不是很像染色体重排(chromosomal rearrangement)呢!
变异算子
变异运算,是指改变个体编码串中的某些基因值,从而形成新的个体。决定遗传算法的局部搜索能力,保持种群多样性。交叉运算和变异运算的相互配合,共同完成对搜索空间的全局搜索和局部搜索。基本遗传算法(SGA)中变异算子采用基本位变异算子。
基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。
对于二进制编码符号串所表示的个体,若需要进行变异操作的某一基因座上的原有基因值为0,则将其变为1;反之,若原有基因值为1,则将其变为0 。
4) 运行参数
① M:种群规模
② T:遗传运算的终止进化代数
③ PC:交叉概率
④ PM:变异概率
Chapter 4 实例原理
Ok,现在可以完整用一例实例来具体阐述下遗传算法。
既然上述有轮盘赌的方法,那么还是应用上述是简单一个实例:求解目标函数
。例子很简单但最实效。
初始化种群为 [0, 1, 1, 1, 0, 1, 0, 0, 1, 1]
1 genetation:
2 genetation:
3 genetation:
4 genetation:
……
直到其中一代出现了近似最大值1.57
ok, 基本完成。
搜索关注公众号「云加社区」,第一时间获取技术干货,关注后回复1024 送你一份技术课程大礼包!