机器学习（八），遗传算法学习---《复杂》的清扫机器人python案例

遗传算法学习---《复杂》的清扫机器人python案例

• 前言
• 一、案例分析
• • 1， 传统方式
  • 2， 遗传算法
• 二，代码实现
• • 1，构造房间
  • 2，清扫工作
  • 3，繁衍后代
  • 3，完整源码
  • 4，运行结果
  • 5，其他
• 总结

前言

镇楼：茴字有13种写法其实才是深入学习的有效方式

上一章完成了任意手绘简单曲线的学习，本来打算继续深入复杂的手绘曲线，遇到不少障碍，无意中阅读到梅拉妮·米歇尔的《复杂》一书，写的真好，书里的清扫机器人只有思路，没有源代码，本章实现一下。

提示：以下是本篇文章正文内容，下面案例可供参考

一、案例分析

我们要设计这样一个清扫机器人robin，他要打扫一个10乘以10的房间，每次打扫所耗资源固定，暂定为200步， 每次房间随机散落50%的垃圾易拉罐，也就是10*10的点上，有一半的位置是有垃圾罐的，如何让他打扫房间效率最大化了？

1， 传统方式

每次移动算一个动作，碰壁并弹回来算一个动作，拾取当前位置算一个动作，另外拾取后才知道当前位置有没有垃圾。

如果是手工方式，分析每一步机器人可能的行走路线，分析当前位置有没有垃圾，旁边有没有垃圾，如何有效的走遍全地图, 最简单的方式是沿着房间边缘走到底，然后下移一格，继续走回来，重复往返，同时每走一步的时候，都要进行拾取。

起点位置(1,1)， 逐行走到最后一个位置，每个位置都要拾取一次，因此总动作数量 99*2 = 198 次。

这样的方式，我们要规定他走的方向，路线。什么时候调整方向而不要撞墙。如果将来地图变化，我们就需要变更算法。简而言之，需要上帝告诉robin怎么做，他才能清扫完整个房间。

2， 遗传算法

这个题目最有意思的地方在于，我们假设robin是随机行走的，他跟自然界的生命一样，应该自己学会如何生存，如何改善自身适应环境。因此我们做一些定义。

罗比的工作是清理它的世界中的空易拉罐。罗比的世界由10x10的100个格子组成（见图9.2）。罗比在位置（1，1）。我们可以假设周围围绕着一堵墙。许多格子中散落着易拉罐（不过每个格子中的易拉罐不会多于一个）。罗比不是很聪明，看得也不远，他只能看到东南西北相邻的4个格子以及本身所在格子中的情况。格子可以是空的（没有罐子），或者有一个罐子，或者是墙。例如，在图9.2中，罗比位于格子（1，1），看到当前格子是空的，北面和西面是墙，南面的格子是空的，东面的格子中有一个罐子。

为跟人工的对比，每次清扫工作罗比也可以执行198个动作。动作可以是以下7种：0：往北移动、1：往南移动、2：往东移动、3：往西移动、4：不动、5：捡拾罐子、6：随机移动。每个动作都会受到奖赏或惩罚。如果罗比所在的格子中有罐子并且收集起来了，就会得到10分的奖赏。如果进行收集罐子的动作而格子中又没有罐子，就会被罚1分。如果撞到了墙，会被罚5分，并弹回原来的格子。显然，罗比尽可能地多收集罐子，别撞墙，没罐子的时候别去捡，得到的分数就最高。

设计思路：

1， 生成第一代机器人群体。群体有200个随机个体（策略）。每个个体策略有243个“基因”。每个基因是一个介于0和6之间的数字，代表一次动作（0=向北移动，1=向南移动，2=向东移动，3=向西移动，4=不动，5=捡拾罐子，6=随机移动）。在初始群体中，基因都随机设定。程序中用一个伪随机数发生器来进行各种随机选择

原文说，罗比可以看到5个格子（当前格子、东、南、西、北），每个格子可以标为空、罐和墙。这样就有243种可能情形，因此基因长度是243，这点其实我不太理解，先按原文的来。

2， 计算群体中每个个体的适应度（工作表现）。通过让罗比执行100次不同的清扫任务来确定策略的适应度。每次将罗比置于位置（1，1），随机撒一些易拉罐（每个格子至多1个易拉罐，格子有易拉罐的概率是50%）。然后让罗比贯彻基因的243个动作。罗比的得分就是策略执行各任务的分数。策略的适应度是执行100次任务的平均得分，每次的罐子分布都不一样。

