什么是遗传算法，它有哪些实际应⽤？
⼏天前，我着⼿解决⼀个实际问题——⼤型超市销售问题。在使⽤了⼏个简单模型做了⼀些特征⼯程之后，我在排⾏榜上名列第219名。
虽然结果不错，但是我还是想做得更好。
于是，我开始研究可以提⾼分数的优化⽅法。结果我果然到了⼀个，它叫遗传算法。在把它应⽤到超市销售问题之后，最终我的分数在排⾏榜上⼀下跃居前列。
没错，仅靠遗传算法我就从219名直接跳到15名，厉害吧！相信阅读完本篇⽂章后，你也可以很⾃如地应⽤遗传算法，⽽且会发现，当把它⽤到你⾃⼰正在处理的问题时，效果也会有很⼤提升。
⽬录
1、遗传算法理论的由来
2、⽣物学的启发
3、遗传算法定义
4、遗传算法具体步骤
初始化
适应度函数
选择
交叉
变异
5、遗传算法的应⽤
特征选取
使⽤TPOT库实现
6、实际应⽤
7、结语
1、遗传算法理论的由来
我们先从查尔斯·达尔⽂的⼀句名⾔开始：
不是最强⼤、也不是最聪明的物种才能⽣存，⽽是最能对变化作出回应的那⼀个。
你也许在想：这句话和遗传算法有什么关系？其实遗传算法的整个概念就基于这句话。让我们⽤⼀个基本例⼦来解释：
我们先假设⼀个情景，现在你是⼀国之王，为了让你的国家免于灾祸，你实施了⼀套法案：
你选出所有的好⼈，要求其通过⽣育来扩⼤国民数量。
这个过程持续进⾏了⼏代。
你将发现，你已经有了⼀整的好⼈。
这个例⼦虽然不太可能，但是我⽤它是想帮助你理解概念。也就是说，我们改变了输⼊值（⽐如：⼈⼝），就可以获得更好的输出值（⽐如：更好的国家）。
现在，我假定你已经对这个概念有了⼤致理解，认为遗传算法的含义应该和⽣物学有关系。那么我们
就快速地看⼀些⼩概念，这样便可以将其联系起来理解。
2、⽣物学的启发
相信你还记得这句话：
“细胞是所有⽣物的基⽯。”
由此可知，在⼀个⽣物的任何⼀个细胞中，都有着相同的⼀套染⾊体。所谓染⾊体，就是指由DNA组成的聚合体。
传统上看，这些染⾊体可以被由数字0和1组成的字符串表达出来。
⼀条染⾊体由基因组成，这些基因其实就是组成DNA的基本结构，DNA上的每个基因都编码了⼀个独特的性状，⽐如，头发或者眼睛的颜⾊。
希望你在继续阅读之前先回忆⼀下这⾥提到的⽣物学概念。结束了这部分，现在我们来看看所谓遗传算法实际上指的是什么？
3、遗传算法定义
⾸先我们回到前⾯讨论的那个例⼦，并总结⼀下我们做过的事情。
1. ⾸先，我们设定好了国民的初始⼈⼤⼩。
2. 然后，我们定义了⼀个函数，⽤它来区分好⼈和坏⼈。
3. 再次，我们选择出好⼈，并让他们繁殖⾃⼰的后代。
4. 最后，这些后代们从原来的国民中替代了部分坏⼈，并不断重复这⼀过程。
遗传算法实际上就是这样⼯作的，也就是说，它基本上尽⼒地在某种程度上模拟进化的过程。因此，为了形式化定义⼀个遗传算法，我们可以将它看作⼀个优化⽅法，它可以尝试出某些输⼊，凭借这些输⼊我们便可以得到最佳的输出值或者是结果。遗传算法的⼯作⽅式也源⾃于⽣物学，具体流程见下图：
那么现在我们来逐步理解⼀下整个流程。
4、遗传算法具体步骤
为了让讲解更为简便，我们先来理解⼀下著名的组合优化问题“背包问题”。如果你还不太懂，这⾥有⼀个我的解释版本。
⽐如，你准备要去野游1个⽉，但是你只能背⼀个限重30公⽄的背包。现在你有不同的必需物品，它们每⼀个都有⾃⼰的“⽣存点数”（具体在下表中已给出）。因此，你的⽬标是在有限的背包重量下，最⼤化你的“⽣存点数”。
4.1 初始化
这⾥我们⽤遗传算法来解决这个背包问题。第⼀步是定义我们的总体。总体中包含了个体，每个个体都有⼀套⾃⼰的染⾊体。
我们知道，染⾊体可表达为2进制数串，在这个问题中，1代表接下来位置的基因存在，0意味着丢失。（译者注：作者这⾥借⽤染⾊体、基因来解决前⾯的背包问题，所以特定位置上的基因代表了上⽅背包问题表格中的物品，⽐如第⼀个位置上是Sleeping Bag，那么此时反映在染⾊体的‘基因’位置就是该染⾊体的第⼀个‘基因’。）
现在，我们将图中的4条染⾊体看作我们的总体初始值。
4.2 适应度函数
接下来，让我们来计算⼀下前两条染⾊体的适应度分数。
对于A1染⾊体[100110]⽽⾔，有：
类似地，对于A2染⾊体[001110]来说，有：
对于这个问题，我们认为，当染⾊体包含更多⽣存分数时，也就意味着它的适应性更强。因此，由图可知，染⾊体1适应性强于染⾊体2。
4.3 选择
现在，我们可以开始从总体中选择适合的染⾊体，来让它们互相‘交配’，产⽣⾃⼰的下⼀代了。
这个是进⾏选择操作的⼤致想法，但是这样将会导致染⾊体在⼏代之后相互差异减⼩，失去了多样性。
因此，我们⼀般会进⾏“赌选择法”（Roulette Wheel Selection method）。update是什么
想象有⼀个，现在我们将它分割成m个部分，这⾥的m代表我们总体中染⾊体的个数。每条染⾊体在上占有的区域⾯积将根据适应度分数成⽐例表达出来。
基于上图中的值，我们建⽴如下“”。
现在，这个开始旋转，我们将被图中固定的指针（fixed point）指到的那⽚区域选为第⼀个亲本。然后，对于第⼆个亲本，我们进⾏同样的操作。
有时候我们也会在途中标注两个固定指针，如下图：
通过这种⽅法，我们可以在⼀轮中就获得两个亲本。我们将这种⽅法成为“随机普遍选择
法”（Stochastic Universal Selection method）。
4.4 交叉
在上⼀个步骤中，我们已经选择出了可以产⽣后代的亲本染⾊体。那么⽤⽣物学的话说，所
谓“交叉”，其实就是指的繁殖。
现在我们来对染⾊体1和4（在上⼀个步骤中选出来的）进⾏“交叉”，见下图：
这是交叉最基本的形式，我们称其为“单点交叉”。这⾥我们随机选择⼀个交叉点，然后，将交叉点前后的染⾊体部分进⾏染⾊体间的交叉对调，于是就产⽣了新的后代。
如果你设置两个交叉点，那么这种⽅法被成为“多点交叉”，见下图：
4.5 变异
如果现在我们从⽣物学的⾓度来看这个问题，那么请问：由上述过程产⽣的后代是否有和其⽗母⼀样的性状呢？答案是否。在后代的⽣长过程中，它们体内的基因会发⽣⼀些变化，使得它们与⽗母不同。
这个过程我们称为“变异”，它可以被定义为染⾊体上发⽣的随机变化，正是因为变异，种中才会存在多样性。
下图为变异的⼀个简单⽰例：
变异完成之后，我们就得到了新为个体，进化也就完成了，整个过程如下图：
在进⾏完⼀轮“遗传变异”之后，我们⽤适应度函数对这些新的后代进⾏验证，如果函数判定它们适应度⾜够，那么就会⽤它们从总体中替代掉那些适应度不够的染⾊体。
这⾥有个问题，我们最终应该以什么标准来判断后代达到了最佳适应度⽔平呢？
⼀般来说，有如下⼏个终⽌条件：
1. 在进⾏X次迭代之后，总体没有什么太⼤改变。
2. 我们事先为算法定义好了进化的次数。
3. 当我们的适应度函数已经达到了预先定义的值。
好了，现在我假设你已基本理解了遗传算法的要领，那么现在让我们⽤它在数据科学的场景中应⽤⼀番。
5、遗传算法的应⽤
5.1 特征选取
试想⼀下每当你参加⼀个数据科学⽐赛，你会⽤什么⽅法来挑选那些对你⽬标变量的预测来说很重要的特征呢？你经常会对模型中特征的重要性进⾏⼀番判断，然后⼿动设定⼀个阈值，选择出其重要性⾼于这个阈值的特征。
那么，有没有什么⽅法可以更好地处理这个问题呢？其实处理特征选取任务最先进的算法之⼀就是遗传算法。
我们前⾯处理背包问题的⽅法可以完全应⽤到这⾥。现在，我们还是先从建⽴“染⾊体”总体开始，这⾥的染⾊体依旧是⼆进制数串，“1”表⽰模型包含了该特征，“0表⽰模型排除了该特征”。
不过，有⼀个不同之处，即我们的适应度函数需要改变⼀下。这⾥的适应度函数应该是这次⽐赛的的精度的标准。也就是说，如果染⾊体的预测值越精准，那么就可以说它的适应度更⾼。
现在我假设你已经对这个⽅法有点⼀概念了。下⾯我不会马上讲解这个问题的解决过程，⽽是让我们先来⽤TPOT库去实现它。
5.2 ⽤TPOT库来实现
这个部分相信是你在⼀开始读本⽂时⼼⾥最终想实现的那个⽬标。即：实现。
那么⾸先我们来快速浏览⼀下TPOT库（Tree-based Pipeline Optimisation Technique，树形传递优化技术），该库基于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（数据集地址：
datahack.analyticsvidhya/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
ics 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'] = 0
combi = 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,

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。