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

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

Гергель Александр Викторович

АДАПТИВНЫЕ МНОГОШАГОВЫЕ МЕТОДЫ И ПРОГРАММНЫЕ СРЕДСТВА ПАРАЛЛЕЛЬНОЙ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ

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

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

Нижний Новгород - 2010

Работа выполнена в Нижегородском государственном университете им Н.И. Лобачевского на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики

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

к.ф.-м.н., доцент Гришагин В.А.

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

д.т.н., проф. Бухановский A.B. к.ф.-м.н., доцент Коротченко А.Г

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

Научно-исследовательский вычислительный центр Московского государственного университета им. М.В. Ломоносова

Защита диссертации состоится " 2-> 2010 г. в (С ко ча-

сов на заседании диссертационного совета Д 212.166.13 при ННГУ им. Н.И. Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, 23, корп. 2, конференц-зал.

С диссертацией можно ознакомиться в фундаментальной библиотеке ННГУ им. Н.И. Лобачевского

Автореферат разослан " (2 " ¿ю^ 2010 г.

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

диссертационного совета Д 212.166.13 / [)

к. ф.м.н., доцент - & Савельев В.П.

российская государственная

библиотека

20 П

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

Научная новизна. При выполнении работы получены следующие основные новые результаты:

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

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

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

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

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

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

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

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

• Программная система С1ориСот для параллельного решения сложных вычислительно-трудоемких задач многомерной многоэкстремальной оптимизации.

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

Внедрение результатов работы. Результаты работы нашли свое применение при выполнении проектов, выполняемых на факультете ВМК при поддержке Российского фонда фундаментальных исследований (проекты № 04-01-00455, № 07-01-00467-а) и Совета по грантам Президента Российской Федерации по государственной поддержке ведущих научных школ РФ (грант № НШ - 4694.2008.9), совместного научно-исследовательского проекта РФФИ и Нидерландской организации по научным исследованиям NWO 047.016.014. Результаты работы используются также в учебном процессе факультета ВМК ННГУ при чтении курсов "Модели и методы многоэкстремальной оптимизации", "Системы поддержки принятия решений"

Апробация работы. Результаты работы докладывались на Международных конференциях "Высокопроизводительные вычисления на кластерных системах" (Нижний Новгород, 2007, Казань, 2008, Владимир, 2009), Всероссийской конференции "Научный сервис в сети Интернет" (Новороссийск, 2009), научно-технических конференциях "Технологии Майкрософт в теории и практике программирования" (Нижний Новгород, 2007-2008, 2010), на научных конференциях и семинарах Нижегородского государственного университета.

Публикации. Основное содержание диссертации изложено в работах [1]-[9].

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

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы из 198 наименований. Основной печатный текст занимает 138 страницы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В § 1.1 излагается постановка задачи многомерной многоэкстремальной оптимизации, которая может быть определена как проблема поиска наименьшего значения действительной функции Ц){у)

ф*) = min{ ф): ycD, gj(y)<0, 1 <j<m} (1)

в области поиска D, представляющей собой некоторый гиперпараллелепипед N-мерного евклидова пространства

D = {ycRN: а,<у,< bh 1 <i<N}, (2)

где a, b &Rn есть заданные векторы.

Точка у* из (1) обычно называется глобально-оптимальной точкой или глобально-оптимальным решением. При этом функцию ср{у) называют функцией цели, или целевой (оптимизируемой, минимизируемой) функцией, а действительные функции gj(y) <0, 1 < j <т, - ограничениями задачи.

Область D называют областью поиска. Точки из области поиска, удовлетворяющие всем ограничениям, называются допустимыми точками или допустимыми решениями. Множество

Q = {yeD: gj(y)<0, 1 <j<m }, (3)

всех таких точек называют допустимой областью.

Численное решение задачи (1) сводится к построению оценки у* е Q, отвечающей тому или иному понятию близости к точке у* на основе конечного числа к значений функционалов задачи, вычисленных в точках области D.

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

— предполагается, что целевая функция (р (в дальнейшем обозначаемая также £,„+|) и левые части ограничений gJ^y),\<j<m, удовлетворяют условию Липшица с соответствующими константами Ьр\<]<т+1.

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

осуществляться последовательно: =<?*(**)

с учетом всей поисковой информации, полученной в процессе вычислений

(4)

где /, !</<£, есть точки испытаний, 1 </'<£, представляют значения целевой функции в точках У, а (§/,..., gm'), 1 </<&, обозначают значения ограничений в этих точках.

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

(5)

шт <р(7) = шт ... гат ср(У1 Уи).

уеО >'|<ЧП|А] >Фл'АУ]

Другим общим способом редукции размерности основывается на известном фундаментальном свойстве, согласно которому Л^-мерный гиперпараллелепипед О из (2) и отрезок вещественной оси [0,1] вещественной оси являются равномощными множествами и отрезок [0,1] может быть однозначно и непрерывно отображен на гиперпараллелепипед О. Отображения такого рода обычно называют развертками или кривыми Пеано.

Пусть ;;(х), ,ге[0,1] есть кривая Пеано и функция (1) непре-

рывна. Тогда

<рО<лг*))=тт{ ф(х)): хе[0,1],&О(х))<0,1</<ш}. (6)

Приведенные схемы редукции размерности (5)-{6) открывают широкое направление по построению многомерных методов многоэкстре-

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

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

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

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

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

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

— Построение отдельных оценок констант Липшица оптимизируемых функций для разных подобластей области поиска.

В § 2.1 изложена схема адаптивного глобального метода с использованием производных.

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

В § 2.2 излагаются методы многоэкстремальной оптимизации с адаптивными оценками константы Липшица, в которых оценки константы Липшица формируются для каждого поискового интервала в отдельности. Общая схема оценки константы Липшица иг,- интервала (х,1<Кк, предложенная Я.Д. Сергеевым, определяется в соответствии со следующими выражениями:

= г Mi, Mi = max { ц' ц" Цо },

(7)

где

//' = max {

zi~zi-1

4х i -x-_l):j = i-l,i,i + l},

(8)

/л" - M(Xj - xf-_j) / d max,

(9)

M = max -

-/-1

]<i<k Xj -

d max = max (x, - )

1 <i<k

Здесь Zj суть значения целевой функции в точках jc„ 1 <i<k.

Параметр цо отражает предположение о том, что функция (fix) не является константой на интервале [а,Ь].

Величина М является оценкой глобальной константы Липшица L на всем интервале поиска [а,Ь]. Величины М,-, 1 <i<k, являются оценками локальных констант Липшица на интервалах ,х,).

В приведенной схеме локальная //', из (8) и глобальная //", из (9) составляющие локальной оценки константы Липшица могут рассматриваться как два разных противоречивых критерия. Предпочтение одного критерия (например, локальной составляющей) приводит к более быстрому завершению работы алгоритма глобального поиска, однако, здесь возможна потеря решения из-за оценки константы Липшица с недостатком. Предпочтение другого критерия (глобальной составляющей) может привести к более продолжительной работе алгоритма глобального поиска из-за оценки константы Липшица с избытком. Как результат, для получения некоторого компромиссного (промежуточного) значения константы Липшица может быть задействована общая методика по-

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

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

1 г-1 (Ю)

/77, =гЛ4 тах { — //',•+-/Л, Но },

г г

где величины //,, /Л, /¿о определяются соотношениями (7)-(9), г>1 — заданный коэффициент (параметр алгоритма).

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

Другим разработанным в диссертации способом построения оценок является использование интервальной схемы построения оценок константы Липшица. Область значений [0,М\ оценок константы Липшица можно представить в виде набора диапазонов

{(Ъ-1,7/)}'- Щ = 0, 77, = М,

где т есть количество диапазонов.

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

т, = гМ„ М = Лр (И)

где у определяется из соотношения ¡1, е (//,. | , ¡1, из (8).

Еще одна из схем оценки отдельных констант Липшица для разных подобластей области поиска разработана при помощи отслеживания участков области поиска, в которых происходит резкое изменение поведения минимизируемой функции. В рамках данной схемы множество интервалов (хм,х,), 1 </<£, разбивается на непересекающиеся подмножества, определяемые отрезками номеров

где 1 <_/'<.?, есть множество номеров интервалов, образующих подмножество с индексом]. При этом

/,= { ;},...,//+ }, 1 <_/'<£, г'о = 0, ^ + ^ = £,¿, + ^ = ¿,+1.

Далее для каждого подмножества интервалов можно определить оценку константы Липшица

М1 = шах {/и]: I е /;}, 1<у<5.

С учетом введенных обозначений разделение множества интервалов (л',-_| д",). 1 <1<к, на подмножества с разными оценками константы Липшица определяется следующими соотношениями:

где 1 <1<к, из (9), а 5 есть параметр данной вычислительной схемы.

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

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

Решение многомерной многоэкстремальной задачи оптимизации согласно (14) сводится к решению одномерной задачи:

V], 1 < ] < Б ц\! М' > / е I

)'

(12)

(13)

ПИП <р(у)= ЩШ хтп ср{ух уИ)

уеО >1ф|.Ч .»Ф/У.Ы

(14)

*

(15)

Ум е1я;+1 >°ж \

<Рк(У\>-->Уи) = <Р(У\>->Ум)

(17)

