本文改编自Mat Buckland的

游戏开发中的人工智能技术

中的Chapter 7 扫雷机的实现，C++代码重新用python来实现(本文所有遗传算法/神经网络相关代码均改编值Mat的C++代码，如有雷同，纯属巧合)。

在本章节中Mat Buckland实现了一个利用神经网络和遗传算法进化的扫雷机，扫雷机从初始的几乎只会原地打转，最终可以进化到自行寻找地图上的地雷。废话不多说，先看示意图，进化开始的时候，扫雷机的行为如下图，这些蠢蠢得扫雷机都在不断的原地打转：

进化一定时间后，扫雷机就智能多了，开始在地图上有目的的搜寻地雷了：

是不是看起来比较神奇，下面我们一步一步的来剖析Mat是如何实现这个进化过程的。

神经网络模型

这个概念现在很火啊，基本的数学原理在这里不再赘述(我也不懂 >_<)，有兴趣的可以自行去搜索。个人对神经网络的理解就是一个决策系统，在训练成熟的神经网络的模型下，神经网络能够根据给定的输入决策出所期望的输出。基本的神经网络的模型如下图，这个神经网络有一个输入层(Layer L1)，一个隐藏层(Layer L2)，还有一个输出层(Layer L3)：

在经过一定阶段的训练之后，我们可以得到这个神经网络里每个节点的系数，这个系数就决定了训练好的神经网络在给定的输入得情况下会得到什么样的输出。

扫雷机的神经网络

扫雷机在工作的时候的状态如下图：



控制扫雷机工作的输入条件有下面两个：

1. 与扫雷机最靠近的地雷的位置(x, y)

2. 代表扫雷机前进的方向的向量(x, y)

在这个模型里，我们对扫雷机的左右履带各设置一个动力值，左右履带的动力值之差我们定义为扫雷机转向的力，左右履带的动力值之和我们定义为扫雷机前进的速度。

综上，我们设计的神经网络需要4个输入，分别对应两个控制条件中的4个值，需要两个输出，对应扫雷机左右履带的动力值。训练的目标就是给出一个最合理的模型来判决扫雷机前进的方向和速度。

来看看神经网络的编码：

神经元

根据神经网络的模型不难写出神经元的python代码，一个神经元有一定数目的输入，每个输入都有一个权重，这里需要注意的是，我们所有的参数最后都会通过Sigmoid来进行归一化(请自行百度Sigmoid函数)，所以我们的权重选择的也是在[-1, 1]之间的随机数：

class SNeuron(object):
    def __init__(self, NumInputs):
        self._NumInputs = NumInputs
        self._Weights   = []    

        for i in xrange(self._NumInputs):
            self._Weights.append(random.random() - random.random()) #生成一个-1, 1之间的随机Weight
        return

神经网络层

一定数目的神经元组合在一起就成为一个网络层：

class SNeuronLayer(object):
    def __init__(self, NumNeurons, NumInputsPerNeuron):
        self._NumNeurons = NumNeurons
        self._Neurons    = []   

        for i in xrange(self._NumNeurons):
            self._Neurons.append(SNeuron(NumInputsPerNeuron))   
        return

网络

再将一定的神经网络层组合起来，就是最终的神经网络的模型了。直接看代码，神经网络接受四个参数分别是：

NumInputs – 神经网络的输入参数的个数

NumOutputs – 神经网络的输出参数的个数

NumHidden – 神经网络隐藏层的层数

NeuronsPerHiddenLayer – 神经网络每个隐藏层包含多少个神经元

class CNeuralNet(object):
    def __init__(self, NumInputs=iNumInputs, NumOutputs=iNumOutputs, NumHidden=iNumHidden, NeuronsPerHiddenLayer=iNeuronsPerHiddenLayer):
        self._NumInputs = NumInputs
        self._NumOutputs = NumOutputs
        self._NumHiddenLayers = NumHidden
        self._NeuronsPerHiddenLyr = NeuronsPerHiddenLayer
        self._Layers = []   

        self.CreateNet()    

        return  

    def CreateNet(self):
        if self._NumHiddenLayers > 0:
            # 第一个hidden layer
            self._Layers.append(SNeuronLayer(self._NeuronsPerHiddenLyr, self._NumInputs))
            # 其余的hidden layer
            for i in xrange(self._NumHiddenLayers - 1):
                self._Layers.append(SNeuronLayer(self._NeuronsPerHiddenLyr, self._NeuronsPerHiddenLyr)) 
            # 输出层
            self._Layers.append(SNeuronLayer(self._NumOutputs, self._NeuronsPerHiddenLyr))  
        else:
            self._Layers.append(SNeuronLayer(self._NumOutputs, self._NumInputs))

