Курс эволюционных вычислений
Блок 3) Генетический алгоритм: функции контрольного теста
Применение концепций курса генетических алгоритмов к ряду реальных задач оптимизации!
Здравствуйте и добро пожаловать обратно на этот полный курс по эволюционным вычислениям! В этом посте мы рассмотрим генетический алгоритм для оценки тестовых функций на основе материала, изученного на данный момент из Модуля 3, Генетические алгоритмы. Поскольку это продолжение серии, если вы еще не читали эту статью, сделайте это, чтобы не остаться в неведении! Вы можете проверить это здесь:
Содержание
- Постановка задачи
- Новые аргументы
- Некоторая помощь
- Реализация
- Результаты различных гиперпараметров
- Видео Объяснение
- Оценка других функций тестирования производительности
- Заключение
Заявление о проблеме
В предыдущем посте мы подробно остановились на основных концепциях эволюционных вычислений, а именно на операторах кроссовера и мутации, и завершились этим «коротким» тривиальным примером. Если вы поняли материал, пора применить наши знания к реальной проблеме оптимизации. Наша проблема будет заключаться в функции верблюжьей спины на шестигорчатой спине:
Наша задача - найти минимум функции на границах: x1 между [-2, 2] и x2 находится между [-1, 1]. Для наглядности у нас есть график темпов доменов выше. Глобальный минимум происходит в двух местах:
Новые аргументы
Мы собираемся создать генетический алгоритм с множеством параметров, с которыми можно будет поиграть. Во-первых, он будет содержать обычные параметры, которые использовались в Кратком тривиальном примере задачи в последнем блоке:
- Вероятности кроссовера / мутации
- Границы значений переменных
- Фитнес-функция
- Процент границ для мутации
- Процент за элитарность
- Максимальное количество поколений
Кроме того, мы добавим несколько новых компонентов, а именно аргументы для метода выбора и для метода воспроизведения. В задаче «Краткий тривиальный пример» мы использовали только пропорциональный выбор с помощью колеса рулетки и усреднение для кроссовера. Однако теперь мы будем включать аргументы в пользу стиля «Колесо рулетки», «Случайность» или «Турнир» для выбора и аргументы в пользу усреднения или «интуитивного» кроссовера.
Некоторая помощь
До сих пор в этой серии статей мы говорили только о нахождении максимума функции приспособленности, а не минимума, так как же мы можем настроить наш алгоритм, чтобы найти правильный минимум? Решение, которое я считаю лучшим, - вместо того, чтобы менять порядок сортировки на противоположный, мы просто находим максимум, как обычно; однако мы масштабируем наши значения пригодности таким образом, что чем они меньше, тем больше они становятся, и чем они больше, тем меньше становятся. Мы бы сделали этот второй уровень масштабирования после первого, что сделает все значения пригодности положительными:
Как указывалось в предыдущем посте, поскольку некоторые из значений пригодности могут быть отрицательными, нам нужно сделать их все положительными, чтобы при вычислении суммы для деления каждого значения пригодности получилось пропорциональное распределение. Если мы максимизируем, мы не выполняем второй уровень масштабирования, но если да, то мы масштабируем, используя приведенное выше уравнение. Например, если масштабированные значения пригодности равны [4, 5, 1], то второй уровень масштабирования создает [0,2, 0,167, 0,5]. Как мы видим, наибольшее значение, 5, теперь становится наименьшим, 0,167, а наименьшее масштабированное значение, 1, становится наибольшим, 0,5. Таким образом, мы все еще можем найти максимум без особых изменений, кроме добавления второго уровня масштабирования.
Реализация
Поскольку мы собираемся иметь дело с множеством движущихся компонентов, я попытаюсь сделать нашу функцию «развития» чрезвычайно компактной, заменив каждый компонент вызовом функции.
Для начала у нас есть функции, которые масштабируют наши данные:
Далее у нас есть три метода выбора: колесо рулетки, случайный выбор и турнирный выбор. Мы уже видели выбор колеса рулетки раньше:
С другой стороны, случайный выбор просто выбирает случайные индексы от 0 до размера поколения:
Что касается выбора турниров, все будет немного иначе. Помните, что при отборе турниров мы случайным образом выбираем группу людей и выбираем лучших, кто выживет, поэтому нам нужен еще один параметр для определения размера турнира. Мы обсудим это позже. На данный момент мы просто выполняем цикл и на каждой итерации создаем случайную выборку конкурентов, в которой находим человека с максимальным значением пригодности и добавляем его к выбранным индексам.
Теперь, когда мы реализовали методы отбора, пришло время для метода воспроизведения. Этот метод принимает набор родителей, их значения приспособленности, вероятности мутации и кроссинговера, а также границы для мутации и метод воспроизводства. Если метод воспроизведения равен 1, мы будем использовать средний метод, иначе мы будем использовать «интуитивный» метод:
Теперь, когда мы определили наш метод воспроизводства, пора перейти к методам кроссовера и мутации. Во-первых, кроссовер. У нас есть два типа: усредняющий и «интуитивный». В отличие от предыдущего, нам нужно разрешить несколько измерений в нашем методе, чтобы обеспечить расширяемость. Итак, мы перебираем каждое значение переменной и выполняем технику кроссовера:
Теперь у нас есть «интуитивный» метод кроссовера. В этом методе мы создаем список случайных битов, где, если бит равен нулю, мы наследуем значение этой переменной от первого родителя, а если оно равно единице, мы наследуем эту переменную от второго родителя. В случае, когда есть только две переменные, существует 50% -ная вероятность того, что потомок может унаследовать оба значения переменных от одного и того же родителя, поэтому, чтобы обойти это, мы принудительно разделяем кроссовер между обоими родителями, если есть два измерения:
Теперь, когда мы НАКОНЕЦ реализовали все вспомогательные функции, пришло время создать алгоритм. Сейчас, к сожалению, этот алгоритм длинный, почти 100 строк компактного кода. Я не думаю, что могу все это здесь объяснить, но если вы действительно следили за этой серией и не заснули, я думаю, вы сможете сделать вывод, что происходит:
Хорошо, теперь, когда мы реализовали наш алгоритм, пора посмотреть, как он работает для нашей проблемы! Здесь у нас есть наша функция Six-Hump Camel-Back вместе с нашим начальным поколением и границами:
Теперь давайте назовем его с 25% кроссовером, 50% мутацией, 1% максимальным значением мутации границ, 10% элитностью, турнирным выбором (sel_method = 3), 10% размером турнира, методом воспроизведения «интуитивного» кроссовера (rep_method = 1) и выполнили 30 итераций:
Как мы видим, наш алгоритм практически сошелся к глобальному минимуму -1,0316.
Результаты различных гиперпараметров
Теперь мы собираемся запустить наш алгоритм с различными гиперпараметрами, вот 5 разных прогонов. Чтобы различать, каждый график имеет [s, r, e, t]: [#, #, #, #] в заголовке, индекс позиции s, используемый метод выбора, Индекс r представляет собой использованный метод воспроизведения, e представляет количество людей, перенесенных за элитарность, а индекс t представляет размер турнира (не означает ничего, если только s = 3). Все опыты были выполнены для 35 поколений, макс. Границы мутаций 1% и размер популяции 10. Здесь мы использовали 0,75% для скрещивания и мутации:
Теперь с 25% кроссовера и мутации:
Описание видео
Поскольку в этом посте было много сложных компонентов, я решил реализовать этот алгоритм для вас в видео, где я объясню его немного более подробно, вы можете проверить это здесь:
Оценка других функций тестирования производительности
Предыдущая задача оптимизации была относительно простой; однако мы можем оценить наш алгоритм, проверив более сложные задачи оптимизации. Мы рассмотрим еще две проблемы: Функция Эггхолдера, Функция Розенброка и Функция Экли. Чтобы сохранить одинаковые условия, мы будем запускать каждый алгоритм для 300 поколений с начальным размером 100 особей, 75% для мутации / кроссовера, 10% для элитарности, 1% границ для максимального значения мутации и случайного спаривания. Несмотря на то, что мы используем случайный выбор для спаривания, мы будем сочетать его с элитарностью, чтобы никогда не потерять лучшие решения от каждого поколения. Теперь, поскольку успех алгоритма в значительной степени зависит от начальных точек исходной популяции, наш алгоритм будет запускаться для каждой проблемы 30 раз, так что мы получаем широкий диапазон значений, сгенерированных из области, и минимум, найденный каждый раз. будет записан. Наконец, чтобы увидеть разницу между двумя методами кроссовера, мы запустим каждый алгоритм по 10 раз для каждого метода кроссовера.
Во-первых, функция Eggholder, вот функция ниже, глобальный min встречается только в одной точке: f (x) = - 959,6407 при X = (512, 404,2319):
Здесь представлены результаты наших 30 независимых пробных прогонов с использованием «интуитивно понятного» кроссовера. Чтобы прочитать результаты, представленные ниже, были собраны наилучшая и средняя пригодность последнего поколения для всех прогонов; затем были рассчитаны среднее значение и стандартное отклонение для каждого из этих прогонов, как мы видим ниже. Например, минимальная средняя пригодность для последнего поколения для любого бега составляла -889,967, где среднее значение средней пригодности для каждого бега составляло -814 со стандартным отклонением 103. Вы можете интерпретировать то же самое для наилучшей приспособленности. Мы видим, что из всех пробных запусков лучшее глобальное минимальное значение было -939, что на 20 значений отличается от глобального минимума. Это по-прежнему хороший результат, поскольку на графике видно много локальных экстремальных точек.
Теперь мы собираемся запустить алгоритм, используя метод кроссовера 1, метод усреднения.
С первого взгляда мы видим, что интуитивно понятный метод кроссовера имеет лучшее среднее значение и меньшее стандартное отклонение для лучшего значения пригодности для каждого прогона. Однако оба метода нашли одно и то же наилучшее минимальное значение.
Во-вторых, функция Розенброка, вот функция ниже, глобальное min встречается только в одной точке: f (x) = 0 в X = (1, 1):
Теперь запустим алгоритм, используя технику «интуитивного» кроссовера:
Теперь мы собираемся запустить алгоритм, используя технику усреднения кроссовера:
Из результатов мы видим, что метод усреднения кроссовера дал лучшие результаты по всем статистическим данным, лучшее среднее и наилучшее соответствие как для среднего, так и для минимального значений. Наилучшее значение пригодности для всех поколений составило 7,97e-8, что достаточно близко к фактическому глобальному минимальному значению 0.
В-третьих, функция Розенброка, вот функция ниже, глобальный min встречается только в одной точке: f (x) = 0 при X = (0, 0):
Теперь запустим алгоритм, используя технику «интуитивного» кроссовера:
Теперь мы собираемся запустить алгоритм, используя технику усреднения кроссовера:
Оценивая результаты, мы видим, что интуитивно понятный метод кроссовера нашел лучшее глобальное минимальное значение и лучшее среднее значение и стандартное отклонение для лучшего минимального значения для всех поколений. Наилучшее найденное минимальное значение было 0,000217, что близко к глобальному минимальному значению 0, но не к степени ответа предыдущей задачи.
В заключение этого раздела я надеюсь, что вы увидите, что ни один набор параметров не будет лучше остальных, это полностью зависит от проблемы. В результате приходится запускать алгоритм много раз с различными комбинациями гиперпараметров, чтобы «почувствовать» результаты. Как я уже говорил в предыдущих сообщениях, часто создают абстрактные и простые GA, которые фактически развивают гиперпараметры более продвинутых GA; однако это может быстро стать чрезвычайно затратным с точки зрения вычислений.
Заключение
Хорошо, на этом публикация завершена! Надеюсь, вы узнали много нового о генетических алгоритмах, решающих эту проблему. Главный вывод, который я хотел бы, чтобы вы заметили, заключается в том, что успех алгоритма строго зависит от гиперпараметров, которые вы ему указываете. Если функция приспособленности чрезвычайно сложна, обычно создают более простой генетический алгоритм для развития гиперпараметров сложного алгоритма на исходной функции. Это называется "настройкой" гиперпараметров. Если вы знакомы с автоматизированным машинным обучением, генетические алгоритмы - это распространенные инструменты, используемые для развития гиперметров моделей машинного обучения, особенно нейронных сетей. В конце этого раздела мы рассмотрим обучение нейронной сети для решения задачи анализа временных рядов. Следите за обновлениями, чтобы увидеть следующий пост, в котором мы расскажем о продвинутых концепциях генетических алгоритмов:
Следите за новостями: мы расскажем о некоторых сложных вопросах генетических алгоритмов! Вы можете найти весь код здесь, на моем GitHub:
