AI: Genetic Evolution of Virtual Fish

• Download application - 21 KB
• Download source - 78.5 KB

Introduction

Another one of evolution experiments. I am using the Parallel Neural Networks library from nuget for its BackPropagationNetwork class for reinforcement learning. Genetic mutations, reinforcement learning and proper selection makes the fish learn how to find food. Here, a Fish is an entity with a neural network, a color, a size, aerodynamic efficiency and a sensor, which feeds the location of food by its angle and distance to the corresponding neural input. The properties of fish are contained within a FishChromosomes, which can be mated with another chromosome to yield a mutated offspring.

The output of the neural network is calculated and is used to compute the heading angle and the speed of the fish, which completes the loop and the fish ‘lives’ in our environment. Number of input neurons corresponds to the resolution of the sensor on the fish. All this happens inside the Fish class.

Every FishChromzomes has physical genes and mental genes, physical genes being the size, aerodynamic efficiency (which control the speed), and color. Mental genes is just the NetworkData of the neural network running the fish. A fish of high aerodynamic efficiency moves fast and a bigger fish requires more food to survive, Color does not affect the performance of the fish.

Reinforcement Learning

The fish has a short term memory of previous 10 steps it has taken till that instance, which is used to train the fish after it successfully feeds itself. When the fish successfully reaches the food, previous 10 steps stored in queue are used to train the neural network on the fish, to make the fish better at finding food in such manner. Hence, a fish learns as it goes. All this is implemented in the FishLearn Class. Each step taken by the fish is added to a queue to be used on the event when the fish feeds.

public class FishLearn
{
    public Fish Fish;
    public Queue<neuralnetworks.dataset> LearnQueue;
    public BackgroundWorker worker;

    public FishLearn(Fish fish)
    {
        Fish = fish;
        LearnQueue = new Queue<neuralnetworks.dataset>(15);

        worker = new BackgroundWorker();

        worker.DoWork += ((object e, DoWorkEventArgs w) =>
        {
            Fish.FishNeural.BatchBackPropogate(LearnQueue.ToArray(),
                                              (int)w.Argument, 0.1, 0.1, worker);
        });
    }

    public void AddStep(IEnumerable<double> neuralInputs, IEnumerable<double> neuralOutputs)
    {
        NeuralNetworks.DataSet fishio = new NeuralNetworks.DataSet() {
                                                Inputs = neuralInputs.ToArray(),
                                                Outputs = neuralOutputs.ToArray()
                                        };
        try
        {
            LearnQueue.Enqueue(fishio);
        }
        catch
        {
            LearnQueue.Dequeue();
            LearnQueue.Enqueue(fishio);
        }
    }

    public void LearnPreviousSteps(int iterations)
    {
        worker.WorkerReportsProgress = true;
        if(!worker.IsBusy)
            worker.RunWorkerAsync(iterations);
    }
}

Reinforcement learning results in a constantly changing neural network of each fish in the simulation, learning the previous steps when the fish feeds.

Genetic Algorithm

When properties of two entities are genetically mutated, both of their properties are mashed up to produce a new entity with different features. As our fish in the simulation are feeding, the feed count is maintained by each fish and when the timer is reset, the best fish are chosen and interbred to produce new individuals. As neural networks are all different for each fish, the offspring will have a unique neural network of their own, hence, different behavior. In our application, the physical genes of the fish are mixed in the following manner.

Mental Genes

A crossover point to selection to enable merging of the two neural networks. NetworkData objects are used for this merging.

if (frontback)
{
    foreach (ConnectionData c in guppiedata.Connections.Where
    (r => r.From.Layer == guppiedata.InputLayerId))
        c.Weight = one.Connections.Find(r => (r.From.Layer == c.From.Layer)
                                          && (r.From.Node == c.From.Node)
                                          && (r.To.Layer == c.To.Layer)
                                          && (r.To.Node == c.To.Node)).Weight;

    foreach (ConnectionData c in guppiedata.Connections.Where
    (r => r.To.Layer == guppiedata.OutputLayerId
                                                                && r.To.Node < crossoverpoint1))
        c.Weight = one.Connections.Find(r => (r.From.Layer == c.From.Layer)
                                          && (r.From.Node == c.From.Node)
                                          && (r.To.Layer == c.To.Layer)
                                          && (r.To.Node == c.To.Node)).Weight;

    foreach (ConnectionData c in guppiedata.Connections.Where(r =>
    r.To.Layer == guppiedata.OutputLayerId
                                          && r.To.Node >= crossoverpoint1))
        c.Weight = two.Connections.Find(r => (r.From.Layer == c.From.Layer)
                                          && (r.From.Node == c.From.Node)
                                          && (r.To.Layer == c.To.Layer)
                                          && (r.To.Node == c.To.Node)).Weight;
}

