一文读懂遗传算法工作原理（附Python实现）

最近，Analyticsvidhya 网站发布了一篇名为《遗传算法入门及其在数据科学中的应用》的文章，作者 Shubham Jain 以亲身经历的方式，借助浅显易懂的表述，对遗传算法进行了系统而精炼的阐释，同时展示了它在诸多领域的实际运用，尤其着重阐述了遗传算法在数据科学领域的具体用途。机器之心对该文进行了编译，原文链接请见文末。

简介

日前，我开始处理一个具体事务，即大型商场的销售情况。运用若干基础方法进行了一些数据准备工作之后，我在相关榜单中位列第 219 位

成绩虽然令人满意，但我仍渴望进一步提升表现。为此，我着手探索能够提升分数的改进措施。幸运的是，我确实发现了一种方法，这种方法名为遗传算法。当将遗传算法应用于超市销售课题后，我的分数迅速攀升，最终在排行榜上位列顶尖。

确实，仅通过遗传算法，我就能从 219 人中直接跃升至 15 人行列，这难道不令人惊叹吗？只要仔细阅读完这篇文章，你也能熟练掌握遗传算法的运用，并且会意识到，当将这种方法运用到你正在面对的难题上时，其效果将会得到显著增强。

目录

1、遗传算法理论的由来

2、生物学的启发

3、遗传算法定义

4、遗传算法具体步骤

初始化适应度函数选择交叉变异

5、遗传算法的应用

特征选取使用 TPOT 库实现

6、实际应用

7、结语

1、遗传算法理论的由来

我们先从查尔斯·达尔文的一句名言开始：

存活下来的通常不是势力最盛的物种，也不是头脑最灵光的物种，而是对环境最为融洽的物种。

你或许在疑惑：这个论述与遗传算法有何关联？事实上，遗传算法的全部思想正是源于这个论断。

让我们用一个基本例子来解释 ：

我们设想一个场景，此刻你是一位君王，为了使你的国度远离祸患，你制定了一系列律法，

你挑选出所有品行端正的人，让他们通过繁衍来增加国民人数。这个做法持续了数代之后，你会发觉自己已经聚集了一大批品德优秀的人。这个事例虽然有些夸张，但我用它的目的是为了让你掌握这个要领。也就是说，我们通过调整初始条件（比如：人口素质），就能得到更理想的成果（比如：更出色的国家）。此刻，我料想您已对这理念有了基本认识，觉得遗传算法的内涵应当与生物学有所牵连。接下来，咱们简要探讨几个要点，以便将其串联起来领会。

2、生物学的启发

你一定还记得那句说法：生命体的基本构造是细胞。从这里就能明白，任何生物的每一个细胞，都包含着一套完全一样的遗传物质。这种遗传物质，其实是由脱氧核糖核酸构成的链状结构。

这些染色体通常能够用包含零与一的序列来描述出来。

一条染色体包含基因，基因是 DNA 的基础构造，DNA 上的每个基因都决定了一个特定特征，例如头发或眼睛的色泽，请你在阅读下文前，回顾一下这些生物学知识，这部分内容到此结束，接下来我们探讨遗传算法究竟是什么。

3、遗传算法定义

首先我们回到前面讨论的那个例子，并总结一下我们做过的事情。

首先，我们设定好了国民的初始人群大小。

然后，我们定义了一个函数，用它来区分好人和坏人。

再次，我们选择出好人，并让他们繁殖自己的后代。

最终，这些子孙替代了先前民众中的某些恶人，并且持续不断地进行此类更替。

遗传算法运作方式确实如此，它主要是在一定水平上模仿了生物进化的机制。

所以，要明确遗传算法的规范表述，可以视其为一种改进途径，这种途径旨在搜寻特定数据，借助这些数据便能获取最优的成效或答案。遗传算法的运作原理借鉴了生物学的原理，详细步骤参见图示。

那么现在我们来逐步理解一下整个流程。

4、遗传算法具体步骤

为了使说明更加清晰，我们先来认识一下广为人知的组合优化课题「背包问题」。倘若你尚有疑惑，此处有一个我个人的阐释方式。

比如，你打算外出旅行一个月，但只能携带一个承重30公斤的背包。现在你有若干必备物品，每件物品都有相应的「生存价值」，详细数据见下表。因此，你的任务是在背包重量限制内，尽可能提高整体的「生存价值」。

4.1 初始化

此处我们借助遗传算法来处理背包难题，首要步骤是明确我们的种群构成，种群由众多个体组成，每个个体都携带一套独特的基因序列，用以表征其解。

染色体能够转化为由二进制数字构成的序列，其中1表示该位置上的基因没有缺失，而0则表明基因已经消失。作者在此运用染色体与基因的概念来处理背包问题，特定位置上的基因对应背包问题表格中的物品，例如首个位置代表睡袋，那么该染色体的首个基因就体现这一物品。