Приводимая в (15) одномерная функция <Р\ (>"1) строится по общему рекуррентному правилу — для вычисления значения <Р\ (7]) для некоторого заданного значения переменной = ух необходимо выполнить минимизацию одномерной функции

Фг(Уг) = <Рг(У\>Уг)

по у2, далее для вычисления значения (У2) в точке >>2 = Уг необходимо провести минимизацию функции

Ръ(Уъ) = <Ръ(У\, Уг^Уъ) по^; и т.д.

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

В § 3.2 рассматривается новая адаптивная многошаговая схема редукции размерности, согласно которой устраняется принцип строгого соподчинения решения порождаемых в рамках многошаговой схемы одномерных функций •(>•,•), 1 < / < Лг все эти задачи предлагается

решать совместно.

В рамках нового подхода:

— для вычисления значения функции уровня г, 1</<ЛГ,, порождается новая задача уровня г'+1, выполняется только одна итерация метода оптимизации для ее решения, после чего новая порожденная задача включается в множество уже имеющихся задач, подлежащих решению;

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

итерация метода оптимизации; выбор задачи для выполнения итерации осуществляется в соответствии с тем или иным правилом выбора задач;

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

Для алгоритмического описания адаптивной схемы дается определение правил:

— инициализации глобального поиска,

— создания новой задачи,

— вычисления значения функции,

— выполнения итерации глобального поиска.

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

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

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

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

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

В § 3.3 представлена форма характеристически-представимых алгоритмов глобального поиска, в рамках которой могут быть конкретизированы общие правила адаптивной многошаговой схемы:

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

— правило выбора точки начальной итерации поиска,

— правило выбора точки очередной итерации поиска,

— правило получения текущей оценки решения оптимизационной задачи,

— правило условия остановки.

В § 3.4 на основе предложенной алгоритмической схемы могут быть построены:

— базовый многомерный многошаговый алгоритм глобального поиска,

— многомерный многошаговый индексный алгоритм глобального поиска,

— многомерный многошаговый алгоритм глобального поиска с адаптивной локальной настройкой,

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

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

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

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

Теорема 1. (теорема 3.2 в 3 главе диссертации). Пусть функция <Р(У)>У е & > из (1) является липшицевой с константой К. Тогда «приближенные» функции (/л(гл), 1 < / < N, построенные в соответствии с

адаптивной многошаговой схемой при выполнении условия устойчивости

VI, 1 < I < N, Уу;, V,"^ 3к >к0: ум (к, V,') - улм (к, V,*)

(19)

также являются липшицевыми с константами Кь где:

Теорема 2 (теорема 3.4 в 3 главе диссертации). Для информационно-статистических алгоритмов в рамках адаптивной многошаговой схемы выполняется условие устойчивости (19).

Теорема 3 (теорема 3.6 в 3 главе диссертации). Пусть точка у есть предельная точка последовательности {ук}, порождаемой информаци-оино-статистическим алгоритмом глобального поиска при использовании адаптивной многошаговой схемы редукции размерности для минимизации липшицевой с константой К функции (р(у), у&й. Тогда данная точка у является точкой глобального минимума функции если начиная с некоторого шага ки для оценки константы Липшица т справедливо неравенство

т > 2 К,

а погрешность вычисления значений функции является ограниченной. Кроме того, любая другая предельная точка у' последовательности {ук} также является точкой глобального минимума функции <р(у).

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

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

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

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

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

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

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

В общем виде разработанная схема состоит в следующем. Пусть Ь есть множество номеров задач семейства из (18):

¿={1,2, ,/}, (20)

и пусть для проведения вычислений имеется р> 1 процессоров. Далее задачи семейства Е/ распределяются между процессорами — данное распределение фиксируется при помощи соответствующего разделения множества Ь на подмножества:

П= { Л\, к2, ,яр), (21)

Щ = {Л '-Ь е I, 1<5< /,-}, 1 <1<р,

V В} г'ещ, V Ц => ={0}

где щ, 1 <1<р, есть множество задач, распределенных для решения на процессоре/, 1 <л<р.

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

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

Пусть номера терминальных задач (одномерных задач, соответствующих последней варьируемой переменной^) образуют множество:

Терминальные задачи распределяются между процессорами; выбранное распределение фиксируется по аналогии с (22):

щ= Ь \ ¿Л', л^ = {е £л', 1 <5</,}, 1 Я<р,

V /е£ 3у /ел;, V => яр\щ ={0}.

В (23) каждое подмножество щ, 1<г<р, определяет список терминальных задач, распределенных для решения на процессоре /, 1 <\<р. Подмножество ль содержит номера всех структурных задач, обработку которых может осуществлять дополнительный процессор. Подобное распределение задач обеспечивает систематический характер информационных взаимодействий между процессорами — процессоры с терминальными задачами пересылают получаемые оценки минимальных значений исходной оптимизируемой задачи только управляющему процессору, а управляющий процессор занимается обработкой только структурных задач без выполнения трудоемких вычислений значений функционалов исходной решаемой задачи оптимизации.

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

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

(22)

Гр = { Щ, Л|, 712, , Лр },

(23)

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

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

В пятой главе представлено описание программного комплекса глобальной оптимизации 01орйСот, в котором реализованы разработанные в рамках диссертационной работы методы многоэкстремальной оптимизации.

В § 5.1 приводится общая характеристика комплекса глобальной оптимизации ОориСот. Разработанный комплекс глобальной оптимизации 01орйСот предназначен для параллельного решения многоэкстремальных многомерных задач оптимизации при наличии нелинейных ограничений на многопроцессорных вычислительных системах.

В состав комплекса ИорйСош входят три системы оптимизации:

— Система 01ориСот-1, ориентированная на решение задач одномерной многоэкстремальной оптимизации. Данная система предназначена для проведения вычислительных экспериментов с целью оценки эффективности одномерных алгоритмов глобального поиска,

— Система С1орйСот-2, ориентированная на решение задач двухмерной многоэкстремальной оптимизации. Данная система предназначена для проведения вычислительных экспериментов с целью исследования адаптивной многошаговой схемы редукции размерности,

— Система 01орйСот+ является основной в комплексе и ориентирована на параллельное решение задач многомерной многоэкстремальной оптимизации.

В § 5.2 представлено описание системы С1ориСош-1, алгоритмическую основу которой составляют информационно-статистические алгоритмы многоэкстремальной оптимизации, представленные в характеристической форме.

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

Система С1ор1лСот-1 использовалась для проведения вычислительных экспериментов с методами одномерной глобальной оптимизации в главе 2.

Для оценки эффективности применения адаптивной многошаговой схемы редукции размерности для построения многомерных многоэкс-трсмальных методов оптимизации используется система С1орНСот-2, описание которой представлено в § 5.3.

Алгоритмическую основу системы составляют информационно-статистические алгоритмы многоэкстремальной оптимизации, представленные в главах 1-2 и реализованные в системе 01орйСот-1. Для применения одномерных методов оптимизации для решения многомерных оптимизационных задач используется редукция размерности. В системе 01ор11Сот-2 реализованы:

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

— многошаговая схема редукция размерности,

— адаптивная многошаговая схема редукция размерности.

Система С1ориСот-2 использовалась для проведения вычислительных

экспериментов с методами одномерной глобальной оптимизации в Главе 3.

В § 5.4 представлено:

— описание системы многомерной многоэкстремальной оптимизации 01ор1тСот+, структура которой представлена на рис 1.

Рис. 1. Структура системы многоэкстремальной оптимизации 01орйСот+,

— описание и назначение каждого из структурных элементов системы.

В § 5.5 представлены результаты вычислительных экспериментов для системы 01ориСот+.

Основные результаты работы

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

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

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

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

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

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

7. Разработана программная система 01орйСош+ для параллельного решения сложных вычислительно-трудоемких задач многомерной многоэкстремальной оптимизации.

Публикации по теме диссертационной работы

Публикации в научных журналах, рекомендованные ВАК.

1. Гергель А. В. Адаптивные параллельные вычисления для многомерной многоэкстремальной оптимизации // Приборостроение. Изд. СПбГУ ИТМО, 2009. Т. 52. № 10. С. 74-80.

2. Гергель A.B. Многомерная многоэкстремальная оптимизация на основе адаптивной многошаговой редукции размерности // Вестник ННГУ Математическое моделирование и оптимальное управление. Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2010. Вып. 1. С.163-170.

Остальные публикации по теме диссертационной работы:

3. Гергель A.B. О новом методе решения многоэкстремальных многомерных задач оптимизации // Шестая нижегородская сессия молодых ученых. Тез. докл. - Нижний Новгород. 2001. С. 87-92.

4. Гергель В.П. Гришагин В.А. Гергель A.B. Адаптивные параллельные вычисления для многомерной многоэкстремальной оптимизации. Труды Всероссийской суперкомпьютерной конференции (21-26 сентября 2009 г., г. Новороссийск). - М.: Изд-во МГУ, 2009. С. 417-421.

5. Гергель А.В, Гнатюк Д.В. Адаптивные параллельные алгоритмы для многомерной многоэкстремальной оптимизации // "Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2009). Изд. ВладГУ, 2009. С. 92-96.

6. Гергель A.B. Применение централизованной схемы параллельного глобального поиска для адаптивной многошаговой схемы редукции размерности // Материалы конференции «Технологии Microsoft в теории и практике программирования». Нижний Новгород, 2010. С. 64—66.

7. Гергель А.В, Гнатюк Д.В. Модификация адаптивных параллельных алгоритмов для многомерной многоэкстремальной оптимизации. Труды Всероссийской суперкомпьютерной конференции (20-25 сентября 2010 г., г. Новороссийск). - М.: Изд-во МГУ, 2010. С. 178-180.

8. Гергель A.B. Параллельные методы многоэкстремальной оптимизации с адаптивными решающими правилами // Материалы конференции "Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2010). Изд. ПГТУ, 2010. С. 152-159.

9. Гергель А.В, Гнатюк Д.В. Адаптивные параллельные алгоритмы для многомерной многоэкстремальной оптимизации // Материалы конференции "Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2010). Изд. ПГТУ, 2010. С. 160-165.

Подписано к печати 12.11.2010 г. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Гарнитура Times. Усл. печ. л. 1. Тираж 100 экз. Заказ 698.

Отпечатано в Центре цифровой печати Нижегородского госуниверситета им. Н.И. Лобачевского 603000, Н. Новгород, ул. Б. Покровская, 37.

и 1 "

2010202845

Введение.-.

1. Модели и методы многомерной многоэкстремальной оптимизации.

1.1. Постановка задачи многомерной многоэкстремальной оптимизации.

1.2. Краткий обзор подходов к численному решению задач многомерной многоэкстремальной оптимизации.

1.3. Информационно-статистические алгоритмы глобального поиска.

2. Методы многоэкстремальной оптимизации с адаптивными решающими правилами.

2.1. Методы многоэкстремальной оптимизации с использованием производных.

2.2. Методы многоэкстремальной оптимизации с адаптивными оценками константами Липшица.

2.2.1. Локальная настройка оценок константы Липшица.

2.2.2. Локальная настройка с аддитивной сверткой оценок константы Липшица.

2.2.3. Локальная настройка с интервальной схемой построения оценок константы Липшица.

2.2.4. Локальная настройка с выделением подобластей с близкими значениями константы Липшица.

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

3.1. Многошаговая схема редукции размерности.

3.2. Адаптивная многошаговая схема редукции размерности.

3.2.1. Общее описание подхода.

3.2.2. Алгоритмическое описание.

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

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

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

3.6. Операционные характеристики алгоритмов глобального поиска.

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

4.1. Централизованная схема параллельного глобального поиска.

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

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

4.3.1. Общая схема распределенных вычислений.

4.3.2. Структурная схема распределенных вычислений.

4.3.3. Балансировка вычислительной нагрузки в структурной схеме распределенных вычислений.

5. Программные средства параллельной глобальной оптимизации.

5.1. Общая характеристика комплекса глобальной оптимизации 01орйСот.

5.2. Система одномерной многоэкстремальной оптимизации С1ор^Сот-1.

5.3. Система двухмерной многоэкстремальной оптимизации С1орйСот

5.4. Система многомерной многоэкстремальной оптимизации 01орйСот+

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

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

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

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

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

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

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

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

Научная новизна. При выполнении работы получены следующие основные новые результаты:

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

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

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

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

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

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

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

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

- Программная система 01орйСот+ для параллельного решения сложных вычислительно-трудоемких задач многомерной многоэкстремальной оптимизации.

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

Внедрение результатов работы. Результаты работы нашли свое применение при выполнении проектов, выполняемых на факультете ВМК при поддержке Российского фонда фундаментальных исследований (проекты № 04-01-00455, № 07-01-00467-а) и Совета по грантам Президента Российской Федерации по государственной поддержке ведущих научных школ РФ (грант № НШ — 4694.2008.9), совместного научно-исследовательского проекта РФФИ и Нидерландской организации по научным исследованиям NOW 047.016.014. Результаты работы используются также в учебном процессе факультета ВМК ННГУ при чтении курсов "Модели и методы многоэкстремальной оптимизации", "Системы поддержки принятия решений".

Апробация работы. Результаты работы докладывались на Международных конференциях "Высокопроизводительные вычисления на кластерных системах" (Нижний Новгород, 2007, Казань, 2008, Владимир, 2009), Всероссийской конференции "Научный сервис в сети Интернет" (Новороссийск, 2009), научно-технических конференциях "Технологии Майкрософт в теории и практике программирования" (Нижний Новгород, 2007-2008, 2010), на научных конференциях и семинарах Нижегородского государственного университета.

Диссертационная работа состоит из пяти глав.

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

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

- локальная настройка с интервальной схемой построения оценок константы Липшица,

- локальная настройка с выделением подобластей с близкими значениями константы Липшица

- локальная настройка с аддитивной сверткой оценок константы Липшица

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

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

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

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

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

В пятой главе представлено описание программного комплекса глобальной оптимизации в1ор1:1Сот, в котором реализованы разработанные в рамках диссертационной работы методы многоэкстремальной оптимизации. В § 5.1 приводится общая характеристика комплекса глобальной оптимизации 01орйСот. В § 5.2 представлено описание системы С1ор1лСот-1, ориентированной на решение задач одномерной многоэкстремальной оптимизации. Данная система предназначена для проведения вычислительных экспериментов с целью оценки эффективности одномерных алгоритмов глобального поиска. В § 5.3 представлено описание системы С1орйСот-2, ориентированной на решение задач двухмерной многоэкстремальной оптимизации. Данная система предназначена для проведения вычислительных экспериментов с целью исследования адаптивной многошаговой схемы редукции размерности. В § 5.4 представлено описание системы многомерной многоэкстремальной оптимизации С1ориСоггН-, которая является основной в комплексе и ориентирована на параллельное решение задач многомерной многоэкстремальной оптимизации. В § 5.5 приведены результаты вычислительных экспериментов для системы 01орйСот+.

Результаты работы докладывались на Международных конференциях "Высокопроизводительные вычисления на кластерных системах" (Нижний Новгород, 2007, Казань, 2008, Владимир, 2009), Всероссийской конференции "Научный сервис в сети Интернет" (Новороссийск, 2009), научно-технических конференциях "Технологии Майкрософт в теории и практике программирования" (Нижний Новгород, 2007-2008, 2010), на научных конференциях и семинарах Нижегородского государственного университета.

Основное содержание диссертации отражено в девяти работах [12-19,23].

120

Заключение

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

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

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

2. Ашманов С.А., Тимохов А. В. Теория оптимизации в задачах и упражнениях. — М.: Наука, 1991.

3. Базара М, ILlemmu К. Нелинейное программирование. Теория и алгоритмы. -М.: Мир, 1982.

4. Батищев Д. И. Методы оптимального проектирования. — М.: Радио и связь, 1984.

5. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации — Н. Новгород: Изд-во ННГУ, 2006.

6. Богачев К.Ю. Основы параллельного программирования. М.: Бином. Лаборатория знаний,2003.

7. Васильев Ф.П. Численные методы решения экстремальных задач.М.: Наука, 1980.

8. Воеводин В.В. Математические основы параллельных вычислений. М.: МГУ 1991.

9. Воеводин В.В. Модели и методы в параллельных процессах. М.: Наука 1986.

10. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. Спб.: БХВ-Петербург, 2002.

11. Габасов Н.С., Кириллова Ф.М. Методы оптимизации. Минск: Изд-во

12. Гергелъ А.В, Гнатюк Д.В. Модификация адаптивных параллельных алгоритмов для многомерной многоэкстремальной оптимизации Труды Всероссийской суперкомпьютерной конференции (20-25 сентября 2010 г., г. Новороссийск). М.: Изд-во МГУ, 2010. С.352-362.

13. Гергелъ A.B. О новом методе решения многоэкстремальныхмногомерных задач оптимизации //Шестая нижегородская сессия молодых ученых, тез. докл., Нижний Новгород. 2001. С 87-92.

14. Гергель A.B. Применение централизованной схемы параллельного глобального поиска для адаптивной многошаговой схемы редукции размерности //материалы конференции «Технологии Microsoft в теории и практике программирования», Нижний Новгород. 2010. С 64-66.

15. Гергель А. В. Адаптивные параллельные вычисления для многомерной многоэкстремальной оптимизации. Приборостроение, Изд СПГУ, 2009. Т. 52, № 10, С. 74-80.

16. Гергель А.В, Гнатюк Д.В. Адаптивные параллельные алгоритмы для многомерной многоэкстремальной оптимизации. // "Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2009), Изд ВТУ, 2009. С. 92-96.

17. Гергель А.В, Гнатюк Д.В. Адаптивные параллельные алгоритмы для многомерной многоэкстремальной оптимизации. // Материалы конференции Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2010), Изд. ПГТУ, 2010. С. 160-165.

18. Гергель A.B. Параллельные методы многоэкстремальной оптимизации с адаптивными решающими правилами. // Материалы конференции Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2010), Изд. ПГТУ, 2010. С. 152-159.

19. Гергель В.П. Алгоритм глобального поиска с использованием производных // Динамика систем: Межвуз. тематич. сб. науч. тр. / Под ред. Ю.И. Неймарка. Горький: ГТУ, 1992.- С. 161 - 178.

20. Гергелъ B.II. Об одном способе учета значений производных при минимизации многоэкстремальных функций // Ж. вычисл. матем и матем. физ. 1996.-Т.36, № 6. - С. 51-67.

21. Гергелъ В.П. Теория и практика параллельных вычислений: учебное пособие. М., Интернет-Университет Информационных Технологий, Бином, 2007.

22. Гергелъ В.П., Гришагин В.А., Гергелъ A.B. Адаптивные параллельные вычисления для многомерной многоэкстремальной оптимизации. Труды Всероссийской суперкомпьютерной конференции (21-26 сентября 2009 г., г.Новороссийск). М.: Изд-во МГУ, 2009. С.417-421.

23. Гергелъ В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Н. Новгород: Изд-во ННГУ, 2001.

24. Гермейр Ю. Б. Введение в теорию исследования операций.- М.:наука, 1971.

25. Гит Ф., Мюррей У.,Райт М. Практическая оптимизация. -М.: Мир, 1985.

26. Голиков А. И., Евтушенко Ю.Г. Теоремы об альтернативах и их применении в численных методах // Ж. вычисл. матем. и матем. физ. -2003. Т.43, №3. - С. 354-375.

27. Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация. — Н.Новгород: Изд-во ННГУ, 2007.

28. Гришагин В.А. Об условиях сходимости для одного класса алгоритмов глобального поиска. В сб.: Тезисы докл. III Всес. Семинара «Численные методы нелинейного программирования». Харьков: ХГУ, 1979. С. 8284.

29. Гришагин В.А. Операционные характеристики некоторых алгоритмов глобального поиска // Проблемы случайного поиска. Рига: Зинатне, 1978. №7. С. 198-206.

30. Гришагин В.А., Сергеев Я.Д. Асинхронные параллельныехарактеристические алгоритмы в многомерной рекурсивной глобальной оптимизации // 8-я Международная Конференция

31. Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2008), Изд КГТУ, 2008. С. 143-150.

32. Даугавет В. А. Численные методы квадратичного программирования.-СПб.: Изд-во СПбГУ, 2004.

33. Демиденко Е.З. Оптимизация и регрессия. М.: Наука, 1989.

34. Евтушенко Ю.Г Методы поиска глобального экстремума // Исследование операций. -М.: ВЦ АН СССР, 1974. Т.4. - С.39-68.

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

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

37. Евтушенко Ю.Г., Малкова В.У., Станевичюс A.A. Распараллеливание процесса поиска глобального экстремума // Автоматика и телемеханика. 2007. - №5. - С.45-58.

38. Евтушенко Ю.Г, Потапов М.А. Методы численного решения многокритериальных задач.// ДАН, 1986. Т.2.№ 11.

39. Ермаков С.М., Жиглявский A.A. Математическая теория оптимального эксперимента. М.: Наука, 1987

40. Ермольев Ю.М., Норкин В.И. Методы решения невыпуклых негладких задач стохастической оптимизации // Кибернетика и системый анализ.-2003. Т.5. - С.89-106.

41. Жиглявский A.A. Математическая теория глобального случайного поиска.-Л.: Изд-во ЛГУ, 1985.

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

43. Жилинскас А.Г.Глобальная оптимизация. Аксиоматика статическихмоделей, алгоритмы, применение.- Вильнюс: Мокслас,1986

44. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. М.: Физматлит, 2003.

45. Карманов В.Г. Математическое программирование. М.: Наука, 1986.

46. Kapp Ч, Хоув Ч. Количественные методы принятия решений в управлении и экономике.-М.: Мир, 1964.

47. Кнут Д. Искусство программирования. Т.2: Получисленные алгоритмы.-3-е изд.- М.: Вильяме, 2000.

48. Корнеев В.В. Параллельное программирование в MPI. М.-Ижевск: Институт компьютерных исследований, 2003.

49. Лузин H.H. Теория функций действительного переменного. Учпедгиз, М, 1948.

50. Малоземов В.Н. Линейная алгебра без определителей. Квадратичная функция. СПб.: Изд-во СПбГУ, 1997.

51. Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.:Наука, 1978.

52. Немировский A.C., Юдин Д.Б. Сложность зада и эффективность методов оптимизации. — М.: Наука, 1979.

53. Немнюгин С.,Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. Спб.: БХВ-Петербург, 2002.

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

55. Пшеничный Б.Н, Данилин Ю.М. Численные методы в экстремальных задачах. М.:Наука, 1975.

56. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.:Наука, 1980.

57. Растригин JI.A. Адаптация сложных систем. Методы и приложения. -Рига: Зинатне, 1981.

58. Растригин JI.A. Статистические методы поиска. -М.: Наука, 1968.

59. Сергеев ЯД. Одномерный детерминированный алгоритм глобальной оптимизации // Ж. вычисл. матем и матем. физ. — 1995. Т.35, № 5. — С. 705-717.

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

61. Сергеев ЯД., Стронгин Р.Г., Алгоритм глобальной оптимизации с параллельными итерациями // Ж. вычисл. матем и матем. физ. 1989. -Т. 29, №3.-С. 332-345.

62. Стрекаловский A.C. К проблеме глобального экстремума //Докл. АН СССР. 1987. - Т.282, №5. - С. 1062-1066.

63. Стронгин Р.Г. О сходимости одного алгоритма поиска глобального экстремума // Изв. АН СССР. Техническая кибернетика. -1973.-Т.4-С.10-16.

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

65. Стронгин Р.Г., Маркин Д. JI. Минимизация многоэкстремальных функций при невыпуклых ограничениях // Кибернетика. — 1986.-Т.4. -С.63-69.

66. Стронгин Р.Г., Гергелъ В.П., Городецкий С.Ю., Гришагин В.А., Маркина М.В. Современные методы принятия оптимальных решений. -Н.Новгород: Изд-во ННГУ, 2002.

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

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

69. Тимонов J1.H. Алгоритм поиска глобального экстремума // Изв. АН СССР. Техническая кибернетика. 1977.-T.3.-C.53-60.

70. Туй X. Вогнутое программирование при линейных ограничениях. //Докл. АН СССР. 1964. - Т. 159, №9. - С. 32-35.

71. Уайлд Д.Дою. Методы поиска экстремума, 1967

72. Якобовский М.В. Распределенные системы и сети. М.: МГТУ «Стакин», 2000.

73. A user's guide to tabu search/isaf. By F. Glover, E. Taillard, D. De. Werra. — The Netherlands: Baltzer Scince Publishers, 1993. Vol. 41 of Special Issue of Annals of Operations Research.

74. Addis В., Locatelli M. A new class of test function for global optimization // J. Global Optim. 2007.- Vol.38, № 3.-P.479-501.

75. Agent Modeling, Papers from the 1996 AAAI Workshop, 1996. AAAI Press. ISBN: 1-5773-5008-1.

76. Andrews G.R. Foundations of Multithreading, Parallel and Distributed Programming. Addison-Wesley,2000 (русский перевод Эндрюс Г.Р.Основы многопоточного, параллельного и распределенного программирования. М.: Издательский дом «Вильяме», 2003)

77. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems / Ed. by P. M. Pardalos.- Dordrecht: Kluwer Academic Publishers, 2000.

78. Archetti F., Schoen F. A survey on the global optimization problem: Generaltheory and computational approaches // Ann. Oper. Res. — 1984. — Vol.1, №2. — P.87-110.

79. Baritompa W. Customizing methods for global optimization — A geometric viewpoint //J. Global Optim. 1993.- Vol. 3, № 2. - P. 193-212.

80. Bayesian Heuristic Approach to Discrete and Global Optimization/ J. Mockus, W.Eddy, A.Mockus et al. Dordrecht: Kluwer Academic Publishers, 1996.

81. Bertsekas D.P., Tsitsiklis J.N. Parallel and Distributed Computation. Numerical Methods. Prentice Hall, Englewood Cliffs, New Jersey, 1989.

82. Breiman L., Citler A. A deterministic algorithm for global optimization // Math. Program. 1993. - Vol.58, № 58, № 1 - 3. -P.179-199.

83. Casado L.G., Garcia I., Csendes T. A new multisection technique in interval methods for global optimization computing // Computing. — 2000. — Vol. 65, № 3. -P.263-269.

84. Cvijovic D., Klinowski J. Taboo search an approach to the multiple minima problem // Science.-1995.-Vo;.267, №5198.-P.664-666.

85. Deep Blue Versus Kasparov: The Significance for Artificial Intelligence, Collected Papers from the 1997 AAA! Workshop, 1997. AAA! Press. ISBN: 1-5773-5031-6.

86. Dekkers A., Aarts E. H. L. Global optimization and simulated annealing // Math. Program. 1991. - Vol. 50, № 1 - 3.- P. 367-393.

87. Developments in Global Optimization / Ed. by I. M. Bomze, T. Csendes, R. Horst, P. M. Parlalosc

88. Encyclopedia of Optimization (6 volumes) / Ed. by C A. Floudas, P. M. Parialos.- Kluwer Academic Publishers, 2001.

89. Essays and Surveys in Global Optimization / Ed. by C. Audet, P. Hansen, G. Savard. GERAD 25th Anniversary. N. Y.: Springer-Verlag, 2005.

90. Evtushenko Y.G. Numerical Optimization Techniques. Berlin: SpringerVerlag, 1985.

91. Floudas C. A. Deterministic Global Optimization: Theory, Algoritms, and Applications. Dordrecht: Kluwer Academic Publishers, 2000

92. Flynn M.J. Very high-speed computing systems //Proceedings of the IEEE 1966. 54(12):P. 1901-1909.

93. Fogel D. B. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. Piscataway, NJ, USA: Wiley-IEEE Press 2000.

94. Foster I. Designing and Building Parallel Programs: Concepts and Tools for Software Engineering. Reading, MA: Addison-Wesley, 1995.

95. Galperin E. A. The cubic algorithms // J. Math. Analys. And Appl. 1985. V.112. P. 635-640.

96. Gergel V.P. A global optimization algorithm for multivariate function with Lipschitzian first derivatives // J. Global Optim. 1997. - Vol.10, № 3,-P.257-281.

97. Gergel V.P. A software system for multiextremal optimization // European J. Oper. Res. 1993. - Vol.65, № 3. - P. 305-313.

98. Global Optimization in Engineering Design / Ed. by I.E. Grossman -Dordrecht: Kluwer Academic Publishers, 1996.

99. Global Optimization Using Inerval Analysis / Ed. by E.R. Hansen-N.Y.: M.Dekker, 1992.

100. Global Optimization: From Theory to Impementation /Ed. by I. E. Liberti, N. Maculan. Berlin: Springer-Verlag, 2006.

101. Global Optimization: Scientific and Engineering Case Studies/ Ed. by J.D. Pmfer.-Berlin:Springer Verlag, 2006.

102. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley,1989.

103. Grama A.Y., Gupta A. and Kumar V. Isoefficiency: Measuring the scalability of parallel algorithms and architectures // IEEE Parallel and Distributed technology, 1993. 1(3).P.12-21.

104. Grishagin V.A., Sergeyev Y.D., Strongin R.G. Parallel characteristic algorithms for solving problems of global optimization // J.Global Optim. -1997.- Vol. 10, № 2. — P. 185-206.

105. Group W., Lusk E., Thakur R. Using MPI-2: Advanced Features of the Message Passing Interface (Scientific and Engineering Computation).- MIT Press, 1999.

106. Hal Abelson, editor. Workshop on Amorphous Computing, September 13-14, 1999, DARPA ITO, MIT Artificial Intelligence Laboratory, Cambridge, MA, USA. MIT AI Lab.

107. Handbook of Global Optimization / Ed, by P.M.Pardalos, H.E. Romeijn. -Dordrecht: Kluwer Academic Publishers, 2002. Vol.2

108. Handbook of Global Optimization / Ed, by R. Horst, P.M.Pardalos. -Dordrecht: Kluwer Academic Publishers, 1995. — Vol.1

109. Handbook of Test Problems in Local and Global Optimization / C.A. Floudas, P.M. Pardalos, C. Adjiman et al. Dordrecht: Kluwer Academic Publishers, 1999.

110. Hansen P., Jaumard B., Lu S. H. Global optimization of univariate Lipschitz functions: 2. New algorithms and computational comparison // Math. Program. 1992. V.55. P. 273-293

111. Hansen P., Jaurmard B. Lipschitz optimization // Handbook of Global Optimization / Ed, by R. Horst, P.M.Pardalos. Dordrecht: Kluwer Academic Publishers, 1995. - Vol.1.- P.407-493.

112. Hartman J.K. Some experiments in global optimization // Nav. Res. Logist. -1973. Vol.20, № 3. — P.569-576.

113. Henri Elle Bal. Programming Distributed Systems. Silicon Press/Prentice Hall International, 1990/1991. ISBN: 0-9293-0605-8, 978-0-92930-605-6, 0-13722083-9.

114. Holland J. H. Adaptation in Natural and Artificial Systems.- Ann Arbor, MI, USA: The University of Michigan Press, 1975.

115. Horst R., Pardalos P. M., Thoai N.V. Introduction to Global Optimization.j

116. Dordrecht: Kluwer Academic Publishers, 1995.- (The 2 edition Kluwer Academic Publishers, 2001).

117. Horst R., Tuy H. Global Optimization Deterministic Approaches.- Berlin: Springer-Verlag, 1996.

118. Horst R., Tuy H. On the convergence of global methods in multiextremal optimization // J. Optim. Theory Appl. 1987. - Vol.54, № 2. -P.253-271.

119. James E. Baker. Adaptive selection methods for genetic algorithms. In Proceedings of the 1 st International Conference on Genetic Algorithms, pages 101-111, 1985.

120. James E. Baker. Reducing bias and inefficiency in the selection algorithm. In Proceedings of the second International Conference on Genetic Algorithms, pages 14-21, 1987.

121. Kearfott R.B. Rogorous Global Search: Continuous Problems. Dordrecht: Kluwer Academic Publishers, 1996.

122. Kelley C.T. Iterative Methods for Optimization. Philadelphia: SIAM Publications, 1999.

123. Kirkpatrick S., Gellat C.D., Vecchi M.P. Optimization by simulated annealing

124. Science. 1983. - Vol. 220, № 4598. -P.671-680

125. Kumar V., Grama A., Gupta A, Karypis G. Introduction to Parallel Computing. The Benjamin / Cumming Publishing Company, Inc., 1994 (2nd edn.,2003).

126. Kumar V., Grama A., Gupta A., Karypis G. Introduction to Parallel Computing.-The Benjamin/Cummings Publishing Company, Inc., 1994 (2nd edn.,2003).

127. Locatelli M. On the multilevel structure of global optimization problems // Comput. Optim. Appl. 2005.- Vol.30, № 1. - P.5-22.

128. MacLagan D., Sturge T., Baritompa W. Equivalent methods for global optimization // State of the Art in Global Optimization / Ed. By C.A. Floudas, P.M. Pardalos. — Dordrecht: Kluwer Academic Publishers, 1996. P.201-212.

129. Meewella C.C., Mayne D. Q. An algorithm for global optimization of Lipschitz continuous // J. Optim. Theory Appl. 1988. - Vol. 57, № 2. -P.307-322.

130. Michalewicz Z. Genetic Algoritms + Data Structures = Evolution Programs. -3 rd edition. Berlin: Springer-Verlag, 1996.

131. Mladineo R.H. Stochastic minimization of Lipschitz functions // Recent Advances in Global Optimization // Ed. by C. A. Floudas, P. M. Pardalos.-Princeton, NJ, USA: Princeton University Press, 1992.- P.369-383.

132. Mockus J. Bayesian approach to global optimization. Dordrecht: Kluwer Academic Publishers, 1989.

133. New Ideas in Optimization / Ed. By D.W. Corne, M. Dorigo, F. Glover.-Maidenhead, UK: McGraw-Hill, 1999

134. New Ideas in Optimization // Ed. by D.W. Corne, M. Dorigo, F. Glover.-Maidenhead, UK: McGraw-Hill, 1999.

135. Nimerical Techniques for Stochastic Optimization Problems / Ed. by Y. M. Ermoliev, R.J. -B.Wets. Berlin: SpringerOVerlag,1988.

136. Nocedal J., Wright S.J. Numerical Optimization. — Dordrecht: Springer-Verlag,1999.

137. Optimization and Industry: New Frontiers / Ed. by P.M. Pardalos, V.V. Korotkikh. Dordrecht: Kluwer Aademic Publishers, 2003.

138. Pacheco P. Parallel Programming with MPI. Morgan Kaufmann, 1996.

139. Pardalos P. M., Rosen J. B. Constrained Global Optimization: Algorithms and Applications.-N.Y.: Springer-Verlag, 1987.

140. Pardalos P.M. Romeijn H.E., Tuy H. Recent developments and trends in global optimization // J.Comput. Appl. Math. 2000. - Vol.124,№1 -2.-P.209-228.

141. Per Bak, Chao Tang, and Kurt Wiesenfeld. Self-organized criticality. Physical Review A, 38(l):364-374, July 1, 1988. doi:10.1103/PhysRevA.38.364.

142. Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire. Boosting the margin: a new explanation for the effectiveness of voting methods. Annals of Statistics, 26(5): 1651—1686, 1998.

143. Peter J. Angeline and Kenneth E. Kinnear, Jr, editors. Advances in Genetic Programming,volume 2 of Complex Adaptive Systems. MIT Press, Cambridge, MA,USA, October 26, 1996. ISBN: 0-2620-1158-1, 978-026201-158-7.

144. Pinter J. D. Global optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementation and Applications). Dordrecht: Kluwer Academic Publishers, 1996.

