Использование распределённой сети при решении задач оптимизации с помощью эволюционных алгоритмов

Актуальность

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

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

Цель

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

Задачи

1.      Реализовать стандартный генетический алгоритм на языке Python.

2.      Составить тестовые задачи для имитации сложной целевой функции.

3.      Получить результаты работы стандартного алгоритма на тестовой функции и проанализировать их.

4.      Предложить модификацию генетического алгоритма для выполнения вычислений в распределённой сети.

5.      Получить результаты работы модифицированного алгоритма на тестовой функции и провести их анализ.

6.      Сравнить полученные данные и сделать вывод об эффективности модификации.

Оснащение и оборудование, использованное при создании работы

• Компьютер

Описание

Для реализации генетического алгоритма был выбран язык Python.

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

Работа автора делилась на семь этапов.

Первый этап

Задавались значения длины каждого индивида n, размера популяции m, режима работы мутации и количество итераций t. Затем генерировалась первая популяция (матрица n*m).

Второй этап

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

Третий этап

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

Четвёртый этап

Из популяции случайно отбирали 4 индивида, из них – два таких, чьё значение целевой функции было наиболее близко к оптимальному, затем два полученных сохранялись в массив для следующей популяции. Эта операция проводилась, пока не набиралось t пар индивидов.

Пятый этап

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

Шестой этап

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

У мутации есть несколько режимов работы, которые отличаются вероятностью смены гена:

WEAK: 1/(3*n)

MEDIUM: 1/n

STRONG: 3/n

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

Седьмой этап

Если алгоритм прошёл все итерации t, то он сохранил лучшее решение и вывел графики.

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

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

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

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

Результаты работы/выводы

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