3， 群体繁衍后代。200个个体，按工作表现排序，每次随机抽取2个个体A和B进行繁衍，表现越好，抽中的概率越高。繁衍的形式是把A基因片段任意拆分为2段，跟B做对应的交换，这样得到两个全新的个体，长度仍然不变。同时新个体做基因突变，随机抽取3个基因位置重置为0到6的整数。

4， 轮回。200个新个体产生后，重新执行2,3的步骤，重复1000次。

二，代码实现

1，构造房间

import numpy as np
import matplotlib.pyplot as plt


# 构造房间，放置垃圾易拉罐
def room():
    xxs = list()
    for i in range(10):
        xx = np.linspace(1, 1, 5)
        d = np.pad(xx,(0,5),'constant',constant_values=(0,0))
        np.random.shuffle(d)
        xxs.append(d)
    k = 0
    xxs = np.array(xxs)
    gbpoints = list()
    for x in np.nditer(xxs):
        if x==1:
            # mark
            a = int(k / xxs.shape[1])   # row
            b = k % xxs.shape[1]    # col
            gbpoints.append([b, a])
        k=k+1
    # 垃圾的坐标从 1 开始
    pts = np.array(gbpoints) + [1,1] 
    return pts
   
# 打印房间以及易拉罐
gbpoints = room()
gbpoints2 = np.array(gbpoints).T

fig1 = plt.figure(num='robin的房间', figsize=(7, 7), facecolor='#FFFFFF', edgecolor='#0000FF')
plt.xlim([0,11])
plt.ylim([0,11])
plt.xticks(np.linspace(0,11,12,endpoint=True))  # 设置x轴刻度
plt.yticks(np.linspace(0,11,12,endpoint=True))  # 设置x轴刻度
plt.scatter(gbpoints2[0], gbpoints2[1], color=(0.1, 0.8, 0.3, 0.4), s=100,marker='*')

# roby has 7 way  罗比有7种可能选择：北移、南移、东移、西移、随机移动、不动、收集罐子
#   0=向北移动，1=向南移动，2=向东移动，3=向西移动，4=不动，5=捡拾罐子，6=随机移动
#  每个动作都会受到奖赏或惩罚。如果罗比所在的格子中有罐子并且收集起来了，就会得到10分的奖赏。
#  如果进行收集罐子的动作而格子中又没有罐子，就会被罚1分。如果撞到了墙，会被罚5分，并弹回原来的格子。

#  初始化行为
peoples = list()
for i in range(2):
    peoples.append(np.random.randint(0, 7, 243))
    
# 存储初始化数据
np.savetxt('pts.txt',gbpoints,fmt='%d')
np.savetxt('peoples.txt',np.array(peoples),fmt='%d')
           

代码中设置了每行随机放置5个易拉罐，运行效果如下：

2，清扫工作

上一个代码里面，我们存储了地图以及人群，我们挑选第一个人，在存储的地图里展开清扫工作。清扫工作的代码 按照个人的基因进行执行。

# -*- coding: utf-8 -*-
"""
Created on Tue Mar  9 14:44:20 2021

@author: huwp001
"""
import numpy as np
import matplotlib.pyplot as plt

pts=np.loadtxt('pts.txt',dtype=np.int)
peoples=np.loadtxt('peoples.txt',dtype=np.int)

# 执行策略
#  罗比有7种可能选择：北移、南移、东移、西移、随机移动、不动、收集罐子
#   0=向北移动，1=向南移动，2=向东移动，3=向西移动，4=不动，5=捡拾罐子，6=随机移动
#  每个动作都会受到奖赏或惩罚。如果罗比所在的格子中有罐子并且收集起来了，就会得到10分的奖赏。
#  如果进行收集罐子的动作而格子中又没有罐子，就会被罚1分。如果撞到了墙，会被罚5分，并弹回原来的格子。
def people_work(people, pts):
    haspts = np.array([[999,999],[888,888]])
    p = np.array([1,1])
    lines = list()
    lines.append(p)
    score = 0   #分数
    sidect = 0  #撞墙次数
    failcolct = 0   #拾取失败的次数
    for step in people:
        if step==6:
            step = np.random.randint(4, size=1)[0]
        p2 = p
        if step==0:
            p2 = p + [0,1]
        if step==1:
            p2 = p + [0,-1]
        if step==2:
            p2 = p + [1,0]
        if step==3:
            p2 = p + [-1,0]
        # 检测p2 是否撞墙
        if p2.__contains__(0) or p2.__contains__(11):
            score = score - 5
            lines.append(p2)
            lines.append(p)
            sidect = sidect + 1
        else:
            p = p2
            lines.append(p)
        if step==4:
            p2 = p
        if step==5:
            if (pts == p2).all(1).any() and (haspts == p2).all(1).any()==False:
                # 有物体
                score = score + 10
                haspts = np.row_stack((haspts, p2))
            else:
                score = score - 1
                failcolct = failcolct + 1
    print('拾取易拉罐%d次，撞墙%d次， 拾取失败%d次 , 得分%d ' % (len(haspts)-2, sidect, failcolct, score))
    return lines, score
                
