Авторы: Котов А.В.
Одна из ключевых глав моего диссертационного исследования посвящена разработке нового метода синтеза плоских рычажных механизмов. Казалось бы, что здесь можно придумать нового? Ведь тема изучена вдоль и поперек.
Действительно, если проанализировать современные научные работы, большинство решений в этой области в настоящее время сводится к совершенствованию уже существующих оптимизационных алгоритмов. Исследования движутся в направлении ускорения поиска экстремума целевой функции и повышения точности для многоовражных функций. Но по сути - это эволюция инструмента, а не изменение подхода.
Долгое время я не знал, как подступиться к этой теме, откладывая ее на потом. Но время шло, и нужно было что-то делать.
⚙️ Начало пути: погружение в оптимизацию
Я начал с анализа существующих оптимизационных алгоритмов, надеясь предложить что-то новое или усовершенствовать старое. Благо, определенные навыки программирования у меня были — писать и читать алгоритмы я умею.
Как вы, наверное, заметили, все свои расчеты я веду в математическом пакете PTC MathCAD. Этот программный продукт обладает встроенными функциями для поиска экстремума — minimize() и maximize(). Работа с ними довольно проста и интуитивно понятна. Я уже решил с их помощью несколько практических задач. Однако эти функции представляют собой «черный ящик» - без возможности вмешательства в процесс поиска решения и влияния на него (за исключением выбора метода: квазиньютоновский или сопряженных градиентов).
И вскоре я начал поиск доступного оптимизационного алгоритма, написанного под математический пакет PTC MathCAD.
📉 Градиентные алгоритмы: первые разочарования
Начал я, как наверное и все, с градиентных алгоритмов оптимизации. Как и ожидалось, поиск решения у данных алгоритмов в PTC MathCAD оказался крайне ресурсоемким. Простые задачи вычислялись еще более-менее, а вот что посложнее - с трудом и зависаниями.
Как я уже давно заметил, нахождение производных в PTC MathCAD — очень затратная операция. Одно дело единожды найти производную функции, и совсем другое — заложить ее в оптимизационный алгоритм и запустить в цикле. Здесь PTC MathCAD откровенно не справляется.
📐 Безградиентные алгоритмы: метод деформируемого многогранника
Тогда я обратил свой взор на безградиентные алгоритмы. Мой выбор пал на метод деформируемого многогранника (или метод Нелдера-Мида, или симплекс-метод). Данный алгоритм придуман давно и считается эталоном оптимизационного программирования. Его ключевое преимущество - он не требует вычисления производных, что делает его идеальным для задач, где градиент сложно или невозможно получить аналитически.
Суть метода в том, что он работает не с отдельными точками, а с симплексом — геометрической фигурой, каждая вершина которой соответствует некоторому набору оптимизируемых параметров. Процесс оптимизации заключается в том, чтобы путем последовательных итераций (отражение, растяжение, сжатие, редукция) изменять и перемещать симплекс в пространстве параметров, стремясь приблизить его вершины к глобальному оптимуму. Подробнее о данном методе можно узнать из моего поста в блоге - От симплекса к рабочей формуле: адаптация метода деформированного многогранника под задачи синтеза механизмов - «От симплекса к рабочей формуле: адаптация метода деформированного многогранника под задачи синтеза механизмов».
Изучив теорию, а также изучив доступные коды данного алгоритма (в том числе реализованные для PTC MathCAD), я, используя свои знания и накопленный опыт работы с массивами, доработал алгоритм. За основу я взял исходную блок-схему, опубликованную авторами, поскольку в процессе изучения темы обнаружилось много разночтений в реализации.
Особенностью моей реализации стало: использование легко читаемого программного кода за счет применения осмысленных буквенных обозначений для вершин симплекса (вместо i-ых индексов); автоматизированное формирование вершин исходного регулярного симплекса, интегрированное в тело алгоритма; ряд второстепенных улучшений, направленных на повышение эффективности работы алгоритма.
Готовый доработанный алгоритм я выложил в открытый доступ для скачивания. А результаты работы с ним вылились в написание научной статьи «Оценка возможности применения метода деформируемого многогранника к задаче оптимизационного кинематического синтеза плоского рычажного механизма», где проверка работоспособности алгоритма показала его достаточно высокую точность и скорость сходимости. Метод позволяет существенно увеличить используемое число оптимизируемых параметров, а также применять более сложные критерии оптимизации, что особенно важно для многозвенных плоских рычажных механизмов со сложной кинематической схемой.
Главный недостаток метода деформируемого многогранника - это начальное приближение. В зависимости от него алгоритм может уйти «не туда». Поэтому требуется проверка поиска решения с различными начальными приближениями. И это меня не устраивало.
🧬 Стохастические алгоритмы: генетический подход
Поэтому дальнейший взор я обратил на наиболее перспективные на сегодняшний день алгоритмы - стохастические. Из них наибольшую известность получил генетический алгоритм, который представлен в различных модификациях и постоянно совершенствуется в научных работах как отечественных, так и зарубежных авторов.
Также интерес представляют муравьиный алгоритм, алгоритм роя, метод отжига и другие. Но данные алгоритмы еще мало представлены в литературе, и для того чтобы в них разобраться, требуется гораздо больше времени. Чего, откровенно говоря, не хотелось делать ввиду его отсутствия и неизвестности дальнейшего направления движения в синтезе плоских рычажных механизмов.
Генетический алгоритм основан на естественном отборе и позволяет, манипулируя генеральной совокупностью, постепенно отсеивать «бесполезные» особи (решения), оставляя наиболее приспособленные.
Поскольку классический генетический алгоритм обладает рядом существенных недостатков (в частности, необходимостью работы с большим числом особей), выбор пал на модифицированный алгоритм.
В научных работах мне приглянулся алгоритм, предложенный Сабаниным В.Р.: «Модифицированный генетический алгоритм для задач оптимизации в управлении».
Полный код данного алгоритма был представлен автором в работе и написан именно для PTC MathCAD. Что меня полностью устраивало и, естественно, заинтересовало.
🚀 Модернизация: гибридный подход
К моей радости, оказалось, что данный алгоритм использует метод деформируемого многогранника для отсеивания «плохих» особей. А этот алгоритм в рабочем виде уже был у меня заготовлен!
Я взял исходный код модифицированного генетического алгоритма за основу и решил разобраться с ним досконально. Строчка за строчкой я полностью понял принцип его работы, обнаружил недостатки и наметил возможные улучшения.
В результате я учел некоторые несовершенства модифицированного генетического алгоритма, объединив его с уже имеющимся у меня методом деформируемого многогранника. В итоге я получил модернизированный модифицированный генетический алгоритм.
Его достоинства (по моим сугубо субъективным оценкам): более быстрая работа; отсутствие сбоев; понятность с точки зрения программирования (осмысленные буквенные обозначения для массивов).
Данный алгоритм у меня полностью написан под PTC MathCAD, но пока я его не выкладываю. Быть может, применив его в одной из своих работ, я, как и алгоритм метода деформируемого многогранника, выложу его со ссылкой в свободный доступ. Так что придется немного подождать.
А пока я выкладываю исходный код модифицированного генетического алгоритма из статьи Сабанина В.Р. «Модифицированный генетический алгоритм для задач оптимизации в управлении», восстановленный по тексту работы. Быть может, он кого-то заинтересует, и ему не придется набирать и отлаживать весь код с нуля (смотрите также и другие мои шаблоны для расчетов, размещенные в разделе «Скачать». Пользуйтесь на здоровье!
Достоинства и ограничения модифицированного генетического алгоритма: менее чувствителен к начальным условиям; может немного выходить за жесткие границы поиска, если там есть экстремум (это одновременно и достоинство, и недостаток); скорость расчета может регулироваться несколькими параметрами, что позволяет минимизировать время счета.
✅ Важное замечание
Все оптимизационные алгоритмы, написанные «вручную», уступают по времени расчета встроенным функциям PTC MathCAD - minimize() и maximize(). Поэтому сравнение времени решения с данными функциями считаю некорректным. Я связываю это с тем, что все ресурсы математического пакета при работе с данными функциями максимально оптимизированы и находятся в приоритете. В то время как пользовательские коды не имеют такого приоритета и рассчитываются гораздо медленнее.
🧰 Итог: мой инструментарий на сегодня
На этом поиск достойных и современных алгоритмов оптимизации я завершил. На сегодняшний день в моем арсенале имеется три оптимизационных алгоритма (метода): 1. встроенный в систему PTC MathCAD (minimize / maximize); 2. метод деформируемого многогранника (Нелдера-Мида); 3. доработанный модифицированный генетический алгоритм (гибридный).
Все, что требуется для работы данных алгоритмов это: наличие целевой функции для минимизации; начальное приближение; границы поиска оптимизируемых параметров; если есть - наложенные функциональные ограничения в виде равенств или неравенств.
Стоит отметить, что метод деформируемого многогранника и модифицированный генетический алгоритм (как и его доработанная версия) могут быть адаптированы для решения задач с ограничениями. Для этого используется метод штрафных функций, когда к целевой функции добавляется штраф за нарушение ограничений. Это особенно важно в инженерной практике, где на параметры механизма всегда наложены конструктивные ограничения (например, на длины звеньев или координаты опор).
🔮 Вместо заключения
Но если оптимизационные алгоритмы — это всего лишь инструмент в умелых руках ученого или инженера, то новый метод синтеза — это уже нечто новое, самостоятельное и научное. О чем и пойдет речь во второй части поста, которая будет уже скоро. Так что не пропустите!
Любое цитирование текста, использование тезисов или иллюстраций из данной статьи допускается только с указанием обязательной ссылки на первоисточник. Пожалуйста, уважайте авторские права и интеллектуальную собственность.
Комментариев нет:
Отправить комментарий