【技术分享】NEAT 进化神经网络

简介

"NeuroEvolution of Augmenting Topologies"，简称：(NEAT) 它一种基于遗传算法的神经网络训练方法，通过进化神经网络的结构和权重来提高网络性能，可以将其视为一种进化人工神经网络的实现方式，在NEAT不断地交叉、变异操作下，会生成新一代的神经网络，使用适应性得分筛选出最优秀的网络作为下一代的父代，来逐步改进和优化神经网络的结构和性能。

NEAT 基本原理

初始化种群：开始时会创建一个初始的神经网络种群，初始种群中的每个个体都是一个具有随机连接和权重的简单神经网络。
评估适应性：对于每个个体，使用其神经网络执 行任务（如玩游戏）并评估其适应性得分，适应性得分用于衡量个体在任务中的表现。
选择繁殖池：根据适应性得分，选择一部分个体作为繁殖池。得分较高的个体有更大的概率被选中，以保留优秀的基因。
交叉和变异操作：选择两个个体，交叉组合基因，随机改变连接和权重。
新一代个体：通过交叉和变异操作生成的新个体被加入到新一代的种群中。
重复迭代：重复进行第2到第5步，直到达到停止条件（如达到预设的适应性阈值、达到最大迭代次数等）。
输出最优个体：在最后一代种群中，选择适应性最高的个体作为最优个体，对应的神经网络结构和权重被视为最佳解决方案。

数学公式

Sigmoid函数：
$\text{sigmoid}(x) = \frac{1}{1 + e^{-x}}$

交叉操作：
$\text{childMat}[:x], \text{childMat}[x:] = \text{mat1}[:x], \text{mat2}[x:]$

变异操作：
$\text{mat}[i][j] = \text{random.uniform}(0, 1)$

AI 谷歌小恐龙

开始的神经网络结构是比较简单的，只有很少的连接点，等玩久了神经网络会慢慢通过遗传操作生成新的结构，然后适应评估筛选出最优秀的个体。

AI 接球游戏

以上的演示中可以发现，NEAT神经网络是可以快速的适应游戏，通过遗传算法创新性和进化，可以快速优化和调整，在进化的过程表现得十分出色。

AI 小车自动驾驶

AI小车游戏源码（NEAT算法）

以下实现的移动方块接小球游戏（并没有使用neat，只是一个简单的前馈神经网络）。

AI 接球游戏源码

# 需要安装第三方库
pip install pygame
pip install numpy

# main.py 文件

import pickle
import random
import pygame
import math
from NeuralNetwork import NeuralNetwork
import numpy as np

class Bar:
    def __init__(self):
        self.length = 120
        self.height = 16
        self.bar_x = (Game.width-self.length)/2
        self.bar_y = Game.height-self.height
        self.center_x = (Game.width/2)
        self.center_y = Game.height-(self.height/2)
        self.radius = 15
        self.ball_x = self.center_x
        self.ball_y = self.bar_x+(self.length)/2-(2*self.radius)
        self.ball_center_x = random.randrange(15, Game.width-15)
        self.ball_center_y = random.randrange(Game.height)
        self.ball_vel_x = 10
        self.ball_vel_y = 10
        self.bar_vel = 0
        self.score = 0
        self.fitness = 0
        self.distance = 0
        self.brain = NeuralNetwork(9, 4, 2)

    def showBar(self, x, y):
        pygame.draw.rect(Game.gameDisplay, Game.black, [
                         x, y, self.length, self.height])

    def showBall(self, x, y):
        pygame.draw.circle(Game.gameDisplay, Game.gray,
                           (int(x), int(y)), self.radius)

    def predict(self):
        # Quadrant I
        if self.ball_center_x > self.center_x:
            dis1 = self.calculateDistance(
                (self.ball_center_x), (self.ball_center_y+self.radius))
        else:
            dis1 = -1
        dis1 /= 1000

        if self.ball_center_x < self.center_x:
            dis2 = self.calculateDistance(
                (self.ball_center_x), (self.ball_center_y+self.radius))
        else:
            dis2 = -1
        dis2 /= 1000

        if self.ball_center_x == self.center_x:
            dis3 = self.calculateDistance(
                (self.ball_center_x), (self.ball_center_y+self.radius))
        else:
            dis3 = -1
        dis3 /= 1000
        vel_x = self.ball_vel_x
        vel_x /= 1000
        vel_y = self.ball_vel_y
        vel_y /= 1000
        dis_wall1 = self.bar_x
        dis_wall2 = (Game.width) - (self.bar_x)
        dis_ball1 = math.sqrt((self.ball_center_x-self.bar_x)**2 +
                              (self.ball_center_y+self.radius-(Game.height-self.height))**2)
        dis_ball2 = math.sqrt((self.ball_center_x-(self.bar_x+self.length))
                              ** 2+(self.ball_center_y+self.radius-(Game.height-self.height))**2)
        dis_wall1 /= Game.width
        dis_wall2 /= Game.width
        dis_ball1 /= 1000
        dis_ball2 /= 1000

        inputs = [dis1, dis2, dis3, dis_wall1, dis_wall2,
                  dis_ball1, dis_ball2, vel_x, vel_y]
        inputs = np.array(inputs)
        inputs = np.reshape(inputs, (9, 1))
        output = self.brain.feedforward(inputs)
        if output[0] > output[1]:
            self.moveRight()
        else:
            self.moveLeft()

    def moveLeft(self):
        if self.bar_x != 0:
            self.bar_x -= 10
            self.center_x -= 10
            self.distance += 1

    def moveRight(self):
        if self.bar_x != (Game.width - self.length):
            self.bar_x += 10
            self.center_x += 10
            self.distance += 1

    def updateVelocity(self):
        self.ball_center_x += self.ball_vel_x
        self.ball_center_y += self.ball_vel_y

    def isColliding(self):
        if (self.ball_center_y + self.radius) >= (Game.height - self.height):
            if self.ball_center_x >= self.bar_x and self.ball_center_x <= (
                    self.bar_x + self.length):
                return True

    def isCollidingSide(self):
        if self.ball_center_x >= Game.width or self.ball_center_x - self.radius <= 0:
            return True

    def isCollidingAbove(self):
        if self.ball_center_y <= 0:
            return True

    def calculateDistance(self, x, y):
        return math.sqrt((self.center_x-x)**2+(self.center_y-y)**2)


