Развивающиеся решения с помощью генетических алгоритмов

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

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

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

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

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

Генетический алгоритм был изобретен Джоном Холландом в 1970-х годах и, конечно же, в общих чертах основан на теориях эволюции.

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

Именно этот процесс естественного отбора приводит к отличным характеристикам птиц и приводит к успешным кандидатам для решения наших задач оптимизации. Но как получить и отобрать этих кандидатов?

Выбор

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

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

Кроссовер

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

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

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

Мутация

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

Это гарантирует, что поиск будет продолжать расти и пробовать новые типы решений.

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

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

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

Игрушечная проблема

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

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

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

Оптимизация Растригина

Взяв все, что мы видели до сих пор, мы можем оптимизировать и анимировать все, используя matplotlib, как показано на гифке ниже. Мы начинаем за высоким холмом, но GA все еще проходит его и спускается к глобальным оптимумам.

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

Заключение

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

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

Ссылки и ссылки

Это сообщение в блоге не было бы создано без этих ссылок: