BEAST 教程3 引入遗传算法

29 Mar 2020

Reading time ~2 minutes

内容介绍

• 使用GA开发的等效网络替换教程2中手动配置的神经网络

• 设置捕食者-猎物模拟并共同开发更复杂的控制器

GA的使用

有关遗传算法的介绍：遗传算法

GA是一个类模板，它的模板参数接受待进化个体的类型（以及变异函数的类型，尽管我们可以忽略该参数，因为我们将使用其默认值）。为第一个模板参数指定的类需要包含某些方法，GA才能对其进行处理：

它必须具有GetGenotype方法，返回关于对象configuration（表现型）的基因（基因型）vector
它必须具有SetGenotype方法，使用基因vector作为参数并由此配置个体
必须有GetFitness方法，返回关于个体fitness的float值，越高越好。对于轮盘选择方法，fitness必须为正，但是如果个体总产生非正的fitness，可以用GeneticAlgorithm :: SetFitnessFix来fix一下。

对于可进化的个体，GA还需要其他的特征，为了简化，可以使用提供的Evolver的抽象基类。如果我们从此类继承并提供合适的GetGenotype，SetGenotype和GetFitness方法，其他的信息都会自动填充。

但其实，Evolver也不需要继承。提供的EvoFFNAnimat类配备了前馈神经网络，并能够兼容GA。EvoFFNAnimat返回神经网络的配置vector作为其基因型，一个传感器一个输入，一个控制器一个输出，并且还有自动的Control方法。

进化前馈神经网络代码如下：

class EvoMouse : public EvoFFNAnimat
{
public:
    EvoMouse(): cheesesFound(0)
    {
        This.Add("angle", NearestAngleSensor<Cheese>());
        This.InitRandom = true;
        This.InitFFN(4);
    }
virtual void OnCollision(WorldObject* obj)
    {
        Cheese* cheese;
if (IsKindOf(obj,cheese)) {
            cheesesFound++;
            cheese->Eaten();
        }
This.EvoFFNAnimat::OnCollision(obj);
    }
virtual float GetFitness()const
    {
        return cheesesFound > 0 ? static_cast<float>(cheesesFound) / static_cast<float>(powerUsed) : 0;
    }
virtual string ToString()const
    {
        ostringstream out;
        out << " Power used: " << powerUsed;
        return out.str();
    }
private:
    int cheesesFound;   // The number of cheeses collected for this run.
};

构造函数像以前一样设置传感器和initRandom，但现在也将cheesesFpund初始化为0并调用InitFFN来谁知具有两个隐藏节点的前馈网络。输入数量是1，因为只有一个传感器，而输出是2，给每个车轮一个。此1-2-2设置与手动配置的网络匹配，因此有充分的理由相信GA将能找到合适的网络。

OnCollision和之前一样，只是所吃的每种奶酪都会将cheesesFound加1，并在最后调用EvoFFNAnimat::OnCollision。

最后，GetFitness返回找到的cheese数量，再除以powerUsed，即评估期间所有控件的激活总量。这样做会惩罚老鼠，使他们往一个方向上尽可能快地前进，让其覆盖的面积更大，捡起更多的奶酪。

现在我们还需要设置仿真，这次小鼠将作为Population而不是Group进入World。

Population是与Group相似的容器，但也有相关的GA，每次在最后为Population做评估。

class MouseSimulation : public Simulation
{
    Population<EvoMouse>        theMice;
    GeneticAlgorithm<EvoMouse>  theGA;
    Group<Cheese>               theCheeses;
public:
    MouseSimulation():
    theGA(0.7f, 0.05f),
    theMice(30, theGA),
    theCheeses(50)
    {
        This.theGA.SetSelection(GA_RANK);
        This.theGA.SetParameter(GA_RANK_SPRESSURE, 2.0);
This.Add("Mice",        theMice);
        This.Add("Cheeses",     theCheeses);
    }
};

evomice的Population配置了对做EvoMouse对象上运行的GA的引用，这个GA将在每一代的末尾使用。

用2值的选择压力而不是轮盘选择指定了等级选择。这意味着做generation末期，个体的繁殖机会会取决于他们在总Population的排名。

选择压力范围在一到二之间，1意味着所有个体有相等机会进入下个generation，2以为着在12个population中，第六个个体具有一半的繁殖机会，第三个有3/4，第九个有1/4，以此类推。

