От симплекса к рабочей формуле: адаптация метода деформированного многогранника под задачи синтеза механизмов

Авторы: Котов А.В.

Чтобы уверенно применить оптимизационный алгоритм и правильно интерпретировать результат, нужно хорошо понимать, как он работает внутри. Но подробных, «человеческих» разборов большинства методов в литературе не так много — обычно приходится собирать информацию по крупицам из многих источников. Я решил исправить это для метода деформируемого многогранника (Нелдера — Мида). Недавно я разобрал его «по винтикам», реализовал в PTC MathCAD и использовал в своих задачах. Делюсь результатами — возможно, это сэкономит вам несколько вечеров.

Оптимизационные методы синтеза рычажных механизмов получили развитие в конце 60-х годов двадцатого столетия в связи с широким внедрением в науку и практику ЭВМ, а также методов машинной оптимизации. Метод деформированного многогранника, предложенный в работе [1], предназначен для поиска локального минимума функции нескольких переменных при помощи эвристического алгоритма численной оптимизации и не требует вычисления производных целевой функции. Причем в отличие от многих других эвристических методов, которые работают с точками в пространстве решений, указанный метод работает с симплексом – геометрической фигурой, каждая вершина которой соответствует некоторому вектору набора оптимизируемых параметров.

Процесс оптимизации заключается в том, чтобы путем проведения последовательных итераций изменять и перемещать симплекс в пространстве параметров (см. рис. 1), стремясь приблизить его вершины к глобальному оптимуму. Метод деформируемого многогранника оказался легко реализуемым алгоритмом на ЭВМ, показал свою высокую эффективность при относительной простоте и стал своего рода эталоном в категории нелинейного программирования [2, 3].

a                                b                                c                                d
Рис. 1. Преобразования симплекса в двумерном пространстве:
a – отражение; b – растяжение; c – сжатие; d – редукция

Процедуру поиска минимума целевой функции методом деформируемого многогранника ведется путем выполнения последовательных итераций, на каждой из которых выполняются следующие шаги [4, 5].

1. Формирование исходного симплекса.

2. Оценка функции. Устанавливаются координаты вершин симплекса и вычисляются значения целевой функции в каждой из вершин многогранника.

3. Сортировка вершин. Вершины упорядочиваются по возрастанию значения целевой функции. Вершина с наихудшим значением целевой функции называется худшей вершиной Xh, вершина с наилучшим значением – лучшей вершиной Xl, а вершина со вторым худшим значением – предпоследней вершиной Xg.

4. Определение центра тяжести вершин. Для всех вершин симплекса, за исключением худшей вершины, рассчитывается точка общего центр тяжести Xс (см. рис. 1):

5. Отражение. Через худшую вершину Xh и центр тяжести остальных вершин Xc проводится проецирующая прямая, на которой строится новая вершина Xr отражением старой. Если значение целевой функции в отраженной точке меньше, чем в предпоследней вершине Xg, то худшая вершина заменяется отраженной, а из оставшихся вершин строится новый деформируемый многогранник, т.е. отражение заменяет оригинал (см. рис. 1, а):

где α – коэффициент отражения. Если значение данного коэффициента много больше единицы, то деформируемый многогранник хуже адаптируется к топологии задачи, а в области локального минимума увеличение размеров многогранника замедлит сходимость. Если значение коэффициента меньше единицы, то требуется большее число вычислений целевой функции. В результате для обеспечения удовлетворительного поиска параметров при оптимизации традиционно рекомендуется α=1 [1], что позволяет поддерживать форму и размер деформируемого многогранника постоянной, пока изменения в топологии задачи не потребуют применения многогранника другой формы.

6. Расширение. Если значение целевой функции в отраженной точке Xr значительно лучше, чем в лучшей вершине Xl, то выполняется операция расширения, при которой отраженная точка Xr еще дальше перемещается от центра тяжести в том же направлении, что может помочь найти новый локальный минимум целевой функции (см. рис. 1, b):

где γ – коэффициент расширения. Если данный коэффициент выбран слишком большим, это может привести к распространению симплекса на большую область пространства параметров, что может замедлить сходимость или привести к потере информации о локальных экстремумах. Если он выбран слишком маленьким, это может привести к недостаточному исследованию новых областей пространства параметров. В результате для обеспечения удовлетворительного поиска параметров при оптимизации традиционно рекомендуется γ=2,0 [1] или следующий диапазон изменения 2,8<γ<3,0 [4].

