遗传算法的工作原理（附Python代码实现）

terry 2年前 (2023-09-27) 阅读数 74 #数据结构与算法

Analytics vidhya发表了一篇题为《Introduction to Genetic Algorithm & their application in data science》的文章。作者Shubham Jain结合自己的经验，用通俗易懂的语言对遗传算法进行了全面、简洁的概述。，并列出了其在多个领域的实际应用，重点介绍了遗传算法的数据科学应用。机器之心整理了这篇文章。

简介

前几天想解决一个实际问题：大型超市的销售问题。使用一些简单模型进行一些特征工程后，我在排行榜上排名第 219 位。

虽然结果很好，但我还是想做得更好。所以我开始研究可以提高我的分数的优化方法。正如所料，我找到了一个，它叫做遗传算法。将其应用到超市销售问题后，我的成绩跃居排行榜前列。

是的，我仅仅依靠遗传算法就从第219位直接跳到了第15位。太棒了！相信读完这篇文章后，你可以非常自如地应用遗传算法，并且你会发现当你将它应用到你正在处理的问题中时，效果会得到很大的提高。

内容

1.遗传算法理论的起源

2。生物灵感

3。遗传算法的定义

4。遗传算法具体步骤

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

5.遗传算法的应用

函数选择
使用TPOT库实现

6。实际应用

7.结论

1，遗传算法理论的起源

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

能够生存的往往不是最强大的物种，也不是最聪明的物种，而是能够生存下来的物种能最好地适应环境。。

你可能会想：这句话和遗传算法有什么关系呢？事实上，遗传算法的整个概念都是基于这句话。

我们用一个简单的例子来解释一下：

我们先从一个场景开始。现在你是一个国家的国王。为了使您的国家免遭灾难，您实施了一系列法律：

您选择了。所有好人都有义务通过生孩子来增加公民数量。
这个过程持续了几代人。
你会发现你已经有一整群好人了。

这个例子不太可能，但我将用它来帮助您理解这个概念。换句话说，如果我们改变输入值（例如：人口），我们可以获得更好的输出值（例如：更好的土地）。现在我假设你对这个概念有一个大致的了解，并且你认为遗传算法的含义应该与生物学相关。因此，让我们快速浏览一下一些小概念，以便我们可以将它们连接起来并理解它们。

2。生物启示

相信你还记得这句话：“细胞是一切生物的基石。”很明显，同一组染色体存在于生物体的每个细胞中。所谓染色体，是指由DNA组成的聚合物。

传统上，这些染色体可以表示为由数字0和1组成的序列。

染色体由基因组成，这些基因实际上形成了DNA的基本结构。 DNA 上的每个基因都编码一个独特的特征，例如头发或眼睛的颜色。我希望您在继续阅读之前记住这里提到的生物学概念。现在这一部分结束了，我们来看看所谓的遗传算法到底指的是什么？

3。遗传算法的定义

让我们首先回到前面讨论的示例并总结我们所做的事情。

首先我们确定公民的初始受众规模。
接下来我们定义一个函数，用它来区分好人和坏人。
我们再次选择好人，让他们繁衍自己的后代。
最终，这些后代取代了一些原公民的反派，重复了这个过程。

这就是遗传算法实际上的工作原理，也就是说，它实际上在某种程度上尽力模拟了进化过程。

因此，要正式定义遗传算法，我们可以将其视为一种优化方法，它可以尝试找到某些输入，使我们能够获得最佳的输出值或结果。遗传算法也起源于生物学。具体过程如下图所示：

现在让我们一步步了解整个过程。

4。遗传算法的具体步骤

为了让解释更容易，我们先来了解一下著名的组合优化问题“背包问题”。如果你还是不明白，这是我的解释版本。

例如，您要去旅行一个月，但您只能携带重量限制为30公斤的背包。现在你有几个必需的物品，每个物品都有自己的“生存点”（如下表所示）。因此，你的目标是在有限的背包重量内最大化你的“生存点数”。

4.1初始化

这里我们使用遗传算法来解决这个背包问题。第一步是定义我们的人口。种群由个体组成，每个个体都有自己的一组染色体。

