Настройка параметров генетического алгоритма

Настройка параметров генетического алгоритма

Результат работы генетического алгоритма сильно зависит от того, каким образом настроены его параметры. Основными параметрами ГА являются:

– длительность эволюции (количество поколений);

– интенсивность (давление) селекции;

– тип оператора кроссинговера;

– вероятность кроссинговера Р_С;

– тип оператора мутации;

– величина разрыва поколений Т.

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

1. Исследование пространства поиска (exploration).

2. Использование найденных «хороших» решений (exploitation).

Первый аспект отвечает за способности ГА к эффективному поиску решения и характеризует способности алгоритма избегать локальных экстремумов. Второй аспект важен для постепенного улучшения имеющихся результатов от поколения к поколению на основе уже найденных «промежуточных» решений. Пренебрежение исследовательскими способностями приводит к существенному увеличению времени работы ГА и ухудшению результатов из-за «застревания» алгоритма в локальных экстремумах. В итоге становится возможной преждевременная сходимость генетического алгоритма (также говорят о вырождении популяции), когда решение еще не найдено, но в популяции практически все особи становятся одинаковыми и долгое время (порядка нескольких десятков и сотен поколений) не наблюдается улучшения приспособленности.

Игнорирование найденных решений может привести к тому, что работа ГА будет напоминать случайный поиск, что также отрицательно сказывается на эффективности поиска и качестве получаемых решений.

Основная цель в настройке параметров ГА и, одновременно, необходимое условие для стабильного получения хороших результатов работы алгоритма – это достижение баланса между исследованием пространства поиска и использованием найденных решений.

Взаимосвязь между параметрами генетического алгоритма, а также влияние параметров на эволюционный процесс имеют сложный характер. На рис. 5.7 схематично изображено влияние изменения некоторых параметров ГА на характеристики эволюционного поиска.

Рис. 5.7. Влияние параметров ГА на характеристики эволюционного поиска

Неправильная настройка параметров может стать причиной различных проблем в работе ГА. Краткий список часто встречающихся проблем и возможные пути их исправления приведены в табл. 5.1.

Дата добавления: 2014-12-23 ; просмотров: 18 ; Нарушение авторских прав

Источник

Генетический алгоритм vs алгоритм роя частиц

Введение

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

В данной статье под задачей оптимизации понимается нахождение экстремума (минимума) некоторой вещественной функции в заданной области. Будут рассмотрены два самых важных алгоритма в оптимизации: генетический алгоритм и алгоритм роя частиц.

Генетический алгоритм

Краткое описание

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

Каждая особь популяции будет обладать тремя основными параметрами: положением по оси Х, положением по оси У и значением целевой функции (именно это значение будет выступать в роли основного параметра при селекции).

На первом этапе происходит создание начальной популяции, где каждая особь случайным образом получает свои координаты по Х и У. Эта популяция может быть далека от идеала, но в процессе эволюции алгоритм должен будет исправить это.

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

После размножения отбирается часть особей, которая подвергается случайным мутациям в генах. В случае с поиском экстремума будет меняться положение индивида по координатам Х и У.

В самом конце должен произойти отбор наиболее приспособленных особей. Особи с наименьшим показателем значения целевой функции проходят дальше. Для того, чтобы популяция не росла беспрерывно, её численность регулируется определенным заданным параметром.

Шаги “размножение”, “мутация” и “отбор” повторяются до тех пор, пока не будет достигнута точка Останова. В качестве конца алгоритма зачастую выбирают либо достижение максимального числа итераций алгоритма, либо ….

Иногда добавляют новые правила для изменения популяции, например, добавляют оператор инверсии (в случае с бинарными генами) или ограничивают время жизни каждой особи. Также добавляют условия на поиск пары для скрещивания, где оба родителя будут схожи по каким-либо признакам или наоборот, будут сильно отличаться.

Реализация

Для начала необходимо реализовать класс одной особи, в качестве параметров он будет принимать: пределы области поиска экстремума, количество шагов для мутации и целевую функцию, а также у индивида будет 2 поля, отвечающих за позицию по Х и У координатам, и поле, отвечающее за значение функции в текущей позиции:

Теперь реализуем функцию мутации в классе самой особи:

Теперь реализуем сам класс для исполнения алгоритма. В качестве параметров в класс будем передавать: размер популяции; процент популяции, который сможет воспроизводить потомство; количество шагов для мутации; шанс мутации особи; количество исполнений алгоритма (количество раз для появления нового потомства), целевую функцию, а также область поиска экстремума. Также в классе будут храниться: наилучшее значение целевой функции для всех итераций и точка (х, у),в которой было получено наилучшее значение:

Реализуем функцию кроссовера (скрещивания). Новые координаты по Х будут находиться случайным образом между координатами первого родителя и второго родителя по Х, аналогичным образом определяются координаты потомка по У:

Теперь можно приступать к написанию функции запуска самого генетического алгоритма (назовем её startGenetic в классе Genetic). Сначала необходимо создать стартовую популяцию нашей колонии:

В качестве конца алгоритма будем считать количество итераций, которые пережила колония. В каждой новой итерации сортируем популяцию в порядке убывания (для нахождения минимума функции) и выбираем ту часть популяции, которая будет принимать участие в размножении:

И для каждой особи находим случайную пару, с которой она сможет дать потомство:

Проводим мутации над каждой особью и отбираем наиболее приспособленных особей в новой популяции, содержащей детей:

И в конце каждой итерации проверяем лучшую особь в новой популяции на наилучшее значение целевой функции в течение всего времени:

На этом весь алгоритм можно считать завершенным. Запустим и проверим алгоритм на функции сферы (её минимум находится в точке 0,0):

Как видно, алгоритм смог найти минимум функции с точностью до 5 знаков после запятой, что является очень хорошим результатом.

Алгоритм роя частиц

Немного об алгоритме

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

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

В классической реализации алгоритма роя частиц для определения скорости частицы используется формула:

Однако для улучшения алгоритма можно использовать другие формулы, например

Реализация алгоритма

Первым делом реализуем класс роя, который на вход будет принимать размер роя, коэффициенты приоритетов смещения частиц к разным точкам, количество итераций алгоритма, целевую функцию и область поиска экстремума:

Также для реализации необходимо создать класс для одной частицы:

Реализуем логику для расчета новой позиции частицы:

Теперь создадим метод для реализации алгоритма в классе Swarm и протестируем:

Сравниваем алгоритмы

В википедии есть несколько функций, которые чаще всего используют для проверки алгоритмов оптимизации. Наиболее интересными, на мой взгляд, являются функции Химмельблау и Табличная функция Хольдера, так как они имеют несколько глобальных минимумов. Для того, чтобы посмотреть, как работает алгоритм, можно создать GIF при помощи библиотек matplotlib (для отрисовки графиков) и imageio (для создания GIF). Создадим обе функции:

Запустим по 2 раза каждый алгоритм с целевой функцией Хольдера. Первым проверим, как работает генетический алгоритм:

Посмотрим, как сходится алгоритм (для первого теста):

До первых 30 итераций все особи распределялись по первым найденным точкам минимума, но после этого все собираются в одной точке. Так как этот алгоритм подразумевает случайные изменения, то при каждом новом запуске программы в одной из 4х точек минимума может начать доминировать один ген и все будущие поколения будут сходиться в этой одной точке.

Давайте посмотрим, как сработает алгоритм роя частиц:

Посмотрим на сходимость роя частиц для теста №1:

В отличии от генетического алгоритма все частицы начали плавно перемещаться в одну точку. Посмотрим на более простой пример, как сходится генетический алгоритм для функции Экли (у этой функции один минимум в точке (0,0)):

И эта же функция с использованием роя частиц:

Генетический алгоритм хуже сходится в одну точку, так как каждую новую итерацию в случайной позиции (между родителями) появляется новая особь, а также случайные мутации, которые не всегда могут попадать в нужную точку. Рой частиц плавно приближался к найденному минимуму.

Вывод

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

Источник

Введение.Основы генетических алгоритмов

1. Введение в генетические алгоритмы

В этом разделе описывается концепция простого генетического алгоритма (ГА), ориентированного на решение различных оптимизационных задач. Вводятся и содержательно описываются понятия, используемые в теории и приложениях ГА. Приводится фундаментальная теорема ГА и излагается теория схем, составляющие теоретическую базу ГА. Обсуждаются концептуальные вопросы, касающиеся преимуществ и недостатков ГА.

1.1. Простой генетический алгоритм

Основы теории генетических алгоритмов сформулированы Дж. Г.Холландом в основополагающей работе [2] и в дальнейшем были развиты рядом других исследователей. Наиболее известной и часто цитируемой в настоящее время является монография Д.Голдберга [3], где систематически изложены основные результаты и области практического применения ГА.

ГА используют принципы и терминологию, заимствованные у биологической науки – генетики. В ГА каждая особь представляет потенциальное решение некоторой проблемы. В классическом ГА особь кодируется строкой двоичных символов – хромосомой, каждый бит которой называется геном. Множество особей – потенциальных решений составляет популяцию. Поиск оптимального или субоптимального решения проблемы выполняется в процессе эволюции популяции, т.е. последовательного преобразования одного конечного множества решений в другое с помощью генетических операторов репродукции, кроссинговера и мутации. ЭВ используют механизмы естественной эволюции, основанные на следующих принципах:

