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

ОГЛАВЛЕНИЕ

Идеей является попытка создать простой каркас, позволяющий реализовать генетический алгоритм с минимальными усилиями, сосредоточившись на деталях тестов на пригодность и полагая, что каркас правильно циклически пройдет популяцию.

•    Скачать исходники - 20.6 Кб
•    Скачать демонстрационный проект - 9.59 Кб

Введение

Вспомните простую задачу: из 10 карточек, помеченных 1-10, создать две пачки A и B, где сумма карточек в A как можно ближе к 36, а произведение карточек в B как можно ближе к 360.

Обобщение

Идеей является попытка создать простой каркас, позволяющий реализовать генетический алгоритм с минимальными усилиями, сосредоточившись на деталях тестов на пригодность и полагая, что каркас правильно циклически пройдет популяцию.

Сначала был рассмотрен общий подход:

Генетический цикл, часть I
1.    Выбрать два члена популяции
2.    Определить "победителя" 1 и "проигравшего" 1
3.    Случайно объединить победителя с проигравшим
4.    Случайно видоизменить проигравшего

Обобщение было продвинуто еще на шаг вперед:

Генетический цикл, часть II
1.    Выбрать N членов популяции, где N > 1
2.    Определить «победителей» W и «проигравших» L, где W+L = N
3.    Случайно объединить победителей с проигравшими
4.    Случайно видоизменить проигравших

Сейчас неясно, насколько важно второе обобщение. Неизвестно, будет ли оно правильно работать для N > 2. Оно может дать популяцию, не имеющую достаточного разнообразия, чтобы найти решение:
Спустя некоторое время (n повторений цикла) популяция может стать слишком однородной, если оставить несколько проигравших. В результате этого главный победитель будет недостаточно отличаться, и рекомбинация и мутация фактически не повлияют на создание организма, могущего решить проблемную область. Далее учтено это предупреждение.

Зачем обобщать? Задача GA возникает часто, поэтому целесообразен подход, который легко повторно использовать. Можно создать базовый класс, работающий с любыми N, W и L, и затем создающий производные классы, соответствующие ситуации. В частности, был создан производный класс с N=2, W=1 и L=1 и назван BinaryGeneticAlgorithm. Затем был создан производный класс от BinaryGeneticAlgorithm по имени "CardProblem". Теперь гораздо легче создать CardProblem и аналогичные классы.

IGenotype

Прежде чем приняться за базовые классы, нужен интерфейс для работы с ними. IGenotype предоставляет интерфейс для генотипов. Он хранит список объектов Gene, являющихся On или Off. (Есть некоторый дополнительный код, заставляющий объекты Gene аккуратно отображаться в обозревателе свойств.)

public interface IGenotype
{
    [Editor(typeof(CollectionEditor), typeof(UITypeEditor))]
    List<Gene> Genes { get; }
}

Ниже приведены флаги On/Off:

[Flags]
public enum EGene
{
    Off = 0,
    On = 1,
}

Класс Gene весьма простой, поэтому смотрите детали в исходнике.

GeneticAlgorithmBase

Класс GeneticAlgorithmBase определяет шаблон для запуска турнира для популяции объектов IGenotype. Турнир запускается с заданием популяции и числа итераций. В течение турнира хранятся абсолютные победители, и каждый следующий победитель сравнивается с абсолютным победителем. Также проверяется, отвечает ли текущий абсолютный победитель генетическим требованиям. Если да, то турнир прекращается. Код приведен ниже:

public List<IGenotype> Tournament(List<IGenotype> Population, 
                                        int NumberOfIterations)
{
    List<IGenotype> returnVal = null;
    // Это будет абсолютный победитель для турнира

    for (int i = 0; i < NumberOfIterations; i++)
    {
        // Запустить цикл для текущих генотипов
        List<IGenotype> currentWinners
            = GeneticCycle(Population);

        // Сохранить абсолютного победителя для тура
        if (returnVal == null)
        {
            // По умолчанию, первый победитель является начальным абсолютным победителем
            returnVal = currentWinners;
        }
        else
        {
            // Сравнить текущего победителя с абсолютным победителем
            // и обновить абсолютного победителя
            List<IGenotype> chosen = new List<IGenotype>();
            chosen.AddRange(returnVal);
            chosen.AddRange(currentWinners);
            List<IGenotype> Winners, Losers;
            // Примечание: Это может перемешать победителей из returnVal
            // с победителями из currentWinners, что нежелательно.
            this.ChooseWinners(chosen, out Winners, out Losers);
            returnVal = Winners;
           
            // Проверить, отвечает ли абсолютный победитель генетическим требованиям
            if (this.Evaluate(returnVal))
            {
                break; // Есть победитель, поэтому турнир прекращается
            }
        }
    }
    return returnVal;
}

Генетический цикл моделируется в шаблонном методе. Сначала выбирается несколько членов из популяции, затем выбирается победитель(и) и проигравший(е), перекомпоновываются и видоизменяются. Наконец, возвращается победитель(и):

public List<IGenotype> GeneticCycle(List<IGenotype> Pop)
{
    // Выбрать два генотипа из популяции
    List<IGenotype> Chosen = this.PickGenotypes(Pop,
                                      this.m_NumberOfSelectees);

    // Определить, который из двух является побеждающим генотипом
    List<IGenotype> Winners, Losers;
    this.ChooseWinners(Chosen, out Winners, out Losers);

    // Заразить гены проигравшего некоторой частью генов победителя
    this.Recombine(Winners, Losers);

    // Видоизменить гены проигравшего
    this.Mutate(Losers);

    return Winners;
}

