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

005010636

Сысоев Александр Владимирович

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

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

9 013

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

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

г-о

005010636

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

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

д.т.н., проф. Гергель В. П.

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

д.т.н., проф. Модорский В.Я. к.ф.-м.н., доцент Коротченко А.Г.

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

Институт прикладной математики им. М.В. Келдыша РАН, г. Москва

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

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

Н.И.Лобачевского

Автореферат разослан “ ЛХ /ду-1-У 2012 г.

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

диссертационного совета Д 212.166.13 к.ф.-м.н., доцент

Савельев В.П.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность заключается в следующем.

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

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

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

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

Внедрение результатов работы.

Исследования по теме диссертации выполнялись при поддержке Российского Фонда Фундаментальных Исследований (грант № 04-01-89002-ШЮ_а), Совета по грантам Президента Российской Федерации (грант № МК-1536.2009.9) и

Федерального агентства по науке и инновациям (ФЦП «Научные и научнопедагогические кадры инновационной России», госконтракт JVb 02.740.11.5018). Результаты работы использовались при реализации совместного исследовательского проекта РФФИ и Нидерландской организации по научным исследованиям (the Netherlands Organization for Scientific Research - NWO); номер проекта NWO: 047.016.014. Результаты работы используются также в учебном процессе факультета ВМК ННГУ при чтении курсов «Модели и методы многоэкстремальной оптимизации», «Системы поддержки принятия решений».

Апробация работы. Результаты работы докладывались на Международных научно-практических семинарах «Высокопроизводительные вычисления на кластерных системах» (Нижний Новгород,;2005, 2007, 2011, Санкт-Петербург, 2006, Владимир, 2009), Всероссийской конференции «Научный сервис в сети Интернет» (Новороссийск, 2006), Всероссийской научно-технической конференции «Аэрокосмическая техника, высокие технологии и инновации» (Пермь, 2008), научнотехнических конференциях «Технологии Майкрософт в теории и практике программирования» (Москва, 2005, Нижний Новгород, 2006-2008), на научных конференциях и семинарах Нижегородского государственного университета.

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

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

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

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

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

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

Пусть объект исследования характеризуется набором параметров У~ (л, ... ,3'д.) (1)

и вектор-функцией характеристик

Н >') = (*1 (.V), ...,Ч (>’)). (2)

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

Предполагаем, что:

• Координаты вектора у= (>\, ... , уу) могут непрерывно изменяться в заданных пределах, которые задают гиперинтервал

О = (уєД":а, < у,< Ь,, 1 < /< ^}. (3)

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

На часть характеристик из (2), номера которых определяются множеством С = и,...,]т}<={1(4) накладываются функциональные ограничения

і * С: 0 ■ (5)

Часть характеристик из (2), номера которых определяются множеством Р = { ,4} с {1,..., и}, (6)

рассматривается как векторный критерий эффективности

/(у)=(Л М> ~’Л(у))> (7)

где

/,■(>') = %(>')> 'ієр■ (8>

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

1. Минимизируется первый по важности критерий /І и определяется его минимальное значение /і*.

2. Назначается величина допустимого увеличения £1 значения первого критерия (уступка).

3. Ищется минимальное значение второго критерия при условии, что первый не превысит значение + е1.

4. Затем назначается величина уступки ег по второму критерию и т.д.

Таким образом, для заданного набора уступок , 1 <1<к оптимальный выбор у является решением рекурсивной задачи:

;* = ащ тш{/к (у): /у (у) < /] + в,, 1 < у ^ к-1}, (9)

