最近在Analyticsvidhya上发表了一篇名为《Introduction to Genetic Algorithm & their application in data science》的文章。一个简洁的概述，包含多个领域的实际应用示例，重点是遗传算法的数据科学应用。简介前几天，我着手解决一个实际问题——一个大卖场的销售问题。在用几个简单的模型做了一些特征工程之后，我在排行榜上排名第219位。虽然结果不错，但我还是想做得更好。于是，我开始研究可以提高分数的优化方法。结果，我找到了一个，它叫做遗传算法。应用到超市销售问题后，我的分数终于跃升到了排行榜的前列。没错，我光靠遗传算法就从219直接跳到了15，厉害了！相信看完这篇文章，你也可以将遗传算法应用得淋漓尽致，你会发现当你把它应用到自己处理问题的时候，效果也会有很大的提升。一、遗传算法理论的起源让我们从达尔文的一句名言说起：能够生存的往往不是体型最大或最聪明的物种，而是最能适应环境的物种。你可能会想：这句话和遗传算法有什么关系？事实上，遗传算法的整个概念都是基于这句话。让我们用一个基本的例子来解释：让我们先假设一个场景，现在你是一个国家的国王，为了拯救你的国家免受灾难，你实施了一套法律：你选举所有好人并要求他们成为born扩大公民数量。这个过程持续了几代人。你会发现你有一大群好人。这个例子不太可能，但我用它来帮助你理解这个概念。换句话说，我们改变输入值（例如：人口）以获得更好的输出值（例如：更好的国家）。现在，我假设你对这个概念有一个大概的了解，并且认为遗传算法的含义应该与生物学有关。因此，让我们快速浏览一些小概念，以便将它们联系在一起。2.生物学的启发相信大家还记得这句话：“细胞是一切生物的基石”。由此我们可以看出，生物体内的任何一个细胞都具有相同的染色体组。染色体是由DNA组成的聚集体。传统上，这些染色体可以用一串数字0和1来表示。染色体由基因组成，基因是DNA的基本组成部分，其中每个基因编码一个独特的特征，例如头发或眼睛的颜色。我希望你在继续阅读之前记得这里提到的生物学概念。这部分就结束了，现在我们来看看所谓的遗传算法到底指的是什么？3.遗传算法定义首先，让我们回到前面讨论的例子，总结一下我们所做的。首先，我们设置国民的初始人口规模。然后，我们定义一个函数来区分好人和坏人。同样，我们选择优秀的人，让他们繁殖自己的后代。最后，这些后代换掉了原人中的一些坏人，如此循环往复。这实际上就是遗传算法的工作原理，也就是说，它基本上试图在某种程度上模拟进化过程。因此，为了形式化地定义一个遗传算法，我们可以把它看作是一种优化方法，它可以尝试找到某些输入，用它我们可以获得最好的输出值或结果。遗传算法的工作方法也来源于生物学。具体过程如下图所示：下面我们一步一步来了解一下整个过程。4.遗传算法的具体步骤为了便于解释，我们先来了解一下著名的组合优化问题“背包问题”。如果您还不太明白，这是我的解释版本。比如你打算去野外一个月，但是你只能背一个背包，背包的重量限制为30公斤。现在你有不同的必需品，每一种都有自己的“生存点数”（具体在下表中给出）。因此，你的目标是在有限的背包重量下最大化你的“生存点数”。4.1初始化这里我们使用遗传算法来解决背包问题。第一步是定义我们的人口。种群包含个体，每个个体都有自己的一组染色体。我们知道，染色体可以表示为一串二进制数。在这个问题中，1表示下一个位置的基因存在，0表示缺失。（译者注：作者这里借用了染色体和基因来解决之前的背包问题，所以特定位置的基因代表了上面背包问题表中的物品。比如第一个位置是SleepingBag，那么就体现在染色体的“基因”位置是该染色体的第一个“基因”。）现在，我们将图中的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库来实现这部分相信是你初读本文时最终想要达到的目标。即：达到。那么首先，让我们快速了解一下基于scikit-learn库的TPOT库（Tree-basedPipelineOptimizationTechnique，基于树的流水线优化技术）。下图显示了一个基本的传输结构。图中灰色区域是用TPOT库自动处理的。这部分的自动处理需要用到遗传算法。我们这里不赘述，直接应用。为了能够使用TPOT库，您需要首先安装一些构建TPOT的python库。让我们快速安装它们：#installingDEAP,update_checkerandtqdmpipinstalldeapupdate_checkertqdm#installlingTPOTpipinstalltpot这里，我使用了BigMartSales（数据集地址：https://datahack.analyticsvidhya.com/contest/practice-problem-big-mart-sales-iii/）数据集，准备实施，我们快速下载训练和测试文件，下面是python代码：]f'].mean()),inplace=True)test['Item_Weight'].fillna((test['Item_Weight'].mean()),inplace=True)###reducingfatcontenttoonlytwocategoriestrain['Item_Fat_Content']=train['Item_Fat_Content'].replace(['lowfat','LF'],['LowFat','LowFat'])train['Item_Fat_Content']=train['Item_Fat_Content'].replace(['reg'],['Regular'])test['Item_Fat_Content']=test['Item_Fat_内容'].replace(['lowfat','LF'],['LowFat','LowFat'])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(测试)foriincol: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)##removingidvariablestpot_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)#finallybuildingmodelusingtpotlibraryfromtpotimportTPOTRegressorX_train,X_test,y_train,y_test=train_test_split(tpot_train,target,train_size=0.75,test_size=0.25)tpot=TPOTRegressor(代数=0_bosize=5)tpot.fit(X_train,y_train)print(tpot.score(X_test,y_test))tpot.export('tpot_boston_pipeline.py')运行完这些代码后，tpot_exported_pipeline.py会把python进行路径优化我们可以在代码中发现ExtraTreeRegressor可以完美解决这个问题问题。##使用tpotoptimisedpipelinetpottpot_pred=tpot.predict(tpot_test)sub1=pd.DataFrame(data=tpot_pred)#sub1.index=np.arange(0,len(test)+1)sub1sub1=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']sub1sub1=sub1[['Item_Identifier','Outlet_Identifier','Item_Outlet_Sales']]sub1.to_csv('tpot.csv',index=False)如果你提交这个csv，那么你会发现我一开始承诺的有没有完全实现。我在骗你吗？当然不是。实际上，TPOT库有一个简单的规则。如果您运行TPOT的时间不长，那么它不会为您的问题找出最可能的传递路径。所以，你要增加进化代数，喝杯咖啡出去走走，剩下的交给TPOT。此外，您还可以使用这个库来解决分类问题。更多内容请参考此文档：http://rhiever.github.io/tpot/。除了比赛，我们在生活中还有很多应用场景可以用到遗传算法。6.实际应用遗传算法在现实世界中有很多应用。这里我罗列了一些有趣的场景，但限于篇幅，我就不一一详细介绍了。6.1工程设计工程设计在很大程度上依赖于计算机建模和仿真，以使设计周期过程快速且经济。可以在这里优化遗传算法并给出良好的结果。相关资源：论文：Engineeringdesignusinggeneticalgorithms地址：http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=16942&context=rtd6.2Trafficandshippingroutes（TravellingSalesmanProblem，旅行商问题）这是一个非常有名的问题，已经被许多贸易公司用来使运输更省时、更经济。为了解决这个问题，还使用了遗传算法。6.3机器人遗传算法广泛应用于机器人领域。事实上，遗传算法目前正被用于创建可以像人类一样行动的自学机器人，执行诸如做饭和洗衣服等任务。相关资源：论文：GeneticAlgorithmsforAuto-tuningMobileRobotMotionControl地址：https://pdfs.semanticscholar.org/7c8c/faa78795bcba8e72cd56f8b8e3b95c0df20c.pdf7。结束语希望通过这篇文章，您对遗传算法有了足够的了解，并且会使用TPOT库来实现它。但是如果不亲自实践的话，这篇文章的知识也是非常有限的。因此，无论是数据科学竞赛还是生活中，读者朋友们一定要自己去尝试去实现。原文：https://www.analyticsvidhya.com/blog/2017/07/introduction-to-genetic-algorithm/:almosthuman2014)》]点此阅读作者更多好文