Эти три принципа составляют ядро ЭВ. Используя их, популяция (множество решений данной проблемы) эволюционирует от поколения к поколению.

Эволюцию искусственной популяции – поиск множества решений некоторой проблемы, формально можно описать в виде алгоритма, который представлен на рис.1.1.

ГА получает множество параметров оптимизационной проблемы и кодирует их последовательностями конечной длины в некотором конечном алфавите (в простейшем случае в двоичном алфавите «0» и «1»).

Предварительно простой ГА случайным образом генерирует начальную популяцию хромосом (стрингов). Затем алгоритм генерирует следующее поколение (популяцию) с помощью трех следующих основных генетических операторов :

В процессе поиска решения необходимо соблюдать баланс между «эксплуатацией» полученных на текущий момент лучших решений и расширением пространства поиска. Различные методы поиска решают эту проблему по-разному.

Например, градиентные методы практически основаны только на использовании лучших текущих решений, что повышает скорость сходимости с одной стороны, но порождает проблему локальных экстремумов с другой. В полярном подходе случайные методы поиска используют все пространство поиска, но имеют низкую скорость сходимости. В ГА предпринята попытка объединить преимущества этих двух противоположных подходов. При этом операторы репродукции и кроссинговера делают поиск направленным. Широту поиска обеспечивает то, что процесс ведется на множестве решений – популяции и используется оператор мутации.

В отличие от других методов оптимизации ГА оптимизируют различные области пространства решений одновременно и более приспособлены к нахождению новых областей с лучшими значениями целевой функции за счет объединения квазиоптимальных решений из разных популяций.

Упомянутые генетические операторы являются математической формализацией приведенных выше трех основополагающих принципов Ч.Дарвина, Г.Менделя и де Вре естественной эволюции. Каждый из функциональных блоков ГА на рис. 1.1. может быть реализован различными способами. Но сначала на простом примере мы рассмотрим основные моменты классического ГА.

Источник

Генетический алгоритм

Материал из MachineLearning.

Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Содержание

Постановка задачи

Для функции приспособленности в пространстве поиска требуется найти (или ).

Описание алгоритма

В процессе селекции выживают отбирают только несколько лучших пробных решений, остальные далее не используются. Скрещивание за место пары решений создаёт другую, элементы которой перемешаны каким-то особым образом. Мутация случайным образом меняет какую-нибудь компоненту пробного решения на иную.

Иные обозначения

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

Встречаются такие обозначения:

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

Генетические алгоритмы применяются для решения следующих задач:

Подробное описание алгоритма

Кодирование пространства поиска

В ГА часто используют следующие типы кодирования компонент пространства поиска:

Начальная популяция

Оценка приспособленности

Оператор отбора (селекции)

На этом этапе отбирается оптимальная популяция для дальнейшего размножения. Обычно берут определённое число лучших по приспособленности. Имеет смысл также отбрасывать «клонов», т.е. особей с одинаковым набором генов.

Оператор скрещивания

Оператор мутаций

Критерии останова

Эвристики

Генетические алгоритмы богаты возможностями встраивания различных эвристик. До сих пор не существует (и не будет!) точных критериев оптимального размера популяции, способов мутаций и скрещивания, выбора начальной популяции и т.п.

Плоидность

Мета ГА

Простейший пример ГА

Подбор ключа 2048 бит

Эффективность генетических алгоритмов

Холланд недвусмысленно пишет[1], что при прочих равных условиях ГА будет работать хуже, чем специальный алгоритм, рассчитанный на конкретную задачу (тип признаков, целевую функцию). Например, полный перебор конечного небольшого пространства или любой эффективных алгоритм спуска будет всегда эффективнее чем ГА. Тем не менее, в ситуации, когда о задаче ничего a priori не известно, можно полагаться на результат работы простейшего генетического алгоритма как некого приближения.

Существуют некоторый класс функций (Hyperplane-defined functions, Holland), с которым за приемлемое время[2] справляются только генетические алгоритмы.

Тестовые функции

В процессе разработки эффективной реализации генетического алгоритма появляется необходимость простой тестовой функции, которая

Мнения

Конвергенция с генетикой и синтетической теории эволюции

Прообраз генетического алгоритма пришёл из биологии и, несомненно, продолжает «подсматривать» оттуда ответы на многие вопросы, возникающие при проектированию эффективных реализаций генетических алгоритмов. Более того, идеи по оптимизации ГА находят подтверждение и у биологов. Например, такие явления как га- ди- и квадру- плоидные наборы хромосом, инцест, удвоение гена, управление скоростью мутаций, триггеры и т.п. Тем не менее, математика и кибернетика позволяет выйти за пределы химической реальности клетки и представить n-плоидный набор хромосом, объектные сущности вместо генов и т.п.

