Методы глобальной и многокритериальной оптимизации на базе концепций ветвей и границ и неравномерных покрытий тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Посыпкин, Михаил Анатольевич
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2014
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
ПОСЫПКИН Михаил Анатольевич
МЕТОДЫ ГЛОБАЛЬНОЙ И МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ НА БАЗЕ КОНЦЕПЦИЙ ВЕТВЕЙ И ГРАНИЦ И НЕРАВНОМЕРНЫХ ПОКРЫТИЙ
01.01.09 Дискретная математика и математическая кибернетика
Автореферат диссертации на соискание ученой степени доктора физико-математических наук
005557497
15ЯНЗ 2015
Москва, 2014
005557497
Работа выполнена в Федеральном государственном бюджетном учреждении науки Вычислительном центре им. A.A. Дородницына Российской академии наук
Научный консультант: академик РАН, доктор физико-математических наук, профессор Евтушенко Юрий Гаврилович
Официальные оппоненты:
Кочетов Юрий Андреевич, доктор физико-математических наук, профессор, ведущий научный сотрудник Федерального государственного бюджетного учреждения науки Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук
Поляк Борис Теодорович, доктор технических наук, старший научный сотрудник, главный научный сотрудник Федерального государственного бюджетного учреждения науки Института проблем управления им. В. А. Трапезникова Российской академии наук
Хамисов Олег Валерьевич, доктор физико-математических наук, старший научный сотрудник, заведующий отделом прикладной математики Федерального государственного бюджетного учреждения науки Института систем энергетики им. Л.А. Мелентьева Сибирского отделения Российской академии наук
Ведущая организация:
Федеральное государственное бюджетное учреждения науки Институт математики и механики им. H.H. Красовского УрО РАН
Защита диссертации состоится 26 февраля 2015 г. в 13 час. на заседании диссертационного совета Д 002.017.02 в Федеральном государственном бюджетном учреждении науки Вычислительном центре им. A.A. Дородницына Российской академии наук по адресу: 119333, г. Москва, ул. Вавилова, д.40.
С диссертацией можно ознакомиться в библиотеке ВЦ РАН и на сайте http: / / www.ccas.ru
Автореферат разослан « 15 » января 2015 г.
Ученый секретарь диссертационного
совета Д 002.017.02, д.ф.-м.н., профессор
В.В. Рязанов
/-
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы
Задачи глобальной оптимизации часто возникают в различных областях современной науки и техники. В биологии и химии актуальны проблемы поиска конфигураций различных химических соединений, соответствующих минимуму энергии взаимодействия. В частности, такие задачи возникают при разработке новых лекарственных препаратов. В микроэлектронике необходимо оптимизировать размещение компонентов больших интегральных микросхем. Оптимизация часто применяется в промышленном дизайне для улучшения параметров различных конструкций и изделий. Также к оптимизационным относятся различные логистические задачи, управление транспортными потоками, размещение предприятий, планирование производства. Большое практическое значение имеют задачи дискретного программирования, связанные с поиском оптимального размещения различных объектов (телекоммуникационных вышек, заправочных станций и т.п.). Классическим стало применение методов оптимизации для решения обратных задач идентификации параметров моделей по данным эксперимента. Экстремальные задачи нередко возникают при решении различных задач распознавания. Есть много и других областей, в которых оптимизация находит свое применение.
Можно с уверенностью утверждать, что задачи прикладной оптимизации являются чрезвычайно важными для развития различных отраслей науки и технологий. Поэтому разработка эффективных методов решения оптимизационных задач и их реализация в виде прикладных программных комплексов представляется актуальной научной и практической проблемой.
Методы решения задач глобальной оптимизации можно условно разделить на два класса: эвристические и детерминированные. Эвристические методы основаны на правдоподобных, но не всегда строго обоснованных, предположениях о природе решаемой задачи и позволяют найти некоторое допустимое решение, не давая при этом каких-либо гарантированных оценок на величину отклонения найденного приближенного решения от оптимума. Такие методы часто применяются для решения задач оптимизации "черного ящика", когда аналитическое выражение для целевой функции неизвестно. Большой вклад в создание, развитие и исследование эвристических алгоритмов был внесен представителями российской и зарубежных школ оптимизации Ю.И. Журавлевым, К.В. Рудаковым, Ю.Ю. Финкельштейиом, И.Х. Сигалом, A.A. Корбутом, Ю.А. Кочетовым, Б.Т. Поляком, A.B. Плясуновым, А.П. Карпенко, В.В. Ку-
рсйчиком, F. Glover, G. Kochenbcrgcr, C. Cotta, R. Marti и многими другими. Для таких алгоритмов иногда удается получить вероятностные оценки точности получаемых решения (см. работы Б.Т. Поляка, Я.З. Ципкина).
Основное внимание в диссертационной работе уделено детерминированным методам глобальной оптимизации. В отличие от эвристических, такие методы позволяют не только найти решение, но и дают оценку отклонения от оптимума найденного значения целевой функции. Различные детерминированные методы решения дискретных задач создавались и развивались И.Х. Сигалом, Ю,Ю. Финкельштейном, В.П. Черениным, В.Р. Хачатуровым, A.A. Лазаревым, А. А. Колоколовым, G. Danzig, Е. Balas, D. Pisinger, S. Martello, P. Toth и др. Детерминированные методы решения непрерывных задач глобальной оптимизации были разработаны Ю.Г. Евтушенко, С.А. Пиявским, Р.Г. Стронгиным, В.П. Гергелем, Я.Д. Сергеевым, A.C. Стрскаловским, Е.С. Левитиным, В.П. Булатовым, О.В. Хамисовым, Е. Hansen, R. Kearfott, J. Pinter, H. Tuy и другими исследователями. Данная диссертационная работа во-многом посвящена развитию идей метода неравномерных покрытий, который был предложен Ю.Г. Евтушенко в 1971 году для решения задач оптимизации с простыми (параллелепипедными) ограничениями и в дальнейшем был обобщен на более широкий класс задач, включая задачи математического программирования и многокритериальной оптимизации.
Большое внимание в современных исследованиях уделяется многокритериальной оптимизации (МКО). Значительный вклад в развитие теории и методов решения таких задач внесли A.B. Лотов, В.В. Подиновский, В.А. Бушенков, В.Д. Ногин, Г.К. Каменев, И.И. Еремин, И.М. Соболь, Р.Б. Статников, К. Deb, М. Ehrgott, Е. Zitzler, Н.Р. Benson, A. Pascoletti, P. Serafini, К. Miettinen и многие другие. Многие подходы и методы решения таких задач восходят к ранним работам Ю.Б. Гермейера и его учеников, посвященным поиску "минимакса". Ю.Б. Гермейер также предложил известный вариант свертки критериев, используемый в локальных методах. Локальные методы и условия экстремума также рассматривались в работах В.Г. Жадана, J. Fliege и др. Детерминированные методы построения приближенных решений многокритериальных задач были предложены Ю.Г. Евтушенко и М.А. Потаповым. Дискретные многокритериальные задачи рассматривались в работах И.Х. Сигала, И.И. Меламеда, Д.И. Когана. Теория и методы решения задач многокритериальной оптимизации занимают существенную часть диссертации.
Вопросы сложности решения задач оптимизации, которым также в
диссертации уделяется существенное внимание, рассматривались в работах A.B. Кельманова, A.B. Пяткина, М.Ю. Хачая, A.B. Плясунова, A.A. Колоколова JI.A. Заозерской, A.B. Еремеева и многих других.
Помимо теоретических основ разрабатывались также программные комплексы для решения задач оптимизации, объединяющие различные методы решения задач глобальной оптимизации. Следует отметить такие разработки, как программный комплекс ДИСО "Диалоговая Система Оптимизации" (ВЦ РАН), пакеты BARON, BONMIN, KNITRO, СВС и другие. Объединение различных методов оптимизации в один программный комплекс является вполне оправданным подходом, так как многие методы решепия оптимизационных задач взаимосвязаны. Например, локальные методы поиска экстремума используются для нахождения рекордов в методах типа ветвей и границ. Методы линейного программирования применяются для нахождения оценок при организации ветвлений.
Несмотря на существенный прогресс, достигнутый в области глобальной оптимизации, возможностей существующих подходов нередко не достаточно для решения практических задач оптимизации за приемлемое время. Поэтому актуальна задача эффективной реализации методов глобальной оптимизации на современных вычислительных платформах. Основные результаты в области применения параллельных вычислений для решения задач глобальной оптимизации получены Р.Г. Стронги-ным, В.П. Гсргелем, Я.Д. Сергеевым, К.А. Байкаловым, Ю.Г. Евтушенко, A.A. Станевичюсом, В.У. Малковой. Следует также отмстить работы A.A. Лазарева в области распараллеливания вариантов метода динамического программирования. Вопросы эффективной организации балансировки вычислительной нагрузки между процессорами при реализации метода ветвей и границ рассматривались в работах G. Ananth, V. Kumar, P. Pardalos, L. Casado, T. Crainic, M. Tolouse, T. Ralphs и другими зарубежными исследователями. Методы распределенных вычислений применялись А.П. Афанасьевым, В.В. Волошиновым, С.А. Смирновым для решения различных оптимизационных задач в сервис-ориентированных средах. Грид-системы персональных компьютеров использовались A.A. Семеновым и О.С. Заикиным для решения задачи выполнимости (SAT). Применение грид-систем для решения задач оптимизации также нашло отражения в работах зарубежных исследователей Е. Alba, F.Almeida, M. Blesa, К. Aida, W. Natsume, Y. Futakata. Тематике эффективной реализации методов решения оптимизационных задач на параллельных и распределенных системах в диссертации уделяется большое внимание.
Практическая значимость и большое количество работ в области дис-
сертационного исследования свидетельствуют о его важности и высокой степени актуальности.
Цель работы. Основной целью диссертационной работы является разработка и реализация методов решения задач оптимизации, а также всестороннее теоретическое и экспериментальное исследование их эффективности. Для достижения этой цели были поставлены и решены следующие задачи:
• разработка новых и развитие существующих алгоритмов глобальной и дискретной оптимизации с одним и несколькими критериями, основанных на идеях неравномерных покрытий;
• разработка и реализация детерминированных методов решения задач многокритериальной оптимизации;
• теоретическое и экспериментальное исследование эффективности методов решения задач глобальной оптимизации, получение оценок сложности оптимизационных алгоритмов;
• создание мультиплатформенного расширяемого программного комплекса, предназначенного для решения задач оптимизации па многопроцессорных вычислительных системах.
На защиту выносятся следующие результаты:
1. Получены новые миноранты и нижние оценки для минимизации скалярных функций. Предложены новые миноранты, основанные на оценке спектра матрицы Гессе, разработан метод вычисления таких оценок. Для задач оптимизации с параллелепипедными ограничениями предложены новые миноранты, учитывающие необходимые условия оптимальности.
2. В методе неравномерных покрытий предложены способы сокращения области иоиска, основанные на построении дополнения покрывающего множества до параллелепипеда, позволяющие существенно повысить быстродействие метода.
3. Метод неравномерных покрытий перенесен на задачи частично-целочисленного программирования, доказана корректность алгоритма.
4. Для задачи многокритериальной оптимизации с параллелепипедными ограничениями доказаны новые свойства е-Парсто множества.
устанавливающие связь между этим множеством, границей Парето и оболочкой Эджворта-Парето.
5. Метод неравномерных покрытий для задач многокритериальной оптимизации обобщен на случай произвольных минорант, доказана сходимость метода.
6. Для задач многокритериальной оптимизации с функциональными ограничениями введено новое понятие приближенного решения — множество е, ¿-Парето и предложен алгоритм для его построения, доказана сходимость метода.
7. На основе идей многокритериальной оптимизации введено понятие эффективной оболочки множества, показано, что эта оболочка содержится в его выпуклой оболочке. Введены понятия е-эффективной границы и е-оболочки множества, предложены методы их численного построения. Разработанные понятия и методы применены для задачи построения внешней границы рабочей области многосекционного робота-манипулятора с заданной точностью.
8. Разработан подход к оценке сложности метода неравномерных покрытий, с помощью которого получены верхние оценки сложности различных вариантов этого метода для различных классов задач.
9. Получены оценки сложности метода ветвей и границ для задачи о булевом ранце. Проведено экспериментальное исследование и сопоставление их точности.
10. Исследован вопрос параллельной вычислительной сложности одной из возможных реализаций метода ветвей и границ. Получена общая оценка вычислительной сложности, не зависящая от конкретной задачи. Для задачи о сумме подмножеств получены асимптотические формулы для минимальной параллельной сложности, максимального параллельного ускорения и эффективности.
11. Предложен подход к реализации детерминированных и гибридных методов глобальной оптимизации на многопроцессорных вычислительных комплексах, основанный на разделении вычислительной, коммуникационной и управляющей функциональности в программе. Разработан язык описания управления параллельным процессом поиска глобального экстремума, основанный на формализме конечных автоматов. Этот язык позволяет описывать как управление
процессом оптимизации, так и балансировку вычислительной нагрузки между процессорами параллельной системы. Такой подход позволяет независимым образом реализовывать и отлаживать соответствующие компоненты, а также, облегчать процесс расширения программного комплекса за счет повторного использования ранее разработанных компонент.
12. На основе разработанного подхода реализован программный комплекс для решения задач глобальной оптимизации на последовательных. параллельных и распределенных системах. В рамках этого программного комплекса были реализованы различные алгоритмы для решения задач конечномерной оптимизации с одним и несколькими критериями, проведены многочисленные эксперименты на различных вычислительных платформах. В частности, разработана и выполнена эффективная параллельная реализация метода ветвей и границ для задачи о булевом ранце с одним ограничением, превосходящая по скорости работы известные аналоги.
Методы исследований. В работе используются методы глобальной оптимизации, методы дискретной математики и математического анализа, методы параллельных и распределенных вычислений.
Научная новизна. Все основные результаты диссертации являются новыми. Разработаны новые алгоритмы решения задач оптимизации с заданной точностью па основе концепции неравномерных покрытий. В частности, в диссертации даны новые миноранты для скалярных функций, оригинальные способы сокращения области поиска, основанные на построении дополнения покрывающего множества до параллелепипеда. Предложенная техника позволила существенно повысить быстродействие метода неравномерных покрытий.
Метод неравномерных покрытий для задач многокритериальной оптимизации обобщен на случай произвольных минорант и перенесен на задачи с функциональными ограничениями.
Введено новое понятие эффективной оболочки множества, обобщающее понятие оболочки Эджворта-Парето для многокритериальных задач. Показано, что эта оболочка содержится в его выпуклой оболочке. Введены понятия е-эффективной границы и £-оболочки множества, предложены методы их численного построения.
Получены новые оценки сложности различных вариантов метода неравномерных покрытий. Также в диссертации предложен новый подход к оценке вычислительной сложности метода ветвей и границ в задаче о
сумме подмножеств, с помощью которого получены оценки для конкретных вариантов метода и серий задач.
Предложен оригинальный подход к реализации детерминированных и гибридных методов глобальной оптимизации на многопроцессорных вычислительных комплексах, основанный на разделении вычислительной, коммуникационной и управляющей функциональности в программе. На базе предложенного подхода создан программный комплекс для решения задач оптимизации.
Теоретическая и практическая ценность. Работа носит теоретический и прикладной характер. Полученные результаты могут найти применение в теории глобальной, дискретной и непрерывной оптимизации с одним и несколькими критериями. В частности, техника получения оценок числа шагов методов, изложенная в диссертационной работе, может быть применена для теоретического исследования сложности детерминированных методов решения задач оптимизации. Подход, предложенный в диссертационной работе, может использоваться при создании оптимизационных пакетов, ориентированных на многопроцессорные системы. Разработанный в результате работы над диссертацией комплекс программ применим при решении различных прикладных задач оптимизации, возникающих в вычислительной химии и биологии, при проектировании летательных аппаратов, машин и механизмов, в экономике и других областях. Разработанные в диссертации методы решения задач многокритериальной оптимизации были применены для практически важной задачи нахождения рабочей области робота-манипулятора.
Апробация работы. Результаты диссертационной работы докладывались на следующих конференциях:
• XII международная конференция "Математические методы распознавания образов", Москва, 2005 г.;
• VII Международная конференция "Дискретные модели в теории управляющих систем", Москва, 2006 г.;
• международная конференция "Тихонов и современная математика: Вычислительная математика и информатика", Москва, 2006 г.;
• вторая международная конференция "Распределенные вычисления и Грид-технологии в науке и образовании", С11Ш'2006, Дубна, 2006 г.;
III международная конференция "Параллельные вычисления и задачи управления" РАСО'2006 памяти И.В. Прангишвили, Москва, 2006 г.;
II международная науч.-практ. конференция "Современные информационные технологии и ИТ-образование":, Москва, 2006 г.;
V московская международная конференция по исследованию операций ORM2007, Москва, 2007 г.;
IX международный семинар "Дискретная математика и ее приложения", Москва, 2007 г.;
Parallel Computing Technologies 9th International Conference, PaCT 2007, Переславль-Залесский, 2007 г.;
вторая международная конференция "Системный анализ и информационные технологии" САИТ-2007, Обнинск, 2007 г.;
XV международная конференция "Проблемы теоретической кибернетики Москва, 2008 г.;
XXI International Symposium on Nuclear Electonics and Computing, Варна, 2007 г.;
Discrete and Global Optimization, International Conference in Honor of 50-th Anniversary of Glushkov Institute of Cybernetics, Ялта, 2008 г.;
Научный сервис в сети Интернет'2008: решение больших задач, Абрау-Дюрсо, 2008 г.;
четвертая Международная конференция "Параллельные вычисления и задачи управления" РАСО'2008, Москва, 2008 г.;
третья международная научно-практическая конференция "Современные информационные технологии и ИТ-образование". Москва, 2008 г.;
третья международная конференция "Распределенные вычисления и Грид-технологии в науке и образовании", GRID'2008, Дубна, 2008 г.;
XVII международная школа-семинар "Синтез и сложность управляющих систем "им. академика О.Б. Лупанова, Москва, 2008 г.;
4th EGEE User Forum, Catania, Sicily, Italy, 2009 г.;
Параллельные вычислительные технологии (ПаВТ'2009), Нижний Новгород, 2009 г.;
International Supercomputing Conference, Hamburg, Germany, 2009 г.;
Optimization and applications (OPTIMA-2009), Petrovac, Montenegro, 2009 г.;
третья международная конференция "Системный анализ и информационные технологии" САЙТ - 2009, Звенигород, 2009 г.;
четвертая конференция "Современные информационные технологии и ИТ-образование", Москва, 2009 г.;
третья международная научная конференция "Суперкомпыотерные системы и их применение" (SSA'2010), Минск, Беларусь, 2010 г.;
8-я международная конференция "Интеллектуальная обработка информации", Пафос, Кипр, 2010 г.;
V Международная конференция «Параллельные вычисления и задачи управлениям РАСО-2010, Москва, 2010 г.;
VI Московская международная конференция по исследованию операций (ORM2010), Москва, 2010 г.;
международная конференция по прикладной математике и информатике, посвященная 100-летию со дня рождения академика A.A. Дородницына, Москва, 2010 г.;
4-я Международная конференция "Распределенные вычисления и грид-технологии в науке и образовании Дубна, 2010 г.;
XV Байкальская международная школа-семинар "Методы оптимизации и их приложения", Листвянка, 2011 г.;
Eleventh International Conference on Parallel Computing Technologies (PaCT-2011), Казань, 2011 г.;
II International conference "Optimization and applications" (OPTIMA-2011), Petrovac, Montenegro, 2011 г.;
• 3rd Int. Conf. on Optimization Methods and Software, Chania, Crete, Greece, 2012 r.;
• шестая международная конференция "Параллельные вычисления и задачи управления РАСО'2012", Москва, 2012 г.;
• международная молодежная конференция-школа "Современные проблемы прикладной математики и информатики", Дубна, 2012 г.;
• 3rd International conference "Optimization and applications" (OPTIMA-
2012), Petrovac, Montenegro, 2012 r.
• 4th International conference "Optimization and applications" (OPTIM A-
2013), Petrovac, Montenegro, 2013 r.
• 20th Conference of the International Federation of Operational Research Societies (IFORS), Barcelona, Spain, 2014 r.
• V International Conference on Optimization Methods and Algorithms (OPTIMA-2014), Petrovac, Montenegro, 2014
• Международная молодежная конференция "Современные проблемы прикладной математики и информатики", Дубна, 2014
• VIII Всероссийская научная конференция с международным участием "Математическое моделирование развивающейся экономики, экологии и технологий", Москва, 2014
Также результаты диссертационной работы докладывались на научных семинарах ВЦ РАН, ИППИ РАН, ИСА РАН, ИПУ РАН.
Личный вклад автора.
Результаты, изложенные в диссертации, получены автором самостоятельно. В коллективных публикациях автору принадлежат те их части, которые составляют основу диссертации. В работах [20, 22, 27, 28] автором получены новые миноранты и нижние оценки для минимизации скалярных функций, предложены способы сокращения области поиска, метод неравномерных покрытий перенесен на задачи частично-целочисленного программирования, доказана корректность алгоритма.
В работах [23, 25, 30] автором доказаны новые свойства г-Парето множества, метод неравномерных покрытий для задач многокритериальной оптимизации обобщен на случай произвольных минорант, доказана сходимость метода, введено понятие эффективной оболочки множества, показано, что эта оболочка содержится в его выпуклой оболочке, введены
понятия е-эффсктивной границы и г-оболочки множества, предложены методы их численного построения. Также в перечисленных работах автором разработан подход к оценке сложности метода неравномерных покрытий, с помощью которого получены верхние оценки сложности различных вариантов этого метода для различных классов задач.
В работах [2, 7, 8, 15, 18, 19, 21] соискателем получены оценки сложности метода ветпей и границ для задачи о булевом ранце, исследован вопрос параллельной вычислительной сложности одной из возможных реализаций метода ветвей и границ, получены асимптотические формулы для минимальной параллельной сложности, максимального параллельного ускорения и эффективности для задачи о сумме подмножеств.
В работах [5, 6, 26, 29] автором разработан подход к созданию пакетов для решения задач оптимизации на современных платформах, на базе которого выполнена реализация программного комплекса для решения задач глобальной оптимизации на последовательных, параллельных и распределенных системах. Применения этого программного комплекса для решения различных задач рассмотрены в работах [4, 12, 13, 14], где автор адаптировал эти задачи для выполнения расчетов в рамках разработанного программного комплекса.
Структура и объем работы.
Диссертация состоит из введения, шести глав, заключения, приложения и списка литературы, содержащего 217 наименований. Общий объем диссертации составляет 265 страниц. СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы, перечисляются цели и задачи исследования, дается оценка научной новизне, теоретической и практической значимости работы. Проводится обзор основных результатов по тематике исследований. Также приводится методология исследования и перечисляются положения, выносимые на защиту.
Глава 1 посвящена развитию метода неравномерных покрытий для решения задач глобальной оптимизации с одним критерием. В разделе 1.1 ставится задача поиска глобального экстремума и производится обзор основных подходов к се решению. Рассматривается задача отыскания глобального минимума непрерывной функции / : М" —> М на компактном допустимом множестве X С Мп:
/* = д1оЬтт/(х) = /(ж»), (1)
хЕЛ
где х» — любая точка, в которой достигается глобальный минимум, рав-
НЫЙ /,.
В разделе 1.2 рассматривается случай, когда допустимое множество X имеет простую структуру, т.е. характеризуется следующими свойствами:
1. минимум миноранты на множестве простой структуры легко определяется;
2. декомпозиция множества простой структуры на подмножества простой структуры легко реализуется алгоритмически;
3. нахождение допустимой точки внутри множества простой структуры представляет собой простую задачу.
Примером множеств простой структуры являются n-мерный параллелепипед или многогранник, задаваемый системой линейных неравенств. Теоретические положения диссертации верны для любого множества простой структуры, но алгоритмы приведены только для случая п-мерного параллелепипеда.
Для задачи (1) определим множество глобальных решений X* и множество е-оптимальных решений Хе:
X, = {xeX: J{x) = f.},Xe = {хеХ: f(x) < /* + е},£ > 0. (2)
Предполагается, что множество X* не пусто. Требуется найти хотя бы одну точку из множества Хе.
Для множества Z С R", функции /(ж) : R" R и числа Л е К определим Лебеговское множество £(/(■), Z, А) = {х € Z : f(x) > Л} и открытое Лебеговское множество £'(/(•), Z, А) = {х S Z : f{x) > А}.
Используя введенное понятие, можно определить необходимые и достаточные условия глобальной оптимальности для любой точки х* € X следующим образом:
Аналогично записывается критерий глобальной е-оптималыгости. Пусть хе 6 X, тогда
ж, б £(/(•), X, f(x£) -е) = Х.
Непосредственное применение приведенных соотношений для определения е-оптимальных решений, как правило, является затруднительным.
В таких случаях прибегают к дроблению множества X на подмножества и к построению на них минорант. Рассмотрим набор множеств {X,}, Х{ С X, г = 1,...,/. На каждом множестве X, определим миноранту цг(х) такую, что /(х) > //¿(ж) для всех х € X, П X,. Пусть заданы совокупность допустимых точек Л^ = {х\,... ,Хк} и совокупность множеств Мк = {А,..., Ск}, удовлетворяющих условию
Сг С С(щ(-), Хи 1{х{) - г), г = 1,..., к. (3)
Будем говорить, что совокупность множеств Мк покрывает множество X*, если
X» п и*=1 А Ф 0. (4)
Множества будем называть покрывающими.
Теорема 1.1 Если для наборов допустимых точек N1- и покрывающих множеств Мк выполнено условие (4), то тонка хг = ащттх6лгк /(я) является е-оптимальпым решением задачи (1) и для пего справедлива оценка:
1{хТ) > и > /(яг) - е (5)
В конце пункта 1.2 приводится формальное описание алгоритма, реализующего метод нахождения г-оптималыюго решения для множеств простой структуры, корректность которого обосновывается с помощью теоремы 1.1.
В пункте 1.3 рассматривается случай, когда допустимое множество задано с помощью функциональных ограничений.
Х = {хёГ: д{х) < 0т}, (6)
где д(х) : К" —> К.711 — непрерывная вектор-функция. Предполагается, что допустимое множество X содержится в некотором ограниченном множестве Р из 7?" простой структуры. Для упрощения изложения определим вспомогательную функцию ф(х) = тах(д^(х),... ,д^тЦх)).
Для ¿€1 определим 6-допустимое множество следующим образом:
X15 = {х е К" : ф(х) < ¿}. (7)
Положим 8 = тф : X5 ф 0}, 6 = 8ир{5 : X5 С Р}.
При 5 < 6 < 6 положим
¡1 = тт/(х).
Рассмотрим £ g 1+ и ii £ R, J2 £ I, | < J) < ¿2 < 8. Определим множество
A = {xG Xs2 : f{x) < j* + £}.
В частном случае, ¿1 = 0, 82 = S это множество будем называть множеством е,6-оптимальных peiueuuü и обозначать через X
Х5£={хеХ6 : fix) </, + £>.
Рассмотрим совокупность множествХ\,...,Хк, где все Xi С Р. Определим миноранты ßiix) такие, что fix) > /¿¿(ж) для всех х из Xi и миноранты Viix) такие, что ф{х) > и^х) для всех х из Xi. Пусть заданы совокупность точек Nk = {х\,... ,Хк} из Х5г и совокупность множеств Мк = {А, • • •, А;}, удовлетворяющих условию
Li С dßii-), Xi, fixi) - е) U С'Ы-),Хи 8г). (8)
Условие покрытия в данном случае имеет вид:
Р = (9)
Справедлива следующая теорема.
Теорема 1.2 Если для наборов точек N к и покрывающих множеств Мк выполнено условие (9), то точка xr = argminlSNkfi%) принадлежит множеству Хр'02 и справедлива оценка:
St+e>fixr)>fi\ (10)
Выделим два важных частных случая теоремы 1.2. В первом ¿1 < 0, ¿2 = 0, при этом точка хТ является приближенным допустимым решением, для которого справедливо неравенство: /»" + £ > f{xr) > /». Из-за отсутствия непрерывности слева функции чувствительности в этом случае приближенное и точное решения могут сколь угодно отличаться. Кроме того, для задач где 6 = 0 данный подход неприменим, т.к. здесь внутренность множества X пуста.
Во втором случае ¿1 = 0, 82 > 0. Положим 6 = Ö2. Точка хт будет приближенным, но возможно недопустимым решением, для которого справедливо неравенство: /» + £ > f(xr) > ff. При стремлении е и 8 к нулю значение /(хг) будет стремиться к /,.
Далее приводится описание алгоритма поиска условного экстремума и обоснование его корректности с использованием Теоремы 1.2. В алгоритме покрывающими множествами являются параллелепипеды. Метод расширяется на случай задач частично-целочисленного программирования
за счет введения простого правила сокращения параллелепипеда. Эффективность предложенного метода демонстрируется на примере двух тестовых задач, в которых удалось улучшить ранее известные значения экстремума.
Пункт 1.4 посвящен вопросам построения минорант на множествеX*, возникающем в процессе работы метода. Показано, что если ki и Я, ~ такие числа, что спектр матрицы Гессе fxx(x) при х £ Xi полностью лежит в пределах отрезка [к{, КЦ, то можно определить миноранту ßi{x) и мажоранту Mi{х) для функции f{x):
к-
= f(Ci) + ifx(Ci),X-Ci) + -±\\х - Cj||2, (11)
Mi{x) = /(cj) + (Мск),х- а) + Щ\\х - а\\2, (12)
где с,- £ Х{ — некоторая точка множества Xi. Предложенная миноранта точнее, чем обычно используемая для минорирования Липшицева миноранта второго порядка, так как спектр матрицы Гессе гарантированно лежит в пределах отрезка [—Li, Li], где Li — константа Липшица для градиента миноруруемой функции.
В теореме 1.1 требуется, чтобы неравенство ßi(х) > f(x) выполнялось только для точек из пересечения Xi ПХ. В диссертационной работе показывается, что если множество Xi не имеет общих точек с границей множества X, то следующая функция будет минорантой f(x) на множестве Xi П Хг:
tii(x) = f(xi)-Ki-\\x-xi\\ (13)
Для случая, когда допустимое множества и множества Xi, получающиеся в процессе его декомпозиции, являются параллелепипедами, факт наличия общей границы Xi и X легко проверяется и, как показывают эксперименты, применение миноранты (13) позволяет существенно сократить перебор по сравнению с минорантой 11 и традиционными Лип-шицевыми минорантами.
При реализации метода неравномерных покрытий на практике требуется определять подмножества Лебеговских множеств, так называемые покрывающие подмножества. В отличие от Лебеговских множеств, имеющих сложную форму, покрывающие подмножества являются параллелепипедами, что облегчает их использование в алгоритме. В диссертации показано, что для рассматриваемых минорант существуют три варианта формы Лебеговского множества:
1. пересечение полупространства и параллелепипеда Î2;
2. дополнение шара до параллелепипеда Г2;
3. пересечение шара и параллелепипеда Г2.
Для каждого из этих случаев также приведены способы определения покрывающих подмножеств. Стандартный подход, применяемый в методе неравномерных покрытий, состоит в том, что параллелепипед либо полностью исключается из дальнейшего рассмотрения, либо делится на меньшие параллелепипеды. Новый подход, предложенный в диссертационной работе, позволяет уменьшать параллелепипед в случае, когда нет возможности отбросить его целиком.
В завершении главы приводятся результаты вычислительных экспериментов. На серии полиномов со случайными коэффициентами исследуется эффективность метода неравномерных покрытий с различными способами построения покрывающего множества и различными минорантами. Дано сравнение с пакетами глобальной оптимизации BARON и LINDOGLOBAL.
Результаты расчетов показали, что из рассмотренных вариантов наиболее эффективным является применение метода неравномерных покрытий с использованием миноранты (13), усиленное предложенной в диссертационной работе техникой сокращения параллелепипедов. При этом, ускорение по сравнению со стандартным вариантом, в котором используется стандартная липшицева миноранта второго порядка, составило в среднем 10-20 раз. Также все задачи были решены существенно быстрее чем пакетами LINDOGLOBAL и BARON. Выигрыш но времени составил 5-10 раз по отношению к BARON и 25-50 раз по отношению к LINDOGLOBAL.
Глава 2 посвящена задачам многокритериальной оптимизации (МКО). В разделе 2.1 приводится общая постановка задачи, рассматриваются основные подходы к ее решению. Задача МКО формулируется следующим образом:
min F(x), (14)
XGA
где X — допустимое множество параметров, а вектор-функция F(-) : Мп —> Rm определяет векторный критерий, компоненты которого fW (■),..-,/{гп)(-) составляют набор из m скалярных критериев. Образ У = F(X) допустимого множества X при отображении F назовем множеством достижимых критериальных векторов. Всюду далее вектор-функция F(-) предполагается непрерывной, а множество X — непустым
компактом. При сделанных предположениях множество У также будет непустым компактом. Для произвольной точки z Е Rm определим юго-западное SW(2) и северо-восточное NE(z) множества следующим образом:
SW(z) = {у е Mm : у < z}, NE(z) = {у € Rm : у > z}.
Здесь и далее векторное неравенство понимается следующим образом: а < Ь означает одновременное выполнение неравенств а™ < Ь^ для всех i = 1,... ,т.
Для произвольного множества Í! С Rm определим его множество Парето 'Р(П) следующим образом:
-P(íí) = {и Е О : Í2 П SW(w) = w}. (15)
Точки множество 'Р(П) являются граничными для множества Я. Если в качестве Í2 взять множество достижимых критериальных векторов У, то данное определение совпадает со стандартным определением множества Парсто, принятым в работах по многокритериальной оптимизации.
Расширим определения SW(;z), NE(.z) на случай произвольного множества П С Rm:
SW(ÍÍ) = UygíjSW(j/), NE(Í2) = UyenNE(y).
Множество NE(fi) называют оболочкой Эджворта-Парето множества П.
Пункт 2.2 посвящен решению задачи (14), в которой множество X является n-мерным параллелепипедом: X = {х € К" : а < х < Ь}. Метод неравномерных покрытий для такой задачи был обобщен Ю.Г. Евтушенко и М.А. Потаповым в 1985 году с использованием Липшице-вых минорант. В диссертационной работе доказываются новые свойства введенного в этой статье множества е-Парето и метод распространяется на случай произвольных минорант.
Для £ > 0 набор точек Ye С У будем называть множеством е-Парето, если:
1. для любой точки у* € Р(У) существует такая точка уе € У, что
Уе - е ■ lm < У(16)
V<ye) = У. (17)
Рис. 1: Иллюстрация теоремы 2.1
Здесь через 1т обозначен вектор из пространства Rm, все компоненты которого равны 1.
В диссертационной работе доказываются ряд новых свойств множества е-Парето. Приведем наиболее значимые свойства.
Теорема 2.1 Справедливы следующие утверждения, связывающие оболочки Эджворта-Парето множества £-Парето и множества достижимых критериальных векторов:
NE(У£) С NE(7>(F)) = NE(F) С NE(Ke - е • em), (18) МЩУ), NE(y)) < dH(NE(Ye), NE(y - e • lm)) < eу/Ш, (19) dff(NE(y), NE(y - e • lm)) < dff(NE(ye), NE(y - e • lm)) < e^ (20)
где c?#(■, ■) расстояние Хаусдорфа.
Следующая теорема дает оценку близости множеств Парето ие-Парето.
Теорема 2.2 Для любого S > 0 найдется такое е > 0, что любое множество е-Парето Ye образует ¿-сеть для множества V(Y).
Далее в разделе приводится способ построения множества е-Парето. Прежде всего понятие Лебеговского множества обобщается на случай многокритериальной задачи. Для произвольных множеств Л С У, О С R" и вектор-функции F(-) : Rn Rm определим Лебеговское множество
£(F(-), О, Л) = {х 6 П : F[x) € NE(A)}. (21)
Ш NEW,-e-eJ\NE(P(Y))
MWWWff,)
my,)
P(Y)
В случае тп = 1 это определение совпадает с определением, данным ранее для скалярной функции.
В диссертационной работе доказывается следующая теорема, аналогичная теореме 1.1. Рассмотрим набор ... ,Хк, Х^ С X подмножеств допустимого множества и совокупность конечных подмножеств множества достижимых критериальных векторов Ах,...,Ак, Л; С У. Пусть — миноранта для вектор-функции на множестве Х{ т.е. щ(х) < .Р(х) для каждого х € Х(. Пусть задана совокупность подмножеств ..., Ск множества X, удовлетворяющих для заданных Х{, Л,-, соотношениям:
А с С(щ{-),Хг,Аг - е ■ ет),г = 1,...,к, (22)
где Лг — е • ет = {х : х = А — е • ет для некоторого А 6 Л*}.
Будем говорить, что совокупность множеств {£;} покрывает множество X, если
х = и ии (23)
Теорема 2.3 Если выполнено условие покрытия (23), то множество Ук = Р (и,к=1Лг) является множеством е-Парето для задачи (14).
Укажем способ определения покрывающих множеств. Пусть ¿¿¿(-) — произвольная миноранта для вектор-функции .Р(-) на множестве Х{. Пусть также для каждого з £ М известен способ определения минимума сер функций на множестве Х^ а* = (а-1',..., а-™').
^ _ | Xi, если найдется такое А £ Л* что аг > А — £ • ет, ' 1 0 в противном случае .
Приводится описание алгоритма построения множества е-Парето, для обоснования корректности которого применяется Теорема 2.3. В конце раздела эффективность предложенного алгоритма демонстрируется на различных тестовых задачах.
Пункт 2.3 посвящен решению задачи (14) в случае, когда множество X определяется с помощью функциональных ограничений:
X = {х £ В : в{х) < 0*}, (25)
где С(-) = ■.. ~ набор функций ограничений, а В — 71-
мерный параллелепипед. Условия (25) можно переписать в эквивалентном виде
X = {х £ В : ф(х) < 0}, (26)
где ф{х) = та
Всюду далее вектор-функции F(•), С(-) предполагаются непрерывными.
Понятие множества г-Парето обобщается для случая многокритериальных задач с ограничениями. Для 5 £ К определим X5 = {х £ : ф(х) < положим У5 = Р(Х6).
Пусть даны действительные числа е > 0,6 > 0. Множество С? Я: У5 будем называть множеством е, 6-Парето , если выполнены условия:
1. для любой точки у* € Р(У) существует такая точка д € ф, что
9-е-1т<У*, (27)
2.
ПО) = Я- (28)
Рассмотрим набор Х\,..., Ху-. Хг С X подмножеств множества В и совокупность конечных подмножеств Лх,... , Л; С У6. Пусть ¡м(-) — миноранта для вектор-функции .Р(-) на множестве Х{ т.е. щ(х) < Р(х) для каждого х £ а Уг{') — миноранта для ф(-) на этом же множестве. Пусть задана совокупность подмножеств С\,...,Ск множества X, удовлетворяющих для заданных цг(-) соотношениям:
А С £(т(-),Хг, Л,- - е • ет) и С'{^{-),Хи 0), г = 1,..., /г, (29)
где \ — е ■ ет = {х : х = \ — е • ет для некоторого А £ Л*}.
Будем говорить, что совокупность множеств {А} покрывает множество X, если
* = и *=1А- (зо)
Теорема 2.4 Если выполнено условие покрытия (30), то множество Ук = ~Р (и^=1Лг) является множеством е, ¿-Парето для задачи (14).
Приводится описание алгоритма построения множества е, ¿-Парето, доказывается его корректность и конечность числа шагов алгоритма. Приводится описание реализации и экспериментов, подтверждающих эффективность предложенного метода. Пример множества £, <5-Парето для следующей тестовой задачи
_(х(1))2 _ (ж(2))2 + 1+0.1 соэ(16агйап < 0, (хМ - 0.5)2 + (ж«2) - 0.5)2 - 0.5 < О,
1.2
\
08
0.6
ч
0.2
\
0
0 0.2 0.4 0.6
0.8
1.2
Рис. 2: Множество 0.01, 0.01-Парето
построенного предложенным методом, приведен на Рис. 2.
В третьей главе определяется понятие эффективной оболочки множества и предлагается метод ее аппроксимации для случая, когда, множество является образом компакта при непрерывном отображении.
Обозначим через Ат множество всех векторов размерности т, компонентами которых являются 1 или —1. Для вектора Л 6 Ат запись У2 У\ означает одновременное выполнение т условий
Если не выполнены соотношения у\ У2 и У2 Ух, то векторы и У2 называются несравним.ыми для данного А 6 Ат.
Для точки у £ Мш и заданного Л £ Ат определим множества 0\{у) = {г £ К771 : г у} и 0*х(у) = {г £ Мт : у г}. Введенные обозначения обобщаются на случай множества ^ С Кт: = ^гег^х(г), ^д(^) =
Для произвольного компактного множества У С Кт точку у £ У назовем \-точкой, если в множестве У нет таких точек г, что г у и г ф у. Объединение всех Л-точек назовем А-границей множества У и обозначим через Т\(У), т.е.
(31)
7МУ) = {у е У : у П Их(у) = у}.
(32)
Объединение А-границ "Ре//(У) = илеЛт^лОО назовем эффективной границей множества У. Справедливо следующее утверждение.
Утверждение 3.1 Эффективная граница компактного строго-выпуклого множества совпадает с его границей.
Несложно проверить, что данное утверждение перестает выполняться для произвольного выпуклого множества.
Множество Н(У) = Пделт£)д СР\0^)) будем называть эффективной оболочкой множества У. Так как для компактного множества У С Ет справедливо включение У С Б*х (Р\(У)) при любом А е Лт, то У С Н(У). Следующая теорема связывает выпуклую оболочку Сопь{У) множества У (наименьшее выпуклое множество, содержащее У) и его эффективную оболочку.
Теорема 3.1 Для произвольного компактного множества У справедливо включение
У С Н{У) С Сопи{У), (33)
и равенство
Сопу{У) = СОПУ(Рс/1(У)). (34)
На практике построить эффективную оболочку точно возможно лишь для ряда частных случаев. В общем случае необходимо понятие аппроксимации эффективной оболочки. Для е > 0 и некоторого А 6 Лт множество точек У£х из М"1 назовем е-аппроксимацией Х-границы, если для каждой точки у» € ~Рх{У) найдется такая точка уе в У£х, что у£ + еА У* и, кроме того, множество У} состоит только из несравнимых точек.
Пусть имеется набор {V/}, А е Ат. Тогда илелтУ\ назовем е-эффективной границей множества У. Внешней е-эффективной границей будем называть множество (_1лелт (У\ + еА).
Так как У — компакт, то У С {Р\{У)) и, следовательно, У С £>д (Уд + еА) для всех А е Ат. Таким образом, У С Пдел^л (^л + ^6)•
Множество П+ Аг) будем называть е-эффективной оболочкой множества У. Очевидно Н(У) С Ллелт-Од (^л + Лля любого е > 0.
Далее в разделе доказываются некоторые свойства е-эффективной оболочки и приводится алгоритм построения е-эффективной границы, позволяющий получать ее за конечное число шагов.
В заключительной части главы рассматривается применение понятия е-эффективной оболочки для практически значимой задачи построения рабочей области робота-манипулятора.
Глава 4 посвящена вопросам вычислительной сложности различных вариантов метода ветвей и границ. В разделе 4.1 определяются основные понятия этого метода. Метод ветвей и границ состоит в последовательной декомпозиции исходного допустимого множества на подмножества, с исключением подмножеств, которые заведомо не содержат оптимального решения. Общая схема метода состоит в следующем:
1. Поместить в список подмножеств исходное подмножество X.
2. Выбрать подмножество С из списка подмножеств.
3. Произвести действия, направленные на вычисление верхних и нижних оценок целевой функции, сокращение и декомпозицию множества С?. Полученные новые подмножества (если таковые получены) добавить в список подмножеств.
4. Если список подмножеств пуст, то завершить алгоритм, в противном случае перейти к шагу 2.
Процесс работы метода ветвей и границ можно схематично представить в виде дерева ветвлений — графа, вершинами которого являются обрабатываемые подмножества, а дуги соединяют одно подмножество с другими, полученными из пего в результате декомпозиции.
Сложностью метода ветвей и границ при решении данной задачи будем называть число итераций цикла 2-4, которое потребовались для решения задачи. Очевидно, что это число совпадает с количеством вершин в дереве ветвлений на момент завершения работы алгоритма.
Далее сложность обозначается буквой Б. Также вместо множества всех вершин иногда удобнее рассматриваться множество концевых вершин V, которое для бинарных деревьев связано с 5 формулой:
5 = 2К-1.
Число V будем называть приведенной сложностью.
Раздел 4.2 посвящен исследованию сложности метода неравномерных покрытий. Основной реализацией метода неравномерных покрытий является алгоритм бисекций, который укладывается в схему метода ветвей и границ. Метод бисекций состоит в последовательной декомпозиции исходного п-мерного параллелепипеда, содержащего допустимое множество X, на параллелепипеды меньшего диаметра. На шаге 3 производится уменьшение рассматриваемого п-мерного параллелепипеда и разбиение полученного параллелепипеда на два равных параллелепипеда вдоль
максимального ребра. В диссертационной работе доказывается следующая теорема, дающая верхнюю оценку сложности алгоритма бисекций.
Теорема 4.1 Пусть существует с?, > 0 такое, что любой параллелепипед с диаметром, не превосходящим (¿*, всегда полностью исключается из рассмотрения на шаге 3 метода ветвей и границ, (1 — диаметр исходного параллелепипеда. Тогда сложность метода бисекций не превосходит величины
т)
гдев(п)= 2/1об2(1-&).
Несложно показать, что данная оценка имеет экспоненциальную асимптотику при увеличении п.
Теорема 4.1 используется для получения оценок сложности конкретных вариантов метода неравномерных покрытий, рассмотренных в главах 1,2 диссертации. В частности, показывается, что если для получения оценок используются асимптотически-точные миноранты, то все предложенные в работе алгоритмы завершаются за конечное число шагов.
Раздел 4.3 посвящен формулировкам и основным понятиям, связанным с вычислительной сложностью метода ветвей и границ для задачи о ранце
п п
тах, У"^¿Ж; < С,х{ е {0,1}. (35)
¿=1 ¿=1
Метод ветвей и границ для дайной задачи основан на разбиении допустимого множества на подмножества с помощью придания переменным значений 0,1. В 1976 году Ю.Ю. Финкелыптейном был построен пример задачи, для решения которой требуется — 1 шагов метода ветвей и границ:
п п
2хг -> тах, ^ 2х{ < 2|п/2] + 1. (36)
¿=1 ¿=1
В том же году В.П. Гришухин показал, что если для ветвления всегда выбирается элемент с максимальным весом, то это число будет и верхней оценкой числа шагов метода. Вариант МВГ, в котором при разбиении фиксируется значение переменной с максимальным весом из числа незафиксированных, будем называть мажоритарным. Таким образом для
сложности S мажоритарного алгоритма имеет место следующая верхняя оценка:
H-mi)"- (з7)
Возникает вопрос, является ли данное неравенство верхней оценкой сложности для любого варианта МВГ. Ответ на этот вопрос — отрицательный. В разделе 4.4 диссертационной работы показано, что в случае ветвления по дробной переменной сложность решения задачи о ранце может быть асимптотически в 1.5 — е раза выше, чем сложность решения примера, предложенного Ю.Ю. Финкельштейном. Для этого построено семейство задач Р(Т, т, к) о сумме подмножеств, где к — целое число, m — целое неотрицательное число, а Т = {ii,..., tn} £ R" - упорядоченный набор натуральных чисел длины п. Задача Р{Т, тп, к) имеет следующий вид:
m+n
У] WiXi —> max; ¿=i m+n
У] WiXi < ка + 1, ¿=1
Xi е {0,1},г = 1,...,п,
^ ^ [а, если 1 < г < 7?г;
где a£N,a>2,H)i= <
I in+m+i_i ■ а, если ш < г < т + п.
Заметим, что сложность решения задачи Р(Т, тп, к) не зависит от параметра а. Учитывая этот факт, мы обозначаем приведенную сложность решения такой задачи через V(T,m,k). В работе получена рекуррентная формула для V(T,m, к), с помощью которой установлено, что для любого Т = {¿1,..., tn} справедливо соотношение
maxfcgz V(T,m,k) ^ / 1 1 \
Л™--= 2 +
Из данного соотношения вытекает, что для рассмотренного варианта метода ветвей и границ существуют задачи Р(Т, тп, к), сложность решения которых превосходит асимптотически в | — е раза сложность решения задачи (36) с тем же числом переменных.
Трудоемкость решения задачи методом ветвей и границ существенно зависит от входных данных задачи. Поэтому важным представляется получение оценок сложности, зависящих от входных данных задачи. Такие оценки позволяют сделать определенные выводы о трудоемкости задачи, не решая ее.
В диссертационной работе доказывается справедливость следующих верхних оценок сложности.
Теорема 4.2 Сложность 5" решения задачи (35) методом ветвей и границ при любом порядке выбора подзадач для обработки и переменных для ветвления удовлетворяет следующему неравенству:
- 1, (38)
где величины s п t определяются соотношениями:
(39)
5 = min е N : > с|
t = min IkeN: wt > С L (40)
l i=n-k+1 J
Величины (39) и (40) определены п предположении, что веса упорядочены по убыванию wi>---> w„.
Более точные оценки удается получить для мажоритарного метода ветвей и границ.
Теорема 4.3 Сложность S решения задачи (35) мажоритарным методом ветвей и границ удовлетворяет следующим неравенствам:
S < 2С+1) - 1, если t < [n/2j + 1, 5 < 2 (([п^/+1) - ([n/'J+1)) + 1, если t > \n/2\ + 1,
(41)
где t задается формулой (40).
Таким образом, для мажоритарного алгоритма имеют место три верхних оценки (37), (38), (41). Несложно заметить, что оценка (41) всегда не хуже (37) и при £ < \_п/2\ не хуже оценки (38).
Также в работе представлено экспериментальное сравнение полученных оценок, показывающее, что оценка (41) превосходит оценки (37) и (38) по среднему значению, максимальной точности и в подавляющем
большинстве случаев была лучшей из всех оценок. В то же время, оценка (38) чаще, чем все остальные была точной.
Глава 5 посвящена вопросам вычислительной сложности параллельного варианта метода ветвей и границ. Рассматривается одна из распространенных параллельных реализаций метода ветвей и границ, применяемая для систем с ограниченными возможностями по взаимодействию между вычислительными узлами в процессе расчетов (грид-системы из персональных компьютеров, графические со-процессоры). Предположим, что имеется бесконечное число одинаковых процессоров. Выделим один процессор и назовем его управляющим. Остальные процессоры будем называть рабочими. На начальном этапе управляющий процессор выполняет заданное число итераций МВГ, в результате чего образуется некоторое количество подзадач, соответствующих концевым вершинам дерева ветвления. Затем полученные подзадачи рассылаются с управляющего процессора рабочим процессорам (по одной на процессор). Каждый рабочий процессор, получивший подзадачу, полностью решает ее. После завершения расчетов рабочие процессоры пересылают наилучшие найденные решения управляющему процессору, который, сопоставляя данные решения, находит оптимум. В дальнейшем будем именовать данный алгоритм фронтальным.
Определим теперь понятие сложности фронтального алгоритма. Обозначим число шагов метода ветвей и границ, выполненных на управляющем процессоре, через Ь\, а максимальную сложность решения любой из сгенерированных задач-кандидатов — через £2- Время решения задачи на рассматриваемой параллельной системе складывается из времени решения на управляющем процессоре, пропорционального Ь\, и максимального из времен решения разосланных подзадач на рабочих процессорах, пропорционального ¿2. Рассмотрим идеальную ситуацию, когда время коммуникаций пренебрежимо мало по сравнению со временем í одного шага метода ветвей и границ. Тогда общее время решения задачи на рассмотренной параллельной системе составит Ь ■ £, где Ь = + Ь^. Исходя из проведенных рассуждений, естественно положить сложность фронтального алгоритма равной введенной величине Ь.
В диссертации доказывается следующее утверждение, дающее нижнюю оценку сложности фронтального алгоритма при условии, что дерево ветвления не изменяется при переходе к параллельному варианту.
Утверждение 5.1 Сложность фронтального алгоритма Ь ограничена снизу величиной 2\/£ + 2—3, где Б — сложность последовательного алгоритма, а ускорение Бр подчиняется неравенству Бр < '
Полученная оценка сложности является общей и годится для любого варианта фронтального алгоритма. Фактическое значение сложности может колебаться в широких пределах в зависимости от исходных данных задачи. Поэтому более точная оценка возможна для конкретных задач и вариантов метода.
В диссертационной работе такие оценки получены для задачи о сумме подмножеств. При условии невырожденности (не существует набора предметов, сумма весов которых совпадает со значением вместимости С) дерево ветвлений для этой задачи не зависит от порядка выбора подзадач для обработки и, соответственно, не изменяется при распараллеливании. Рассматривается ярусный фронтальный алгоритм, при котором управляющий процессор выполняет ветвление в ширину: на очередном шаге для декомпозиции выбирается любая из вершин дерева ветвлений, находящаяся па минимальном расстоянии от корня дерева. Процесс ветвления на управляющем процессоре заканчивается, когда все не отсеянные подзадачи имеют заданную глубину е.
Вопрос минимальной вычислительной сложности фронтального алгоритма исследуется для задач следующего вида:
' п
ахг —> тах,
¿=1
при условиях
' п
йХ1 < ка + 1,
г=1
XI е {0,1},г = 1 ,...,гг,
где а — произвольное действительное число, большее 1.
Следующая теорема определяет асимптотическое поведение минимальной сложности фронтального алгоритма Ь*(п) и значения 5*(гг) при котором достигается минимум.
Теорема 5.1 При п/3 < к < 2п/3 справедливы соотношения:
2п/2
ьм х —,
5„(п) = п/2 - ^ 1о§2 п + 0(1).
Положим а = п/к, 1/3 < а < 1/2. В диссертации показано, что по порядку ускорение оптимального параллельного варианта по отношению
(42)
к последовательному составляет
где Р = 1/(аа(1 — а)1_а). При а е [1/3,1/2] выполняется неравенство 2 > /3 > у/2. Следовательно, при любом а ускорение растет с ростом размерности задачи. При этом максимум /3 = 2 достигается в единственной точке а = 1/2.
Количество процессоров р(п), задействованных в вычислениях, имеет следующую асимптотику р(п) х ^ 2П//2 • тг-1/4.
Рассмотрим выражение для параллельной эффективности
При /3 = 2 параллельная эффективность максимальная и по порядку является константой Е(п) = 0( 1). При любом другом значении а параллельная эффективность убывает с ростом п. Таким образом, эффективность использования вычислительного ресурса будет падать при росте размерности для любых а, отличных от 1/2.
Глава 6 посвящена разработке и реализации программного комплекса для решения задач оптимизации на однопроцессорных и многопроцессорных ЭВМ, который был использован для практической апробации подходов и методов, предложенных в диссертационной работе. Целью разработки программного комплекса являлось создание универсальной расширяемой программной инфраструктуры, обладающей следующими свойствами:
1. гибкая поддержка широкого спектра вариантов метода ветвей и границ;
2. высокая производительность на задачах оптимизации большой размерности;
3. модульность и расширяемость, позволяющая минимизировать усилия разработчика при добавлении новой функциональности;
4. переносимость на уровне исходного кода между различными последовательными и параллельными платформами.
Состояние автомата
ТЕКСТ
Проверка условия
Переход
Результат проверки условия У, N
Событие на входе
? ТЕКСТ
Управляющее воздействие ! ТЕКСТ на выходе
Рис. 3: Элементы формальпого описания стратегии решения задачи
Для достижения поставленных целей предложен подход, основанный на разделении вычислительной, коммуникационной и управляющей функциональности в программе. Такой подход позволяет независимым образом реализовывать и отлаживать соответствующие компоненты, а также, облегчать процесс расширения программного комплекса за счет повторного использования ранее разработанных компонент.
В разделе 6.2 описываются современные высокопроизводительные вычислительные системы. Рассматриваются классические параллельные архитектуры с общей и распределенной памятью. Также рассматривается кластерная архитектура, в которой эти виды параллелизма сочетаются.
Раздел 6.3 посвящен реализации метода ветвей и границ для систем с распределенной памятью. Выделены основные элементы метода: выбор множества для ветвления, выбор способа ветвления, выбор правила отсева (исключения из рассмотрения) подзадачи, выбор алгоритма формирования приближенных решений.
Выбор параметров оказывает существенное влияние на производительность метода ветвей и границ. В 1990-м году И.Х. Сигалом было предложено понятие стратегии решения задачи как способа управления перечисленными параметрами в процессе решения задачи с учетом ресурсов ЭВМ.
Процесс решения оптимизационной задачи комбинированным мето-
Рис. 4: Пример автомата, описывающего стратегию управления процессом оптимизации
дом ветвей и границ можно представить как взаимодействие модуля управления, реализующего стратегию решения, и вычислительного модуля, выполняющего шаги метода. Для наглядного и строгого описания логики управления процессом решения в диссертационной работе было предложено использовать расширенный формализм конечных автоматов с двумя лентами. Основные элементы, входящие в формальное описание такого автомата, приведены на Рис. 3. Автомат выполняет переходы между состояниями, реагируя на события, приходящие от вычислительного модуля и генерирует управляющие воздействия (команды), которые воспринимаются и выполняются вычислительным модулем.
На Рис. 4 приведен пример автомата, описывающего стратегию управления методом ветвей и границ. Способ выбора очередного множества для ветвления меняется в динамике. Если число подзадач в списке превосходит заданную верхнюю границу и, то выдается команда ЗЕТ_БРЗ, переключающая вычислительный модуль на стратегию ветвления в глубину. Если число подзадач в списке становится меньше установленной нижней границы Ь, то происходит переключение на стратегию ветвления в ширину с помощью команды ЗЕТ_\УЕЗ.
В случае реализации для многопроцессорных ЭВМ к действиям, выполняемым в последовательном случае, добавляются обмены данными между процессами параллельного приложения. К событиям, подающимся на вход автомата, добавляются события, связанные с получением
процессом рекорда, подзадач или некоторой управляющей информации. Множество выдаваемых автоматом команд расширяется командами посылки перечисленных данных. Таким образом описывается процесс управления не только решением задачи, но и балансировкой загрузки многопроцессорной системы.
Отметим, что помимо улучшения структуры программного комплекса выделение управления процессом вычислений в отдельный модуль открывает дополнительные возможности для исследования эффективности методов балансировки нагрузки на эмуляторах параллельной системы. Наличие формального описания позволяет проводить верификацию алгоритмов управления процессом решения оптимизационной задачи на параллельной системе, выясняя потенциальные проблемы с корректностью работы алгоритмов балансировки нагрузки.
Далее в работе рассматривается программный комплекс ЕШВ-8о1усг, который является платформой для реализации предложенных в диссертационной работе методов и подходов. Этот программный комплекс представляет собой расширяемую библиотеку классов Си++. Основная идея организации программного комплекса состоит в выделении универсальных компонентов, которые могут быть использованы с различными вариантами метода ветвей и границ. Практически любая программа, реализующая метод ветвей и границ имеет типовую схему, представленную на Рис. 5. Интегрирующий модуль обеспечивает взаимодействие управляющего модуля, реализующего стратегию решения задачи с вычислительным модулем, выполняющим шаги метода ветвей и границ, и коммуникационного модуля, ответственного за обмен данными с другим процессом. В последовательном варианте коммуникационный модуль не требуется, так как нет взаимодействия процессов.
Каждый из модулей, представленных на Рис. 5, имеет фиксированный документированный интерфейс, который допускает различные реализации. В библиотеке имеются различные реализации этих модулей. Приложение, решающее задачу методом ветвей и границ, получается с помощью объединения нужных реализаций. Такой подход позволяет сократить усилия, необходимые для реализации новой задачи или нового модуля управления, за счет повторного использование ранее реализованных компонентов.
На данный момент реализованы вычислительные модули для методов ветвей и границ для задачи о булевом ранце с одним и несколькими ограничениями, задачи коммивояжера, различные варианты метода неравномерных покрытий для задач математического программирова-
Последовательный Параллельный
вариант вариант
Рис. 5: Компонентная схема типовой реализации метода ветвей и границ
ния и задач многокритериальной оптимизации с простыми и функциональными ограничениями. Реализован коммуникационный модуль для систем с распределенной памятью на основе библиотеки MPI.
В пункте 6.4 подробно рассматривается реализация метода ветвей и границ для задачи о булевом ранце с одним ограничением. Применяется комбинирование двух способов ветвления: но наибольшей оценке и одностороннего. Одностороннее ветвление более эффективно с точки зрения экономии памяти и организации вычислений. В диссертации предлагается модификация одностороннего алгоритма Горовица-Сахни на базе булева вектора для применения на параллельной вычислительной системе, достигаемая комбинированием с ветвлением по наилучшей оценке, организованном на базе списка подзадач. С помощью экспериментов показывается, что применение такого подхода позволяет эффективно распараллелить алгоритм Горовица-Сахни, сохранив при этом присущую ему высокую скорость выполнения операций ветвления.
Пункт 6.5 посвящен программному комплексу BNB-Grid, ориентированному на решение задач оптимизации в распределенной среде. В настоящее время в распоряжении отдельных исследователей и научных коллективов, как правило, имеются ресурсы следующих типов: рабочие станции, небольшие многопроцессорные комплексы, доступные в монопольном режиме, суперкомпьютеры коллективного доступа. Программный комплекс BNB-Grid предназначен для решения задач оптимизации на распределенных системах, состоящих из узлов перечисленного типа.
( ^ уМапэоег
А—СЕ-ч
умападт Я2;
_^
г-501—^
у Мапад&г у
(магая&р) ф—ф Смападег#Г) ^ V
ТСРЛР
Рис. 6: Организация вычислений в ВТчВ-Опё
ВИВ-Спс! запускает и организует взаимодействие параллельных приложений, решающих задачу с помощью библиотеки ВКВ-Эо1уег на различных вычислительных узлах. В результате формируется иерархическая распределенная система: на верхнем уровне части работы распределяются между параллельными приложениями, а далее они распределяются по процессорам средствами библиотеки BNB-Solver.
В диссертации приводится детальное описание архитектуры программного комплекса и рассматривается его применение для решения задач поиска энергетически-оптимальных конформаций химических соединений, а также, криптоанализа потоковых шифров.
В Заключении диссертационной работы сформулированы основные результаты и выводы.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
По теме диссертации соискателем опубликовано более 90 печатных работ, включая статьи в журналах, сборниках трудов и тезисов докладов конференций. Из них 25 в журналах из списка ВАК.
Публикации в изданиях из перечня ВАК РФ российских ре-
цензируемых научных журналов
1. М.А. Посыпкип, И.Х. Сигал, Исследование алгоритмов параллельных вычислений в задачах дискретной оптимизации ранцевого типа. // ЖВМ и МФ, 45(10), С. 1801-1809, 2005.
2. М.А. Посыпкип, И.Х. Сигал, Оценки ускорения для некоторых вариантов параллельной реализации метода ветвей и границ// ЖВМ и МФ, 46(12), С. 2289-2304, 2006.
3. М.А.Посынкин, Архитектура и программная организация библиотеки для решения задач дискретной оптимизации методом ветвей и границ на многопроцессорных вычислительных комплексах// Труды ИСА РАН, Т. 25, С. 18-25, 2005.
4. И.Х. Сигал, Я.Л. Бабинская, М.А.Посыпкин, Параллельная реализация метода ветвей и границ в задаче коммивояжера на базе библиотеки BNB-Solver// Труды ИСА РАН, Т. 25, С. 26-36.
5. А.П. Афанасьев, В.В. Волошинов, М.А. Посыпкип, И.Х. Сигал, Д.А. Хуторной, Программный комплекс для решения задач оптимизации методом ветвей и границ на распределенных вычислительных системах// Труды ИСА РАН, Т. 25, С. 5-17.
6. М.А. Посыпкип, A.C. Хританков, О понятии производительности в распределенных вычислительных системах// Труды ИСА РАН, Т. 32, 2008 г., С. 26-32.
7. P.M. Колпаков, М.А. Посыпкин, Асимптотическая оценка сложности метода ветвей и границ с ветвлением по дробной переменной для задачи о ранце// Труды ИСА РАН, Т. 32, 2008 г., С. 109-136.
8. P.M. Колпаков, М.А. Посыпкин, Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце// Труды ИСА РАН, Т. 32, 2008 г., С. 137-158.
9. М.А. Посыпкин, Параллельный эвристический алгоритм глобальной оптимизации // Труды ИСА РАН, Т. 32, 2008 г., С. 166-179.
10. М.А. Посыпкин, И.Х. Сигал, Комбинированный параллельный алгоритм решения задачи о ранце, Известия РАН, Теория и системы управления, №4, 2008 , С. 50-58.
11. М.А. Посыпкин, Мультиплатформенный программный комплекс для решения задач оптимизации в распределенной вычислительной среде. // Проблемы вычислений в распределенной среде / Под ред. C.B. Емельянова, А.П. Афанасьева. Труды ИСА РАН, Т. 46. - М.: КРАСАНД, 2009. С. 24-43.
12. А.Л. Игнатьев, М.А. Посыпкин, И.Х. Сигал, Решение задачи коммивояжера на многопроцессорных системах с общей и распределенной
памятью // Проблемы вычислений в распределенной среде / Под ред. C.B. Емельянова, А.П. Афанасьева. Труды ИСА РАН, Т. 46. - M.: КРА-САНД, 2009. С. 111-119
13. М.А. Посыпкин, О.С. Заикин, Д.В. Беспалов, A.A. Семенов, Решение задач криптоанализа поточных шифров в распределенных вычислительных средах // Проблемы вычислений в распределенной среде / Под ред. C.B. Емельянова, А.П. Афанасьева. Труды ИСА РАН, Т. 46. - М.: КРАСАНД, 2009. С. 119-138
14. А.П. Афанасьев, В.Д. Лахно, М.А. Посыпкин, В.Б. Султанов, Стационарные состояния в нелинейной модели переноса заряда в ДНК // Проблемы вычислений в распределенной среде / Под ред. C.B. Емельянова. А.П. Афанасьева. Труды ИСА РАН, Т. 46. - М.: КРАСАНД, 2009. С. 147-153
15. P.M. Колпаков, М.А. Посыпкин, О масштабируемости и эффективности одного метода решения задачи о рапце в распределенной вычислительной среде // Проблемы вычислений в распределенной среде / Под ред. C.B. Емельянова, А.П. Афанасьева. Труды ИСА РАН, Т. 46. -М.: КРАСАНД, 2009. С. 164-174
16. М.А. Посыпкин, Решение задач глобальной оптимизации в среде распределенных вычислений // Программные продукты и системы. №1.
2010. С. 23-29.
17. М.А. Посыпкин, Методы и распределенная программная инфраструктура для численного решения задачи поиска молекулярных кластеров с минимальной энергией //Вестник нижегородского университета им. Н.И. Лобачевского №1. 2010. С. 210-219.
18. P.M. Колпаков, М.А. Посыпкин, Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце // Дискретная математика, Т. 22, вып. 1, 2010, С. 58-73
19. P.M. Колпаков, М.А. Посыпкин, И.Х. Сигал, О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ // Автоматика и телемеханика. 2010. №10. С. 156-166.
20. Ю. Г. Евтушенко, М. А. Посыпкин, Применение метода неравномерных покрытий для глобальной оптимизации частично целочисленных нелинейных задач. // ЖВМиМФ, 2011, том 51, №8, С. 1376-1389.
21. Р. М. Колпаков, М. А. Посыпкин, Об оценках вычислительной сложности варианта параллельной реализации метода ветвей и границ для задачи о ранце // Известия РАН: Теория и системы управления. №5,
2011, С. 74-83.
22. Ю.Г. Евтушенко, М.А. Посыпкин, Варианты метода неравномер-
ных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач. // Доклады Академии Наук, 2011, том 437, №2, С 168-172.
23. Ю.Г. Евтушенко, М.А. Посыпкин, Метод неравномерных покрытий для решения задач многокритериальной оптимизации с гарантированной точностью. // ЖВМиМФ, 2013, том 53, №2, С. 209-224.
24. М.А. Посыпкин, Метод решения задач условной многокритериальной оптимизации с гарантированной точностью // Доклады академии наук, 2013, том 452, №4, с. 375-378.
25. Ю.Г. Евтушенко, М.А. Посыпкин, Метод неравномерных покрытий для решения задач многокритериальной оптимизации с заданной точностью. // Автоматика и телемеханика, 2014, №6, С. 49-68.
Статьи в реферируемых международных изданиях:
26. Y. Evtushenko, М. Posypkin, I. Sigal, A framework for parallel large-scale global optimization // Computer Science - Research and Development 23(3), pp. 211-215, 2009.
27. Y. Evtushenko, M. Posypkin. A Deterministic Algorithm for Global Optimization // Lecture Notes in Economics and Mathematical Systems Vol. 658, ISBN 978-3-642-22883-4, P. 205-218, 2012.
28. Y. Evtushenko, M. Posypkin. A deterministic approach to global box-constrained optimization // Optimization Letters, 2013, Volume 7, Issue 4 pp 819-829.
29. A. Afanasiev, Yu. Evtushenko, M. Posypkin. The Layered Software Infrastructure for Solving Large-scale Optimization Problems on the Grid,Horizons in Computer Science Research, Vol. 4, pp. 129-145, Nova Science Publishers Inc, 2012.
30. Yu.G. Evtushenko. M.A. Posypkin. A deterministic algorithm for global multiobjective optimization // Optimization Methods and Software, Vol. 29 Iss. 5, pp. 1005-1009, 2014.
£ Q
Посыпкин Михаил Анатольевич
Методы глобальной и многокритериальной оптимизации на базе концепций ветвей и границ и неравномерных покрытий
Подписано в печать 02.10.2014
Формат бумаги 60x84 1/16 Уч.-изд. л. 1,7. Усл.-печл. 2,5 Тираж 100 экз. Заказ 21
Отпечатано на ротапринтах в Федеральном государственном бюджетном учреждении науки Вычислительный центр им. A.A. Дородницына Российской академии наук 119333, Москва, ул. Вавилова, 40
