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

ОГЛАВЛЕНИЕ

В данной статье создается простой генетический алгоритм на C#. Он не будет многопоточным и не будет содержать необычных операторов или критериев сходимости (т.е. условия, при котором многие из найденных решений очень похожи). Будет показан генетический алгоритм в управляемом коде, использующий ряд возможностей среды выполнения .NET.

• Скачать исходники - 11 Кб

Введение

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

Впервые генетические алгоритмы были разработаны в начале 1970-х (Холлэнд, 1975). Первоначальная идея взялась из наблюдения за тем, как эволюция биологических существ вытекает из составляющих их ДНК и хромосом. Это походит на математическую задачу, состоящую из множества параметров. Каждый параметр может занять место хромосомы в математической аналогии реальной химической последовательности.

По сути, эволюция осуществляется процессом селекции, служащим типичным примером выражения «выживает сильнейший». Чтобы выбрать индивидуума, необходима популяция индивидуумов на выбор, чтобы произвести новое поколение индивидуумов.

Для любой задачи, требующей решения, необходим какой-то показатель хорошего качества решения, т.е. пригодность, часто показатель ?2(хи-квадратный), т.е. чем лучше решение, тем выше пригодность, возвращенная из функции. Чем менее пригодны решения, тем меньше их шансы сохраниться до следующей популяции. Используя такой метод, алгоритм уменьшает число проверяемых им возможных решений.
Различные генетические алгоритмы внутренне представляют многие задачи в двоичном виде. Далее рассматривается только десятичное представление. Внутреннее представление генетического алгоритма на самом деле не важно, если реализация доскональная (Филд, 1995).

Задача

В примере кода задается тестовая функция, использующая sin и cos для выработки следующего графика:

Оптимальное решение для данной задачи - (0.5,0.5), т.е. самый высокий пик. Этот пример показывает, как генетический алгоритм не вводят в заблуждение соседние локальные максимумы (т.е. высокие пики).

Тестовая программа

Объявляется новый генетический алгоритм:

GA ga = new GA(0.8,0.05,100,2000,2);

ga.FitnessFunction = new GAFunction(theActualFunction);

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

public delegate double GAFunction(double[] values);

public class GA
{
static private GAFunction getFitness;
public GAFunction FitnessFunction {
// и т.д.
};
// и т.д.
}

Это позволяет объявить функцию пригодности так же, как функцию делегата:

public static double theActualFunction(double[] values) 
{
if (values.GetLength(0) != 2)
throw new ArgumentOutOfRangeException("should only have 2 args");
double x = values[0];
double y = values[1];
double n = 9;
double f1 = Math.Pow(15*x*y*(1-x)*(1-y)*Math.Sin(n*Math.PI*x)
*Math.Sin(n*Math.PI*y),2);
return f1;
}

которая поэтому принимается алгоритмом. Затем генетический алгоритм устанавливается на выполнение с помощью:

ga.Go();

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


Алгоритм

Код алгоритма содержит два простых класса, 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 и функции делегата.