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

近期，在Analyticsvidhya平台上有一篇名为《遗传算法入门及其在数据科学领域的应用》的文章，作者Shubham Jain亲自阐述，以浅显易懂的文字对遗传算法进行了详尽且精炼的介绍，同时他还展示了该算法在众多领域的具体应用案例，特别着重于遗传算法在数据科学领域的应用情况。机器之心对该文进行了编译，原文链接请见文末。

简介

不久前，我开始着手处理一个具体的难题——那就是大型超市的销售问题。经过对几个基础模型的应用和一系列特征工程的操作，我在竞赛的排行榜上取得了第219名的成绩。

尽管成绩已经相当可观，我内心却渴望更上一层楼。因此，我投入精力去探寻提升成绩的技巧。经过一番努力，我成功发现了一种名为遗传算法的方法。将此方法应用于超市销售问题后，我的成绩在排行榜上迅速攀升，名列前茅。

没错，仅凭遗传算法，我就能从219名跃升至15名，这真的很厉害！相信你在阅读完这篇文章后，同样能够熟练运用遗传算法，并且在使用它解决你自己的问题时，你会发现其效果同样显著提升。

目录

1、遗传算法理论的由来

2、生物学的启发

3、遗传算法定义

4、遗传算法具体步骤

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

5、遗传算法的应用

特征选取使用 TPOT 库实现

6、实际应用

7、结语

1、遗传算法理论的由来

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

存活下来的往往是那些并非最强壮亦非最智慧的物种，而是那些最能顺应环境变化的物种。

或许你会有所疑问：这句话与遗传算法之间有何关联？实际上，遗传算法这一理念正是建立在这样一个观点之上。

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

我们设一个场景，假想自己成为了一个国家的君主，为了确保国家远离灾难，我们制定了一系列的法律和措施：

你挑选出了所有品德高尚的人，并期望他们通过繁衍后代来增加国民总数。这一过程历经数代人的努力。最终，你会发现，你已经聚集了一大批优秀的人才。虽然这样的例子并不常见，但我举这个例子是为了让你更好地把握这个理念。换句话说，通过调整输入条件（例如：人口数量），我们就能实现更优的输出结果（例如：一个更美好的国家）。目前，我假设你对这一概念已经有了基本的认识，并认同遗传算法的内涵与生物学存在关联。基于此，我们将简要探讨几个相关的小概念，以便于你们将这些概念相互串联，形成深入的理解。

2、生物学的启发

你还应该对这句话印象深刻：「细胞构成了所有生物的基础。」从这个观点来看，每个生物体内的每一个细胞都携带着相同的染色体组。所谓的染色体，实际上是由DNA构成的集合体。

在传统观念中，这些染色体能够通过由数字零和一构成的字符序列来表示。

染色体是由基因构成的，而这些基因正是DNA的基本构成单元。DNA上的每一个基因都负责编码一个特定的性状，例如头发的颜色或是眼睛的色泽。在您继续阅读之前，不妨先回顾一下文中提到的生物学知识点。这部分内容结束后，我们将深入探讨所谓的遗传算法究竟是指什么。

3、遗传算法定义

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

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

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

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

最终，这些新生代成员取代了部分原有的不良分子，并且这一行为模式持续不断地被重复执行。

遗传算法运作的原理实际上与此类似，换言之，它主要是在一定程度上尽可能地模仿了生物进化的过程。

因此，在给遗传算法一个形式化的定义时，我们可以将其视为一种优化策略，这种策略能够尝试寻找特定的输入，通过这些输入，我们能够获得最理想的输出值或结果。遗传算法的运作原理借鉴了生物学的原理，具体操作步骤可参考下方的图示：

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

4、遗传算法具体步骤

为了使讲解过程更加直观易懂，我们首先需对广为人知的组合优化难题——“背包问题”进行一番认识。若您对此尚感困惑，不妨参考以下我提供的个人解读。

例如，若你计划外出探险长达一个月，却只能携带一个重量上限为30公斤的行囊。目前，你面临众多必需品，每一样都标注有各自的“生存价值”（详细信息请参考下表）。鉴于此，你的任务是确保在背包重量限制内，尽可能提升你的“生存价值”。

4.1 初始化

在此，我们采用遗传算法来攻克背包难题。首先，我们需要明确我们的总体概念。这个总体由众多个体组成，而每个个体都携带着一套独特的染色体。

