Введение
Решение прикладных задач параметрической оптимизации технических систем и теории оптимального управления динамическими системами, как правило, связано с применением численных методов оптимизации, в развитии которых можно выделить два ключевых подхода.
Первый подход связан с реализацией детерминированных и стохастических процедур поиска экстремума при наложении различных, иногда весьма существенных ограничений на свойства и структуру целевой функции. Основное преимущество такого подхода заключается в возможности математического обоснования сходимости алгоритма и в ряде случаев получения гарантий по скорости его сходимости. Однако данный подход предъявляет высокие требования к условиям постановки задачи, которые нередко трудно соблюсти в практических применениях, а проверка выполнения этих условий может быть крайне затруднена из-за их сложности. При этом применяются следующие методы и подходы: численные алгоритмы удовлетворения необходимых условий условного или безусловного экстремумов (Поляк, 1983; Bazaraa, Sherali, Shetty, 2006), методы штрафов (внешних штрафов, барьерных функций, комбинированный метод штрафов, метод множителей, метод точных штрафных функций) (Bazaraa, Sherali, Shetty, 2006), методы возможных направлений (Bazaraa, Sherali, Shetty, 2006), методы, использующие идеи моментов и адаптацию (Нестеров, 2010), методы на основе универсального градиентного спуска (Гасников, 2018), диагональные методы (Sergeyev, Kvasov, 2017), интервальные методы (Hansen, Walster, 2004), методы второго порядка и квазиньютоновские методы (Поляк, 1983; Bazaraa, Sherali, Shetty, 2006; Пантелеев, 2025). Достаточно полное единообразное описание методов оптимизации имеется в (Locatelli, 2021; Floudas, Pardalos, 2009).
Второй подход связан с применением метаэвристических методов оптимизации, которые объединяют в себе один или более эвристических методов, управляемых стратегией поиска более высокого уровня. Они способны покидать окрестности локальных экстремумов и выполнять достаточно полное исследование множества допустимых решений. Метаэвристические методы оптимизации позволяют находить решение высокого качества за разумное с практической точки зрения время. В отличие от традиционных методов оптимизации, метаэвристические методы могут применяться в ситуациях, когда практически полностью отсутствует информация о характере и свойствах исследуемой функции. Тем не менее, слабой стороной этой группы методов является, как правило, отсутствие формальных доказательств сходимости и гарантий, что найденное решение действительно близко к глобальному экстремуму. Классификация метаэвристических методов в настоящее время носит условный характер, поскольку характерные группы методов базируются на сходных идеях, и имеется устойчивая тенденция к созданию гибридных алгоритмов, объединяющих в себе сразу несколько хорошо зарекомендовавших себя алгоритмов. Кроме того, один и тот же алгоритм может принадлежать сразу к нескольким группам. Можно выделить следующие группы метаэвристических методов оптимизации: эволюционные методы (Gendreau, Potvin, 2019; Alorf, 2023; Tomar, Bansal, Singh, 2024; Пантелеев, Скавинская, 2023), методы «роевого» интеллекта (Del Ser et al., 2019; Niculina Dragoi, Dafinescu, 2021; Tzanetos, Fister, Dounias, 2020; Карпенко, 2021; Пантелеев, Скавинская, 2023), методы, имитирующие физические процессы (Floudas, Pardalos, 2009; Пантелеев, Скавинская, 2023), биоинспирированные методы (Yang, Chien, Ting, 2015; Карпенко, 2021; Пантелеев, Каранэ, 2024), мультиагентные методы (Пантелеев, Каранэ, 2024; Карпенко, 2021), мультистартовые методы (Floudas, Pardalos, 2009; Пантелеев, Скавинская, 2023).
Разнообразие методов оптимизации и постоянное появление новых алгоритмов и их модификаций объясняется хорошо известной теоремой No Free Lunch (NFL) (Wolpert, Macready, 1997). Эта теорема утверждает отсутствие универсального метода, способного эффективно решать все возможные задачи оптимизации. Поэтому выбор метода определяется конкретной задачей оптимизации: видом целевой функции и ограничений, задающих множество допустимых решений.
В статье предлагается новый метод оптимизации, который объединяет оба описанных подхода. Исследование области допустимых решений использует перелеты Леви (Gutowski, 2001) с целью борьбы с эффектом «застревания» в окрестностях локальных экстремумов. Этап разработки перспективных областей реализуется из прогнозируемой точки, определяемой конечной памятью алгоритма на двух последних шагах (Поляк, 1983; Нестеров, 2010; Гасников, 2018). Поиск из прогнозируемой точки реализует стратегию последовательного сокращения области поиска с ее неполным восстановлением после каждого из проходов (Luus, 2000). Новое положение решения определяется суммарным влиянием прогнозируемой точки и взвешенным влиянием результатов удачных шагов из нее. Процесс завершается после достижения заданного числа проходов. В качестве приближенного решения задачи выбирается наилучшее решение (решения) из полученных в результате реализованных проходов. Алгоритм относится к многошаговым (Поляк, 1983), так как использует концепцию конечной памяти о предыдущих положениях решения.
В работе рассматривается программная реализация многошагового адаптивного алгоритма оптимизации с прогнозированием (МААОП). Алгоритм сочетает последовательный поиск в окрестности прогнозируемой точки, адаптивное изменение величины шага, использование информации об успешных положениях решения и генерацию новых начальных приближений с помощью распределения Леви. Такой подход позволяет совмещать локальное уточнение решения с возможностью перехода к новым перспективным областям поиска.
Материалы и методы
Постановка задачи
Рассматривается задача поиска условного глобального минимума непрерывной целевой функции f(x) на множестве допустимых решений D, т.е. такой точки x* ∈ D, что
f(x*) = min f(x), x ∈ D
где x = (x₁, ..., xₙ)ᵀ, D = {x | xᵢ ∈ [aᵢ, bᵢ], i = 1, ..., n}.
Стратегия поиска решения
Метод использует идеи алгоритма Luus–Jaakola с последовательной редукцией и неполным восстановлением области исследования и ускоренного метода Нестерова, в котором антиградиент находится не в текущей точке, а в некоторой прогнозируемой точке в процессе поиска. Из начальной (текущей) точки совершается заданное число итераций, в результате которых реализуется проход. Начальная точка для следующего прохода получается при помощи распределения Леви с целью исследования еще неисследованных областей. Поиск завершается после окончания заданного числа проходов. В качестве приближенного решения задачи выбирается наилучшее решение (решения) из полученных в результате реализованных проходов. Согласно классификации алгоритм относится к многошаговым, так как использует концепцию конечной памяти о предыдущих положениях.
Алгоритм решения задачи
Шаг 1. Задать параметры метода:
- максимальное число попыток из текущей точки N;
- максимальное число проходов P;
- число итераций за время прохода K;
- наименьшая величина шага R;
- параметр уменьшения величины шага α (0 < α < 1);
- параметр восстановления величины шага η (0 < η << 1);
- величина шага, используемого при полетах Леви β;
- параметр распределения Леви λ (1 < λ ≤ 3).
Шаг 2. Задание начального приближения x⁽⁰⁾ ∈ D:
- а) используя равномерный закон распределения. Для этого с помощью равномерного распределения на единичном отрезке [0;1] генерировать n случайных точек Pᵢ⁰, i = 1, ..., n. Используя линейное преобразование, каждую точку отобразить на соответствующий ей промежуток [aᵢ, bᵢ]: xᵢ⁽⁰⁾ = (bᵢ - aᵢ)Pᵢ⁰ + aᵢ;
- б) положить xᵢ⁽⁰⁾ = (aᵢ + bᵢ) / 2, i = 1, ..., n.
Шаг 3. Положить p = 1 (счетчик числа проходов), множество Pool = ∅. Задать начальную величину шага t₀ = 1/2 * min(bᵢ - aᵢ), i = 1, ..., n.
Шаг 4. Положить k = 0 (счетчик числа итераций).
Шаг 5. Найти прогнозируемое решение:
z⁽ᵏ⁾ = x⁽ᵏ⁾ + 0.5 * (x⁽ᵏ⁾ - x⁽ᵏ⁻¹⁾) * rand[0,1]
где rand[0,1] — случайная величина, описываемая равномерным законом распределения на отрезке [0,1].
Если для какого-либо значения i не выполняется ограничение, т.е. zᵢ⁽ᵏ⁾ ∉ [aᵢ, bᵢ], то положить zᵢ⁽ᵏ⁾ = xᵢ⁽ᵏ⁾.
Шаг 6. Реализовать поиск в окрестности прогнозируемого решения.
Шаг 6.1. Положить s = 0 (число удачных попыток), j = 1 (число попыток из точки), J = ∅ (множество номеров удачных попыток из текущей точки).
Шаг 6.2. Генерировать случайный вектор ξʲ = (ξ₁ʲ, ..., ξₙʲ)ᵀ, где ξᵢʲ — случайная величина, равномерно распределенная на отрезке [-1, 1], которая получается из случайной величины ηᵢʲ, равномерно распределенной на [0,1], с использованием преобразования ξᵢʲ = 2ηᵢʲ - 1.
Шаг 6.3. Найти yʲ = z⁽ᵏ⁾ + tₖ * (ξʲ / ||ξʲ||), где ||ξʲ|| — евклидова норма вектора.
Шаг 6.4. Если yʲ ∈ D и f(yʲ) < f(z⁽ᵏ⁾), то шаг удачный, положить s = s + 1, номер j включить в множество J. Если yʲ ∉ D или f(yʲ) ≥ f(z⁽ᵏ⁾), то шаг неудачный.
Если j < N, то положить j = j + 1 и перейти к шагу 6.2.
Если j = N, то процедуру поиска с текущей величиной шага завершить.
Шаг 6.5. Если s = 0, проверить условие завершения прохода:
- если tₖ ≤ R, проход завершить, включить найденное решение в множество Pool и перейти к шагу 8;
- если tₖ > R, положить tₖ = α * tₖ и перейти к шагу 6.1.
Если s ≠ 0, то упорядочить решения yʲ, j ∈ J по неубыванию значения целевой функции: y⁽¹⁾, ..., y⁽ˢ⁾. Затем наилучшему удачному решению y⁽¹⁾ поставить в соответствие вес, равный 1, а наихудшему y⁽ˢ⁾, равный 1/s, т.е. всем удачным решениям сопоставить значения веса, уменьшающиеся по линейному закону wⱼ = (s + 1 - j) / s, j = 1, ..., s.
Шаг 6.6. Найти новое положение решения, используя средневзвешенную величину:
x⁽ᵏ⁺¹⁾ = z⁽ᵏ⁾ + [ Σ(wⱼ * (y⁽ʲ⁾ - z⁽ᵏ⁾)) ] / [ (s + 1) / 2 ]
Если x⁽ᵏ⁺¹⁾ ∉ D, то положить x⁽ᵏ⁺¹⁾ = y⁽¹⁾.
Шаг 7. Проверка завершения итераций в рамках текущего прохода.
Если k < K, то положить k = k + 1 и перейти к шагу 5.
Если k = K, то полученное решение включить в множество Pool и перейти к шагу 8.
Шаг 8. Проверка завершения числа проходов.
Если p < P, то положить p = p + 1 и перейти к шагу 9.
Если p = P, процесс поиска завершить. Из множества Pool выбрать решения x*, соответствующие наименьшему значению целевой функции f(x*).
Шаг 9. Реализация следующего прохода.
Найти новое начальное значение величины шага t₀ᵖ = η * 1/2 * min(bᵢ - aᵢ), i = 1, ..., n.
Генерировать новое положение начальной точки с помощью распределения Леви:
xᵢ⁽⁰⁾ = zᵢ⁽ᵏ⁾ + β * Levyᵢ(λ), i = 1, ..., n,
где для генерации величины Levyᵢ(λ) требуется:
- генерировать число Qᵢ с помощью равномерного закона распределения на отрезке [aᵢ - ε, bᵢ], ε = 10⁻⁷ — константа различимости;
- вычислить значения θᵢ = π * Qᵢ / 2 и Lᵢ = Qᵢ^(1/(1-λ));
- вычислить Levyᵢ(λ) = Lᵢ * sin(θᵢ), Levyᵢ(λ) = Lᵢ * cos(θᵢ), i = 1, ..., n.
Если xᵢ⁽⁰⁾ ∉ [aᵢ, bᵢ], процесс генерации следует повторить.
Перейти к шагу 4.
Замечания.
- На шаге 5 находится прогнозируемое решение с целью начала поиска из него, а не из текущего решения. При этом используется схема двухшагового быстрого градиентного метода [Поляк, 1983; Нестеров, 2010; Гасников, 2018]. Для учета информации о двух последних итерациях используется величина 0.5 * (x⁽ᵏ⁾ - x⁽ᵏ⁻¹⁾) с весовым коэффициентом, отличающимся от известного rₖ = 1/(k+1). Умножение этого слагаемого на rand[0,1] способствует активизации поиска (при этом детерминированный подход заменяется стохастическим).
- При поиске из прогнозируемой точки на шаге 6.3 реализуется метод случайного поиска с возвратом при неудачном шаге, дополненный процедурой сохранения в памяти удачных попыток из данной точки, которые ранжируются по величине целевой функции. На шаге 6.5 при нахождении новой величины шага фактически проводится редукция области поиска, как в методе (Luus, 2000).
- На шаге 6.6 авторами предложена формула для нахождения нового положения решения c использованием средневзвешенной величины удачных решений, найденных на шаге 6.5.
- На шаге 9 реализуется переход к следующему проходу. При этом для нахождения величины шага используется стратегия метода (Luus, 2000) с частичным восстановлением области поиска (с коэффициентом η).
Программное обеспечение
На основе изложенных алгоритмов разработан программный комплекс поиска глобального экстремума функций. Для его создания использовалась среда разработки Microsoft Visual Studio, язык программирования С# (Пантелеев, Каранэ, 2024).
Описанные в данном разделе методы соответствует задаче поиска минимума целевой функции. Так как заданные тестовые функции имеют глобальный максимум, при разработке программного обеспечения этого алгоритма был заменен знак перед целевыми функциями на противоположный.
Возможности программного комплекса позволяют изучить алгоритмы методов, а также влияние параметров каждого метода на результат его работы. В список выбираемых функций включены стандартные многоэкстремальные тестовые функции двух переменных, для которых известно точное решение (Пантелеев, Скавинская, 2023).
На рис. 1 представлено главное окно многошагового адаптивного алгоритма оптимизации с прогнозированием, где пользователь может выбрать вид целевой функции, задать множество допустимых решений и параметры метода, просматривать результаты работы.
алгоритма оптимизации с прогнозированием
Fig. 1. Main window of the multi-step adaptive optimization algorithm with prediction
Результаты
Пример 1. Найдем глобальной максимум функции Шаффера.
Зададим множество допустимых решений, x, y ∈ [-10, 10]. Выберем следующие параметры алгоритма: максимальное число попыток из текущей точки N = 100; максимальное число проходов P = 10; число итераций за время прохода K = 5; наименьшая величина шага R = 10⁻⁸; параметр уменьшения величины шага α = 0,95; параметр восстановления величины шага η = 0,89; величина шага, используемого при полетах Леви β = 0,4; параметр распределения Леви λ = 1,5.
На рис. 2 представлена популяция на начальной (k = 1), промежуточных (k = 40, 75) и конечной (k = 100) итерациях. Красным обозначено наилучшее решение в популяции на данной итерации.
Результаты работы алгоритма: наилучшее решение (x*, y*) = (0,006; -0,007); значение целевой функции f(x*, y*) = 0,999913; отклонение от точного решения ∆ = 8,7 * 10⁻⁵.
Fig. 2. Initial, intermediate, and final populations
Пример 2. Найдем глобальной максимум функции Розенброка.
Зададим множество допустимых решений, x, y ∈ [-2, 2]. Выберем следующие параметры алгоритма: максимальное число попыток из текущей точки N = 100; максимальное число проходов P = 20; число итераций за время прохода K = 5; наименьшая величина шага R = 10⁻⁸; параметр уменьшения величины шага α = 0,9; параметр восстановления величины шага η = 0,89; величина шага, используемого при полетах Леви β = 0,4; параметр распределения Леви λ = 1,5.
На рис. 3 представлена популяция на начальной (k = 1), промежуточных (k = 15, 25) и конечной (k = 40) итерациях. Красным обозначено наилучшее решение в популяции на данной итерации.
Результаты работы алгоритма: наилучшее решение (x*, y*) = (-1,006; -1,013); значение целевой функции f(x*, y*) = -4,3 * 10⁻⁵; отклонение от точного решения ∆ = 4,3 * 10⁻⁵.
Fig. 3. Initial, intermediate, and final populations
Пример 3. Оптимизация конструкции зубчатой передачи (Сандгрен, 1988).
Рассматривается редуктор, включающий четыре шестерни для уменьшения угловой скорости ведомого вала. Все шестерни могут иметь от 12 до 60 зубьев. Цель — минимизация стоимости конструкции. Переменными являются x₁ = Td — число зубьев ведущей шестерни, x₂ = Tb, x₃ = Ta — числа зубьев промежуточных шестерен, x₄ = Tf — число зубьев ведомой шестерни. В результате получается конструкция с передаточным отношением TR.
TR = (Td * Tb) / (Ta * Tf)
Постановка задачи оптимизации:
min f(x) = (1/6.931 - (x₁ * x₂) / (x₃ * x₄))², x ∈ D
D = [12; 60] × [12; 60] × [12; 60] × [12; 60], где ⌊·⌋ — целая часть числа.
Результат решения с параметрами N = 100, P = 80, K = 30, R = 10⁻⁸, α = 0,7; η = 0,89; β = 12; λ = 1,5: x*(T) = [6; 19; 43; 9], f(x*) = 2,7001 × 10⁻¹². Сравнение с результатами других методов показано в таблице 1.
Таблица 1 / Table 1
Сравнение результатов работы алгоритма МААОП с другими методами / Comparison of the results of the new algorithm with other methods
| Method | Best Solution [x1, x2, x3, x4] | f(x*) |
|---|---|---|
| (Sandgren, 1988) | [18, 22, 45, 60] | 0.146667 |
| (Kannan, Kramer, 1994) | [13, 15, 33, 41] | 0.144124 |
| (Deb, Goyal, 1996) | [19, 16, 49, 43] | 0.144281 |
| (Gandomi et al., 2013) | [19, 16, 43, 49] | 0.144281 |
| (Garg, 2019) | [19, 16, 43, 49] | 0.14428096 |
| (Nekoo et al., 2022) | [16, 19, 43, 49] | 0.14428096 |
| МААОП | [16, 19, 43, 49] | 0.14428096 |
Примечание: В оригинальной таблице значения f(x) представлены как отклонения или сами значения функции, в тексте указано 2.7001 × 10⁻¹² для МААОП, что соответствует высокой точности.
Анализ эффективности метода
Исследуемые методы применялись к некоторым функциям из набора тестовых функций. Для каждой функции проводилась серия из 100 решений одной и той же задачи с одними и теми же значениями параметров. Для полученной выборки {f₁, f₂, ..., f₁₀₀} вычислялись среднее значение отклонения полученного решения от точного ∆f_avg = (1/100) * Σ∆fᵢ, где ∆fᵢ = |f(xᵢ) - f(x*)|; наименьшее значение отклонения ∆f_best = min ∆fᵢ; среднеквадратичное отклонение σf; количество успехов n_усп (успехом считалось попадание лучшей точки в ε-окрестность точного решения, ε = max(bᵢ - aᵢ) / 1000).
Результаты, полученные для каждой функции, представлены в табл. 2—4.
Таблица 2 / Table 2
Анализ выбора параметров метода. Корневая функция / Analysis of method parameter selection. Root function
| N | P | K | R | α | η | β | λ | ∆f_avg | ∆f_best | σf | n_усп |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 40 | 10 | 15 | 10⁻⁸ | 0,8 | 0,5 | 0,3 | 2 | 0,000177 | 0,000000 | 0,000227 | 100 |
| 30 | 10 | 15 | 10⁻⁸ | 0,8 | 0,5 | 0,3 | 2 | 0,000227 | 0,000002 | 0,000284 | 100 |
| 50 | 10 | 15 | 10⁻⁸ | 0,8 | 0,5 | 0,3 | 2 | 0,000182 | 0,000005 | 0,000208 | 100 |
| 40 | 20 | 15 | 10⁻⁸ | 0,8 | 0,5 | 0,3 | 2 | 0,000152 | 0,000002 | 0,000227 | 100 |
| 40 | 30 | 15 | 10⁻⁸ | 0,8 | 0,5 | 0,3 | 2 | 0,000142 | 0,000001 | 0,000168 | 100 |
| 40 | 30 | 25 | 10⁻⁸ | 0,8 | 0,5 | 0,3 | 2 | 0,000005 | 0,000000 | 0,000005 | 100 |
| 40 | 20 | 15 | 10⁻⁹ | 0,8 | 0,5 | 0,3 | 2 | 0,000146 | 0,000003 | 0,000174 | 100 |
| 40 | 20 | 15 | 10⁻⁸ | 0,5 | 0,5 | 0,3 | 2 | 0,000001 | 0,000000 | 0,000003 | 100 |
| 40 | 20 | 15 | 10⁻⁸ | 0,5 | 0,9 | 0,3 | 2 | 0,000000 | 0,000000 | 0,000000 | 100 |
| 40 | 20 | 15 | 10⁻⁸ | 0,5 | 0,9 | 0,9 | 2 | 0,000009 | 0,000000 | 0,000016 | 100 |
Таблица 3 / Table 3
Анализ выбора параметров метода. Мульти-функция / Analysis of method parameter selection. Multifunction
| N | P | K | R | α | η | β | λ | ∆f_avg | ∆f_best | σf | n_усп |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 40 | 10 | 20 | 10⁻⁶ | 0,89 | 0,89 | 0,3 | 1,5 | 0,800518 | 0,000000 | 0,888984 | 20 |
| 40 | 20 | 20 | 10⁻⁶ | 0,89 | 0,89 | 0,3 | 1,5 | 0,265937 | 0,000000 | 0,420819 | 32 |
| 40 | 20 | 30 | 10⁻⁶ | 0,89 | 0,89 | 0,3 | 1,5 | 0,090201 | 0,000000 | 0,227720 | 41 |
| 40 | 30 | 30 | 10⁻⁶ | 0,89 | 0,89 | 0,3 | 1,5 | 0,116452 | 0,000000 | 0,329003 | 41 |
| 40 | 30 | 30 | 10⁻⁸ | 0,89 | 0,89 | 0,3 | 1,5 | 0,171381 | 0,000000 | 0,374197 | 47 |
| 40 | 30 | 30 | 10⁻⁸ | 0,5 | 0,89 | 0,3 | 1,5 | 0,074884 | 0,000000 | 0,191694 | 47 |
| 40 | 30 | 30 | 10⁻⁸ | 0,5 | 0,6 | 0,3 | 1,5 | 0,415003 | 0,000000 | 0,457901 | 23 |
| 40 | 30 | 30 | 10⁻⁸ | 0,5 | 0,99 | 0,3 | 1,5 | 0,064881 | 0,000000 | 0,182047 | 52 |
| 40 | 30 | 30 | 10⁻⁸ | 0,5 | 0,99 | 0,9 | 1,5 | 0,019978 | 0,000000 | 0,097809 | 45 |
| 40 | 30 | 30 | 10⁻⁸ | 0,5 | 0,99 | 0,9 | 2,9 | 0,033619 | 0,000000 | 0,123121 | 47 |
Таблица 4 / Table 4
Анализ выбора параметров метода. Функция Розенброка / Analysis of method parameter selection. Rosenbrock function
| N | P | K | R | α | η | β | λ | ∆f_avg | ∆f_best | σf | n_усп |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 40 | 5 | 10 | 10⁻⁶ | 0,89 | 0,89 | 0,3 | 1,5 | 0,061874 | 0,000000 | 0,351095 | 32 |
| 40 | 10 | 10 | 10⁻⁶ | 0,89 | 0,89 | 0,3 | 1,5 | 0,000023 | 0,000000 | 0,000083 | 70 |
| 40 | 5 | 20 | 10⁻⁶ | 0,89 | 0,89 | 0,3 | 1,5 | 0,011783 | 0,000000 | 0,101855 | 78 |
| 40 | 10 | 20 | 10⁻⁶ | 0,2 | 0,89 | 0,3 | 1,5 | 0,000138 | 0,000000 | 0,000468 | 48 |
| 40 | 10 | 20 | 10⁻⁶ | 0,5 | 0,89 | 0,3 | 1,5 | 0,000007 | 0,000000 | 0,000016 | 74 |
| 40 | 10 | 20 | 10⁻⁶ | 0,99 | 0,89 | 0,3 | 1,5 | 0,009835 | 0,000000 | 0,031232 | 16 |
| 40 | 10 | 20 | 10⁻⁶ | 0,5 | 0,5 | 0,3 | 1,5 | 0,000002 | 0,000000 | 0,000008 | 96 |
| 40 | 10 | 20 | 10⁻⁶ | 0,5 | 0,2 | 0,3 | 1,5 | 0,000436 | 0,000000 | 0,002041 | 46 |
| 40 | 10 | 20 | 10⁻⁶ | 0,5 | 0,5 | 0,9 | 1,5 | 0,000011 | 0,000000 | 0,000029 | 67 |
| 40 | 10 | 20 | 10⁻⁶ | 0,5 | 0,5 | 0,9 | 0,5 | 0,000025 | 0,000000 | 0,000143 | 78 |
Анализ работы метода показал, что с большинством тестовых функций метод справляется успешно. В серии из 100 запусков удается найти глобальный максимум функций с достаточно высокой точностью или вообще точное решение. Метод показал, что увеличение значений N, P и K обычно повышает надёжность метода, но одновременно увеличивает вычислительные затраты.
Рекомендации по выбору параметров
- Максимальное количество попыток N определяет число попыток из точки. Чем больше параметр размера количества попыток, тем лучше полученный результат, но в силу возрастающих вычислительных затрат замедляется алгоритм. Рекомендуемое значение N ≥ 40.
- Максимальное число проходов P определяет, сколько раз алгоритм может повторно запускать процедуру поиска с новым начальным приближением. Увеличение P повышает вероятность нахождения более точного решения, поскольку алгоритм получает больше возможностей уточнить результат и выйти из неудачной области поиска. При малом значении P процесс может завершиться преждевременно, особенно для многоэкстремальных функций. Рекомендуемое значение P ≥ 10.
- Число итераций за время прохода K задает глубину локального поиска в рамках одного прохода. При увеличении K повышается точность найденного решения, но возрастает время работы алгоритма. Анализ результатов показал, что при слишком малом значении K алгоритм не всегда успевает приблизиться к искомой точке глобального экстремума. Рекомендуемое значение K ≥ 15.
- Наименьшая величина шага R используется как критерий завершения прохода. Чем меньше значение R, тем более точным может быть найденное решение. Слишком малое значение параметра увеличивает число вычислений и может привести к избыточному уточнению. Рекомендуемое значение R ∈ [10⁻⁹, 10⁻⁶].
- Параметр уменьшения величины шага α определяет скорость уменьшения шага при неудачном поиске. При больших значениях α шаг уменьшается медленно, что позволяет дольше исследовать область, но может замедлить сходимость. Рекомендуемое значение 0 < α < 1.
- Параметр восстановления величины шага η задает увеличение шага после успешного поиска. Данный параметр позволяет алгоритму адаптивно изменять шаг и продолжать движение в перспективном направлении. При слишком малом значении η шаг восстанавливается недостаточно быстро, а при слишком большом возможны резкие переходы по области поиска. Рекомендуемое значение 0 < η << 1.
- Величина шага, используемого при полетах Леви β. Подбирается в зависимости от особенностей решаемой задачи оптимизации: размеров множества допустимых решений, свойств целевой функции.
- Параметр распределения Леви λ. Рекомендуемое значение 1 < λ ≤ 3.
Обсуждение результатов
Полученные результаты показывают, что разработанное программное обеспечение позволяет наглядно исследовать работу многошагового адаптивного алгоритма оптимизации с прогнозированием. На тестовых функциях алгоритм находил решения, близкие к известным значениям глобального экстремума, что подтверждает корректность его программной реализации.
По сравнению с классическими градиентными методами рассматриваемый алгоритм не требует вычисления производных целевой функции, поэтому может применяться к задачам со сложным рельефом поверхностей уровня. В отличии от других алгоритмов он использует информацию об успешных положениях решения, что делает процесс поиска более направленным.
В сравнении с эволюционными и методами «роевого интеллекта» предложенный алгоритм имеет более простую структуру, так как не требует операторов скрещивания, мутации или моделирования взаимодействия частиц. При этом использование распределения Леви позволяет выполнять переходы к новым областям поиска и снижать вероятность преждевременного попадания в локальный экстремум.
Анализ экспериментов показал, что параметры алгоритма существенно влияют на качество результата. Увеличение значений N, P и K повышает вероятность нахождения точного решения, однако увеличивает время вычислений. Выбор величин параметров α, η, β и λ позволяет регулировать баланс между локальным уточнением решения и исследованием новых областей множества допустимых решений.
Таким образом, результаты подтверждают выдвинутую гипотезу о том, что сочетание прогнозирования, памяти об успешных шагах, адаптивного изменения шага и применение распределения Леви повышает устойчивость алгоритма при решении задач глобальной оптимизации.
Заключение
В работе создано программное обеспечение для реализации многошагового адаптивного алгоритма оптимизации с прогнозированием. Программа позволяет задавать целевую функцию, область допустимых решений и параметры алгоритма, выполнять численный эксперимент и визуализировать процесс поиска решения.
Проведенные эксперименты на тестовых функциях показали, что реализованный алгоритм способен находить решения, близкие к точным значениям глобального экстремума. Использование прогнозирования, памяти об успешных положениях, адаптивного изменения шага и распределения Леви позволяет сочетать локальное уточнение решения с исследованием новых областей множества допустимых решений.
Полученные результаты подтверждают работоспособность разработанного программного комплекса и возможность его применения для анализа поведения алгоритма, подбора параметров и решения задач глобальной оптимизации. Перспективой дальнейших исследований является расширение набора тестовых функций, сравнение с другими метаэвристическими методами и применение программы в прикладных задачах оптимизации сложных технических систем.
Ограничения.
Ограничением исследования является то, что проверка программного обеспечения выполнялась на ограниченном наборе тестовых функций с известными значениями экстремума. Это позволяет оценить корректность реализации алгоритма, однако не полностью отражает сложность реальных прикладных задач. Кроме того, качество работы метода зависит от выбора параметров алгоритма, поэтому при их неудачном задании возможно увеличение времени вычислений или снижение точности результата. Как и другие метаэвристические методы, предложенный алгоритм не гарантирует нахождения глобального экстремума за конечное число итераций для произвольной целевой функции. В дальнейшем исследование может быть расширено за счет более подробного сравнения с другими методами оптимизации и применения программы в прикладных задачах поиска оптимальных законов управления динамическими системами (Пантелеев, Бортаковский, 2016).
Limitations.
A limitation of this study is that the software was tested on a set of test functions with known extremes values. While this allows to study the algorithm’s correct implementation, it does not fully reflect the complexity of real-world application problems. Furthermore, the performance of the method depends on the choice of algorithm parameters; therefore, if they are set incorrectly, this may lead to increased computation time or reduced accuracy of the result. Like other metaheuristic methods, the proposed algorithm does not guarantee finding the global extremum for an arbitrary objective function within a finite number of iterations. Future research could be expanded through a more detailed comparison with other optimization methods and the application of the software to real-world problems (Panteleev, Bortakovskii, 2016).