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



На правах рукописи ЖИХАЛКИНА НАДЕЖДА ФЕДОРОВНА

- МОДЕЛЬ ГРАВИТАЦИОННОГО ВЗАИМОДЕЙСТВИЯ МАТЕРИАЛЬНЫХ ТОЧЕК ПЕРЕМЕННОЙ МАССЫ В ЗАДАЧАХ ПОИСКА ЭКСТРЕМУМА ФУНКЦИИ

05.13.18 - Теоретические основы математического моделирования, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Омск - 2000

Работа выполнена на кафедре математического моделирования Омского государственного университета.

Научные руководители: доктор физико-математических наук,

профессор Гуц Александр Константинович; кандидат физико-математических наук, доцент Файзуллин Рашит Тагирович.

Официальные оппоненты: доктор физико-математических наук,

профессор Широков Игорь Викторович; кандидат физико-математических наук, доцент Бигильдеева Татьяна Борисовна-

Ведущая организация: Институт вычислительного моделирования

СО РАН (г. Красноярск).

Защита состоится « £ » оеил^^иИ 2000 г. в & часов на заседании диссертационного совета Д 064.19.03 по присуждению ученой степени доктора наук в Челябинском государственном университете по адресу: 454021, г. Челябинск, ул. Братьев Кашириных, 129.

С диссертацией можно ознакомиться в библиотеке Челябинского государственного университета.

Автореферат разослан « 3 » 2000 г.

Ученый секретарь

диссертационного совета, ^

д-р физ.-мат. наук, профессор В.И. Ухоботов

Актуальность темы.

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

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

Последнее десятилетие в связи с развитием вычислительной техники V при исследовании различных задач моделирования успешно используются алгоритмы, основанные на «естественных» аналогиях. Разработка мате-\ матической модели на основе законов эволюции живой природы позволила создать эффективные алгоритмы, успешно применяемые в теории экстремальных задач, при проектировании самообучающихся систем, в задачах распознавания и т.п. Примерами могут служить генетические алгоритмы и эволюционные стратегии [9, 10, 11]. Смежным направлением, также использующим биологические аналогии, является нейропро-граммирование (нейронные сети). В русле данного подхода рассматриваются методы исследования экстремальных задач с использованием алгоритмов, основанных на законах механики [8]. В настоящее время развиваются энтропийные методы моделирования сложных систем, в частности, «гравитационные модели» задач транспортного типа и размещения [2]. Попытки выявить закономерности, лежашие в основе пространственных взаимодействий между городами (перемещение людей, грузов, информации, диффузии нововведений, другие виды взаимодействий), также привели к идее воспользоваться аналогиями с фундаментальным законом всемирного тяготения [5].

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

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

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

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

Практическая и теоретическая ценность результатов работы: разработан приближенный метод поиска экстремума нелинейной функции с действительными переменными без предположения о ее дифференцируе-мости - «гравитационный» метод; метод, основанный на гравитационных аналогиях, применен при решении задачи минимизации многоэкстремальной функции, возникающей в экспериментах физики высоких энергий, проводимых в ОИЯИ РАН (г. Дубна); в соавторстве с Р.Т. Файзулли-ным, К.В. Логиновым, С.Л. Семиным создан пакет программ «Гидравлический расчет и выбор оптимальных режимов работы разветвленного магистрального нефтепровода», в настоящее время используемый в ОАО «Транссибнефть» (г. Омск).

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

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

Публикации. Основные результаты диссертации опубликованы в 11 печатных работах [12] - [22]. Р1з совместных публикаций в диссертацию вошли результаты, полученные непосредственно соискателем.

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

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

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

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

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

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

Содержание работы:

Во введении сформулированы цель и задачи исследования, освещена история вопроса, перечислены основные результаты работы.

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

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

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

