Пащенко Д.А. – СРАВНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА И АЛГОРИТМА ОПТИМИЗАЦИИ РОЯ ЧАСТИЦ НА ПРИМЕРЕ ОДНОЙ ЗАДАЧИ СТРУКТУРНОЙ ОПТИМИЗАЦИИ

СРАВНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА И АЛГОРИТМА ОПТИМИЗАЦИИ РОЯ ЧАСТИЦ НА ПРИМЕРЕ ОДНОЙ ЗАДАЧИ СТРУКТУРНОЙ ОПТИМИЗАЦИИ

Донецкий национальный технический университет, г. Донецк

кафедра искусственного интеллекта и системного анализа

Пащенко Д.А. Сравнение генетического алгоритма и алгоритма оптимизации роя частиц на примере одной задачи структурной оптимизации. Данная работа посвящена сравнительному исследованию двух методов оптимизации на основании результатов решения задачи минимизации массы алюминиевой фермы. Результаты исследования показывают, что Генетические алгоритмы, как правило, лучше, чем Оптимизация Роя Частиц по всем показателям эффективности.

Ключевые слова: структурная оптимизация, генетический алгоритм, оптимизация роя частиц.

Pashchenko D.A. Comparison of the genetic algorithm and particle swarm optimization algorithm using an example of a structural optimization problem. This work is devoted to a comparative study of two optimization methods based on the results of solving the problem of minimizing the mass of an aluminum truss. The results show that the Genetic Algorithms are generally better than the Particle Swarm Optimization with regard to all performance indicators.

Keywords: structural optimization, genetic algorithm, particle swarm optimization.

Введение. Эвристическая оптимизация не новая концепция. Первый генетический алгоритм (ГА) был разработан в 1975 году [1], в то время как оптимизация роя частиц (ОРЧ) впервые была предложена в 1995 году [2], но они оба считаются современными методами. Данные методы обычно используются для нелинейных задач с большими и сложными проектными пространствами или с прерывистыми целевыми функциями, задачами, которые очень трудно или невозможно решить с помощью классических методов.

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

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

Стоит упомянуть, что в некоторых исследованиях изучается возможность комбинировать ГА и ОРЧ в одном алгоритме и таким образом использовать преимущества, как эволюционных аспектов ГА, так и возможностей обмена данными между индивидуумами, специфичных для ОРЧ [3]. Как сообщают авторы, этот комплексный подход может привести к более эффективным методам.

Методология. Как в ГА, так и в ОРЧ группа решений генерируется случайным образом в качестве отправной точки алгоритма. Каждое решение в группе (называемое популяцией) является индивидуальным и представлено рядом значений: параметров задачи.

ГА развивает популяцию в течение нескольких поколений, используя специфические генетические операторы. Наиболее важным оператором является мутация, которая позволяет исследовать пространство в поисках более подходящих индивидуумов. Мутация в основном производит случайные или псевдослучайные изменения индивидуумов. Ее можно реализовать несколькими способами. В данной работе будем использовать следующее уравнение:

В приведенном уравнении (1) k это k–й ген хромосомы, n длина хромосомы (количество генов), x_k^(t+1) значение k–го гена в хромосоме при генерации t + 1, x_k^(t) значение k–го гена в хромосоме при генерации t, s признак операции (выбирается случайным образом, но настраивается в зависимости от направления мутации), f(u,p) функция случайного числа u и параметра мутации p, R диапазон мутации (зависит от текущего значения гена и его границ).

В ОРЧ каждое решение представлено индивидуумом в движущейся группе. Группа перемещается в пространстве проектирования, увеличивая количество итераций, причем на каждой итерации (i) позиция каждого индивидуума (p_i) обновляется с учетом его текущей скорости (v_i), наилучшей предыдущей позиции (pO_i) и глобальной наилучшей позиции группы (gO_i). Положение внутри пространства проектирования представляет собой решение, оптимальность которого оценивается с помощью целевой функции:

В уравнении (2) коэффициенты r_p и r_g случайные числа в интервале (0,1). Влияние каждой составляющей скорости определяется параметрами ω (коэффициент инерции), φ_p (когнитивная компонента, определяющая характеристики частицы относительно ее предыстории), φ_g (социальная компонента, характеризующая частицу относительно своих соседей). Их выбор имеет решающее значение для эффективности алгоритма.

Сравнительное исследование было выполнено для популярной задачи структурной оптимизации [4]. Она заключается в минимизации массы алюминиевой фермы, изображенной на рис. 1, в условиях ограничения предельного напряжения (130 МПа) и деформации (50,8 мм).

Рисунок 1 – Контрольная задача структурной оптимизации

В процессе тестирования ГА наиболее оптимальный размер популяции составил 50, а максимальное количество итераций 51 (включая начальную, сгенерированную случайным образом).

Для ГА были использованы 3 различных оператора мутации: индивидуальная вероятность мутации (ИВ), вероятность генной мутации (ГВ), конечное значение параметра каждого типа (КЗП). 12 пар ИВ и ГВ были протестированы на трех типах мутации (равномерная, полиномиальная, Гаусс), как показано в таблице 1. Ячейки, отмеченные «х», представляют рассматриваемые пары. Чтобы уменьшить общую вычислительную нагрузку, явно невыгодные пары были исключены (пары, приводящие к слишком низкой или слишком высокой вероятности мутации). Вероятности в таблице следует считать в процентах: например, 0.2 означает 20%, а 1 означает 100%.

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

Взяв комбинацию между каждым из вышеперечисленных параметров и значений, получилось всего 144 конфигурации: (3 типа мутации) x (12 пар ИВ–ГВ) x (4 значения для КЗП).

Для ОРЧ рассмотренный размер популяции также составляет 50 и максимальное количество итераций 51.

Как указано выше, значения трех параметров ОРЧ имеют решающее значение для успеха алгоритма. Для изучения всех возможных вариантов, для параметров ОРЧ были выбраны значения, указанные в таблице 3.

Были рассмотрены все комбинации параметров, что позволило получить в общей сложности 80 (5x4x4) конфигураций.

Принимая во внимание, что как ГА, так и ОРЧ являются стохастическими методами, каждая конфигурация была выполнена 50 раз, чтобы компенсировать присущую случайность методов.

Результаты. Производительность алгоритмов оценивалась по трем критериям:

После сортировки результатов для сравнения были рассмотрены только 9 лучших конфигураций. На рисунках 2–4 представлены графики производительности для этих 9 лучших конфигураций каждого из алгоритмов.

Рисунок 2 – Средние оценки всех симуляций для лучших 9 конфигураций ГА и ОРЧ (надежность)

Рисунок 3 – Средние оценки лучших 20% симуляций для лучших 9 конфигураций ГА и ОРЧ (точность)

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

Рисунок 4 – Общее время выполнения для лучших 9 конфигураций ГА и ОРЧ

Заключение. Графики, представленные на рис. 2 и рис. 3, показывают, что по надежности и точности все 3 реализации ГА превосходят ОРЧ во всех лучших конфигурациях. Разница очевидна, особенно в случае надежности, наиболее важного показателя эффективности для ситуаций, когда процедура оптимизации не может быть запущена несколько раз из–за высоких вычислительных нагрузок, необходимых для оценки функции пригодности. Это часто имеет место в структурной оптимизации, где пригодность вычисляется с использованием моделирования методом конечных элементов.

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

Сравнивая также время выполнения, которое показывает, что PSO в два раза медленнее, чем GA, можно сделать вывод, что генетические алгоритмы превосходят оптимизацию роя частиц для задач структурной оптимизации, по крайней мере, в том, что касается ферменных конструкций. Также следует отметить, что все 3 оператора мутации имеют схожие характеристики, все они неизменно лучше, чем PSO.