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

005001250

Елсаков Сергей Михайлович

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

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

1 О НОЯ 2011

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

Челябинск - 2011

005001250

Работа, выполнена в Южно-Уральском государственном университете.

Научный руководитель — доктор технических наук,

профессор Ширяев Владимир Иванович.

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

профессор Панюков Анатолий Васильевич;

Защита состоится 29 ноября 2011 г., в 15 часов, на заседании диссертационного совета Д 212.298.14 при Южно-Уральском государственном университете по адресу: 454080, г. Челябинск, пр. Ленина, 76, ауд. 1001.

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

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

доктор физико-математических наук, профессор Жадан Виталий Григорьевич.

Ведущая организация — Нижегородский государственный

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

Ученый секретарь диссертационного совета, к. ф.-м. н., доц.

А. В. Келлер

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

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

Для численного решения подобных задач применяются методы многоэкстре-альной (глобальной) оптимизации. Исследованию численных методов миогоэкс-ремалыюй оптимизации посвящены работы К. А. Баркалова, Д. И. Батищева, . П. Булатова, В. П. Гергеля, А. И. Голикова, С. Ю. Городецкого, В. А. Гришаги-а, X. М. Гутмана (Н.-М. Gutmarin), Д. Р. Джонса (D. R. Jones), Ю. Г. Евтушенко, . Г. Жадана, А. А. Жиглявского, А. Г. Жилинскаса, Д. Е. Квасова, А. Г. Корот-енко, А. В. Орлова, П. М. Пардалоса (Р. М. Pardalos), Я. Пинтера (J. D. Pinter), \ А. Пиявского, М. А. Посыпкина, J1. А. Растригина, А. И. Рубана, Я. Д. Сер-еева, А. С. Стрекаловского, Р. Г. Стронгина, А. Г. Сухарева, X. Туя (Н. Тиу), . Флудаса (С. Floudas), Р. Хорста (R. Horst) и многих других.

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

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

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

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

В соответствии с поставленной целью решались следующие задачи:

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

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

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

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

Методы исследования. При выполнении исследования применялись теория алгоритмов, теория локальной оптимизации, теория многоэкстремальной оптимизации, методы интерполяции, объектно-ориентированное программирование.

Научная новизна.

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

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

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

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

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

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

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

овании систем, идентификации нелинейных моделей и т.д. В рамках работы со-дан программный комплекс, реализующий разработанные алгоритмы и позволя-щий тестировать однородные алгоритмы с различными моделями целевых функ-щй. На программный комплекс получено свидетельство о государственной реги-трации программы для ЭВМ №2010616850 от 14.10.2010. Исследования выполня-ись при поддержке грантов губернатора Челябинской области (115.07.06-05.АХ, 65.07.06-08.БХ), гранта г. Челябинска «Лучшая инновационная идея года» 2010 г.

Апробация работы. Результаты работы докладывались на международных 1 всероссийских конференциях: ХШ-й и XIV-й Всероссийских конференциях «Магматическое программирование и приложения»(г. Екатеринбург, 2007, 2011), меж-ународной конференции «Алгоритмический анализ неустойчивых задач», посвя-ценной 100-летию со дня рождения В. К. Иванова (г. Екатринбург, 2008), междуна-одной конференции «Оптимизация и приложения (ОРТ1МА-2009)»(Черногория, . Петровац, 2009), VI Московской международной конференции по исследованию пераций (г. Москва, 2010), а также на конференциях: 38 молодежной школс-кон-еренции «Проблемы теоретической и прикладной математики»(г. Екатеринбург,

007), «Технологии Microsoft в теории и практике программирования»^. Нижний овгород, 2007, 2010), XXVI конф. памяти H.H. Острякова (г. Санкт-Петербург,

008), I и II научной конференции аспирантов и докторантов ЮУрГУ (г. Чсля-инск, 2009, 2010). Результаты работы также докладывались на семинаре иод ру-оводством акад. Евтушенко Ю. Г. (ВЦ РАН, г. Москва, 2011) и на семинаре под уководством проф. Гергеля В. П. (ННГУ, г. Нижний Новгород, 2011).

Публикации. Основные результаты диссертации опубликованы в 28 научных заботах, в том числе 4 — в изданиях, рекомендованных ВАК [1-4]. В опубликооан-ibix статьях В. И. Ширяеву принадлежит общая постановка задачи, а С. М. Елсако-у - все полученные результаты. Из остальных работ, выполненных в соавторстве, ! диссертацию включены только те результаты, которые были получены лично . М. Елсаковым, и но затрагивают интересов других соавторов.

Структура и объем работы. Работа состоит из введения, четырех глав, за-лючения, библиографии и одного приложения. Объем диссертации 123 страницы, бъем библиографии 116 источников.

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

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

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

В и. 1.1 рассматриваются постановки задач многоэкстремальной оптимизации, оль дополнительной информации при решении задач многоэкстремальной опти-изации. Отдельное внимание уделено липшицевой оптимизации и условию Лип-

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

/ (х) -4 min, X С Rd, Х= {х € Kd:0 < Xj < 1, j=Xd] , (1

где / (х): Rd -> R — целевая функция, X — допустимое множество, d ■■ размерность задачи. Целевая функция f(x) удовлетворяет условию Липшиц; ¡/ (ii) - / {х2)\ < L ||ti - х2\\, Vxi,x2 е X, где L — константа Липшица (0 < < L < оо), ||-|| — евклидова норма.

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

В и.2.1 вводится новый класс однородных алгоритмов оптимизации. Пуст {xi}i=l — последовательность точек допустимого множества X, в которых ocj ществляется вычисление значений целевой функции f(x). Будем говорить, чтс алгоритм относится к классу однородных алгоритмов многоэкстремальной опчч мизации, если одновременно выполнены три условия:

1. Алгоритм является однородным, т.е. для любых двух целевых функций, р«т ли чающихся на константу, последовательности точек испытаний {ж,}-Lj совиад; ют.

2. На каждой итерации алгоритма определены функцн mk(x)=m(x,xij(xi),...,xk,f\xk)) и sk(x) ~s{x,xuf{x1), ...,хк, f(xk)), кап. рыс удовлетворяют следующим условиям:

AI) mk(xj) =f(xi)1i=l,t,

А2) sk(xi) = 0, i=l,fc; _ A3) sk(x) >0, x Ф Xi, i=l,k;

A4) mk(x), sk(x) — липшицевы.

3. Алгоритм представлен в следующем виде: _

