Введение к работе
Актуальность темы диссертационной работы.
В подавляющем большинстве научно-технических задач возникает проблема выбора рационального варианта из множества возможных. К числу наиболее часто встречающихся моделей рационального выбора можно отнести математические задачи оптимизации некоторого функционала в некоторой заданной области. Однако в приложениях на параметры исследуемого объекта обычно накладываются дополнительные функциональные ограничения, а сам оптимальный выбор зависит от
т~ч и и
нескольких критериев. В данной ситуации выполнение ограничений для фиксированного вектора параметров, задающего решение, означает допустимость этого решения, т.е. возможность его реализации на практике при имеющихся ресурсах. Как результат, в зависимости от существа решаемой задачи рационального выбора могут применяться различные модели, использующие разные априорные предположения о виде функционалов, разные схемы выполнения расчета их значений, разные способы выбора решения в многокритериальном случае и т.д.
Одной из активно исследуемых задач оптимизации являются задачи глобальной или многоэкстремальной оптимизации. В задачах такого вида допускается, что оптимизируемый критерий имеет несколько локальных оптимумов в области поиска, которые имеют различные значения. Наличие нескольких локальных оптимумов существенно усложняет поиск глобального оптимума, так как требует исследования всей допустимой области.
К примерам задач оптимизации, возникающих в приложениях, можно отнести задачу уменьшения уровня температурной неравномерности на поверхности лопатки турбины или задачу идентификации параметров моделей региональной экономики, отражающих степень близости расчётных и реальных данных и др.
Особенностью таких задач является наличие большого количества варьируемых параметров, многоэкстремальность оптимизируемых функционалов, наличие нелинейных ограничений, многокритериальность, и, самое главное, - высокая вычислительная сложность функционалов, лежащих в основе оптимизируемых критериев и ограничений. Расчет одного варианта модели может занимать существенно длительные промежутки времени, что с использованием одного современного однопроцессорного компьютера для решения таких задач на практике приводит к значительным временным затратам.
Как результат, можно говорить о том, что решение таких задач при реалистических временных затратах может осуществляться только при использовании высокого вычислительного потенциала современных суперкомпьютерных систем.
Ввиду сложности архитектуры современных многопроцессорных систем, классические последовательные математические алгоритмы и численные методы не
могут эффективно использовать их вычислительный потенциал, так как основаны на строго последовательном порядке вычислений. Таким образом, возникает проблема разработки эффективных алгоритмов не только для реализации собственно параллельных вычислений, но и управления ими.
Результаты современных российских и советских научных исследований в области моделей и методов глобальной оптимизации имеют широкое признание.
Отметим работы Батищева Д.И., Васильева Ф.П., Гергеля В.П.,
Гришагина В.А., Евтушенко Ю.Г., Жилинскаса А.Г., Карманова В.Г., Коротченко А.Г , Неймарка Ю.И., Пиявского С.А., Сергеева Я.Д., Стронгина Р.Г., Сухарева А.Г. и др. Среди зарубежных ученых можно выделить Brent R., Pardalos P, Pinter J., Tuy H., Hansen E., Horst, R. и др.
Данная работа выполняется в рамках информационно-статистической теории глобального поиска. Алгоритмы, развиваемые в рамках указанного подхода, основаны на предположении липшицевости всех функционалов задачи. В рамках информационно-статистической теории была разработана индексная схема учета ограничений (индексный метод). При этом допускается, что некоторые функционалы задачи определены не во всей области поиска (частичная вычислимость).
В обсуждаемом подходе есть еще одно важное принципиальное отличие: решение многомерных задач сводится к решению эквивалентных им одномерных задач (редукция размерности). Соответствующая редукция может быть основана на использовании разверток единичного отрезка вещественной оси на гиперкуб. Роль таких разверток играют непрерывные однозначные отображения типа кривой Пеано, называемые также кривыми, заполняющими пространство, и их обобщения, названные "множественными развертками". Эффективное использование аппарата таких отображений послужило основой для разработки перспективных параллельных численных методов глобальной оптимизации.
Предметом исследования являются модели и алгоритмы управления параллельным решением вычислительно трудоемких задач глобального поиска на высокопроизводительных вычислительных системах.
Целью работы является разработка, исследование и реализация эффективных алгоритмов управления параллельным решением задач глобального поиска, основанных на новой модели построения набора информационно-связанных задач. Разработанная модель позволяет каждой из задач семейства взаимно пополнять и взаимно использовать поисковую информацию, полученную при решении другой задачи, повышая эффективность поиска. В работе предлагается новая двухуровневая схема управления параллельными вычислениями для глобальной оптимизации, учитывающая иерархическую структуру современных кластерных систем. В диссертационной работе предлагается новая схема построения множественных отображений на основе вращаемых разверток и рассматриваются алгоритмы глобального поиска, использующие данную схему, что позволяет без введения дополнительных искусственных ограничений применять сотни и тысячи вычислительных узлов для решения исходной задачи глобального поиска.
Методы исследования. Работа базируется на информационно-статистической теории глобального поиска, аппарате теории оптимизации, методах анализа алгоритмов, методах вычислительной математики, методах параллельных вычислений.
Научная новизна. При выполнении работы получены следующие основные новые результаты, выносимые на защиту:
Сформулирована модель процесса параллельного глобального поиска и общая схема сведения сложных проблем оптимального выбора к серии информационно-связанных задач глобального поиска, решение которых может осуществляться параллельно;
Предложен двухуровневый алгоритм управления параллельными вычислениями для глобальной оптимизации, позволяющий на уровне отдельных вычислительных узлов с общей разделяемой памятью исключить передачу данных, а на уровне всей вычислительной системы обеспечивающий асинхронное выполнение параллельных вычислений и балансировку вычислительной нагрузки;
Предложена новая схема порождения множественных отображений для многомерных многоэкстремальных задач глобальной оптимизации на основе вращаемых разверток типа кривой Пеано, позволяющая задействовать при организации параллельных вычислений высокий вычислительный потенциал (сотни и тысячи процессоров) современных суперкомпьютерных систем;
Разработаны модифицированные информационно-статистические алгоритмы глобального поиска, использующие новую схему порождения множественных отображений.
Практическая ценность работы составляет:
Методика организации и управления параллельными вычислениями для разработанной схемы редукции размерности на основе вращаемых разверток может быть использована для решения других многомерных научно-технических задач из разных областей приложений.
Разработанная программная система GlobalExpert+ может использоваться для параллельного решения сложных вычислительно-трудоемких задач многомерной многоэкстремальной оптимизации. Система применена на практике и внедрена в учебный процесс.
Достоверность научных результатов и выводов подтверждается строгостью постановки задач исследования, обоснованностью применения и корректной реализацией используемого математического аппарата, результатами вычислительных экспериментов и тестирования алгоритмов и программного обеспечения, научной экспертизой на научных конференциях и при публикации в научной печати.
Внедрение результатов работы. Результаты работы нашли свое применение при выполнении проектов, выполняемых на факультете вычислительной математики и кибернетики ННГУ им. Н.И. Лобачевского при поддержке Российского фонда фундаментальных исследований (грант № 11-07-97017-р_поволжье_а), Совета по грантам Президента Российской Федерации (гранты № МК-1536.2009.9, НШ- 64729.2010.9, НШ-1960.2012.9), ФЦП «Научные и научно-педагогические кадры инновационной России» (госконтракт № 02.740.11.5018), ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007 - 2013 годы» (госконтракт № 11.519.11.4015). Результаты работы используются также в учебном процессе факультета вычислительной математики и кибернетики ННГУ им. Н.И. Лобачевского при чтении курсов «Модели и методы многоэкстремальной оптимизации», «Системы поддержки принятия решений».
Апробация работы. Результаты работы докладывались на международных конференциях «Высокопроизводительные вычисления на кластерных системах» (Нижний Новгород 2005, Санкт Петербург 2006, Нижний Новгород 2007, Казань 2008, Владимир 2009, Пермь 2010, Нижний Новгород 2011), «Параллельные вычислительные технологии» (Уфа 2010), Всероссийской конференции «Научный сервис в сети Интернет» (Новороссийск, 2008, 2010, 2012), научно-технических конференциях «Технологии Майкрософт в теории и практике программирования» (Нижний Новгород, 2006-2008), Всероссийской научно-технической конференции «Аэрокосмическая техника, высокие технологии и инновации», (Пермь, 2008, 2009), на научных конференциях и семинарах ННГУ им. Н.И. Лобачевского.
Публикации. Основное содержание диссертации изложено в работах [ 1]—[26] из них пять представлено в Перечне рецензируемых научных журналов [1]-[5].
Личный вклад соискателя. Постановка задач и методика исследования принадлежат руководителю. Соискателю принадлежит разработка модели процесса параллельного глобального поиска и новой схемы сведения сложных проблем оптимального выбора к серии информационно-связанных задач глобального поиска, двухуровневый алгоритм управления параллельными вычислениями, новой схемы множественной развертки, выполнение вычислительных экспериментов, обработка и интерпретация результатов.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы из 184 наименований. Основной печатный текст занимает 101 страницы.