145. Pinter J.D. Convergence qualification of adaptive partition algorithms in global optimization // Math. Program. 1992. - Vol. 56, № 1-3. - P.343-360.

146. Proceedings of the The Fifth Conference on Innovative Applications of Artificial Intelligence (IAAI 1993), July 11-15, 1993, Washington, DC, USA. AAAI. ISBN:0-9292-8046-6.

147. Quinn M.J. Parallel programming in C with MPI and OpenMP.- New York, NY: McGraw-Hill, 2004.

148. R. Battiti and G. Tecchiolli. The reactive tabu search. ORSA Journal on Computing, 6(2): 126-140, 1994.i

149. Ratschek H., Rockne J. New computer Methods for Global Optimization. -Chichester, England: Ellis Horwood Ltd, 1988.

150. Ratschek H., Rockne J. New Computer Methods for Global Optimization.-Chichester, England: Ellis Hordoow Ltd, 1988.

151. Recent advances in Global Optimization / Ed. by C.A. Floudas, P.M. Pardalos.- Princeton, NJ, USA: Princeton University Press, 1992.

152. Rinnooy Kan A.H.G., Timmers G.T. Global optimization // Handbook of Operations Research, Volume 1: Optimization / Ed. by.G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd. Amsterdam: North-Holland, 1989.-P.631-662.