Шаг 1. Выбрать начальные точки Xi 6 X, г—1,М. Вычислить / (х{), г -1 ,М. Положить к—М.

Шаг 2. Построить функции тк(х) и S/t(o;).

Шаг 3. Вычислить

3^+1= arg min P(mk(x),sk(x)), (2

e P(mk(x),sk(x)) :R2 -> K — некоторая функция, mt(i), sk(x) — функции, удо-летворяющие условиям Al)-A4).

Шаг 4. Вычислить значение f (xk+i ), положить к=к+1. Шаг 5. Если выполнено некоторое условие <р останова алгоритма, то завер-тть алгоритм, иначе вернуться на Шаг 2. ■

Предлагаемый класс однородных алгоритмов имеет следующие особенности о сравнению с другими классами алгоритмов:

1. Рассматриваются многомерные алгоритмы оптимизации целевых функций.

2. Алгоритмы рассматриваются вне зависимости от метода разбиения допу-тимого множества.

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

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

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

Несмотря на вышеприведенные отличия, класс однородных алгоритмов пересе-ается со многими другими классами алгоритмов: характеристическими, типично-редставимыми, «divide-the-best», методы ветвей и границ, методы неравномерных окрытий, методы на основе поверхностей отклика.

Введем дополнительные условия на модель целевой функции: 5) тп {х, хъ f (ii) + с,..., хк, / (хк) + c) = m(x,xi,f (zi) ,...,xk,f (хк)) + с, Е N, с 6 К;

G) s(x,xuf(xi) + с, ...,xk,f(xk) + с) = s(x,xi, f(xi), ...,хк, f(xk)), к е N, с £ К. И наряду с задачей (2), рассмотрим задачу

(m*,5*)=arg min P(m,s), (3)

(m,s)eSM

де rn* = mk(xk+i), s* = sk(xk+i), SM = {(ra,s)elxl\l_: m = mk{x), • = sk(x), x € X}. Доказываются следующие теоремы.

сорема 1. Если существует двао/сды непрерывно дифференцируемая функция (m,s), такал что

) для любых функций тк(х) и sk(x), удовлетворяющих условиям Al)-A6), выполняется условие arg min Р (тк (х), sk (х)) = arg min P(m<; (х) 4- с, «¿(х)),

х£Х х£Х

>) для любой точки (m*,s*) существуют функции т*к(х) и sk(x), удовлетворя-ощие условиям А1)-А6), такие, что решение задачи (3) достигается в точке m',s*),

по тогда выполняется arg min Р (mk (х), sk (х)) = arg min \Cmk (x) + p(sk (x))] ,

xGX z£X

de С — const, p(s) — двао/сды непрерывно дифференцируемая функция.

Георема 2. Для того чтобы миоо/сество предельных точек последовательности испытаний {^i}^, порождаемых однородным алгоритмом с критерием

P(mk(x),Sk(x)) = Cmk(x) + p(sk{x)), совпадало с множеством глобальных jш

иимумов липшицевой функции f(x) с константой Липшица L на компакте Л

достаточно, чтобы функция р(х) была липшицева и mm(P{mk(x),Sk(x))) _

хеХ

< min max (/(x¡) — К \\х — х,:||), где К — const и К > L. хех i=itk

Теорема 3. Если для функций rrik{x) и sk(x) выполняются условия Al)-A6) i

дополнительно выполняется условие

Al) sk(x)> mm ||х - , i=l,k

