Обобщение простого генетического алгоритма (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.