关于人工智能:用遗传算法优化垃圾收集策略

55次阅读

共计 6759 个字符，预计需要花费 17 分钟才能阅读完成。

作者 |Andrew Kuo
编译 |VK
起源 |Towards Data Science

遗传算法是一个优化技术，在实质上相似于进化过程。这可能是一个粗略的类比，但如果你眯着眼睛看，达尔文的自然选择的确大抵上相似于一个优化工作，其目标是制作出齐全适宜在其环境中繁衍生息的有机体。

在本文中，我将展现如何在 Python 中实现一个遗传算法，在几个小时内“进化”一个收集垃圾的机器人。

背景

我所遇到的遗传算法原理最好的教程来自 Melanie Mitchell 写的一本对于简单零碎的好书《Complexity: A Guided Tour》。

在其中一个章节中，Mitchell 介绍了一个名叫 Robby 的机器人，他在生活中的惟一目标是捡垃圾，并形容了如何应用 GA 优化 Robby 的控制策略。上面我将解释我解决这个问题的办法，并展现如何在 Python 中实现该算法。有一些很好的包能够用来结构这类算法（比方 DEAP），然而在本教程中，我将只应用根本 Python、Numpy 和 TQDM（可选）。

尽管这只是一个玩具的例子，但 GAs 在许多理论利用中都有应用。作为一个数据科学家，我常常用它们来进行超参数优化和模型抉择。尽管 GAs 的计算成本很高，但 GAs 容许咱们并行地摸索搜寻空间的多个区域，并且在计算梯度时是一个很好的抉择。

问题形容

一个名为 Robby 的机器人生存在一个充斥垃圾的二维网格世界中，四周有 4 堵墙（如下图所示）。这个我的项目的指标是倒退一个最佳的控制策略，使他可能无效地捡垃圾，而不是撞墙。

Robby 只能看到他四周上下左右四个方块以及他所在的方块，每个方块有 3 个抉择，空的，有垃圾，或者是一面墙。因而，Robby 有 3⁵=243 种不同的状况。Robby 能够执行 7 种不同的动作：上下左右的挪动（4 种）、随机挪动、捡拾垃圾或静止不动。

因而，Robby 的控制策略能够编码为一个“DNA”字符串，由 0 到 6 之间的 243 位数字组成（对应于 Robby 在 243 种可能的状况下应该采取的口头）。

办法

任何 GA 的优化步骤如下：

  1. 生成问题初始随机解的“种群”
  2. 个体的“拟合度”是依据它解决问题的水平来评估的
  3. 最合适的解决方案进行“滋生”并将“遗传”物质传递给下一代的后辈
  4. 反复第 2 步和第 3 步，直到咱们失去一组优化的解决方案

在咱们的工作中，你创立了第一代 Robbys 初始化为随机 DNA 字符串（对应于随机控制策略）。而后模仿让这些机器人在随机调配的网格世界中运行，并察看它们的性能。

拟合度

机器人的拟合度取决于它在 n 次挪动中捡到多少垃圾，以及它撞到墙上多少次。在咱们的例子中，机器人每捡到一块垃圾就给它 10 分，每次它撞到墙上就减去 5 分。而后，这些机器人以它们的拟合度相干的概率进行“交配”（即，捡起大量垃圾的机器人更有可能繁殖后辈），新一代机器人诞生了。

交配

有几种不同的办法能够实现“交配”。在 Mitchell 的版本中，她将父母的两条 DNA 链随机拼接，而后将它们连贯在一起，为下一代发明一个孩子。在我的实现中，我从每一个亲本中随机调配每个基因（即，对于 243 个基因中的每一个，我掷硬币决定遗传谁的基因）。

例如应用我的办法，在前 10 个基因里，父母和孩子可能的基因如下：

Parent 1: 1440623161
Parent 2: 2430661132
Child:    2440621161

渐变

咱们用这个算法复制的另一个自然选择的概念是“变异”。尽管一个孩子的绝大多数基因都是从父母那里遗传下来的，但我也建设了基因突变的小可能性（即随机调配）。这种突变率使咱们可能摸索新的可能。

Python 实现

第一步是导入所需的包并为此工作设置参数。我曾经抉择了这些参数作为终点，然而它们能够调整，我激励你能够尝试调整。

"""导入包"""
import numpy as np
from tqdm.notebook import tqdm

"""设置参数"""
# 仿真设置
pop_size = 200 # 每一代机器人的数量
num_breeders = 100 # 每一代可能交配的机器人数量
num_gen = 400 # 总代数
iter_per_sim = 100 # 每个机器人垃圾收集模仿次数
moves_per_iter = 200 # 机器人每次模仿能够做的挪动数

# 网格设置
rubbish_prob = 0.5 # 每个格子中垃圾的概率
grid_size = 10 # 0 网格大小(墙除外)

# 进化设置
wall_penalty = -5 # 因撞到墙上而被扣除的拟合点
no_rub_penalty = -1 # 在空方块捡垃圾被扣分
rubbish_score = 10 # 捡垃圾可取得积分
mutation_rate = 0.01 # 变异的概率