то множество предельных точек последовательности испытаний {Х{п( рождаемых алгоритмом с функцией Р (sk{х),тк{х)) = mk(x) — 2Ksk(x), гд К > L + Lm, а Lm — константа Липишица для функциитк(х), будет совпадат с множеством глобальных минимумов липшицевой функции f(x) с констанпич Липшица L.

Теорема 4. Если в качестве условия <р останова алгоритма выбрать услови

ттЦх; — ifc+i|| < Е, где хк+\ — точка следующего испытания целевой функции i=i,fc

то однородный алгоритм обеспечит решение задачи (1) с точностью по am чеиию целевой функции не хуже, чем L (Lp + Lm) £/ (К — L), где L — конспии та Липшица целевой функции, a Lp и Lm — константы Липшица для функци p(sk(x)) и тк(х) соответственно.

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

Пусть допустимое множество X разбито на подмножества X — Xi UX2 U • • • I UХм и количество точек испытаний внутри каждого подмножества отличио о нуля. Обозначим границу множества X как ЭХ, а множеств Х{ как дХ,. Введе.-расстояние до.внутренней границы подмножества как Pi{x) = min ||г —

у£дХ\дХ

Теорема 5. Пусть функции т\(х), s'k(x), г = 1,М, построенные по резулыт там испытаний, которые располагаются только внутри подмножесгпваХ(, уд< влетворяюгп условиям А1)-А7), и для разбиения допустимого множества сущ сгпвует 6 > 0 такая, что для любой точки х 6 X, которая принадлежит Сн лее чем одному подмножеству Х1: выполняется pi(x) > 5. Тогда функци

i-.xe.Xi

тк(х) = £ ■ Pi(x)mi(x) ) / £ Pi{x), sk(x) = ( £ Pi{x)s[{x) / £ M* \i-.xe Xt J i:x€X, \i:x€Xi J i-.xeXi

■удовлетворяют условиям AI)-AI).

Теорема 6. Если на к-м шаге не удалось найти точку xk+i такую, чтобы вь полнилось условие

Рк {хш) < min f (xi) - £, (4

то задача многоэкстремалъпой оптимизации (1) решена с точностью £ по значению целевой функции.

Предлагается алгоритм совместного оценивания константы Липшица и поиска точки следующего испытания Xk+i, удовлетворяющей условию (4). В качестве оценки константы Липшица L используется выражение L — = гmax\f(xj) — f(xi)\/ \\xj — Xi\\, где г — коэффициент достоверности. Если i/j

k + 1 — 2d+1 < argmin/(a;i), то в качестве текущего коэффициента достоверно-i=l,fc

сти используется минимальное значение из ряда г = 0,0.1,... 3.0, при котором локальный поиск из arg min_J(xi) позволяет найти точку, в которой выполняет-

хi, i—l,k

ся условие (4); в противном случае используется текущее значение коэффициента достоверности, который изначально равен 1.0. Локальный поиск запускается из точек, в которых модель целевой функции не соответствует целевой функции, что выражается значением величины |— / (z*) ¿j, а также из то-

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

В п. 2.2 рассматриваются различные модели целевых функций для однородных алгоритмов многоэкстремальной оптимизации. Для функции т*(х) предложены: кусочно-линейная функция на основе триангуляции Делоне (Д), кубический RBF-сплайн (К), логарифмический RBF-сплайн (Л), функция на основе обычного кригинга (О). Для функций Sk(x) предложены: кусочно-квадратичная функция на основе триангуляции Делоне (Д), функция расстояния до ближайшей точки испытания (Р), гладкая аппроксимация функции расстояния до точки ближайшего испытания (Г(1,3,5) — число указывает значение используемого параметра), функция на основе простого кригинга (П). Для всех моделей доказано, что они удовлетворяют условиям А1)-А7).

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

числениями, А — алгоритм с несущественными вспомогательными вычислениями, — количество обращений к целевой функции алгоритмом Л, Ne — количество обращений к целевой функции алгоритмом В, Tt — время, необходимое для однократного вычисления целевой функции, Т^ — время, затрачиваемое на вспомогательные вычисления алгоритмом В, а время, затрачиваемое на вспомогательные вычисления алгоритмом Л, будем полагать нулевым, и Tt > TJ (Nд — Ng), тогда суммарное время, затраченное алгоритмом В, меньше, чем суммарное время, затраченное алгоритмом Л.

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

В п. 3.1 описываются условия проведения вычислительных экспериментов. Для тестирования были выбраны распространенные тестовые функции: из набора Dixon-Szego (9 тестовых функций), предложенные В. А. Гришагиным (100 тестовых функций), генерируемые генератором GKLS (10 наборов по 100 тестовых функций в каждом), задача оптимизации конфигурации атомного кластера с потенциальной энергией Морса, задачи размещения радиомаяков в разностно-дальномерной системе посадки, задачи идентификации нелинейной динамической модели. Эксперименты выполнялись на кластере «СКИФ-УРАЛ»: процессоры Intel Xeon Е5472 (4 ядра по 12 Гфлопс каждое), каждому процессу выделялось отдельное ядро (кроме результатов в п. 3.8).

В п. 3.2 приведены результаты тестирования моделей липшицевых целевых функций. Были построены 24 однородных алгоритма многоэкстремальной оптимизации с различными моделями целевых функций. Сравнение проводилось на тестовых функциях В. А. Гришагина, наборе Díxon-Szego, двухмерном наборе тестовых функций GKLS. Количество испытаний для всех алгоритмов не превышало 1000.

В табл. 1 представлена сумма (по трем наборам Таблица 1

тестовых функций) количества алгоритмов на OCHO- Ранжирование моделей

ве моделей целевых функций, которые в среднем _целевых функций

смогли решить тестовую задачу за меньшее коли- 771* (я)

чество испытаний, чем алгоритм на основе рассмат- Д К Л О

риваемой модели целевой функции, которая опреде- д 46 13 23 32

лялась соответствующим выбором функций т^х) Р 42 6 14 27

и $к(х). Использование этого показателя позволя- н Г1 61 26 38 62

ет сравнивать модели целевых функций на различ- « п 48 20 17 36

ных наборах тестовых функций с учетом того, что гз 64 27 32 52

на одном наборе в среднем может требоваться зна- Г5 53 13 22 54

читсльно больше испытаний, чем на другом. Наи-

лучший результат показал Однородный Алгоритм с использованием Кубического

RBF-сплайна и Расстояния до ближайшей точки испытания (ОАКР). По количеству решенных задач и по среднему времени решения задачи оптимизации алгоритм ОАКР также оказался лучшим по сравнению с алгоритмами на основе других моделей.

В п. 3.3 приводятся результа- 80% ты сравнения ОАКР с алгорит- 60% мами, использующими множественные оценки константы Липшица (DIRECT, DIRECT!, алгоритм на

40% 20% 0%

........................... !>■............... п .....-.............щ.............СП.............. ..............OJ-

Nvl SS £ Ш $

шшт

Q '5

У £

I Й

СП U

Sp

О 3

u-i ° g 3

__yjtiSoyi^o^i

Шс gg oc 13 с В с ш5

О Максимальное число испытаний Я Среднее число испытаний

основе адаптивных диагональных кривых). Использование алгоритма ОАКР для решения шести тестовых задач из девяти в наборе Dixon-Szego потребовало наимень- P[)c i. Снижение количества испытаний при исполь-шего числа испытаний по сравне- зоваиии алгоритма ОАКР по сравнению с алгорит-нию С другими алгоритмам. На те- мом на основе адаптивных диагональных кривых стовых функциях GKLS (рис. 1) использование алгоритма ОАКР позволило сократить среднее число испытаний на 31-72% (в зависимости от набора тестовых функций) относительно наилучшего из остальных алгоритмов. Согласно модели, предложенной в п. 2.4, и ко результатам экспериментов в п. 3.3 алгоритм ОАКР целесообразно применять для целевых функций, время вычисления которых более 278 мс (« 3,3 ■ 10° операций с плавающей запятой).

В п. 3.4 сравнивается алгоритм ОАКР с алгоритмами на основе поверхностей отклика (rbfSolve, EGO, ARBF). На тестовых функциях Dixon-Szego применение алгоритма ОАКР потребовало меньшего количества обращений к целевой функции на четырех тестовых функциях из девяти. Использование алгоритма ОАКР позволило в среднем использовать на 13% меньше испытаний (табл. 2) по сравнению с алгоритмами rbfSolve, EGO и ARBF на тестовых функциях В. А. Гришагина. При этом только применение алгоритма ОАКР позволило решить 100% тестовых задач. Согласно модели, предложенной в п. 2.4, и по результатам экспериментов в п, 3.4 алгоритм ОАКР целесообразно применять для целевых функций, время

вычисления которых более 16 мс (и 1,9 ■ 108 операций с плавающей запятой).

Таблица 2

Результаты сравнения алгоритма ОАКР с алгоритмами из пакета TOMLAB па тестовых функциях В. А. Гришагина

Критерии сравнения ОАКР RBF1 RBF2 EG01 EG02 ARBF

Средн. кол-во испытаний 76,92 286,82 286,67 "ЩГ"1 38,09 87,99

Макс, кол-во испытаний 349 1000 1000 127 97 225

Средн. время опт им., с 0,17 2563,40 1629,96 81,54 36,20 521,37

Доля решенных задач, % 100 89 90 40 38 98

В п. 3.5 было проведено сравнение алгоритма ОАКР с алгоритмами, реализованными в программных комплексах 1030 и ЬСО. Для сравнения были выбраны

□ LG02 И LG03 ■ LG04

60%

20%

тестовые функции В. А. Гришагина и GKLS. Использование алгоритма ОАКР позволило решить 100% предложенных задач, использование алгоритмов из ПК IOSO и LGO позволило решить от 8% до 89% предложенных задач (в зависимости от набора тестовых функций). Применение алгоритма ОАКР также позволило снизить среднее число обращений к целевой функции на 66-91% (в зависимости от набора тестовых функций) по сравнению с наилучшим из алгоритмов IOSO и LGO, с помощью которых было решено более 50% функций в наборе тестовых функций (рис. 2, отсутствие столбца в диаграмме означает, что алгоритм решил менее 50% предложенных задач). Согласно модели, предложенной в п. 2.4, и по результатам экспериментов в п. 3.5 алгоритм ОАКР целесообразно применять для целевых функций, время вычисления которых более 326.4 мс 3,9 • 109 операций с плавающей запятой).

