神经网络从被人忽悠到忽悠人(三)

引子

在上一章，讲过bp神经网络虽然取得了很大的进步，但它本身存在着一些无法避免的问题，其中一个比较困惑的应该是局部最优解问题。

推荐阅读：

神经网络从被人忽悠到忽悠人(一)

只接触那些你已经喜欢的东西是有风险的，即你可能会卷入一个以自我为中心的漩涡，从而对任何与你的标准存在细微差异的事情都视而不见，即使你原本会喜欢它。这种现象被称为“过滤器泡沫”（filter bubble），技术术语是“过适”（overfitting）。 — 必然

所谓的局部最优解的问题就是：卡在一个小高点的位置，而却认为自己在最高点，导致训练提前结束。

很多优化的算法相继提出，目前来说比较火热的也许应该算是多种算法的结合。在2015 “机器学习”年度回顾中使用遗传算法进化的神经网络开发了能够自己玩超级玛丽的算法。

遗传算法

9世纪中叶，达尔文创立了科学的生物进化学说，以自然选择为核心的达尔文进化论，第一次对整个生物界的发生、发展，作出了唯物的、规律性的解释，推翻了特创论等唯心主义形而上学在生物学中的统治地位，使生物学发生了一个革命变革。
神经网络从被人忽悠到忽悠人(三)
达尔文

在重要著作《物种起源》：他使用在1830年代环球科学考察中积累的资料，试图证明物种演化是通过自然选择和人工选择实现的。

1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法（Genetic Algorithms）”一词简称GA，他抓住了《物种起源》两个重要的规则：交叉和变异。把这两个过程用算法的方式完美的演绎出。

Super Mario World的人工智能

2002年，Kenneth O. Stanley 在Massachusetts Institute of Technology上发表了，《Evolving Neural Networks throughAugmenting Topologies》（神经网络进化拓扑结构），简称NEAT。

简单的来看，神经网络进化拓扑结构用的是遗传算法和神经网络的结合，能够最大程度的克服神经网络陷入局部最小值的问题。

2015年SethBling用他开发了一款能玩Super Mario World的人工智能。并开源了自己的代码，短短的一千多行的代码，就能够自己学习，并能够通关超级玛丽。

神经网络从被人忽悠到忽悠人(三)

代码使用lua写成，一千多行的代码，结构也非常的清晰。

代码用神经网络算法计算权值，用遗传算法（交叉和变异）优化权重。

神经网络的权值计算过程：

function evaluateNetwork(network, inputs)
    table.insert(inputs, 1)
    if #inputs ~= Inputs then
        console.writeline("Incorrect number of neural network inputs.")
        return {}
    end

    for i=1,Inputs do
        network.neurons[i].value = inputs[i]
    end

    for _,neuron in pairs(network.neurons) do
        local sum = 0
        for j = 1,#neuron.incoming do
            local incoming = neuron.incoming[j]
            local other = network.neurons[incoming.into]
            sum = sum + incoming.weight * other.value
        end

        if #neuron.incoming > 0 then
            neuron.value = sigmoid(sum)
        end
    end

    local outputs = {}
    for o=1,Outputs do
        local button = "P1 " .. ButtonNames[o]
        if network.neurons[MaxNodes+o].value > 0 then
            outputs[button] = true
        else
            outputs[button] = false
        end
    end

    return outputs
end

交叉：

function crossover(g1, g2)
    -- Make sure g1 is the higher fitness genome
    if g2.fitness > g1.fitness then
        tempg = g1
        g1 = g2
        g2 = tempg
    end

    local child = newGenome()

    local innovations2 = {}
    for i=1,#g2.genes do
        local gene = g2.genes[i]
        innovations2[gene.innovation] = gene
    end

    for i=1,#g1.genes do
        local gene1 = g1.genes[i]
        local gene2 = innovations2[gene1.innovation]
        if gene2 ~= nil and math.random(2) == 1 and gene2.enabled then
            table.insert(child.genes, copyGene(gene2))
        else
            table.insert(child.genes, copyGene(gene1))
        end
    end

    child.maxneuron = math.max(g1.maxneuron,g2.maxneuron)

    for mutation,rate in pairs(g1.mutationRates) do
        child.mutationRates[mutation] = rate
    end

    return child
end