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

На правах рукописи

ЖАДАЫ Игорь Витальевич

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

Специальность 05.13.18 "Математическое моделирование, численные методы и комплексы программ"

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

1 4 АПР 2011

Москва 2011

4844006

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования "МАТИ" - Российском государственном технологическом университете имени К.Э.Циолковского

Научный руководитель:

доктор технических наук, профессор Беневоленский Сергей Борисович

Официальные оппоненты:

доктор технических наук, профессор Ватадзе Наталья Николаевна

кандидат технических наук, доцент Шилов Валерий Владимирович

Ведущая организация:

Институт системного анализа РАН

Защита состоится 2011 года в часов на

заседании диссертационного совета Д212.110.08 при Государственном образовательном учреждении высшего профессионального образования "МАТИ" - Российском государственном технологическом университете имени К.Э.Циолковского по адресу: 121552, Москва, ул. Оршанская, д.З, ауд. 612а.

С диссертацией можно ознакомиться в библиотеке Государственного образовательного учреждения высшего профессионального образования "МАТИ"- Российского государственного технологического университета имени К.Э. Циолковского.

Автореферат разослан

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

диссертационного совета Д212.110.08 кандидат физико-математических наук

Г

Спыну М.В.

Общая характеристика работы

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

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

На сегодняшний день существует значительное число различных подходов к решению задач глобальной оптимизации. Среди них можно отметить методы: случайного поиска; представления функций в виде суммы выпуклой и вогнутой составляющих; неравномерного покрытия; различные варианты метода ветвей и границ; методы, основанные на одномерной глобальной оптимизации и многие другие. Отечественные и зарубежные ученные, такие как Ю.Г. Евтушенко, С.Н. Пиявский, В.П. Булатов, Р.Г. Стронгин, Я.Д. Сергеев, А.Г. Жилинскас, A.C. Стрекаловский, Р. Хорст, X. Туй, А.М. Рубинов, И. Торн, П. Пардалос, К. Флоудас внесли значительный вклад в развитие теории и методов глобальной оптимизации. Стоит отдельно отметить задачи нахождения глобального экстремума липшицевой функции, как один из наиболее важных классов задач, рассматриваемых в глобальной оптимизации. В последние десятилетия для решения этих задач были предложены несколько эффективных численных методов, к примеру, A.M. Рубиновым, М. Андрамоновым, Б. Гловером был разработан метод секущих углов. Также были разработаны варианты метода секущих углов, предназначенные для решения задач с ограничениями, с использованием метода внешних штрафных функций. В перечисленных выше методах всегда возникает проблема выбора штрафных коэффициентов: при их увеличении возрастает константа Липшица, снижая тем самым эффективность большинства методов поиска глобального экстремума, в том числе и метода секущих углов.

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

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

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

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

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

Для достижения цели необходимо решить следующие задачи:

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

2. Предложить алгоритм реализации модифицированного метода поиска глобального экстремума на основе парадигмы распределенных вычислений.

3. Реализовать предложенный алгоритм модифицированного метода поиска глобального экстремума в программном комплексе.

4. Протестировать и применить разработанные алгоритмы на практических и прикладных задачах.

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

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

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

приводит к сокращению времени вычислений по сравнению с существующими аналогами в 1,3-1,5 раза.

3. С помощью разработанного программного комплекса проведена минимизация функционала качества для обменного и обгонного взаимодействия солитонов.

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на Международной научно-технической конференции «Международный форум молодых ученых и студентов» (Турция, 2004г.), Научной конференции «Современные наукоемкие технологии» (Испания, 2005г.), Юбилейной конференции РАЕ «Современные проблемы науки и образования» (Москва, 2005г.), Международных XXX, XXXI НТК «Гагаринские чтения» (Москва, 2006,2009 г.).

Структура работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и приложений. Изложение иллюстрируется 18 рисунками и И таблицами. Общий объем 122 страницы, список литературы 87 наименования.

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

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

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

Рассмотрим задачу отыскания глобального минимума многоэкстремальной функции Г(х), с заданной точностью е>0, где п -количество аргументов функции, определённой на п-мерном параллелепипеде РсЯ"

/. =min/(x), P = {xeRn :a<x<b). (1)

Здесь и ниже векторное неравенство х <, z означает, что х' z z' для всех 1 < j < и. Через X. обозначим множество решений задачи (1). Введем множество е -оптимальных (или приближенных) решений задачи (1):

х:={хеР:/(х)й/,+е} (2)

Очевидно, что X. с Xе, с Р. В большинстве практических задач достаточно найти по крайней мере одну точку xr е XI и вычислить значение fr=f(xr). Другими словами, надо с заданной точностью в определить величину глобального минимума от n-мерного вектора х и найти хотя бы одну точку хг , где это значение достигается.

В процессе расчетов будут использоваться векторы я,, А е R" и порождаемые ими прямоугольные параллелепипеды Р„ с гранями, параллельными координатным плоскостям: Pt - {х, gP:üi<xi <Ь:]. Центр с, параллелепипеда Pi и вектор его главной диагонали dj определяются по формулам:

с/ = 1/2(А/+а/), dj =bf -a{, \<j<n. (3)

Запись ^lim^...) подразумевает предельный процесс для

последовательности вложенных параллелепипедов

Рэ^ =>...=> ^ =>РМ э...такой, что lli/Ц»—>0. Здесь и ниже:

ikil=H*/-4

Предельную точку этой последовательности обозначим Рт. Обозначим д>(Р,) = min Дх). (4)

Предположим, что есть способ для каждого P\<zP определять нижнюю оценку значения функции <p(Pi), т.е. задана функция g(Pi), удовлетворяющая следующим двум условиям:

g(Pt)<<р(Р,) для каждого Р,еР, (5)

^im = 0 равномерно по Рю еР. (6)

Значения функции g(Pi) можно определять либо с помощью техники интервального анализа, либо используя какие-либо дополнительные предположения о классе, к которому принадлежит функция f. Пусть, например, функция f удовлетворяет условию Липшица с константой L, т.е. для любых х и z из Р выполнено неравенство:

|/(*)-/(г) |<£|ML (7)