В п. 3.6 представлено сравнение алгоритмов ОАКР, IOSO и OPTIMUM по результатам решения трех задач оптимизации размещения радиомаяков (одна задача размерности два и две задачи размерности четыре) и трех задач идентификации нелинейных систем (одна задача размерности три и две задачи второй размерности). Количество испытаний при решении задач о размещении ра- Рис 2 Снижение среднего количества обращений диомаяков не превышало 1000, при к целевой функции для различных наборах тесто-решении задач идентификации — вых функций при использовании алгоритма ОАКР 200. Рандомизированный алгоритм по фавие.шю с алгоритмами LGO OPTIMUM запускался десять раз. Алгоритмы упорядочивались по минимальному найденному значению целевой функции за все испытания. Алгоритм, с помощью которого было найдено минимальное значение, получал ранг 1, остальные алгоритмы получали последовательные ранги в соответствии с найденными минимальными значениями. На рис. 3 представлен суммарный ранг алгоритмов по всем шести задачам. Во втором сравнении (табл. 3) рассматривались алгоритмы ОАКР, IOSO и OPTIMUM

(медианное значение найденного минимума целевой функции из десяти запусков).

* х а '5

d « г i s з § ;

i. 3 ^Q-SiO ^ а. ^ о ^а^о а. о

15 с о 5 " = а 5 ° с о 5 ° с о 5

Рис. 3. Суммарный ранг алгоритмов

Таблица 3

Ранги алгоритмов при решении задач оптимизации размещения радиомаяков и идентификации нелинейной модели

Алгоритм 4 5 6 Прямое Обратное Обратное Сумма

РМ РМ РМ время время N = 20 время N = 100

ОАКР 1 2 1 1 1 1 7

IOSO 3 1 2 2 2 3 13

OPTIMUM 2 3 3 3 3 2 16

Сравнение алгоритмов ОАКР, IOSO и OPTIMUM показало, что алгоритм О АКР оказался наиболее эффективным при решении задачи оптимизации расположения радиомаяков в разностно-дальномерной системе посадки JIA и в задаче идентификации нелинейной динамической системы.

В п. 3.7 для решения задач высокой размерности представлена модификация алгоритма ОАКР, которая заключается в том, что для решения вспомогательной задачи используется только алгоритм локальной оптимизации и первоначальные точки выбираются согласно латинского гиперкуба (число точек — 3d, где d — размерность пространства). Модифицированный алгоритм сравнивался с алгоритмом на основе метода неравномерных покрытий на тестовой функции, описывающей потенциал Морса для кластера атомов в трехмерном пространстве. Рассматривались две серии тестовых задач: минимизировалась непосредственно потенциальная энергия для размерностей 6, 9 и 12 и минимизировалось значение, получаемое алгоритмом локальной оптимизации, который запускался из точки, определяемой алгоритмом многоэкстремальной оптимизации для размерностей 6, 9, 12, 15, 18, 21, 24, 27, 33, 45. Число испытаний в первой серии задач было ограничено 5000, во второй — 200. Все алгоритмы ранжировались по числу затраченных испытаний |для поиска глобального минимума с заданной точностью. Алгоритм исключался из ранжирования, если его применение не позволило найти глобальный минимум. Алгоритм ОАКР получил средний ранг 2.5, модифицированный алгоритм ОАКР — 1.2, наилучший из алгоритмов на основе метода неравномерных покрытий.....2.5.