/*=1шп{/(>-), уей: /Ду)</’ + Ер 1< /\ <1<к. (10)

В § 1.2 приведен пример описания вычислительно-трудоемкой задачи

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

терминах. Профиль колеса описывается с помощью 5-сплайна, построенного на основе множества точек на кромке, основании кромки и поверхности качения колеса. В качестве компонент вектора у параметров задачи оптимизации выбраны ординаты подвижных точек сплайна, при этом абсциссы данных точек фиксированы. В описываемой задаче число подвижных точек (число переменных) N = 11, границы изменения параметров [-1, 1]. В процессе движения центр колесной пары вследствие конической формы колеса совершает синусоидальные колебания относительно линии, проходящей в середине рельсового полотна. Минимизировать необходимо разность радиусов вращения, а ограничения вводятся из соображений устойчивости. Таким образом, возникает задача оптимизации с числом параметров //=11, числом ограничений т = 6; целевая функция и функции ограничений - многоэкстремальные. Задача является вычислительно-трудоемкой: проверка ограничений задачи и вычисление значения целевой функции в одной точке занимает более десяти секунд (1гие1 Хеоп 3 ГГц). Результаты решения описанной задачи с использованием представляемого в работе программного комплекса изложены в главе 4.

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

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

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

Один из общих подходов к редукции основан на использовании отображений, называемых кривыми (развертками) Пеана, которые сопоставляют любой липшицевой в гиперкубе Р = {»'еЛл : -X' < < V , 1< /< функции <р{у)

одномерную функцию <р(у{х)), удовлетворяющую на отрезке [0, 1] равномерному условию Гельдера с показателем \Ш.

|«,(>'(л'2))-<г,(^(^))|<4-/.-7л?-(х2-х1)1Л. (11)

При численном построении развертки задается точность М, которая определяет максимальную погрешность оценки каждой координаты функции <р(у) равную 2чл/+1). Оценки точек кривой сопоставляют равномерной с шагом 2~ш сетке на отрезке [0, 1] равномерную с шагом Тм сетку в гиперкубе Р.

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

Вводится гиперкуб

Р0 = |иеЛл': -2 ‘< ц < 3-2-' , 1< /< А'} (12)

с длиной ребра, равной 2, и семейство гиперкубов

Р, = |иеЛЛ’: -2Ч< ц.+2-/< 3-2'1 , 1< 1< Аг|, 1</<1, (13)

где гиперкуб Р/+1 получается путем сдвига гиперкуба Р/ вдоль главной диагонали на шаг -Т! по каждой координате, и для каждого гиперкуба Р/, ()</</, вводится своя развертка у^х) типа кривой Пеано, отображающая отрезок [0, 1] на этот гиперкуб. Приближенное построение развертки у{х) для точности, соответствующей разбиению с номером М+ 1 порождает в гиперкубе Р, равномерную сетку с шагом 2~м по каждой координате.

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

Рассмотрим первоначально двумерный случай. На рис. 1 а) представлены гиперкубы Ро-Л исходной множественной развертки для Ь == 3.

а)

б)

Рис. 1. Гиперкубы исходной а) и модифицированной б) множественной развертки

(ы=г,ь = ъ)

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

Р, = {иеД-у: -1< ц < 1 , 1< ;< ЛГ}. (14)

Дадим общее описание правила построения каждой множественной развертки для произвольного N.

Введем двоичную нумерацию множественных разверток, состоящую из N разрядов:

а =(а0,...,аЛМ), а, =0,1. (15)

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

Для построения каждой множественной развертки достаточно задать описание базового гиперкуба Р0 и правила сдвига гиперкубов.

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

Ра = {иеЛ¥: -2~х-а,<, и,< 3-2~’-а,., 1</< Я} (16)

То есть по тем разрядам, в которых в двоичном номере множественной развертки стоит единица, базовый гиперкуб будет иметь по соответствующим переменным границы —З-Т1..!'1, а по разрядам равным нулю границы по переменным будут

Смещение же остальных гиперкубов Рь ..., Р/, в множественной развертке с номером а будет описываться вектором

Р =(-2'-(-1Г,...,-2‘'-(-1Гч) • (17)

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

Предложенная в работе модифицированная множественная развертка значительно повышает потенциал использования параллелизма в процессе поиска глобально оптимума. Так уже для трехмерных задач при точности построения приближения развертки М= 10, общее число доступных разверток в семействе множественных разверток составит Л/ ■ 23 — 1 = 79. В общем же случае число разверток может быть получено согласно следующему правилу.

Утверждение. Для задач размерности N при точности приближенного построения кривых Пеано М максимальное число разверток в семействе множественных разверток равно М • 2Л - 1.

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

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

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

В § 2.1 предложена новая схема иерархического описания объекта исследований, включающая три базовых элемента:

• объект оптимизации

О =<у, Д лу(у) > (18)

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

• задание оптимизации

г = (19)

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

• задача оптимизации

г = < у, Д и,и> (20)

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

В работе предложена расширенная модель объекта исследований на случай, когда некоторые входящие в нее функционалы могут быть вычислимы не во всех точках области Д В этом случае описание объекта О должно быть дополнено вектором признаков £" (}’), указывающим, для каждого функционала и; (г) вычислен он или нет

0 = <у,Д №(у), 4"(у) >. (21)

Назовем такую модель частично вычислимой, а модель, для описания которой достаточно описания в виде (18), - полностью вычислимой.

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

г = <Р,/£г,С,8,?,Ч>. (22)

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

0 = {(У,'ИУ»: 0 £/'<£}, (23)

а для частично вычислимой - множества

« = {(ЛЧУ),Г(У)): 0< 1 < А’|, (24)

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

Будем называть множество О поисковой информацией.

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

Переход от модели объекта к заданию оптимизации означает преобразование множества П в множество

« = {(У,/(У)^/(У),Я(/),^(У)): 0<,-Ц. (25)

Множество м будем называть оптимизационными данными.

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

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

1. скаляризация векторного критерия эффективности,

2. редукция задачи условной оптимизации к безусловной,

3. редукция размерности,

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

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

При переходе в процессе численного решения от задачи оптимизации к задаче -2 в рамках одного и того же задания Ъ все точки из ш^), попадающие в область поиска задачи г2, могут быть сразу же внесены в ее оптимизационные данные. Такую ситуацию будем называть полной информационной совместимостью. Напротив, при переходе в процессе численного решения от задания Ъ\ к заданию Ъ2 элементы в ю^) на основе значений из множества м(2]) могут быть восстановлены не полностью. Действительно, даже если точка у' из и(2,) является допустимой в области поиска для задания Ъ2, в силу разных множеств (/ и Р' в этих заданиях часть необходимых значений ограничений и/или значение критерия могут отсутствовать. Такую ситуацию будем называть частичной информационной совместимостью. Допустимые данные из £и7.\) могут быть, тем не менее, использованы в процессе решения задания Ъъ поскольку при порождении в задании Ъг точки, уже имеющейся в (), можно будет через номера критериев и ограничений восстановить данные в (0(г2), что позволит вычислять лишь недостающие значения функционалов.

В § 2.3 на основе оптимизационных данных со и поисковой информации П построена полная информационная модель состояния поиска в виде матрицы состояния поиска (МСП).

А = (а, ак), (26)

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

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

приходящаяся на обработку МСП, в общем времени работы метода оптимизации может достигать 95%.

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

Для существенно многомерных задач объем памяти, необходимый для хранения МСП, может превысить размер физической оперативной памяти вычислительного узла. В диссертационной работе предложена и реализована собственная схема страничной организации памяти, позволяющая продолжить счет при исчерпании оперативной памяти. Стратегия замещения страниц, реализованная в системе, (вытеснять страницу, у которой максимальная характеристика наименьшая среди всех страниц) близка по эффективности к оптимальному алгоритму Билэди и существенно превышает показатели стратегий замещения современных операционных систем. В диссертации приведены результаты экспериментов, показывающие выигрыш в 5.9 раза во времени счета при использовании собственной реализации страничной памяти в сравнении с механизмом виртуальной памяти ОС ^Ут<Зо\\'5.

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

В § 3.1 приводится общая характеристика комплекса глобальной оптимизации 01орЕх. Комплекс предназначен для решения широкого класса многомерных многоэкстремальных задач условной оптимизации с невыпуклыми ограничениями, постановка которых может быть выполнена в виде (1}-(8). Алгоритмическую основу системы составляют информационно-статистические алгоритмы глобальной оптимизации. Основной режим функционирования комплекса - параллельные вычисления на кластерных системах.

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

• выполнение требований информационно-алгоритмической модели процесса поиска;

• возможность функционирования комплекса в качестве приложения в системах управления кластером;

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

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

Рис. 2. Компонентная архитектура программного комплекса

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

На прикладном уровне программный комплекс содержит реализацию трех решателей:

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

• в виде динамически подключаемой библиотеки - обеспечивает решение задач оптимизации в качестве оптимизационной компоненты во взаимодействие с прикладным пакетом;

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

В § 3.2 описана программная реализация компонент системного и прикладного уровней комплекса GlobEx.

Программный комплекс GlobEx реализован в среде разработки Microsoft Visual Studio 2005. Компоненты системного уровня, консольный и dll-решатель реализованы на языке C++. GUI-решатель выполнен на управляемом (managed) C++ с использованием технологий .NET и DirectX. Для реализации параллельных вычислений использовалась библиотека передачи сообщений MPI. Программный комплекс ориентирован на функционирование в ОС семейства Windows и под управлением систем управления кластером Microsoft Compute Cluster Server 2003 и Microsoft НРС Server 2008. Общий объем исходного кода —2 Мб.

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

В §4.1 представлена методика применения программного комплекса GlobEx, включающая этапы:

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

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

3. Использование консольного решателя во взаимодействии с системой управления кластером Microsoft НРС Server 2008.

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

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

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

Рассматривается задача идентификации параметров производственного блока модели экономики России, разрабатывавшаяся в ВЦ РАН для оценки динамики теневого оборота в 1995-2003 гг. За производственную функцию экономики России 1995-2003 гг., описывающую в каждый момент времени t зависимость валового внутреннего продукта Y от количеств используемых производственных факторов: труда R и капитала С, - взята однородная степени у CES-функция.

Y(t) = C(c)f(x), f(x) = S[a+{\-a)xfJ1’, x = R{t)/C(l), (27)

где параметры производственной функции удовлетворяют неравенствам 0 < « < 1, /9 > 0, у > 1, £>>0.

Считаем, что производитель функционирует с целью максимизации его капитализации. Задача содержит 12 варьируемых параметров и два ограничения. Постановка задачи была оформлена в виде динамической библиотеки в соответствие с рекомендациями из § 4.1. Для анализа были выбраны параметры: число разверток L= 1 (две развертки), точность построения разверток т = 4 (16 точек на каждый параметр). Время решения с использованием разработанного программного 16

комплекса 01оЬЕх на одном из узлов кластера ННГУ составило порядка двух минут. Указанная задача также была решена в ВЦ РАН на суперкомпьютере межведомственного суперкомпьютерного центра МВС-1000 на сетке в 8 точек для каждого параметра, что дает 81", т.е. порядка 69 млрд. вариантов. Расчет с использованием 512 процессоров потребовал около 4 часов. В силу использования в два раза более высокой точности по каждой размерности, с использованием программного комплекса 01оЬЕх было найдено значение критерия (40.014) лучшее, нежели при решении на сетке. Необходимо отметить, что подобная точность недостижима при полном переборе, поскольку потребовала бы расчета 824 вариантов.

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

Х(^м'(>’)-^(х,.’)):

/(х) = —--------------------------------------------------------------------£-шп, (28)

1=1

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

Задача была решена с использованием разработанного программного комплекса ИоЬЕх. Параметры решения: число разверток 4, плотность построения разверток гп = 10. Для решения использовался четырехузловой кластер в технологическом университете г. Делфта.

Была получена оценка оптимума <р*=2.7676 в точке у[0]=8.041, у[1]=4.174, у[2]=10.619, у[3]=2.748, у[4]=9.857, у[5]=8.432, у[6]=9.447, у[7]=7.709, у[8]=8.978, у[9]=9.35, у[10]=8.881 (значения округлены до 10~3).

Расчет занял 27 часов, при этом значение функционалов задачи было посчитано 4 297 + 4 415 + 4 236 + 4 266 = 17 214 раз.

Расчеты, проведенные специалистами технологического университета г. Делфта для колеса оптимизированного профиля, показали, что его ресурс возрос до 120 тыс. км пробега (более чем в пять раз по сравнению с колесом оригинального профиля), а максимально допустимая скорость - с 40 до 60 м/сек.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

1. Сысоев А.В. Об одной информационно-алгоритмической модели процесса параллельного глобального поиска // Вестник ННГУ. Математическое моделирование и оптимальное управление. - Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2011. Вып. 3(2). С. 304-311.

2. Сысоев А.В. О построении семейства множественных разверток на основе кривых Пеано для параллельного решения задач глобально-оптимального поиска // Известия вузов. Приборостроение. Изд-во СПбГУ ИТМО, 2011. Вып. 10. С. 100-102.

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

3. Сысоев А.В. О проблеме расчета функционалов в программных системах глобальной оптимизации // Труды Всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования». - М.: МГТУ им. Н.Э. Баумана, 2005. С. 57.

4. Сидоров С.В., Сысоев А.В. Использование чисел расширенной точности в реализации индексного метода поиска глобально-оптимальных решений // Материалы пятого Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах». - Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2005. С. 208-212.

5. Виноградов Р.В., Гергель В.П., Сысоев А.В. Визуализация вычислений в процессе решения задач глобально-оптимального выбора // Материалы конференции «Технологии Microsoft в теории и практике программирования». - Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2006. С. 42-45.

6. Гергель В.П., Рябов В.В., Сысоев А.В. Алгоритмы принятия глобальнооптимальных решений и их модификации // Материалы конференции «Технологии Microsoft в теории и практике программирования». - Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2006. С. 266-269.

7. Гергель В.П., Сидоров С.В., Сысоев А.В. О распараллеливании индексного метода поиска глобально-оптимальных решений // Материалы конференции «Технологии Microsoft в теории и практике программирования». - Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2006. С. 273-276.

8. Гергель В.П., Субботина Е.В., Сысоев А.В. Способы организации поисковой информации в программной системе параллельного решения задач глобальнооптимального выбора // Материалы конференции «Технологии Microsoft в теории и практике программирования». - Нижний Новгород: Изд-во Нижегородского гос. унта, 2006. С. 284-288.

9. Гергель В.П., Сысоев А.В. О реализации параллельной версии индексного метода поиска глобально-оптимальных решений в многомерных задачах оптимизации в программном комплексе «Абсолют Эксперт» // Труды всероссийской конференции «Научный сервис в сети Интернет: технологии параллельного программирования». -М.: Изд-во МГУ, 2006. С. 115-118.

10. Сидоров С.В., Сысоев А.В. Реализация схемы остановки и возобновления счета в параллельном индексном методе поиска глобально-оптимальных решений // Материалы шестого Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах». -Санкт-Петербург, 2007. С. 159-163.

11. Сидоров С.В., Сысоев А.В. Общая схема реализации остановки и

возобновления счета индексного метода поиска глобально-оптимальных решений // Материалы конференции «Технологии Microsoft в теории и практике программирования», Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2007. С. 259-263. '

12. Рябов В.В., Сидоров С.В., Сысоев А.В. Интерактивное управление параллельными вычислениями при решении задач многомерной многоэкстремальной оптимизации // Материалы седьмого Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах», Нижний Новгород, 2007. С. 294-298.

13. Рябов В.В., Сидоров С.В., Сысоев А.В. Эффективные параллельные алгоритмы и программные средства поиска глобально-оптимальных решений в многомерных многоэкстремальных задачах // Материалы седьмого Международного

научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах», Нижний Новгород, 2007. С. 302-305.

14. Баркалов К.А., Рябов В.В., Сидоров С.В., Сысоев А.В. Об опыте решения задач многоэкстремальной оптимизации на высокопроизводительных кластерных системах // Материалы XI всероссийской научно-технической конференции «Аэрокосмическая техника, высокие технологии и инновации», Пермь, 2008. С. 36-39.

15. Казаков А.О., Сысоев А.В. Структуры хранения данных в программной системе параллельного поиска глобально-оптимальных решений Global Expert // Материалы Девятой международной научно-практической конференции-семинара «Высокопроизводительные параллельные вычисления на кластерных системах». -Владимир, 2009. С. 196-201.

16. Сысоев А.В., Сысоева Т.А. Повышение эффективности реализации индексного метода решения задач глобальной оптимизации // Материалы XI всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах». - Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2011. С. 306-308.

Подписано в печать 23.01.2012 г. Формат 60x84 1/16. Бумага офсетная. Печать цифровая.

Уел. печ. л. 1. Заказ № 29. Тираж 100 экз.

Отпечатано с готового оригинал-макета в РИУ ННГУ им. Н.И. Лобачевского.

603000, г. Нижний Новгород, ул. Б. Покровская, 37

61 12-5/2227

Нижегородский государственный университет им. Н.И. Лобачевского

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

Сысоев Александр Владимирович

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

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

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

Руководитель:

Гергель Виктор Павлович, д.т.н., профессор

Нижний Новгород 2011

СОДЕРЖАНИЕ

ВВЕДЕНИЕ....................................................................................................................................

1. ПАРАЛЛЕЛЬНЫЕ ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА ГЛОБАЛЬНО-ОПТИМАЛЬНЫХ РЕШЕНИЙ.......................................................................................9

1.1. Математическая модель объекта глобально-оптимального выбора............9

1.1.1. Модель объекта.....................................................................................................ю

1.1.2. Функциональные ограничения.........................................................................12

1.1.3. Частичная вычислимость функционалов задачи.........................................12

1.1.4. Векторный критерий эффективности................................................................13

1.1.5. Понятие оптимального решения......................................................................13

1.1.6. Область применимости.......................................................................................15

1.1.7. Необходимость параллельных вычислений при решении задач рационального выбора........................................................................................16

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

1.2.1. Содержательная постановка задачи...............................................................18

1.2.2. Математическая модель....................................................................................19

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

1.3.1. Сведение многокритериальной задачи к семейству однокритериальных задач........................................................................................................................22

1.3.2. Сведение многомерной задачи к семейству одномерных задач -многошаговая схема..........................................................................................23

1.3.3. Сведение многомерной задачи к семейству одномерных задач -редукция размерности на основе кривых Пеано...........................................24

1.3.4. Параллелизм на основе множественной развертки......................................26

1.3.5. Модифицированная множественная развертка............................................28

1.3.6. Характеристическая представимость методов.............................................31

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

2. ИНФОРМАЦИОННО-АЛГОРИТМИЧЕСКАЯ МОДЕЛЬ ПРОЦЕССА ПАРАЛЛЕЛЬНОГО ГЛОБАЛЬНОГО ПОИСКА.....................................................38

2.1. Моделирование процесса параллельного глобального поиска....................40

2.1.1. Модель объекта исследований.........................................................................40

2.1.2. Поисковая информация и оптимизационные данные.................................43

2.1.3. Общая схема процесса глобального поиска.................................................46

2.1.4. Параллельные вычисления в процессе глобального поиска......................47

2.2. Моделирование информационного обеспечения методов параллельного

глобального поиска.................................................................................................................

2.2.1. скаляризация векторного критерия.................................................................51

2.2.2. Учет ограничений.................................................................................................54

2.2.3. Редукция размерности.........................................................................................55

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

2.3. Моделирование информационного обеспечения процесса параллельного

глобального поиска.................................................................................................................

2.3.1. Информационная модель состояния поиска.................................................57

2.3.2. Структуры представления оптимизационных данных................................59

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

2.4.1. Блочное представление матрицы состояния поиска...................................61

2.4.2. Информационная поддержка решающих правил алгоритмов глобального поиска.......................................................................................................................

2.4.3. Система страничной организации памяти.....................................................68

2.4.4. Выбор структуры хранения поисковых данных.............................................73

2.4.5. Параллельные вычисления при информационном обеспечении процесса глобального поиска.............................................................................................73

2.5. Общая схема процесса параллельного глобального поиска.........................74

3. РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА ПАРАЛЛЕЛЬНЫХ

ВЫЧИСЛЕНИЙ В ЗАДАЧАХ ГЛОБАЛЬНО-ОПТИМАЛЬНОГО ВЫБОРА....76

3.1. Принципы организации программного комплекса............................................77

3.1.1. Назначение и основные задачи.........................................................................77

3.1.2. Высокоуровневая архитектура программного комплекса.........................78

3.1.3. Программные компоненты системного уровня............................................80

3.1.4. Программные компоненты прикладного уровня...........................................84

3.1.5. Последовательный и параллельный режимы работы....................................86

3.1.6. Способы постановки задачи оптимизации....................................................88

3.1.7. Использование чисел расширенной точности...............................................89

3.1.8. Эффективность программного комплекса.....................................................90

3.1.9. Требования к аппаратному и программному окружению...........................91

3.2. Реализация программного комплекса...................................................................92

3.2.1. Общие принципы реализации программного комплекса.............................92

3.2.2. Системный уровень - библиотека классов.....................................................92

3.2.3. Принципы реализации параллельного индексного метода......................103

3.2.4. Прикладной уровень - консольный решатель..............................................103

3.2.5. Прикладной уровень - решатель в виде динамически подключаемой библиотеки..............................................................................................................

3.2.6. Прикладной уровень - решатель в виде оконного приложения................105

4. ОЦЕНКА ЭФФЕКТИВНОСТИ ПРОГРАММНОГО КОМПЛЕКСА.................109

4.1. Методика применения программного комплекса............................................109

4.1.1. Создание постановки задачи в виде динамически подключаемой

библиотеки...........................................................................................................110

4.1.2. Запуск консольного решателя........................................................................113

4.1.3. Постановка задачи в системе управления кластером Microsoft НРС Server 2008 ..........................................................................................................115

4.1.4. Постановка задачи в GUI-решателе...............................................................117

4.1.5. Эффективность использования чисел расширенной точности................120

4.1.6. Схемы оценки ускорения при решении задач оптимизации.....................121

4.2. Решение тестовых задач............................................................................................122

4.2.1. Примеры решения задач безусловной оптимизации...................................122

4.2.2. Пример решения задачи условной оптимизации.........................................124

4.3. Решение прикладных задач......................................................................................126

4.3.1. Задача идентификации параметров в модели экономики........................126

4.3.2. Оптимизация профиля колеса для рельсовых видов транспорта............128

ЗАКЛЮЧЕНИЕ.......................................................................................................................131

ЛИТЕРАТУРА.........................................................................................................................132

ПРИЛОЖЕНИЕ 1. АКТ ВНЕДРЕНИЯ...............................................................................144

ПРИЛОЖЕНИЕ 2. ФРАГМЕНТЫ ИСХОДНЫХ ТЕКСТОВ ПРОГРАММНОГО

КОМПЛЕКСА................................................................................................................145

ВВЕДЕНИЕ

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

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

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

5

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

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

Достижение указанной цели предполагает решение следующих задач:

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

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

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

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

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

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

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

• Эффективная асинхронная параллельная модификация индексного метода решения задач оптимизации.

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

Практическая ценность работы. Исследования по теме диссертации выполнялись при поддержке Российского Фонда Фундаментальных Исследований (грант № 04-01-89002-НЕЮ_а), Совета по грантам Президента Российской Федерации (грант № МК-1536.2009.9) и Федерального агентства по науке и инновациям (ФЦП «Научные и научно-педагогические кадры инновационной России», госконтракт № 02.740.11.5018). Результаты работы использовались при реализации совместного исследовательского проекта РФФИ и Нидерландской организации по научным исследованиям (the Netherlands Organization for Scientific Research - NWO); номер проекта NWO: 047.016.014. Практическая ценность работы определяется созданием программного комплекса параллельных вычислений для решения сложных существенно многоэсктремальных многомерных задач глобально-оптимального выбора.

Разработанный программный комплекс GlobEx реализован на языке С++ в среде Microsoft Visual Studio 2005, внедрен в опытную эксплуатацию.

Научные результаты и положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Международный научно-практический семинар «Высокопроизводительные вычисления на кластерных системах» (Нижний Новгород, 2005, 2007, 2011, Санкт-Петербург, 2006, Владимир, 2009), Всероссийская конференция «Научный сервис в сети Интернет» (Новороссийск, 2006), Всероссийская научно-техническая конференция «Аэрокосмическая техника, высокие технологии и инновации» (Пермь, 2008), научно-техническая конференция «Технологии Майкрософт в теории и практике программирования» (Москва, 2005, Нижний Новгород, 2006-2008), на научных конференциях и семинарах Нижегородского государственного университета.

По теме диссертационной работы опубликовано 16 печатных работ, из них 2 статьи в научных журналах, рекомендованных ВАК.

Диссертационная работа состоит из введения, 4 глав, заключения, списка использованной литературы из 118 наименований и приложений. Основная часть работы изложена на 131 странице текста, содержит 34 рисунка и 6 таблиц.

1. ПАРАЛЛЕЛЬНЫЕ ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА ГЛОБАЛЬНО-ОПТИМАЛЬНЫХ РЕШЕНИЙ

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

1.1. Математическая модель объекта глобально-оптимального выбора

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

9

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

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

1.1.1. Модель объекта

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

Пусть объект исследования характеризуется набором параметров

определенных таким образом, что уменьшение значений характеристик соответствует лучшему выбору. Предполагается, что: 1. Координаты вектора у= [ух, ... могут непрерывно изменяться в

заданных пределах, определяемых векторами начала и конца

(1.1)

и вектор-функцией характеристик

(1.2)

а = {ах,...,аы), Ъ = (ЬХ,...,ЬМ), (1-3)

которые задают гиперинтервал

£> = [у^-.а^у^ Ъ{ , 1< /< ТУ}. (1.4)

2. Кортеж и принимает значения в виде набора дискретных параметров из заданного множества

и = ихх...хим, (1-5)

где Ц= {ип, ...,и1к), 1 <1<М.

Разрешенные сочетания ие11 описываются путем задания отображения

и:т->и, 1 <т<Б, (1.6)

сопоставляющего номеру т допустимый кортеж и(т)&17 (т.е. все

допустимые сочетания дискретных параметров перенумерованы числами т от 1 до 5).

3. Каждая характеристика wi(y,u(тf), 1<1<п, 1 <г<£ является

липшицевой функцией с соответствующей константой Липшица К1Т, которая может быть не задана.

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