通过上面的代码我们就成功创建了一个所有权重在[-1,1]之间的神经网络。而我们的目标是通过遗传算法来不停的迭代进化神经网络，这样我们就需要接口来获取和更新神经网络的权重：

def GetWeights(self):
    weights = []
    for i in xrange(self._NumHiddenLayers + 1):
        for j in xrange(self._Layers[i]._NumNeurons):
            for k in xrange(self._Layers[i]._Neurons[j]._NumInputs):
                weights.append(self._Layers[i]._Neurons[j]._Weights[k])

    return weights

def PutWeights(self, weights):
    weightIdx = 0
    for i in xrange(self._NumHiddenLayers + 1):
        for j in xrange(self._Layers[i]._NumNeurons):
            for k in xrange(self._Layers[i]._Neurons[j]._NumInputs):
                self._Layers[i]._Neurons[j]._Weights[k] = weights[weightIdx]
                weightIdx += 1

当给出一组inputs时，神经网络需要能够给出对应的outputs，其实就是根据神经网络每层的权重依次计算结果，本层的outputs就是下一层网络层的inputs，直到计算到最后的输出层：

def Update(self, inputs):
    outputs = []
    weightIdx = 0

    if len(inputs) != self._NumInputs:
        return outputs

    for i in xrange(self._NumHiddenLayers + 1):
        if i > 0:
            inputs = copy.deepcopy(outputs)

        outputs = []
        weightIdx  = 0

        for j in xrange(self._Layers[i]._NumNeurons):
            netinput = 0.0
            NumInputs = self._Layers[i]._Neurons[j]._NumInputs

            for k in xrange(NumInputs-1):
                netinput  += (self._Layers[i]._Neurons[j]._Weights[k] * inputs[weightIdx])
                weightIdx += 1

            netinput += (self._Layers[i]._Neurons[j]._Weights[NumInputs-1] * dBias) #dBias = -1

            outputs.append(self.Sigmoid(netinput, dActivationResponse)) # dActivationResponse = 1
            weightIdx = 0

    return outputs

遗传算法

遗传算法就不再赘述，仅介绍几个算子的实现：

变异

满足变异条件的染色体，我们对每个gene在原有的基础上增加一个随机的扰动：

def Mutate(self, chromo):
    newChromo = []
    for idx, gene in enumerate(chromo):
        if random.random() < self._dMutationRate:
            gene += (random.random() - random.random()) * dMaxPerturbation # dMaxPerturbation = 0.3
        newChromo.append(gene)
    return newChromo

选择

赌轮盘，永远的赌轮盘：

def GetChromoRoulette(self):
    Slice = random.random() * self._dTotalFitness
    TheChosenOne = None

    FitnessSoFar = 0

    for i in xrange(self._iPopSize):
        FitnessSoFar += self._vecPop[i]._dFitness
        if FitnessSoFar >= Slice:
            TheChosenOne = copy.deepcopy(self._vecPop[i])
            break
    return TheChosenOne

交叉

这里有两种交叉方式：

1. 随机在所有的权重里进行交叉；

2. 将每层神经网络的的权重看成一个整体，将这个整体统一进行交叉；

def Crossover(self, mum, dad):
    baby1 = []
    baby2 = []
    if random.random() > self._dCrossoverRate or mum == dad:
        baby1 = copy.deepcopy(mum)
        baby2 = copy.deepcopy(dad)
        return baby1, baby2

    cp = random.randint(0, self._iChromoLength-1)
    baby1 = mum[:cp] + dad[cp:]
    baby2 = dad[:cp] + mum[cp:]

    return baby1, baby2

def CrossoverAtSplits(self, mum, dad):
    baby1 = []
    baby2 = []
    if random.random() > self._dCrossoverRate or mum == dad:
        baby1 = copy.deepcopy(mum)
        baby2 = copy.deepcopy(dad)
        return baby1, baby2

    cpIdx1 = random.randint(0, len(self._vecSplitPoints)-2)
    cp1 = self._vecSplitPoints[cpIdx1]
    cp2 = self._vecSplitPoints[random.randint(cpIdx1, len(self._vecSplitPoints)-1)]

    baby1 = mum[:cp1] + dad[cp1:cp2] + mum[cp2:]
    baby2 = dad[:cp1] + mum[cp1:cp2] + dad[cp2:]

    return baby1, baby2

第二种交叉方式中的_vecSplitPoints是在神经网络的类中获取的：