В первом параграфе рассматривается задача безусловной максимизации с целевой функцией Г : [а, Ь] -» где отрезок [о, £>] принадлежит пространству К. Требуется найти такую точку х* € [а,Ь], что Ух € [аД (Г{х*) > ^(ж)). Предлагаемый гравитационный алгоритм заключается в следующем. На отрезке [а,6] задаются одновременно две «частицы» х\, Х2■ В начальный момент времени их координаты равны, соответственно, а и Ь. Определяя «массу частицы» как значение целевой функции в данной точке области поиска: ттц = г € {1,2}, предполагается, что между

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

о о 1 1 ^

ж" = а, %2= Ь.

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

Во втором параграфе представлена математическая модель динамической системы материальных точек переменной массы в ^-мерном ев-

клидовом пространстве Ж*, на основе которой строится гравитационный метод. Пусть ^ : б 8, где С? - область в Ж*. Требуется найти точку г * е <7 такую, что *) = тах^о ^(г)- Предполагается, что целевая функция удовлетворяет следующим условиям: функция Е определена в любой точке, принадлежащей (7; точка экстремума лежит внутри области С; Уг ев

В начальный момент времени в области (7, называемой областью оптимизации или поиска, генерируется N точек (частиц) г -° с плотностью распределения ро(г) > 0. Масса каждой частицы зависит от ее координат и опредачяется значением целевой функции в данной точке пространства: га™ = ^(г{п). На каждой итерации решается аналог задачи N тел [7], при этом формулы расчета координат «взаимодействующих частиц» принимают вид:

здесь А^1 - коэффициент, определяющий величину шага в выбранном направлении а? на итерации п,к\ = 0 ,...,к. Алгоритм (2) назван гравитационным. Помимо А" и к\ настраиваемыми параметрами алгоритма являются: радиус взаимодействия; число наиболее «тяжелых» частиц, остающихся неподвижными на данной итерации; коэффициент М, определяющий во сколько раз фиктивная масса «лучших», с точки зрения целевой функции, частиц превышает значение целевой функции.

Начиная с некоторой итерации, на каждом шаге метода осуществляется так называемое «отражение» в одной из координатных плоскостей, играющее роль малых возмущений системы. При этом выбор плоскости «отражения» носит вероятностный характер. Пусть выбрана плоскость Огиг„ и п = Формулы

для вычисления координат г-й точки имеют вид:

Настраиваемыми параметрами являются /х", радиус взаимодействия Лг и £ {0,1,2}, наиболее «тяжелые» частицы могут фиксироваться и наделяться добавочной массой. Алгоритм (3) назван малыми возмущениями системы.

Гп+1 = гТ+Хп^п+ 1А?гг. а{° = 0,

71 — 1

(2)

(3)

В третьем параграфе представлена, общая схема гравитационного метода поиска экстремума функции:

Шаг 0: п := 0, в области поиска О на основе некоторого закона распределения задается N точек г,0 с плотностью распределения ро(г) > 0, переход на шаг 1.

Шаг 1: используя гравитационный алгоритм, происходит преобразование координат точек г^"',..., ггу , переход на шаг 2.

Шаг 2: (может отсутствовать) реатизуются малые возмущения системы Лг точек на основе «отражения» в одной из координатных плоскостей, переход на шаг 3.

Шаг 3: (может отсутствовать) представляет собой случайный поиск. В соответствии с плотностью распределения р(г) > 0 в области (7 генерируется случайный вектор грп. «Худший» с точки зрения целевой функции, вектор г" заменяется на грп в том случае, если Р(г^п) < лР(грп). Далее п := п + 1, переход на шаг 1.

Утверждение 2.1. Если Р непрерывна в С, на шаге 3 используется равномерное распределение, то гравитационный метод сходится по вероятности к экстремуму целевой функции.

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

В четвертом параграфе рассматривается связь с существующими эволюционными стратегиями: рекомбинации ставится в соответствие «отражение» (шаг 2), а мутации отвечают гравитационное взаимодействие (шаг 1) и случайный поиск (шаг 3). Но принципиальное отличие заключается в том, что если в эволюционных алгоритмах мутация играет роль малых возмущений, тогда как рекомбинация выступает основным оператором получения новых особей в популяции, то в гравитационном методе - наоборот: решение аналога'задачи Лг тел является инструментом получения новых точек, близких к экстремуму, а «отражение» вносит в систем}' элемент случайности.

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

Пусть F : £7 —> К ((? - область в ^ дифференцируема в С, число рассматриваемых точек равно N 4- 1. Новые координаты текущей точки г П+1 вычисляются по схеме: г = г "+ Л'1 ^ту^ „"^ц - ■ Пусть

Г,« = 74, Р{п) = Мг, ||г- - 7=11 = Ъ,К= ЕГ=1 '

Утверждение 2.3. Вектор Л (при к\ — к > Ъ) представляет собой градиент интерполяционной формулы Рн{г) = М№(г) в том случае, когда сама конечная сумма получена с помощью функций / _\-(*-2)

К(г) = ф = С , где С =

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

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

В третей главе детально исследуется задача выбора оптимальных режимов работы нефтепровода.

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

Формализация проблемы во втором параграфе осуществляется в терминах задачи целочисленного (булева) программирования: требуется найти вектор ж* € B.'^!:1""i~••■+'u^', доставляющий минимум в уравнении (4) и удовлетворяющий ограничениям (5):

V щ

а. т1п; (4)

¿=1

2>?<1, I =1,^е{0,1), (5)

г=1 5=1 в=1

где 8{ = 1,...,щ, г = 1,..., V. Коэффициенты целевой функции щ и константа С положительные; Н? - неотрицательны. Величина С опреде-' ляется напором, необходимым, чтобы прокачать по нефтепроводу заданный объем нефти.

В третьем параграфе рассматривается общая постановка задачи минимизации суммарных затрат по производству некоторого продукта.. Не-

зависимая переменная t £ [0,1]. Неотрицательная, ограниченная функция H(t) (H : [0,1] —> 0 < H{t) < К) задает распределенную мощность по производству продукта Q. Требуется минимизировать суммарные затраты с учетом КПД v(t) (1/ : [0,1] М+) и функции цены a(t)

(а : [0,1] -> М+, 0 < ка < a(t) < Ка): f Щ^-dt min, полагая, что

о

1

суммарная мощность постоянна: f H{t)dt = С > 0. В общем случае

о

КПД также зависит от H(t). Представим данную проблему в терминах

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

t

ния. Для этого введем функцию x(t) = J H(х : [0,1] —> M). Тогда

о

ж(0) = 0, ж(1) = £ H(£)dÇ — С и i(i) = #(£). Таким образом, исходная задача

0

1

j H(t)dt = С, (7)

о

представленная в терминах задачи вариационного исчисления, является задачей Лагранжа [4] и имеет вид:

1 1 J{x{.)) = j L(t,x(t))dt = j inf; (8)

о о

ж(0) = 0, х(1) = С, 0 < ¿(¿) < К. (9)

Используя уравнение Эйлера и неравенство Гельдера в четвертом параграфе удалось найти точное решение для некоторых частных видов интегранта задачи. Рассмотрим случай, когда цена неизменна на всей трассе. Тогда Ь(£, #(£)) = у-

Утверждение 3.1. Пусть интегрант L задачи (6) - (7) имеет

вид L(t,H(t)) = Hm{t) (т е NJ. Тогда функция H*(t) = С = const доставляет минимум в этой задаче. Отсюда непосредственно следует

Утверждение 3.2. Дано семейство неотрицательных ограниченных функций, нормы которых в пространстве L\ равны некоторому числу С. Тогда минимум нормы в пространстве Lm достигается на константе С.

Утверждение 3.3. Пусть интегрангп L задачи (6) - (7) имеет вид L(t,H(t)) = Cm(H(t))m + ... + CiH(t) (т е Nj. Тогда функция H,(t) ~ С = const доставляет минимум в этой задаче.

Пусть теперь цена, заданная функцией a(i), не равна константе.

Утверждение 3.4. Функция

п

X. (t) = Я* (0 =-Ц--(10)

(aW)1^"1) I щф^Т

доставляет минимум в задаче (6) - (7), интегрант которой задается формулой L(t, H(t)) = (H(i))ma(i) (т G N, m > 2).

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

Р,-С~1мт.«±3* (И,

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

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

Будем рассматривать допустимую функцию Н(Ь) как материальную точку а некотором функциональном пространстве. Расстояние между двумя такими «частицами» Н1(Ь) и #-Ч£) определяется при помощи нормы в выбранном пространстве. Материальной точке Н(£) ставится в соответствие ее масса, равная значению максимизируемого функционала:

Мя = М(Н(4))| =1 //д1 —■ Областью поиска С является пря-

I ¿6(0,1] /

моугольная область [0,1] х [О, А']. Пусть ¿1 = 0,... ,£„+1 = 1 - разбиение отрезка [0,1]. В качестве начального распределения материальных точек выбирается конечное число функций £Р(г) (з = представля-

ющих собой ломаные с узлами в точках для которых значе-

ние функции в г-й точке разбиения равно вырабатываемому на г-й станции напору при одном из возможных включений насосов: Н!>(Ь{) — Н? (г 1,...,г>) и /д Нв(í)íit — С. Предлагаемый приближенный метод поиска экстремума основан на аналогиях с законом гравитационного притяжения и заключается в корректировке функции Н5(£) на итерации (га. 4-1) в зависимости от «массы» окружающих ее «частиц» на итерации п. Далее осуществляется переход от притяжения в функциональном пространстве к покоординатному притяжению в пространстве К". В общем случае

Я«.+1) - Щ(п) + л; £ . (*>

где 8 = 1,..., Лг, г = 1,... ,г). На каждой итерации возможны проверка допустимости функции Н* (I, п) и последующая ее корректировка в соответствии с технологическими ограничениями.

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

В первом параграфе рассматривается задача реконструкции треков заряженных частиц. В процессе эксперимента по изучению радиоактивного распада ядер 100Мо, проводимого в Объединенном институте ядерных исследований (ОИЯИ, Дубна) [13], строится набор окружностей: (хг,1л) - координаты центров, ¿i - радиусы (г = 1,..., А''). Трек частицы определяется как ломаная с узлами в точках, которые лежат на полученных окружностях и абсциссы которых равны х¿. Гладкостью линии

в данном случае называется сумма величин меньших углов между прямыми, содержащими соседние прямолинейные отрезки, образующие эту линию. Задача восстановления трека заряженной частицы сводится к минимизации функции, определяющей гладкость линии. Итерационная процедура поиска трека электрона стартует с двух «точек». Здесь роль «точек» играют линии, первоначально «касающиеся» окружностей сверху и снизу. В процессе итераций эти «точки» подвергаются воздействию нескольких типов сил, один из которых - «силы взаимного притяжения». Рассмотрим произвольную окружность т из N возможных. Пусть у[1 и у" - соответствующие ординаты узлов рассматриваемых ломаных на итерации п (их абсциссы совпадают и равны хт). Значения целевой функции не зависят от номера узла и определяются гладкостью соответствующей линии на текущей итерации. Обозначим их Р™ и ЛГ. Тогда формулы гравитационного алгоритма принимают вид:

Критерием остановки является условие совпадения рассматриваемых «точек».

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

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

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

Основные результаты диссертации:

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

'пи У2 — Ут

м €{1,2}, 1фз\

(13)

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

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

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

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

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

[1] Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988. 128 с.

[2] Вильсон А.Д. Энтропийные методы моделирования сложных систем. М.: Наука, 1978. 248 с.

[3] Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир, 1988. 440 с.

[4] Иоффе А. Д., Тихомиров В. М. Теория экстремальных задач. М.: Наука, 1974. С.73-399.

[5] Перцик Е.Н. Города мира. География мировой урбанизации. М.: Международные отношения, 1999. С.243.

[6] Полак Э. Численные методы оптимизации. М.: Мир, 1974. 376 с.

[7] Поттер П. Вычислительные методы в физике. М.: Мир, 1975. С.162-193.

[8] Asselmeyer Т., Ebeling W. Unified Description of Evolutionary Strategies over continous Parameter spaces // Institut of Physics, Humboldt University Berlin. 1996. Electronic version.

[9] Goldberg D. E. Genetic Algorithms in Search, Optimization and Mashing Learning. Addison-Wesley. Reading. MA. 1989. 412 p.

[10] Mühlenbein Heinz Genetic algorithms // local Search in Combinatorial Optimization / Edited by E. Aarts and J. K. Lenstra. 1997. P.137-171.

[11] Reeves C. R. Genetic Algorithms for the Operations Reseacher // INFORMS Journal on Computing. V.9. N 3. 1997. P.231-250.

Список публикаций автора по теме диссертации

[12] Жихалкина Н. Ф., Файзуллин Р. Т. Гравитационная и генетическая аналогии в задаче безусловной оптимизации // Тезисы докладов международной конференции «Проблемы оптимизации и экономические приложения». Омск. 1997. С.71.

[13] Жихалкина Н. Ф., Кисель И. В., Назаренко М. А., Файзуллин Р. Т. Гравитационный метод безусловной глобальной оптимизации // Сообщения ОИЯИ Р5-97-255. Дубна, 1997. 14 с.

[14] Жихалкина Н. Ф., Кисель И. В., Назаренко М. А., Файзуллин Р. Т. Гравитационные аналогии в задаче безусловной глобальной оптимизации // Вторая открытая научная конференция молодых ученых и специалистов ОИЯИ. Труды конференции. Д-98-244. Дубна. 1998. С.77-79.

[15] Жихалкина Н. Ф., Файзуллин Р. Т. Модель взаимодействующих частиц разной массы в задаче безусловной оптимизации // Третий сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ-98). Тезисы докладов. Часть V. Новосибирск. 1998. С.79-80.

[16] Жихалкина Н. Ф., Файзуллин Р. Т. Гравитационные аналогии в задаче оптимизации // Математические структуры и моделирование. 1998. Омск: ОмГУ. Вып. 2. С.60-76.

[17] Жихалкина Н. Ф., Файзуллин Р. Т. Гравитационный алгоритм поиска экстремума функции // Тезисы докладов конференции «Математическое программирование и приложения». Екатеринбург. 1999. С.107-108.

[18] Жихалкина Н. Ф. Непрерывные модели и гравитационные аналогии в одной задаче гидравлики // Математические структуры и моделирование. 1999. Омск: ОмГУ. Вып. 4. С.69-73.

[19] Жихалкина Н. Ф., Логинов К. В., Семин С. Л., Файзуллин Р. Т. Поиск оптимальных режимов работы больших гидросетей и нефтепроводов. Омск: ОмГУ. 1999. 96 с.

[20] Жихалкина Н. Ф. Алгоритмы, функционирующие по законам типа гравитационного и генетического // I всесибирский конгресс женщин-математиков. Тезисы докладов. Красноярск, 2000. С.70.

[21] Жихалкина Н. Ф. Динамический подход к задаче кластеризации // Математические структуры и моделирование. 2000. Омск: ОмГУ. Вып. 5. С. 133-139.

[22] Жихалкина Н. Ф., Файзуллин Р. Т. Вариационная задача о поиске оптимальных (по цене) режимов работы нефтепровода // Четвертый сибирским конгресс по прикладной и индустриальной математике (ЙНПРИМ-00). Тезисы докладов. Часть II. Новосибирск. 2000. С. 32-33.

Подписано в печать 09.10.00. Формат 60 х 84 1/16. Печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 557.

Издательско-полиграфический отдел ОмГУ 6^4077, Омск-77, пр. Мира, 55-А, госуниверситет

Введение

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 ритмов, сильно чувствительных к выбору стартовой точки;

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