Библиотека генетических алгоритмов - часть 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, каркас изменяет масштаб значений пригодности всех хромосом в популяции.

 

Схема – Интерфейс операции масштабирования

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