手机版 | 登陆 | 注册 | 留言 | 设首页 | 加收藏
当前位置: 网站首页 > 最新快讯 > 文章 当前位置: 最新快讯 > 文章

清扫机器人罗比与遗传算法,轮盘赌算法(算法)

时间:2019-11-14    点击: 次    来源:清扫机器人罗比与遗传算法,轮盘赌算法(算法)    作者:清扫机器人罗比与遗传算法,轮盘赌算法(算法)名 - 小 + 大

清扫机器人罗比与遗传算法,轮盘赌算法(算法)

                                                                 

最近有一本美国人梅拉妮·米歇尔写的书,书名叫《复杂》的,有点火,说它火,主要是得到一些业内大佬的推崇,比如猎豹软件创始人,傅盛,引出一篇微博文[机器思维:所有复杂事物都有底层规律],主要是介绍这本书的,该文甚至称之为”天书“,呵呵,不过我倒没觉得这本书有那么神,不过在《复杂》这本书里,介绍了一个罗比机器人的实例,在一个10x10的方格内,随机分布着一些易拉罐,罗比机器人就是专门清扫易拉罐的。我们先来看下描述:

这里写图片描述

罗比身处一个10*10的二维世界,同时周边随机散布着待清扫的罐子。罗比看不远,它只能看到与自己相邻的五个格子(东南西北中),只能有七个动作(向东移动、向南移动、向西移动、向北移动、随机移动、不动和清扫罐子)。

评分规则:
1)当前格子有罐子并且清扫了得10分。
2)当前格子没有罐子却执行清理的动作,扣 1 分。
3)撞墙扣5分,并且弹回原来格子。
4)普通行走,不撞墙不捡罐子不得分不扣分,也就是0分。

10*10的二维世界只有100个格子,每次清扫,罗比会进行50个动作。
如果按照0.5的密度散布罐子,这样就有50个罐子,每清扫一个罐子10分,满分就会是500分。可以算负分。50次动作如果每次都撞墙,就是-250分。罗比的得分区间是[-250, 500](其中格子大小MxN,罐子密度,每次清扫动作次数,这些都是参数,都是可以调的。相应的得分数与得分区间也会调整。)

按照《复杂》这本书里介绍的计分规则, 我们用传统策略(有罐子就清扫,然后就往有罐子的方向上移动并清扫,否则就随机移动)测试10000次后,得到的平均分是346。而通过遗传算法,在最后迭代1000代的时候,满分500分的情况下,平均得分是480分,而人制定的传统策略,平均得分只有346分。

”如此演化了1000代以后,我们得到了下面这张惊人的曲线。1000代的时候,平均得分是480几分(满分500)。我们发现,第1代非常差,只有负80几分,还不停撞墙。但,就是这么一个起点非常差的清扫机器人罗比,通过拿出无数个体去观察,不断迭代之后,它甚至超出预料,产生了自己的策略——不是见地就扫,而是清扫完一片之后,再去清扫下一片。“
这里写图片描述
通过这个实例,说明一个问题:效率更高的策略,完全是自动进化来的,人类甚至都没能发现。这就是遗传算法。虽然运算量极大,但它自己完成了从简单的规则进化成为非常复杂的策略的过程。得到的结果,比人类精心打磨出来的策略,可能还要好。

这就是一个简单明了的遗传算法的一个实例。跟复杂的机器学习算法比起来,这个遗传算法比较简单,不过用到了一些我们前面博文介绍的简单的概率计算(比如n人分N间房,总共有Nn 种分法),不需要用太多其他的数学知识,简单的c语言或者python程序就可以实现,可以作为入门学习实例。

我看到有两篇详细介绍了罗比机器人的清扫算法的文章,并且有源码链接,(参考后面“参考文献”),特别是叶小伦的在知乎上的回答很详细,下面我概要分析一下。这里面还用到了轮盘赌算法,网文也介绍得很好。


【遗传算法】

众所周知,遗传算法有几个步骤:
1)编码–>创造染色体
2)个体–>组成群组
3)定义评分函数
4)遗传算法,迭代1000次
4.1)所有个体轮流run一遍,评分
4.2)选择
4.3)交叉
4.4)变异