Physical Genes

A crossover point is randomly taken with the length of the list as the maximum value. Two lists of genes are copied on both sides of the crossover points.

public static List<gene> MixGenesUp(List<gene> one, List<gene> two)
{
    int crossoverpoint = RandomProvider.Random.Next(one.Count);
    List<gene> genes = new List<gene>();
    for (int i = 0; i < one.Count; i++)
    {
        if (i <= crossoverpoint)
            genes.Add(new Gene() { Name = one[i].Name, Value = one[i].Value });
        else
            genes.Add(new Gene() { Name = two[i].Name, Value = two[i].Value });
    }
    return genes;
}

The Simulation

The food in the simulation is autogenerated each time it is consumed. The fish cannot see each other but can see all food particle locations at any given time. The sensor values are calculated and applied to the neural networks, the output is read, and the fish’s heading angle and forward speed are calculated and applied.

public void Live(FoodGenerator foodGen, IEnumerable<fish> fishes)
{
    Sensor.UpdateSensors(foodGen.FoodParticles);
    FishNeural.ApplyInput(Sensor.FoodSensors);
    FishNeural.CalculateOutput();

    CheckFood(foodGen);

    Age += 0.005;

    if (Age > 10)
    {
        IsDead = true;
        if (Dead != null)
            Dead(this, new DeadEventArgs() { });
    }

    IEnumerable<double> Outputs = FishNeural.ReadOutput();

    FishLearn.AddStep(Sensor.FoodSensors, Outputs);
    HeadingAngle = (Math.Atan(Outputs.ElementAt(1)/Outputs.ElementAt(2))-(Math.PI/4));
    MoveForward(Outputs.ElementAt(0));
}

Backpropagation class from the neural network library is directly used for this purpose.

Selection Procedure

Selecting only one or two fish to re-spawn the entire next generation may result in loss of desired features, hence the two fishes from top 3 fishes are selected and mated to produce the offspring.

public void NextGeneration()
{
    IEnumerable<fish> topFishes = fishes.OrderByDescending(r => r.NumFoodEaten).Take(5);
    int totalfood = 0;
    generation ++;
    fishes.ForEach(r => totalfood += r.NumFoodEaten);
    status_text_block.Text = "Generation: " +
                             generation.ToString() +
                             ", Total Food: " +
                             totalfood.ToString();

    graphWindow.AddDataPoint(generation, totalfood);

    for (int i = 0; i < fishes.Count; i++)
    {
        if(i < fishes.Count/3)
            fishes[i] = new Fish(FishChromozomes.Mate
            (topFishes.ElementAt(0).Chromozomes, topFishes.ElementAt(1).Chromozomes));
        else if(i < fishes.Count*2/3)
            fishes[i] = new Fish(FishChromozomes.Mate
            (topFishes.ElementAt(0).Chromozomes, topFishes.ElementAt(2).Chromozomes));
        else
            fishes[i] = new Fish(FishChromozomes.Mate
            (topFishes.ElementAt(1).Chromozomes, topFishes.ElementAt(2).Chromozomes));
    }
}

Result

Initially the fish barely know how to reach the food, some keep circling around like baby zebra fish in petri dish. Gradually, generation after generation, the fish acquire traits which enable them to consume more food. The result is visible, as after a few generations, the fish directly go for the food, gaining a flock behavior. Overall fitness of the population is nothing but the total food consumed by the fish plotted in the graph window and a consistence increase is seen, generation after generation. This proves that the simulation is a success and genetic mutation is successfully producing fitter individuals. Another trait that emerged is shooting for the mid point of two food particles. Experiments have shown that when a frog is shown two insects some distance away, the frog initially moves towards the mid-direction of the food sources, then after a threshold distance, it chooses one side. Same behavior is seen in our fish after a few generations.