Разработка рандомизированных алгоритмов в интервальной глобальной оптимизации тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

005013940

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

Панов Никита Владимирович

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

01.01.07 — вычислительная математика

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

1 5 [.!др 1Ш

Красноярск — 2012

005013940

Работа выполнена в Институте вычислительных технологий Сибирского Отделения Российской Академии Наук (г. Новосибирск) и Конструкторско-техно-логическом институте вычислительной техники Сибирского Отделения Российской Академии Наук (г. Новосибирск).

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

Шарый Сергей Петрович.

Официальные оппоненты: Добронец Борис Станиславович,

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

Жилин Сергей Иванович, кандидат физико-математических наук, Алтайского государственный университет, заведующий каферой информатики.

Ведущая организация: Федеральное государственное бюджетное

учреждение науки Институт динамики систем и теории управления Сибирского отделения Российской Академии Наук (г. Иркутск).

Защита состоится 22 марта 2012 г. в 14:00 на заседании диссертационного совета ДМ 212.099.18 при Сибирском федеральном университете по адресу: 600074 г. Красноярск, ул. Корейского, 26«б», корпус «Ж» Сибирского федерального университета, ауд. УЛК-115.

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

Автореферат разослан 18 февраля 2012 г.

Ученый секретарь диссертационного совета

Кириллов Кирилл Анатольевич

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

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

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

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

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

Несмотря на явный прогресс в этой области за последние два десятиле-

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

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

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

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

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

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

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

1) Исследована точность различных способов вычисления интервальных расширений функций.

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

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

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

1 Предложено ранее научным руководителем работы, см. Шарый С.П. Стохастические подхода в интервальной глобальной оптимизации. Труды XIII Байкальской мелщугщюдной школы-ссшпшра « Методы оптимизации я их приложенияИркутск-Северобапкальск, 2-3 июля 2005 года. Том 4 «Интервальный анализ». ~ Иркутск, ИСЭМ СО РАН, 2005. - С. 85-105.

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

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

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

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

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

2По терминологии, берущей начало с работ А.И. Тятюшкина и А.Ю. Горнова. См. Гор нов А.Ю. Тятюшкин А.II. Программная реализация м.таьтимегоднон технологии для задач оптимального управления // Сборник трудов 3-й Междуяар. конф. гЩюблемы управления и моделирования в сложных системах», Самара. 2001. С. 301-307. и Горнов А.Ю. Вычислительные технологии решения задач оптимального ¿правления. Новосибирск: Наука. 2009.

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

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

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

Результаты диссертации докладывались и обсуждались

■ на объединенном семинаре Института вычислительных технологий СО РАН, Коиструкторско-тсхиологическою института СО РАН и Новосибирского государственного университета (г. Новосибирск, 2011); на XII Всероссийской конференция молодых ученых по математическому моделированию и информационным технологиям (г. Новосибирск, 2011); на Международной конференции «Современные проблемы прикладной математики и механики: теория, эксперимент и практика», посвященной 90-легшо со дня рождения академика Н.Н. Яненко. (г. Новосибирск 2011);

на XV Международной Байкальской школе-семинаре «Методы оптимизации и их приложения», (п. Листвянка, 2011); на семинаре Института систем энергетики СО РАН (г. Иркутск, 2010); на семинаре Института динамики систем и теории управления СО РАН (г. Иркутск, 2009, 2010);

на семинаре Сибирского федерального университета (г. Красноярск, 2009); на семинаре кафедры математического моделирования НГУ и Института вычислительных технологий СО РАН (г. Новосибирск, 2006, 2008, 2009); на семинаре математического факультета Алтайского Государственного Университета (г. Барнаул, 2009);

па IX Всероссийской конференция молодых ученых по математическому моделированию и информационным технологиям (г. Кемерово, 2008); на Международной конференции «Современные проблемы математического моделирования и вычислительных технологий - 2008» (г. Красноярск, 2008);

на VIII Всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям (г. Новосибирск, 2007); на Всероссийской конференции по вычислительной математике «КВМ-2007» (г. Новосибирск, 2007);

на конференции «Twelfth ECMWF Workshop "Use of High Performance Computing in Meteorology"» (Англия, 2007);