153. Roosta S.H. Parallel Processing and Parallel Algorithms: Theory and Computation. Springer-Verlag, NY,2000.

154. Schhwefel H.-P. Evolution and Optimum Seeking. — N.Y.: John Wiley &Sons, 1995.

155. Schneider J. J., Kirkpatrick S. Stochastic Optimization.-Berlin: Springer, 2006.

156. Schoen F. Stohasctic techniques for global optimization: A survey of recent advances //J. Global Optim.-1991.-Vol.1, № 1. -P.207-228.

157. Schwefel H.-P. Evolution and Optimum Seeking. -N.Y.: John Wiley & Sons, 1995.

158. Sergeyev Y. D. A global optimization algorithms using smooth auxiliary functions: Tech. Rep. 1. Institute of Systems and Informatics, Rende (CS), Italy: ISI-CNR, 1994.

159. Sergeyev Y. D. An efficient strategy for adaptive partition of N-dimensional intervals in the framework of diagonal algorithms // J. Optim. Theory Appl.-2000.-Vol.l07№ 1. -P. 145-168.

160. Sergeyev Y. D. Global one-dimensional optimization using smooth auxiliaryfunctions //Math. Program. 1998.-Vol.81, № 1. -P. 127-146.

161. Sergeyev Y. D., Grishagin V.A. Parallel asynchronous global search and the nested optimization scheme // J. Comput. Anal. Appl. — 2001. — Vol. 3, № 2. — P. 123-145.