def CalculateSplitPoints(self):
    SplitPoints = []
    WeightCounter = 0

    for i in xrange(self._NumHiddenLayers + 1):
        for j in xrange(self._Layers[i]._NumNeurons):
            for k in xrange(self._Layers[i]._Neurons[j]._NumInputs):
                WeightCounter += 1
            SplitPoints.append(WeightCounter - 1)
    print SplitPoints
    return SplitPoints

进化

进化也很简单，保留最优的几个个体，其余的个体通过赌轮盘选择后进行交叉变异。

def Epoch(self, old_pop):
    self._vecPop = copy.deepcopy(old_pop)
    self.Reset()
    self._vecPop.sort()  # 我们为SGenome重载了__lt__
    self.CalculateBestWorstAvTot()

    vecNewPop = []
    if (iNumCopiesElite * iNumElite) % 2 == 0:
        vecNewPop = vecNewPop + self.GrabNBest(iNumElite, iNumCopiesElite)

    while len(vecNewPop) < self._iPopSize:
        mum = self.GetChromoRoulette()
        dad = self.GetChromoRoulette()
        baby1, baby2 = self.CrossoverAtSplits(mum._vecWeights, dad._vecWeights)
        baby1 = self.Mutate(baby1)
        baby2 = self.Mutate(baby2)

        vecNewPop.append(SGenome(baby1, 0.0))
        vecNewPop.append(SGenome(baby2, 0.0))

    self._vecPop = copy.deepcopy(vecNewPop)

    return self._vecPop

扫雷机

再来看看扫雷机的实现：

_dRotation – 扫雷机初始的行进方向

_lTrack – 扫雷机初始的左履带的动力

_rTrack – 扫雷机初始的右履带的动力

_dFitness – 扫雷机进化的适应度

_dScale – 扫雷机在windows里显示的大小比例

_iClosestMine – 距离扫雷机最近的地雷的索引

_vLookAt – 扫雷机行进过程中的方向

_ItsBrain – 扫雷机的大脑，也就是神经网络

_dSpeed – 扫雷机的速度

_vPosition – 扫雷机在windows里的位置

class CMinesweeper(object):
    def __init__(self):
        self._dRotation = random.random() * dTwoPi
        self._lTrack = 0.16
        self._rTrack = 0.16
        self._dFitness = dStartEnergy
        self._dScale   = iSweeperScale
        self._iClosestMine = 0
        self._vLookAt = SVector2D()
        self._ItsBrain = CNeuralNet()
        self._dSpeed = 0.0  

        self._vPosition = SVector2D(random.random()*WindowWidth, random.random()*WindowHeight)
        return

GetClosestMine用于获取当前离扫雷机最近的地雷；

CheckForMine用于检查扫雷机于地雷间的距离是否小于给定值，如果小于给定值，认为该扫雷机成功的扫除了该地雷。

def GetClosestMine(self, mines):
    closest_so_far = 99999.9
    vClosestObj = SVector2D(0.0, 0.0)

    for idx, mine in enumerate(mines):
        len_to_obj = Vec2DLength(mine - self._vPosition)
        if len_to_obj < closest_so_far:
            closest_so_far = len_to_obj
            vClosestObj = self._vPosition - mine  # 计算当前Position到最近的mine的矢量距离
            self._iClosestMine = idx

    return vClosestObj

def CheckForMine(self, mines, size):
    DistToObj = self._vPosition - mines[self._iClosestMine]
    if Vec2DLength(DistToObj) < (size + 5):
        return self._iClosestMine

    return -1

程序运行过程中，扫雷机每时每刻都在进行更新：

1. 查找最近的地雷，将最近的地雷的位置和当前扫雷机前进的方向作为神经网络的输入，得到当前扫雷机应该对左履带和右履带施加的动力

2. 根据扫雷机左右履带的动力，计算出扫雷机前进的方向，速度，以及更新后的位置

