Can I kill 10% of bottom performing gnomes?

[robertvo]

Hi Colin, is there a way to kill X% of bottom performing gnomes and replace them with totally random gnomes for each generation?

for example I'd like to kill 10% of the worst performers and replace them with new random ones. (Not offspring)

I feel like this would prevent stagnation in my case. Is this functionality already there?

[colgreen]

No, this behaviour is not built-in.

However, the evolution algorithm does already discard the bottom n% of genomes, this is just 1 - elitismProportion. Therefore I think the easiest way to achieve what you describe is to modify this method on the NeatGenome class:

public NeatGenome CreateOffspring(uint birthGeneration)

This is the method that is called to produce new offspring asexually. You could simply put a conditional branch in there to create random genomes for some proportion of calls.

E.g.

public NeatGenome CreateOffspring(uint birthGeneration)
{
    // Enter the section 30% of the time.
    if(_genomeFactory.Rng.NextDouble() < 0.3)
    {
        return _genomeFactory.CreateGenome(birthGeneration);
    }

    // Make a new genome that is a copy of this one but with a new genome ID.
    NeatGenome offspring = _genomeFactory.CreateGenomeCopy(this, _genomeFactory.NextGenomeId(), birthGeneration);

    // Mutate the new genome.
    offspring.Mutate();
    return offspring;
}

I think that should work.

I'm not sure if the approach will prevent stagnation though. The new random genomes will probably always have very low fitness, so will almost immediately be culled in favour of yet more new random genomes!

[colgreen]

What you could try instead is to set both the elitism and selection percentages high, say 50% to 75%. This means that many more poor genomes remain in the population between generations, which should increase diversity.

If you do this you could also increase the population size... if the evaluation scheme is deterministic such that the fitness score doesn't have to be recalculated for a genome evaluated in a previous generation. Make sense?

[robertvo]

Thanks for the answer!! Althou I have to call InnovationIdGenerator.Reset() before CreateGenome(birthGeneration)

and then sometimes I'm getting problems related to the ID: "Hidden neuron gene is out of order and/or a duplicate."

or ArgumentException: An item with the same key has already been added.