lines, score = people_work(peoples[0], pts)

lines = np.array(lines)
np.savetxt('lines.txt',lines,fmt='%d')

#lines = lines.T

plt.cla()
fig1 = plt.figure(num='robin的房间', figsize=(7, 7), facecolor='#FFFFFF', edgecolor='#0000FF')
plt.xlim([0,11])
plt.ylim([0,11])
plt.xticks(np.linspace(0,11,12,endpoint=True))  # 设置x轴刻度
plt.yticks(np.linspace(0,11,12,endpoint=True))  # 设置x轴刻度

#打印地图垃圾罐
pts2 = np.array(pts).T
plt.scatter(pts2[0], pts2[1], color=(0.1, 0.8, 0.3, 0.4), s=100,marker='*')

for i in range(len(lines)-1):
    A = lines[i]
    B = lines[i+1]
    plt.arrow(A[0], A[1], B[0]-A[0], B[1]-A[1],
             width=0.01,
             length_includes_head=True, # 增加的长度包含箭头部分
              head_width=0.1,
              head_length=0.2,
             fc='r',
             ec='b')


           

运行效果如下，可以看到robin从（1,1）开始移动，碰到墙会返回回来。有的时候还原地打转。

另外，在spyder里面看到 ，这次清扫拾取成功12次，撞墙31次，失败28次 ，总分数-63分。

3，繁衍后代

分两部分，结婚和生子。先看如何结婚， 我将所有人群分为4部分，越是业绩好的人群越是容易被选中，然后在人群里面，选中2个人结婚。

# 随机寻找优秀的人去组合，结婚生子
    p = [0.1, 0.2, 0.3, 0.4]
    childrens = list()
    argss = np.split(args,4)    #人群拆分为4部分
    for i in range(100):
        k = int(np.random.choice([0,1,2,3], 1, replace=True, p=p))
        spouse = np.random.choice(argss[k], 2, replace=True)
        man = peoples[spouse[0]]
        woman = peoples[spouse[1]]
        c1, c2 = makelove(man, woman)
        childrens.append(c1)
        childrens.append(c2)
    return childrens    
           

生子则是交换基因DNA，并诱发微小的基因突变，代码如下

def mutation(gene):
    #基因突变， 随机取3个。
    for i in range(3):    
        ixs = np.random.randint(len(gene), size=1)[0]
        gene[ixs] = np.random.randint(7, size=1)[0]
    return gene

def makelove(p1, p2):
    # 基因重组, 随机得到一个拆分点，重新组合
    s1 = np.random.randint(len(p1), size=1)[0]
    c1 = mutation(np.append(p1[0:s1],p2[s1:]))
    c2 = mutation(np.append(p2[:s1],p1[s1:]))
    return c1, c2
           

3，完整源码

我们组织下代码，函数封装到func.py文件里面：

# -*- coding: utf-8 -*-
"""
func.py
Created on Tue Mar  9 17:40:51 2021

@author: huwp001
"""
import numpy as np

# 执行策略
#  罗比有7种可能选择：北移、南移、东移、西移、随机移动、不动、收集罐子
#   0=向北移动，1=向南移动，2=向东移动，3=向西移动，4=不动，5=捡拾罐子，6=随机移动
#  每个动作都会受到奖赏或惩罚。如果罗比所在的格子中有罐子并且收集起来了，就会得到10分的奖赏。
#  如果进行收集罐子的动作而格子中又没有罐子，就会被罚1分。如果撞到了墙，会被罚5分，并弹回原来的格子。
def people_work(people, pts):
    haspts = np.array([[999,999],[888,888]])
    p = np.array([1,1])
    lines = list()
    lines.append(p)
    score = 0   #分数
    sidect = 0  #撞墙次数
    failcolct = 0   #拾取失败的次数
    for step in people:
        if step==6:
            step = np.random.randint(4, size=1)[0]
        p2 = p
        if step==0:
            p2 = p + [0,1]
        if step==1:
            p2 = p + [0,-1]
        if step==2:
            p2 = p + [1,0]
        if step==3:
            p2 = p + [-1,0]
        # 检测p2 是否撞墙
        if p2.__contains__(0) or p2.__contains__(11):
            score = score - 5
            lines.append(p2)
            lines.append(p)
            sidect = sidect + 1
        else:
            p = p2
            lines.append(p)
        if step==4:
            p2 = p
        if step==5:
            if (pts == p2).all(1).any() and (haspts == p2).all(1).any()==False:
                # 有物体
                score = score + 10
                haspts = np.row_stack((haspts, p2))
            else:
                score = score - 1
                failcolct = failcolct + 1
    #print('拾取易拉罐%d次，撞墙%d次， 拾取失败%d次 ' % (len(haspts)-2, sidect, failcolct))
    #print(haspts)
    return lines, score

