楼上说了很多了，只举个没提到的例子。感觉这个例子更容易懂。
大学时搞过一个机器学习机器人，用的就是神经网络+遗传算法。
假设你要做一个机器人，目的是自动盯紧另一个乱串的机器人并想办法抓住他。你的输入是各种传感器读数，你的输出是轮子马达的转速（左右可以速率不同实现转向）。
设计一个简单的神经网络（图片来自网络），
但是权值是什么才能达到目的呢？需要training。我们就用遗传算法。
你可以开始random一组权值，测试一下能不能抓到？然后再random一组权值，测试一下能不能抓到？即使抓不到，是不是离对方很近？（就是楼上提到的fitness function评估）。
把评估结果好的留下，不好的扔掉，然后交叉繁殖。即一部分权值取爸爸的，另一部分权值取妈妈的，看看小孩结果怎样？
最后，还要有变异，因为不变异，只靠random一些解来进行交叉繁殖，是很容易近亲繁殖只找到次优解。变异就是某些权值（随机一下）突然变了，不再继承爸爸妈妈了。
经过若干轮的遗传+变异之后呢，你确实可以看到机器人在不同地形会演化出各种策略抓捕哦，例如绕圈从旁边绕到前面抓捕，等等。
本次回答将引用腾讯高级工程师tracyyma在腾讯内部发表的一篇原创文章。
内容索引
· Chapter 1 算法简介
· Chapter 2 算法应用
· Chapter 3 算法原理
· Chapter 4 实例说明
Chapter 1 遗传算法的简介
说到遗传算法，貌似很复杂呢，是不是跟生物遗传有关呢？没错，遗传算法就是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程以求得最优解。
遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似最优解的方案，在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原来个体更能适应环境，就像自然界中的改造一样。
Chapter 2 遗传算法的应用场景
需求拉到消费嘛，笔者以前接触过这个算法早在学校还给老师了，之所以想在此记下，主要是同事提出了一个问题:能否根据一堆变量的数据来预测一个变量，简单地说，"能给出一个公式吗，让我用用"，想想貌似这比较接近一个优化问题，可以用遗传编程来解决。没错，是遗传编程，它是遗传算法的一个沿伸，下章会具体介绍这个算法。本章先打基础。当然另一个原因还是由于笔者本人还是有点遗传学的工作背景的。
提出上一堆废话，无非就想引入一个问题：“优化问题”；遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。
比如：旅游航班优化问题、物流系统设计、生产调度、时间表安排等问题上。遗传算法的主要有以下八方面的应用：
（1）组合优化 （2）函数优化 （3）自动控制 （4）生产调度
（5）图像处理 （6）机器学习 （7）人工生命 （8）数据挖掘
Chapter 3 遗传算法的原理
说了这么多，重点就只有一个：达尔文、孟德尔，开个小玩笑，先来复习下我们高中课本，待会说应用。达尔文的进化论强调的是自然选择：适者生存，优胜劣汰；孟德尔种了八年豌豆，人家不也发现了遗传定理了吗？（基因的分离规律和基因的自由组合规律）；遗传算法就是模仿自然界的生物进化机制而来的，基础的遗传算法主要有三个算子：选择算子（自然选择，适者生存）、交叉算子（自由组合规律）、突变算子（适者生存）
先看一个大概的算法实现流程：
图1: 遗传算法原理
当然在算法中选择、交叉、变异算子可选择进行，也可交叉进行，也可顺序进行（蓝虚线）并无特别的要求。
所以遗传算法的组成可分为：
1） 编码
遗传算法（GA）通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。
正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串，基本遗传算法（SGA）使用二进制串进行编码。
2） 适应度函数
评价一个个体（解）的好坏程度，适应度函数是遗传算法进化过程的驱动力，也是
进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
3） 遗传算子（选择、交叉、变异）
选择算子：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是从父代群体中选取一些个体，遗传到下一代群体。
基本的遗传算法采用轮赌法进行，举个例子通谷易懂，有助于理解选择算子。其基本的思想是各个个体被选中的概率与其适应度函数值大小成正比。
轮盘赌选择法可用如下过程模拟来实现：
交叉算子
交叉运算，是指对两个相互配对的染色体依据交叉概率PC按某种方式相互交换其部分基因，从而形成两个新的个体。基本的遗传算法采用单点交叉。如下所示
是不是很像染色体重排（chromosomal rearrangement）呢！
变异算子
变异运算，是指改变个体编码串中的某些基因值，从而形成新的个体。决定遗传算法的局部搜索能力，保持种群多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。基本遗传算法（SGA）中变异算子采用基本位变异算子。
基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。
对于二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则将其变为1；反之，若原有基因值为1，则将其变为0 。
4) 运行参数
① M：种群规模
② T：遗传运算的终止进化代数
③ PC：交叉概率
④ PM：变异概率
Chapter 4 实例原理
Ok,现在可以完整用一例实例来具体阐述下遗传算法。
既然上述有轮盘赌的方法，那么还是应用上述是简单一个实例：求解目标函数
http://pic1.zhimg.com/50/v2-3c40829a650f96ab57be6975d78f8601_hd.jpg?source=1940ef5c。例子很简单但最实效。
初始化种群为
1 genetation：
2 genetation：
3 genetation：
4 genetation：
……
直到其中一代出现了近似最大值1.57
ok, 基本完成。
搜索关注公众号「云加社区」，第一时间获取技术干货，关注后回复1024 送你一份技术课程大礼包！
2020年6月更新：
大概整理了一下，如下：
李是Lyapunov的李：科学与艺术的融合：遗传算法绘制蒙娜丽莎楼上 @尼布甲尼撒 提到了科学松鼠会的文章，我在18年的时候用MATLAB复现了这个内容，进化出的蒙娜丽莎就是我知乎的头像。
如果有人感兴趣，我再来补充代码细节吧。。。陈年资料，需要去整理一下。
想学习遗传算法或者其他智能控制的，可以看看我的这篇回答，推荐几本书籍和资源。
想问一下有没有大佬推荐一下遗传算法及python实现的相关资料或者书籍的呀？
补充几个关于遗传算法的说明：
现实问题转换到遗传算法是一个难点，也就是现实问题的解如何映射到遗传算法的个体上，完成了这一步，后面的三个算子操作就按部就班了（也要根据实际问题做调整）。将现实问题的解映射到遗传算法中的个体之后，接下来就要确定一个评估函数（也叫适应度函数），这个评估函数能够定量地评估某个个体的好坏，从而指导整个进化过程朝着使群体适应度增加的方向进化，这样一来，最终的群体中才会有较优解。遗传算法中最重要的就是几个算子，包括选择算子，交叉算子，变异算子，每一种算子在解决问题的时候都需要根据实际情况仔细考究，比如交叉算子是单点还是双点，交叉点怎么确定？选择算子中是轮盘赌选择还是锦标赛选择？这些算子是遗传算法最重要的地方。而前面所说的适应度函数也在这里使用，怎么使用呢，简单地说，就是适应度大的个体更有机会把基因遗传给下一代，注意，这里说的是更有机会，也就是说适应度小的个体基因也有一定机会往下一代遗传，避免了出现寻优只寻到局部最优的情况（如果适应度小的没有任何机会，那么寻优过程就变成了爬坡，爬到一个山头发现还有一个更高的山头，但这个时候已经下不去了，详细过程看下文吧）。遗传算法中有很多参数，比如说初始种群的数量，交叉概率，变异概率，进化代数等等，这些参数影响算法的收敛速度和收敛值。遗传算法是一种仿生算法，类似这样的算法还有粒子群和蚁群算法，这类算法得益于自然界现象的启发，而不是像确定性算法那样的数学论证。
------------以下是原答案------------
通俗地讲，遗传算法是一种最优化方法，很多书上介绍说，它是一种“软”算法，软算法是相对于严格，确定，精确的硬算法而言的，显然遗传算法这种模拟自然界进化行为的计算属于“软”计算，扯远了，既然遗传算法是一种求解最优化问题的方法，那么本质上，它是一种寻优算法，下面讲一个例子，来说明它的寻优过程。
这个例子来自《复杂》这本书，书中讲了一个大概，我用C语言实现了一遍这个例子，加上了我自己的理解，可能更好懂些。
我现在有一个叫做罗比的机器人，它的世界是二维的，你可以把它的世界想象成一个M乘以N的网格，它的世界里到处是废易拉罐，这些废易拉罐的分布完全是随机的，我现在要为它寻求一个策略，让它去清扫这些易拉罐，而且是快速有效地清理。
上图是罗比世界的示意图，图中散乱放着易拉罐，当然，只是示意图，M和 N 可以随意指定。我们假设它的世界周围是高高的墙，每个格子里面的易拉罐不多于１个，罗比本身并不是很聪明，也看不远，它只能看到自己当前所在的格子和它周围的四个格子，显然，每个格子有三种状态：空的，有一个易拉罐，墙壁。比如罗比现在看到它的东边有易拉罐，北边和西边是墙，南边的格子是空的。每次罗比的动作我们规定有以下几种：
[*]向北移动
[*]向东移动
[*]向南移动
[*]向西移动
[*]随机移动
[*]不动收集罐子
为它设计了如下的计分规则：
[*]如果当前格子中有罐子而且清理了，加 10 分。
[*]如果当前格子中没有罐子却执行清理的动作，扣 1 分。如果撞到了墙，扣 5 分，并且弹回原来的格子。
当然，罗比尽可能多捡罐子，不要撞墙，没罐子的时候别去捡，得到的分数就会越多。显然，这个问题是一个最优化问题，我们的目标是让罗比取得最高的分数，问题本身也比较简单，一个M乘以N的网格，网格中随机地放上易拉罐，罗比有固定的几种动作，制定好计分规则，问题是：寻求一个最佳策略，在这个策略下，罗比能够快速地取得高分。
这个最佳策略就是我们要的最优解，用遗传算法解决问题的第一步就是确定进化的个体是什么，这里的个体对应于问题的解，正如有的个体好，有的个体差一样，解也是有好有坏，我们的目的是找到一个最优解，类似于遗传进化中的优胜劣汰，我们需要的就是遗传算法给出的那个最优个体（这里不严谨，其实应该是较优个体，只保证全局较优）。
接下来我们就来确定要进化的个体到底是什么，这里的个体对应于问题的某个解，即罗比的一个策略，在这里，定义罗比的策略是K-V 形式的映射关系，其中的键是罗比当前的情况，值是罗比应该执行的动作。简单点说，就是什么情况下应该做什么动作（动作是有限的，只有七种）。
我们把每个格子的三种状态映射到整数（每个格子只有三种状态）:
[*]空 --> 0
[*]有罐子 --> 1墙壁 --> 2
把罗比可以执行的动作也映射到整数:
[*]向北移动 --> 0
[*]向东移动 --> 1
[*]向南移动 --> 2
[*]向西移动 --> 3
[*]随机移动 --> 4
[*]不动 --> 5收集罐子 --> 6
给定顺序：[北，东，南，西，中]，那么罗比在最开始那副图中的“情况”就是 [ 2 , 1 , 0 , 2 , 0 ] ,这个“情况”对应于前面说的那个“K”，很显然，现在它应该向东移动，那么这个键对应的值就是 1（V），（好的策略是这样，坏的策略可能面对这样的情况偏偏要罗比撞墙）。
我们得对“情况”，也就是K进行数值化，对该情况下采取的"动作"（V）也得数值化，这样才能计算。
先考虑罗比所处的“情况”都有哪些，包括罗比自己当前的格子，共有五个方向，每个方向又有三种可能的状态，那么，情况一共就有 3×3×3×3×3＝243 种（当然一些情况是不可能的，比如罗比当前的位置是墙，不过程序员都很懒，不想费劲找出所有不可能的情况，我们只要知道就行了）。
那么一个策略就是 243 个键值对，这个 键值表(策略表) 就是我们的策略，应该说是罗比的策略，每次罗比只要抬头四周望望（确定自身所处情况），然后根据自己当前的情况到策略表中找对应的动作（根据K查找键值表中的V），然后执行对应的动作（V），然后再抬头望望，判断一下自身情况，从策略表中找到对应的动作，然后执行，下一次再这样，它就可以根据这个策略来进行游走了。显然，好的策略表让它有高分，坏的策略表只会让它乱走，撞得头破血流，还捡不着罐子。
我们还可以把键的顺序按照一定的原则固定下来，那么只要有一个值的列表就可以了（键的位置即是索引），罗比会知道当前的情况是情况几（确定索引），然后直接查对应的值去执行动作就行，这样一来，罗比的策略就是一个有243个元素的一维数组，比如说下面的这个是它的一个策略:
可是这样的策略有多少种呢？一共有 https://www.zhihu.com/equation?tex=7%5E%7B243%7D种（243个元素，每个元素都有7种可能的取值），是个很大的数字，这也说明了我们的解空间是很大的，注意，这么多策略中可能90% 以上都是糟糕的策略，比如说罗比现在的北边是墙壁，某一个策略让它向北移动，那好，它一头撞在墙上，所以我们的目的是为罗比找出最优的策略，让它的得分尽可能地多。
如何在这么多解中找到一个较优解，是遗传算法要做的事情。
下面来介绍一下大致思路，其实为罗比寻找最佳策略的过程就是一个进化的过程，你可以想象有一个种群，这个种群中有若干个个体，每个个体代表一个策略，其实前面我们说每个策略表示为一个长度为243 的数组，这个就是编码的过程，一个这样的数组就是一个个体。不同的问题有不同的编码方式，比较多的是二进制编码，不过我们这里更加适合字符串编码方式，编码完成之后，我们让这个种群按照适者生存，物竞天择的原则进行进化，最后进化到一定的代数之后，剩下来的就是那些比较优秀的个体，也就是那些比较好的策略，从最后一代中选出一个最好的个体，OK ,这个就是我们为罗比找到的好策略。
主函数中关键的就三行，选择，重组，变异
void main()
{
//随机生成解
int solu;
init_solu(solu);
int i;
double fit;
//最初的解
get_fitness(solu,fit);
printf("当前的最高分数为:%f",max(fit,POP_SIZE));
printf("\n计算中........\n");
//进化
for(i = 0; i < GEN_NUM;i++)
{
ga_sel(solu);//选择
ga_cross(solu);//交叉重组
ga_mut(solu);//变异
}
//进化完毕，输出最终的解
get_fitness(solu,fit);
printf(&#34;最终的最高分数为:%f&#34;,max(fit,POP_SIZE));
printf(&#34;\n&#34;);
}
这里面有几个关键的地方：
[*]每个个体怎么表示？
[*]如何度量一个个体的优劣程度？
[*]种群如何不断选择，重组，变异?
问题一：个体和种群的表示
对于第一个问题，其实对应于遗传算法中的编码过程，也就是将现实问题的解对应到程序中的具体表示，上文中说道我们可以把罗比所能碰到的所有情形和该情形下执行的动作当成一个键值表，那么在这里，问题的一个解就是一张键值表，而这个键值表在程序中我们可以很方便的表示，为了更方便一些，我们把键出现的顺序固定下来，那么只要用一个长度为243的一维数组就可以表示了，索引表示情形(可以把每种情形映射到一个0到242的整数，下文会讲到)，数组的值表示该情形下罗比该执行的动作(前文中已经编号，0到6)，于是我们就可以用一个一维数组表示一个解，也就是一个策略，即一个个体，假定种群包含200个个体（200个策略，即200张键值表），我们设定种群的大小为 200 ，那么这个种群就可以用一个 200×243 的矩阵来表示，就像下面这样：
其中，每一行表示一个个体，这个矩阵表示的是一个有 200 个个体的种群。
下面说一下某一种情形如何映射到一个0~242的整数。
罗比所面对的某一种情形类似下面的形式：
[*]北 –> 墙壁(2)
[*]东 –> 易拉罐(1)
[*]南 –> 空(0)
[*]西 –> 墙壁(2)
[*]中 –> 空(0)
第一列是方位，第二列是此处的状态，这种情形对应的表示就是21020，我们可以把这个数字当做三进制的数，因为每一位都有三种取值，这种情形对应的十进制值就是:
https://www.zhihu.com/equation?tex=2%5Ctimes3%7B%5E4%7D+%2B+1%5Ctimes3%7B%5E3%7D+%2B+0%5Ctimes3%7B%5E2%7D+%2B+2%5Ctimes3%7B%5E1%7D+%2B+0%5Ctimes3%7B%5E0%7D+%3D+195
按照这种编码方式，第1种情形到第243种情形都可以用一个0到242之间的整数表示，而且顺序是唯一的，那么具体情形到整数之间的映射就完成了，我们可以用这个整数值作为数组的索引，而罗比也可以根据自己面对的情形知道其所对应的编号，立刻得到对应索引位处的整数，即动作编号，然后执行相应的动作。
下面代码用来生成一个初始种群：
/**生成初始解**/
void init_solu(int solu[])
{
int i,j;
for(i = 0;i < POP_SIZE;i++)
for(j = 0;j < SOLU_DIM;j++)
solu = m_round(rand_zo()*6);
}
顺便说下罗比的模拟世界，我们用一个二维数组生成罗比的网格世界，然后为它建好墙壁，撒上易拉罐。
void init_world(int world[],double p)
{
int i,j;
//初始每个格子为空，用０表示
for(i = 0;i < ROW;i++)
for(j = 0;j < COL;j++)
world = 0;
//放置墙壁,2代表墙壁
for(i = 0;i < ROW;i++)
{
world = 2;
world = 2;
world = 2;
world = 2;
}
//放置易拉罐
for(i = 1;i < ROW - 1;i++)
for(j = 1;j < COL - 1;j++)
if(rand_zo()<p)
world = 1;
}
该函数接收一个二维数组和概率 p ,以这个概率在罗比的世界里放置易拉罐。
问题二：度量个体的优劣程度 对于每一个个体(策略)，我们让罗比采用这个策略去清理 100 次，在每次清理过程中执行200次动作，每次清理都有一个得分，取这100 次的平均成绩作为它的最终得分，注意，100 次清理，每次清理的世界都不同(每次随机放置易拉罐) , 这样，我们就大致衡量出了每个个体的好坏。
在代码中，这个评价函数接受一个种群，也就是200 个个体，然后返回一个长度为 200的得分数组，里面的元素对应每一个个体的分数，也叫做它的适应度，为了使适应度都为正值(因为后面要求和算比率), 我给每个个体的最终得分加上了最低得分的相反数，那么每个个体的得分区间就是。
/**适应度**/
void get_fitness(int solu[],double fitness[])
{
int i,j;
int ST; //每个个体对应一张策略表
for(i = 0; i < POP_SIZE;i++)
{
for(j = 0;j < SOLU_DIM;j++)
ST = solu;
double per_sum = 0;
/*对于每一个个体，给它CL_TIMES机会打扫,取平均成绩做为它的适应度分数,每一次的世界都不同，但是策略表相同*/
for(j = 0;j < CL_TIMES;j++)
{
int wor;
init_world(wor,P);
per_sum += do_clean(wor,ST);
}
//保证适应度是正数
fitness = per_sum/CL_TIMES + 5*PER_DO_TIMES;
}
}
这段代码中用到了一个函数do_clean()，这个函数用来模拟罗比清理的过程，它接收一个脏乱的世界和一个清扫策略，然后罗比按照这个清扫策略执行动作200次，返回这一次清扫过程的得分，下面是具体过程：
/**根据策略表ST,执行清扫动作,返回对应的分数**/
double do_clean(int wor[],int ST[])
{
//约定：可以执行的动作有：
// 向北移动 ０
// 向东移动 １
// 向南移动 ２
// 向西移动 ３
// 随机移动 ４
// 不动 ５
// 清理罐子 ６
//计分规则：
// 如果罗比所在的格子中有罐子，并且打扫了罐子，+10分
// 如果执行打扫的动作而当前格子中没有罐子, -1分
// 如果撞到了墙，-5分，并且弹回原来的格子
//从左上角开始打扫
int pos = {1,1};
double sc = 0;
int i;
for(i = 0; i < PER_DO_TIMES;i++)
{
// 得到当前位置的情况
int situ;
situ = wor - 1]];
situ = wor] + 1];
situ = wor + 1]];
situ = wor] - 1];
situ = wor]];
// 得到此情况下的策略编号
int str_num = get_stra(situ);
// 按照此策略进行行动，并对wor和sc进行对应更新
int dire;
int rand_num;
switch(ST)
{
case 0:
//向北移动
N:
if(move(pos,pos,0))
sc -= 5;
else
pos--;
break;
case 1:
//向东移动
E:
if(move(pos,pos,1))
sc -= 5;
else
pos++;
break;
case 2:
//向南移动
S:
if(move(pos,pos,2))
sc -= 5;
else
pos++;
break;
case 3:
//向西移动
W:
if(move(pos,pos,3))
sc -= 5;
else
pos--;
break;
case 4:
//随机移动
rand_num = rand_zo();
if(rand_num < 0.25)
goto N;
else if(rand_num < 0.50)
goto E;
else if(rand_num < 0.75)
goto S;
else
goto W;
break;
case 5:
//不动
break;
case 6:
//清理罐子
if(wor]] == 1)
sc += 10;
else
sc -= 1;
break;
}
}
return sc;
}
问题三：进化过程
现在到了最有趣的地方，就是种群如何进行选择,重组,变异，我们一个一个来说。
选择
选择，顾名思义，就是从种群中选择一批比较优良的个体，让它进行繁殖，而判断某个个体是否优良自然就是看这个个体在评估函数下的得分高低，这里我们使用比较简单的轮盘赌的方式来选择个体，想象有下面这个轮盘：
每个部分的面积不同，如果有一根指针，你旋转这个轮盘，当然指针落在面积大的那一块上的概率会大些，注意，这里是概率，具有更高适应度的个体仅仅是有比较大的概率被选中，这就保证了算法具有一定的随机性，一定程度上避免落入局部最优解，因为那些适应度不高的个体也有机会被选中，而你不能说这些适应度不高的个体就没有好的基因片段遗传给下一代，但是从总体上来讲，适应度高的个体更多的机会把自己的基因遗传给下一代。在代码中，我们先计算出每个个体的被选概率，概率之和是1,然后计算累计概率，进行选择，关于为什么计算累计概率，这仅仅是种实现上的技巧，只要能够按照轮盘赌的原则进行选择就可以了，选择的结果是一个新的种群，新的种群的大小和原来的种群大小是相同的，但是已经发生了变化，因为一些适应度高的个体可能被多次选中，有一些适应度很低的个体可能一次都没有被选中，也就是被淘汰了，下面是选择的具体过程：
//选择算子
void ga_sel(int old_pop[])
{
int new_pop;
double pr,cum_pr;
double pr_sum = 0;
int i,j,k;
//计算每个个体的适应度
get_fitness(old_pop,pr);
//计算累计概率
for(i = 0;i < POP_SIZE;i++)
pr_sum += pr;
for(i = 0;i < POP_SIZE;i++)
pr = pr/pr_sum;
cum_pr = pr;
for(i = 1;i < POP_SIZE;i++)
cum_pr = cum_pr + pr;
//轮盘赌方法选择
for(i = 0;i < POP_SIZE;i++)
{
double rand_n = rand_zo();
for(j = 0; j < POP_SIZE - 1;j++)
{
if(rand_n < cum_pr)
{
for(k = 0;k < SOLU_DIM;k++)
new_pop = old_pop;
break;
}else if(rand_n >= cum_pr && rand_n <= cum_pr)
{
for(k = 0;k < SOLU_DIM;k++)
new_pop = old_pop;
break;
}
}
}
for(i = 0;i < POP_SIZE;i++)
for(j = 0;j < SOLU_DIM;j++)
old_pop = new_pop;
}
重组(交叉)
现在我们进入基因重组这个步骤，基因重组的概念不用多说，我们把上一步骤中选择出来的个体，以一定的概率P_CROSS进行基因重组，提一句，这个程序的有很多参数，比如说种群大小，度量适应度时罗比清理的次数，每次清理中执行的动作次数，基因重组的概率，基因变异的概率，进化的代数，网格世界的大小，这些参数是可以适当调节的，对算法的收敛速度和收敛值会有影响。回到正题，在选择出一批个体之后（这些个体有向下一代传递基因的权利），让他们两两之间进行交叉（啪啪啪），啪啪啪的结果当然就是产生了新的个体。交叉算子的具体操作有很多种，这里我们还是选择比较简单的单点交叉，如图所示
图中是以二进制来编码的，采用单点交叉，它很好地说明了单点交叉的过程。下面是代码中的交叉过程
//交叉
void ga_cross(int new_pop[])
{
//选择需要交叉的个体
int count = 0;
int need_cr;
int i,j;
int temp;
for(i = 0;i < POP_SIZE;i++)
if(rand_zo() < P_CROSS)
{
need_cr = i;
count++;
}
if(count % 2 != 0)
count++;
//随机决定一个不为0的交叉点
int cr_point = 0;
while(cr_point == 0)
cr_point = m_round(rand_zo()*SOLU_DIM);
//进行交叉
for(i = 0;i < count;i+=2 )
for(j = cr_point;j < SOLU_DIM;j++)
{
temp = new_pop];
new_pop] = new_pop];
new_pop] = temp;
}
}
变异
正如自然界中的个体一样，我们的进化过程也要考虑到变异的情况，与前面两个过程不同的是，变异针对的是某个基因，比如说我们的种群大小是200，每个个体有243个基因，那么这个种群的基因总数就是200×243，每一个基因都有变异的可能性，当然这个可能性通常来说是比较小的（就像自然界中的变异也不常发生一样），在这里我们给定每个基因变异的概率是0.005，下面是变异的具体过程
/***变异**/
void ga_mut(int pop[])
{
int ge_sum = POP_SIZE*SOLU_DIM;
int i,j,k;
for(i = 0; i < ge_sum;i++)
{
if(rand_zo() < P_MUT)
{
//定位此基因所在的染色体,此处，染色体即个体，下同
int chr_loc;
chr_loc = i/SOLU_DIM;
//定位此基因所在染色体上的基因位
int gen_loc;
gen_loc = i%SOLU_DIM;
//进行变异
pop = m_round(rand_zo()*6);
}
}
}
至此，种群完成了第一次进化，选择，交叉，变异，我们设定让此种群进化1000代，最终幸存下来的个体就是我们所要找的好策略。
C语言运行的结果说一下，如果这个网格的大小是30×30，其中易拉罐的比例设在0.5,每次让罗比行动200步，那么，这个游戏的满分就是2000分，我自己事先按照我觉得比较好的策略给罗比用，就是向有罐子的地方移动，有罐子就捡起来，不要撞墙，罗比按照这个策略清理1000次，每次罐子的分布都随机，平均得分是1210分，遗传算法进化出来的策略平均得分是1992分，完整代码需要的话请留言，可以运行试一试。
可以看看《复杂》一书，里面有关于遗传算法的介绍。
本文作者：颀周，版权归原作者所有，如需转载请联系作者。
原文链接：https://www.cnblogs.com/qizhou/p/13381474.html遗传算法（Genetic Algorithm, GA）是一种通用的优化算法，属于进化算法簇中一个比较实用又有名的算法。进化算法融合了自然生物进化中共有的一些行为：繁殖、变异、竞争、选择等。
基本流程
GA通过迭代来优化目标函数的参数，直到目标函数满足一定条件时结束。迭代对目标函数的连续性并无要求，也就是说算法的迭代并不基于目标函数在当前参数下的梯度等连续性质。算法的转化思想是将所有待优化参数看做生物染色体，单个参数看做染色体上对应位置的基因，而目标函数看做生物对生存环境的适应度。大致的迭代流程如下：
0、随机生成一定数量的生物个体，它们的染色体各不相同，因此在生存环境中的适应度也不同。也就是说，这些随机生成的参数对目标函数的满足度各不相同。
1、根据个体对环境的适应度，适者生存。选择适应度较高的一部分个体，生存下来，有资格繁殖下一代，剩下的都死在这一代。当然这里也可以随机少量选择一些“幸运”的适应度较低的个体，让它们也能参与繁殖，增加多样性。
2、对选出的个体进行两两“交配”，交配就是让它们DNA中对应位置的基因进行交叉和变异产生新的个体（不知道交叉和变异的回去读高中生物书），得到下一代。具体的交配和交叉变异策略下面再详细介绍。
3、在新的一代，对所有个体进行判断，是否已经有个体满足目标函数的终极条件。有就结束迭代，否则回到1。
算法基本概念
串：表示生物个体的染色体，通常是二进制串，或根据优化需要使用其它形式的串。群体和群体大小：个体的集合称为群体，串是群体的元素。群体中个体的数量称为群体大小。基因：基因是串中的元素，用来表示个体特征。通常一个基因对应一个参数，或者在二进制编码时，一位就代表一个基因。基因位置：基因在串中的位置，简称基因位。串结构空间：基因任意组合所形成的串集合，也就是在当前优化背景下所有可能的串的集合。适应度：表示某一个体对环境的适应程度，用一个函数表示，通常就是待优化的目标函数。
算法组成部分
介绍完GA的大致流程和基本概念，你应该对其有了个大致了解。下面开始详细讲解算法的各个组成部分，由四个部分组成：编码机制、适应度函数、控制参数、遗传算子。
编码机制
待优化的参数可以编码为各种形式的串，以便进行上述的遗传迭代。编码要是可逆的，也就是说串与参数之间应该是一一对应的，从而每次迭代都能解码并计算个体的适应度。并且GA的编码可以有个十分广泛的理解，不局限于简介中对待优化参数的编码。比如，在分类问题，串可解释为一个规则，即串的前半部为输入或前件，后半部为输出或后件、结论。因此，遗传算法可以对大量的问题进行建模，只要把问题的条件啊，约束啊，参数啊全都一股脑地编码丢进去“进化”就好了，这也是为什么它在数学建模比赛中如此热门的原因。
编码方式有二进制编码、格雷编码、实数编码等。二进制编码就是把参数都转换为二进制，然后排成一排，编码的每一位都看做一个基因。实数编码实际上就是不编码，当参数都为实数而且很多时，就可以直接把这些实数参数作为染色体基因。下面介绍格雷码。
格雷编码
格雷编码是对二进制编码进行变换后所得到的一种编码方法，它要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的。因此，格雷码解决了二进制编码的汉明悬崖问题。二进制编码与格雷码之间的转换如下：
设有二进制串$b_1,b_2,...,b_n$，对应的格雷串为$a_1,a_2,…,a_n$，则从二进制编码到格雷编码的变换为：
$ a_i = \left\{ \begin{aligned} &b_i,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;i=1\\ &b_{i-1}\oplus b_i,\;\;\;\;i>1 \end{aligned} \right. $
其中$\oplus$为异或运算。格雷码到二进制编码的变换为：
$b_i = (\sum\limits_{j=1}^ia_i)mod\; 2$
尽管转换式子有了，但是这样看不出格雷码的特点，下面通过列举格雷码来总结它的特点。
可以发现，格雷码每增加一位，低位（仅除了最高位外）编码即为所有位数少于它的格雷码的反序排列。比如上面的四位格雷码，低三位分别是100、101、111、110、010、011、001、000，观察小于四位的格雷码，从7到0，格雷码同样也是100、101、111、110、010、011、001、000。
适应度函数
适应度函数用于判断个体对环境的适应度、评估个体，定出优劣程度。
原始适应度函数直接将待求解问题的目标函数$f(x)$定义为算法的适应度函数。比如求解极值问题
$\max\limits_{x\in }f(x)$
直接将$f(x)$作为原始适应度函数。
还有其他的定义方式，但是因为对于不同问题，定义方式各不相同，所以不再举例，只要适应度函数是向着优化目标定义的即可（物种适应度越大，越接近你的优化目标）。
控制参数
在GA的实际操作时，需适当确定某些参数的值以提高选优的效果。这些参数包含：
字符串所含字符的个数，即串长。这一长度为常数，记为$L$。每一代群体的大小，也称群体的容量，记为$n$。交换率，即施行交换算子的概率，记为$P_c$。突变率，即施行突变算子的概率，记为$P_m$。
遗传算子
遗传算子就是执行选择、交叉、变异等操作的方法。GA中最常用的算子有三种：选择算子、交叉算子、变异算子。
选择算子
选择算子从群体中按某一概率成对选择个体，某个体$x_i$被选择的概率$P_i$与其适应度值成正比。最通常的实现方法是轮盘赌型。
所谓轮盘赌，就是根据适应度函数来确定个体被选择的概率。如果适应度函数$f(x)>0$，则可以这样定义：
$\displaystyle P(x_i) = \frac{f(x_i)}{\sum\limits_{j=1}^Nf(x_j)}$
否则定义成softmax也行（我觉得）：
$\displaystyle P(x_i) = \frac{\exp f(x_i)}{\sum\limits_{j=1}^N\exp f(x_j)}$
然后根据概率选择个体。这就是最简单的概率选择，不知道为什么要扯出一个所谓轮盘赌来，是怕别人理解不了吗。
交叉算子
交叉算子将被选中的两个个体的基因链按概率$P_c$进行交叉，生成两个新的个体。其中$P_c$是一个系统参数，通常看群体的大小，群体越小，$P_c$可以取得更大一些，但一般小于0.5。这是因为大于0.5等于把大部分基因都交换了，而这和交换剩余的小部分基因等价。具体来说，交叉有所谓的单点交叉、两点交叉、多点交叉、均匀交叉等。这些分类感觉没有任何意义，直接就按$P_c$进行交叉就行了。过程如下：
首先生成长度为$L$的二进制模板串，其中每位为1的概率为$P_c$。然后按照这个串对选择出来的两个父串进行交叉，为1的位置交叉，为0不交叉。比如对于两个父串
$X = 1011010$
$Y = 1101001$
模板串为
$T = 0101010$
则交叉后变为
$X&#39;=1111000$
$Y&#39;=1001011$
变异算子
变异算子将新个体的基因链的各位按概率$P_m$进行变异，$P_m$通常取得很小比如0.0001。对二值基因链(0,1编码)来说即是取反，对于实数基因来说，则可以在这个数的范围内取随机值，或是在某个固定范围内取随机值。另外，还可以进行基因之间的数字的调换、循环移动等。
总结
以上这些操作对于具体的优化任务而言，并没有什么原理可以讲解，也没有理论依据表明交叉和变异的确可以让个体更优。但是从宏观上来看，群体的适应度的确会在选择操作下不断向好发展，最终达到一个良好的点。归根结底，我认为这个算法就是在保持当前较好结果的前提下的随机迭代。它是十分随机的，有时可能迭代几步就搞定了，而有时可能几千步都出不来，所以会浪费大量的计算资源。而且对于很复杂的非凸问题，它同样也可能会陷入局部最优。所以能用传统方法求解的问题，尽量不用这种启发式算法。
实验
实验使用遗传算法求解以下函数的最大值：
$f(x,y) = 2\exp\left[\frac{-(x+3)^2-(y-3)^2}{10}\right] + 1.2\exp\left[\frac{-(x-3)^2-(y+3)^2}{10}\right] + \frac{1}{5}\exp\left[-\cos(3x)-\sin(3y)\right]$
$x,y$的范围都是$(-100,100)$，函数三维图像如下：
看表达式和图像可以判断最大值在$(-3,3)$附近。下面先以均匀分布产生1000个点，然后进行40次迭代。1000个点的迭代过程如下：
每次迭代的最大值和坐标：
这里交叉率是0.2，变异率是0.3，变异使用的正态分布标准差是10，因此比较容易跳出这个函数的局部最优点。比如函数在$(3,-3)$附近的局部最优点，这点和$(-3,3)$之间差了$6\sqrt{2}$左右，刚好是10左右。另外，在$100\times 100$的范围内，把种群的大小设置为1000实际上过于饱和了，随随便便就找到了最优解，这和直接网格暴力搜索都有的一拼了。现在把种群大小调为200，变异标准差调为20，交叉率调为0.4，变异率调为0.1，看看迭代几次可以达到最优。以下是迭代过程图：
迭代了150次，也到了$(-3,3)$附近，时间上消耗少了一些。如果要再精确可能还要更多次的迭代，但因为它的变异方差较大，所以比较难。
以下是实验代码：
#%%定义函数
import time
import numpy as np
def func(X,Y):
return np.exp((-(X+3)**2-(Y-3)**2)/10)*2 + np.exp((-(X-3)**2-(Y+3)**2)/10)*1.2 + np.exp(-np.cos(X*3)-np.sin(Y*3))/5
#%%遗传算法
time_start=time.time()
dim = 2
iterate_times = 150
individual_n = 200
p_c = 0.4
p_m = 0.15
std_var = 20
num_range = [-100,100]
def initialize(individual_n,num_range):
return np.random.uniform(num_range,num_range,size = )
def overlapping(a,b,pc,dim):
T = np.random.choice(a=2, size=dim,p=)
for i in range(dim):
if T == 1:
a,b = b,a
def variation(a,pm,dim,num_range):
T = np.random.choice(a=2, size=dim,p=)
for i in range(dim):
if T == 1:
a = np.clip(np.random.normal(loc = a, scale=std_var),num_range,num_range)
def get_select_p(v):
exp_v = np.exp(v)
sum_exp_v = np.sum(exp_v)
return exp_v/sum_exp_v
def select_and_reproduction(population,num_range):
values = func(population[:,0],population[:,1])
select_p = get_select_p(values)
choices = np.random.choice(a=len(population), size=len(population), replace=True, p=select_p)
new_population = population
for i in range(int(len(new_population)/2)):
overlapping(new_population,new_population,p_c,dim)
variation(new_population,p_m,dim,num_range)
variation(new_population,p_m,dim,num_range)
argmax_value = np.argmax(values)
return values,population,new_population
population = initialize(individual_n,num_range)
times_population = np.empty()
max_value = 0
max_value_coordinate = []
for i in range(iterate_times):
times_population = population
last_max_value,last_max_value_pos,population = select_and_reproduction(population,num_range)
if last_max_value>max_value:
max_value = last_max_value
max_value_coordinate = last_max_value_pos
print(i,&#34;:&#34;,last_max_value)
time_end=time.time()
print(&#39;总共耗时：&#39;,time_end-time_start)
print(&#39;迭代最大值：&#39;,max_value)
print(&#39;对应坐标：&#39;,max_value_coordinate)
#%%画出种群的迭代过程
import matplotlib.pyplot as plt
import matplotlib.animation as animation
fig, ax = plt.subplots()
xdata, ydata = [], []
ln, = plt.plot([], [],&#39;ro&#39;,animated=True,color=&#39;black&#39;,markersize = 2)
def init():
ax.set_xlim(num_range,num_range)
ax.set_ylim(num_range,num_range)
ax.set_xlabel(&#39;X&#39;)
ax.set_ylabel(&#39;Y&#39;)
return ln,
def update(frame):
frame = int(frame)
xdata = times_population
ydata = times_population
ln.set_data(xdata, ydata)
return ln,
anim = animation.FuncAnimation(fig, update, frames=np.linspace(0,iterate_times-1,iterate_times),interval=100,
init_func=init,blit=True)
plt.show()
点击关注，第一时间了解华为云新鲜技术~
求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间的最大值。
既然高票提出了这样一个问题，那我在学习了遗传算法之后，也给了自己的解决方案，已经将代码贴在了自己的CSDN的博客上，希望大家共同交流。
其实大家可以在我的算法基础上加入精英机制，每次选择的时候必然留下一个最优解。
遗传算法（初步） - CSDN博客同时，如果用退火算法，也可以在较长时间里获得更优秀的答案，更加精确。
模拟退火算法（初步） - CSDN博客但是，如果用粒子群算法，就会很头疼，太容易局部收敛。不过我采取了一种方法，每当有鸟逃离边界的时候，就丢弃这只鸟并重新随机生成一只鸟。
粒子群算法（初步） - CSDN博客说到这里，是不是已经被智能算法弄得眼花缭乱了呢？这个时候，我们不妨来看看平易近人的一维搜索中的斐波拉契法和黄金分割法。基本只要20次以内，就找到了！难受不难受？
一维搜索（斐波拉契法和黄金分割法） - CSDN博客谢谢各位的观看。
我们可以通过自然界的遗传原理来理解遗传算法。
简单来说，遗传算法是一种随机搜索算法，主要目的是用来优化。和自然界的遗传一样，遗传算法秉持的是适者生存、优胜劣汰的原则。通过选择、交叉和变异，不断迭代出更优秀的解法。
通过编码，将解空间变成编码空间，从中选择当前较为优秀的解当作“父母”，下一步则是将多种解的特征进行交叉，诞生下一代，最后经过变异成为“子嗣”。如果“子嗣”还是不能符合要求，那就再进行一次上述步骤，直到满足要求。过程中，较差的基因就会一步步被淘汰。总之，这是一个枚举的过程。就像长颈鹿的进化一样，树叶长在高处，每一只鹿都去尝试吃树叶，只有符合“标准”的长颈鹿能够吃到食物、生存下来并诞生后代。
但要注意的是，这种算法很多时候不会给出一个“最优解”，而是给出一些较为接近的次优解，从矮子里面拔将军。
有一款非常有趣的小游戏——Boxcar 2D，可以帮你理解遗传算法：
这款游戏的主要内容是用几何图形和圆形的轮子组成小汽车，不断走过一条有上下波动的“路”，看什么形状的小车可以走得更远。但和大部分游戏不一样的是，不用玩家自己手动拼装小车，整个过程完全由算法自动进行，每次随机生成小车，卡到路上了就重新来过。最后小车会越走越远，整个过程中小车的形状会越来越合适，一开始可能只是个“独轮车”，到后期则会很接近我们生活中摩托车的样子。
动图来源：BoxCar 2D官网还可以通过实际场景中的应用来理解遗传算法的特点：
遗传算法可以解决调度类问题，比如确定车间工作流程、飞机航线等。它是将工程、航行中所需要的资源消耗、时间等权值看作“染色体”，几种染色体排列组合，最终选择其中的较优方案。机器人中也会用到遗传算法，尤其是快速定位、路径规划等。就像 Boxcar 这个游戏一样，机器人在仿真环境中不断尝试接近目标，路线的优越度随着路线的长度增加，结合机器人对自身位置的感知，最后得出较优解。遗传算法也可以被应用于帮助神经网络调整参数，只是这种方式需要的时间太长、运算量太大，属于性价比较低的参数调整方式。遗传算法可以用来增强游戏体验。很多游戏会有在同一场景面对多轮敌人的“生存模式”，在这一模式中，敌人的属性是会不断增强的，有了遗传算法，就可以根据你自身属性的变化不断改变敌人的属性，以增强游戏的难度。比如说你的法术强度高，敌人就会增加法术防御度；你的攻击穿透性高，敌人就会增加血量。这样一来相比直接增加属性，可以有更好的游戏体验。
其实，目前遗传算法已经慢慢淡出了主流算法舞台。虽然主旨是为了避开局部最优误区，为无限解集问题寻找答案，可在实际应用时相比梯度和蒙特卡洛算法都没有明显的差异和优势，常常被视作“玄学算法”。比如计算结果的稳定性差、求解过程没有可复制性等都是遗传算法的缺点。很长一段时间里，遗传算法都被看作只能用来凑论文的算法。不过理论也和技术一样，会随着实践和研究不断发展，神经网络也曾被打入冷宫。DeepMind还提出了把神经网络和遗传算法结合，应用到迁移学习中的案例。或许，有朝一日遗传算法还会重新进入我们的视野。
<hr/>内容选自《未来学徒 读懂人工智能飞驰时代》
欢迎关注 @人民邮电出版社 知乎机构号，更多计算机好书等你来读~
关于遗传算法，我们可以追溯到约翰·霍兰德和吃豆游戏，故事的大幕徐徐拉开。
本文故事来源：《卓老板聊科技》第二季第53期《用计算机模拟进化》
世界上第一位计算机科学专业的博士叫约翰·霍兰德，估计知道他的人不多，他是1959年在密歇根大学拿到的博士学位，全世界第一个正式的计算机系也是在密歇根大学建立的。他的导师是计算机工程师巴克斯，你看第一个计算机博士的导师却不是计算机博士，巴克斯曾经协助冯·诺依曼建造EDVAC，这台计算机是世界上第一台计算机ENIAC的改进版。
霍兰德被称为“遗传算法之父”，是最早研究复杂理论（Complexity）和非线性理论的科学家。这多亏了他手中有计算能力超强的工具，在他之前很多好想法都由于计算量过大被卡住了，因为像EDVAC和ENIAC最初设计的目的都是给国防部用来计算导弹弹道的。为什么霍兰德能在那个年代，这么早就能拿到计算机，用来研究非军事目的呢，别忘了，他的导师巴克斯就是搭建计算机EDVAC的，霍兰德理所当然的就近水楼台先得月了。
当时霍兰德研究的是进化策略，他的这篇开山之作叫《自然与人工系统中的适应》，霍兰德所研究的内容，可以简单的描述为吃豆游戏。
吃豆游戏的规则是这样的，有一个10*10的格子空间，边界是墙，在格子里随机撒下50颗豆子，然后随机位置放一个吃豆人，这个吃豆人的视野和活动能力都是有限的，他只能看到自己当前格子和自己前后左右4个格子的情况，而对于每一个格子有三种情况——空的、有豆子、墙（边界也可以看成是一排格子）。
吃豆人能做的动作有7种：上移、下移、左移、右移、不动、随机移动、吃豆。
然后规定一下吃豆人的收益和损失，吃到豆得10分，移动位置分数不变，执行吃豆的动作，但是格子里没有豆子，减1分，撞墙了减5分。限制吃豆人总共能做200次动作。理论上最高得分就是在不扣分的情况下把豆子全部吃掉，有50个豆子，最高得分就是500分。
吃豆人能观察到的，是前后左右和自己所在格子的状态。所以一共是5个格，每个格子有三种状态，总的状态数就是3的5次方，就是243种状态，然后在除去一些地图中不存在的状态（如三面是墙，左右是墙），最后总共剩下128种状态。
吃豆人根据当前状态，决定采取什么样的动作。用0-6，分别代表上移、下移、左移、右移、不动、随机移动、吃豆。这样就可以用一个128列的表格来保存当前状态和吃豆人动作之间的对应关系，这128列的表格就是这个吃豆人的生存策略。所以每个吃豆人，下一步应该怎么行动，按照当前状态查一下这个表格就可以知道了。
这个研究的目的就是要找到这个吃豆生存游戏中得分最高的吃豆策略是什么，这个策略就是指的这128列的表格，一共有多少种呢，每一位可以取0-6七个数，所以总共的策略组合就有7128种，如果用线性思维，把每个生成的策略组合都去试试看得分多少的话，把这些策略都执行完，也比整个宇宙的历史要长，所以这就是一个典型的计算量远远超过全球算力加和的计算任务。所以想要通过穷举法去计算，这个问题是无解的，但是遗传进化算法可以从另一个思路解决这个问题。
这个研究的实验步骤如下：
随机生成200个策略，就是生成了200个采用不同策略吃豆的人；
让每种策略都进行1000场吃豆挑战赛。每场比赛让吃豆人行动200次，在1000场挑战赛中，每场比赛的50个豆子都是随机撒下的。最后评估在这1000场挑战赛中，平均每走200步，得到的分数是多少；
根据得分的高低从200个策略里随机选出2个策略，得分越高被选中的概率越高。然后用所选中的2个策略，生成出一个新的策略，新的策略的每一列有一半概率使用第一个策略的对应列，一半概率使用第二个策略的对应列。在生成新策略的过程中，会有小概率产生策略的变异；
用第3步的方法不断生成新策略，直到生成了200个为止；
返回第2步，用新生成的策略进行比赛，再按照分数生成再下一代的策略；
按照上面的方法循环1000次，就是生成1000代吃豆人。第一代吃豆人的策略是随机生成的，在大规模的高频的比赛中，他们按照自己的策略来执行行动，因为场次多频率高，所以得分可以反映出他持有的策略是否有竞争力。评分最高500分，对应着把所有的豆子都吃光，也没有白做功，也没有撞墙。实验引入了进化的行为，把每个吃豆人策略列表中的每条策略看成基因一样，重组生成下一代的过程有点像染色体的分裂和组合，第一代成绩较高的吃豆人，就有更高的几率留下后代，后代还遗传了上一代的策略。得分低的也有几率生成后代，只是没有得分高的概率高。在生成下一代的过程中，下一代的策略还有非常低的几率产生遗传变异，有的策略位会随机变成其他数。
在当时，这个实验就受限于计算机的性能，不过现在算起来就容易多了。大概用了3个小时，生成了1000代吃豆人。每一代最优评分的吃豆人评分情况如下：
每一代全部吃豆人平均评分情况如下：
可以看到第一代策略随机生成的吃豆人的分情况非常差，最高评分是-95分，最低是-300多。因为策略是随机生成的，就会总出现撞墙、没有豆子时吃豆的这种被扣分的情况。但是这种情况在第19代就有了本质上的改观，从第19代开始子代的平均得分就已经超过0了，此后得分逐渐上升，但上升的速度越来越缓慢，第48代开始超过100，第175代超过200，第604代超过300，从第650代之后，得分超过了400，最后在第1000代的时候，上升到了470。我们可以看出那些差的、不合理的策略，被淘汰的速度非常的快。这些有重大错误的策略，在最开始的迭代中，就被淘汰掉了，剩下的都是稍稍有些竞争力的策略。
如果我们人为去制定策略，怎么制定呢，最简单的就是：当前格子有豆子就吃，旁边格子有豆子就移过去，都没有就随机走一步，像这种策略实际评分为346分。
到第1000代，最好的策略平均得分是471分，这个策略很难像上面我们自己制定策略那样用几条规则总结描述出来，它大致也有一些规律可循，也能观察到，当前格子里有豆，它可能会吃，旁边格子有豆，会移过去，但是它又时不时的不按这个规则来，比如当前格子和挨着的好几个格子都有豆子，这时它并不是直接把当前格子里的豆子吃掉，而是先向其他方向移，直到移动到没有豆子的格子，才开始吃它旁边的豆。这种吃豆的方式描述起来就不太容易，但是比我们之前自己定义的策略会少走不少弯路。另外在一直没有豆的情况，它会去找墙，然后沿着墙走，然后发现内圈有豆子就吃。
虽然能看出一些规律，但是想用线性的几条规则去描述这个策略还是基本上办不到的。想要描述这个策略还是的靠那个128条规则，每一种状态做什么动作来逐条来描述。这就是一个复杂系统，我们很难通过简单的思辨来理解和总结。通过这个例子也可以明白，一个复杂系统中的最优解，你想描述它，其实它的所有的行为就是你描述他的方法，想通过约化和简化的方式描述他，这种方式是徒劳的。
怎么去证明这个策略显示出来的一些特点，比如当前格子有豆子不去吃，是不是真的在吃豆游戏中是有优势的呢？可以这样去做：把这个策略中当前格子里有豆子状态的动作都改成吃豆，然后进行实验，结果这个策略的评分从471分下降到了456分。所以从这一点说明进化出来的这些基因还是有自己的优势的，这种实验方法在科学研究中有个名字叫基因敲除法。
这个就是用计算机来模拟进化过程的研究，它逐渐掀起了进化论的主流观点的改变，这种遗传算法将突变式的进化用计算机模拟出来了。进化是一个复杂过程，通过计算机在算法上做简单规定就能模拟出来，而且还能在7^128的可能性中，短时间找出最优解，这也给研究算法的科学家提供了一个新的思路。用遗传算法进化出来的那个最优解，往往是人类思维无法理解的，它还往往照顾到很多思维的死角。今年年初战胜李世石的AlphaGo，用的是深度神经网络，也有研究算法的人提出，如果采用遗传算法的方式，也能设计出一套围棋对弈的策略，同样可以战胜人类。
以上答案来自我厂吕默威老师的博文《吃豆游戏中的遗传算法 》
更多网易技术、产品、运营经验分享敬请关注网易社区知乎机构号：网易云 - 知乎
最近在整理参加数模的笔记，在知乎上写了专栏，第4期写了遗传算法的内容，引子中的内容很通俗易懂。
贴通俗易懂的内容部分上来吧！
这里是“上帝体验俱乐部”，现在俱乐部刚刚开张，快过来体验下当上帝的感觉吧！想知道怎么创造一个属于你的“世界”吗？想要制定这个“世界”的运作规则吗？不要888888，不要99999，只要你掌握了遗传算法（Genetic Algorithm），就可以自己体检一番，创造一个专属于你的“世界”！（“世界”理解为臆想中的另一个平行时空就可以了，下文同。）
在这里，我自己先来示范一下，作为创世主，我要创造一个寻找最快蜗牛的“世界”。
首先，身为造物主，我要先用泥巴捏出50个第1代蜗牛出来，让这些蜗牛进行第1届百米赛跑，把第1代蜗牛的最快成绩记录下来，当然还有对应的记录拥有者，把它推上现在的“最强者”王座，开启它的朝代。
通过第1届百米赛跑比赛之后，我要选择出一批蜗牛，也就是进行优胜劣汰，这里我选择50 次，选出50个蜗牛出来。当然每次选择中，跑得快的蜗牛被选择的机会要更多，跑得慢的蜗牛也稍微给一丢丢机会吧，也难保它们会生出个跑得快的蜗牛呢！这里允许重复选择，如果某个蜗牛被选择了3 次，后面的2 次我就用泥巴再捏个一模一样的出来。经过这样优胜劣汰，第1代蜗牛的数量还是维持在50 只，只不过可能淘汰了一批，新增了一批。
紧接着我考虑到它们成年了，需要交配产生下一代，希望在爱情的火花下，它们会生出跑得更快的蜗牛出来！当然交配的蜗牛的比例由我来控制，还是会有单身狗们的。交配过的蜗牛就可以退休了，让它们的孩子，也就是第2代蜗牛进行第2 届的百米赛跑。那些不幸运的单身狗们怎么办呢？我决定还是让他们继续跑着，让他们加入到第2代蜗牛竞争的行列！多说一句，这里我还是要把第2 代蜗牛的数量维持在50只。
第2代蜗牛逐渐长大，和他们的父母太像了，我不开心，我想要见到一些新面孔，再给它们其中的一小部分稍微改造改造，让它们变异下。
第2届百米赛跑开始，第2代的50只蜗牛奋起直追原先的记录。如果第2代蜗牛中的最快蜗牛成绩超过现有的最快成绩记录，就把最快成绩记录更新下，将“最强者”王座上的蜗牛换成这个最快蜗牛，如果第2代蜗牛中的最好成绩没有超过以前王座上蜗牛的成绩，就不必更替朝代。
按照这个运作规则，让它们最多繁衍500代，那时候我再来看看这个“最强者”王座上是谁，让它去爬金字塔的话，应该就快太多了。第500代的蜗牛经过一代一代的优胜劣汰，自然选择，应该绝大部分都特别能跑了。如果其中连续50代蜗牛中的“最强者”王座上都没有换蜗牛，我就没必要让它们延续到500代了，就让那个连续50次占据“最强者”王座的蜗牛去爬金字塔。如果其中某代“最强者”王座上的蜗牛的百米赛跑记录比9.58秒的人类记录还要好，我觉着那也不必延续到500代了，让这只蜗牛去爬金字塔。
其实上面所述就是遗传算法的核心思想，有了上面的思想再去理解遗传算法就简单太多了，关键在于如何将选择，交配和变异的运作规则进行细化。
遗传算法的流程图如下所示：
其他稍微深入的，可以看我写的这篇文章，再深入的就直接搜些专业书籍文献钻研了。
木水小亭：数模系列(4)：遗传算法（Genetic Algorithm）