на VII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (г. Красноярск, 2006); на Всероссийском (с международным участием) совещании по интервальному анализу и его приложениям «ИНТЕРВАЛ-06» (г. Петергоф, 2006); на VI Всероссийской (с участием иностранных ученых) конференции мо-

лодых ученых по математическому моделированию и информационным технологиям (г. Кемерово, 2005);

— на X Всероссийской научной конференции студентов-физиков и молодых ученых (г. Красноярск, 2004);

— на V Международной конференции «Перспективы систем информатики» памяти акад. А.П. Ершова - PSI'03 (г. Новосибирск, 2003);

— на XLI Международной научной студенческой конференции «Студент и научно-технический прогресс» (г. Новосибирск, 2003).

Публикации. По теме диссертации опубликовано 20 работ, из них 1G в форме трудов, тезисов и расширенных тезисов докладов конференций, а так же 4 статьи в журналах, рекомендованных ВАК для публикации основных результатов диссертаций.

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

— Результаты исследований точности различных интервальных расширений функций.

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

— Создание интервального эволюционного алгоритма доказательной глобальной оптимизации.

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

— Создание оптимизированию адаптивного параллельного алгоритма глобальной оптимизации.

Структура и объем работы. Диссертационная работа состоит из введения, трёх глав основного текста, заключения и библиографического списка. Работа изложена на 178 страницах машинописного текста, включающих 50 рисунков и список литературы из 128 наименований.

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

Во введении описан предмет представляемой работы — задача глобальной оптимизации вещественнозначной функции / : X -» Ж на прямоугольном брусе X С К" со сторонами, параллельными координатным осям.

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

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

Даётся краткая классификация существующих методов г.о.

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

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

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

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