Тогда для всех х е Pj имеем:

(8)

Поэтому можно взять

sW) = /(c,)-(£/2)|KL (9)

В процессе работы алгоритма будет строиться некоторая последовательность 5т={?|/гД-Л} параллелепипедов Ри

принадлежащих Р. В центрах этих параллелепипедов будут вычисляться значения минимизируемой функции. Пусть Мт={сис2,...,ст} последовательность центров параллелепипедов, принадлежащих Р. Назовём текущим рекордом величину:

Ля=тт(/(с,)) (10)

Любую точку с, из Ыт, удовлетворяющую условию назовём

рекордной точкой и обозначим хг. С каждым набором Р, свяжем набор

5,=(с,Д,й), где g,=g{Pд■ Совокупность наборов 5,- для всего набора

параллелепипедов Вт будем называть списком наборов и обозначать

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

Рассмотрим начальные операции:

1. Положить Р\=Р. 1. Задать е>0.

3. Вычислить центр С], главную диагональ с1], значение функции в центре исходного параллелепипеда Р\]{с\).

4. Вычислить значение функции ^Р) по формуле (9).

5. Положить в качестве рекордной точки хг значение центра исходного параллелепипеда Р. Если g > Дс{) - е, то закончить работу. Значение центра исходного параллелепипеда с\ - есть приближённое решение задачи. В противном случае начинается основной цикл поиска глобального экстремума.

Рассмотрим основной цикл (А-шаг):

6. Из текущего набора параллелепипедов Вт(к) выбрать тот параллелепипед Р!г для которого

7. В параллелепипеде Р, определить номер наибольшего ребра V.

= тах«//,

1<У£л

где I - координата ребра

8. Разделить на 2 части параллелепипед по 1:-ой координате, породив тем самым два новых параллелепипеда Р' и Р". Их центры и главные диагонали обозначим с', <!' и с", (1" соответственно.

9. Вычислить

Л = шт(/(С),/(С")). (11)

10. Если ЖД®, то положить = К. В качестве рекордной точки хг взять ту из точек с',с", в которой достигается минимум.

11 .Если то положить =

12.0пределить величины g' = §(?') и = ^Р") по формуле (9).

13.Исключить параллелепипед из набора Вт(к\ т.е. удалить набор из списка Б«. Включить в список два набора ¿^(с',^^') и Б"={с" положив 5" и = 5".

14.В полученном списке наборов провести для всех Б! следующую проверку: если выполнено

(12)

то Б; исключить из списка. Новый список наборов {5,1,5,2,... Д^} перенумеровать и обозначить {5/}1<,<р.

15. Пол ожить т=р. Если т= О, т.е. О, то закончить работу алгоритма. В противном случае перейти к п.6 основного цикла, положив к = к+1.

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

( Начало ]

/-^

/ ВаадЦоО« / СТСщим

Вычислить: а. А, 0(РО

/

Вычислить: Г(<?) и ({(О

Вьмиспить: цО*} и д(Р")

Рис. 1. Алгоритм метода половинных делений для однопроцессорной

машины

Одной из модификаций метода половинного деления для поиска глобального экстремума является модификация, основанная на разрезании п - мерного параллелепипеда по самому длинному ребру на 4 новых и-мерных параллелепипеда, вычислении их центров с„ диагоналей diy значений функций g(Pi), сравнении значений исследуемой функции в центрах новых полученных параллелепипедов.

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

Рассмотрим начальные операции:

1. Положить Р\=Р.

2. Задать £>0.

3. Вычислить центр С], главную диагональ di, значение функции в центре исходного параллелепипеда P\ßc\).

4. Вычислить значение функции g(P) по формуле (9)

5. Положить в качестве рекордной точки хг значение центра исходного параллелепипеда Р. Если g > fic{) - е, то закончить работу. Значение центра исходного параллелепипеда С\ - есть приближённое решение задачи. В противном случае начинается основной цикл поиска глобального экстремума.

Рассмотрим основной цикл (А-шаг):

6. Из текущего набора параллелепипедов ßm(t) выбрать тот параллелепипед Ps, для которого

gs = min g„

1 S<m

7. В параллелепипеде Ps определить номер наибольшего ребра t:

ds' = max d'.

ISrSi

8. Разделить параллелепипед по /-ой координате, породив тем самым два новых параллелепипеда Р' и Р". Их центры и главные диагонали обозначим с', d', с" и d" соответственно.

9. В параллелепипедах Р' и Р" определить номера наибольших рёбер ? и t". Каждый параллелепипед Р' и Р" разделить на 2 новых параллелепипеда плоскостью, перпендикулярной наибольшему ребру в этих параллелепипедах, тем самым породив 4 новых параллелепипедах Р'", Р"", Р'"" и Р""". Их центры и главные диагонали обозначим с'", d"\ с"", d"",c'"",d"",c"""nd......соответственно.

10. Вычислить:

R=mm {ЯПЛс"")Лс...........)}• (13)

11 .Если R<tfk\ то положить I^k+l)= R. В качестве рекордной точки хг взять ту из точек с'", с"", с'"", с""", в которой достигается минимум. Если R>R(k\ то положить R(k+l)=R(k>.

12.0пределить величины = ё"" = 8{Р""Х = £Р'"") и

ё......= 8ЦР......)■

13.Исключить параллелепипед Р.ч из набора Вт(т.е. удалить набор из списка Включить в список четыре набора

5""'=(с..........) и У.....=(с.....\сГ.....£""") положив