现在，我们将图中的 4 条染色体看作我们的总体初始值。

4.2 适应度函数

现在，我们开始评估头两个染色体的适宜度值，针对 A1 染色体

而言，有：

类似地，对于 A2 染色体

来说，有：

这个问题上，我们看法是，如果染色体带有更多生存值，那么说明它的生存能力更好。

因此，由图可知，染色体 1 适应性强于染色体 2。

4.3 选择

当前，我们能够从整体里挑选出合适的染色体，让它们彼此『结合』，繁衍出属于它们的后代。这就是实施选择过程的基本思路，然而，这种方式可能会导致染色体在几代之后彼此相似度增加，丧失了差异性。所以，我们通常采用「轮盘赌选择法」（Roulette Wheel Selection method）。

设想一个圆盘，现在将其划分成若干区域，这些区域的数量对应着全部染色体的数目。每条染色体在圆盘上占据的面积大小，会依据其适应度值进行相应比例的分配。

基于上图中的值，我们建立如下「轮盘」。

此刻，这个轮盘启程转动开元ky888棋牌官方版，我们将依据图中那个不变标记的指引，选定轮盘上对应的区域作为首个亲本，接着，为第二个亲本重复这一过程。偶有情形，我们会在中途设定两个不变标记，其形态如右图所示

运用这种手段，我们能在单次过程中选定两个亲本个体，并将此方法命名为「随机普遍选择法」。

4.4 交叉

先前环节已挑选出能够繁衍的后代亲本基因链，所谓「配对」，从生物角度理解就是指的繁殖现象，接下来我们针对步骤中选定的染色体 1 和 4 进行「配对」，具体情形如下图所示

这种互换最基础的样式，我们称作「单点互换」。在此，我们随机挑选一个互换位置，接着，把该位置之前的基因片段与之后的基因片段，在基因之间进行互换对接，由此便形成了新的后代。

若你确立两个相交位置，此种技术称作「多点相交」，参见图示。

4.5 变异

从生命科学的角度审视，需要探究的是：经由前述繁衍方式出生的后代，其体貌特征是否与双亲一致呢？答案是否定的。在子代发育期间，其遗传物质会经历若干调整，导致其与亲代有所区别。这种现象称作「变异」，它指染色体层面出现的随机性改变，正因存在变异，物种群体才会呈现丰富性。

下图为变异的一个简单示例：

基因发生改变后，便形成了新的生命体，物种的演化到此结束，整个过程具体展示在附图之中

完成「遗传变异」步骤后，我们借助适应度函数检测新生成的后代，当函数确认其符合标准时，便用这些个体替换掉那些表现不佳的基因型，这其中存在一个疑问开元ky888棋牌官网版，我们究竟该依据何种依据来判定后代已达到最优适应程度呢？

一般来说，有如下几个终止条件：

在进行 X 次迭代之后，总体没有什么太大改变。

我们事先为算法定义好了进化的次数。

当我们的适应度函数已经达到了预先定义的值。

现在，我们假定你已大体掌握了遗传算法的核心思想，接下来开yun体育app入口登录，就让我们借助这个方法，在数据分析的领域中展开实践。

5、遗传算法的应用

5.1 特征选取

设想一下，在参与数据科学竞赛时，如何挑选对目标变量预测起关键作用的特征呢？通常需要评估模型中各特征的重要性，随后设定一个界限值，选取那些重要性超过该界限的特征。

那么，是否存在更优的应对策略呢？事实上，针对特征挑选工作，遗传学方法堪称顶尖技术之一

我们先前解决背包问题的思路完全可以借鉴过来。接下来，我们首先需要构建「染色体」的整体框架，这里的染色体由二进制序列构成，其中「1」代表模型包含了对应特征，「0」则表示模型舍弃了该特征。

但是有一点差异，就是我们的评价函数需要调整。这个评价函数应该是本次竞赛准确度的衡量标准。具体来说，染色体的预测结果越准确，那么它的评价就越好。

我现在猜想你对该方法已有基本了解。接下来我不会立刻阐述这个问题的处理步骤，而是要引导大家先运用 TPOT 库来完成它。

5.2 用 TPOT 库来实现

这部分就是你最初阅读本文时心中最终期望达成的那个目的。就是：达成。现在我们先简要了解一下 TPOT 库（Tree-based Pipeline Optimisation Technique，树形传递优化技术），此库是建立在 scikit-learn 库之上的。接下来展示的是一种基础的传递构造图。

图中那个深色部分是借助 TPOT 库自动完成的。要完成这一步的自动化操作，必须运用遗传学方法。

我们不作详尽阐述，而是直接着手实践。若要运用 TPOT 库，必须预先配置 TPOT 所依赖的若干 python 框架。接下来，我们将迅速完成这些配置工作。