5)调整参数,优化
很多参数都是可以调的,比如棋牌大小MxN(初始10x10),每一次打扫执行多少动作(初始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种可能性,总共的可能状态数就是35 =243

35 怎样得出来的?回忆前面写的博客【数学】–1.样本空间,随机事件基本概念 n个人每人有N种取值,总事件数就是Nn
这里写图片描述

上下左右中
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总共35 =243个状态

一个五位数,每一位数都是0到2,所以这实际上就是一个3进制的5位数,可以把它编号,序号从0到242。

序号=34+33+32+3+1

比如:
0 0 0 0 0 编码 =034+033+032+03+01=0
0 0 0 0 1 编码 =034+033+032+03+11=1
0 0 0 1 2 编码 =034+033+032+13+21=5
….
1 2 0 1 2 编码 =134+233+032+13+21=140

2 2 2 2 2 编码 =234+233+232+23+21=242

1.3)罗比看到“状态”后,要执行动作,总共有几种*动作*

根据题目介绍的,罗比只能有七个动作(向东移动、向南移动、向西移动、向北移动、随机移动、不动和清扫罐子),我们将动作进行编码,将东西南北改成上下左右:
0: 向上走
1: 向下走
2: 向左走
3: 向右走
4: 随机选取方向走
5: 捡罐头
6: 什么都不干

1.4)将“状态”“动作”组合起来,生成一组“策略”
我们构造一个长度为243的一维整型数数组,叫做 stragy[],在一维数值的每一项元素里存放一个动作编号,是一个0~6的数值。
一维数组的下标,就是前面编码的状态号。
总共有243种状态,将状态进行编号,作为一维数值的下标,

数值stragy[]就构成了一个243个0~6数字字符组成的字符串,一组字符串就是一种策略。

那么,罗比的策略就可以用一个字符串表示,字符串的长度是格子情况的总数,每一位代表对应格子情况所需要作出的策略,比如
152455021256444063355141362453351200451455123151604162324266004040256060052004316401456203443334225141156451050235106256354245063143011340422626044356444400300555631325215155436144345164455440161256251412661563442063025020602255536510141514365 。这个策略的第一位是 1,这代表着罗比所处的情况是 00000 时,应该作出动作 1,也就是向下走。类似的,第二位是 5,代表罗比在 00001 时应该捡罐头。

罗比的工作流程就变成:
查看当前的(上下左右中)格子的状态,根据3进制法则计算出状态编号,比如计算得到数值 i0(0i0242) ,把 i0 作为数值stragy[] 的下标(索引),取出 stragy[i0 ] 的数值,比如a0=stragy[i0] ,(0a06 )就执行a0 这个动作。这样就完成了一个动作。下一个动作又根据所处格子的状态计算状态号 i1 ,取出 a1=stragy[i1] ,执行a1 对应的动作。如此循环。

因此,数值stragy[]就构成了一个243个0~6数字字符组成的字符串,一组字符串就是一种策略,按照这组字符串每执行一个动作就能得到一个分值,假定在10x10的方格内清扫一次执行50个动作,最多只有50个罐子,得分就是就得到一个 [-250,500]的数字。

因此我们的目标,就是找到一组较优的straty[]字符串,使之得分尽可能高。

2)个体–>组成群组

定义”群组“ int popu[200][243]

上面编码得到的策略字符数组,我们可以将它看作是一个“个体”,在本题中,一个个体就是一组策略,我们可以生成若干个这样的“个体”,将他们组成“群组”。在本题中,我们构造200个这样的“个体”,组成一个二维数组,这就是“群体”,我们用c语言实现算法,群体就是一个二维数组 int popu[200][243] ;

3)定义评分函数 。

定义 个体得分数值 int score[200]
评分规则前面已经写了,

评分规则:
3.1)当前格子有罐子并且清扫了得10分。
3.2)当前格子没有罐子却执行清理的动作,扣 1 分。
3.3)撞墙扣5分,并且弹回原来格子。
3.4)普通行走,不撞墙不捡罐子不得分不扣分,也就是0分。

每执行一个动作得到一个评分,我们假定罗比在10x10的棋盘内每打扫一次执行50个动作,得分就在[-250,500]之间。(10x10和50个动作这些都是参数,都可以调整)

