Оптимизация мутации генетических алгоритмов

Исследование на примере задачи оптимизации ранца.

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

Если вы не помните, как работает этот алгоритм машинного обучения, посмотрите мой предыдущий урок:

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

• размер популяции: количество особей в поколении.
• количество поколений: количество циклов.
• скорость мутации: вероятность мутации ДНК человека.

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

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

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

Если вы хотите следовать объяснениям с кодом, вы можете проверить мой репозиторий git. Он находится в файле «KnapsackProblem_Mutation».

Задача о ранце

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

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

• Набор предметов:

Это название набора ящиков, это массив ящиков. Коробка имеет два параметра: вес и значение.

• Физические лица:

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

• Подбор и размножение:

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

• Фитнес:

Для фитнес-функции есть 2 случая. Если индивидуум больше, чем вместимость рюкзака, фитнес равен нулю. В противном случае оно равно 2-кратному значению за вычетом веса предмета. Это лучшее решение, которое я нашел эмпирически.

• Мутация: внутригенная

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

Связь: «размер популяции» и «частота мутаций»

Изучение компромисса

Таким образом, мы попробуем разные значения: частота мутаций и размер популяции. Затем мы сравним их выступления. Какова производительность генетического алгоритма? Это его способность найти решение, максимально оптимизированное за заданное время. В заключение, мы собираемся дать ему ограниченное время и посмотреть на найденное решение. Чтобы убедиться в этом, мы нарисуем трехмерную карту их результатов. Библиотека, используемая для 3D-графика, будет mplot3d.

Полученные результаты

Первый шаг: влияние численности населения

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

• количество позиций: 500
• частота мутаций: 0%
• количество повторений для каждого значения: 50
• ограничение по времени: 0,05 с

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

Как мы можем это объяснить? Большой «размер популяции» подразумевает много вычислений в каждом поколении. Итак: чем больше численность населения, тем меньше количество поколений. Большой размер популяции подразумевает меньшее количество поколений и ограничивает эффективность этого алгоритма.

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

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

Второй шаг: влияние скорости мутаций и размера популяции

Теперь мы собираемся варьировать оба параметра и попытаться найти их совместное влияние на силу алгоритма.

Вот алгоритм, используемый для печати 3D-графика. Осторожно, здесь много импорта, здесь - документация, используемая для установки matplotlib.

Константы:

• количество позиций: 500
• частота мутаций: от 0 до 100
• численность населения: от 5 до 100 человек.
• количество повторов для каждого значения: 50
• ограничение по времени: 0,05 с

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

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

Чтобы проверить эту гипотезу, мы должны изменить реализацию мутации. Мы собираемся попробовать межгенную мутацию.

Последний шаг: влияние межгенной мутации и размера популяции

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

Константы:

• количество позиций: 500
• частота мутаций: от 0 до 100
• численность населения: от 5 до 100 человек.
• количество повторений для каждого значения: 50
• ограничение по времени: 0,05 с

Этот график непростой, я распечатаю разные срезы, чтобы подчеркнуть результаты.

Итак, мутация по-прежнему негативно влияет на алгоритм. Видимо, даже хуже.

Заключение

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

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

Оптимизированные значения в контексте задачи о ранце не оптимизируются в другом контексте. Значение пары «частота мутаций» «размер популяции» должно быть оптимизировано для вашего собственного алгоритма. Эта статья предназначена только для того, чтобы научить вас выбирать эти два значения. Я очень удивлен своими результатами. Если у вас есть встречные примеры или объяснения, я был бы рад их получить.

Вам понравилась эта статья? Не стесняйтесь комментировать или свяжитесь со мной.