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

Written on .

ОГЛАВЛЕНИЕ

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

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

• Скачать исходный код библиотеки - 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 – базовый класс для параметров многопоточных алгоритмов. Он определяет число рабочих потоков, задействованных в выполнении генетического алгоритма.

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