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

Алексей Бревнов,
Владимир Любителев,

1. Краткий обзор

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

2. Введение

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

Генетические алгоритмы были впервые применены в начале 70-х годов (Голландия, 1975). В основу данного алгоритма легла зависимость, выявленная человечеством в долгой борьбе с природой. Оказалось, что эволюции биологических видов зависит от составных частей хромосом (ДНК). И сразу же, можно провести аналогию с проблемами математики. К примеру, расчет системы с возрастающим числом параметров всегда был трудоемким и в некоторых случаях даже невозможным... Как же можно решить эту проблему, применив генетический алгоритм? Решение есть. Надо каждый параметр представить в виде хромосомы, которая в математическом представлении имеет вид реальной химической последовательности.

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

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

С помощью генетического алгоритма решено уже много задач, написано множество страниц подробного кода. Мы же остановимся лишь на числовом представлении. Для генетического алгоритма не играет никакой роли то, насколько полным является его внутреннее представление по отношению к действительности (Field, 1995).

3. Проблема

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

Оптимальным решением для данного случая будет x = 0.5, y = 0.5. То есть наивысший из пиков. Мы выбрали этот пример для того, чтобы продемонстрировать, тот факт, что генетический алгоритм не будет сбит с толку локальными максимумами функции, которые окружают наилучшее решение и явно наблюдаются на графике.

4. Подготовка теста

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

GA ga = new GA(0.8, 0.05, 100, 2000, 2);
ga.FitnessFunction = new GAFunction(theActualFunction);

где аргументами функции являются:

1. коэффициент скрещиваний,
2. коэффициент мутаций,
3. размер популяции,
4. число поколений,
5. число параметров, для которых должно быть найдено решение.

Свойство FitnessFunction объявлено следующим образом:

public delegate double GAFunction(double[] values);

public class GA
{
    static private GAFunction getFitness;
    public GAFunction FitnessFunction {  
        // etc.
    };
    // etc.
}

Это позволит в последствии объявить функцию адекватности (fitness function) в виде функции-делегата (delegate function). Например,

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();

После этого генетический алгоритм просчитает определенное выше число поколений.

5. Алгоритм

Состав исходного кода алгоритма:

1. Основные классы
   • GA
   • Genome
2. Вспомогательные классы
   • GenomeComparer

Класс Genome (геном) можно представить в виде простого контейнера. Его внутренняя структура представляет собой массив чисел типа double от 0 до 1. Предполагается, что эти значения будут масштабированы в желаемые величины.

Так как мутации происходят с генами, вы можете обнаружить метод Mutate в классе Genome. Оператору Crossover (скрещивание) необходим доступ к закрытым (private) членам класса Genome, поэтому он также является его методом, которому передается еще один экземпляр класса Genome, и результатом являются два наследных гена (два новых объекта класса Genome). Коэффициент адекватности каждого из генов храниться здесь же, в объекте класса Genome. Кроме того, вы можете обнаружить ряд дополнительных функций класса для вспомогательных целей.

Вся основная работа выполняется классом GA. Генетический алгоритм состоит из следующих этапов:

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

При выборе индивидуумов для размножения используется так называемый метод колеса рулетки. Здесь более удачные решения имеют большую пропорцию "колеса" и соответственно большую вероятность быть выбранными. Мы остановили свой выбор на классе System.Collection.ArrayList для хранения собранных значений адекватности, так как этот класс обладает некоторыми полезными для нас возможностями, такими как сортировка. К сожалению, его функция бинарного поиска предназначена только для конкретных значений, поэтому пришлось обойти это следующим образом:

mid = (last - first) / 2;

// ArrayList's BinarySearch is for exact values only
// so do this by hand.
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;
    // lies between i and i + 1
    if ((last - first) == 1)
        idx = last;
}

Класс GenomeComparer наследует от интерфейса IComparer. Каждое поколение храниться в System.Collection.ArrayList, и нам необходимо отсортировать поколение по величине пригодности (fitness). Для этого необходимо реализовать интерфейс IComparer следующим образом:

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 обратно к типу Genome. Мы также объявили класс запечатанным (sealed), так как нет никакого смысла наследовать от него.

6. Короткие замечания об операторах

Мы уже упомянули коротко о двух операторах: скрещивание (crossover) и мутация (mutation). Здесь же хотелось бы остановиться на них более подробно.

Скрещивание (crossover) по существу берет два генома, делит каждый из них их на две части в определенном месте и меняет местами эти части между геномами. Например,

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

Мутация (mutation), в отличие от скрещивания, случается гораздо реже, так что вероятность этого события должна быть достаточно низкой, обычно менее 5%. Каждый ген из состава генома проверяется на возможность мутации и, если это произошло, заменяется случайным числом. Например,

7. Результаты

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

8. Заключение и комментарии

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

За время написания статьи я познакомился со следующими особенностями языка C#, которые мне хотелось бы отметить здесь (исходя из опыта программирования на C++):

• Класс-контейнер System.Collections.ArrayList позволяет сделать только неглубокую копию (shallow copy) объектов.
• Бинарный поиск контейнера System.Collections.ArrayList работает только для конкретных значений.
• Очевидная вещь, однако ж объявление переменной не обязательно присваивает ей значение по умолчанию.
• Реализация интерфейса IComparer воистину тривиальна (см. класс GenomeComparer).

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

9. Ссылки

1. Field, P., "A Multary Theory for Genetic Algorithms: Unifying Binary and Non-binary Problem Representations", Ph.D. Thesis, 1995, Queen Mary and Westfield College.
2. Holland, J.H., "Adaption in Natural and Artificial Systems", MIT Press, 1975, (1992 Edition).
3. Lippman, S.B., "C# Primer, A Practical Approach", Addison-Wesley, 2002, (1st Edition).

10. Исходный код программы

Исходный код программы, демонстрирует работу алгоритма - (13.3 Кб)