Нейронные сети и эволюционное моделирование

ИНС и ГА часто пытаются применять в тандеме, т.к. и те и другие имеют корни из биологии. Тем не менее (см. выше об эффективности ), во-первых алгоритм обратного распространения ошибки настройки ИНС работает значительно (на порядок) быстрее в простых случаях. А во-вторых, настройка нейронной сети в биологии происходит методом, который, скорее всего, значительно разнится с генетическим подходом.

Аналогия с другими алгоритмами

В случае отключённого кроссинговера ГА начинает вести себя по образу случайного поиска. Также у ГА есть аналогия со случайным поиском с адаптацией. Во многих стохастических алгоритмах можно найти аналогию с ГА.

Источник

Optlib. Реализация генетического алгоритма оптимизации на Rust

Проблема глобальной оптимизации

Для некоторой заданной функции f(x) среди всех возможных значений x найти такое значение x’, при котором f(x’) принимает минимальное (или максимальное) значение. При этом x может принадлежать различным множествам — натуральным числам, вещественным числам, комплексным числам, векторам или матрицам.

Существует множество алгоритмов, которые гарантированно находят экстремум функции, который является локальным минимумом или максимумом вблизи заданной начальной точки x₀. К таким алгоритмам относятся, например, алгоритмы градиентного спуска. Однако на практике часто нужно найти глобальный минимум (или максимум) функции, которая в заданном диапазоне изменения x помимо одного глобального экстремума имеет множество локальных экстремумов.

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

Один из наиболее известных (и сложных в реализации) алгоритмов — генетический алгоритм.

Общая схема генетического алгоритма

Идея генетического алгоритма рождалась постепенно и была сформирована в конце 1960-х — начале 1970-х годов. Мощное развитие генетические алгоритмы получили после выхода книги Джона Холланда «Адаптация в естественных и искусственных системах» (1975 г.)

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

Генетические алгоритмы применяются во многих областях. Например, их можно использовать для подбора весовых коэффициентов в нейронных сетях. Многие CAD-системы используют генетический алгоритм для оптимизации параметров устройства, чтобы удовлетворить заданным требованиям. Также алгоритмы глобальной оптимизации можно применять для подбора расположения проводников и элементов на плате.

Структурная схема генетического алгоритма показана на следующем рисунке:

Рассмотрим каждый этап алгоритма более подробно.

Создание начальной популяции

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

Вместо случайного распределения хромосом можно создавать хромосомы таким образом, чтобы начальные значения x были равномерно распределены по всей области поиска с заданным шагом, который зависит от того, какое количество особей будет создано на данном этапе алгоритма.

Чем больше особей будет создано на данном этапе, тем больше вероятность того, что алгоритм найдет правильное решение, а также при увеличении размера начальной популяции как правило требуется меньшее количество итераций генетического алгоритма (количество поколений). Однако при росте размера популяции требуется все большее количество расчетов целевой функции и выполнения других генетических операций на последующих этапах алгоритма. То есть при увеличении размера популяции увеличивается время расчета одного поколения.

В принципе, размер популяции не обязан оставаться постоянным на протяжении всей работы генетического алгоритма, часто по мере увеличения номера поколения размер популяции можно уменьшать, т.к. со временем все большее количество особей будут располагаться все ближе к искомому решению. Однако часто размер популяции поддерживают примерно постоянным.

Выбор особей для скрещивания

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

Лучше дать больший шанс на скрещивание особям с более удачными хромосомами (с минимальным значением целевой функции), а тех особей, у которых целевая функция больше (хуже) лишить возможности оставить потомство.

Таким образом, на данном этапе нужно создать пары особей (или не обязательно пары, если в скрещивании могут участвовать большее количество особей), для которых на следующем этапе будет проводиться операция скрещивания.

Здесь также можно применять различные алгоритмы. Например, создавать пары случайным образом. Или можно отсортировать особей по возрастанию значению целевой функции и создавать пары из особей, расположенных ближе к началу отсортированного списка (например, из особей в первой половине списка, в первой трети списка и т.п.) Данный метод плох тем, что требуется время на сортировку особей.

Часто используется метод турнира. Когда на роль каждого претендента на скрещивание случайным образом выбирают несколько особей, среди которых в будущую пару отправляется та особь, у которой лучшее значение целевой функции. И даже здесь можно ввести элемент случайности, дав небольшой шанс особи с худшим значением целевой функции «победить» особь с лучшим значением целевой функции. Это позволяет поддерживать популяцию более разнородной, обезопасив ее от вырождения, т.е. от ситуации, когда все особи имеют примерно равные значения хромосом, что равносильно сваливанию алгоритма к одному экстремуму, возможно, не глобальному.

Результатом данной операции будет список партнеров для скрещивания.