_глк о _гчш о _ сит О _ С"""

О , От+1 —О , От+2 — О , От+3 ~ О

14.В полученном списке наборов провести для всех 5, следующую проверку: если выполнено

&>#Ы)-е, (14)

то Б; исключить из списка. Новый список наборов {5,1,5д,...Др} перенумеровать и обозначить {5у} \%<р.

15.Положить т=р. Если т=0, т.е. то закончить работу алгоритма. В противном случае перейти к п.1 основного цикла, положив к = ¿+1.

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

Другой модификацией метода половинного деления для поиска глобального экстремума является модификация, основанная на использовании метода сопряжённых градиентов в качестве локального метода оптимизации. В результате работы этого метода получаем точку, которая является локальным экстремумом, и эта точка сравнивается с точкой, являющейся текущим рекордом. В случае, когда в точке, представляющей локальный экстремум, значение функции меньше значения функции в точке текущего рекорда, точка локального экстремума объявляется рекордом. Рассмотрение метода сопряженных градиентов целесообразно начать с рассмотрения более простого метода поиска экстремума функции - метода наискорейшего спуска. На рисунке 2 изображена траектория движения в точку минимума методом наискорейшего спуска. Суть этого метода: в начальной точке дг(0) вычисляется градиент, и движение осуществляется в направлении антиградиента до тех пор, пока уменьшается целевая функция; в точке, где функция перестает уменьшаться, опять вычисляется градиент, и спуск продолжается в новом направлении; процесс повторяется до достижения точки минимума.

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

Определение сопряженности формулируется следующим образом: два вектора х и у называют А-сопряженными (или сопряженными по отношению к матрице А) или А-ортогональными, если скалярное произведение х и Ау равно нулю, то есть:

хгАу = 0 . (15)

Сопряженность можно считать обобщением понятия ортогональности. Действительно, когда матрица А - единичная матрица, в соответствии с равенством (15), векторы х и у - ортогональны. Можно и иначе продемонстрировать взаимосвязь понятий ортогональности и сопряженности: мысленно растяните рисунок 3 таким образом, чтобы линии равного уровня из эллипсов превратились в окружности, при этом сопряженные направления станут просто ортогональными.

Сопряженные направления вычисляются с помощью процесса ортогонализации Грамма-Шмидта. Но для этого необходимо знать матрицу А, поэтому для большинства задач (например, обучение многослойных нейросетей) этот метод не годится. К счастью, существуют другие, итеративные способы вычисления сопряженного направления, самый известный - формула Флетчера-Ривса:

¿0+1) = Гр+1) + , (16)

где

г

о _ Г0+1) Г(1+1)

(О г(0 . (17)

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

Дх) = (1/2)хтАх-Ь7х I с , (18)

где х - неизвестный вектор, Ь - известный вектор, а А - известная, квадратная, симметричная, положительно-определенная матрица.

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

Можно привести еще одну формулу для определения сопряженного направления, формула Полака-Райбера (Ро1ак-ИлЫеге):

г

Г(0ГС0 (19)

Метод Флетчера-Ривса сходится, если начальная точка достаточно близка к требуемому минимуму, тогда как метод Полака-Райбера может в редких случаях бесконечно циклиться . Однако последний часто сходится быстрее первого метода. К счастью, сходимость метода Полака-Райбера может быть гарантирована выбором р = тах(р,0} Это эквивалентно рестарту алгорима по условию &<=0. Рестарт алгоритмической процедуры необходим, чтобы забыть последнее направление поиска и стартовать алгоритм заново в направлении скорейшего спуска.

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

1. Вычисляется антиградиент в произвольной точке Х(оу

4о)='со, = "/%)). (20)

2. Осуществляется спуск в вычисленном направлении пока функция уменьшается, иными словами, поиск а^, который минимизирует

/(*«+а(>А)). (21)

3. Переход в точку, найденную в предыдущем пункте

хс»и = + ааЛо. (22)

4. Вычисление антиградиента в этой точке

=-/'(х(.+1)). (23)

5. Вычисления по формуле 16 или 17. Чтобы осуществить рестарт алгоритма, то есть забыть последнее направление поиска и начать алгоритм заново в направлении скорейшего спуска, для формулы Флетчера-Ривса ^("«присваивается 0 через каждые п + 1 шагов, для формулы Полака-Райбера - Ам>= тах( А^п -0)

6. Вычисление нового сопряженного направления

4»« = л(1+ц + Ак+ч^со. (24)

Переход на пункт 2.

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

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

Разработанное программное обеспечение представляет собой комплекс различных модулей предназначенных для выполнения на однопроцессорной ЭВМ и для многопроцессорной ЭВМ.

Комплекс написан на языке Borland С++ 5.02. Комплекс для однопроцессорной ЭВМ состоит из 2 модулей globex.cpp и globsol.cpp.

В модуле globsol.cpp содержатся описания функций, которые вычисляют значения самой исходной функции, выводят дополнительную справку по использованию и назначению данной программы и "главная" функция, из которой производится вызов функций "конструктор", "деструктор" и функции, которая осуществляет поиск глобального экстремума. В "главной" функции проводится грамматический разбор параметров командной строки и происходит обращение к 3 основным функциям: void constructor(...), которая осуществляет начальные операции выше изложенного алгоритма, к функции int globmin(...), которая непосредственно проводит поиск глобального экстремума для заданного параллелепипеда Pi и функции void destructor(...), которая освобождает динамическую память, выделяемую под переменные и массивы структур. Таким образом все управление процессом поиска глобального экстремума лежит на этих трёх "основных" функциях.

В модуле globex.cpp находятся описания главной и основных функций, которые используются для поиска глобального экстремума. В функцию, реализующую поиск глобального экстремума int globmin(), в качестве одного из параметров передаётся значение функции, ранее достигнутое на исходном параллелепипеде F_best=f(ci). Работа функции начинается с проверки условия g(P;) > F_best - s для всех i>l. Те из параллелепипедов (BOX), которые удовлетворяют проверяемому условию, удаляются из набора рассматриваемых параллелепипедов. В дальнейшем в автореферате параллелепипед будет обозначаться как BOX. Далее определяется номер параллелепипеда (BOX) из рассматриваемого набора "неразрезанных" параллелепипедов с минимальным значением функции g(P). Далее этот параллелепипед мы разрезаем по самому длинному ребру на 2 новых параллелепипеда. Для этих параллелепипедов определяются "новые" границы, центры, наибольшие диагонали, значения функции g(P) и эти параллелепипеды добавляются к списку рассматриваемых параллелепипедов, с помощью функции markdel(). Увеличивается число построенных параллелепипедов. Определяются значения функции в центрах этих параллелепипедов и каждое значение сравнивается с уже имеющимся "лучшим" значением Fbest. Если оно оказывается меньшим, чем Fbest, то

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

Комплекс для многопроцессорной ЭВМ реализован в системе параллельного программирования на базе системы с передачей сообщений MPI.

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

Пусть имеется р процессоров. Один из них ( с номером нуль) назовём управляющим ("администратор"), а остальные ( с номерами 1,2,3, ... ,р-1 ) -рабочими процессорами. Опишем язык, который используется для обмена данными между управляющим и рабочими процессорами. Управляющий процессор может посылать рабочим процессорам следующие команды:

а) "f'- завершить работу (т.е закончить процесс вычислений),

б) "g (i)" - передать BOX с минимальным значением функции g(P) процессору с номером i,

в) "t G)" - принять BOX от рабочего процессора с номером j,

г) "w"- продолжить работу однопроцессорного метода половинного деления для функции многих переменных.

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

От рабочих процессоров управляющему передаются следующие данные: число имеющихся BOX, лучшее значение функции, достигнутое на этом рабочем процессоре, и минимальное значение функции g(P). Эта передача данных осуществляется через заданный промежуток времени с помощью неблокированного способа взаимодействия. Данный способ взаимодействия осуществляется с помощью функции MPIIRECV. Неблокированная функция указывает, что система может начинать писать данные в буфер приёма. После передачи параметров функции в систему, функция возвращает управление. После этого принимающий процесс не должен иметь доступ к буферу приёма, т.е. система не гарантирует в этом случае сохранность принимаемых данных. Для проверки завершения рассматриваемой операции используется функция MPITEST. Под завершением операции здесь понимается, что принимаемые данные находятся в буфере приёма.

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

а) принять BOX от рабочего процессора, у которого имеется более одного BOX, которые подлежат дальнейшему исследованию;

б) отдать BOX с наименьшим значением функции g(P) рабочему процессору, который не имеет BOX.

Если каждый из рабочих процессоров, ожидающих приказа от управляющего процессора, имеет ненулевое число BOX, подлежащих дальнейшему исследованию, то управляющий процессор даст каждому из них команду "w" (продолжить работу). Если все рабочие процессоры сообщили управляющему процессору, что у них работа завершена, то управляющий процессор отдаёт им всем команду "f ' (завершить работу).

Третья глава. В этой главе представлены результаты тестирования разработанного программного комплекса. Приводятся решения простейших тестовых задач, иллюстрирующие работу реализованного метода по отысканию глобального решения в многоэкстремальных задачах. Приводятся численные и временные результаты тестирования последовательной и параллельной работы программного комплекса. Вычислительные эксперименты проведены на компьютере Pentium4 2660 MHz, 512 SDRAM. В табл.1 представлены результаты тестирования разработанного программного комплекса на примере липшицевой функции. Липшицевой функции называется функция, которая удовлетворяет условию (формула 9). Далее будут введены следующие обозначения: г - точность, с которой ищется глобальный минимум, F - значение глобального минимума,

il - время поиска глобального минимума методом половинного деления, ¡2 - время поиска глобального минимума методом деления на 4 параллелепипеда,

- время поиска глобального минимума с использованием метода локального экстремума. Функция:

f,(xx,x2,x3) = F1(xl,x1,x,)+F2(x„x2,xi),

F, (х,, х2, x3)=cos(-5.22607 + 3.5432l)-cos(-0.58521-x2 -3.22080)-• cos(-7.98633-7.13696)

F2(*i,x2,*3) = cos(-7,38574-х, -5,79810)-cos(2,09302• дг2 -0,08203)-■ cos(2,91260-х3 +2,40845) ^ '

константа Липшица ¿=18,692 точность 0,1,0,01,0,001

ограничения: -1.0 <х, <1.0, -5.0 <*, <10.0, -35.0 <дг, <5.0, где/=1,2,3. Результаты приводятся в таблицах 1,2, 3.

Таблица 1

е ¥ сек сек сек

0.1 -1.98887420 0.26599 0.153 0.093999

0.01 -1.9895192 12.5939 9.9689 1.530999

0.001 -1.9895202 529.500 285.162 50.35900

Таблица 2

Е р 1], сек сек 1з, сек

0.1 -1.98914139189 29.76500 25.872 24.078

0.01 -1.98951768842 69.68767 60.891 56.750

0.001 -1.98952024084 987.7339 723.162 626.656

Таблица 3

е Б ^ сек 1г, сек 1з, сек

0.1 -1.9996560139164 419.39100 415.982 406.359

0.01 -1.9996560139167 709.21899 703.230 699.219

0.001 -1.9996560139169 2693.4840 2120.345 1997.156

Зависимость времени поиска глобального минимума от точности для данной исследуемой фунцкии (25) представлена на рис.5,6,7.

Рис. 4 Зависимость времени поиска глобального минимума от точности, Константа Липшица 18.692, -1.0 <х, < 1.0 /=1,2,3

Константа Липшица 18.692, -5.0 < Х1 < 10.0 ¡=1,2,3

Рис.6 Зависимость времени поиска глобального минимума от точности, Константа Липшица 18.692, -35.0 < х; < 5.0 ¡=1,2,3

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

Одной из актуальных практических задач в глобальной оптимизации является задача минимизации функционала качества для обменного и обгонного взаимодействия солитонов. Рассмотрим взаимодействие 2 солитонов с использованием уравнения Кортевега - де Фриса.

ди ди „ду „ —+и—+ /?—= 0 Ы дх &х

При Р~\, точное решение уравнения имеет вид:

(26)

Ф,0 = (4-4)*

Ах/г'2 — + АлЬТ2 — Д, Д,

(27)

где

АЛ .

амплитуды солитонов;

скорости солитонов,

=А =А

»72 = Х-И2/. з'"2 з

■ длительности.

Характер взаимодействия солитонов, определяется соотношением их

амлитуд. При значительном взаимодействии солитонов (^ ), меньший солитон сначала поглощается, а зачем излучается большим солитоном. Такое взаимодействие называется обгонным. При незначительном

— <2.62

взаимодействии солитонов (^ ) в течении всего периода взаимодействия присутствуют 2 волновых максимума. Такое взаимодействие называется обменным.

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

Расстояние Sm* между максимумами 2 солитонов при обменном взаимодействии удобно использовать в качестве единицы измерения расстояния между солитонами между солитонами. Так ^

г^ 1

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

J(f,J>) = hrWr~jf2))' ЛгМ) = МЛ (28)

В данном выражении & - вейвлетобразующая функция а под -анализируемый сигнал s(t). Оптимальному выбору базиса соответствовать минимальное значение данного функционала. В качестве решения данной модели в работе использовался вейвлет Морле. Вычисления производились с использованием метода половинных делений с использованием метода сопряженных градиентов с константой Липшица и точностью е =0.001 для обгонного и обменного взаимодействия при разных а. Результаты расчетов функционала качества для обгонного и обменного взаимодействия 2 солитонов представлены таблицах 4 и 5.

Таблица 4. Функционал качества При обгонном взаимодействии

солитонов при разложении по базисам вейвлетов Морле и Симлета.

Вейвлет а =5.6 а=3 а=1.7 а =1 а= 0

Вейвлет Морле 6.016281 6.38716 5.45012 6.09082 5.760133

Вейвлет Симлета 542.0000 65.30012 10.220012 5.170290 2.81023

Таблица 5. Функционал качества при обменном взаимодействии

солитонов при разложении по базисам вейвлетов Морле и Симлета.

Вейвлет а =5.6 а= 3 а=1.7 а= 1 а= 0

Вейвлет Морле 6.230012 6.86021 5.75102 6.67209 5.89205

Вейвлет Симлета 202.0000 82.70107 20.80006 6.39081 4.48901

При а>2 для обоих видов взаимодействия на основании результатов расчета оптимальным является вейвлет Морле. При а <2 для обоих видов взаимодействия оптимальным является вейвлет Симлета.

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

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

В таблицах 6 и 7 приводятся результаты "распараллеливания" (время в секундах) липшицевой функции методом половинного деления и методом локального спуска в методе половинного деления с использованием выше предложенного алгоритма. В процессе тестирования использовалась функция (25) при заданной константе Липшица 18.692 на интервале -35.0 < Х1 < 5.0, где 1=1,2,3, с использованием метода сопряжённых градиентов в методе половинного деления. Вычисления производились с использованием 4, 8 и 10 процессоров, чтобы показать эффективность применения параллельных вычислений для данной тестовой задачи. На рис.8 представлен график зависимости времени "распараллеливания" данной задачи от количества процессоров, с использованием метода локального спуска в методе половинных делений в параллельном алгоритме "управляющий - рабочий" без перераспределения задания.

Таблица 6. Константа Липшица 18.692, 8=0.1,0.01,0.001, п=1,4,8,10, -35.0 < х; < 5.0 ¿=1,2,3; метод половинного деления

8 П=1 п=4 п=8 п=10

0.1 419.39100 сек 108.766 сек 64.484 сек 45.844 сек

0.01 709.21899 сек 184.719 сек 117.500 сек 108.328 сек

0.001 2693.4840 сек 899.032 сек 679.524 сек 1320.192 сек

Таблица 7. Константа Липшица 18.692, 8=0.1,0.01,0.001, п=1,4,8,10, -35.0 < х; < 5.0 ¿=1,2,3; метод локального спуска (сопряжённых градиентов в методе половинных делений)

8 п=1 п=4 п=8 п=10

0.1 406.359 сек 98.765 сек 46.265 сек 40.328 сек

0.01 699.219 сек 154.578 сек 92.343 сек 63.766 сек

0.001 1997.156 сек 540.265 сек 503.782 сек 243.281 сек

Рис.7

Как видно из результатов задач, представленных в таблицах 6 и 7, видно, что с применением 4 процессоров время "распараллеливания" исходных задач заметно улучшается, по сравнению с использованием 1 процессора' Зато с использованием 8 и 10 процессоров, время улучшается не так быстро, по сравнению с использованием 4 процессоров. Такой факт

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

Выводы по работе

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

1. Предложен алгоритм модификации метода поиска глобального экстремума, основанная на разбиении на 2п - параллелепипедов (пег) и на использовании метода сопряженных градиентов.

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

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

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

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

Основные результаты диссертации изложены в следующих опубликованных работах:

1. Беневоленский Д.С., Жадан И.В., Спыну С.К. Использование параллельных вычислений при расчете метода половинных делений для глобальной оптимизации функции многих переменных. // Успехи современного естествознания, 2005. №10. С. 78-79.

2. Беневоленский Д.С., Жадан И.В., Спыну С.К. Виртуальная суперЭВМ на основе использования распределенных вычислений в локальной вычислительной сети для решения сложных научно-технических задач. // Успехи современного естествознания, 2005. №10. С. 77.

3. Беневоленский С.Б., Жадан В.Г., Жадан И.В., Истомина Н.Л., Спыну М.В., Спыну С.К. Принципы создания программного обеспечения для систем распределенного вычисления. II Успехи современного естествознания, 2005. №11. С. 27-28.

4. Жадан И.В, Спыну С.К., Станевичус A.A. Программное обеспечение для поиска глобального экстремума функции многих переменных Globex. Свидетельство об отраслевой регистрации разработки №5383, 16.11.05 г.

5. Беневоленский С.Б., Жадан В.Г., Жадан И.В., Спыну С.К. Применение технологии распределенных вычислений при решении задач методом половинных делений для глобальной оптимизации функции многих переменных. // Известия ВУЗов. Электроника, 2006. №3. С. 44-49. (журнал из списка ВАК).

6. Беневоленский Д.С., Жадан В.Г., Жадан И.В. Технология вычислений в распределенной среде при расчете метода половинных делений для глобальной оптимизации функции многих переменных // Нейрокомпьютеры, 2007.№5. С. 8-11. (журнал из списка ВАК).

7. Жадан И.В. Программное обеспечение для поиска глобального экстремума методом половинных делений при неравномерном покрытии. Свидетельство о государственной регистрации программы для ЭВМ №2009616922, 14.12.09 г.

8. Жадан И.В. Модификация метода половинных делений путем использования метода сопряженных градиентов // XXXV Гагаринские чтения. Научные труды Международной молодежной научной конференции в 8 томах. М.: МАТИ, 2009. Т.4. С.76-77

В авторской редакции Формат 60x84/16 Усл. печ. л. 1,0. Тираж 100 экз.

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР МЕТОДОВ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ, НЕДОСТАТКИ И ПЕРСПЕКТИВЫ РАЗВИТИЯ.

1.1 Задача глобальной оптимизации и практическая ценность

1.2 Обзор методов глобальной оптимизации. Преимущества и недостатки.

1.3 Задача поиска глобального экстремума функции многих переменных методов половинных делений и его недостатки.

Выводы по главе

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

2.1 Модификация метода половинных делений (деление на 2т параллелепипеда).

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

2.3 Общая схема работы программного комплекса для поиска глобального экстремума функции многих переменных (для однопроцессорной ЭВМ).

2.4 Архитектура систем параллельной обработки данных.

2.5 Алгоритм распараллеливания вычислительного процесса реализованного метода.

Выводы по главе 2.

ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПРОГРАММНОГО КОМПЛЕКСА И ЕГО ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ В АКУСТООПТИКЕ.

3.1 Особенности работы программного комплекса в среде параллельных вычислений.

3.2 Тестирование программного комплекса.

3.3 Задача о минимизации функционала качества для обгонного и обменного взаимодействия солитонов.

Выводы по главе 3.

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

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

На сегодняшний день существует значительное число различных подходов к решению задач глобальной оптимизации. Среди них можно отметить методы: случайного поиска; представления функций в виде суммы выпуклой и вогнутой составляющих; неравномерного покрытия; различные варианты метода ветвей и границ; методы, основанные на одномерной глобальной оптимизации и многие другие. Отечественные и зарубежные ученные, такие как Ю.Г. Евтушенко, С.Н. Пиявский, В.П. Булатов, Р.Г. Стронгин, Я.Д. Сергеев, А.Г. Жилинскас, A.C. Стрекаловский, Р. Хорст, X. Туй, A.M. Рубинов, И. Торн, П. Пардалос, К. Флоудас внесли значительный вклад в развитие теории и методов глобальной оптимизации.

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

Одним из наиболее плодотворных направлений глобальной оптимизации является идея неравномерных покрытий допустимого множества. В 1971 году опубликовал одну из первых научных работ Евтушенко Ю.Г. "Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке)" ЖВМ и МФ, 1971. 11 (6). С. 1390-1400, посвященную поиску глобального экстремума функций многих переменных с помощью неравномерных покрытий допустимого множества. Это направление в дальнейшем нашло плодотворное развитие. В статье Евтушенко Ю.Г. "Численный метод отыскания наилучших гарантированных оценок." ЖВМ и МФ, 1972. 12 (1). С. 89— 104, метод был перенесен на нахождение гарантированных оценок в многошаговых играх, в статье Евтушенко Ю.Г., Потапов М. А. "Методы решения многокритериальных задач."Доклады Академии наук СССР, 1986. Т. 291. N 1, С. 25-39.- на построение эпсилон-сети Паретовского множества. В статье Евтушенко Ю.Г., Ратькин В. А. "Метод половинных делений для глобальной оптимизации функции многих переменных." Техническая кибернетика, 1987, (1). С. 119-127, развивавшей метод неравномерных покрытий, был получен метод бисекций. Интерес к этому направлению значительно возрос в последнее время в связи с разработкой новых высокопроизводительных ЭВМ, основанных на параллельной и конвейерной организации расчётов.

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

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

Стоит отдельно отметить задачи нахождения глобального экстремума липшицевой функции, как один из наиболее важных классов задач, рассматриваемых в глобальной оптимизации. В последние десятилетия для решения этих задач были предложены несколько эффективных численных методов, в частности, Ю.Г.Евтушенко был разработан метод половинных делений; A.M. Рубиновым, М.Андрамоновым, Б.Гловером — метод секущих углов. С помощью метода половинных делений были разработаны также варианты модификации метода половинных делений, предназначенные для решения задач с ограничениями. В перечисленных выше методах всегда возникает проблема выбора штрафных коэффициентов: при их увеличении возрастает константа Липшица, снижая тем самым эффективность большинства методов поиска глобального экстремума, в том числе и метода половинных делений.

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

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

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

2. Предложить алгоритм реализации модифицированного метода поиска глобального экстремума на основе парадигмы распределенных вычислений.

3. Реализовать предложенный алгоритм модифицированного метода поиска глобального экстремума в программном комплексе.

4. Протестировать и применить разработанные алгоритмы на практических и прикладных задачах.

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

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

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

3. С помощью разработанного программного комплекса проведена минимизация, функционала качества для обменного и обгонного взаимодействия солитонов.

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на Международной научно-технической конференции «Международный форум молодых ученых и студентов» (Турция, 2004г.), Научной конференции «Современные наукоемкие технологии» (Испания, 2005г.), Юбилейной конференции РАЕ «Современные проблемы науки и образования» (Москва, 2005г.), Международных XXX, XXXI НТК «Гагаринские чтения» (Москва, 2006, 2009 г.).

ВЫВОДЫ ПО РАБОТЕ

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

1. Модифицирован метод поиска глобального экстремума путем разбиения на п - параллелепипедов (п кратное 2).

2. Предложена модификация метода половинных делений, основанная на использовании метода сопряженных градиентов.

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

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

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

1. Ю.Г.Евтушенко. Численный метод поиска глобального экстремума функции (перебор на неравномерной сетке) // Журнал вычисл. матем. и матем. физики, 1971. Т. 11. № 6. С. 1390-1403.

2. Пиявский С.А. Один алгоритм отыскания абсолютного экстемума функции // Журнал вычисл. матем. и матем. физики, 1972. Т. 12. № 4. С. 888-896.

3. Черноусько Ф. JI. Об оптимальном поиске экстремума унимодальных функций // Журнал вычислительной математики и математической физики. 1970, т. 10.

4. Черноусько Ф. Л. Об оптимальном поиске минимума выпуклых функций // Журнал вычислительной математики и математической физики. 1970, т. 10.

5. Кузнецов А. Г., Черноусько Ф. Л. Об оптимальном управлении, минимизирующем экстремум функции фазовых координат //Кибернетика. 1968. № 3. С. 50 -55.

6. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. М.: Наука, 1978.

7. Нефедов В.Н. Отыскание глобального максимума функции нескольких переменных на множестве, заданном ограничениями типа неравенств // Журнал вычисл. математики и матем. физики, 1987. Т. 27. № 1.С. 35-51.

8. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. М.: Наука, 1991.

9. Гергель В.П. Алгоритм глобального поиска, использующий производные // Динамика систем и оптимизация. Нижний Новгород: ННГУ, 1992. С. 161-178.

10. Я.Д.Сергеев, Д.Е.Квасов. Диагональные методы глобальной оптимизации. //ФИЗМАТЛИТ 2008. стр.9-14.

11. A.M.Rubinov and B.M.Glover. Increasing convex along rays functions with applications to global optimization. — Research Report 21/96, University of Ballarat, 1996.

12. Rinnoy Kan, A.H.G., Timmer, G.T. Stocactic global optimization methods //Mathematical programming. 39, 27-28, 1987.

13. Torn A. Global Optimization as a Combination of Global and Local Search // Turku, Abo Akademi University, HHAA A: 13, 1974.

14. Torn A., Viitanen S. Topographical Global Optimization // Floudas C.A., Pardalos P.M. (eds): Recent Advances in Global Optimization. Princeton University Press, 384-398, 1992.

15. T6rn A., Viitanen S. Topographical Global Optimization Using Pre-Sampled Points // Journal of Global Optimization, Vol 5, No 3, 267-276, 1994.

16. Evtushenko Yu. G., Potapov M. A., Korotkich V. V. Recent Advances in Global Optimization // Prinston, Princeton University Press, 274-297, 1992.

17. Moore R. Interval Analysis // New Jersey, Prentice-Hall, 1966.

18. Nemhauster G.L., Pruul E.A., Rushmeier R.A. Branch-and-bound and Parallel Computation: a Historical Note // Oper. Res. Let., 7, 65-69, 1988.

19. Gomez S., Levy A.V. The Tunneling Method Applied to Global Optimization // SIAM, Numerical Optimization (Boggs, P.T., ed.), 213244, 1985.

20. Metropolis N., Rosenbluth A., Rosenbluth M., Teller A., Teller E. Equation of State Calculations by Fast Computing Machines // J. Chem. Phys. Vol. 21, No. 6, 1087-1092, 1953.

21. Aarts E.H.L., van Laarhoven PJ.M. Simulated Annealing: Theory and Applications // London, Kluwer, 1987.

22. АИ M., Storey C. Aspiration Based Simulated Annealing Algorithm // J. of Global Optimization 11, 181-191, 1996.

23. Hamma В., Viitanen S., A. Torn. Parallel Continuous Simulated Annealing for Global Optimization // Optimization Methods and Software, Vol. 13, №2, 93-116, 2000.

24. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs (3rd Edn.) // New York, Springer-Verlag, 1996.

25. Price W.L. A Controlled Random Search Procedure for Global Optimization // The Computer Journal, 20, 367-370, 1977.

26. AH M., Torn A., Viitanen S. A Numerical Comparison of Some Modified Controlled Random Search Algorithms // J. of Global Optimization 11, 377-385, 1997.

27. Rubinov A. Andramonov M. Lipschitz programming via increasing convex-along-rays functions // Optimization Methods and Software, 1999. V. 10. P. 763-781.

28. С.С.Кутателадзе, А.М.Рубинов. Двойственность Минковского и ее приложения. ~ Новосибирск: Наука, 1976.

29. Pallachke D., Rolewicz S. Foundations of Mathematical Optimization (Convex Analysis without Linearity). Kluwer Academic Publishers, Dordrecht, 1997.

30. Singer I. Abstract Convex Analysis. New York: Willey \& Sons, 1997.

31. A.M.Rubinov. Abstract Convexity and Global Optimization. Dordrecht, Kluwer Academic Publishers, 2000.

32. J. Kelley. The cutting plane method for solving convex programs // SIAM Journal, 1960. V. 8, № 4. P. 703-712.

33. Анциферов Е.Г., Ащепков Л.Е., Булатов В.П. Методы оптимизации и их приложения. 4.1. Математическое программирование. Новосибирск: Наука, 1990.

34. Хамисов О.В. Глобальная оптимизация функций с вогнутой минорантой // Журнал вычисл. математики и матем. физики. 2004. Т. 44. №9. С. 1552-1563.

35. А.Р.Ершов, О.В.Хамисов. Автоматическая глобальная оптимизация //. Дискретный анализ и исследование операций. 2004. Серия 2. T.l 1, № 2. С 45-68.

36. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

37. Гроссман К., Каплан А.А. Нелинейное программирование на основе без условной минимизации. Новосибирск: Наука, 1981.

38. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

39. D.D. Morrison, Optimization by least squares // SIAM J. Numer. Analysis, 1968. № 5. P. 83-88.

40. J. Kowalik, M.R. Osborn and D.M. Ryan, A new method for constrained optimization problems // Operat. Res., 1969. V. 17. P. 973-989.

41. Докл. АН СССР. 1967. Т.-173, №-4. С.-748-751. 46.Евтушенко Ю.Г., Жадан В.Г. Точные вспомогательные функции в задачах оптимизации // Журнал вычисл. матем. и матем. физики,1990. Т. 30. № 1. С.31-42.

42. Evtushenko Yu.G., Rubinov A.M. and Zhadan V.G. General Lagrangetype functions in constrained global optimization. Part II: Exact auxiliary functions // Optimization ' 48.Methods and Software, 2002. Vol. 16, № 1-4. P. 231-256.

43. A.M.Bagirov and A.M.Rubinov. Global minimization of increasing positively homogeneous functions over the unit simplex, Research Report 99/37, University of Ballarat, 1999.

44. Gourdine E., Jaumard В., Ellaia R. Global optimization of Holder functions // J. Global Optim. 1996. V.8, N 4. P.323-348.

45. Сухарев А.Г. Минимаксные алгоритмы в задачах численного анализа. М.: Наука, 1989.

46. Hansen P., Jaumard В., Lipschitz optimization // Handbook of global optimization. Dordrecht: Kluwer Acad. Publ., 1995. P. 407-494

47. Horst R., Nast M., Thoai N.Y. New LP bound in multivariable Lipschitz optimization: theory and applications // J. Optim. Theory Appl. 1995. V. 86, №2. P. 369-388

48. Pinter J. Global optimization in action. Dordrecht: Kluwer Acad. Publ., 1996.

49. Sergeev Ya.D. An one-dimensional deterministic global optimization algorithm. // Журн. вычисл. математики и матем. физики. 1995. Т. 35, №5. Р. 705-717

50. Wood G.R., Zhang В.Р. Estimation of the Lipschitz constant of a function // J. Global Optim. 1996. V.8, N 1. P. 91-103.

51. Baritompa W. Accelerations for a variety of global optimization methods // J. Global Optim. 1994. V.4, N 1. P. 37-45.

52. Breiman L., Cutler A. A deterministic algorithm for global optimization // Math. Program. 1993. V. 58, N 2, P. 179-199.

53. Gergel V.P. A global optimization algorithm for multivariable functions with Lipschitzian first derivatives // J. Global Optim. 1997. V.10, N 3. P. 257-281.

54. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

55. Сухарев А.Г., Подобедов В.Е., Алгоритм поиска глобального максимума функции нескольких переменных. // Вычислительные комплексы и моделирование сложных систем. М.: МГУ, 1989. С. 124-134.

56. Брайсон А., Хо Ю-Ши. Прикладная теория оптимального управления

57. Шнитман В., Отказоустойчивые компьютеры компании Stratus // Открытые Системы № 1 1998

58. Дубова Н., Суперкомпьютеры nCube // Открытые Системы № 2 1995

59. Макстеник М., Сравнение сетевых архитектур // Сети № 2 1997

60. Французов Д., Оценка производительности вычислительных систем // Открытые Системы № 2 1996

61. Французов Д., Оценка производительности суперкомпьютеров // Открытые Системы № 6 19956 8. Воеводин В.В., Параллельная обработка данных, htlp://w\vw.parallel.ru/wv/

62. Комолкин A.B., Немнюгин С.А., Программирование для высокопроизводительных ЭВМ, http://vvww.hpc.nw.ru/COURSES/HPC/

63. Кркжов В.А., Операционные системы распределенных вычислительных систем (распределенные ОС), http://www.parallel.ru/krukov/

64. Ian Foster, Designing and Building Parallel Programs, http://rsusu 1 .rnd.runnet.ru/tutor/design/dbpp/text/book.html

65. Booth S., MacDonald N., Perfomance Optimization, http://www.hpc.nw.ru/COURSES/

66. Спыну С.К. Поиск глобального экстремума с использованием параллельных вычислений. Сб. трудов Международной НТК «XXX Гагаринские чтения», (Москва, 6-10 апреля 2004 г.). — М.: «МАТИ» -РГТУ им. К.Э.Циолковского, 2004, т.5, с.101

67. Спыну С.К. Поиск глобального экстремума с использованием параллельных вычислений. «Успехи современного естествознания» 2004, №7, с. 94,94.

68. Беневоленский Д.С., Жадан И.В., Спыну С.К. Использование параллельных вычислений при расчете метода половинных делений для глобальной оптимизации функции многих переменных. «Успехи современного естествознания» 2005, №7, с. 94,94.

69. Беневоленский Д.С., Жадан И.В., Спыну С.К. Виртуальная суперЭВМ на основе использования распределенных вычислений в локальной вычислительной сети для решения сложных научно-технических задач. «Успехи современного естествознания» 2005, №7, с. 94,94.

70. Беневоленский С.Б., Жадан В.Г., Жадан И.В., Истомина Н.Л., Спыну М.В., Спыну С.К. Принципы создания программного обеспечения для систем распределенного вычисления. «Успехи современного естествознания» 2005, №7, с. 94,94.

71. Свидетельство об отраслевой регистрации разработки №5383 «Программное обеспечение для поиска глобального экстремума функции многих переменных С1оЬех», Дата регистрации 16 ноября 2005г.

72. Беневоленский Д.С., Жадан В.Г., Жадан И.В. Технология вычислений в распределенной среде при расчете метода половинных делений для глобальной оптимизации функции многих переменных // Нейрокомпьютеры, 2007, 5, С. 8-11.

73. Свидетельство о государственной регистрации программы для ЭВМ №2009616922 «Программное обеспечение для поиска глобального экстремума методом половинных делений при неравномерном покрытии», Дата регистрации 14 декабря 2009г.

74. Беневоленский С.Б., Жадан И.В. Модификация метода половинных делений путем использования метода сопряженных градиентов. XXXV Гагаринские чтения: материалы Международной молодежной научной конференции в 8 томах, Москва, 2009, т.4, с. 7677.

75. MPI: The Message Passing Interface http://parallel.ru/tech/techdev/mpi.html.

76. Александр Каленюк, "Нестандартные алгоритмы сортировки".

77. Подбельский В.В. Язык Си++. М.: Финансы и статистика, 2000. -560с.

78. В. В. Воеводин, Вл. В. Воеводин, Параллельные вычисления. 2002, с.600

79. Корнеев В. В., Параллельные вычислительные системы. 1999, с.320

80. В.Ф.Кравченко, О.В.Лазаренко, В.И.Пустовойт, Л.Ф.Черногор. Вейвлет -анализ поведения солитонов при обгонном и обменном взаимодействиях. Доклады академии наук, 2007, том 412, №2 с. 179184.

81. Кравченко В.Ф., Пустовойт В.И., Чуриков Д.В. Цифровая обработка нелинейных сигналов на основе преобразования Кравченко-Котельникова Вигнера. Успехи современной радиоэлектроники. Зарубежная радиоэлектроника. 2007, №8, с.67-71.