Библиотека генетических алгоритмов - часть 1
ОГЛАВЛЕНИЕ
Данная статья является первой из четырех статей, повествующих о библиотеке генетических алгоритмов. В этой статье мы расскажем о структуре библиотеки, а также о хромосомах и популяциях, используемых в наших приложениях.
• Скачать исходный код библиотеки - 279 Кб
• Скачать исходный код демонстрационных приложений - 85.81 Кб
• Скачать демонстрационные приложения - 138.83 Кб
• Скачать документацию библиотеки - 1.03 Мб
• Последние версии библиотеки
Генетические алгоритмы
Генетические алгоритмы применяются к набору возможных решений. Из-за случайности генетических алгоритмов найденные ими решения могут быть хорошими, плохими или недопустимыми [дефектными, ошибочными], поэтому нужен способ определения пригодности решения. Это делается путем назначения значения пригодности [или просто пригодности] решению. Хромосомы представляют решения в рамках генетического алгоритма. Двумя основными частями хромосом являются закодированное решение и его значение пригодности.
Хромосомы группируются в популяцию [набор решений], к которой применяется генетический алгоритм. На каждом шаге [генерации] генетический алгоритм выбирает хромосомы из популяции [обычно выбор основан на значении пригодности хромосомы] и объединяет их для выработки новых хромосом [потомства]. Хромосомы потомства образуют новую популяцию [или заменяют некоторые из хромосом в существующей популяции] в надежде, что новая популяция будет лучше предыдущих. Популяции отслеживают худшие и лучшие хромосомы и хранят дополнительные статистические данные, используемые генетическим алгоритмом для определения критерия остановки.
Хромосома некоторым образом хранит представляемое ею решение. Это называется представлением [кодированием] решения. Есть ряд возможных способов представления решения в пригодном для генетического алгоритма виде [двоичный код, вещественное число, вектор вещественного числа, перестановки и так далее], зависящих от сути задачи.
Схема – Представления хромосом [для максимизации функции с единственным параметром]
Схема - Представления хромосом [Задача коммивояжера]
Генетические алгоритмы вырабатывают новые хромосомы [решения] путем объединения существующих хромосом. Такая операция называется кроссовером. Операция кроссовера берет части кодировок решения из двух существующих хромосом [родителей] и объединяет их в одно решение [новую хромосому]. Эта операция зависит от представления хромосомы и бывает очень сложной. Хотя общие операции кроссовера просты в реализации, построение специализированных операций кроссовера для конкретных задач может значительно повысить производительность генетического алгоритма.
Схема – Примеры операций кроссовера
Прежде чем генетический алгоритм закончит выработку новой хромосомы, после чего он выполняет операцию кроссовера, он производит операцию мутации. Операция мутации вносит случайные, но маленькие, изменения в закодированное решение. Это предотвращает попадание всех решений в локальный оптимум и расширяет область поиска алгоритма. Мутации, равно как и операции кроссовера, зависят от выбранного представления.
Схема – Примеры операций мутации [мутация перестановки производится над первой хромосомой, а над второй производится операция инвертирования]
Операции кроссовера и мутации не всегда выполняются при выработке новой хромосомы. Если кроссовер не выполняется, генетический алгоритм вырабатывает новую хромосому путем копирования одного из родителей. Проценты операций кроссовера и мутации называются вероятностью кроссовера и вероятностью мутации, соответственно. Вероятность кроссовера обычно высокая [около 80%], а вероятность мутации относительно низкая [около 3%, но для некоторых задач более высокая вероятность дает лучшие результаты]. Более высокая вероятность мутации может превратить генетический алгоритм в алгоритм случайного поиска.
Последними операциями, определяемыми генетическими алгоритмами и используемыми для манипулирования хромосомами, являются операции пригодности и сравнители пригодности. Операция пригодности измеряет качество выработанного решения [хромосомы]. Эта специфичная для задачи операция сообщает генетическому алгоритму, что оптимизировать. Сравнители пригодности [как следует из самого названия] применяются для сравнения хромосом на основе их пригодности. Сравнитель пригодности говорит генетическому алгоритму, должен ли он минимизировать или максимизировать значения пригодности хромосом.
Выбор родителей для выработки новых хромосом из популяции называется селекцией. Селекция может быть основана на множестве разных условий, но обычно она основана на значении пригодности. Выбираются лучшие хромосомы из родителей в надежде, что их объединение даст лучшие хромосомы-потомки. Но основной недостаток выбора только лучших хромосом заключается в том, что все хромосомы в популяции быстро начинают выглядеть одинаково. Это сужает область поиска, проталкивает генетический алгоритм в локальный оптимум и мешает генетическому алгоритму найти лучшие решения, находящиеся в недоступных участках области поиска. Чтобы сохранить разнообразие хромосом [и более широкую область поиска] внутри популяции, операции селекции обычно вносят фактор случайности в процесс селекции. Некоторые реализации операций селекции полностью случайны.
У операций селекции на базе значений пригодности есть проблема. В большинстве случаев будет выбираться хромосома со старшим значением пригодности, что вызовет проблемы, сходные с существующими. Во избежание этого значения пригодности можно масштабировать [преобразовать], чтобы уменьшить разность между старшей(ими) хромосомой(ами) и остальной популяцией [это позволяет выбрать другие хромосомы]. Есть много способов преобразования значения пригодности. Обычно они заключаются в применении математического преобразования к значению пригодности, но есть другие методы типа масштабирования на базе ранжирования, использующие ранг [основанный на непосредственных значениях пригодности хромосом] хромосомы в качестве масштабированного значения пригодности.
Схема – Масштабирование значения пригодности [показывает вероятность селекции хромосом]
Операция спаривания определяет, как выбранные хромосомы [родители] спариваются для скрещивания [скрещивание осуществляется путем выполнения операции кроссовера над спаренными родителями и применения операции мутации к вновь созданной хромосоме]. Эта операция позволяет лучше контролировать создание новых хромосом, но она может быть пропущена, и новые хромосомы могут создаваться, по мере того как операция селекции выбирает родителей из популяции.
Схема – Блок-схема операции спаривания
Схема – Блок-схема операции селекции без операции спаривания
На следующем шаге генетический алгоритм вводит новые хромосомы в популяцию. Хромосомы потомства могут образовать новую популяцию и заменить всю [предыдущую] популяцию [неперекрывающаяся популяция], или они могут заменить всего несколько хромосом в текущей популяции [перекрывающаяся популяция]. Для перекрывающихся популяций операция замены определяет, какие хромосомы удаляются [обычно худшие хромосомы] из текущей популяции, и какие хромосомы потомства вставляются. При замене хромосом генетический алгоритм может потерять лучшую хромосому(ы) [найденные до сих пор]. Во избежание этого в генетические алгоритмы вводится принцип элитизма. Элитизм гарантирует, что лучшая хромосома[ы] из текущего поколения сохранится в следующей генерации.
Алгоритм выполняет вышеописанные шаги подряд последовательно, и когда они были выполнены, говорится, что поколение прошло. В конце каждой генерации генетический алгоритм проверяет условие остановки. Из-за природы генетических алгоритмов большей частью неясно, когда алгоритм должен остановиться, поэтому условие обычно основано на статистических данных, таких как номер генерации, значение пригодности лучшей хромосомы, или среднее значение пригодности хромосом в популяции, длительность процесса эволюции...
Схема – Блок-схема генетического алгоритма [операция спаривания перекрывающейся популяции]
Схема - Блок-схема генетического алгоритма [перекрывающаяся популяция без операции спаривания]
Схема - Блок-схема генетического алгоритма [неперекрывающаяся популяция с операцией спаривания]
Библиотека генетических алгоритмов
Это краткое введение в устройство и структуру библиотеки генетических алгоритмов. Библиотека является набором классов C++, представляющих собой составляющие генетических алгоритмов.
Структура библиотеки
Следующая схема показывает основную структуру библиотеки генетических алгоритмов:
Схема - Структура библиотеки генетических алгоритмов
Первый слой в основном содержит классы, прямо не относящиеся к генетическим алгоритмам, но необходимые для их реализации. Библиотека генетических алгоритмов реализует генераторы случайных чисел, набор классов для платформно-независимой организации поточной обработки и синхронизации, интеллектуальные указатели для облегчения управления памятью [прежде всего для автоматического управления памятью, используемой хромосомами], и каталоги [каталоги применяются для хранения и отслеживания существующих генетических операций].
Кроме этих универсальных возможностей, библиотека предоставляет более специфичные для генетических алгоритмов вещи на низшем уровне, такие как классы для отслеживания статистических данных генетических алгоритмов и слежения за каркасом. Интерфейсы для объектов генетических операций и параметров также определены на этом уровне.
Вместе эти возможности предоставляют общий функционал, используемый остальными, более высокими уровнями библиотеки. Классы этого уровня разбиты на несколько пространств имен.
Часть среднего уровня разбита на три пространства имен, как показано на схеме. Большинство ключевых возможностей библиотеки реализовано на этом уровне.
Прежде всего, пространство имен Chromosome содержит набор интерфейсов и классов, используемых для представления хромосом в библиотеке и для определения их базового поведения в системе. Это пространство имен содержит объявление интерфейсов для 4 типов генетических операций: кроссовер, мутация, операция пригодности и сравнитель пригодности.
Второе пространство имен - Population. Основной класс этого пространства имен – класс, управляющий популяцией хромосом, хранит статистические данные и отслеживает лучшие и худшие хромосомы. Интерфейсы для операций селекции, спаривания, замены и масштабирования определены в этом пространстве имен.
Последнее пространство имен, Algorithm, определяет интерфейсы для генетических алгоритмов и реализует некоторые из их базовых поведений. Это пространство имен также определяет интерфейс для операций, реализующих условие остановки алгоритмов.
Эти два уровня являются ядром библиотеки.
Верхний уровень библиотеки реализует вышеназванные генетические операции, представления хромосом и генетические алгоритмы. Как сказано, все встроенные генетические операции рассортированы по соответствующим каталогам.
Схема – Пространства имен
Хромосомы
Хромосомы являются основными объектами в генетическом алгоритме. Хромосомы определены классом GaChromosome в этой библиотеке.
Схема – Класс GaChromosome
GaChromosome – интерфейс для фактических реализаций хромосом. Этот класс [интерфейс] определяет методы Crossover, Mutation, CalculateFitness и CompareFitness, представляющие вышеописанные генетические операции [мутация, кроссовер, операция пригодности и сравнитель пригодности].
Метод MakeCopy является виртуальным копирующим конструктором. Новые классы должны переопределить этот метод, и он должен возвращать новый экземпляр объекта хромосомы. Этот метод может копировать всю хромосому [набор заданных значений и закодированное решение], или он может копировать лишь набор заданных значений хромосомы [оставляя кодировку пустой]. Метод MakeFromPrototype создает новый объект хромосомы с таким же набором заданных значений, что и у текущего объекта, но случайно инициализирует кодировку решений.
Каждая хромосома имеет определенные параметры [такие как вероятность кроссовера и мутации]; эти параметры представлены классом GaChromosomeParams.
Схема - Класс GaChromosomeParams
GaChromosomeParams определяет вероятность мутации и кроссовера, размер мутации и число точек кроссовера, а также флаг "только улучшающая мутация". Конструктор по умолчанию инициализирует следующие параметры хромосомы по умолчанию:
• вероятность мутации: 3%
• размер мутации: 1 [изменяется только одно значение кодированного решения]
• разрешены только улучшающие мутации: да
• вероятность кроссовера: 80%
• число точек кроссовера: 1
Все классы параметров в библиотеке наследуют класс GaParameters.
Схема – Класс GaParameters
Этот класс [интерфейс] определяет метод Clone, являющийся виртуальным копирующим конструктором, и он должен возвращать указатель на новый объект параметров, являющийся копией текущего объекта.
Класс GaChromosomes является интерфейсом и не реализует никаких поведений. Однако несколько базовых свойств свойственно всем типам хромосом [хранение параметров хромосомы и значения пригодности]; эти свойства реализует класс GaDefaulChromosome. Кроме параметров, хромосомы могут иметь другие данные конфигурации [блок конфигурации хромосомы или CCB], и обычно эти данные одинаковы у всех хромосом в популяции. Хранение данных конфигурации хромосомы определяется классом GaChromosomeParamBlock.
Схема – Классы GaDefaultChromosome и GaChromosomeParamsBlock
Методы Crossover и Mutation класса GaDefaultChromosome выполняют эти генетические операции только с вероятностью, определенной параметрами хромосомы. Если надо выполнить операции, эти методы вызывают PerformCrossover и PerformMutation. Новые хромосомы, наследующие класс GaDefaultChromosome, должны переопределить PerformCrossover и PerformMutation, а не методы Crossover и Mutation.
Также этот класс вводит каркас для исключительно улучшающих мутаций. Перед выполнением операции мутации вызывается метод PrepareForMutation. Этот метод делает резервную копию старой хромосомы, после чего выполняется мутация. Затем сравниваются старая пригодность хромосомы [до мутации] и новая пригодность. Если мутация имеет улучшенную пригодность, она принимается, и вызывается метод AcceptMutation; в противном случае вызывается метод RejectMutation. Если не установлен флаг "только улучшающая мутация", мутации сразу принимаются без вызова упомянутых методов.
Операции кроссовера, мутации и пригодности могут быть реализованы путем наследования уже определенного класса, реализующего конкретные типы хромосом. Затем пользователь может переопределить методы PerformCrossover [или Crossover],PerformMutation [или Mutation] и CalculateFitness и реализовать конкретные операции для целевой задачи.
Библиотека генетических алгоритмов предоставляет другой способ добиться этого. Упомянутые генетические операции могут быть определены и реализованы в отдельных классах. Ссылки на объекты этих классов [называемые функторами] могут храниться в CCB. Это позволяет пользователю менять генетические операции во время выполнения [что невозможно при использовании ранее описанного метода].
Схема – Класс GaDynamicOperationChromosome и интерфейсы для генетических операций
GaDynamicOperationChromosome переопределяет методы PerformCrossover, PerformMutation, CalculateFitness и CompareFitnesses и направляет вызовы к функторам генетических операций, хранящимся в CCB.
CCB, представленный классом GaChromosomeOperationsBlock, хранит эти функторы.
GaCrossoverOperation – интерфейс для операции кроссовера. Определенные пользователем классы должны переопределять operator():
virtual GaChromosomePtr operator ()(
const GaChromosome* parent1,
const GaChromosome* parent2) const;
Параметры являются указателями на родителей, используемых операцией кроссовера. Оператор должен вернуть интеллектуальный указатель на созданную хромосому потомства.
GaMutationOperation – интерфейс для операции мутации. Определенные пользователем классы должны переопределять operator():
virtual void operator ()(GaChromosome* chromosome) const;
Этот оператор принимает [в качестве параметра] указатель на хромосому, над которой должна быть выполнена эта операция.
GaFitnessOperation – интерфейс для операции пригодности. Определенные пользователем классы должны переопределять operator():
virtual float operator ()(const GaChromosome* chromosome) const;
Этот оператор принимает [в качестве параметра] указатель на хромосому, над которой должна быть выполнена эта операция, и возвращает вычисленное значение пригодности хромосомы.
Последняя операция – сравнитель пригодности. Интерфейс для сравнителей пригодности определен классом GaFitnessComparator. Определенные пользователем классы должны переопределять operator():
virtual int operator ()
float fitness1,
float fitness2) const;
Этот оператор принимает два значения пригодности в качестве параметров и возвращает целое число:
1. -1, если первое значение пригодности меньше второго
2. 0, если эти два значения равны
3. 1, если первое значение пригодности больше второго
Все классы, реализующие генетические операции в библиотеке, наследуют класс GaOperation.
Схема – класс GaOperation
MakeParameters создает объект параметров, необходимый операции, и возвращает указатель на объект. Если операция не требует параметров, метод возвращает указатель NULL. Метод CheckParameters проверяет правильность предоставленных параметров и возвращает true в случае их правильности или false при их неправильности. Все генетические операции должны реализовывать эти два метода.
Библиотека генетических алгоритмов рассчитана на использование объектов генетических операций без внутреннего состояния [функторов]. Исходя из такого устройства, все встроенные операции лишены внутреннего состояния, но библиотека способна обрабатывать определенные пользователем операции, объекты которых обладают внутренним состоянием.
Популяции
Объекты популяций генетических алгоритмов представлены в библиотеке классом 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, каркас изменяет масштаб значений пригодности всех хромосом в популяции.
Схема – Интерфейс операции масштабирования
Продолжение статьи вы найдете во второй части данной серии здесь.