Библиотека генетических алгоритмов - часть 1 - Популяции
ОГЛАВЛЕНИЕ
Популяции
Объекты популяций генетических алгоритмов представлены в библиотеке классом GaPopulation.
Схема - Класс GaPopulation
Объект популяции хранит хромосомы и статистические данные. Хромосомы в популяции представлены объектами класса GaScaledChromosome. Объекты этого класса привязывают хромосомы к популяции. Хромосомы, как правило, хранят данные, не зависящие от популяции, в которой находятся хромосомы, но часть информации о хромосомах зависит от популяции [например, масштабированная пригодность или индекс хромосом в популяции]. Эти данные являются членами класса GaScaledChromosome. Это облегчает разделение хромосом между популяциями, причем расходуется меньше памяти.
Хромосомы могут храниться в популяции в отсортированном или в неотсортированном порядке [по значению пригодности – масштабированному или непосредственному]. Надо сортировать популяцию или нет, зависит от других частей генетического алгоритма [например, от операции селекции], и этим управляют параметры популяции. Также легче отследить лучшие и худшие хромосомы, когда популяция отсортирована, но это требует больше времени. Если популяция не отсортирована, она использует сортированные группы [класс GaSortedGroup] для отслеживания этих хромосом. Сортированные группы хранят индексы хромосом в популяции. Число отслеженных хромосом [в обеих группах, лучших и худших] определяется параметрами популяции. Важно отметить, что отслеживание больших количества хромосом неэффективно; в таких случаях лучше использовать отсортированную популяцию.
Когда популяция создана, она не содержит никаких хромосом [она не инициализирована]. Метод Initialize заполняет популяцию путем создания новых хромосом с помощью метода MakeFromPrototype предоставленной прототипной хромосомы.
Схема – Хромосомы в популяции
Класс GaStatistics используется для хранения и отслеживания статистических данных популяции. Объекты этого класса хранят данные о текущем и предыдущем поколении популяции.
Схема - GaStatistics и служебные классы
Шаблонный класс GaStatValue хранит единственное статистическое значение. Перечисление GaStatValueType определяет отслеженные статистические данные. Эти данные применяются для измерения прогресса алгоритма, и их обычно использует условие остановки.
Поведением популяции управляют параметры популяции. Класс GaPopulationParameters управляет параметрами популяции.
Параметры – лишь один сегмент конфигурации популяции. Конфигурация также содержит генетические операции [выполняемые над популяцией - селекция, спаривание, замена и масштабирование] и их параметры. Класс GaPopulationConfiguration хранит и управляет конфигурацией. Конфигурацию можно разделить между популяциями. Метод BindPopulation применяет конфигурацию и привязывает к ней популяцию. UnbindPopulation сообщает популяции, что она больше не должна использовать конфигурацию, и отвязывает популяцию. При изменении любой составляющей конфигурации уведомляются все связанные популяции.
Когда объект конфигурации популяции создается и инициализируется с помощью стандартного конструктора, конструктор копирует стандартную конфигурацию. Ссылку на стандартную конфигурацию можно получить с помощью метода GetDefault. Пользователь может менять стандартную конфигурацию во время выполнения. При запуске стандартная конфигурация инициализируется в:
• параметры популяции:
o размер популяции: 10
o с изменяемым размером: нет
o сортированная: да
o масштабированное значение пригодности используется для сортировки: нет
o отслеживать лучшие хромосомы: 0 [сортированная популяция]
o отслеживать худшие хромосомы: 0 [сортированная популяция]
• сравнитель пригодности: GaMaxFitnessComparator
• селекция: GaSelectRouletteWheel, размер: 2
• спаривание: GaInverseCoupling, размер: 2
• замена: GaReplaceWorst, размер: 2
• масштабирование: нет
Схема – Управление конфигурацией популяции
Генетические операции и их параметры хранятся в виде пары в конфигурации. Конфигурация использует класс GaOperationParametersPair для хранения этих пар. Объект пары хранит указатель на объект операции и копию предоставленного объекта параметров операции.
Схема - класс GaOperationParametersPair
Интерфейс для операций селекции определяется классом GaSelectionOperation. Определенные пользователем классы должны переопределять operator():
virtual void operator ()(
const GaPopulation& population,
const GaSelectionParams& parameters,
GaSelectionResultSet& result) const;
Операция селекции принимает ссылку на объект популяции и ссылку на параметры селекции. Он также принимает ссылку на результирующий набор, хранящий выбранные хромосомы. Результирующий набор хранит индексы [в популяции] выбранных хромосом в сортированном порядке [по значению пригодности]. Класс GaSelectionResultSet обертывает класс GaSortdeGroup. Класс GaSelectionOperation имеет метод MakeResultSet, создающий новый экземпляр результирующего набора и возвращающий ссылку на него. Определенные пользователем классы могут переопределить этот метод, если операция селекции требует другой тип результирующего набора.
GaSelectionParams – базовый класс для параметров операций селекции. Этот класс определяет только один параметр [общий для всех операций селекции], размер селекции.
Схема – Интерфейс операции селекции
Интерфейс для операций спаривания определяется классом GaCouplingOperation. Определенные пользователем классы должны переопределять operator ():
virtual void GACALL operator ()(
const GaPopulation& population,
GaCouplingResultSet& output,
const GaCouplingParams& parameters,
int workerId,
int numberOfWorkers) const=0;
Операция спаривания принимает ссылку на объект популяции и ссылку на параметры спаривания. Она также принимает ссылку на результирующий набор [класс GaCouplingResultSet], хранящий выработанные хромосомы потомства и сведения об их родителях.
Операция спаривания может выполняться одновременно несколькими работающими потоками. Каркас дает число потоков, выполняющих операцию, и идентификатор потока, выполняющего текущий вызов операции.
GaCouplingParams – базовый класс для параметров операций спаривания. Этот класс определяет только один параметр [общий для всех операций спаривания], число вырабатываемых хромосом потомства.
Схема – Интерфейс операции спаривания
Интерфейс для операций замены определяется классом GaReplacementOperation. Определенные пользователем классы должны переопределять operator():
virtual void GACALL operator ()(
GaPopulation& population,
const GaReplacementParams& parameters,
const GaCouplingResultSet& newChromosomes) const;
Операция замены принимает ссылку на объект популяции, ссылку на параметры замены и ссылку на набор результатов операции спаривания, содержащий хромосомы потомства, подлежащие вставке в популяцию.
GaReplacementParams – базовый класс для параметров операций замены. Этот класс определяет только один параметр [общий для всех операций замены], число хромосом, подлежащих замене.
Схема – Интерфейс операции замены
Интерфейс для операций масштабирования определяется классом GaScalingOperation. Определенные пользователем классы должны переопределять operator(), методы IsRankingBase и NeedRescaling:
virtual float operator ()(
const GaScaledChromosome& chromosome,
const GaPopulation& population,
const GaScalingParams& parameters) const;
virtual bool IsRankingBased() const;
virtual bool NeedRescaling(
const GaPopulation& population,
const GaScalingParams& parameters) const;
• operator() принимает ссылку на объект популяции и ссылку на параметры масштабирования.
• IsRankingBased должен возвращать true, если реализация операции масштабирования основана на ранжировании хромосом. В противном случае он должен возвращать false.
• GaScalingParams – базовый класс для параметров операций масштабирования.
Масштабирование может быть основано на значениях, меняющихся от поколения к поколению, или может использовать значения, не меняющиеся в течение более длительного процесса вычисления, или вообще не меняющиеся значения. Масштабированные значения пригодности вычисляются при вставке новой хромосомы в популяцию, но изменение популяции может потребовать изменения масштаба значений пригодности всех хромосом в популяции. Метод NeedRescaling вызывается каркасом для проверки, надо ли менять масштаб, в конце каждой генерации. Если этот метод возвращает true, каркас изменяет масштаб значений пригодности всех хромосом в популяции.
Схема – Интерфейс операции масштабирования
Продолжение статьи вы найдете во второй части данной серии здесь.