7. Сжатие. Если значение целевой функции в отраженной точке хуже, чем у предпоследней вершины Xg, то выполняется операция сжатия, когда точка Xh сдвигается к центру тяжести остальных вершин в попытке найти лучшее положение вершины внутри симплекса (см. рис. 1, с):

где β – коэффициент сжатия. Если данный коэффициент выбран слишком маленьким, это может привести к слишком сильному сжатию симплекса, что приведёт к потере информации о локальных минимумах или преждевременному завершению поиска. Если он выбран слишком большим, сжатие может быть недостаточным для исследования окрестности худшей точки или может потребоваться избыточное число шагов и больше машинного времени для достижения окончательного решения. В результате для обеспечения удовлетворительного поиска параметров при оптимизации традиционно рекомендуется β=0,5 [1] или следующий диапазон изменения 0,4<β<0,6 [4].

8. Редукция. Если ни отражение, ни сжатие не улучшают ситуацию, то деформированный многогранник сужается, сближая каждую i-ю вершину с лучшей вершиной Xl (базовая точка), в результате чего формируется новый симплекс с уменьшенными вдвое сторонами. Эта операция является наиболее затратной и вызывается при застревании алгоритма, когда перемещение худшей точки симплекса не приносит улучшения решения (см. рис. 1, d):

9. Получение нового симплекса с вершинами.

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

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

Реализация метода деформируемого многогранника. Для программной реализации оптимизационного алгоритма деформируемого многогранника использовались известные блок-схемы схемы данного алгоритма [1, 4, 6], примеры его адаптации в различных математических пакетах и языках программирования [4 - 7], а также различные научные работы [8 - 10]. Результатом проделанной работы стал полностью работоспособный оптимизационный алгоритм для математического пакета PTC MathCAD, выложенный автором в свободном доступе для скачивания по ссылке [11].

Особенностью предлагаемой математической реализации алгоритма является замена традиционно встречающегося обозначения вершин многогранника через i-ый индекс на осмысленные буквенные обозначения, что сделало алгоритм легко воспринимаемым и читаемым. Кроме того, все математические операции с вершинами многогранника выполняются не перебором по каждому отдельному оптимизируемому параметру, а сразу со всем вектором оптимизируемых параметров вершины, что существенно ускоряет процесс оптимизационного поиска решения. Также стоит отметить, что из-за обнаруженного разночтения в опубликованных блок-схемах алгоритма [1, 4, 6], в качестве исходной была принята оригинальная блок схема [1].

Проверка математической реализации оптимизационного алгоритма деформированного многогранника проводилась на известных тестовых функциях [12], традиционно используемых для таких целей и позволяющих проверить скорость сходимости и точность найденного решения. Тестирование проводилось на различных двумерных целевых функциях, которые в настоящее время являются наиболее проработанными и легко проверяемыми в оптимизационных задачах. В качестве примера на рис. 2 приведено изображение одной из таких функций (функция Химмельблау) в изометрической проекции и в виде поверхности линий уровня с наложенным поиском решения методом деформируемого многогранника (схождением алгоритма).

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

a                                                         b
Рис. 2. График функции Химмельблау:
a – изометрическая проекция; b – поверхность линии уровня с наложенным поиском решения методом деформируемого многогранника (схождением алгоритма)

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

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

Результаты и обсуждение. При поиске минимума целевой функции начальные векторы оптимизируемых параметров X могут быть выбраны в точках, находящихся в вершинах регулярного симплекса. Из аналитической геометрии известно, что если в пространстве необходимо построить регулярный симплекс, одна из вершин которого находится в точке исходного вектора оптимизируемых параметров, то координаты вершин такого симплекса удобно задавать с помощью N×(N+1) матрицы [4, 5]:

где a – расстояние между двумя вершинами; N – число вершин симплекса.

После того как сформирована матрица вершин регулярного симплекса, можно применить предложенный математический алгоритм оптимизации методом деформируемого многогранника [11], для которого входными параметрами является матрица вершин регулярного симплекса (1) и сформированная целевая функция, а выходным параметром – вектор оптимизированных параметров.

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

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

где Ch и Cg – коэффициенты штрафов соответственно для равенств и неравенств.

