geneticalgorithmbase.cs

Generalization of a Simple Genetic Algorithm (GA)

using System;
using System.Collections.Generic;
using System.Text;

namespace GeneticAlgorithmLib
{
    public abstract class GeneticAlgorithmBase
    {
        protected int m_NumberOfSelectees = -1;

        #region Constructors / Destructors
        public GeneticAlgorithmBase(int NumberOfSelectees)
        {
            m_NumberOfSelectees = NumberOfSelectees;
        }
        #endregion

        #region Tournament
        public List<IGenotype> Tournament(List<IGenotype> Population, int NumberOfIterations)
        {
            List<IGenotype> returnVal = null; // This will be the overall winner for the tournament
            for (int i = 0; i < NumberOfIterations; i++)
            {
                // Run the cycle for the current genotypes
                List<IGenotype> currentWinners 
                    = GeneticCycle(Population);

                // Keep track of the overall winner for the tournament
                if (returnVal == null)
                {
                    // By default, the first winner is the starting overall winner
                    returnVal = currentWinners;
                }
                else
                {
                    // Compare the current winner to the overall winner
                    // and update the overall winner
                    List<IGenotype> chosen = new List<IGenotype>();
                    chosen.AddRange(returnVal);
                    chosen.AddRange(currentWinners);
                    List<IGenotype> Winners, Losers;
                    // NOTE: This could lead to winners from returnVal intermingled 
                    // with winners from currentWinners, which may not be desirable?
                    this.ChooseWinners(chosen, out Winners, out Losers);
                    returnVal = Winners;
                    
                    // Check if our overall winner fulfills the genetic requirements
                    if (this.Evaluate(returnVal))
                    {
                        break; // We have a winner so stop the tournament
                    }
                }
            }
            return returnVal;
        }
        #endregion

        #region GeneticCycle
        public List<IGenotype> GeneticCycle(List<IGenotype> Pop)
        {
            // Choose two Genotypes from the population
            List<IGenotype> Chosen = this.PickGenotypes(Pop, this.m_NumberOfSelectees);

            // Determine which of the two is the winning Genotype
            List<IGenotype> Winners, Losers;
            this.ChooseWinners(Chosen, out Winners, out Losers);

            // Infect the loser's genes with some portion of the winner's genes
            this.Recombine(Winners, Losers);

            // Mutate the loser's genes
            this.Mutate(Losers);

            return Winners;
        }
        #endregion

        #region PickGenotypes
        /// <summary>
        /// Choose some subset of the population 
        /// </summary>
        /// <param name="Population">The population to choose from</param>
        /// <param name="NumberOfSelectees">The number of genotypes to choose from the
        /// population</param>
        /// <returns>Some subset of Population</returns>
        private List<IGenotype> PickGenotypes(List<IGenotype> Population, int NumberOfSelectees)
        {
            List<IGenotype> returnVal = new List<IGenotype>();
            Random r = new Random();
            // We'll choose random numbers between 0 and the total size of the population
            int max = Population.Count - 1;

            List<int> usedPositions = new List<int>();
            for (int i = 0; i < NumberOfSelectees; i++)
            {
                // We need to remove positions from the pool as we go along
                int newPosition = -1;
                do
                {
                    newPosition = (int)Math.Round(r.NextDouble() * (double)max);
                } while (usedPositions.Contains(newPosition));
                usedPositions.Add(newPosition);

                // Select the entry from the population
                returnVal.Add(Population[newPosition]);
            }

            if (returnVal.Count < 2)
            {
                throw new Exception("Must have at least 2 chosen genotypes.");
            }
            return (List<IGenotype>)returnVal;
        }
        #endregion

        #region CreatePopulation
        /// <summary>
        /// As a convenience, we provide a method to create a new population of a particular
        /// size.
        /// </summary>
        /// <param name="PopulationSize"></param>
        public List<IGenotype> CreatePopulation(int PopulationSize)
        {
            if (PopulationSize < 2)
            {
                throw new ArgumentException("PopulationSize must be greater than 2");
            }

            List<IGenotype> returnVal = new List<IGenotype>(PopulationSize);
            for (int i = 0; i < PopulationSize; i++)
            {
                returnVal.Add(this.CreateGenotype());
            }

            return returnVal;
        }
        #endregion

        #region Abstract
        /// <summary>
        /// Determine which members of Pop are the winners and which are the 
        /// losers, and assigns them to the out variables Winners and Losers, 
        /// respectively.
        /// </summary>
        public abstract void ChooseWinners(List<IGenotype> Potentials, out List<IGenotype> Winners, out List<IGenotype> Losers);
        /// <summary>
        /// Takes some portion of the genes from Winners and inserts them into
        /// the genes of the Losers
        /// </summary>
        protected abstract void Recombine(List<IGenotype> Winners, List<IGenotype> Losers);

        /// <summary>
        /// Changes in some way the genes of the Losers
        /// </summary>
        protected abstract void Mutate(List<IGenotype> Losers);

        /// <summary>
        /// Check whether Genes are sufficient for our model. 
        /// </summary>
        /// <param name="returnVal">The IGenotype objects to check</param>
        /// <returns>Returns true if Genes is a "match", false otherwise.</returns>
        protected abstract bool Evaluate(List<IGenotype> Genes);
        /// <summary>
        /// Create a new IGenotype. This is specific to the kind of algorithm
        /// </summary>
        /// <returns>A new IGenotype</returns>
        protected abstract IGenotype CreateGenotype();
        #endregion
    }
}