162. Sergeyev Y. D., Grishagin V.A. Parallel method for finding the global minimum of univariate function // J. Optimt. Theory. Appl. — 1994. Vol. 80, №3.-P. 513-536.

163. Sergeyev Y. D., Grishagin V.A. Parallel Method for Finding the Global Minimum of Univariate Functions // Journal of Optimization Theory and Applications, 1994. V. 80.№ 3.

164. Sergeyev Y. D., Grishagin V.A. Sequential and parallel global optimization algorithms // Optim. Methods Softw. 1994. - Vol. 3, № 1 -3. - P. 1111-124.

165. Sergeyev Y.D. A global optimization algorithm using derivatives and local tuning: Tech. Rep. 1. Institute of Systems and Informatics, Rende (CS), Italy: ISI-CNR, 1994.

166. Sergeyev Y.D. A one-dimensional global minimization algorithm using local estimation of Lipschitz constant: Tech. Rep.28. — University of Calabria, Rende (CS), Italy: DEIS, Department of Electronics, Computer Sience and Systems, 1992.

167. Sergeyev Y.D. An algorithm for finding the global minimum of multiextremal Lipschitz functions // Operations Researh 93 / Ed. by A. Bahem, U. Derigs, MJunger, R.Schrader.-Physica-Verlag, 1994.-P.463-465.