Сформированную функцию штрафов (2) необходимо добавить к целевой функции и заново решить оптимизационную задачу методом деформируемого многогранника:

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

Список литературы

1. Nelder, J.A., Mead, R. A simplex method for function minimization. Comput. J. 7. P. 308 - 313, 1965.

2. Гальченко, В.Я. Трембовецкая Р.В. MathCAD: математические методы и инструментальные средства оптимизации / В.Я. Гальченко, Р.В. Трембовецкоая. – Черкассы: ЧП Гордиенко Е.И., 2018. – 516 с.

3. Мэтьюз, Джон Г., Финк, Куртис, Д. Численные методы. Использование MATHLAB, 3-е издание. : Пер. с англ. – М. : Издательский дом «Вильямс», 2001. –720 с.

4. Химмельблау, Д. Прикладное нелинейное программирование [Текст] / Д. Химмельблау; Пер. с англ. И. Н. Быховской и Б. Т. Вавилова ; Под ред. М. Л. Быховского. - Москва: Мир, 1975. - 534 с.

5. Аттетков, А.В. Галкин, С.В., Зарубин В.С. Методы оптимизации: учеб. для вузов / Под ред. В.С. Зарубина, А.П. Крищенко. – 2-е изд., стереотип. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2003. – 440 с.

6. Банди, Б. Методы оптимизации. Вводный курс: Пер. с англ. – М.: Радио и связь, 1988. – 128 с.

7. Дмитриева, Т. Л. Реализация условной задачи нелинейного математического программирования с использованием метода деформируемого многогранника в программе MathCAD / Т. Л. Дмитриева, В. Т. Нгуен // Современные технологии. Системный анализ. Моделирование. – 2014. – № 4(44). – С. 73-79.

8. Lagarias, J. C., Poonen, B., & Wright, M. H. (2012). Convergence of the Restricted Nelder--Mead Algorithm in Two Dimensions. SIAM Journal on Optimization, 22(2), 501–532. https://doi.org/10.1137/110830150

9. Суфиянов, В.Г., Клюкин Д.А., Русяк И.Г. (2023). Метод Нелдера-Мида решения задачи оптимизации геометрической формы ствола автоматической пушки для улучшения колебательных характеристик. Известия Самарского научного центра Российской академии наук, 25 (4 (114)), 121-131. doi: 10.37313/1990-5378-2023-25-4-121-131

10. Петрушин, А. Д. Оптимизация активной части вентильно-индукторного электродвигателя / А. Д. Петрушин, А. В. Кашуба // Вестник Ростовского государственного университета путей сообщения. – 2016. – № 1(61). – С. 61-65.

11. Алгоритм деформируемого многогранника [Электронный ресурс]. – Режим доступа : https://drive.google.com/file/d/172ozZXeprDCfWc3eA4_-xJd_zgVEIpyv. – Дата доступа: 01.11.2025.

12. Тимофеева, О. П. Исследование популяционных алгоритмов в решении задач непрерывной оптимизации / О. П. Тимофеева, С. А. Неимущев, Л. И. Неимущева // Труды НГТУ им. Р.Е. Алексеева. – 2018. – № 4(123). – С. 48-55. – DOI 10.46960/1816-210X_2018_4_48.

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

Для цитирования данной работы | To cite this work:

Котов, А. В. От симплекса к рабочей формуле: адаптация метода деформированного многогранника под задачи синтеза механизмов / А. В. Котов // Vectormethod.blogspot.com [Электронный ресурс]. – 2020. – Режим доступа: https://vectormethod.blogspot.com/2026/04/ot-simpleksa-k-rabochej-formule-adaptaciya-metoda-deformirovannogo-mnogogrannika-pod-zadachi-sinteza-mekhanizmov.html. – Дата доступа: .

Kotov A. V. Ot simpleksa k rabochey formule: adaptatsiya metoda deformirovannogo mnogogrannika pod zadachi sinteza mekhanizmov [From simplex to working formula: adaptation of the deformed polyhedron method to the problems of mechanism synthesis]. Vectormethod.blogspot.com [Electronic resource]. – 2020. – Mode of access: https://vectormethod.blogspot.com/2026/04/ot-simpleksa-k-rabochej-formule-adaptaciya-metoda-deformirovannogo-mnogogrannika-pod-zadachi-sinteza-mekhanizmov.html. – Date of access: (in Russ.)