def mutation(gene):
    #基因突变， 基因链上随机取3个值
    for i in range(3):    
        ixs = np.random.randint(len(gene), size=1)[0]
        gene[ixs] = np.random.randint(7, size=1)[0]
    return gene

def makelove(p1, p2):
    # 基因重组, 随机得到一个拆分点，重新组合
    s1 = np.random.randint(len(p1), size=1)[0]
    c1 = mutation(np.append(p1[0:s1],p2[s1:]))
    c2 = mutation(np.append(p2[:s1],p1[s1:]))
    return c1, c2

# 构造房间，放置垃圾易拉罐，注意放置了50%的易拉罐
def room():
    xxs = list()
    for i in range(10):
        xx = np.linspace(1, 1, 5)
        d = np.pad(xx,(0,5),'constant',constant_values=(0,0))
        np.random.shuffle(d)
        xxs.append(d)
    k = 0
    xxs = np.array(xxs)
    gbpoints = list()
    for x in np.nditer(xxs):
        if x==1:
            # mark
            a = int(k / xxs.shape[1])   # row
            b = k % xxs.shape[1]    # col
            gbpoints.append([b, a])
        k=k+1
    # 垃圾的坐标从 1 开始
    pts = np.array(gbpoints) + [1,1] 
    return pts

# 这就是生活， 有能力才可以结婚，生娃娃，否则被淘汰
def life(peoples):
    scores = list()
    for i in range(len(peoples)):
        # 每个人要工作100次，取平均值
        #print('people epoch=%d ix=%d' %(epoch_num, i))
        if i % 10==0:
            print('.', end=('')) 
        a = list()
        for k in range(10):
            lines, score = people_work(peoples[i], room())
            a.append(score)
        score = np.average(a)
        scores.append(score)
    scores = np.array(scores)
    print()
    print('这一代人的平均工作能力 %.3f' % np.average(scores))
    args = np.argsort(scores)  # 按工作能力排序
    
    # 随机寻找优秀的人去组合，结婚生子
    p = [0.1, 0.2, 0.3, 0.4]
    childrens = list()
    argss = np.split(args,4)    #人群拆分为4部分
    for i in range(100):
        k = int(np.random.choice([0,1,2,3], 1, replace=True, p=p))
        spouse = np.random.choice(argss[k], 2, replace=True)
        man = peoples[spouse[0]]
        woman = peoples[spouse[1]]
        c1, c2 = makelove(man, woman)
        childrens.append(c1)
        childrens.append(c2)
    return childrens    

           

执行文件：

# -*- coding: utf-8 -*-
"""
Created on Tue Mar  9 15:15:42 2021

@author: huwp001
"""


import numpy as np
import matplotlib.pyplot as plt

from func import life

# define

#基因长度 
GENE_LEN = 243

#  初始化，女娲造人200个，基因随机
peoples = list()
for i in range(200):
    peoples.append(np.random.randint(0, 7, GENE_LEN))
    

# 暂定繁衍1000代
for epoch_num in range(1000):
    print('开始繁衍第%d代' % epoch_num )
    np.savetxt('peoples%d.txt' % epoch_num ,np.array(peoples),fmt='%d')
    peoples = life(peoples)
    epoch_num = epoch_num +1
    

           

4，运行结果

运行主程序，得到如下结果， 可以看到robin确实越来越强。

我另外使用上面的清扫程序，读取每代存储的peoples文件，测试了下运行的结果，第2代人群的第一个，运行结果如下：

可以看到初始的基因真的很差，撞墙26次。分数计算： 710-265-23=-83

当运行到第10代人的时候，结果如下：

当运行到第50代人的时候：

当运行到100代人群的时候：

真是令人惊喜的进步，robin确实越来越聪明了，由上可见遗传的力量确实很强大，robin没有主动意识，也不会观察当前位置有没有易拉罐，只会随机的走路和随机的拾取物品，自动获得了进化。

5，其他

开发环境安装 前往

总结

本章完整演示了一个遗传算法的例子，让机器学习之路进一步充满了欢乐。