Библиотека генетических алгоритмов - часть 2

Данная статья является продолжением первой части из серии статей о библиотеке генетических алгоритмов.

• Скачать исходный код библиотеки - 279 Кб
• Скачать исходный код демонстрационных приложений - 85.81 Кб
• Скачать демонстрационные приложения - 138.83 Кб
• Скачать документацию библиотеки - 1.03 Мб
• Последние версии библиотеки

Первую часть данной серии статей вы можете найти здесь.

Библиотека генетических алгоритмов

Алгоритмы

Объект генетического алгоритма соединяет описанные составляющие. Он определяет и управляет процессом эволюции и определяет ее конец. Интерфейс для генетических алгоритмов определен классом GaAlgorithm.

Схема - Класс GaAlgorithm

Методы StartSolving, StopSolving и PauseSolving позволяют пользователям управлять процессом эволюции, а метод GetState позволяет получить его текущее состояние. Когда пользователь меняет любую часть алгоритма [генетическую операцию или ее параметры] во время выполнения, метод BeginParameterChange должен вызываться перед внесением любых изменений. При завершении изменений пользователь должен вызвать метод EndParameterChange. Класс GaAlgorithmParams является базовым классом для параметров алгоритма.

Генетический алгоритм уведомляет остальную систему об изменениях в процессе эволюции с помощью шаблона наблюдателя. Пользователь должен вызвать метод SubscribeObserver, чтобы начать получать эти уведомления. Если уведомления больше не нужны, пользователь может вызвать метод UnsubscribeObserver. Объекты, передаваемые этим двум методам, должны быть экземплярами классов, унаследованных от класса GaObserver [или GaObserverAdapter].

Схема – Наблюдение за алгоритмом

GaObserver – интерфейс для наблюдателей генетического алгоритма. Реализации методов этого интерфейса являются обработчиками событий. Когда происходит событие в генетическом алгоритме, алгоритм проходит по списку подписанных наблюдателей и вызывает соответствующих наблюдателей, обрабатывающих событие.

virtual void StatisticUpdate(
    const GaStatistics& statistics,
    const GaAlgorithm& algorithm);

void NewBestChromosome(
    const GaChromosome& newChromosome,
    const GaAlgorithm& algorithm); 

void EvolutionStateChanged(
    GaAlgorithmState newState,
    const GaAlgorithm& algorithm);

Список наблюдателей управляет GaObserverList. Этот класс также реализует интерфейс GaObserver, но вместо обработки событий он направляет уведомления всем подписанным наблюдателям. operator+= и operator-= используются для подписания и отмены подписки наблюдателей.

// подписать наблюдателя
observerList += observer;

// отменить подписку наблюдателя
observerList -= observer;

Когда определенный пользователем наблюдатель наследует класс GaObserver, он должен реализовать все определенные методы. Иногда пользователь не хочет получать все события. Тогда пользователь может использовать класс GaObserverAdapter в качестве базового класса для наблюдателя. Класс GaObserverAdapter реализует все методы, определенные GaObserver, со стандартной обработкой событий; пользователь может переопределить только те методы, которые обрабатывают нужные события.
Конец процесса эволюции определяется условием остановки. Библиотека генетических алгоритмов определяет класс GaStopCriteria, являющийся интерфейсом для этой генетической операции.

Определенный пользователем класс, реализующий условие остановки, должен переопределить метод Evaluate:

virtual bool Evaluate(
    const GaAlgorithm& algorithm,
    const GaStopCriteriaParams& parameters) const;

Этот метод принимает ссылку на объект алгоритма, состояние которого оценивается, и ссылку на параметры условия остановки. Если алгоритм достиг нужного состояния и должен остановить эволюцию, этот метод должен вернуть true. Если условие не достигнуто, метод должен вернуть false.
GaStopCriteriaParams – базовый класс для параметров условия остановки.

Некоторые стандартные поведения генетического алгоритма реализованы в классе GaBaseAlgorithm.

Схема - Класс GaBaseAlgorithm

Этот класс управляет состоянием и переходами состояний процесса эволюции. Следующая схема показывает возможные состояния процесса эволюции, переходы, действия, инициирующие переходы, и реакции на изменения состояния.

Схема – Состояния алгоритма

