Библиотека для генетических алгоритмов в .NET Framework

Скачать исходники

Введение

Для начала (хотя скорее для приличия) надо сказать, что из себя представляют эти самые генетические алгоритмы. Только долго их описывать их не буду, т.к. вы можете найти много хороших статей по ним и интернете. А есл ив двух словах, то генетические алгоритм - это такой алгоритм с помощью которого можно искать минимум (или максимум) целевой функции от многих переменных. Такой алгоритм применяют, когда целевая функция сложная и не понятно как еще можно найти ее экструмум. Для примера, целевой функцией может быть ошибка между полученными данными и расчетными с параметрами, которые надо установить. Например, в исходниках, которые вы можете скачать по ссылке в конце статьи, алгоритм вычисляет коэффициенты перед переменными.

Ну раз уж начал об исходниках, то сразу опишу задачу, которая там решается.
Есть функция f = a5 * X0 ^ 5 + a4 * X1 ^ 4 + a3 * X2 ^ 3 + a2 * X3 ^ 2 + a1 * X4 + a0. Здесь X0...X4 - переменные функции, а a0...a5 - это коэффициенты, которые впринципе не меняются, но нам не известны и мы хотим их найти. Изначально a0 = 2.2, a1 = 1.32, a2 = -4.06, a3 = -3.1, a4 = 4.7, a5 = 0.2. Для расчетов мы знаем значения функции в некоторых точках (30 точек). Для увеличения точности и скорости ограничим интервал, в котором находятся коэффициенты, отрезком [-5.0; 5.0].

Идея генетических алгоритмов взята из теории Дарвина о эволюции. Суть его в том, что изначально мы имеем набор произвольных видов. Каждый вид содержит в себе набор хромосом, которые и надо рассчитать. Сначала мы имеем в популяции виды, у которых все хромосомы случайны. После этого происходит скрещивание видов и, возможно, мутирование. После этого отбираются самые лучшие виды (у которых минимальна целевая функция), а самые плохие (с максимальными целевыми функциями и с хромосомами, которые не попадают в заданный интервал) удаляются из популяции. На следующей итерации скрещивание, мутирование и отбор повторяется. Благодаря этому у нас постепенно остаются только те, у которых целевая функция близка к минимуму.

Реализация

Реализация алгоритма была сделана на языке C# для .NET Framework 1.1.

Базовый класс для видов

Все виды должны быть производными от базового класса BaseSpecies

    /// <summary>
    /// Базовый класс для вида
    /// </summary>
    abstract public class BaseSpecies: IComparable
    {
            #region Статические функции для скрещивания хромосом базовых типов
            /// <summary>
            /// Скрестить две хромосомы типа double
            /// </summary>
            /// <param name="x">1-я хромосома</param>
            /// <param name="y">2-я хромосома</param>
            /// <returns>Новая хромосома</returns>
            static protected double Cross (double x, double y)
            {
                ...
            }
            
             static protected Int32 Cross (Int32 x, Int32 y)
            {
                ...
            }
            
            static protected Int64 Cross (Int64 x, Int64 y)
            {
                ...
            }

            #endregion
            
            #region Методы для мутаций в базовых типах
            /// <summary>
            /// Мутация для типа double
            /// </summary>
            /// <param name="val">Мутируемое значение</param>
            /// <returns>Промутирующее значение</returns>
            static protected double Mutation (double val)
            {
                ...
            }

             static protected Int32 Mutation (Int32 val)
            {
                ...
            }

            static protected Int64 Mutation (Int64 val)
            {
                ...
            }

            #endregion

            /// <summary>
            /// Мертв ли вид.
            /// </summary>
            /// <remarks>Например, когда хромосовы не попадают в заданные интервал</remarks>
            protected Boolean m_Dead = false;

            /// <summary>
            /// Мертвый ли вид?
            /// </summary>
            public bool Dead
            {
                    get	{ return m_Dead; }
            }

            /// <summary>
            /// Проверяет, чтобы все хромосомы попали бы в заданные интервалы. 
            /// В противном случае помечает вид как "мертвый".
            /// </summary>
            abstract public void TestChromosomes();

            /// <summary>
            /// Метод для скрещивания себя с другим видом
            /// </summary>
            /// <param name="Species">Другой вид</param>
            /// <returns>Полученный вид</returns>
            abstract public BaseSpecies Cross (BaseSpecies Species);

            /// <summary>
            /// Произвести мутацию
            /// </summary>
            abstract public void Mutation();

            /// <summary>
            /// Целевая функция. Должна в случае удачного набора хромосом стремиться к своему минимуму
            /// </summary>
            /// <returns>Значение целевой функции</returns>
            abstract public double FinalFunc
            {
                    get;
            }

            #region IComparable Members

            /// <summary>
            /// Вид считается больше, если он мертв или у него больше целевая функция
            /// </summary>
            /// <param name="obj"></param>
            /// <returns></returns>
            public Int32 CompareTo(object obj)
            {
                ...
            }
            #endregion
	}