Код для выбора генотипов для использования несколько громоздкий, но, по сути, выбираются случайные точки из популяции. Как только одна точка выбрана, надо следить за тем, чтобы она не была выбрана повторно.

private List<IGenotype> PickGenotypes(List<IGenotype> Population, 
                                            int NumberOfSelectees)
{
    List<IGenotype> returnVal = new List<IGenotype>();
    Random r = new Random();
    // Выбираются случайные числа от 0 до
    // полного размера популяции
    int max = Population.Count - 1;

    List<int> usedPositions = new List<int>();
    for (int i = 0; i < NumberOfSelectees; i++)
    {
        // Надо удалять точки из пула по мере продолжения
        int newPosition = -1;
        do
        {
            newPosition = (int)Math.Round(r.NextDouble() * (double)max);
        } while (usedPositions.Contains(newPosition));
        usedPositions.Add(newPosition);

        // Выбрать запись из популяции
        returnVal.Add(Population[newPosition]);
    }

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

Предоставлен шаблонный метод для быстрого создания популяции:

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;
}

Наконец, есть группа абстрактных методов, которые наследники должны будут реализовать:

public abstract void ChooseWinners(List<IGenotype> Potentials, 
       out List<IGenotype> Winners, out List<IGenotype> Losers);
protected abstract void Recombine(List<IGenotype> Winners,
       List<IGenotype> Losers);
protected abstract void Mutate(List<IGenotype> Losers);
protected abstract bool Evaluate(List<IGenotype> Genes);
protected abstract IGenotype CreateGenotype();

Первые три - ChooseWinners, Recombine и Mutate – должны быть очевидны, так как являются шагами в цикле.

Evaluate – метод, определяющий генетическую пригодность. Он показывает, отвечают ли заданные генотипы требованиям решения.

CreateGenotype позволяет средству реализации создать генотип. Он используется шаблонным методом CreatePopulation.

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


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).


Пользовательский интерфейс(UI)

UI в примере кода обеспечивает легкий способ передачи необходимых параметров для запуска турниров, так что можно испробовать разные комбинации, и позволяет просмотреть результаты. Установите заданное значение суммы, заданное значение произведения и количество карточек. Эти параметры специфичны для задачи карточек. Установите размер популяции, чтобы создать популяцию конкретного размера. Установите вероятность рекомбинации и вероятность мутации в значение от 0 до 1. Наконец, установите число итераций, чтобы задать длительность турнира. Установив все значения, нажмите кнопку "Вперед!". Спустя некоторое время она снова станет активной, сообщая об окончании Tournament. в зависимости от результатов турнира, станет активной кнопка "Просмотреть результаты". Основная форма выглядит так:

Основная форма сохраняет абсолютного победителя всех турниров, аналогично тому, как GeneticAlgorithmBase сохраняет абсолютного победителя в турнире. После каждого турнира основная форма сравнивает победителя турнира с абсолютным победителем. Если победитель турнира "лучше" абсолютного победителя, он становится новым абсолютным победителем, и активируется кнопка «Просмотреть результаты». Затем можно нажать «Просмотреть результаты» и увидеть результаты, выглядящие таким образом:

Это лишь обозреватель свойств в форме. Обозреватель свойств отображает текущий абсолютный побеждающий IGenotype. Можно держать открытыми формы старых результатов, чтобы сравнивать различия между победителями и убеждаться в приближении к решению. Можно посмотреть конкретные гены в IGenotype, нажав кнопку с многоточием "..." рядом с набором генов "Gene". Такой прием отобразит редактор набора генов Gene.

Вот и все с UI.

Вопросы

Возникают следующие вопросы:

1.    Насколько важен  GeneticAlgorithmBase. Полезен ли он, или следует сжать его в BinaryAlgorithmBase? Почему?
2.    Каково обобщение? Хороши ли применяемые стратегии объектно-ориентированного программирования для обеспечения повторного использования? Следует ли над чем-то поработать?
3.    Любые другие комментарии

Известные проблемы

В данном подходе были замечены следующие проблемы:

1.    GeneticAlgorithmBase работает с коллекциями IGenotype. Может появиться проблема при наличии нескольких победителей и/или проигравших. В частности, при таких классах "PolyGenenticAlgorithm" рекомбинирование победителей с проигравшими может вызвать проблемы, потому что неясно, какого победителя следует рекомбинировать с каким проигравшим, или же каждого победителя следует рекомбинировать с каждым проигравшим. Так как рекомбинирование оставлено реализатору, определение подобающего способа рекомбинирования остается на усмотрение разработчика. Например, в TernaryGeneticAlgorithm может быть один победитель и два проигравших, или один проигравший и два победителя, и в обоих случаях стоит вопрос, как победители влияют на проигравших? Разработчику придется ответить на эти вопросы.
2.    Как сказано, есть вероятность, что несколько победителей, рекомбинированных с проигравшими, дадут популяцию, не имеющую достаточного разнообразия для отыскания решения.
3.    Касательно структуры кода, использование IComparable для сравнения IGenotype может упростить дело.