GaBaseAlgorithm реализует методы StartSolving, StopSolving и PauseSolving, управляющие процессом эволюции. Эти методы выполняют проверки состояния и переходы состояния. При изменении состояния процесса эволюции вызывается один из следующих виртуальных методов: OnStart, OnResume, OnPause, OnStopt. Новые классы, реализующие конкретные генетические алгоритмы, должны переопределить эти методы, чтобы обрабатывать изменения состояния.

Этот класс также управляет списком подписанных наблюдателей и обрабатывает изменения во время выполнения, реализуя методы BeginParameterChange и EndParameterChange, защищающие одновременные изменения из нескольких потоков.

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

Схема – Класс GaMultithreadingAlgorithm

Каждый многопоточный алгоритм имеет один управляющий поток и минимум один рабочий поток. Управляющий поток готовит работу и передает управление рабочим потокам. После завершения всеми рабочими потоками своих частей работы управляющий поток вновь получает управление и объединяет результаты, выработанные рабочими процессами. Этот класс управляет всеми используемыми потоками, поэтому пользователю не надо беспокоиться о ресурсах, задействованных в многопоточности.
Следующая схема показывает управляющую логику многопоточного алгоритма:

Схема – Последовательность операций многопоточного алгоритма

Класс GaMultithreadingAlgorithm переопределяет методы OnStart, OnResume, OnPause и OnStop, чтобы управлять рабочим и управляющим потоками.

Методы ControlFlow и WorkFlow представляют последовательность операций управляющего и рабочего потоков. Эти методы обеспечивают синхронизацию и взаимодействие между управляющим потоком, рабочими потоками и остальной системой. Прежде чем ControlFlow передаст управление рабочим потокам, он вызывает метод BeforeWorkers, а после завершения рабочих потоков он вызывает метод AfterWorkers. Реализации генетических алгоритмов могут переопределять эти методы, чтобы производить специфические подготовки работ и объединение работ. Когда рабочий поток получает управление, метод WorkFlow вызывает метод WorkStep. Этот метод выполняет всю работу, которая может выполняться одновременно.

GaMultithreadingAlgorithmParams – базовый класс для параметров многопоточных алгоритмов. Он определяет число рабочих потоков, задействованных в выполнении генетического алгоритма.

Организация поточной обработки

Библиотека генетических алгоритмов содержит набор классов, типов данных и макросов, изолирующих зависящую от платформы организацию поточной обработки. Класс GaThread обертывает и управляет системными потоками.

Схема – Класс GaThread

Перечисление GaThreadStatus определяет возможные состояния потока, и структура GaThreadParameter хранит начальные параметры потока.

Типы данных потоков определены библиотекой:

GaCriticalSection изолирует системно-специфическую защиту критических секций от одновременного доступа к ним нескольких потоков. Класс GaSectionLock используется для автоматической блокировки и разблокировки объектов критической секции.

// ...

GaCriticalSection _criticalSection;

// ...

void SomeMethod()
{
    // автоматически блокирует объект синхронизации _criticalSection
    GaSectionLock lock( &_criticalSection, true );

    // ...код критической секции...

    // объект блокировки уничтожается, когда выполнение покидает эту область
    // деструктор объекта снимает блокировку с используемого объекта критической секции
}

Схема – Классы GaCriticalSection и GaSectionLock

Библиотека генетических алгоритмов определяет макросы, облегчающие синхронизацию с объектами критической секции. Эти макросы описаны далее.

Типы данных синхронизации:

Функции синхронизации:

bool MakeSemaphore(
    SysSemaphoreObject& semaphore,
    int maxCount,
    int initialCount); 

bool DeleteSemaphore(
    SysSemaphoreObject& semaphore);
 

bool LockSemaphore(
    SysSemaphoreObject& semaphore); 

bool UnlockSemaphore(
    SysSemaphoreObject& semaphore,
    int count); 

bool MakeEvent(
    SysEventObject& event,
    bool intialState); 

bool DeleteEvent(
    SysEventObject& event); 

bool WaitForEvent(
    SysEventObject& event);

bool SignalEvent(
    SysEventObject& event); 

Макросы синхронизации:

Чтобы синхронизировать доступ к объекту с помощью макросов LOCK_OBJECT и LOCK_THIS_OBJECT, класс объекта должен использовать макрос DEFINE_SYNC_CLASS, вставляющий члены, используемые этими макросами.

Вставляются следующие члены:

•    атрибут mutable(изменяемый) GaCriticalSection _synchronizator и
•    метод GaCriticalSection* GACALL GetSynchronizator() const