abstract public void TestChromosomes();
Этот методы должен устанавливать внутреннюю защищенную Булеву переменную m_Dead, которая показывает, подходят ли хромосомы по ограничениям, которые на них накладывают (например, в нашем примере, попадают ли значения хромосом в отрезок [-5.0; 5.0]). Если значения хромосом нас устраивают, то m_Dead надо установить в false, иначе в true. По этой переменной (получаемую через свойство Dead) популяция отбрасывает неудачные виды.

Следующий метод, который необходимо реализовать, это abstract public BaseSpecies Cross (BaseSpecies Species);
Этот метод создает новый вид, скрещивая себя и другой вид, который передается как аргумент. Здесь надо сделать некоторые пояснения. Обычно, если вид содержит несколько хромосом, скрещивают хромосомы "одного вида", т.е. в нашем случае скрещиваем a0 себя (т.е. this) и a0 другого вида, анологично скрещиваем a1 и a1, т.е. нет смысла скрещивать a0 себя и a1 другого класса. Возможно, у вас будет задача, где это понадобится, но я так сходу ее придумать не смогу.

Смысл скрещивания состоит в том, что берем одну часть хромосомы себя и вторую часть другого вида и создаем из них новую хромосому, которая и будет содержаться в новом виде. Часто хромосомы скрещивают побайтово. Суть его состоит в том, что сначала случайно выбираем точку разрыва (скрещивания) хромосомы, потом создаем новую хромосому, которая состоит из левой части первой хромосомы и правой второй. Пусть например у нас есть дву хромосомы (8-мибитовые для простоты): 10110111 и 01110010. Случайно выбираем точку разрыва (отмечена символом '|').
101 | 10111
011 | 10010
Отсюда мы может сделать две разные хромосомы это 101 10010 и 011 10111. Какую из них выбрать - это также можно решить генератором случайных чисел :). Также можно искать две и более точек пересечения.

Таким образом, мы должны иметь конструктор, который создает вид из хромосом. Для того, чтобы не надо было изобретать велосипед, в классе BaseSpecies есть публичные статические методы для скрещивания хромосом некоторых типов (Double, Int64 и Int32). Разберем поподробнее первые два метода. В данном случае по сути есть две точки перечечения - в середине слова и знак числа, т.е. сначала скрещиваются хромосомы побитово без учета знака, а потом также случайно берем знак от одной из хромосомы.

Расмотрим код.

/// <summary>
/// Скрестить две хромосомы типа double
/// </summary>
/// <param name="x">1-я хромосома</param>
/// <param name="y">2-я хромосома</param>
/// <returns>Новая хромосома</returns>
static protected double Cross (double x, double y)
{
        Int64 ix = BitConverter.DoubleToInt64Bits(x);
        Int64 iy = BitConverter.DoubleToInt64Bits(y);

        double res = BitConverter.Int64BitsToDouble(BitCross(ix, iy));

        if (m_Rnd.Next() % 2 == 0)
        {
                if (x * res < 0)
                {
                        res = -res;
                }
        }
        else
        {
                if (y * res < 0)
                {
                        res = -res;
                }
        }

        return res;
}

Работает этот метод следующим образом: сначала преобразуем хромосомы из типа Double в Int64. Это сделано для того, чтобы можно было бы без проблем скрещивать побитово. (Спасибо henson-у с форума RSDN за то, что подсказал, что есть метод DoubleToInt64Bits. Собственно все эта ветка форума находится здесь.)
После скрещивания уже типов Int64 без учета знака (об этом чуть позже), переводим число обратно к Double, а потом берем знак одной из двух хромосом.

А теперь давайте посмотрим как происходит скрещивание типов Int64:

/// <summary>
/// Скрестить побитово без учета знака две хромосомы типа Int64
/// </summary>
/// <param name="x">1-я хромосома</param>
/// <param name="y">2-я хромосома</param>
/// <returns>Новая хромосома</returns>
static protected Int64 BitCross (Int64 x, Int64 y)
{
        // Число бит, оставшиеся слева от точки пересечения хромосом
        int Count = m_Rnd.Next(62) + 1;
        Int64 mask = ~0;

        mask = mask << (64 - Count);

return (x & mask) | (y & ~mask);
}

/// <summary>
/// Скрестить побитово с учетом знака две хромосомы типа Int64
/// </summary>
/// <param name="x">1-я хромосома</param>
/// <param name="y">2-я хромосома</param>
/// <returns>Новая хромосома</returns>
static protected Int64 Cross (Int64 x, Int64 y)
{
        Int64 res = BitCross(x, y);

        if (m_Rnd.Next() % 2 == 0)
        {
                if (x * res < 0)
                {
                        res = -res;
                }
        }
        else
        {
                if (y * res < 0)
                {
                        res = -res;
                }
        }

        return res;
}

Как видно из кода, сначала скрещиваются хромосомы без учета знака, а потом (как и с типом Double) выбирается знак одной из хромосом. Точнее, это работает так, что сравнивают знак выбранной хромосомы с результатом, и, если знаки не совпали (произведение меньше нуля), то знак результата меняется на противоположный. Скрещивание без учета знаков - это просто игра с битами.

Если вас по каким-то причинам не устраивают эти методы для скрещивания, то вы можете сделать свои и использовать их, а мы переходим к следующему абстрактному методу, который надо реализовать.

public void Mutation(); Здесь все очень похоже на скрещивание. Мутация действует на одну хромосому. В теории при мотации могут происходить любые изменения. Но в данной реализации мутация меняет один бит в слове. Вот пример кода:

/// <summary>
/// Мутация для типа double
/// </summary>
/// <param name="val">Мутируемое значение</param>
/// <returns>Промутирующее значение</returns>
static protected double Mutation (double val)
{
    UInt64 x = BitConverter.ToUInt64(BitConverter.GetBytes(val), 0);

    UInt64 mask = 1;
    mask <<= m_Rnd.Next(63);
    x ^= mask;

    double res = BitConverter.ToDouble(BitConverter.GetBytes(x), 0);

    return res;
}

/// <summary>
/// Мутация для типа Int64
/// </summary>
/// <param name="val">Мутируемое значение</param>
/// <returns>Промутирующее значение</returns>
static protected Int64 Mutation (Int64 val)
{
    Int64 mask = 1;
    mask <<= m_Rnd.Next(63);

    return val ^ mask;
}

Мутации обычно происходят довольно редко. Например, вероятность мутации часто ставят не больше нескольких процентов (я предпочитаю 1%).

Пример реализации видов

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

Для начала объявлен класс для представления точек функции:

public class DoubleFuncPoint
{
    public const int FuncSize = 5;
    
    /// <summary>
    /// X1, X2, ..., X5
    /// </summary>
    private double[] m_X = new double[FuncSize];
    public double[] X
    {
        get
        {
            return m_X;
        }
    }

    /// <summary>
    /// Значение функции
    /// </summary>
    private double m_Y;
    public double Y
    {
        get
        {
            return m_Y;
        }
    }

    public DoubleFuncPoint(double[] x, double y)
    {
         m_X = (double[])x.Clone();
        m_Y = y;
    }
}

Здесь я думаю все понятно. А в самом классе вида DoubleSpecies (причем как статический члены, чтобы у всех видов были одинаковые данные и не надо было бы их лишний раз передавать) хранится ArrayList, в который заносятся экземпляры класса DoubleFuncPoint. По-хорошему надо было бы сделать класс, производный от CollectionBase, чтобы исключить добавление туда других типов, но для тестового приложения я этого делать не стал (лень, знаете ли :) ). Значение целевой функции (что она из себя представляет расскажу немного попозже) вычисляется только в двух случаях для каждого вида - когда он создается и мутирует -, а потом сохраняется в приватном поле и извлекается от туда.

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

private void GetFunc()
{
    m_FuncVal = 0.0;
    foreach (DoubleFuncPoint point in m_FuncPoints)
    {
        double f = Func(point.X) - point.Y;
        m_FuncVal += f * f;
    }
}

Ну и просто так, без комментариев приведу методы для скрещивания и теста хромосом:

public override BaseSpecies Cross(BaseSpecies Species)
{
    if (this == Species)
    {
        return new DoubleSpecies ((double[])m_Chromosomes.Clone());
    }

    DoubleSpecies Other = (DoubleSpecies)Species;

    //В данном конкретном случае лучше работает скрещивание сразу всех хромосом

    double[] chromosomes = new double[m_Chromosomes.Length];
    for (int i = 0; i < chromosomes.Length; ++i)
    {
        chromosomes[i] = Cross(m_Chromosomes[i], Other.Cromosomes[i]);
    }
    

    /*double[] chromosomes = (double[])m_Chromosomes.Clone();
    Int32 n = m_Rnd.Next(6);
    chromosomes[n] = Cross(m_Chromosomes[n], Other.Cromosomes[n]);*/
    
    return new DoubleSpecies(chromosomes);
}

public override void TestChromosomes()
{
    Boolean res = false;
    foreach (double chromosome in m_Chromosomes)
    {
        if (Double.IsNaN(chromosome) || chromosome < m_MinVal || chromosome > m_MaxVal)
        {
            res = true;
            break;
        }
    }

    m_Dead = res;
}

Да, чуть не забыл сказать, что при скрещивании в нашем случае есть два варианта: скрещивать сразу все хромосомы или скрещивать по одной хромосоме за один раз. В данном примере лучше (быстрее находится минимум), если скрещивать сразу все хромосомы, а в другом случае, например, как в примере с целыми хромосомами лучше работает скрещивание по одной хромосоме. Здесь уже надо экспериментировать.

Реализация популяции (класс Population)

А теперь рассмотрим класс популяции, где живут, размножаются и умирают виды. Вы будете добавлять свои виды в этот класс (точнее в массив видов, находящийся в этом классе).

Начнем со свойств, которые надо настроить перед началом работы алгоритма.
MaxSize (Int32) - максимальное число видов, которое может содержать популяция. Это тот размер, до которого "урезается" популяция после скрещивания. По умолчанию 500.
CrossPossibility (Double) - вероятность скрещивания. Она должна быть в интервале (0.0; 1.0]. Если это условие не выполняется, то бросается исключение ArgumentOutOfRangeException. По умолчанию 0.95.
MutationPossibility (Double) - вероятность мутации. Она должна быть в интервале [0.0; 1.0). Если это условие не выполняется, то бросается исключение ArgumentOutOfRangeException. Не рекомендуется ставить большую вероятность мутации.
Впринципе, можно было бы ввести еще вероятность отбора, но в данном случае она считается равной 1.0. В противном случае надо было бы удалять виды из популяции не все подряд самые плохие, а с некоторой вероятностью. Но мертвые виды (напомню, что это виды, у которых хромосомы не попадают в заданный интервал или не удовлетворяет другим условиям) надо удалять в любом случае.

А теперь рассмотрим публичные методы, которые необходимо вызывать.

void Add (BaseSpecies species) - добавить новый вид в популяцию. Заметьте, что вы должны вручную добавлять необходимое число видов. Перед началом работы алгоритма надо, чтобы в популяции было хотя бы два вида. Число видов в популяции может быть меньше, чем установленное значение MaxSize. Если после скрещивания размер популяции меньше MaxSize, то просто не удаляются самые плохие виды (даже мертвые).

Чтобы получить следующую популяцию, необходимо вызвать метод void NextGeneration(). Работа этого метода может занимать достаточно много времени, поэтому лучше всего его вызывать из отдельного потока. Давайте посмотрим что он делает.

/// <summary>
/// Обновить популяцию (получить слудующее поколение)
/// </summary>
public void NextGeneration()
{
    if (m_Generation == 0 && m_Species.Count < 2)
    {
        throw new SmallSizePopulationException();
    }

    // Сначала скрестим
    Cross();
    
    // Промутируем и заодно проверим все хромосомы
    foreach (BaseSpecies species in m_Species)
    {
        // Если надо мутировать с учетом вероятности.
        if (m_Rnd.NextDouble() <= m_MutationPossibility)
        {
            species.Mutation();
        }

        species.TestChromosomes();
    }

    // Отберем самые живучие виды
    m_Species.Sort();
    Selection();

    m_Generation++;
}

Сначала метод проверяет, чтобы при первом вызове метода (при нулевом поколении, о поколениях чуть позже) размер популяции был бы больше 2 (иначе некого скрещивать). Если это не так, то бросается исключение SmallSizePopulationException. После этого происходит скрещивание видов:

/// <summary>
/// Получить новые виды скрещиванием
/// </summary>
protected void Cross()
{
    // Размер до начала пополнения популяции (чтобы не скрещивать новые виды,
    // которые добавляются в конец списка)
    Int32 OldSize = m_Species.Count;

    // Номер пары для скрещиваемого вида
    Int32 Count = m_Species.Count;

    for (int i = 0; i < Count; ++i)
    {
        // Если надо скрещивать с учетом вероятности.
        if (m_Rnd.NextDouble() <= m_CrossPossibility)
        {
            // Добавляем в список вид, полученный скрещиванием очередного вида и
            // вида со случайным номером.
            m_Species.Add (m_Species[i].Cross (m_Species[m_Rnd.Next (OldSize)] ) );
        }
    }
}

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

После скрещивания происходит мутация видов также с заданной вероятностью, а после скрещивания идет тест хромосом. Дальше сортируем виды по их целевой функции. Метод Sort определен в классе BaseSpecies, здесь я его приводить не буду, но скажу, что вид считается больше тот, который мертвый, а, если все виды живые, то с максимальной целевой функцией. Отбор видов также происходит просто:

/// <summary>
/// Произвести отбор самых "живучих" видов
/// </summary>
protected void Selection()
{
    // Сколько видов надо удалить
    Int32 Count = m_Species.Count - m_MaxSize;

    for (Int32 i = 0; i < Count; ++i)
    {
        m_Species.RemoveAt (m_Species.Count - 1);
    }
}

Вот, пожалуй и все. Пример использования смотрите в исходниках.

Все Ваши предложения и замечания шлите мне.