168. Sergeyev Y.D. An information global optimization algorithm with local tuning // SIAM J. Optim. 1995. - Vol.5, № 4.- P.858-870.

169. Sergeyev Y.D. Parallel information algorithm with local tuning for solving multidimensional GO problems // J. Global Optim. -1999. -Vol.15, № 2. -P. 157-167.

170. Shir M., Otto S., Huss-Lderman S., Walker D., Dongarra J. MPI: The Complete Reference. MIT Press, Boston, 1996.

171. Skillicorn D.B., Talia D. Models and languages for parallel computation // ACM Computing surveys, 1998, 30, 2.

172. Snir M., Otto S., Huss-Lederman S., Walker D., Dongarra J. MPI: The Complete Reference. — MIT Press, Boston, 1996.

173. State of The Art in Global Optimization: Computation Methods and Applications / Ed. by. C.A. Floudas, P.M. Pardalos.- Dordrecht: Kluwer Academic Publishers, 1996.

174. Stephanos Androutsellis-Theotokis and Diomidis Spinellis. A survey of peer-to-peer content distribution technologies. ACM Comput. Surv., 36(4):335-371,2004. ISSN: 0360-0300.

175. Stephens C.P., Baritompa W. Global optimization requires global information // J. Optim. Theory Appl. 1998. - Vol. 96, № 3.- P.575-588.