Скрещивание

Скрещивание — это генетическая операция, в результате которой создаются новые особи с новыми значениями хромосом. Новые хромосомы создаются на основе хромосом родителей. Чаще всего в процессе скрещивания одного набора партнеров создается одна дочерняя особь, но теоретически дочерних особей может создаваться больше.

Алгоритм скрещивания также можно реализовать разными способами. Если у особей тип хромосом — число, то самое простое, что можно сделать, это создать новую хромосому как среднее арифметическое или среднее геометрическое от хромосом родителей. Для многих задач этого достаточно, но чаще всего применяют другие алгоритмы на основе битовых операций.

Побитовое скрещивание работает таким образом, что дочерняя хромосома состоит из части бит одного родителя и части бит другого родителя, как показано на следующем рисунке:

Точка разбиения родителей обычно выбирается случайным образом. Не обязательно при таком скрещивании создавать два ребенка, часто ограничиваются одним из них.

Если точка разбиения родительских хромосом одна, то такое скрещивание называется одноточечным. Но можно использовать и многоточечное разбиение, когда хромосомы родителей разбиваются на несколько участков, как показано на следующем рисунке:

В этом случае возможно больше комбинаций дочерних хромосом.

Если хромосомы представляют собой числа с плавающей точкой, то к ним можно применять все описанные выше способы, но они будут не очень эффективны. Например, если числа с плавающей точкой скрещивать побитово, как было описано ранее, то многие операции скрещивания будут создавать дочерние хромосомы, которые будут отличны от одного из родителей только лишь в дальнем знаке после запятой. Ситуация особенно усугубляется, если использовать числа с плавающей точкой двойной точности.

Во многих задачах особь имеет не одну, а несколько хромосом, причем может быть даже разных типов (целые и числа с плавающей точкой). Тогда возникает еще больше вариантов скрещивания таких хромосом. Например, при создании дочерней особи можно скрещивать все хромосомы родителей, а можно некоторые хромосомы полностью передавать от одного из родителей без изменений.

Мутация

Мутация — важный этап генетического алгоритма, который поддерживает разнообразие хромосом особей и таким образом уменьшает шансы на то, что решение быстро сойдется к какому-то локальному минимуму вместо глобального. Мутация представляет собой случайное изменение в хромосоме особи, которая была только что создана путем скрещивания.

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

Так же как и для скрещивания, для мутации можно использовать разные алгоритмы. Например, можно заменять одну хромосому или несколько хромосом на случайную величину. Но чаще всего используют побитовую мутацию, когда в хромосоме (или в нескольких хромосомах) инвертируют один бит или несколько битов, как показано на следующих рисунках.

Мутация одного бита:

Мутация нескольких битов:

Количество бит для мутации может либо заранее задаваться, либо быть случайной величиной.

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

Отбор

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

Алгоритмы отбора также могут быть различные. Часто в первую очередь отбрасываются особи, чьи хромосомы не попадают в заданный интервал поиска решения.

Затем можно отбросить такое количество наименее удачных особей, чтобы поддерживать постоянный размер популяции. Также могут применяться различные вероятностные критерии для отбора, например, вероятность отбора особи может зависеть от значения целевой функции.

Условия окончания алгоритма

Так же как и в других этапах генетического алгоритма, существует несколько критериев окончания алгоритма.

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

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

Также существует неблагоприятная ситуация, когда хромосомы всех особей имеют одно и то же значение. Это так называемая вырожденная популяция. Скорее всего в этом случае алгоритм застрял в одном экстремуме, и не обязательно глобальном. Вывести популяцию из такого состояния способна только удачная мутация, но поскольку вероятность мутации обычно устанавливают небольшой, и далеко не факт, что мутация создаст более удачную особь, то обычно ситуация с вырожденной популяцией рассматривается как повод остановить генетический алгоритм. Для проверки такого критерия нужно сравнить хромосомы всех особей, есть ли среди них различия, и если различий нет, то остановить алгоритм.

В некоторых задачах не требуется нахождения глобального минимума, а нужно найти достаточно хорошее решение — решение, значение целевой функции для которого меньше заданной величины. В этом случае алгоритм можно остановить досрочно, если найденное на очередной итерации решение удовлетворяет данному критерию.

optlib

Optlib — это библиотека для языка Rust, предназначенная для оптимизации функций. На момент написания этих строк в библиотеке реализован только генетический алгоритм, но в будущем планируется расширять эту библиотеку, добавляя в нее новые алгоритмы оптимизации. Optlib полностью написана на Rust.

Optlib — библиотека с открытым кодом, она распространяется под лицензией MIT.

optlib::genetic

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