So not sure what to do with the ID :(

[robertvo]

Could you please advise Colin? I'm having a tough time with the IDs

[colgreen]

Yeh ok, you can't reset the ID generator like that. Here's how you do it. Quickly tired it here and seems to be working...

Add this method to NeatGenomeFactory.cs

    public NeatGenome CreateRandomGenome(uint birthGeneration)
    {   
        NeuronGeneList neuronGeneList = new NeuronGeneList(_inputNeuronCount + _outputNeuronCount);
        NeuronGeneList inputNeuronGeneList = new NeuronGeneList(_inputNeuronCount); // includes single bias neuron.
        NeuronGeneList outputNeuronGeneList = new NeuronGeneList(_outputNeuronCount);

        UInt32IdGenerator idGen = new UInt32IdGenerator();

        // Create a single bias neuron.
        uint biasNeuronId = idGen.NextId;
        if(0 != biasNeuronId) 
        {   // The ID generator must be reset before calling this method so that all generated genomes use the
            // same innovation ID for matching neurons and structures.
            throw new SharpNeatException("IdGenerator must be reset before calling CreateGenome(uint)");
        }

        // Note. Genes within nGeneList must always be arranged according to the following layout plan.
        //   Bias - single neuron. Innovation ID = 0
        //   Input neurons.
        //   Output neurons.
        //   Hidden neurons.
        NeuronGene neuronGene = CreateNeuronGene(biasNeuronId, NodeType.Bias);
        inputNeuronGeneList.Add(neuronGene);
        neuronGeneList.Add(neuronGene);

        // Create input neuron genes.
        for(int i=0; i<_inputNeuronCount; i++)
        {
            neuronGene = CreateNeuronGene(idGen.NextId, NodeType.Input);
            inputNeuronGeneList.Add(neuronGene);
            neuronGeneList.Add(neuronGene);
        }

        // Create output neuron genes. 
        for(int i=0; i<_outputNeuronCount; i++)
        {
            neuronGene = CreateNeuronGene(idGen.NextId, NodeType.Output);
            outputNeuronGeneList.Add(neuronGene);
            neuronGeneList.Add(neuronGene);
        }

        // Define all possible connections between the input and output neurons (fully interconnected).
        int srcCount = inputNeuronGeneList.Count;
        int tgtCount = outputNeuronGeneList.Count;
        ConnectionDefinition[] connectionDefArr = new ConnectionDefinition[srcCount * tgtCount];

        for(int srcIdx=0, i=0; srcIdx<srcCount; srcIdx++) {
            for(int tgtIdx=0; tgtIdx<tgtCount; tgtIdx++) {
                connectionDefArr[i++] = new ConnectionDefinition(idGen.NextId, srcIdx, tgtIdx);
            }
        }

        // Shuffle the array of possible connections.
        SortUtils.Shuffle(connectionDefArr, _rng);

        // Select connection definitions from the head of the list and convert them to real connections.
        // We want some proportion of all possible connections but at least one (Connectionless genomes are not allowed).
        int connectionCount = (int)NumericsUtils.ProbabilisticRound(
            (double)connectionDefArr.Length * _neatGenomeParamsComplexifying.InitialInterconnectionsProportion,
            _rng);
        connectionCount = Math.Max(1, connectionCount);

        // Create the connection gene list and populate it.
        ConnectionGeneList connectionGeneList = new ConnectionGeneList(connectionCount);
        for(int i=0; i<connectionCount; i++)
        {
            ConnectionDefinition def = connectionDefArr[i];
            NeuronGene srcNeuronGene = inputNeuronGeneList[def._sourceNeuronIdx];
            NeuronGene tgtNeuronGene = outputNeuronGeneList[def._targetNeuronIdx];

            ConnectionGene cGene = new ConnectionGene(def._innovationId,
                                                    srcNeuronGene.InnovationId,
                                                    tgtNeuronGene.InnovationId,
                                                    GenerateRandomConnectionWeight());
            connectionGeneList.Add(cGene);

            // Register connection with endpoint neurons.
            srcNeuronGene.TargetNeurons.Add(cGene.TargetNodeId);
            tgtNeuronGene.SourceNeurons.Add(cGene.SourceNodeId);
        }

        // Ensure connections are sorted.
        connectionGeneList.SortByInnovationId();

        // Create and return the completed genome object.
        return CreateGenome(_genomeIdGenerator.NextId, birthGeneration,
                            neuronGeneList, connectionGeneList,
                            _inputNeuronCount, _outputNeuronCount, false);
    }

And modify CreateOffspring(uint birthGeneration) in NeatGenome.cs like so

    /// <summary>
    /// Asexual reproduction.
    /// </summary>
    /// <param name="birthGeneration">The current evolution algorithm generation. 
    /// Assigned to the new genome at its birth generation.</param>
    public NeatGenome CreateOffspring(uint birthGeneration)
    { 
        // Enter the section 30% of the time.
        if(_genomeFactory.Rng.NextDouble() < 0.3)
        {
            return _genomeFactory.CreateRandomGenome(birthGeneration);
        }

        // Make a new genome that is a copy of this one but with a new genome ID.
        NeatGenome offspring = _genomeFactory.CreateGenomeCopy(this, _genomeFactory.NextGenomeId(), birthGeneration);

        // Mutate the new genome.
        offspring.Mutate();
        return offspring;
    }

Colin

[robertvo]

Thanks Colin! You're the best! I'm working on a bitcoin robot :) If it's profitable I'll send some coins your way!

[colgreen]

No problem. For fun here's my bitcoin market size projection...

Bitcoin Market Capitalisation Projection