接下来，咱们为网格世界环境定义一个类。咱们用标记“o”、“x”和“w”来示意每个单元，别离对应一个空单元、一个带有垃圾的单元和一个墙。

class Environment:
    """类，用于示意充斥垃圾的网格环境。每个单元格能够示意为:'o': 空'x': 垃圾'w': 墙"""
    def __init__(self, p=rubbish_prob, g_size=grid_size):
        self.p = p # 单元格是垃圾的概率
        self.g_size = g_size # 不包含墙

        # 初始化网格并随机调配垃圾
        self.grid = np.random.choice(['o','x'], size=(self.g_size+2,self.g_size+2), p=(1 - self.p, self.p))
        
        # 设置内部正方形为墙壁
        self.grid[:,[0,self.g_size+1]] = 'w'
        self.grid[[0,self.g_size+1], :] = 'w'

    def show_grid(self):
        # 以以后状态打印网格
        print(self.grid)

    def remove_rubbish(self,i,j):
        # 从指定的单元格 (i,j) 革除垃圾
        if self.grid[i,j] == 'o': # 单元格曾经是空
            return False
        else:
            self.grid[i,j] = 'o'
            return True

    def get_pos_string(self,i,j):
        # 返回一个字符串，示意单元格 (i,j) 中机器人“可见”的单元格
        return self.grid[i-1,j] + self.grid[i,j+1] + self.grid[i+1,j] + self.grid[i,j-1] + self.grid[i,j]

接下来，咱们创立一个类来示意咱们的机器人。这个类包含执行动作、计算拟合度和从一对父机器人生成新 DNA 的办法。

class Robot:
    """用于示意垃圾收集机器人"""
    def __init__(self, p1_dna=None, p2_dna=None, m_rate=mutation_rate, w_pen=wall_penalty, nr_pen=no_rub_penalty, r_score=rubbish_score):
        self.m_rate = m_rate # 突变率
        self.wall_penalty = w_pen # 因撞到墙上而受罚
        self.no_rub_penalty = nr_pen # 在空方块捡垃圾的处罚
        self.rubbish_score = r_score # 捡垃圾的处分
        self.p1_dna = p1_dna # 父母 2 的 DNA
        self.p2_dna = p2_dna # 父母 2 的 DNA
        
        # 生成字典来从场景字符串中查找基因索引
        con = ['w','o','x'] # 墙，空，垃圾
        self.situ_dict = dict()
        count = 0
        for up in con:
            for right in con:
                for down in con:
                    for left in con:
                        for pos in con:
                            self.situ_dict[up+right+down+left+pos] = count
                            count += 1
        
        # 初始化 DNA
        self.get_dna()

    def get_dna(self):
        # 初始化机器人的 dna 字符串
        if self.p1_dna is None:
            # 没有父母的时候随机生成 DNA
            self.dna = ''.join([str(x) for x in np.random.randint(7,size=243)])
        else:
            self.dna = self.mix_dna()

    def mix_dna(self):
        # 从父母的 DNA 生成机器人的 DNA
        mix_dna = ''.join([np.random.choice([self.p1_dna,self.p2_dna])[i] for i in range(243)])

        #增加变异
        for i in range(243):
            if np.random.rand() > 1 - self.m_rate:
                mix_dna = mix_dna[:i] + str(np.random.randint(7)) + mix_dna[i+1:]

        return mix_dna

    def simulate(self, n_iterations, n_moves, debug=False):
        # 仿真垃圾收集
        tot_score = 0
        for it in range(n_iterations):
            self.score = 0 # 拟合度分数
            self.envir = Environment()
            self.i, self.j = np.random.randint(1,self.envir.g_size+1, size=2) # 随机调配初始地位
            if debug:
                print('before')
                print('start position:',self.i, self.j)
                self.envir.show_grid()
            for move in range(n_moves):
                self.act()
            tot_score += self.score
            if debug:
                print('after')
                print('end position:',self.i, self.j)
                self.envir.show_grid()
                print('score:',self.score)
        return tot_score / n_iterations # n 次迭代的均匀得分

    def act(self):
        # 依据 DNA 和机器人地位执行动作
        post_str = self.envir.get_pos_string(self.i, self.j) # 机器人以后地位
        gene_idx = self.situ_dict[post_str] # 以后地位 DNA 的相干索引
        act_key = self.dna[gene_idx] # 从 DNA 中读取口头
        if act_key == '5':
            # 随机挪动
            act_key = np.random.choice(['0','1','2','3'])

        if act_key == '0':
            self.mv_up()
        elif act_key == '1':
            self.mv_right()
        elif act_key == '2':
            self.mv_down()
        elif act_key == '3':
            self.mv_left()
        elif act_key == '6':
            self.pickup()

    def mv_up(self):
        # 向上挪动
        if self.i == 1:
            self.score += self.wall_penalty
        else:
            self.i -= 1

    def mv_right(self):
        # 向右挪动
        if self.j == self.envir.g_size:
            self.score += self.wall_penalty
        else:
            self.j += 1

    def mv_down(self):
        # 向下挪动
        if self.i == self.envir.g_size:
            self.score += self.wall_penalty
        else:
            self.i += 1

    def mv_left(self):
        # 向左挪动
        if self.j == 1:
            self.score += self.wall_penalty
        else:
            self.j -= 1

    def pickup(self):
        # 捡垃圾
        success = self.envir.remove_rubbish(self.i, self.j)
        if success:
            # 胜利捡到垃圾
            self.score += self.rubbish_score
        else:
            # 以后方块没有捡到垃圾
            self.score += self.no_rub_penalty