我们知道染色体可以表示为二进制序列。在这个问题中，1代表该基因在下一个位置存在，0代表该基因缺失。（译者注：作者借用了染色体和基因来解决之前的背包问题，所以具体位置的基因代表了上面背包问题表中的条目。例如第一个位置是睡袋，然后反映在染色体上。 “基因”位置是染色体的第一个“基因”。）

现在我们将图像中的 4 条染色体视为我们的整体初始值。

4.2 适应度函数

我们来计算前两条染色体的适应度得分。对于A1染色体[100110]有：

同样对于A2染色体[001110]有：

对于这个问题我们认为当染色体包含更多的生存分数时，就意味着它有更多的生存分数。适应性强。

因此，从图中可以看出，1 号染色体比 2 号染色体更能适应。

4.3 选择

现在我们可以开始从群体中选择合适的染色体来相互“交配”。产生下一个我们这一代人。这是进行选择操作的总体思路，但这会导致染色体在经过几代之后，相互差异减少，失去多样性。因此，我们通常会执行“轮盘赌选择法”。

想象有一个轮盘赌，现在我们将它分成 m 个部分，其中 m 代表我们群体中的染色体数量。轮盘赌轮上每条染色体占据的面积与其适应度得分相关。

根据上图中的值，我们创建以下“轮盘赌”。

现在轮盘开始旋转，我们选择图像中固定点指示的区域作为第一个父级。然后我们对第二个父母做同样的事情。有时我们也会沿途标记两条固定线索，如下图：

通过这种方法，我们可以在一轮中获得两个父母。我们将此方法称为随机通用选择方法。

4.4 交叉

在上一步中，我们选择了可以产生后代的亲代染色体。所以从生物学的角度来说，所谓的“杂交”其实就是指繁殖。现在让我们“交叉”1号和4号染色体（在上一步中选择的），如下图所示：

这是最基本的交叉形式，我们称之为“单点交叉”。在这里，我们随机选择一个交叉点，然后交换交叉点前后的染色体，产生新的后代。

如果设置两个交叉点，这种方法称为“多点交叉”，见下图：

4.5 突变

现在如果我们从生物学的角度来看这个问题，请问：有上述过程产生的后代是否具有与父母相同的特征？答案是不。随着后代的成长，他们的基因发生变化，使他们与父母不同。我们将这个过程称为“突变”，它可以定义为染色体上发生的随机变化。正是通过突变，种群中才存在多样性。

下图是一个简单的突变示例：

突变完成后，我们得到了一个新的个体，进化就完成了。整个过程如下：

完成一轮“基因突变”后。然后我们使用适应度函数来验证这些新的后代。如果该函数确定它们足够适合，则它们将用于替换群体中不够适合的染色体。那么问题来了：我们最终应该用什么标准来判断后代是否达到了最优的适应度呢？

一般有以下终止条件：

经过X次迭代后，整体情况没有太大变化。
我们已经预定义了算法的进化次数。
当我们的适应度函数达到预定义值时。

好了，现在我想你已经从原理上理解了遗传算法的本质，那么现在让我们把它用在数据科学场景中。

5。遗传算法的应用

5.1 特征选择

想象一下，每次参加数据科学竞赛时，你会使用什么方法来选择那些对目标变量的预测很重要的特征？？通常，您会评估模型中特征的重要性，然后手动设置阈值并选择重要性高于该阈值的特征。

有没有办法更好的解决这个问题呢？处理特征选择任务的最先进算法之一是遗传算法。

我们之前处理背包问题的方法可以完全套用到这里。现在我们仍然开始确定一般的“染色体”。这里的染色体仍然是二进制序列。 “1”表示模型包含该特征，“0”表示模型不包含该特征。

然而，有一个区别：我们的适应度函数必须改变。这里的适应度函数应该是本次比赛的准确度标准。换句话说，如果一条染色体的预测值越准确，那么它的适应度可以说越高。

现在我想你已经知道这个方法了。我不会立即解释这个问题的解决方案，但我们首先使用 TPOT 库来实现它。

5.2 使用TPOT库实现

。相信这部分就是您第一次阅读本文时最终想要达到的目标。也就是说：实现。首先，让我们快速浏览一下 TPOT（基于树的管道优化技术）库，它基于 scikit-learn 库。下图显示了一个基本的传输结构。

图中灰色区域是使用TPOT库自动处理的。需要遗传算法来实现这部分的自动处理。