所谓评分就是让罗比执行一次打扫流程(50个动作),或者打扫流程循环100次,每次随机生成不同的棋盘布局,取100次打扫的得分平均值。

由上面分析得到,罗比是按照策略数值来执行动作的,有了群组以后,我们使用群组的每一个“个体”来执行一次打扫任务,得到一个评分,群组共有200个”个体“,就循环执行200个打扫任务,得到一个评分数值 int score[200],score[i]对应 popu[i],

4)遗传算法
编码已经编好了,群组已经定义好了,评分函数已经定好了,下面就用遗传算法来筛选优秀的个体。

遗传算法由下面4个步骤组成,迭代1000次就是1000代

4.1)将群组中所有个体轮循打扫一遍,评分得到score[]数组
get_score(score[])函数;
这个函数循环给群组popu[]的200个个体评分,得到 score[200] ,对应200个个体。所谓每次评分,就是取出popu[i]的策略字符串,按照这个字符串,去执行一个打扫任务,每个打扫任务是50个动作,得分就是这50个动作的分数之合,大小在[-250,500]之间。get_score()执行完成后,得到当前群组 popu[200] 每个个体对应的得分, score[200]。

4.2)选择 —-使用轮盘赌算法
由上面一步get_score() 得到 score[200]以后,就要依据score[200]的得分,对相应的群组popu[200]中的个体实行优胜劣汰,总体原则就是说,对popu[200]内评分高的个体留下来,将评分低的淘汰掉,使用评分高的个体替代评分低的个体,由此得到一个新的群组popu_new[200],个体数目还是不变,还是200个个体。把那些去掉的个体空位,用较优的个体替代,200个个体可以有重复。

至于选择个体的具体算法,较好的一种算法是使用“轮盘赌”算法。
关于“轮盘赌”算法,有很多优秀的很直观的网文可以参考,比如轮盘赌算法

轮盘赌的意义就在于概率高的占据轮盘的面积就大,随机转动轮盘后,指针停留在面积大的区域的概率就高。

这里写图片描述

对应于本题,轮盘赌算法的步骤就是:

(1)分数取正数 。
对score[200]那些得负数的分数,将它归为0,反正不遗传负数。
(2)计算比率。
将每个得分score[i] 整合到一个(0,1)之间的小数区间上,得double score_pr[200];
score_pr[i]=score[i]j=0199score[j]
(3)累加比率,整合到0~1的直线上。
得double cum_pr[200];
cum_pr[0]=score_pr[0];
for(i=1 to 199){
cum_pr[i]= cum_pr[i-1]+ score_pr[i]
}
(4) 生成一个(0,1)的随机数 rand_zo,比较rand_zo落在cum_pr[200]数组的哪一个区间上,落在哪一个区间就保留哪一个个体。