Модуль optlib::genetic создан таким образом, чтобы можно было собирать генетический алгоритм «из кубиков». При создании экземпляра структуры, внутри которой будет происходить работа генетического алгоритма, нужно указать, какие алгоритмы будут использоваться для создания популяции, выбора партнеров, скрещивания, мутации, отбора, а также какой критерий используется для прерывания алгоритма.

В библиотеке уже существуют наиболее часто используемые алгоритмы этапов генетического алгоритма, но можно создавать и свои типы, реализующие соответствующие алгоритмы.

В библиотеке наиболее хорошо проработан случай, когда хромосомы — это вектор дробных чисел, т.е. когда минимизируется функция f(x), где x — это вектор чисел с плавающей точкой (f32 или f64).

Пример оптимизации с использованием optlib::genetic

Прежде чем начать подробно описывать модуль genetic, рассмотрим пример его использования для минимизации функции Швефеля (Schwefel function). Эта многомерная функция рассчитывается следующим образом:

Типаж Optimizer объявлен в модуле optlib следующим образом:

Поскольку многие стохастические алгоритмы оптимизации используют так называемых агентов (в терминах генетического алгоритма агент — это особь), то модуль optlib также содержит типаж AlgorithmWithAgents с единственным методом get_agents(), который должен возвращать вектор агентов.

Агент, в свою очередь, — это структура, которая реализует еще один типаж из optlib — Agent.

Типажи AlgorithmWithAgents и Agent объявлены в модуле optlib следующим образом:

И для AlgorithmWithAgents, и для Agent тип T имеет то же значение, что и для Optimizer, то есть это тип объекта, для которого рассчитывается значение целевой функции.

Структура GeneticOptimizer — реализация генетического алгоритма

Для структуры GeneticOptimizer реализованы оба типажа — Optimizer и AlgorithmWithAgents.

Каждый этап генетического алгоритма представлен своим типажом, который можно реализовать с нуля или воспользоваться одной из имеющихся внутри optlib::genetic реализаций. Для каждого этапа генетического алгоритма внутри модуля optlib::genetic есть подмодуль со вспомогательными структурами и функциями, которые реализуют наиболее часто используемые алгоритмы этапов генетического алгоритма. Про эти модули будет сказано ниже. Также внутри некоторых таких подмодулей существует подмодуль vec_float, реализующие этапы алгоритма для случая, если целевая функция рассчитывается от вектора чисел с плавающей точкой (f32 или f64).

Конструктор структуры GeneticOptimizer объявлен следующим образом:

Конструктор GeneticOptimizer принимает множество объектов-типажей, которые влияют на каждый этап работы генетического алгоритма, а также на вывод результатов работы:

Иногда после останова алгоритма полезно изменить параметры алгоритма или используемые методы. Это можно сделать с помощью следующих методов структуры GeneticOptimizer: replace_pairing(), replace_cross(), replace_mutation(), replace_pre_birth(), replace_selection(), replace_stop_checker(). Эти методы позволяют заменить типажи-объекты, переданные структуре GeneticOptimizer при ее создании.

Основные типажи для генетического алгоритма рассматриваются в следующих разделах.

Типаж Goal — целевая функция

Типаж Goal объявлен в модуле optlib::genetic следующим образом:

Метод get() должен возвращать значение целевой функции для заданной хромосомы.

Внутри модуля optlib::genetic::goal содержится структура GoalFromFunction, которая реализует типаж Goal. Для этой структуры есть конструктор, принимающий функцию, которая является целевой функцией. То есть с помощью этой структуры можно создавать типаж-объект Goal из обычной функции.

Типаж Creator — создание начальной популяции

Типаж Creator описывает «создателя» начальной популяции. Этот типаж объявлен следующим образом:

Метод create() должен возвращать вектор хромосом, на основе которых будет создана начальная популяция.

Для случая, если оптимизируется функция от нескольких чисел с плавающей точкой, в модуле optlib::genetic::creator::vec_float есть структура RandomCreator для создания начального распределения хромосом случайным образом.

Структура RandomCreator объявлена следующим образом:

Здесь NumCast — это типаж из крейта num. Этот типаж позволяет создавать тип из других числовых типов с помощью метода from().

Здесь population_size — размер популяции (количество наборов хромосом, которое нужно создать), а intervals — это вектор кортежей из двух элементов — минимальным и максимальным значением соответствующей хромосомы (гена) в наборе хромосом, а размер этого вектора определяет сколько хромосом содержится в наборе хромосом у каждой особи.

В примере, приведенном выше, оптимизировалась функция Швефеля для 15 переменных типа f32. Каждая переменная должна лежать в интервале [-500; 500]. То есть для создания популяции вектор interval должен содержать 15 кортежей (-500.0f32, 500.0f32).

Типаж Pairing — выбор партнеров для скрещивания

