最近有一本美国人梅拉妮·米歇尔写的书，书名叫《复杂》的，有点火，说它火，主要是得到一些业内大佬的推崇，比如猎豹软件创始人，傅盛，引出一篇微博文[机器思维：所有复杂事物都有底层规律]，主要是介绍这本书的，该文甚至称之为”天书“，呵呵，不过我倒没觉得这本书有那么神，不过在《复杂》这本书里，介绍了一个罗比机器人的实例，在一个10×10的方格内，随机分布着一些易拉罐，罗比机器人就是专门清扫易拉罐的。我们先来看下描述：
这就是一个简单明了的遗传算法的一个实例。跟复杂的机器学习算法比起来，这个遗传算法比较简单，不过用到了一些我们前面博文介绍的简单的概率计算（比如n人分N间房，总共有
我看到有两篇详细介绍了罗比机器人的清扫算法的文章，并且有源码链接，（参考后面“参考文献”），特别是叶小伦的在知乎上的回答很详细，下面我概要分析一下。这里面还用到了轮盘赌算法， 文也介绍得很好。
【遗传算法】
众所周知，遗传算法有几个步骤：
1）编码–>创造染色体
2）个体–>组成群组
3）定义评分函数
4）遗传算法，迭代1000次
4.1）所有个体轮流run一遍，评分
4.2）选择
4.3）交叉
4.4）变异
5）调整参数，优化
很多参数都是可以调的，比如棋牌大小MxN（初始10×10），每一次打扫执行多少动作（初始50个动作），每次评分是打扫一次还是打扫N次（初始只打扫1次）扫次数越多，取平均值评分越客观。群组的个体数取值（默认200），遗传算法迭代次数（初始1000次），等等，这些参数都可以调大调小。
==========
将上面的步骤写详细点：
[遗传算法]
1）编码，创造染色体，就是个体。假设个体是一个一维数组。
2）由个体组成群种。假设群种是一个2维数组。
3）定义评分函数（评分规则），也叫适应度函数。
for(遗传算法循环1000遍）
{
4）遗传算法
4.1）for（群种每个个体）运行一遍，得到所有的评分。在这里是for（每个策略），罗比使用第i个策略清扫一次，得到第i个个体的评分，或者清扫N次，取平均分。
4.2）优胜劣汰得到新的种群。根据评分进行选择。通常用轮盘赌算法进行选择，越是评分高的个体被留下了的概率越大，但是只是概率问题，评分低的也不是完全没机会，只是概率低。
4.3）交叉。最简单的就用单点交叉法，将上下两个个体交换后半部分基因。定义一个交叉概率(cross_rate)，推荐cross_rate在80%~95%。
4.4）变异。变异率(muta_rate)一般来说应该比较小，一般使用0.5％-1％最好。
经过交叉与变异后，新的种群又发生了变化。肯定比上一代评分高。
}
遗传算法每循环一遍，代表生成新的一代 。
在《复杂》那本书里介绍的罗比机器人，最后迭代1000代的时候，满分500分的情况下，平均得分是480分，而人制定的传统策略，平均得分只有346分。
【实例：罗比机器人实现遗传算法】
1）首先主要是编码问题。
“现实问题转换到遗传算法是一个难点，也就是现实问题的解如何映射到遗传算法的个体上，完成了这一步，后面的三个算子操作就按部就班了（也要根据实际情况进行调整）。”
1.1）罗比的工作流程：
1.先判断当前状态。就是观察自己所处的格子，周围4个方向的格子，有没有罐子，是不是墙壁。
2.根据不同的状态，执行一定的动作 。不同的状态对应不同的动作就叫做策略。
3. 重复1和2，直到动作执行完。
根据不同的状态执行不同的动作，这个就叫做策略。策略可以人为制定，比如当前格子有罐子就检罐子，没罐子就朝有罐子的方向行走，如果四周都没有罐子就朝不是墙壁的方向走。我们当前遗传算法的目的，就是通过遗传算法，逐步得到优化的策略，看看是否比人为制定的策略优秀。
1.2）先看下罗比能看到几种“状态”
罗比只能看到当前的格子以及上下左右，共4个格子，每个格子有三种状态，取0,1,2编码：
*没有罐子 —>0
*有罐子 —–>1
*墙壁 —->2
那么罗比可以看到5个格子(上下左右中)，每个格子有3种可能性，总共的可能状态数就是
” role=”presentation” style=”position: relative;”>怎样得出来的忆前面写的博客【数学】–1.样本空间，随机事件基本概念 n个人每人有N种取值，总事件数就是 3 5 ” role=”presentation” style=”position: relative;”> N n
上下左右中
0 0 0 0 0
0 0 0 0 1
0 0 0 0 2
0 0 0 1 0
0 0 0 1 1
…
2 2 2 2 2
从00000到22222总共
一个五位数，每一位数都是0到2，所以这实际上就是一个3进制的5位数，可以把它编 ，序 从0到242。
序 =
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！