В п. 3.8 рассматривается параллельная реализация алгоритма ОАКР. Задача (1) декомпозируется на Р подзадач f(x) —> min, где Р — число доступных ядер,

]Х = Хх U Х2 и... и АГр, и Xi П Xj = dXi П dXj, если г ф j, г, j = VP. Каждая (подзадача решалась алгоритмом ОАКР на отдельном ядре. Реализация этого алгоритма предусматривает завершение всех процессов, если хотя бы один нашел (глобальный минимум. Тестирование алгоритма (рис. 4) на различном числе ядер на тестовых функциях GKLS продемонстрировало возможность использование алгоритма ОАКР на многоядерных системах. Сверхлинейное ускорение параллельного алгоритма по времени на «сложном»наборе тестовых функций достигается 'за счет того, что с ростом количества испытаний общее время, затрачиваемое на ¡вспомогательные операции алгоритмом ОАКР, растет квадратично.

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

—О—вШ простой — -Линейное ускорение 512

-О-ЙШ сложный

1 2 4 8 16 32 64 128 256 512 Количество ядер

(а). По среднему количеству итераций -^-бКЦ; простой -О-бКи; сложный

— -Линейное ускорение

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

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

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

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

В приложении А представлено описание задач о размещении радиомаяков и идентификации нелинейной динамической системы.

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

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

5157,4Р)—

Э2Э61119^4656,<

317,6/" гт *

124,.

11,0

✓

-ФГ в 3,9 5,9 '

1 2 4 8 16 32 64 128 256 512 Количество ядер

(б). По среднему времени решения Рис. 4. Ускорение параллельного алгоритма

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

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

3. Разработан однородный алгоритм многоэкстрсмальной оптимизации. Сравнение его с различными алгоритмами многоэкстрсмальной оптимизации на различных тестовых функциях, задаче размещения радиомаяков в разностно-дальномер-ной системе навигации и задаче идентификации нелинейной модели подтвердило высокую эффективность предложенного алгоритма. По результатам вычислительного эксперимента установлено, что область применения предложенного алгоритма — многомерные (размерность до 6) задачи многоэкстрсмальной оптимизации с целевой функцией, время вычисления которой превышает 327 мс (и 3,9 • Коопераций с плавающей запятой). Предложены две модификации алгоритма: для задач высокой размерности (решена задача 45 размерности) и для многоядерных вычислительных систем (продемонстрирована работа на 512 ядрах).

4. Спроектирован и реализован программный комплекс (свидетельство о государственной регистрации программы для ЭВМ №2010616850 от 14.10.2010) для решения задач многоэкстремальной оптимизации и проведения вычислительного эксперимента с однородными алгоритмами многоэкстремальной оптимизации и моделями липшицевых целевых функций.

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

Статьи, опубликованные в ведущих рецензируемых научных журналах, рекомендованных ВАК:

1. Антонов, М.О. Нахождение оптимального расположения радиомаяков в разностно-дальномерной системе посадки летательного аппарата / М.О. Антонов, С.М. Елсаков, В.И. Ширяев // Авиакосмическое приборостроение. - 2005. №11.

С. 41-45.

2. Елсаков, С.М. О многоэкстремальности в задачах оценивания состояния систем детерминированного хаоса / С.М. Елсаков, В.И.Ширяев // Вестник ЮУрГУ. Сер. Компьютерные технологии, управление, радиоэлектроника. - 2009. - №3. С. 37-41.

3. Елсаков, С.М. Однородные алгоритмы многоэкстремальной оптимизации / С.М. Елсаков, В.И.Ширяев // Ж. вычисл. матсм. и матем. физ. - 2010. - №10. С.1727-1740.

4. Елсаков, С.М. Однородные алгоритмы многоэкстремальной оптимизации для целевых функций со значительным временем вычисления значения / С.М. Елсаков, В.И. Ширяев // Вычислительные методы и программирование. -2011. - № 1. С. 52-73.

Другие научные публикации:

5. Елсаков, С.М. Об однородных алгоритмах глобальной оптимизации / С.М.Елсаков, В.И.Ширяев // Информ. бюллетень Ассоциации математического программирования. №11. Конф. «Математическое программирование и приложения». Научн. издание. - Екатеринбург: УрО РАН, 2007. - С. 37-38.

G. Елсаков, С.М. Однородные алгоритмы многоэкстрсмальной оптимизации на основе сплайнов / С.М.Елсаков, В.И.Ширяев // Современные проблемы вычислительной математики и математической физики: Мсждунар. кокф. Москва, МГУ им. М.В.Ломоносова, 16-18 июня 2009 г.: Тез. докл. - М.: Изд. отд. фак. ВМК МГУ им. М.В. Ломоносова: МАКС Пресс, 2009. - С. 49-50.

7. Елсаков, С.М. Алгоритмы многомерной глобальной оптимизации на основе RBF-сплайнов / С.М. Елсаков, В.И. Ширяев // Забабахинские научные чтения: сб. матер. X Мсждунар. конф. 15-19 марта 2010. - Снежинск: Изд-во. РФЯЦ-ВНИ-ИТФ, 2010. С. 292 294.

8. Елсаков, С.М. Однородный алгоритм глобальной оптимизации с использованием вспомогательной модели для целевой функции / С.М. Елсаков, В.И.Ширяев //VI Московская Мсждунар. конф. по исследованию операций (ORM2010). - М.: МАКС Пресс, 2010. С.230-232.

9. Елсаков, С.М. Повышение эффективности однородных алгоритмов многоэкстремальной оптимизации для решения задач с большим временем вычисления значения целевой функции / С.М. Елсаков // Информ. бюллетень Ассоциации математического программирования №12. Конф. «Математическое программирование и приложения». Научн. издание. - Екатеринбург: УрО РАН, 2011. - С. 32-33.

10. Elsakov, S.M. Homogeneous algorithms of global optimization / S.M. Elsakov, V.I. Shiryaev // Abstracts of International conference «Optimization and applications (OPTIMA-2009)». Montenegro: Dorodnicyn computing center of RAS, 2009. -P. 23-24.

11. Elsakov, S.M. Linear Homogeneous Algorithms of Global Optimization / S.M. Elsakov, V.I. Shiryaev // Global Optimization: Theory, Methods & Applications. Series Lecture notes in decision science. Vol. 12. - Hong Kong, London, Tokyo: GlobalLink Publisher, 2009. P. 241-247.

Типография «Два комсомольца»_

Подписано в печать 20.10.2011. Формат 60 х 84 1/16. Печать цифровая. Усл. нсч. л. 0,86. Уч.-изд. л. 1.

_Тираж 100 экз. Заказ 143/249._

Отпечатано в типографии «Два Комсомольца». 454008 г. Челябинск, Комсомольский пр., 2, оф. 207

Введение

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

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

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

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

1.2.2. Алгоритмы многоэкстремалыюй оптимизации без декомпозиции допустимого множества.

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

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

Глава 2. Класс однородных алгоритмов многоэкстремальной оптимизации: алгоритмы и модели целевых функций

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

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

2.1.2. Снижение трудоемкости однородных алгоритмов без потери сходимости.

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

2.2.1. Оценивание значений целевой функции.

2.2.2. Погрешность оценивания значений целевой функции . . 57 2.3. Определение области применения алгоритма многоэкстремальной оптимизации с существенными вспомогательными вычислениями.

Глава 3. Вычислительные эксперименты по сравнению однородных алгоритмов многоэкстремальной оптимизации 65 3.1. Тестирование алгоритмов оптимизации.

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

3.3. Сравнение алгоритма ОАКР с алгоритмами многоэкстремальной оптимизации на основе множественных оценок константы Липшица.

3.4. Сравнение алгоритма ОАКР с алгоритмами многоэкстремальной оптимизации на основе методологии поверхностей отклика

3.5. Сравнение алгоритма ОАКР с алгоритмами программных комплексов IOSO и LGO.

3.6. Сравнение алгоритма ОАКР с алгоритмами программных комплексов IOSO и OPTIMUM при решении задач размещения радиомаяков и идентификации нелинейной модели.

3.7. Тестирование алгоритма ОАКР на задачах оптимизации конфигурации атомного кластера.

3.8. Тестирование параллельной версии алгоритма ОАКР

Глава 4. Программный комплекс HAGO.

4.1. Описание программного комплекса.

4.2. Пример использования ПК HAGO

Актуальность темы диссертационной работы. В настоящее время многие задачи принятия решений можно сформулировать как задачи оптимизации. Такие задачи возникают в самых разных областях науки и техники: проектирование различных систем и материалов [1, 89, 90, 95, 98, 99, 104], идентификация нелинейных моделей [28, 57, 103] и т.д. Трудности численного решения таких задач связаны с отсутствие аналитического описания целевой функции — функции часто задаются алгоритмически. Целевая функция может быть невыпуклой, негладкой, а также может иметь несколько существенных экстремумов, допустимое множество также может быть невыпуклым и, возможно, несвязным. Кроме того, однократное вычисление целевой функции может требовать значительных вычислительных ресурсов.

Для решения подобных задач применяются специальные алгоритмы — алгоритмы многоэкстремальной оптимизации. Исследованиям алгоритмов многоэкстремальной оптимизации посвящены работы К. А. Баркалова, Д. И. Батищева, В. П. Булатова, В. П. Гергеля, А. И. Голикова, С. Ю. Городецкого, В. А. Гришагина, X. М. Гутмана (Н.-М. Gutmann), Д. Р. Джонса (D. R. Jones), Ю. Г. Евтушенко, В. Г. Жадана, А. А. Жиглявского, А. Г. Жи-линскаса, Д. Е. Квасова, А. Г. Коротченко, А. В. Орлова, П. М. Пардалоса (Р. М. Pardalos), Я. Пинтера (J. D. Pintér), С. А. Пиявского, М. А. Посыпки-на, JI. А. Растригина, А. И. Рубана, Я. Д. Сергеева, А. С. Стрекаловского, Р. Г. Стронгина, А. Г. Сухарева, X. Туя (Н. Тиу), К. Флудаса (С. Floudas), Р. Хорста (R. Horst) и многих других. Алгоритмы многоэкстремальной оптимизации, в отличии от алгоритмов локальной оптимизации, способны находить глобальный экстремум целевой функции, но при этом, как правило, характеризуются более высокой вычислительной трудоемкостью. В ряде случаев целесообразно предсталять целевую функцию в виде "черного ящика", когда на вход подается некоторый аргумент, а на выходе наблюдается соответствующее значение целевой функции. Такая постановка задачи является достаточно распространненой на практике и позволяет записывать в этой форме задачи из различных предметных областей, но при этом при решении таких задач требуется, как правило, использовать специальные модели — модели целевых функций, которые содержат некоторые дополнительные предположения о целевой функции, позволяющие построить эффективный алгоритм решения задачи многоэкстремальной оптимизации.

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

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

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

В соответствии с поставленной целью решались следующие задачи:

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

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

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

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

Методы исследования. При выполнении исследования применялись теория алгоритмов, теория локальной оптимизации, теория многоэкстремальной оптимизации, методы интерполяции, объектно-ориентированное программирование.

Научная новизна.

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

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

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

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

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

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

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

Практическая значимость работы. Предложенные алгоритмы могут быть использованы для решения задач многоэкстремальной оптимизации при проектировании систем, идентификации нелинейных моделей и т.д. В рамках работы создан программный комплекс, реализующий разработанные алгоритмы и позволяющий тестировать однородные алгоритмы с различными моделями целевых функций. На программный комплекс получено свидетельство о государственной регистрации программы для ЭВМ №2010616850 от 14.10.2010. Исследования выполнялись при поддержке грантов губернатора Челябинской области (115.07.06-05.АХ, 065.07.06-08.БХ), гранта г. Челябинска «Лучшая инновационная идея года» 2010 г.

Апробация работы. Результаты работы докладывались на международных и всероссийских конференциях: XII 1-й и Х1У-Й Всероссийских конференциях «Математическое программирование и приложения»(г. Екатеринбург, 2007, 2011), международной конференции «Алгоритмический анализ неустойчивых задач», посвященной 100-летию со дня рождения В. К. Иванова (г. Екатринбург, 2008), международной конференции «Оптимизация и приложения (OPTIMA-2009)» (Черногория, г. Петровац, 2009), VI Московской международной конференции по исследованию операций (г. Москва, 2010), а также на конференциях: 38 молодежной школ е-конференции «Проблемы теоретической и прикладной математики» (г. Екатеринбург, 2007), «Технологии Microsoft в теории и практике программирования» (г. Нижний Новгород, 2007, 2010), XXVI конф. памяти H.H. Острякова (г. Санкт-Петербург, 2008), I и II научной конференции аспирантов и докторантов ЮУрГУ (г. Челябинск, 2009, 2010). Результаты работы также докладывались на семинаре под руководством акад. Евтушенко Ю. Г. (ВЦ РАН, г. Москва, 2011) и на семинаре под руководством проф. Гергеля В. П. (ННГУ, г. Нижний Новгород, 2011). Публикации. Основные результаты диссертации опубликованы в 28 научных работах [89-116], в том числе 4 — в изданиях, рекомендованных ВАК [89, 103, 108, 113].

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, библиографии и одного приложения. Объем диссертации 123 страницы, объем библиографии 116 источников.

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

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

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

3. Разработан однородный алгоритм многоэкстремальной оптимизации. Сравнение его с различными алгоритмами многоэкстремальной оптимизации на различных тестовых функциях, задаче размещения радиомаяков в раз-ностно-дальномерной системе навигации и задаче идентификации нелинейной модели подтвердило высокую эффективность предложенного алгоритма. По результатам вычислительного эксперимента установлено, что область применения предложенного алгоритма — многомерные (размерность до 6) задачи многоэкстремальной оптимизации с целевой функцией, время вычисления которой превышает 327 мс (« 3,9-109 операций с плавающей запятой). Предложены две модификации алгоритма: для задач высокой размерности (решена задача 45 размерности) и для многоядерных вычислительных систем (продемонстрирована работа на 512 ядрах).

4. Спроектирован и реализован программный комплекс (свидетельство о государственной регистрации программы для ЭВМ №2010616850 от 14.10.2010) для решения задач многоэкстремальной оптимизации и проведения вычислительного эксперимента с однородными алгоритмами многоэкстремальной оптимизации и моделями липшицевых целевых функций.

ЗАКЛЮЧЕНИЕ

1. Ананченко А. Г. Разработка алгоритмов и программных комплексов для глобальной оптимизации химико-технологических систем: дис. . канд. техн. наук: 05.13.18. СПб, 2004.

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

3. Бердышев В.И., Петрак Л.В. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999. 296 с.

4. Булатов В. П., Хамисов О. В. Метод отсечения в Еп+г для решения задач глобальной оптимизации на одном классе функций // Ж. вычисл. матем. и матем. физ. 2007. №11. С. 1830-1842.

5. Гергель В.П. Об одном способе учета значений производных при минимизации многоэкстремальных функции // Ж. вычисл. матем. и матем. физ. 1996. т. С. 51-67.

6. Гергель В.П., Стронгин Р.Г. АБСОЛЮТ. Программная система для исследований и изучения методов глобальной оптимизации. Н. Новгород:

7. Изд-во Нижегородского университета, 1998. 141 с.

8. Городецкий С.Ю. Сходимость и асимптотические оценки поведения для одного класса методов поиска // Динамика систем. Динамика и управление / Горький: ГГУ, 1984. С. 24.

9. Городецкий С.Ю. Многоэкстремальная оптимизация на основе триангуляции области // Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Математическое моделирование и оптимальное управление. 1999. №2. С. 249-269.

10. И. Гришагин В. A. V.A.Grishagin's class of test functions. URL: http://si.deis.unical.it/~yaro/Grishaginweb.zip. Дата обращения:0505.2010.

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

12. Гришагин В. А. Исследование одного класса численных методов решения задач многоэкстремальной оптимизации: автореф. дис. . канд. физ.-мат. наук: 05.13.02. Горький, 1983.

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

14. Евтушенко Ю.Г. Численный метод отыскания наилучших гарантированных оценок // Ж. вычисл. матем. и матем. физ. 1972. №1. С. 89-104.

15. Евтушенко Ю. Г., Ратькин В. А. Метод половинных делений для глобальной оптимизации функции многих переменных // Изв. АН СССР. Техн. кибернетика. 1987. №1. С. 119-127.

16. Евтушенко Ю. Г., Малкова В. У., Станевичюс А. А. Параллельный поиск глобального экстремума функций многих переменных // Ж. вычисл. матем. и матем. физ. 2009. №2. С. 255-269.

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

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

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

20. Жолен Л., Кифер М., Дидри О., Вальтер Э. Прикладной интервальный анализ. Москва-Ижевск: РХД, 2007. 468 с.

21. Карпенко А. П., Селиверстов Е. Ю. Глобальная оптимизация методом роя частиц. Обзор // Информационные технологии. 2010. №2. С. 25-34.

22. Квасов Д.Е., Сергеев Я.Д. Многомерный алгоритм глобальной оптимизации на основе адаптивных диагональных кривых // Ж. вычисл. ма-тем. и матем. физ. 2003. №. С. 42-59.

23. Квасов Д. Е. Диагональные алгоритмы решения задач липшицевой глобальной оптимизации: дис. . канд. физ.-мат. наук: 05.13.18. Н. Новгород, 2006.

24. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. М.: Вильяме, 2005. 1296 с.

25. Кузнецов А. В. Алгоритмы глобальной оптимизации функций в пространстве непрерывных переменных при наличии ограничений-неравенств: дис. . канд. техн. наук: 05.13.01. Красноярск, 2006.

26. Кушербаева В. Т., Сушков Ю. А. Статистическое исследование алгоритма случайного поиска // Стохастическая оптимизация в информатике 2007. т. С. 21-36.

27. Оленев H.H., Фетинина А.И. Моделирование экономики Кировской области с применением технологий параллельного программирования // Научно-технический вестник СПбГУ ИТМО. 2010. №1. С. 108-113.

28. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир 1975. 534 с.

29. Abakarov A., Sushkov Yu., Almonacid S., Simpson R. Thermal processing optimization through a modified adaptive random search // Journal of Food Engineering. 2009. №2. R 200-209.

30. Bjorkman M., Holmstrom K. Global Optimization of Costly Nonconvex Functions Using Radial Basis Functions // Optimization and Engineering. 2000. №. R 373-397.

31. Box G. E. P., Wilson К. B. On the Experimental Attainment of Optimum Conditions // Journal of the Royal Statistical Society. 1951. №1. P. 1-45.

32. Clausen J., Zilinskas A. Subdivision, Sampling, and Initialization Strategies for Simplical Branch and Bound in Global Optimization // Computers and Mathematics with Applications. 2002. №7. P. 943-955.

33. Dreo J., Petrowski A., Siarry P., Taillard E. Metaheuristics for Hard Optimization: Methods and Case Studies. Paris: Springer, 2005. 369 p.

34. Egorov I.N., Kretinin G.V., Leshchenko I.A. Robust Design Optimization Strategy of IOSO Technology // Fifth World Congress on Computational Mechanics / Vienna, Austria., 2002. P. 8.

35. Finkel D. E. Global optimization with the direct algorithm: PhD thesis. Raleighh, NC, 2005.

36. Forrester A., Keane A. J. Recent advances in surrogate-based optimization // Progress in Aerospace Sciences. 2009. №1-3. P. 50 79.

37. Gablonsky J. M., Kelley С. T. A Locally-Biased Form Of The Direct Algorithm // J. of Global Optimization. 2001. №. P. 27-37.

38. Gaviano M., Kvasov D. E., Lera D., Sergeyev Ya. D. Generation of Classes of Test Functions with Known Local Minima // ACM Trans. Math. Soft. 2003. №4. P. 469-480.

39. Gergel V.P. A Global Optimization Algorithm for Multivariate Functionswith Lipschitzian First Derivatives // J. of Global Optimization. 1997. №10. P. 257-281.

40. Gergel V.P., Sergeyev Ya.D. Sequential and parallel global optimization algorithms using derivatives // Computers and Mathematics with Applications. 1999. №4/5. P. 163-180.

41. Grishagin V. A., Sergeyev Ya. D., Strongin R. G. Parallel Characteristical Algorithms for Solving Problems of Global Optimization // J. of Global Optimization. 1997. №2. P. 185-206.

42. Gutmann H. M. A Radial Basis Function Method for Global Optimization // J. of Global Optimization. 2001. №3. P. 201-227.

43. Hellstrom Т., Holmstrom K. Global Optimization of Costly Nonconvex Functions, with Financial Applications // Theory of Stochastic Processes. 2001. №7. P. 121-141.

44. Holmstrom К. An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization // J. of Global Optimization. 2008. №3. P. 447-464.

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

46. Jakobsson S., Patriksson M., Rudholm J., Wojciechowski A. A method for simulation based optimization using radial basis functions // Optimization and Engineering. 2009. №3. P. 409-426.

47. Jones D. R., Perttunen C. D., Stuckman В. E. Lipschitzian optimization without the Lipschitz constant // J. Optim. Theory Appl. 1993. №1. P.157.181.

48. Jones D. R., Schonlau M., Welch W. J. Efficient Global Optimization of Expensive Black-Box Functions // J. of Global Optimization. 1998. №4. P. 455-492.

49. Jones D. R. A Taxonomy of Global Optimization Methods Based on Response Surfaces // J. of Global Optimization. 2001. №4. P. 345-383.

50. Kushner M. J. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise // Journal of Basic Engineering. 1964. №86. P. 97-106.

51. Levy A. V., Montalvo A. The Tunneling Algorithm for the Global Minimization of Functions // SIAM Journal on Scientific and Statistical Computing. 1985. №. P. 15-29.

52. Locatelli M. Bayesian Algorithms for One-Dimensional Global Optimization // J. of Global Optimization. 1997. №10. P. 57-76.

53. Locatelli M. On the multilevel structure of global optimization problems // Comput. Optim. Appl. 2005. M. P. 5-22.

54. Neumaier A., Shcherbina O., Huyer W., Vinko T. A comparison of complete global optimization solvers // Math. Programming. 2005. №2. P. 335-356.

55. Paulavicius R., Zilinskas J. Global optimization using the branch-and-bound algorithm with a combination of lipschitz bounds over simplices // Baltic Journal on Sustainability. 2009. №2. P. 310-325.

56. Pinter J. D. Convergence qualification of adaptive partition algorithms in global optimization // Math. Programming. 1992. №3. P. 343-360.

57. Pinter J. D. Global Optimization in Action. Dordrecht Boston - London:

58. Kluwer Academic Publishers, 1996. 512 p.

59. Pinter J. D. Nonlinear optimization with GAMS/LGO // J. of Global Optimization. 2007. №1. P. 79-101.

60. Regis R. G. Global optimization of computationally expensive functions using serial and parallel radial basis function algorithms: PhD thesis. Ithaca, NY, USA, 2004.

61. Regis R. G., Shoemaker C. A. Improved Strategies for Radial basis Function Methods for Global Optimization // J. of Global Optimization. 2007. №1. P. 113-135.

62. Regis R. G., Shoemaker C. A. Parallel radial basis function methods for the global optimization of expensive functions // European Journal of Operational Research. 2007. №2. P. 514 535.

63. Sergeyev Ya.D. On convergence of "Divide the Best" global optimization algorithms // Optimization. 1998. №2. P. 303-325.

64. Sergeyev Y. D., Kvasov D. E. Global Search Based on Efficient Diagonal Partitions and a Set of Lipschitz Constants // SIAM J. on Optimization. 2006. №. P. 910-937.

65. Simpson T. W., Mauery T. M., Korte J. J., Mistree F. Kriging Models for Global Approximation in Simulation-Based Multidisciplinary Design Optimization // AIAA Journal. 2001. №12. P. 2233-2241.

66. Sobester A., Leary S. J., Keane A. J. On the Design of Optimization Strategies Based on Global Response Surface Approximation Models // J. of Global Optimization. 2005. №1. P. 31-59.

67. Strekalovsky A. S. Global Optimality Conditions for Nonconvex Optimization // J. of Global Optimization. 1998. №4. P. 415-434.

68. Strongin R. G., Sergeyev Ya. D. Global Optimization with Non-Convex Constraints Sequential and Parallel Algorithms. Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2000. 728 p.

69. Tobor I., Reuter P., Schlick C. Efficient reconstruction of large scattered geometric datasets using the partition of unity and radial basis functions // Journal of WSCG 2004. 2004. №3. P. 467-474.

70. Torn A., Zilinskas A. Global optimization. New York, NY, USA: Springer-Verlag, 1989. 350 p.

71. Towards global optimisation / eds. G.P. Szego, L.C.W. Dixon. New York: North-Holland Pub. Co., 1978. 363 p.

72. Villemonteix J., Vazquez E., Walter E. An informational approach to the global optimization of expensive-to-evaluate functions // J. of Global Optimization. 2009. №4. P. 509-534.

73. Zhigljavsky A., Zilinskas A. Stochastic Global Optimization. Berlin: Springer, 2008. 262 p.

74. Антонов M. О., Елсаков С. M., Ширяев В. И. Нахождение оптимального расположения радиомаяков в разностно-дальномерной системе посадки летательного аппарата // Авиакосмическое приборостроение 2005. №11. С. 41-45.

75. Ел саков С. М., Ширяев В. И. Однородные алгоритмы глобальной оптимизации // ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ: Тр. 38-й Региональной молодеж. конф. / Екатеринбург: УрО РАН, 2007. С. 326-329.

76. Елсаков С. М., Ширяев В. И. Однородные алгоритмы глобальной оптимизации и модели целевых функций // Матер, конф. «Технологии Microsoft в теории и практике программирования» / Н. Новгород: Изд-во Нижегородского гос. ун-та, 2007. С. 83-87.

77. Елсаков С. М. Многомерные однородные алгоритмы глобальной оптимизации // Научный поиск: Матер, первой науч. конф. аспирантов и докторантов. Социально-гуманитарные и естественные науки / Челябинск: Изд. центр ЮУрГУ, 2009. С. 27-31.

78. Елсаков С. М., Ширяев В. И. О многоэкстремальности в задачах оценивания состояния систем детерминированного хаоса // Вестник ЮУрГУ. Сер. Компьютерные технологии, управление, радиоэлектроника 2009. т. С. 37-41.

79. Елсаков С. М., Ширяев В. И. Разностно-дальномерная система ближней навигации для мобильных роботов // Мобильные роботы и мехатронные системы// Матер, научн. школы-конф. Москва, 24-29 марта 2008 г. / М.:

80. Изд-во Моск. ун-та, 2009. С. 135-142.

81. Елсаков С. М., Ширяев В. И. Алгоритмы многомерной глобальной оптимизации на основе RBF-сплайнов // Забабахинские научные чтения: сб. матер. X Междунар. конф. 15-19 марта 2010 / Снежинск: Изд-во РФЯЦ-ВНИИТФ, 2010. С. 292-294.

82. Елсаков С. М., Ширяев В. И. Однородные алгоритмы многоэкстремальной оптимизации // Ж. вычисл. матем. и матем. фиа 2010. №10. С. 1727-1740.

83. Елсаков С. М., Ширяев В. И. Однородный алгоритм глобальной оптимизации с использованием вспомогательной модели для целевой функции //VI Московская Междунар. конф. по исследованию операций (ORM2010) / М.: МАКС Пресс, 2010. С. 230-232.