def Update(self, mines):
    inputs = []

    vClosestMine = self.GetClosestMine(mines)
    vClosestMine = Vec2DNormalize(vClosestMine)

    inputs.append(vClosestMine._x)
    inputs.append(vClosestMine._y)
    inputs.append(self._vLookAt._x)
    inputs.append(self._vLookAt._x)
    output = self._ItsBrain.Update(inputs)

    if len(output) < iNumOutputs:
        print "Output size not correct. Length of output %d, iNumOutputs %d" % (len(output), iNumOutputs)
        return False

    self._lTrack = output[0]
    self._rTrack = output[1]

    RotForce = self._lTrack - self._rTrack
    # Clamp rotation
    RotForce = -dMaxTurnRate if RotForce < -dMaxTurnRate else dMaxTurnRate if RotForce > dMaxTurnRate else RotForce

    self._dRotation += RotForce

    self._dSpeed = self._lTrack + self._rTrack
    self._vLookAt._x = -math.sin(self._dRotation)
    self._vLookAt._y = math.cos(self._dRotation)

    self._vPosition = self._vPosition + (self._vLookAt * self._dSpeed) # 注意这里都是重载了Vector的运算

    self._vPosition._x = 0 if self._vPosition._x > WindowWidth else WindowWidth if self._vPosition._x < 0 else self._vPosition._x
    self._vPosition._y = 0 if self._vPosition._y > WindowHeight else WindowHeight if self._vPosition._y < 0 else self._vPosition._y

    return True

总控

最后，将上面的神经网络、遗传算法和扫雷机类都整合到一起，通过pygame展示出来，就是我们文初所体现的效果了。

扫雷机和地雷都被归一化成对应的顶点，然后用pygame将这些顶点按照顺序依次连线，就可以画出效果：

sweeper = [SPoint(-0.5, -0.5), SPoint(-0.5, -1), SPoint(-1, -1), SPoint(-1, 1), SPoint(-0.5, 1), SPoint(-0.5, 0.5), SPoint(-0.25, 0.5), SPoint(-0.25, 1.75),SPoint(0.25, 1.75), SPoint(0.25, 0.5), SPoint(0.5, 0.5), SPoint(0.5, 1), SPoint(1,1), SPoint(1, -1), SPoint(0.5, -1), SPoint(0.5, -0.5)]

mine = [SPoint(-1, -1), SPoint(-1, 1), SPoint(1, 1), SPoint(1, -1)]

generationStr = "Generation:       " + str(self._iGenerations)
screen.blit(font.render(generationStr, True, (0, 0, 255)), (20, 20))    # 画mines
for i in xrange(self._NumMines):
    mineVB = copy.deepcopy(mine)
    mineVB = self.WorldTransform(mineVB, self._vecMines[i])
    points4Paint = []
    for item in mineVB:
        points4Paint.append((item._x, item._y))
    pygame.draw.polygon(screen, green, points4Paint, 1) # 画sweepers，最优的前iNumElite用红色画出来
for i in xrange(self._NumSweepers):
    sweeperVB = copy.deepcopy(sweeper)
    sweeperVB = self._vecSweepers[i].WorldTransform(sweeperVB)
    points4Paint = []
    for item in sweeperVB:
        points4Paint.append((item._x, item._y))
    if i < iNumElite:
        pygame.draw.polygon(screen, red, points4Paint, 1)
    else:
        pygame.draw.polygon(screen, blue, points4Paint, 1)

Pygame在每帧更新的时候，都会调用update函数来计算扫雷机和地雷的状态，当iTick达到iNumTicks(2000)的时候，进行遗传算法的新一轮迭代：

def Update(self):
    self._iTicks += 1
    if self._iTicks < iNumTicks:
        for i in xrange(self._NumSweepers):
            if self._vecSweepers[i].Update(self._vecMines) == False:
                return False

            # 查看是否找到了一个mine
            GrabHit = self._vecSweepers[i].CheckForMine(self._vecMines, dMineScale)
            if GrabHit > 0:
                self._vecSweepers[i].IncrementFitness()
                # 该mine被找到了，随机生成另外一个mine
                self._vecMines[GrabHit] = SVector2D(random.random() * self._cxClient, random.random() * self._cyClient)

            self._vecThePopulation[i]._dFitness = self._vecSweepers[i].Fitness()

    else:
        self._vecAvFitness.append(self._pGA.AverageFitness())
        self._vecBestFitness.append(self._pGA.BestFitness())

        self._iGenerations += 1

        self._iTicks = 0

        self._vecThePopulation = self._pGA.Epoch(self._vecThePopulation)

        for i in xrange(self._NumSweepers):
            self._vecSweepers[i].PutWeights(self._vecThePopulation[i]._vecWeights)
            self._vecSweepers[i].Reset()

    return True

后话

这只是遗传算法和神经网络的一个简单的应用，也很容易入门，如果有兴趣，还是强烈建议看看Mat Buckland的书，讲得真的很好。神经网络看起来很绕，自己动手敲一遍代码能让人更加深刻的理解它是怎么实现的。:)

btw: Python功底还是有待加强，python写出来的APP运行起来还是比C++慢了好多，如果不用numpy，那就更慢啦

~

~~~~~~