这里不深入解释，直接应用。要使用 TPOT 库，您首先需要安装一些构建 TPOT 的 Python 库。让我们快速安装它们：

# installing DEAP, update_checker and tqdm 

pip install deap update_checker tqdm
# installling TPOT 
pip install tpot

这里我使用了Big Mart Sales数据集（数据集地址：https://datahack.analyticsvidhya.com/contest/practice-problem-big-mart-sales-iii/）来准备实施，我们首先快速下载训练和测试文件。以下是Python代码：

# import basic libraries

import numpy as np 
import pandas as pd 
import matplotlib.pyplot as plt 
%matplotlib inline 
from sklearn import preprocessing 
from sklearn.metrics import mean_squared_error 
## preprocessing 
### mean imputations 

train['Item_Weight'].fillna((train['Item_Weight'].mean()), inplace=True)
test['Item_Weight'].fillna((test['Item_Weight'].mean()), inplace=True) 
### reducing fat content to only two categories 

train['Item_Fat_Content'] = train['Item_Fat_Content'].replace(['low fat','LF'], ['Low Fat','Low Fat']) 
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['Outlet_Establishment_Year'] = 2013 - train['Outlet_Establishment_Year'] 
test['Outlet_Establishment_Year'] = 2013 - test['Outlet_Establishment_Year'] 

train['Outlet_Size'].fillna('Small',inplace=True)
test['Outlet_Size'].fillna('Small',inplace=True)

train['Item_Visibility'] = np.sqrt(train['Item_Visibility'])
test['Item_Visibility'] = np.sqrt(test['Item_Visibility'])

col = ['Outlet_Size','Outlet_Location_Type','Outlet_Type','Item_Fat_Content']
test['Item_Outlet_Sales'] = 0combi = train.append(test)for i in col:
 combi[i] = number.fit_transform(combi[i].astype('str'))
 combi[i] = combi[i].astype('object')
train = combi[:train.shape[0]]
test = combi[train.shape[0]:]
test.drop('Item_Outlet_Sales',axis=1,inplace=True)
## removing id variables 

tpot_train = train.drop(['Outlet_Identifier','Item_Type','Item_Identifier'],axis=1)
tpot_test = test.drop(['Outlet_Identifier','Item_Type','Item_Identifier'],axis=1)
target = tpot_train['Item_Outlet_Sales']
tpot_train.drop('Item_Outlet_Sales',axis=1,inplace=True)
# finally building model using tpot library

from tpot import TPOTRegressor
X_train, X_test, y_train, y_test = train_test_split(tpot_train, target,
 train_size=0.75, test_size=0.25)

tpot = TPOTRegressor(generations=5, population_size=50, verbosity=2)
tpot.fit(X_train, y_train)
print(tpot.score(X_test, y_test))
tpot.export('tpot_boston_pipeline.py')

这些代码完成后，用于路径优化的Python代码将被放置在tpot_exported_pipeline.py中。我们可以得出结论，ExtraTreeRegressor最能解决这个问题。

## predicting using tpot optimised pipeline

tpot_pred = tpot.predict(tpot_test)
sub1 = pd.DataFrame(data=tpot_pred)
#sub1.index = np.arange(0, len(test)+1)

sub1 = sub1.rename(columns = {'0':'Item_Outlet_Sales'})
sub1['Item_Identifier'] = test['Item_Identifier']
sub1['Outlet_Identifier'] = test['Outlet_Identifier']
sub1.columns = ['Item_Outlet_Sales','Item_Identifier','Outlet_Identifier']
sub1 = sub1[['Item_Identifier','Outlet_Identifier','Item_Outlet_Sales']]
sub1.to_csv('tpot.csv',index=False)

提交这个CSV文件后，你会发现我一开始的承诺并没有完全兑现。我在骗你吗？当然不是。实际上，TPOT 库有一个简单的规则。如果您长时间不使用 TPOT，程序将无法找出最有可能解决您的问题的交付方法。

所以你需要增加进化代数，喝杯咖啡去散步，剩下的就交给TPOT吧。而且，你还可以使用这个库来解决分类问题。更多信息请参考此文档：http://rhiever.github.io/tpot/。除了比赛之外，生活中我们还有很多可以用到遗传算法的应用场景。