遗传算法GA详解（Python实现代码）

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

遗传算法（GA，Genetic Algorithm），又称进化算法！？能够适应环境的物种。

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

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

我们先假设一个场景。现在你是一个国家的国王。为了拯救你的国家免于灾难，你制定了一套法律：

你选择所有善良的人都必须通过生育来扩大他们的数量国民。
这个过程持续了几代人。
你会发现你已经有一整群好人了。

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

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次迭代后，大体情况没有太大变化。
我们提前定义了算法的进化次数。
当我们的适应度函数达到预定义值时。

好了，现在我假设你已经基本了解了遗传算法的本质，那么现在让我们将其应用到数据科学场景中。？？你经常会判断模型中特征的重要性，然后手动设置一个阈值，选择重要性高于这个阈值的特征。

那么，有什么办法可以更好地处理这个问题呢？事实上，处理特征选择任务的最先进算法之一是遗传算法。

我们之前处理背包问题的方法可以完全套用到这里。现在我们还是从建立整体的“染色体”开始。这里的染色体仍然是一个二进制串。 “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/。除了比赛之外，我们生活中也有很多可以用到遗传算法的使用场景。