Простой генетический алгоритм на 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();

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

Читайте также:
  • Манипулирование цветами в .NET – часть первая
    • Скачать демонстрационный проект (.NET 1.1) - 58.8 Кб• Скачать исходники C# (.NET 1.1) - 110.0 Кб• Скачать исходники C# (.NET 2.0) - 111.2 Кб• Скачать исходники VB (.NET 2.0) - 115.7 Кб Введение Почему статья о "цветах"? На самом деле, в .NET, можно использовать только два формата цвета: цвет...
  • Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0
    •    Скачать исходники - 265.8 Кб (с тестами NUnit)•    Скачать двоичные файлы - 40.5 Кб•    Домашняя страница проекта NGenerics (CodePlex)Статья не дает все подробности и полные описания внутреннего устройства этих коллекций и алгоритмов - наоборот, она дает ссылки на имеющиеся в интернете ресурс...
  • Определение цен барьерных опционов с помощью сеток. Часть первая – постоянные барьеры
    •    Скачать демонстрационный проект - 5.26 Кб•    Скачать исходники - 12.2 Кб Введение Стоит отметить, что представленный метод можно расширить до вмещения опционов с несколькими постоянными барьерами. После изучения простого примера перейдем к более сложным опционам с изменяющимися во времени ...
  • FuzzyAdvisor – простая экспертная система с нечеткой логикой на F#
    •    Скачать исходники - 108 Кб Введение Более 15 лет назад разрабатывали проект (Brulé и др., 1995), требовавший экспертную систему, выбирающую подходящий вариант исходя из некоторых основных параметров. Были опробованы несколько подходов, в том числе использование исчисления предикатов (...
  • Нейронные сети на C#
    •    Скачать исходники - 251 Кб•    Скачать демонстрационный проект - 181 Кб Введение История нейронных сетей начинается в 1950-х гг., когда была представлена архитектура простейших нейронных сетей. После начальной работы в области идея нейронных сетей стала весьма популярной. Но затем область...