Обобщение простого генетического алгоритма (GA) - BinaryAlgorithmBase и CardProblem

BinaryAlgorithmBase

Уже сделано много работы в GeneticAlgorithmBase,  так что же надо сделать тут? Сначала необходимо задать N – число выбранных членов популяции. Также надо знать вероятность рекомбинации и мутации. Это делается в конструкторе.

public BinaryGeneticAlgorithm(double ChanceOfInfect, double ChanceOfMutate)
    : base(2)
{
    m_ChanceOfInfect = ChanceOfInfect;
    m_ChanceOfMutate = ChanceOfMutate;
    this.m_NumberOfSelectees = 2;
}

Затем надо упростить некоторые из абстрактных методов, чтобы работать с размерами выборки равным двум. Сначала переопределяется метод ChooseWinners, выбирающий первые две записи из списка выбранных генотипов. Затем они передаются другому абстрактному методу, также именуемому ChooseWinners, но требующему только два выбранных генотипа, и вырабатывающему только одного победителя и одного проигравшего:

public override void ChooseWinners(List<IGenotype> Potentials,
     out List<IGenotype> Winners, out List<IGenotype> Losers)
{
    Winners = (List<IGenotype>)new List<IGenotype>();
    Losers = (List<IGenotype>)new List<IGenotype>();
    IGenotype gWinner, gLoser;
    this.ChooseWinners(Potentials[0], Potentials[1], out gWinner, out gLoser);
    ((List<IGenotype>)Winners).Add(gWinner);
    ((List<IGenotype>)Losers).Add(gLoser);
}

Теперь переопределяются методы Recombine и Mutate. В каждом случае код случайно выбирает, какие гены рекомбинируются / видоизменяются. Переменные класса m_ChanceOfInfect и m_ChanceOfMutate определяют вероятностный шанс.

protected override void Recombine(List<IGenotype> Winners, 
             List<IGenotype> Losers)
{
    IGenotype Winner = Winners[0],
        Loser = Losers[0];
    Random r = new Random();
    for (int i = 0; i < Loser.Genes.Count; i++)
    {
        double rand = r.NextDouble();
        if (rand < this.m_ChanceOfInfect)
        {
            Loser.Genes[i].SetGene(Winner.Genes[i].Value);
        }
    }
}
protected override void Mutate(List<IGenotype> Losers)
{
    IGenotype Loser = Losers[0];
    Random r = new Random();
    for (int i = 0; i < Loser.Genes.Count; i++)
    {
        double rand = r.NextDouble();
        if (rand < this.m_ChanceOfMutate)
        {
            Loser.Genes[i].SetGene(Loser.Genes[i].Value == EGene.On
                ? EGene.Off
                : EGene.On);
        }
    }
}

Метод Evaluate делегирует перегрузке, принимающей единственный IGenotype:

protected override bool Evaluate(List<IGenotype> Genes)
{
    return Evaluate(Genes[0]);
}

Вот, собственно, и все с BinaryAlgorithmBase. Имеется пара абстрактных методов, которые переопределят наследники, но они довольно простые. Необходимо позаботиться о том, чтобы наследники работали с двумя селекциями, и не больше.

protected abstract void ChooseWinners(IGenotype First, 
     IGenotype Second, out IGenotype gWinner, out IGenotype gLoser);
protected abstract bool Evaluate(IGenotype Genes);

Вот и все. Далее рассматривается CardProblem.

CardProblem

Чтобы дойти до фактической решаемой проблемы, потребовалось всего 285 строк. Ожидание того стоило. Вначале передаются некоторые аргументы конструктору CardProblem. Надо знать:

1.    Сколько карточек рассматривается
2.    Общую сумму, которую надо получить (в примере это 36)
3.    Общее произведение, которое надо получить (в примере это 360)
4.    Вероятность рекомбинации
5.    Вероятность мутации

public CardProblem(int NumberOfCards, int SumTarget, int ProductTarget, 
       double ChanceOfInfection, double ChanceOfMutation)
     : base(ChanceOfInfection, ChanceOfMutation)
{
    this.m_NumberOfCards = NumberOfCards;
    this.m_SumTarget = SumTarget;
    this.m_ProdTarget = ProductTarget;
}

Далее делается несколько переопределений. Первое - ChooseWinners. Аргументы приводятся к конкретному типу IGenotype по имени "CardGenes" (подробности в исходном коде). Затем они оцениваются, и назначается победитель и проигравший. Можно было бы поднять это едва ли не до уровня BinaryGeneticAlgorithm, но оценка проверяет значения double, возвращаемые "double Evaluate(IGenotype Genes)", что не всегда желательно. BinaryGeneticAlgorithm должен быть достаточно гибким, чтобы работать с разными видами ограничений. Поскольку средства реализации определяют свой собственный показатель пригодности, им целесообразно также определить свой собственный метод сравнения.

protected override void ChooseWinners(IGenotype First, 
         IGenotype Second, out IGenotype Winner, out IGenotype Loser)
{
    CardGenes f = First as CardGenes,
        s = Second as CardGenes;
    double fFitness = Evaluate(f),
        sFitness = Evaluate(s);
    string result = null;
    if ( fFitness < sFitness)
    {
        Winner = f;
        Loser = s;
    }
    else
    {
        Winner = s;
        Loser = f;
    }
}

Метод Evaluate весьма простой. Помните, как метод Evaluate обсуждался ранее? В данном случае Evaluate показывает, дает ли текущий генотип решение с нулевой ошибкой (т.е. сумма A точно равна X - например, 36, и произведение B точно равно Y - например, 360). Заметьте, что Evaluate делегирует закрытому методу (смотрите ниже):

protected override bool Evaluate(IGenotype Genes)
{
    CardGenes g = Genes as CardGenes;
    bool returnVal = Evaluate(g) == 0.0;
    return returnVal;
}

Ниже приведен небольшой метод CreateGenotype.

protected override IGenotype CreateGenotype()
{
    return new CardGenes(this.m_NumberOfCards);
}

Теперь посмотрите на закрытый метод Evaluate. Он должен быть знаком. Это дословный код оценки, исправленный в соответствии с каркасом:

private double Evaluate(CardGenes f)
{
    double sumErr, prodErr, combinedErr;
    int sum = 0, prod = 1;

    for (int i = 0; i < f.Genes.Count; i++)
    {
        Gene gene = f.Genes[i];
        if (gene.Value == EGene.On)
        {
            // On означает сумму
            sum += (i + 1);
        }
        else
        {
            // Off означает произведение
            prod *= (i + 1);
        }
    }
    sumErr = ((double)(sum - m_SumTarget)) / (double)m_SumTarget;
    prodErr = ((double)(prod - m_ProdTarget)) / (double)m_ProdTarget;
    combinedErr = Math.Abs(sumErr) + Math.Abs(prodErr);
    f.Sum = sum;
    f.Product = prod;
    return combinedErr;
}

Почти все. Остался только класс CardGenes, реализующий IGenotype. Подробности смотрите в исходном коде. Есть еще пользовательский интерфейс(UI).