Типаж Pairing используется для выбора особей, которые будут скрещиваться между собой. Этот типаж объявлен следующим образом:

Метод get_pairs() заимствует указатель на структуру Population, которая содержит в себе все особи популяции, а также через эту структуру можно узнать лучшую и худшую особь в популяции.

Метод get_pairs() типажа Pairing должен вернуть вектор, который содержит вектора, которые хранят индексы особей, которые будут скрещиваться между собой. В зависимости от алгоритма скрещивания (о них будет сказано в следующем разделе) скрещиваться могут две и более особи.

Например, если будут скрещиваться особи с индексом 0 и 10, 5 и 2, 6 и 3, то метод get_pairs() должен вернуть вектор vec![vec![0, 10], vec![5, 2], vec![6, 3]].

Модуль optlib::genetic::pairing содержит две структуры, реализующие различные алгоритмы выбора партнеров.

Для структуры RandomPairing реализован типаж Pairing таким образом, что для скрещивания партнеры выбираются случайным образом.

Для структуры Tournament типаж Pairing реализован таким образом, чтобы использовался метод турнира. Метод турнира подразумевает, что каждая особь, которая будет участвовать в скрещивании, должна победить другую особь (значение целевой функции победившей особи должно быть меньше). Если в методе турнира используется один раунд, это значит, что случайным образом выбираются две особи, и в будущую «семью» попадает особь с меньшим значением целевой функции среди этих двух особей. Если используется несколько раундов, то победившая особь таким образом должна выиграть у нескольких случайных особей.

Конструктор структуры Tournament объявлен следующим образом:

Типаж Cross — скрещивание

После того, как были сформированы «семьи» из особей, для скрещивания, нужно скрестить их хромосомы, чтобы получить детей с новыми хромосомами. Этап скрещивания представлен типажом Cross, который объявлен следующим образом:

Метод cross() выполняет скрещивание одного набора родителей. Этот метод принимает параметр parents — срез из ссылок на хромосомы родителей (не сами особи) — и должен вернуть вектор из новых хромосом. Размер parents зависит от алгоритма выбора партнеров для скрещивания с помощью типажа Pairing, который был описан в предыдущем разделе. Часто используется алгоритм, который создает новые хромосомы на основе хромосом из двух родителей, тогда размер parents будет равен двум.

В модуле optlib::genetic::cross содержатся структуры, для которых реализован типаж Cross с разными алгоритмами скрещивания.

Типаж Mutation — мутация

После скрещивания необходимо провести мутацию полученных детей, чтобы поддерживать разнообразие хромосом, и популяция не скатилась к вырожденному состоянию. Для популяции предназначен типаж Mutation, который объявлен следующим образом:

Единственный метод mutation() типажа Mutation заимствует ссылку на хромосому и должен вернуть возможно измененную хромосому. Как правило, устанавливают небольшую вероятность мутации, например, единицы процентов, чтобы все-таки сохранялись хромосомы, полученные на основе родителей и таким образом улучшали популяцию.

Некоторые алгоритмы мутации уже реализованы в модуле optlib::genetic::mutation.

В этом модуле, например, содержится структура VecMutation, которая работает аналогично структуре VecCrossAllGenes, т.е. в случае если хромосома — это вектор, VecMutation принимает типаж-объект Mutation и применяет его с заданной вероятностью для всех элементов вектора, создавая новый вектор с мутированными генами (элементами вектора-хромосомы).

Также в модуле optlib::genetic::mutation содержится структура BitwiseMutation, для которой реализован типаж Mutation. Эта структура инвертирует заданное количество случайных бит в переданной ей хромосоме. Эту структуру целесообразно использовать вместе со структурой VecMutation.

Типаж PreBirth — отбор перед рождением

После скрещивания и мутации обычно наступает этап отбора, на котором уничтожаются самые неудачные особи. Однако в реализации генетического алгоритма в библиотеке optlib::genetic перед этапом отбора есть еще один этап, на котором можно отбросить неудачные хромосомы. Этот этап был добавлен, потому что расчет целевой функции для особей часто занимает достаточно много времени, и незачем ее рассчитывать, если хромосомы не попадают в заведомо известный интервал поиска. Например, в приведенном выше примере должны быть отброшены хромосомы, которые не попадают на отрезок [-500; 500].

Для выполнения такой предварительной фильтрации предназначен типаж PreBirth, который объявлен следующим образом:

Единственный метод pre_birth() типажа PreBirth заимствует ссылку на упоминаемую выше структуру Population, а также изменяемую ссылку на вектор хромосом new_chromosomes. Это вектор хромосом, полученных после этапа мутации. Реализация метода pre_birth() должна удалить из этого вектора те хромосомы, которые заведомо не подходят по условию задачи.