dist (f(x), range xf) -s- 0 при ||wid сс|[ ->■ 0, (1)

где dist — хаусдорфово расстояние между интервальным расширением f(x) и точной областью значений range xf функции / на интервале х (возможно, многомерном), ii wid х — ширина интервала х. Это означает, что при уменьшении размеров области определения точность интервального расширения

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

В самом деле, если разбить исходный брус х на два подбруса х' и ж", дающие в объединении весь х, то есть такие, что х' U х" = ж, то

{/(.*) \хех} = {/(*) IX€и {fix) 11ех"}.

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

min{/(x% /Ю},

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

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

Для анализа работы существующих алгоритмов и сравнения новых использована специально разработанная программная система, включающая в себя сервер приложений, позволяющий выбирать методы оптимизации, исполнять их (в том числе в режиме профилирования) и модули трёхмерной визуализации [7].

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

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

— зачастую границы интервальных оценок целевой функции на нодбрусах не коррелируют с действительными областями значений. То есть, несмотря на то, что min f(x) > min f(x), величина f(a) часто оказывалась мень-

о, Ь ' "

ше, чем /(Ь), где а и Ь — два каких-то подбруса из «рабочего списка»;

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

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

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

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

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

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

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

В главе 3 описаны следующие новые интервальные оптимизационные алгоритмы, основанные на привлечении стохастики (рандомизации):

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

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

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

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

В диссертации для этого алгоритма доказана следующая теорема.

Теорема 1 Алгоритм случайного интервального дробления с приоритетом сходится % глобальному оптимуму почти наверное (почти всегда).

Далее в работе подробно рассмотрена, интервальная версия алгоритма имитации отжига, предложенная С.П. Шарым в 2005 году4. За основу взят популярный классический (точечный) метод оптимизации (известный также

4Шарый С.П. Стохастические подходы в интервальной глобальной оптимизации // Труды XIII Байкальской международной швалы-ссмшара *Методы оптимизации я их приложения». Том 4 «Интервальный анализ». Иркутск, ИСЭМ СО РАН, 2005. С. 85-105.

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

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

Для интервального алгоритма имитации отжига в работе доказано следующее утверждение.

Утверждение 1 В процессе работы предложенного интервального алгоритма имитации отжига при любом законе предельного перехода Т —» О существуют такие натуральные числа imax и п, что любой брус х' из рабочего списка С. удовлетворяющий равенству f(x') = mini<j<s/(ж,-), начиная с шага с номером гтах подвергается дроблению не реже чем одного раза в продолжение любых п последовательных шагов алгоритма.

Опираясь на это утверждение доказана теорема о сходимости:

Теорема 2 Интервальный алгоритм имитации отжига гарантированно сходится к глобальному оптимуму.

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

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

&Ьамвекг M.S., Miriam т.т., Susan F.M. Simulated Annealing: Global Optimization, Applied Mathematics. Global Optimum, Metropolis-Hastings Algorithm, Monte Carlo Method, Nicholas Metropolis, Quantum Annealing. — Betascript Publishers, 2009.

6Мишшальную при поиске минимума, максимальную при поиске максимума. Такой брус ещё называют ведущим.

Алгоритм 1. Схема простейшего интервального алгоритма «имитации отжига».

присваиваем ¡/ЫиТьТо; назначаем целочисленную величину Nt

— «количество испытаний на один температурный уровень»; вычисляем f(y) и инициализируем список С записью { (у, f(y)) }; DO WHILE ( Т > TIin )

DO FOR j = 1 TO NT

случайно выбираем из С запись (z, f(z)) по правилу S(y); DO ( с вероятностью Pr(j/i2) )

рассекаем z по самой длинной компоненте пополам

на брусы-потомки z' и г"; вычисляем f(z') и f{z"); удаляем запись (г, /(г)) из списка С; помещаем записи (г', f(z')) и (г", f(z")) в список £; обозначаем через (y,f(y)) ту из записей (V, /(г')) и (z". f(z")), которая имеет меньшее значение второго поля; END ШОуИВныпаем значение температуры Т а Г

EUD DO /•<-/(!/);

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

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

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

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

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

В описанной схеме применение генетических операторов не обязательно. Их использование позволяет повысить рандомизацшо метода, увеличить вариабельность популяции и избежать застоя вблизи локальных опгимумов. Кроме того, в классических генетических алгоритмах операции мутации и скрещивания могут порождать новые решения, которые никогда не встречались в предыдущих поколениях. Интервальный алгоритм, описанный в рамках настоящей работы их не использует. Тем не менее, в отличии от классических вариантов он позволяет гарантированно найти именно глобальный оптимум. Для сохранения доказательности, являющейся характерной чертой интервальных методов, мы не отбрасываем никакие подобласти исходной области поиска из рассмотрения до тех пор, пока не будет доказано что они гарантированно не содержат оптимум. Подробнее о различных подходах к выявлению бесперспективности брусов (их называют ещё «критериями отбраковки»), можно прочитать, например, в [9,12]. Таким образом, в алгоритме особи либо рождаются нежизнеспособными (не выдерживают критериев отбраковки применяемых сразу после дробления) или погибают в результате «эпидемий» — срабатывания уточненного критерия отбраковки.

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

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

Алгоритм 2. Схема интервального биологического алгоритма.

Задаётся начальная популяция и передаётся в основной цикл Основной цикл

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

2. N из наиболее приспособленных брусов с вероятностью Р„ порождают от L„ до Un потомков.

3. М из неприспособленных брусов с вероятностью Рт порождают от Lm до Um потомков.

4. Потомки проверяются на жизнеспособность (применяются интервальные критерии отбраковки).

5. Если критерий отбраковки был улучшен, возможно случается эпидемия (улучшенные критерии применяются ко всем особям).

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

п

Fit (Ь) = (а ■ wid Ь;) + /? ■ ДЬ) + 7 • wid /(Ь). (2)

¿=1

Приведён её вид для поиска минимума. Здесь

f(b) — интервальная оценка значений целевой функции / на брусе Ь; f(b) — нижняя граница интервальной оценки (оценка минимума снизу); wid f(b) — ширина (точность) интервальной оценки области значений;

\vicl Ь; — ширина г-ой стороны бруса области определения;

«1, ..., о:„, /?, 7 — соответствующие весовые коэффициенты.

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

Утверждение 2 В ходе работы интервального эволюционного алгоритма границы интервальной оценки оптимума монотонно сужаются. Утверждение 3 Интервальный эволюционный алгоритм не упускает из рассмотрения глобальные оптимумы.

На основе этих результатов в диссертации доказана теорема:

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

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

Конкретизация этой идеи следующая. Запускается какой-то алгоритм глобальной оптимизации из заданного семейства. Через короткий промежуток времени он останавливатся и на существующем рабочем списке брусов запускается уже другой алгоритм, т.е., фактически, происходит подмена алгоритма оптимизации в процессе поиска оптимума. При этом отслеживается относительную эффективность каждого из алгоритмов — сколько итераций было сделано, насколько улучшилась оценка оптимума, как изменился размер рабочего списка и т.п. По каждому алгоритму отслеживается как глобальная статистика, то есть результаты за всё время работы алгоритма, так и локальная — результаты каждого конкретного сеанса работы. Исходя их сравнительной успешности алгоритмов динамически регулируется квант времени, выделяемый каждому из алгоритмов, таким образом обеспечивая оптимальность их применения. Таким образом, нами реализуется «мета-алгоритм», адаптивный алгоритм второго порядка (по аналогии с терминологией, принятой в функциональных языках программирования для функций, оперирующих функциями), или мультимегодный подход по терминологии, берущей начало с работ А.И. Тятюшкина и А.Ю. Гориова. На рис. 1 показан пример

Рис. 1: Пример переключения между алгоритмами

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

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

всем остальным алгоритмам будет предоставлено одинаковое небольшое время для работы. На следующем шаге относительная успешность алгоритмов снова сравнивается и выделяемое время корректируется.

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

Основные итоги главы 3 могут быть сформулированы следующим образом:

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

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

3) разработаны и экспериментально исследованы различные версии интервального эволюционного алгоритма для д.г.о.;

4) для предложенных алгоритмов сформулирован и доказан ряд утверждений и теорем о сходимости разработанных алгоритмов. В частности, доказано, что алгоритм интервального случайного поиска с приоритетом сходится к глобальному оптимуму почти всегда (Сходимость «почти всегда» сильнее «сходимости по вероятности»); а интервальный алгоритм имитации отжига и интервальный генетический алгоритм гарантированно сходятся к глобальному оптимуму.

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

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

Заключение

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

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

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

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

Литература

Статьи в изданиях, рекомендованных ВАК РФ для опубликования материалов и результатов кандидатских диссертаций

1. Панов Н.В., Шарый С.П. Интервальный эволюционный алгоритм поиска глобального оптимума // Известия Алтайского государственного университета (ISSN 1561-9443). 2011. М(69). Т.2. С. 108-113.

2. Панов Н.В. Объединение стохастических и интервальных подходов для решения задач глобальной оптимизации функций /7 Вычислительные технологии. 2009. Т. 14, №5. С. 49435.

3. Панов Н.В. Оценка области значений функций методами интервального анализа // Вопросы современной науки и практики. 2009. №3. С. 78-86.

4. Панов Н.В. Адаптивный мета-алгоритм глобальной оптимизации // Естественные и технические науки (ISSN 1684-2626). 2009. №1 (39). С. 315-318.

Прочие публикации

5. Шарый С.П., Колдаков В.В., Панов Н.В. Интервальный симулированный отжиг для глобальной оптимизации функций // Студент и научно-технический прогресс: Материалы XLI Международной научной студенческой конференции. Серия «Математика». Новосибирск: НГУ. 2003. С. 76.

6. Шарый С.П., Панов Н.В. Пакет визуализации интервальных методов глобальной оптимизации // Студент и научно-технический прогресс: Материалы XLI Международной научной студенческой конференции. Серия «Физика: Автоматизация научных исследований и машинной графики». Новосибирск: НГУ. 2003. С. 21.

7. Панов Н.В., Колдаков В.В. Программный комплекс для графического представления процесса и результатов работы интервальных алгоритмов /'/ Перспективы систем информатики: Труды Пятой международной конференции памяти академика А.П. Ершова. Новосибирск. ИПО Эмари. 2003. Том «Международное совещание по интервальной математике и методам распространения ограничений ИМРО-ОЗ». С. 38-46.

22

ЛИТЕРАТУРА

8. Зюбиы В.Е., Панов Н.В., Шарый СЛ. Распределенная система для решения задач глобальной оптимизации функции методами интервального анализа с возможностью трехмерной визуализации // Десятая научная конференция студентов-физиков и молодых ученых: Материалы всероссийской конференции. Красноярск. 2004. С. 195.

9. Панов Н.В., Шарый С.П. Стохастические подходы в интервальных методах глобальной оптимизации // I1HTEPBAJI-06: Расширенные тезисы докладов всероссийского (с международным участием) совещания по интервальному анализу и его приложениям. С.-Пб: ВВМ. 2006. С. 101-105.

10. Панов Н.В. Гибридные алгоритмы глобальной оптимизации // Методы оптимизации и их приложения: Труды XV Байкальской международной школы-семинара. Т. 2 Математическое программирование. Иркутск: РИО ИДСТУ СО РАН. 2011. С. 145-150.

И. Лозбель М.Е.. Панов Н.В. Параллельные алгоритмы интервальной глобальной оптимизации // Современные проблемы прикладной математики и механики: теория, эксперимент и практика: Труды Международной конференции посвященной 90-летию со дня рождения академика H.H. Яненко. - No. гос. регистр. 0321101160, ФГУП НТЦ «Информрегистр». -Новосибирск. 2011.

12. Лядова М.А., Панов Н.В. Интервальный метод Ньютона и его модификации для решения задачи поиска глобального оптимума функций // Современные проблемы прикладной математики и механики: теория, эксперимент и практика: Труды Международной конференции посвященной 90-летшо со дня рождения академика H.H. Яненко. - No. гос. регистр. 0321101160, ФГУП НТЦ «Информрегистр». - Новосибирск. 2011.

13. Панов Н.В. Решатель задач поиска глобального оптимума функций // Современные проблемы прикладной математики и механики: теория, эксперимент и практика: Труды Международной конференции посвященной 90-летию со дня рождения академика H.H. Яненко. - No. гос. регистр. 0321101160, ФГУП НТЦ «Информрегистр». - Новосибирск. 2011.

14. Панов Н.В. Комбинирование точечных и интервальных методов поиска глобального оптимума // XII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям: Дополненные тезисы докладов. Новосибирск: ИВТ. 2011. С. 55-56.

Подписано в печать 15.02.2012г. Формат 60x84 1\16 Усл. печ. л. 1,5 Объем 24 стр. Тираж 150 экз. Заказ 47 Огпечатано Омега Принт 630090, г. Новосибирск, пр. Ак.Лавреитьева,6 email: omegap@yandex.ru

61 12-1/715

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК КОНСТРУКТОРСКО-ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ СИБИРСКОГО ОТДЕЛЕНИЯ РАН

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

01.01.07 — вычислительная математика

Диссертация на соискание учёной степени кандидата физико-математических наук

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

Панов Никита Владимирович

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

д. ф.-м. н. Шарый Сергей Петрович

Новосибирск — 2012

Оглавление

Введение 5

1 Инструменты интервального анализа 25

1.1 Основы интервального анализа...................25

1.2 Автоматическое дифференцирование ...............29

1.2.1 Численное дифференцирование...............30

1.2.2 Наклоны функции......................32

1.2.3 Автоматическое дифференцирование ...........33

1.3 Интервальные расширения функций................39

1.3.1 Естественное интервальное расширение..........40

1.3.2 Среднезначная форма интервального расширения .... 42

1.3.3 Наклонная форма интервального расширения......44

1.4 Точность интервального расширения функций..........44

Итоги главы 1 ...............................66

2 Критический анализ интервальных методов 67

2.1 Обзор классических (точечных) методов .............67

2.2 Интервальные методы........................74

2.3 Особенности современных машинных вычислений........79

2.4 Структура рабочего списка.....................86

2.5 Критерии отбраковки........................87

2.6 Способы дробления брусов.....................95

2.7 Процедура выбора ведущего бруса.................98

Итоги главы 2 ...............................108

3 Стохастические интервальные

методы глобальной оптимизации 109

3.1 Случайное интервальное дробление................109

3.2 Случайное интервальное дробление с приоритетом........116

3.3 Интервальный алгоритм имитации отжига............124

3.4 Интервальный генетический алгоритм...............132

3.5 Универсальный (мультиметодный) алгоритм...........145

3.6 Параллельный интервальный алгоритм

глобальной оптимизации.......................148

3.7 Вычислительные эксперименты...................153

3.8 Практическое применение......................158

Итоги главы 3 ...............................163

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

Введение

Предмет представляемой работы — задача глобальной оптимизации веще-ственнозначной функции / : X —»• М на прямоугольном брусе J С 1" со сторонами, параллельными координатным осям:

найти min f(x) . (1)

хех

Задача оптимизации — одна из востребованных проблем современной вычислительной и прикладной математики. Решение подобных проблем требуется во многих задачах из различных отраслей науки и техники. Леонард Эйлер (1707-1783), один из величайших математиков, говорил: «В мире не происходит ничего, в чём бы не был виден смысл какого-нибудь максимума или минимума» [57].

Особый интерес представляет нахождение так называемых глобальных экстремумов (оптимумов) функции, т.е. таких, которые являются наилучшими на всей рассматриваемой области определения целевой функции, а не только в сравнении с близлежащими точками из некоторой своей окрестности. Следует отметить, что в самом общем случае задача глобальной оптимизации является труднорешаемой. Современные численные методы её решения сводятся, по существу, к нахождению значений всех локальных оптимумов целевой функции и сравнению их между собой, причём подобное положение не является следствием ущербности, недоработанности и т. п. существующих методик или недостаточным уровнем развития современной теории оптимизации, а носит принципиальный характер. В 1984 году A.A. Гагановым [11] было строго показано, что даже для полиномиальной целевой функции f(x) задача глобальной оптимизации (1) на прямоугольном брусе является NP-трудной, что, фактически, равносильно признанию того, что для её решения требуются не менее чем экспоненциальные в зависимости от размерности п трудозатраты. Один из последних эффектных результатов в этом направлении — теорема Кирфотта-Крейновича [100], утверждающая, что за пределами класса выпуклых целевых функций решение задачи глобальной оптимизации (1) является NP-трудным.

Осознание специфичности поиска глобальных оптимумов и его сложности, и, как следствие, оформление глобальной оптимизации в отдельную ветвь общей теории оптимизации произошло в 70-е годы прошлого века. Впервые этот термин прозвучал в работах Торна, Бекера и Лаго, а также Диксона и Сзего [79, 87, 88, 129, 130].

К настоящему моменту наработан богатый инструментарий поиска глобального оптимума [9, 10, 17, 21, 58, 78, 85, 86, 91, 94, 97, 106]. Существующие методы можно условно разделить, с одной стороны, на детерминистские и стохастические, а с другой, по применяемой в них технике, на классические точечные и интервальные. Точнее это разделение можно представить в виде дерева на рис. 1.

Рис. 1: Классификация алгоритмов глобальной оптимизации

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

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

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

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

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

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

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

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

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

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

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

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

1) Исследована точность различных способов вычисления интервальных расширений функций.

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

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

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

'■Предложено ранее научным руководителем работы, см. Шарый С.П. Стохастические подходы в интервальной глобальной оптимизации. Труды XIII Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск-Северобайкальск, 2-8 июля 2005 года. Том 4 «Интервальный

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

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

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

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

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

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

анализ». - Иркутск, ИСЭМ СО РАН, 2005. - С. 85-105.

2По терминологии, берущей начало с работ А.И. Тятюшкина и А.Ю. Горнова. См. Горнов А.Ю. Тятюшкин А.И. Программная реализация мультиметодной технологии для задач оптимального управления // Сборник трудов 3-й Междунар. конф. «Проблемы управления и моделирования в сложных системахСамара. 2001. С. 301-307. и горнов А.Ю. Вычислительные технологии решения задач оптимального управления. Новосибирск: Наука. 2009.

ванных (стохастических) методов, в частности, перспективных интервальных генетических алгоритмов.

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

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

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

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

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

— на объединённом семинаре Института вычислительных технологий СО РАН, Конструкторско-технологического института СО РАН и Новосибирского государственного университета (г. Новосибирск, 2011);

— на XII Всероссийской конференция молодых ученых по математическому моделированию и информационным технологиям (г. Новосибирск, 2011);

— на Международной конференции «Современные проблемы прикладной математики и механики: теория, эксперимент и практика», посвященной 90-летию со дня рождения академика H.H. Яненко. (г. Новосибирск, 2011);

— на XV Международной Байкальской школе-семинаре «Методы оптимизации и их приложения», (п. Листвянка, 2011);

— на семинаре Института систем энергетики СО РАН (г. Иркутск, 2010);

— на семинаре Института динамики систем и теории управления СО РАН (г. Иркутск, 2009, 2010);

— на семинаре Сибирского федерального университета (г. Красноярск, 2009);

— на семинаре кафедры математического моделирования НГУ и Института вычислительных технологий СО РАН (г. Новосибирск, 2006, 2008, 2009);

— на семинаре математического факультета Алтайского Государственного Университета (г. Барнау