Модель гравитационного взаимодействия материальных точек переменной массы в задачах поиска экстремума функции тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Жихалкина, Надежда Федоровна

• Жихалкина, Надежда Федоровна
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Жихалкина, Надежда Федоровна

Введение

1. Методы решения задачи поиска экстремума функции

1.1. Постановка задачи

1.2. Методы первого и второго порядка.

1.3. Классификация методов поиска.

1.4. Методы и модели, основанные на гравитационных аналогиях

2. Гравитационный метод поиска экстремума функции

2.1. Одномерное пространство поиска.

2.2. Гравитационный метод в задачах произвольной размерности

2.3. Сходимость гравитационного метода.

2.4. Связь с эволюционными алгоритмами

2.5. Аппроксимация градиента целевой функции.

2.6. Общие характеристики, тестирование.

3. Выбор оптимальных режимов работы нефтепровода

3.1. Содержательная постановка.

3.2. Формализация проблемы.

3.3. Постановка задачи минимизации суммарных затрат.

3.4. Точное решение.

3.5. Задача выбора оптимальных режимов, примеры.

3.6. Поиск приближенного решения, гравитационные аналогии

4. Гравитационный метод в прикладных задачах

4.1. Геометрическая реконструкция треков заряженных частиц

4.2. Дипольные решетки.

4.3. Динамический подход к задаче кластеризации

4.4. Задача Штейнера.

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

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

Теория экстремальных задач включает в себя несколько направлений: математическое программирование [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 ритмов, сильно чувствительных к выбору стартовой точки;

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