class SomeClass
{
    DEFINE_SYNC_CLASS

    // остальная часть объявления класса
};

Пользователь может использовать макросы для синхронизации доступа к объекту класса.

void SomeMethod()
{
    SomeClass obj;

    // Объявляет объект GaSectionLock obj_lock,
    // использующий объект критической секции, встроенный в объект obj
    LOCK_OBJECT( obj_lock, obj );

    // ...код критической секции...

    // блокировка снимается автоматически
    // путем уничтожения объекта obj_lock
}
void SomeClass::SomeMethod()
{
    // Объявляет объект GaSectionLock obj_lock,
    // использующий объект критической секции, встроенный в текущий объект
    LOCK_THIS_OBJECT( obj_lock );

    // ...код критической секции...

    // блокировка снимается автоматически
    // путем уничтожения объекта obj_lock
}

Если критическая секция завершается раньше конца области видимости, макрос UNLOCK может использоваться для разблокировки объекта критической секции.

void SomeClass::SomeMethod()
{
    // Объявляет объект GaSectionLock obj_lock,
    // использующий объект критической секции, встроенный в текущий объект
    LOCK_THIS_OBJECT( obj_lock );

    // ...код критической секции...

    // снимается блокировка с объекта критической секции
    UNLOCK( obj_lock );

    // ...некритический код...

    // секцию можно снова заблокировать с использованием того же объекта блокировки
    LOCK( obj_lock );

    // ...критическая секция...
}

Можно заблокировать критическую секцию без применения объектов GaSectionLock. Макросы LOCK и UNLOCK можно применять непосредственно к объектам критической секции.

// ...

GaCriticalSection _criticalSection;

// ...

void SomeMethod()
{
    // блокируется объект критической секции
    LOCK( _criticalSection );

    // ...код критической секции...

    // снимается блокировка
    UNLOCK( _criticalSection );
}

Каталоги

Каталоги применяются для хранения доступных генетических операций. Каждый тип генетической операции имеет свой собственный каталог. Генетические операции хранятся в каталоге в виде пары [имя операции и указатель на объект операции]. Имя операции должно быть уникальным в каталоге. Пользователь может получить указатель на объект операции (функтор), указав имя операции. Шаблонный класс GaCatalogue управляет каталогами.

Схема - Класс GaCatalogue

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

Методы Register и Unregister добавляют или удаляют генетические операции из каталога. Метод GetEntryData находит генетические операции по их именам.

Библиотека генетических алгоритмов определяет 8 встроенных каталогов:
•    GaCrossoverCatalogue
•    GaMutationCatalogue
•    GaFitnessComparatorCatalogue
•    GaSelectionCatalogue
•    GaCouplingCatalogue
•    GaReplacementCatalogue
•    GaScalingCatalogue
•    GaStopCriteriaCatalogue

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

// использование встроенного каталога
GaSelectionOperation* select =
    GaSelectionCatalgoue::Instance().GetEntryData(
    "GaRandomSelect" );

// определенный пользователем каталог
GaCatalgoue<UserOperationType>::MakeInstance();

// зарегистрировать
GaCatalgoue<UserOperationType>::Instance().Register(
    "UserOperation1", new UserOperation1() );
GaCatalgoue<UserOperationType>::Instance().Register(
    "UserOperation2", new UserOperation2() );

// извлечь данные
UserOperationType* operation =
    GaCatalgoue<UserOperationType>::Instance().GetEntryData(
    "UserOperation1" );

// разрегистрировать
GaCatalgoue<UserOperationType>::Instance().Unregister(
    "UserOperation1");

// освободить ресурсы, используемые каталогом
GaCatalgoue<UserOperationType>::FreeIntance();

Каталоги управляют памятью, используемой зарегистрированными объектами.

Генераторы случайных чисел

Класс GaRandomGenerator реализует алгоритм RANROT генерации случайных чисел. Он генерирует 64-битное целое число [два 32-битных целых числа] за раз. Все остальные встроенные генераторы случайных чисел в библиотеке построены поверх этого класса.

Схема – Генераторы случайных чисел

Эти классы генератора случайных чисел имеют методы, генерирующие числа в заранее заданном интервале, между заранее заданным минимумом и определенным пользователем максимумом и между определенным пользователем минимумом и максимумом. GaRandomBool имеет два дополнительных метода, задающих вероятность генерации значения true.

Продолжение статьи вы найдете в третьей части данной серии.