我们了解到，染色体可以被表示为一系列的二进制数字，具体来说，数字1代表该位置的基因是存在的，而数字0则表明该基因已经缺失。作者此处运用染色体与基因的概念来处理前述的背包问题，故而在染色体上特定位置的基因对应着背包问题表格中的各个物品。例如，若第一个位置标注的是Sleeping Bag，那么在染色体上的相应‘基因’位置上，便体现了该染色体的首个‘基因’。

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

4.2 适应度函数

现在，我们需对前两条染色体的适应度进行评估。针对 A1 染色体，我们将进行相应的计算。

100110

而言，有：

类似地，对于 A2 染色体

001110

来说，有：

关于这一议题，我们持这样的观点：若染色体中携带的生存率数值较高，则表明其具有更佳的适应性。

因此kaiyun全站网页版登录，由图可知，染色体 1 适应性强于染色体 2。

4.3 选择

此刻，我们着手从整体中挑选恰当的染色体，促使它们进行“配对”，进而孕育出新的后代。这便是选择操作的大致构想。然而，如此操作会在数代之后使染色体间的差异逐渐缩小，导致多样性的丧失。鉴于此，我们通常采用“轮盘赌选择法”。

设想一个圆形的轮盘，我们将它划分为 m 个区域，其中 m 是我们染色体总数的象征。每个区域所代表的面积，将依照各自的适应度得分，按比例进行分配。

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

此刻，轮盘开始转动，我们将目光锁定图中的定点指针所指的区域，将其作为首个亲本的候选。随后的步骤中开yun体育app官网网页登录入口，我们将对第二个亲本采取相同的选取方式。在某些情况下，我们还会在图中标记两个定点指针，如图所示。

采用此法，我们能够在单次操作中同时获取两个亲本。我们将此技术命名为“随机全面选取法”。

4.4 交叉

在先前的阶段，我们已成功挑选出能够繁衍后代的亲本染色体。按照生物学的术语，所谓的“交叉”实际上就是繁殖的过程。接下来，我们将对步骤一中选定的染色体1和染色体4实施“交叉”操作，具体操作方法可参考下方的图示。

这是最基本的交叉方式，我们将其命名为“单点交叉”。在此过程中，我们随机选取一个交叉点，随后，将交叉点附近染色体的相应部分进行交换，从而孕育出新的后代。

若你设定了两个相交的点，这种技术便称作“多点交叉”，具体可参考下方的示意图。

4.5 变异

若我们从生物学的视角审视此问题，便会发现：上述过程孕育出的子代是否继承了与父母相同的特征？答案是否定的。在子代成长的过程中，其体内的基因会发生某些改变，导致它们与父母存在差异。我们将这一现象称作“变异”，它指的是染色体上发生的随机性变化。正因如此，种群中才呈现出多样性。

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

变异过程结束后，我们将获得新的个体，此时进化过程便告一段落，具体步骤详见图示。

完成了一次“遗传变异”过程后，我们借助适应度函数对新生个体进行检验，若该函数认为它们的适应度达标，便将它们用于替换总体中那些适应度不足的染色体。然而，一个问题随之而来，我们究竟应依据何种标准来判定后代是否已达到最佳的适应度状态呢？

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

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

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

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

既然你已经对遗传算法的基本原理有了大致的了解，那么接下来，我们就将尝试将其应用于数据科学领域。

5、遗传算法的应用

5.1 特征选取

设想在参与数据科学竞赛时，你将如何筛选出对目标变量预测至关重要的特征？你通常会评估模型中各个特征的重要性，随后手动设定一个标准值，进而挑选出重要性超过此标准值的特征。

那么，是否存在着某种方法，能够更有效地解决这一问题呢？实际上，在处理特征选择任务方面，遗传算法可称得上是当前最为先进的算法之一。

我们之前解决背包问题的策略在此处同样适用。首先，我们需要构建「染色体」的总体框架，这里的「染色体」依旧是由二进制数字组成的序列，「1」代表模型中包含该特征，「0」则表示模型中不包含该特征。

然而，存在一个显著差异，那就是我们的适应性函数必须作出调整。在这个情境下，适应性函数应当作为衡量本次竞赛精确度的准则。换句话说，若染色体的预测结果越接近真实值，那么其适应性便相对更强。

现在，我假定你对这种方法已有了一定的了解。在此，我暂不立即阐述该问题的解决方案，而是建议我们先借助 TPOT 库来尝试实现它。

5.2 用 TPOT 库来实现