class Game():
    width = 900
    height = 600
    black = (0, 0, 0)
    gray = (70, 70, 70)
    gameDisplay = pygame.display.set_mode((width, height))
    population = 200
    generation = 1
    bars = []
    savedBars = []
    highscore = []
    score = []

    def __init__(self):

        pygame.init()
        self.clock = pygame.time.Clock()
        self.bar = Bar()
        self.gameLoop()

    def gameLoop(self):
        gameExit = False
        font = pygame.font.SysFont(None, 25)
        for i in range(Game.population):
            self.bars.append(Bar())
        while not gameExit:

            msg = 'Gen : ' + str(self.generation)
            screen_text = font.render(msg, True, (0, 0, 0))
            self.gameDisplay.blit(screen_text, [10, 10])
            for bar in self.bars:
                bar.predict()
                bar.updateVelocity()
                for event in pygame.event.get():
                    if event.type == pygame.QUIT:
                        gameExit = True
                    if event.type == pygame.KEYDOWN:
                        if event.key == pygame.K_s:
                            print('true')
                            self.showBest()
                if bar.isColliding():
                    bar.ball_vel_y = -bar.ball_vel_y
                    bar.score += 10
                if bar.bar_x == 0 or bar.bar_x == Game.width-bar.length:
                    bar.score -= 1
                if len(self.highscore) > 0:
                    if bar.score >= max(self.highscore):
                        self.bestBar = bar.brain.serialize()
                        self.highscore.append(bar.score)
                if bar.isCollidingSide():
                    bar.ball_vel_x = -bar.ball_vel_x
                if bar.isCollidingAbove():
                    bar.ball_vel_y = -bar.ball_vel_y
                if bar.ball_center_y > Game.height:
                    self.savedBars.append(bar)
                    self.score.append(bar.score)
                    self.bars.remove(bar)
                    if len(self.bars) == 0:
                        self.generation += 1
                        self.highscore.append(max(self.score))
                        self.score = []
                        ga = GA(self)
                        ga.nextGen()

                bar.showBar(bar.bar_x, bar.bar_y)
                bar.showBall(bar.ball_center_x, bar.ball_center_y)
            pygame.display.update()
            self.gameDisplay.fill((255, 255, 255))
            self.clock.tick(60)
        pygame.quit()
        quit()

    def showBest(self):
        self.gameDisplay.fill((135, 206, 250))
        bar = Bar()
        bar.brain = pickle.loads(self.bestBar)
        gameExit = False
        while not gameExit:
            bar.predict()
            bar.updateVelocity()
            if bar.isColliding():
                bar.ball_vel_y = -bar.ball_vel_y
                bar.score += 1
            if bar.isCollidingSide():
                bar.ball_vel_x = -bar.ball_vel_x
            if bar.isCollidingAbove():
                bar.ball_vel_y = -bar.ball_vel_y
            if bar.ball_center_y > Game.height:
                return
            pygame.display.update()
            self.gameDisplay.fill((135, 206, 250))
            self.clock.tick(30)
        pygame.quit()
        quit()


