Модель гравитационного взаимодействия материальных точек переменной массы в задачах поиска экстремума функции

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

Теория экстремальных задач включает в себя несколько направлений: математическое программирование [33, 56], численные методы безусловной оптимизации [14], вариационное исчисление, теорию оптимального управления [32, 42]. Дальнейшая классификация задач связана со спецификой целевой функции. Так в математическом программировании выделяют следующие разделы: линейное, нелинейное, выпуклое, квадратичное программирование, многоэкстремальные задачи, а также целочисленное программирование. В каждом из них разработан свой аппарат поиска экстремума [7, 14, 42].

В рамках данной работы рассматриваются задачи поиска экстремума нелинейной функции с действительными переменными. Этот класс задач относится к области непрерывной оптимизации, ведущими российскими специалистами в которой являются В. П. Булатов, Ю. Г. Евтушенко, И. И. Ерёмин, A.C. Стрекаловский и др [16, 46].

К сожалению, в практических приложениях целевая функция нередко не удовлетворяет необходимым условиям для возможности применения той или иной методики. В связи с этим при решении прикладных экстремальных задач наряду с традиционными методами широко используются приближенные алгоритмы, которые с одной стороны имеют меньшую трудоемкость, и с другой — позволяют снизить требования на гладкость целевой функции [6, 11, 13, 84].

Но даже в случае, когда целевая функция дифференцируема достаточное число раз, остро встает вопрос о близости начального приближения к точке экстремума, что является необходимым требованием применения локальных быстр о сходящихся алгоритмов [14, с.114−117], [42, с.46−59].

Последнее десятилетие в связи с развитием вычислительной техники при исследовании различных задач моделирования успешно используются алгоритмы, основанные на «естественных» аналогиях. Этот класс методов имеет богатую историю и продолжает активно развиваться [58, 61, 88]. Например, моделирование сложных самоорганизующихся структур и изучение их поведения явилось первой ступенью для создания нового направления в науке — синергетики [40, 54]. Разработка математической модели на основе законов эволюции живой природы позволила создать эффективные алгоритмы, успешно применяемые в теории экстремальных задач [77, 88], при проектировании самообучающихся систем [69, 75, 94], в задачах распознавания[59] и т. п. Примерами могут служить генетические алгоритмы [71, 78, 87, 88, 96] и эволюционные стратегии [86, 92]. Смежным направлением, также использующим биологические аналогии, является нейропрограммирование (нейронные сети) [10, 85, 97].

В русле данного подхода рассматриваются методы исследования экстремальных задач с использованием алгоритмов, основанных на законах механики [25, 60, 62, 70] и энтропийные методы моделирования сложных систем, в частности, «гравитационные модели» задач транспортного типа и размещения [8].

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

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

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

Для достижения этой цели были выполнены исследования по следующим направлениям. В теоретическом плане:

— проведен обзор приближенных, в том числе эвристических, методов поиска экстремума, указаны преимущества и слабые моменты существующих подходов;

— построена математическая модель реального процесса, законы протекания которого позволяют учесть особенности поставленной экстремальной задачи;

— на основе этой модели разработан эвристический «гравитационный» метод поиска экстремума нелинейной функции без предположения о ее дифференцируемости;

— установлена связь основных стратегий разработанного метода с существующими алгоритмами.

В экспериментальном плане:

— при помощи компьютерного моделирования исследованы работоспособность и качественные характеристики «гравитационного» метода;

— «гравитационный» метод применен для решения ряда прикладных задач и производственных проблем;

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

Методы исследования. При решении поставленных задач использовались приближенные алгоритмы поиска экстремума функции, геометрическое моделирование в пространстве произвольной размерности, конечно-разностные методы решения обыкновенных дифференциальных уравнений (ОДУ) и систем ОДУ, компьютерное моделирование, а также современная методология экспериментальных исследований с применением вычислительной техники.

Научная новизна. К новым результатам диссертации относятся:

— использование гравитационных аналогий в методе поиска экстремума функции, основанном на коллективном взаимодействии набора рабочих точек;

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

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

— математическая модель задачи минимизации суммарных затрат по производству некоторого продукта для непрерывно распределенных величин;

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

Практическая и теоретическая ценность результатов работы:

— разработан приближенный метод поиска экстремума нелинейной функции с действительными переменными без предположения о ее дифферен-цируемости — «гравитационный» метод;

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

— «гравитационный» метод используется при решении задачи минимизации многоэкстремальной функции, возникающей в экспериментах физики высоких энергий, проводимых в ОИЯИ РАН (г. Дубна).

— в соавторстве с Р. Т. Файзуллиным, К. В. Логиновым, С. Л. Семиным создан пакет программ «Гидравлический расчет и выбор оптимальных режимов работы разветвленного магистрального нефтепровода», в настоящее время используемый в ОАО «Транссибнефть» (г. Омск).

Апробация работы. Результаты работы докладывались на Международной научно-технической конференции «Динамика систем, механизмов и машин» (Омск, 1995), Международной конференции «Проблемы оптимизации и экономические приложения» (Омск, 1997), Второй научной конференции молодых ученых и специалистов ОИЯИ (Дубна, 1998), Третьем Сибирском конгрессе по прикладной и индустриальной математике «ИНПРИМ-98» (Новосибирск, 1998), Х1-ой Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 1999), Четвертом Сибирском конгрессе по прикладной и индустриальной математике «ИНПРИМ-00» (Новосибирск, 2000), а также на семинарах кафедры математического моделирования Омского государственного университета, на спецсеминаре «Моделирование систем. Информационная экология» Омского филиала института математики им. С. Л. Соболева СО РАН, на семинаре кафедры теории управления и оптимизации Челябинского государственного университета.

Публикации.

Основные результаты диссертации опубликованы в 11 печатных работах [19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30]. Из совместных публикаций в диссертацию вошли результаты, полученные непосредственно автором.

Основные положения, выносимые на защиту:

— «гравитационный» метод поиска приближенного экстремума функции с действительными переменными без предположения о ее дифференцируемости, основанный на модели динамической системы гравитирукмцих частиц с переменной массой;

— математическая модель и точное решение задачи минимизации суммарных затрат по производству некоторого продукта для непрерывно распределенных величин;

— алгоритм выбора оптимальных режимов работы разветвленного нефтепровода, использующий гравитационные аналогии;

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и приложения. Объем составляет 160 страниц. Библиографический список насчитывает 97 наименований.

Заключение

.

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

На первом этапе предложен «гравитационный» подход к решению экстремальной задачи. Разработан приближенный метод поиска экстремума функции, характерными свойствами которого являются:

— использование множества точек вместо одного начального приближения;

— на каждом шаге метода на основе предложенной модели решается аналог задачи ]У-тел, где масса частиц меняется от итерации к итерации и равна значению целевой функции в данной точке пространства;

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

— в методе используется механизм случайного поиска, что позволяет гарантировать сходимость (по вероятности) к экстремуму целевой функции;

— на каждой итерации лучшие, с точки зрения целевой функции, частицы фиксируются.

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

— необходимы малые возмущения системы по мере приближения «лучшей» точки (множества точек) к экстремуму целевой функции;

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

Решение ряда практических задач (оптимизация систем дипольных решеток [22, 36], задача геометрической реконструкции событий в экспериментах физики высоких энергий [22]), использование гравитационных аналогий в задаче поиска оптимальных режимов работы разветвленного нефтепровода позволили получить следующие характеристики метода и рекомендации по его применению на практике:

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

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

142 ритмов, сильно чувствительных к выбору стартовой точки;

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