Для случая, если оптимизируется функция от вектора чисел с плавающей точкой, в модуле optlib::genetic::pre_birth::vec_float содержится структура CheckChromoInterval, предназначенная для удаления хромосом, если они представляют собой вектор чисел с плавающей точкой, и какой-нибудь элемент вектора не попадает в заданный интервал.

Конструктор структуры CheckChromoInterval выглядит следующим образом:

Здесь конструктор принимает вектор кортежей с двумя элементами — минимальным и максимальным значением для каждого элемента в хромосоме. Таким образом, размер вектора intervals должен совпадать с размером вектора-хромосомы особей. В приведенном выше примере в качестве intervals использовался вектор из 15 кортежей (-500.0f32, 500.0f32).

Типаж Selection — отбор

После предварительного отбора хромосом создаются особи и помещаются в популяцию (структуру Population). В процессе создания особей для каждой из них рассчитывается значение целевой функции. На этапе отбора нужно уничтожить некоторое количество особей, чтобы популяция не разрасталась бесконечно. Для этого используется типаж Selection, который объявлен следующим образом:

Объект, который реализует типаж Selection, в методе kill() должен вызвать метод kill() структуры Individual (особь) для каждой особи в популяции, которую нужно уничтожить.

Для обхода всех особей в популяции можно воспользоваться итератором, который возвращает метод IterMut() структуры Population.

Поскольку часто нужно применять несколько критериев отбора, то при создании структуры GeneticOptimizer, конструктор принимает вектор типажей-объектов Selection.

Как и с другими этапами генетического алгоритма, в модуле optlib::genetic::selection уже предлагается несколько реализаций этапа отбора.

Типаж StopChecker — критерий останова

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

Здесь метод can_stop() должен вернуть true, если алгоритм можно останавливать, в противном случае этот метод должен вернуть false.

Модуль optlib::genetic::stopchecker содержит несколько структур с базовыми критериями останова и две структуры для создания комбинаций из других критериев:

Типаж Logger — лог работы алгоритма

Типаж Logger не влияет на работу генетического алгоритма, но позволяет следить за его работой, а также с помощью этого типажа можно организовать сбор статистики, связанной с работой алгоритма. Типаж Logger описан следующим образом:

В модуле optlib::genetic::logging содержатся следующие структуры, реализующие типаж Logger:

Функции для тестирования алгоритмов оптимизации

Функция Швефеля

Для тестирования алгоритмов оптимизации было придумано достаточно много функций со множеством локальных экстремумов. Модуль optlib::testfunctions содержит несколько функций, на которых можно тестировать алгоритмы. На момент написания этой статьи в модуле optlib::testfunctions содержится всего две функции.

Одна из этих функций — функция Швефеля, о которой писалось в самом начале статьи. Еще раз напомню, что эта функция записывается следующим образом:

В модуле optlib::testfunctions эта функция называется schwefel. Эта функция принимает вектор из N значений.

Многомерный параболоид

Другая функция для тестирования намного более простая, она имеет всего один экстремум, и для ее оптимизации достаточно простого градиентного спуска, однако эта функция полезна для отладки алгоритмов оптимизации, чтобы выявить проблемы на простой функции.

Эта функция записывается следующим образом:

Эта функция принимает минимальное значение в точке x’ = (1.0, 2.0,… N). Значение функции в этой точке равно нулю.

В модуле optlib::testfunctions эта функция называется paraboloid.

Заключение

Описанная выше библиотека optlib позволяет создавать различные алгоритмы оптимизации, которые можно динамически выбирать в процессе выполнения программы. На момент написания этой статьи в этой библиотеке реализован только генетический алгоритм (модуль optlib::genetic), однако в будущем планируется добавить и другие алгоритмы глобальной оптимизации, такие как алгоритм роя частиц, алгоритм роя пчел, алгоритм имитации отжига и др.

Многое еще можно улучшать в модуле optlib::genetic. Помимо добавления новых алгоритмов для различных этапов работы генетического алгоритма для ускорения расчета можно использовать параллельные вычисления. Также планируется добавить новые логгеры для вывода результатов не в консоль, а в файлы, а также структуру для сбора статистики процесса работы алгоритма, чтобы можно было построить график сходимости генетического алгоритма, узнать сколько раз вызывался расчет целевой функции.

В качестве отдельного примера может быть полезна программа, которая запускает генетический алгоритм множество раз и сохраняет усредненную статистику. Хотелось бы сделать программу с графическим интерфейсом, которая бы выводила статистику выполнения алгоритма в процессе работы (график сходимости, распределение особей по пространству поиска и т.д.)

Помимо этого планируется добавить новые аналитические функции (помимо функции Швефеля) для тестирования алгоритмов оптимизации.

Еще раз напомню ссылки, связанные с библиотекой optlib:

Источник