class GA(Game):
    def __init__(self, game):
        self.game = game

    def nextGen(self):
        self.calculateFitness()
        for i in range(len(self.savedBars)):
            self.game.bars.append(self.pickOne())
        self.game.savedBars = []
        self.savedBars = []

    def calculateFitness(self):
        sum = 0
        self.savedBars = self.game.savedBars
        for i in range(len(self.savedBars)):
            self.savedBars[i].fitness = (
                self.savedBars[i].score)**2 + (pow(2, self.savedBars[i].distance))
            sum += self.savedBars[i].fitness

        for i in range(len(self.savedBars)):
            self.savedBars[i].fitness /= sum

    def pickOne(self):
        r = random.uniform(0, 1)
        index = 0
        while r > 0:
            r = r-self.savedBars[index].fitness
            index += 1
        index -= 1

        r2 = random.uniform(0, 1)
        index2 = 0
        while r2 > 0:
            r2 = r2-self.savedBars[index2].fitness
            index2 += 1
        index2 -= 1

        child = Bar()
        bar = self.savedBars[index]
        bar2 = self.savedBars[index2]
        child.brain.in_hidden1_weights = bar.brain.crossover(
            bar.brain.in_hidden1_weights, bar2.brain.in_hidden1_weights)
        child.brain.in_hidden1_biases = bar.brain.crossover(
            bar.brain.in_hidden1_biases, bar2.brain.in_hidden1_biases)
        child.brain.hidden1_output_weights = bar.brain.crossover(
            bar.brain.hidden1_output_weights, bar2.brain.hidden1_output_weights)
        child.brain.hidden1_output_biases = bar.brain.crossover(
            bar.brain.hidden1_output_biases, bar2.brain.hidden1_output_biases)

        child.brain.mutate(child.brain.in_hidden1_weights, 0.3)
        child.brain.mutate(child.brain.in_hidden1_biases, 0.3)
        child.brain.mutate(child.brain.hidden1_output_weights, 0.3)
        child.brain.mutate(child.brain.hidden1_output_biases, 0.3)
        return child


if __name__ == '__main__':
    game = Game()

# NeuralNetwork.py 文件

import numpy as np
import math
import random
import pickle

class NeuralNetwork():
    def __init__(self,input_nodes,hidden_nodes1,output_nodes):
        self.input_nodes = input_nodes
        self.hidden_nodes1 = hidden_nodes1
        self.output_nodes = output_nodes
        self.in_hidden1_weights = np.random.rand(self.hidden_nodes1,self.input_nodes)
        self.hidden1_output_weights = np.random.rand(self.output_nodes,self.hidden_nodes1)
        self.in_hidden1_biases = np.random.rand(self.hidden_nodes1,1)
        self.hidden1_output_biases = np.random.rand(self.output_nodes,1)
        self.sigmoid_v = np.vectorize(self.sigmoid)

    def sigmoid(self,x):
        return (1/(1+math.exp(-x)))

    def feedforward(self,inputs):
        self.inputs = inputs
        self.hidden_layer1 = self.in_hidden1_weights.dot(self.inputs)
        self.hidden_layer1=self.sigmoid_v(self.hidden_layer1+self.in_hidden1_biases)
        self.output = self.hidden1_output_weights.dot(self.hidden_layer1)
        self.output =self.sigmoid_v(self.output+self.hidden1_output_biases)
        return self.output

    def crossover(self,mat1,mat2):
        childMat = np.zeros((mat1.shape[0],mat1.shape[1]))
        x = mat1.shape[0]//2
        childMat[:x],childMat[x:] = mat1[:x],mat2[x:]
        return childMat

    def mutate(self,mat,rate):
        for i in range(mat.shape[0]):
            if rate > (random.uniform(0,1)):
                for j in range(mat.shape[1]):
                    mat[i][j] = random.uniform(0,1)
    def serialize(self):
        return pickle.dumps(self)

代码知识点

平方根函数 math.sqrt()：用来计算两点之间的距离，用于碰撞检测和位置计算。
幂函数 pow()：用来计算适应度的幂值，用于衡量个体的适应程度。
随机数生成函数 random.uniform()：用于生成随机数，用于选择个体进行交叉和变异操作。
算法中实现了一个简单的神经网络（NeuralNetwork）来预测下一步的移动方向，神经网络输入是游戏中的一些状态信息，如：球的位置、速度以及挡板的位置，经过计算后输出一个移动方向（左或右），这里的神经网络是手动实现的，不依赖于现有的神经网络库。

在代码中还使用了遗传算法（Genetic Algorithm）来优化神经网络的结构和权重，每一代中会根据个体的适应度进行选择、交叉和变异操作，生成新一代的个体适应度的计算基于个体的得分和运动距离。