接着进行编译和运行模拟，这时Animat会开始活动，但它们还不知道奶酪是什么。在特定时间段结束时，Animat会被带出世界并通过GA评估，他们的后代将成为下一代。如果想加快进程，可以在Simulation菜单选择High Speed。

过了几个generation后，我们可以点cancel看看mice是否在做有意义的行为。在大约200代之后，应该就能看到一个不错的效果。

协同进化模拟

现在可以尝试两个种群的协同进化仿真，每个种群的fitness都依赖于另一个种群的fitness。Predator类和Mouse类相似，它们寻找猎物并获得分数，猎物被抓到就受惩罚。捕食者具有传感器。

Predator和Prey类代码：

// Forward declaration for Prey
class Predator;

class Prey : public EvoFFNAnimat
{
public:
    Prey():timesEaten(1)
    {
        This.Add("right", ProximitySensor<Predator>(PI/1.05, 100.0, -PI/2));
        This.Add("left", ProximitySensor<Predator>(PI/1.05, 100.0, PI/2));

        This.InitFFN(4);
        This.InitRandom = true;
        This.MinSpeed = 0;
        This.MaxSpeed = 100;
    }

    void Eaten()
    {
        This.timesEaten++;
        This.Location = myWorld->RandomLocation();
    }

    float GetFitness()const
    {
        return 1.0f / static_cast<float>(This.timesEaten);
    }

private:
    int timesEaten;
};

class Predator : public EvoFFNAnimat
{
public:
    Predator():preyEaten(0)
    {
        This.Add("left", ProximitySensor<Prey>(PI/5, 200.0, -PI/20));
        This.Add("right", ProximitySensor<Prey>(PI/5, 200.0, PI/20));

        This.InitFFN(4);
        This.InitRandom = true;

        This.MinSpeed = 0;
        This.MaxSpeed = 100;
        This.Radius = 10.0;
    }

    void OnCollision(WorldObject* obj)
    {
        Prey* ptr;

        if (IsKindOf(obj,ptr)) {
            This.preyEaten++;
            ptr->Eaten();
        }

        This.FFNAnimat::OnCollision(obj);
    }

    float GetFitness()const { return preyEaten; }

private:
    int preyEaten;
};

Prey类中引用了Predator，所以要在prey前先声明Predator。

Prey的fitness函数：越fit，每次就吃得越少，所以每次吃的时候都应从prey的fitness中减1。最开始就提过，使用轮盘时无法使用负值，对此有两个办法：

用SetFitnessFix调整scores，可调整三个选项：

GA_IGNORE是缺省值，不对scores更改

GA_CLAMP设置低于0的分数设置为0

GA_FIX线性调整，使最低分变为0

确保GetFitness返回正值，通过返回个人被进食次数的倒数，使较高的数字变低但是保持正值。

可以根据自己的条件设置更大的Population数量，但是太大了会使World变得过于拥挤，但可以试着使用World :: SetWidth和World :: SetHeight来扩大World，但如果太大了Objects会太小，导致看不到。

class ChaseSimulation : public Simulation
{
    GeneticAlgorithm<Predator> gaPred;
    GeneticAlgorithm<Prey> gaPrey;
    Population<Predator> popPred;
    Population<Prey> popPrey;

public:
    ChaseSimulation():
    gaPred(0.7f, 0.1f), gaPrey(0.7f, 0.1f), 
    popPred(30,gaPred), popPrey(30,gaPrey)
    {
        This.gaPred.SetSelection(GA_RANK);
        This.gaPred.SetParameter(GA_RANK_SPRESSURE, 2.0);
        
        This.gaPrey.SetSelection(GA_RANK);
        This.gaPrey.SetParameter(GA_RANK_SPRESSURE, 2.0);

        This.popPred.SetTeamSize(5);
        This.popPrey.SetTeamSize(10);
        This.SetAssessments(30);

        This.Add("Predators", popPred);
        This.Add("Prey", popPrey);
    }
};

在仿真中，每个generation做30个评估，而每个Predator将会有5个评估，每个Prey有10个评估。

仿真过了几百个generation后，就可以看到一些比较有说服力的结果。

BEAST教程索引

BEAST 教程0 代码说明

BEAST 教程1 创建第一个Animat

BEAST 教程2 添加Object和交互式Animat

BEAST 教程3 引入遗传算法

Reference

https://minerva.leeds.ac.uk/webapps/blackboard/content/listContent.jsp?course_id=_505438_1&content_id=_6865832_1&mode=reset

进化学习机器学习