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

Written on .

ОГЛАВЛЕНИЕ

Страница 1 из 2

В данной статье создается простой генетический алгоритм на 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();

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

форум разработчиков