最初是运行遗传算法的时候了。在上面的代码中，咱们生成一个初始的机器人种群，让自然选择来运行它的过程。我应该提到的是，当然有更快的办法来实现这个算法（例如利用并行化），然而为了本教程的目标，我就义了速度来实现清晰。

# 初始种群
pop = [Robot() for x in range(pop_size)]
results = []

# 执行进化
for i in tqdm(range(num_gen)):
    scores = np.zeros(pop_size)
    
    # 遍历所有机器人
    for idx, rob in enumerate(pop):
        # 运行垃圾收集模仿并计算拟合度
        score = rob.simulate(iter_per_sim, moves_per_iter)
        scores[idx] = score

    results.append([scores.mean(),scores.max()]) # 保留每一代的平均值和最大值

    best_robot = pop[scores.argmax()] # 保留最好的机器人

    # 限度那些可能交配的机器人的数量
    inds = np.argpartition(scores, -num_breeders)[-num_breeders:] # 基于拟合度失去顶级机器人的索引
    subpop = []
    for idx in inds:
        subpop.append(pop[idx])
    scores = scores[inds]

    # 平方并标准化
    norm_scores = (scores - scores.min()) ** 2 
    norm_scores = norm_scores / norm_scores.sum()

    # 发明下一代机器人
    new_pop = []
    for child in range(pop_size):
        # 抉择拟合度优良的父母
        p1, p2 = np.random.choice(subpop, p=norm_scores, size=2, replace=False)
        new_pop.append(Robot(p1.dna, p2.dna))

    pop = new_pop

尽管最后大多数机器人不捡垃圾，总是撞到墙上，但几代人之后，咱们开始看到一些简略的策略（例如“如果与垃圾在一起，就捡起来”和“如果挨着墙，就不要移到墙里”）。通过几百次的重复，咱们只剩下一代不堪设想的垃圾收集蠢才！

后果

上面的图表表明，咱们可能在 400 代机器人种群中“进化”出一种胜利的垃圾收集策略。

为了评估进化控制策略的品质，我手动创立了一个基准策略，其中蕴含一些直观正当的规定：

  • 如果垃圾在以后方块，捡起来
  • 如果在相邻的方块上能够看到垃圾，移到那个方块
  • 如果凑近墙，则向相同方向挪动
  • 否则，随便挪动

均匀而言，这一基准策略达到了 426.9 的拟合度，但咱们最终的“进化”机器人的均匀拟合度为 475.9。

策略剖析

这种优化办法最酷的一点是，你能够找到反直觉的解决方案。机器人不仅可能学习人类可能设计的正当规定，而且还自发地想出了人类可能永远不会思考的策略。一种先进的技术呈现了，就是应用“标记物”来克服远视和记忆有余。

例如，如果一个机器人当初在一个有垃圾的方块上，并且能够看到东西方方块上的垃圾，那么一个天真的办法就是立刻捡起以后方块上的垃圾，而后挪动到那个有垃圾的方块。这种策略的问题是，一旦机器人挪动（比方向西），他就无奈记住东边还有 1 个垃圾。为了克服这个问题，咱们察看了咱们的进化机器人执行以下步骤：

  1. 向西挪动（在以后方块留下垃圾作为标记）
  2. 捡起垃圾往东走（它能够看到垃圾作为标记）
  3. 把垃圾捡起来，搬到东边去
  4. 捡起最初一块垃圾

从这种优化中产生的另一个反直觉策略的例子如下所示。OpenAI 应用强化学习（一种更简单的优化办法）教代理玩捉迷藏。咱们看到，这些代理一开始学习“人类”策略，但最终学会了新的解决方案。

论断

遗传算法以一种独特的形式将生物学和计算机科学联合在一起，尽管不肯定是最快的算法，但在我看来，它们是最漂亮的算法之一。

本文中介绍的所有代码都能够在我的 Github 上找到，还有一个演示 Notebook:https://github.com/andrewjkuo…。谢谢你的浏览！

原文链接：https://towardsdatascience.co…

欢送关注磐创 AI 博客站：
http://panchuang.net/

sklearn 机器学习中文官网文档：
http://sklearn123.com/

欢送关注磐创博客资源汇总站：
http://docs.panchuang.net/

正文完
人工智能
发表至： 人工智能
2020-10-25
 0
关于人工智能:为什么-AI-时代人人都需要学一点编程
关于人工智能:2025年自动驾驶分水岭智能电动汽车行业的上下半场丨曼孚科技
关于人工智能:基础大模型能像人类一样标注数据吗
关于人工智能:第三届-Apache-Flink-极客挑战赛暨-AAIG-CUP-报名开始