下面列出轮盘赌算法选择个体的代码(c语言代码)

 void ga_sele(int old_popu[][243]) {       int  new_popu[200][243];  //生成新的种群,还是200个个体       double  score_pr[200];  //将score[200] 整合到(0,1)的比率区间       double cum_pr[200];    //比率累加整合到 0~1 的直线上       double score_sum=0;       int i,j,k;     for(i=0;i< 200;i++)        score_sum += score[i];   //计算累计得分     for(i=0;i<200;i++)        score_pr[i] = score[i]/score_sum;    //计算比率,整合到(0,1)的区间     cum_pr[0]=score_pr[0];    //累加比率,整合到0~1的直线上     for(i=1;i<200;i++)           cum_pr[i]=cum_pr[i-1]+score_pr[i];      //----              //轮盘赌个体选择   for(i=0;i< 200;i++)   {                double rand_0  = rand_zo();  //产生一个(0,1)的随机数        for(j=0;j< 200-1; j++)        {           if(rand_0<  cum_pr[0])           {                memcpy(new_popu[i], old_popu[0], 243);                //如果随机数落在cum_pr[0]的区间,将old_popu[0]个体保留到新的群组              break;           }           else           if(cum_pr[j]< = rand_0 < = cum_pr[j+1])           {              memcpy(new_popu[i], old_popu[j+1], 243);                //如果随机数落在cum_pr[j] 到 cum_pr[j+1] 之间的区间,将old_popu[j+1]个体保留到新的群组              break;          }        }     }       for(i=0;i<  200;i++)     memcpy(old_popu[i]; new_popu[i], 243);   //将优选后的个体重新放回带来的数组中 } 		
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

4.3)交叉
交叉就是先根据交叉概率,比如取cross_rate=0.85,随机取相邻的两个个体,采用单点交叉法,随机计算一个交叉点,交换前后两个个体的后半段,得到两个新的个体。
列出示意代码:

 void ga_cross(int new_popu[][243]) {     //选择需要交叉的个体     int count=0;     int need_cr[200];     int i,j;     int temp[243];     int cross_lno, cross_lno_1;     int cross_rate=0.85;       for(i=0;i< 200;i++)        if(rand_zo< cross_rate)         {            need_cr[count]=i;            count++;         }    if(count%2!=0)      count++;   //随机获取一个不为0的交叉点   int cr_point=0;   while(cr_point==0)        cr_point = m_round(rand_zo()*243);   //进行交叉   for(i=0;i< count;i++)   {        cross_lno=need_cr[i];        cross_lno_1=need_cr[i+1];        for(j=cr_point;j< 243;j++)        {             temp[j]=new_popu[cross_no][j];                        new_popu[cross_no][j]=new_popu[cross_lno_1][j];             new_popu[cross_lno_1][j]=temp[j];        }   }      } 		
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

4.4)变异
变异是小概率事件,比如我们定一个变异概率mut_rate=0.5%=0.005,有200个个体,每个个体有243个位(基因),那么总共有200*243个基因,再乘0.005,就是群组中大概只有243个位(基因)会发生变异,散布在200个个体中。变异就是把原来的数字用另一个0~6的随机数代替。

列出变异代码

 void ga_muta(int popu[][243])   {        int sum=200*243;        int muta_rate=0.005;            int i,j,k;        for(i=0;i< sum;i++)        {            if(rand_zo()< muta_rate)              {                  //定位此基因所在的个体(染色体)                  int chr_loc;                  chr_loc=i/243;                  //再定位此基因所在的个体(染色体)上的基因位                  int gen_loc;                  gen_loc=i%243;                  //进行变异                  popu[chr_loc][gen_loc]=m_round(rand_zo()*6);              }         }   } 		
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

5)最后调整参数,优化
很多参数都是可以调的,比如棋牌大小MxN(初始10x10),每一次打扫执行多少动作(初始50个动作)。群组的个体数取值(默认200),遗传算法迭代次数(初始1000次),等,参数的调整可能会对最优解,速度,收敛性有影响。


简单主程序代码概要

void main(){      int prop[200] [243];        //prop 代表由200个个体组成的种群,每个个体是一个243字符串代表的策略                   double score[200];         //score[i]是策略prop[i]得到的评分,按照初始参数,是一个[ -250,500 ]之间的数字。    init_prop(prop);   //初始化,随机生成200个策略    get_score(prop, score);        printf("当前的最高分数为:%f\n", max(score);    printf("\n计算中...\n");    for(i=0;i<1000;i++)  //遗传算法,迭代1000代    {        get_score(score[])  ;//使用群组每个个体作为策略打扫一轮,得到所有个体的评分score[200];        ga_sele(prop);   //评分完后,使用轮盘赌算法,优胜劣汰,得到新的群组       ga_cross(prop); // 交叉重组           ga_mut(prop);  //变异     }       //迭代1000代后,进化完毕,输出最终得分    get_score(prop, score);      printf("最终最高得分为:%f \n", max(score));}

上一篇:GEP中的轮盘赌选择程序(MATLAB)

下一篇:轮盘赌法

 别浪费都给你吧懒得弄电脑来到宁波懒得弄便利店内懒得弄 哪来的呢懒得弄老地方能力的看法卡积分换员不是卡八VB不不大好说是 时空金币是那伤口局部深V不睡觉 100是开放道具卡类风湿VB你没收到是是你
备案5589485-ICP编号  |   QQ:微信:SL49568  |  地址:北京市东城区  |  电话:186-5901-6237  |