安装DEAP，更新检查器，以及tqdm使用pip安装deap，使用pip安装update_checker，使用pip安装tqdm安装TPOT使用pip安装tpot

这里，我选用了 Big Mart Sales（数据集地址：https://datahack.analyticsvidhya.com/contest/practice-problem-big-mart-sales-iii/）数据集，为后续工作做安排，我们先迅速获取训练和测试数据，接下来是 python 代码：

引入基础库，包含numpy，pandas，matplotlib.pyplot，设置绘图环境为inline模式，从sklearn中导入preprocessing和mean_squared_error### 数据预处理### 使用均值进行数据填充，应用于训练集

'Item_Weight'

.fillna((train

'Item_Weight'

.mean()), inplace=True)test

'Item_Weight'

.fillna((test

'Item_Weight'

将脂肪含量仅归为两类进行训练，先通过函数处理数据，然后删除多余字段

'Item_Fat_Content'

= train

'Item_Fat_Content'

.replace(

少脂肪的，简称为LF

少脂肪，少脂肪

)train

'Item_Fat_Content'

= train

'Item_Fat_Content'

.replace(

'reg'

'Regular'

)test

'Item_Fat_Content'

= test

'Item_Fat_Content'

.replace(

'low fat','LF'

'Low Fat','Low Fat'

)test

'Item_Fat_Content'

= test

'Item_Fat_Content'

.replace(

'reg'

'Regular'

)train

店铺开设年份

= 2013 - train

'Outlet_Establishment_Year'

test

'Outlet_Establishment_Year'

= 2013 - test

'Outlet_Establishment_Year'

train

'Outlet_Size'

将空值替换为小,然后应用这个变化到test上

'Outlet_Size'

用空值替换为小,完成替换,应用于训练集

'Item_Visibility'

= np.sqrt(train

'Item_Visibility'

)test

'Item_Visibility'

= np.sqrt(test

'Item_Visibility'

)col =

商品出口规模，销售网点地理位置，店铺经营类别，商品脂肪含量

test

'Item_Outlet_Sales'

将测试数据添加到训练集中，针对每一列进行遍历，合并这些数据

= number.fit_transform(combi

.astype('str'))combi

= combi

转换数据类型后训练集变为对象类型，组合数据完成

:train.shape

test = combi

train.shape

删除了名为商品出口销售额的列，通过指定轴为1并应用更改，训练数据集也去除了标识变量

渠道识别码，商品类别，物品编号

该测试集删除了轴为1的特定维度,得到tpot_test结果

'Outlet_Identifier','Item_Type','Item_Identifier'

,axis=1)target = tpot_train

'Item_Outlet_Sales'

tpot_train删除了名为Item_Outlet_Sales的列，采用inplace参数进行操作接着借助tpot库来构建模型从tpot导入TPOTRegressor函数将tpot_train和目标变量进行分割，训练集占比75%，测试集占比25将TPOTRegressor实例化，设置代数为5，种群大小为50，详细程度为2对训练集和目标训练集进行拟合操作输出模型在测试集上的得分将模型流程导出为tpot_boston_pipeline.py文件

这些代码执行过后，tpot_exported_pipeline.py 文件中就会包含执行路径优化的相关代码片段。经过分析，ExtraTreeRegressor 模型最为适合处理此类任务。

使用tpot优化后的管道进行预测，结果赋值给tpot_pred变量，然后创建一个数据框架sub1，包含tpot_pred数据，接着将数据框架的列名从'0'更改为'Item_Outlet_Sales'，最后输出sub1数据框架

'Item_Identifier'

= test

'Item_Identifier'

sub1

'Outlet_Identifier'

= test

'Outlet_Identifier'

sub1.columns =

销售项目金额,项目唯一识别码,店铺唯一识别码

sub1 = sub1

物品唯一编号，店铺唯一编号，商品销售额

将数据保存为文件名为tpot的csv格式，不包含行索引

若你递交了这个表格，便会察觉先前承诺的诸多功能尚未全部达成，这是否意味着我在欺瞒各位？绝非如此。事实上，TPOT 工具遵循一条基本准则，倘若未让其长时间执行，它便难以为你所面对的课题探寻出最优的解决方案。

因此，你需要提升算法的迭代次数，端着咖啡到户外散散步，剩下的工作就让 TPOT 来完成。不仅如此，这个工具同样适用于解决分类任务。想要了解更多详情，可以查阅这个网址：http://rhiever.github.io/tpot/。除了竞赛之外，日常生活中也存在许多可以利用遗传算法的场合。

6、 实际应用

遗传算法实际应用非常广泛。在此列举部分引人入胜的案例，不过受限于篇幅，无法对每个案例进行详尽阐述。

6.1 工程设计

工程设计高度依靠计算机建模与仿真，以此实现设计流程既迅速又划算，遗传算法在此能进行优化，并得出一个理想方案。

相关资源：