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

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

Оптимизация дисперсионных мух

Неотъемлемым источником вдохновения для решения задач оптимизации и поиска является природа. Оптимизация дисперсионных мух, или сокращенно DFO, основана на поведении мух, роящихся над источниками пищи.

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

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

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

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

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

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

Заткнись и покажи мне код

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

А что насчет чего-то посложнее?

Очевидно, что это довольно простая игрушечная задача, а что насчет чего-то более сложного?

Я подумал, что вместо использования обучения с подкреплением интересным способом применения DFO будет оптимизация обучаемых весов нейронной сети для решения задачи с тележкой. Задача тележки - это стандартная задача по обучению с подкреплением, а библиотека тренажерного зала OpenAI предоставляет среду тележки Python, с которой наша нейронная сеть может взаимодействовать. Проблема описана на их сайте:

Шест прикреплен к тележке, которая движется по бесконтактной дорожке, с помощью незадействованного шарнира. Система управляется приложением к тележке силы +1 или -1. Маятник запускается вертикально, и цель состоит в том, чтобы не допустить его падения. Награда +1 предоставляется за каждый временной шаг, на протяжении которого шест остается в вертикальном положении. Эпизод заканчивается, когда штанга отклоняется от вертикали более чем на 15 градусов или тележка перемещается более чем на 2,4 единицы от центра.

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

Так что это за изменения?

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

  • Метод обновления (всего семь.)
  • Элитарность мух.
  • Затухающий порог возмущения.
  • Многопоточные вычисления для более быстрой оценки пригодности.
  • Вечный бог летать.

Обновление

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

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

Другой метод обновления получил название гибридного режима.

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

Следующим шагом по сравнению с гибридным режимом стал режим n_fittest.

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

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

Элитарность

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

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

Выше мы можем видеть два прогона программы, один с элитарностью, установленной на 20, и один с установленным на 0. Для обоих прогонов режим был установлен на исходный метод обновления DFO, а размер популяции составлял 1000, а порог нарушения был установлен на 0,1 - что очень много!

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

Распад порога возмущения

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

Многопоточность

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

Вечный бог летать

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

Мысли о производительности DFO для обновлений нейронного веса

У DFO было заметное снижение производительности, когда размерность стала очень большой. Например, попытка оптимизации в сети с 256 нейронами в каждом слое практически невозможно решить за разумное время. Возможно, если бы он мог работать на графическом процессоре с таким же количеством времени, отведенным для алгоритма, такого как обратное распространение или градиенты политики с воспроизведением опыта, то это было бы честное соревнование. Однако, согласно прилагаемому видео, после достаточной настройки DFO в конечном итоге удалось получить работающую сеть, которая решила проблему!

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

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

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

Заключительные замечания

Я хотел бы закончить этой замечательной цитатой героев искусственного интеллекта Стюарта Рассела и Питера Норвига:

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

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

Спасибо за чтение!