Простой генетический алгоритм на C# - Алгоритм

Алгоритм

Код алгоритма содержит два простых класса, GA и Genome, плюс вспомогательный класс GenomeComparer.
Класс Genome можно считать простым контейнером. Нижележащая структура является массивом вещественных чисел двойной точности в диапазоне от 0 до 1. Ожидается, что пользователь берет эти значения и масштабирует их до любых нужных значений. Так как мутация происходит в геноме, метод Mutate находится в этом классе. Оператор кроссовера требует доступа к закрытым данным генома, поэтому он является функцией-членом, принимающей второй геном и выдающей два дочерних объекта генома. Пригодность конкретного генома также хранится в объекте генома. В коде есть еще дополнительные вспомогательные функции.

Класс GA делает всю работу. Генетический алгоритм состоит из следующих базовых шагов:
1. Создать новую популяцию
2. Выбрать двух индивидуумов из популяции, взвешивая относительно индивидуума, представляющего лучшее на настоящий момент решение.
3. 'Размножить' их, чтобы произвести потомство.
4. Если нет достаточного потомства для новой популяции, вернуться к шагу 2.
5. Заменить старую популяцию новой.
6. Если не было произведено достаточно поколений, вернуться к шагу 2.
7. Конец.

Индивидуумы для размножения выбираются с помощью метода колеса рулетки. Более подходящие индивидуумы имеют более крупную часть 'колеса' и выбираются с большей вероятностью. Пригодность хранится совокупно в System.Collections.ArrayList, так как он снабжен удобной сортировкой. Увы, его метод двоичного поиска подходит только для точных значений, поэтому пришлось реализовать следующий обходной прием:

mid = (last - first)/2;

// Двоичный поиск ArrayList поиска подходит только для точных значений,
// поэтому он сделан вручную.
while (idx == -1 && first <= last)
{
  if (randomFitness < (double)m_fitnessTable[mid])
  {
    last = mid;
  }
  else if (randomFitness > (double)m_fitnessTable[mid])
  {
    first = mid;
  }
  mid = (first + last)/2;
  // лежит между i и i+1
  if ((last - first) == 1)
     idx = last;
}

Класс GenomeComparer унаследован от интерфейса IComparer. Каждое поколение хранится в System.Collections.ArrayList, и надо сортировать каждое поколение по порядку пригодности. Поэтому данный интерфейс реализован таким образом:

public sealed class GenomeComparer : IComparer
{
    public GenomeComparer()
    {
    }
    public int Compare( object x, object y)
    {
        if ( !(x is Genome) || !(y is Genome))
            throw new ArgumentException("Not of type Genome");
        if (((Genome) x).Fitness > ((Genome) y).Fitness)
            return 1;
        else if (((Genome) x).Fitness == ((Genome) y).Fitness)
            return 0;
        else
            return -1;
    }
}

Необходимо явно привести элементы ArrayList обратно к типу геном. Также класс запечатывается, так как нет смысла наследовать от него.

Краткая заметка об операторах

Были кратко упомянуты два оператора – кроссовер и мутация, и следует объяснить их чуть подробней.
Кроссовер берет два генома, разделяет их в некоторой точке и порождает два новых генома путем обмена местами конечных частей, например:

10 20 30 40 50 60 70	80 90 00		10 20 30 40 50 60 70	30 20 10
		===>
00 90 80 70 60 50 40	30 20 10		00 90 80 70 60 50 40	80 90 00

Разделение происходит в случайно выбранной точке вдоль длины генома, только если успешно пройден тест вероятности. Она обычно устанавливается весьма высоко, что отражает происходящее в природе.
Мутация, в сравнении, происходит редко, поэтому вероятность ее возникновения устанавливается низкой, как правило, менее 5%. По очереди тестируется каждый ген в геноме, чтобы узнать, разрешено ли ему мутировать, и если да, то он меняется на случайное число, например:

10

20

30

40

50

60

70

80

90

===>

10

20

30

40

50

60

22

80

90

Результаты

Простой пример показывает, что оптимальное решение находится в (0.5, 0.5), и после 250 поколений находится очень близкое к нему решение (в пределах 4 значащих цифр). Прогресс GA виден ниже:

Заключение и примечания.

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

Далее обобщены несколько свойств C# (важных для ранее работавших с C++):
• Контейнер System.Collections.ArrayList делает лишь поверхностные копии.
• Двоичный поиск контейнера System.Collections.ArrayList работает только для точных значений.
• Определение переменной не обязательно присваивает ей значение.
• Реализация интерфейса IComparer тривиальная (смотрите класс GenomeComparer).

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