这部分内容很可能是您在阅读本文之初心中所期望达成的目标。也就是说，目标是实现这一目标。因此，我们首先简要介绍一下 TPOT 库，即树形传递优化技术（Tree-based Pipeline Optimisation Technique），它是以 scikit-learn 库为基础构建的。图中展示了一个基础的传递结构。

图中灰色区域的处理是通过TPOT库自动完成的，而要实现这一自动处理功能，遗传算法是必不可少的。

在此，我们不进行深入的理论阐述，而是直接将其应用于实践。为了能够运用 TPOT 库，您必须首先安装一系列构建于其基础之上的 Python 库。接下来，我们将迅速进行安装。

安装DEAP、update_checker以及tqdm库，执行命令如下：pip install deap, update_checker, tqdm；同时，安装TPOT库，使用以下命令：pip install tpot。

在此，我选用了Big Mart Sales数据集（数据集链接：https://datahack.analyticsvidhya.com/contest/practice-problem-big-mart-sales-iii/）进行准备工作，因此我们首先需要迅速下载相关的训练和测试文件，下面是相应的Python代码：。

导入基础库，例如numpy、pandas、matplotlib.pyplot，以及sklearn中的preprocessing和metrics模块。接下来，进行数据预处理，特别是均值填充操作。

'Item_Weight'

.fillna((train

'Item_Weight'

.mean()), inplace=True)test

'Item_Weight'

.fillna((test

'Item_Weight'

执行.mean()函数，将脂肪含量降至仅两个类别，且操作直接在原数据上进行。

'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'

对数据进行处理，将空值填充为“Small”kaiyun全站登录网页入口，并直接在原数据集上进行修改。

'Outlet_Size'

将缺失值填充为“Small”，并直接在原数据集上进行修改。

'Item_Visibility'

= np.sqrt(train

'Item_Visibility'

)test

'Item_Visibility'

= np.sqrt(test

'Item_Visibility'

)col =

'出口尺寸','店铺位置类型','店铺类型','商品脂肪含量'

test

'Item_Outlet_Sales'

将测试数据集追加到训练数据集，随后对每一列进行迭代处理：0combi = train.append(test)，for i in col:combi。

= number.fit_transform(combi

.astype('str'))combi

= combi

将训练数据转换为对象类型，并存储在变量train中。

:train.shape

test = combi

train.shape

出口标识符，商品类型，商品标识符。

axis=1，tpot_test变量被创建，它是通过从test数据集中删除指定列得到的。

'Outlet_Identifier','Item_Type','Item_Identifier'

,axis=1)target = tpot_train

'Item_Outlet_Sales'

使用tpot库删除了'Item_Outlet_Sales'列，随后，我们构建模型。导入TPOTRegressor，将数据集分为训练集和测试集，其中75%用于训练，25%用于测试。设置TPOTRegressor的参数，包括迭代次数、种群大小和详细程度。模型在训练集上训练完毕后，输出测试集上的评分。最后，将模型导出为Python文件。

代码执行完毕后，tpot_exported_pipeline.py 文件中将存储用于路径调整的 Python 源码。通过观察，我们发现 ExtraTreeRegressor 能够最为有效地解决这一问题。

利用经过tpot优化的pipelinetpot_pred对tpot_test进行预测，得到预测结果后，创建一个包含这些结果的DataFrame sub1，并将test数据的索引从0开始连续编号，最后将列名'0'更改为'Item_Outlet_Sales'。

'Item_Identifier'

= test

'Item_Identifier'

sub1

'Outlet_Identifier'

= test

'Outlet_Identifier'

sub1.columns =

'项目销售数据'，'商品标识符'，'销售点标识符'

sub1 = sub1

项目标识符，销售点标识符，商品销售点销售额

将数据保存至名为“tpot.csv”的文件中，不包含行索引。

因此，需要提升进化的计算量，外出时带上咖啡，其他事宜则可交由TPOT处理。另外，此库同样适用于解决分类难题。更多详细信息，请参阅该文档：http://rhiever.github.io/tpot/。实际上，除了竞赛场合，遗传算法在日常生活诸多场景中也大有可为。

6、 实际应用

遗传算法在现实世界中应用广泛。以下是一些颇具趣味的应用场景，不过因篇幅所限，我无法对每一个都进行详尽阐述。

6.1 工程设计

工程设计高度依赖于计算机的建模与仿真技术，这一做法使得设计流程既高效又节省成本。在此过程中，遗传算法能够发挥其优化作用，并最终提供令人满意的结果。

相关资源：