176. Stochastic and Global Optimization / Ed. by G.Dzemyda, V. Saltenis, A. Zilinskas. Dordrecht: Kluwer Academic Publishers, 2002.

177. Stochastic and Global Optimization / Ed. by. G. Dzemyda, V. Saltenis, A. Zilinskas. Dordrecht: Kluwer Academic Publishers, 2002.

178. Storn R., Price K. Different evolution A simple and efficient heuristic for global optimization over continuous spaces // J. Global Optim. - 1997.-Vol.ll, №4. -P.341-259.

179. Strekalovsky A.S. Global optimality conditions for nonconvex optimization // J. Global Optim. 1998. - Vol.12, №4. -P.415-434.

180. Strongin R.G., Sergeev Ya.D. Global multidimensional optimization on parallel computer//Parallel Comput. 1992.- Vol. 18, № 11.-P.1259-1273.

181. Strongin R.G., Sergeev Ya.D. Global optimization with Non-Convex Constrains. Sequential and Parallel Algorithms.-Dordrecht: Kluver Academic Publishers. The Netherlands, 2000.

182. Sturua E.G., Zavriev S.K. A trajectory algorithm based on the gradient method. The search on the quasioptimal trajectories //J. Global Optim. 1991. -Vol. 1, №4.-P.375-388.

183. Tawarmalini M., Sahinidis N.V. Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory Algorithms, Software and Applicatios. Dordrecht: Kluwer Academic Publishers, 2002.

184. Torn A, Zilinskas A. Global optimization. Berlin: Springer-Verlag, 1989.

185. Torn A., Zilinskas A. Global Optimization. Berlin: Springer-Verlag, 1989.

186. Towards Global Optimization (Volumes 1 and 2) / Ed. by L.C.W. Dixon, G.P. Szego. — Amsterdam: North-Holland,1975,1978.

187. Van Laarhoven P. J. M., Aarts E. H. L. Simulated Annealing: Theory and Applications.- Dordrecht: Kluwer Academic Publishers, 1987.

188. Walster G., Hansen E., Sengupta S. Test results for global optimization algorithm // Numerical Optimization 1984 / Ed. by P.T. Boggs, R.H. Byrd, R. B. Schnabel. -Phuiladelphia: SIAM, 1985. -P.272-287.

189. Wilkinson B., Allen M. Parallel programming. Prentice Hall, 1999.

190. William Bateson. Mendel's Principles of Heredity. Cambridge University Press, Cambridge, 1909. ISBN: 978-1-42864-819-7.

191. Zavriev S.K. On the global optimization properties of finite-difference local descent algoritms // J. Global Optim. 1993.-Vol.3, №3.-P.337-358.

192. Zhigljavsky A. A. Theory of Global Random Search. Dordrecht: Kluwer Academic Publishers, 1991.

193. Zhigljavsky A. A., Zilinskas A. Stochastic Global Optimization. N. Y.: Springer, 2008.

194. Zomaya A.Y. Parallel and Distributed Computing Handbook. McGraw-Hill, 1996.