Содержание к диссертации
Введение
1. Модели и методы многомерной многоэкстремальной оптимизации 12
1.1. Постановка задачи многомерной многоэкстремальной оптимизации 12
1.2. Краткий обзор подходов к численному решению задач многомерной многоэкстремальной оптимизации 14
1.3. Информационно-статистические алгоритмы глобального поиска 21
2. Методы многоэкстремальной оптимизации с адаптивными решающими правилами 29
2.1. Методы многоэкстремальной оптимизации с использованием производных 30
2.2. Методы многоэкстремальной оптимизации с адаптивными оценками константами Липшица 38
2.2.1. Локальная настройка оценок константы Липшица 38
2.2.2. Локальная настройка с аддитивной сверткой оценок константы Липшица 42
2.2.3. Локальная настройка с интервальной схемой построения оценок константы Липшица 47
2.2.4. Локальная настройка с выделением подобластей с близкими значениями константы Липшица 48
3. Многомерная многоэкстремальная оптимизации на основе многошаговой редукции размерности 50
3.1. Многошаговая схема редукции размерности 50
3.2. Адаптивная многошаговая схема редукции размерности 53
3.2.1. Общее описание подхода 54
3.2.2. Алгоритмическое описание 56
3.3. Многомерные характеристически-представимые алгоритмы глобального поиска на основе адаптивной многошаговой схемы редукции размерности .62
3.4. Информационно-статистические алгоритмы глобального поиска в рамках адаптивной многошаговой схемы редукции размерности 67
3.5. Вычислительные эксперименты для оценки эффективности адаптивной многошаговой схемы редукции размерности 73
3.6. Операционные характеристики алгоритмов глобального поиска 74
4. Адаптивные параллельные вычисления для многомерной многоэкстремальной оптимизации 78
4.1. Централизованная схема параллельного глобального поиска 81
4.2. Централизованная схема параллельного глобального поиска для адаптивной многошаговой схемы редукции размерности 87
4.3. Распределенная схема параллельного глобального поиска для адаптивной многошаговой схемы редукции размерности 91
4.3.1. Общая схема распределенных вычислений 91
4.3.2. Структурная схема распределенных вычислений 92
4.3.3. Балансировка вычислительной нагрузки в структурной схеме распределенных вычислений 95
5. Программные средства параллельной глобальной оптимизации 105
5.1. Общая характеристика комплекса глобальной оптимизации GloptiCom 108
5.2. Система одномерной многоэкстремальной оптимизации GloptiCom-1.110
5.3. Система двухмерной многоэкстремальной оптимизации GloptiCom-2 .113
5.4. Система многомерной многоэкстремальной оптимизации GloptiCom+ 115
Заключение 119
Литература
- Краткий обзор подходов к численному решению задач многомерной многоэкстремальной оптимизации
- Локальная настройка с аддитивной сверткой оценок константы Липшица
- Многомерные характеристически-представимые алгоритмы глобального поиска на основе адаптивной многошаговой схемы редукции размерности
- Распределенная схема параллельного глобального поиска для адаптивной многошаговой схемы редукции размерности
Введение к работе
Актуальность темы диссертационной работы. Проблема рационального выбора вариантов является присущей практически любой научно-технической задаче. Разнообразие проблем выбора является чрезвычайно большим и, как следствие, для их формального описания разработан целый спектр математических постановок задач оптимизации — это задачи локальной оптимизации, линейного программирования, дискретной оптимизации и многие другие. К числу наиболее общих и сложных постановок проблемы выбора относятся задачи глобшьной или многоэкстремальной оптимизации, в которых допускается, что оптимизируемые критерии качества проблемы выбора могут иметь несколько локальных, отличающихся между собой решений. Данное предположение существенно повышает сложность решения оптимизационной задачи, ибо, если для подтверждения локального минимума достаточно исследования локальной окрестности, то глобальный минимум является интегральной характеристикой решаемой оптимизационной задачи и требует исследования всей области глобального поиска. Как результат, задачи глобальной оптимизации являются проблемами значительной вычислительной трудоемкости и их решение при каком-либо значительном количестве варьируемых параметров становится возможным только при самом активном использовании высокопроизводительных вычислительных систем.
Проблематика моделей, методов и программных средств решения задач оптимизации является областью активных научных исследований, в которой результаты советских и российских ученых имеют широкое признание в стране и за рубежом. Можно выделить работы Д.И. Бати-щева, Ф.П. Васильева, В.П. Гергеля, В.А. Гришагина, Ю.Г Евтушенко, А.Г Жилинскаса, В.Г Карманова, А.Г Коротченко, Ю.И. Неймарка, С.А. Пиявского, Я. Д. Сергеева, Р.Г Стронгина, Ю.А. Флерова и др. Среди зарубежных ученых можно указать Р. Брента, П. Пардалоса, Я. Пинтера, X. Туя, П. Хансена, Р Хорста и др.
Важнейшим полученным результатом в теории многоэкстремальной оптимизации является обоснование того факта, что, в общем случае, поиск глобального оптимума оптимизируемой функции сводится к построению некоторого покрытия (сетки) в области глобального поиска. При этом данные покрытия должны быть существенно неравномерными для обеспечения эффективности вычислений — эти сетки должны быть достаточно плотными в окрестности глобального оптимума и более раз-
реженными вдали от искомого решения. Построение таких оптимальных покрытий обеспечивается при повышении сложности самих численных методов глобального поиска.
В связи с этим активно развиваемым направлением в теории и практике многоэкстремальной оптимизации является использование тех или иных схем редукции размерности, которые позволяют свести решение многомерных оптимизационных задач к семейству задач одномерной оптимизации. Редукция размерности позволяет существенно снизить сложность разрабатываемых алгоритмов глобального поиска. Кроме того, данный подход позволяет задействовать весь имеющийся аппарат одномерной многоэкстремальной оптимизации для построения эффективных многомерных методов глобального поиска.
Один из наиболее общих методов редукции размерности состоит в применении многошаговой схемы редукции размерности, согласно которой решение многомерной задачи оптимизации может быть получено посредством решения последовательности «вложенных» одномерных задач. Данная схема уже послужила основой для разработки многих эффективных алгоритмов оптимизации и является перспективным направлением научных исследований для создания новых методов по численному решению существенно многомерных задач глобального поиска на высокопроизводительных вычислительных системах.
Предметом исследования являются математические модели, численные методы, параллельные алгоритмы и программные комплексы для решения сложных вычислительно-трудоемких задач глобального поиска на высокопроизводительных вычислительных системах.
Цель работы. Целью работы является разработка, исследование и реализация на высокопроизводительных вычислительных системах новой адаптивной многошаговой схемы редукции размерности для решения вычислительно-трудоемких многомерных задач многоэкстремальной оптимизации. Основное предложение разработанной в работе адаптивной многошаговой схемы состоит в совместном решении всех порождаемых в ходе редукции размерности одномерных оптимизационных задач, что позволяет существенно сократить объем вычислений в подобластях области поиска, далеких от расположения искомого глобального оптимума. В рамках работы проводится теоретическое обоснование предложенной адаптивной многошаговой схемы, рассматриваются алгоритмы глобального поиска в рамках данной схемы, исследуются вопросы параллельной реализации сформулированного алгоритмического подхода на многопроцессорных вычислительных системах. Ко-
нечным результатом работы является разработанная программная система GloptiCom для параллельного решения сложных вычислительно-трудоемких задач глобального поиска.
Методы исследования включают аппарат теории оптимизации, информационно-статистической теории глобального поиска, методы анализа алгоритмов, методы вычислительной математики, методы параллельных вычислений.
Научная новизна. При выполнении работы получены следующие основные новые результаты:
Предложена новая адаптивная многошаговая схема редукции размерности для решения многомерных многоэкстремальных задач оптимизации, основанная на совместном решении всех порождаемых в ходе редукции одномерных оптимизационных задач.
Разработан способ характеристической представимости предложенной адаптивной многошаговой схемы, что позволяет в рамках данной схемы рассматривать все множество характеристически-представимых алгоритмов глобального поиска.
Проведено теоретическое обоснование предложенной адаптивной многошаговой схемы: показано выполнение свойства устойчивости разработанных вычислительных схем, а также выполнимость условия Липшица для всех порождаемых одномерных оптимизационных задач.
Получены достаточные условия сходимости разработанных вычислительных схем при совместном использовании с информационно-статистическими алгоритмами глобального поиска.
Предложены схемы параллельных вычислений для разработанной адаптивной многошаговой схемы, включающие способы распределения и динамической балансировки вычислительной нагрузки между вычислительными устройствами.
Практическую ценность работы составляют:
Методика организации параллельных вычислений для разработанной адаптивной многошаговой схемы и ее применение для всего множества характеристически-представимых алгоритмов глобального поиска.
Методы распределения и динамической балансировки вычислительной нагрузки между вычислительными устройствами высокопроизводительных вычислительных систем.
Программная система GloptiCom для параллельного решения сложных вычислительно-трудоемких задач многомерной многоэкстремальной оптимизации.
Достоверность научных результатов и выводов подтверждается строгостью постановки задач исследования, обоснованностью применения математического аппарата, результатами тестирования алгоритмов и программного обеспечения, научной экспертизой на научных конференциях и при публикации в научной печати.
Внедрение результатов работы. Результаты работы нашли свое применение при выполнении проектов, выполняемых на факультете ВМК при поддержке Российского фонда фундаментальных исследований (проекты № 04-01-00455, № 07-01-00467-а) и Совета по грантам Президента Российской Федерации по государственной поддержке ведущих научных школ РФ (грант № НШ - 4694.2008.9), совместного научно-исследовательского проекта РФФИ и Нидерландской организации по научным исследованиям NWO 047.016.014. Результаты работы используются также в учебном процессе факультета ВМК ННГУ при чтении курсов "Модели и методы многоэкстремальной оптимизации", "Системы поддержки принятия решений"
Апробация работы. Результаты работы докладывались на Международных конференциях "Высокопроизводительные вычисления на кластерных системах" (Нижний Новгород, 2007, Казань, 2008, Владимир, 2009), Всероссийской конференции "Научный сервис в сети Интернет" (Новороссийск, 2009), научно-технических конференциях "Технологии Майкрософт в теории и практике программирования" (Нижний Новгород, 2007-2008, 2010), на научных конференциях и семинарах Нижегородского государственного университета.
Публикации. Основное содержание диссертации изложено в рабо-тах [1]-[9].
Личный вклад соискателя. Постановка задач и методика исследования принадлежат руководителю. Соискателю принадлежит разработка адаптивной многошаговой схемы редукции размерности, теоретическое обоснование подхода, разработка программного обеспечения, выполнение вычислительных экспериментов, обработка и интерпретация результатов.
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы из 198 наименований. Основной печатный текст занимает 138 страницы.
Краткий обзор подходов к численному решению задач многомерной многоэкстремальной оптимизации
Важно отметить, что в задачах многоэкстремальной оптимизации глобальный экстремум является интегральной характеристикой задачи, и его определение, вообще говоря, связано с построением покрытия области поиска точками вычислений функции. Поэтому на сложность решения задач рассматриваемого класса решающее влияние оказывает размерность: они подвержены "проклятию размерности", состоящему в экспоненциальном росте вычислительных затрат при увеличении размерности. Использование простейших способов решения (таких, как перебор по равномерной сетке) является чрезмерно затратным - так, для построения равномерной сетки с шагом є для задачи размерности iV требует вычислений значений оптимизируемой функции, что становится практически нереализуемым уже при сравнительно небольшом количестве варьируемых параметров. Получение решений сложных многомерных многоэкстремальных задач оптимизации при реалистических вычислительных затратах может быть обеспечено при помощи более экономных методов, которые порождают в области поиска существенно неравномерную сетку, более плотную в окрестности решения задачи. Создание таких методов становится возможным только при соблюдении следующих важных принципов численного решения задач многоэкстремальной оптимизации.
Прежде всего, в задачах многоэкстремальной оптимизации возможность достоверной оценки глобального оптимума принципиально основана на наличии априорной информации о функции, позволяющей связать возможные значения минимизируемой функции с известными значениями в точках осуществленных поисковых итераций. Наиболее широко используемая форма задания такой априорной информации о задаче (1.1) представляется в виде предположения, что целевая функция ср (в дальнейшем обозначаемая также gm+\) и левые части ограничений gj(y),\ j m, удовлетворяют условию Липшица с соответствующими константами Lj, 1 j m+1, а именно
Второй важный момент при решении многоэкстремальных задач состоит в том, что для эффективного использования информации, получаемой в процессе вычислений, генерацию узлов неравномерной сетки следует осуществлять последовательно с учетом всей поисковой информации, полученной в процессе вычислений точки испытаний, z, l i k, представляют значения целевой функции в точках/, a (gi ,..., gml), 1 &, обозначают значения ограничений в этих точках. Данный момент определяет необходимость запоминания поисковой информации достаточно большого объема и организации ее эффективной обработки.
После подобного общего вступления дадим краткий обзор существующих подходов к решению задач многомерной многоэкстремальной оптимизации. Разнообразие задач глобальной оптимизации влечет за собой разнообразие используемых подходов для их решения (см., например, [1-4, 27-28, 32-33, 35, 39-40, 42-43, 50, 57, 62, 65, 71, 79-80, 91-95, 104, 111-112, 120-121, 125, 138, 143, 153-155, 176, 180, 182, 185-186, 189-190, 195]). Стоит отметить, что некоторые методы позволяют эффективно решать задачи определенного класса, но в тоже время используемые подходы могут оказаться неприемлемыми для решения задач из более широкого класса. При этом методы, разработанные для решения задач из общего класса, могут оказаться неэффективным при решении конкретной задачи.
Прежде всего, можно выделить широко используемый подход, состоящий в обобщении методов локальной оптимизации на случай многоэкстремальных функций (см., например, [7, 11, 45, 51, 56]). При этом для получения глобального решения нужно либо иметь начальную точку из области притяжения точки у (т.е. из области, где у есть единственная локально-оптимальная точка), либо найти все локально-оптимальные точки у , 1 і s, для их последующего сравнения. Трудность, связанная с таким подходом, состоит в том, что ни область притяжения точки у , ни ЧИСЛО S локально-оптимальных точек обычно не известны. При таком подходе возникает дополнительная задача выбора начальных точек. Возможными вариантами выбора начальных точек является использование некоторой регулярной сетки или выбор точки при помощи тех или схем случайной генерации (методы Монте-Карло). Сетки строятся так, чтобы обеспечить уплотняющее покрытие всей области поиска, что обеспечивает сходимость к глобальному экстремуму. Недостатком использования данных подходов является ситуация в которой в зону притяжения одного и того же локального минимума попадают несколько начальных точек.
Отдельный класс методов составляют так называемые пассивные (неадаптивныё) алгоритмы, в которых точки вычисления целевой функции выбираются до начала поиска (см., например, [68]). Как отмечалось выше, такой подход требует значительного объема вычислений.
Значительно более обширный класс методов образуют последовательные {адаптивные) алгоритмы глобального поиска, в которых при проведении вычислений используется как априорная информация о задаче, так и получаемая в процессе расчетов поисковая информация. Среди таких методов можно выделить алгоритмы ветвей и границ, алгоритмы на основе интервальной арифметики, байесовские методы (см., например, [42-43, 65, 82, 135]), методы многократного локального спуска. Во многих случаях данные алгоритмы ориентированы на некоторые специальные классы задач типа дискретной или выпуклой оптимизации.
Отдельную группу методов составляют эвристические алгоритмы глобальной оптимизации, в основе которых лежит те или иные механизмы стохастического поиска. Среди таких алгоритмов — методы имитации отжига (simulated annealing methods), генетические алгоритмы и др. (см. например, [5, 41-42, 74, 86, 90, 97, 106, 111-112, 119, 127, 133, 136, 147, 158-160, 181, 191, 196, 197]).
Важный подход к решению многоэкстремальных задач - и именно в этом направлении будут выполнены исследования в данной работе — основывается на следующем. Как отмечалось ранее, построение оценок глобального решения предполагает построение тех или иных сеток, покрывающих область поиска. Получение таких сеток, содержащих минимально-возможное количество узлов, является значительной проблемой, и именно этот факт приводит к тому, что эффективные алгоритмы многоэкстремальной оптимизации являются достаточно сложными. Определенное преодоление этой проблемы может быть достигнуто при помощи очень интересной идеи -редукции размерности, т.е. различных способов сведения многомерных задач глобального поиска к задачам одномерной оптимизации
Локальная настройка с аддитивной сверткой оценок константы Липшица
В адаптивной многошаговой схеме все порождаемые задачи решаются совместно - выбор задачи для очередной итерации глобального поиска осуществляется в соответствии с тем или иным правилом выбора задач. Такой подход, с одной стороны, требует запоминания всей поисковой информации, получаемой в ходе вычислений, а с другой стороны, позволяет при необходимости увеличивать необходимую точность решения задач. Данная возможность способствует применению методики оптимизации с последовательно увеличивающейся точностью вычислений — так, начальная стадия оптимизации может быть выполнена с достаточно грубой точностью, что позволит получить оценки решения за сравнительно небольшое время вычислений, далее после анализа результатов точность может быть повышена и процесс глобального поиска может быть продолжен.
Наличие правила выбора задачи для выполнения очередной итерации глобального поиска позволяет строить разнообразные и гибкие процедуры оптимизации (в частности, исходная многошаговая схема редукции размерности может быть получена как частный случай нового подхода) — этот аспект обобщенной многошаговой схемы более подробно рассматривается в следующем параграфе данной главы.
Существование множества одновременно решаемых задач позволяет ставить вопрос об их параллельном решении и использовать, тем самым, для решения сложных оптимизационных задач весь потенциал современных высокопроизводительных многопроцессорных систем — данному направлению исследования посвящена глава 4 диссертации.
Вместе с этим, как уже отмечалось, новый подход требует запоминания все поисковой информации, получаемой в ходе вычислений (в отличие от исходной многошаговой схемы) - данный аспект проводит к необходимости разработки специальных методов для организации хранения и эффективной обработки накапливаемых поисковых данных. Еще один важный момент, отличающий предложенный подход от исходной многошаговой схемы, состоит в динамическом характере способа вычислений значений одномерных функций. Поясним более подробно данный аспект. Основой многошаговой схемы является принцип? в соответствии с которым вычисление значения любой одномерной функции Р,(У,) (кроме функций конечного уровня N) требует решения задачи минимизации соответствующей одномерной функции следующего уровня (см. (3.3)):
В новой обобщенной многошаговой схеме в качестве искомого значения функции РІІУІ) используется текущая оценка минимального значения функции І+ІСУЙ-І), определяемая на основе выполненных итераций глобального поиска. Используемые оценки могут уточняться в процессе вычислений, но, тем не менее, эти оценки могут существенно отличаться от значений, получаемых при решении задач (3.3). Более точно можно говорить, что при выполнении глобального поиска вычисления проводятся не с «точными» одномерными функциями ф у,), l i N, а с их. приближенными аппроксимациями цг,(у,), \ i N. Следует отметить, что определенная приближенность вычисления значений одномерных функций присуща и исходной многошаговой схеме редукции размерности (см. [65]).
Построение оценок минимальных значений одномерных функций РІ+І(УІ+\) зависит от способов конкретизации представленных выше правил адаптивной многошаговой схемы. Для сохранения свойства липшицевости исходной оптимизируемой функции р(у) потребуем соблюдения устойчивости для правил адаптивной многошаговой схемы, в соответствии с которой применяемые правила при близких значениях варьируемых параметров должны порождать близкие оценки минимальных значений, т.е. где yi+\(k,Vi) есть значение переменной yi+\, соответствующей текущей оценке значения функции фі(у,) на итерации к глобального поиска, а есть норма в области поиска D из (1.1), определяющая расстояние между векторами V,! и v". Соблюдение условий (3.9) обеспечивает выполнимость следующего утверждения. Теорема 3.2. Пусть функция (p(y),yeD, из (1.1) является липшицевой с константой К. Тогда «приближенные» функции y,(v,),l i N, построенные в соответствии с адаптивной многошаговой схемой при выполнении условия устойчивости (3.9), также являются липшицевыми с константами К(, где:
Доказательство. В соответствии с правилами построения y/N(vN)-(p(y) является липшицевой с константой К.
Применив индукцию по /, полученные соотношения показывают справедливость сформулированной теоремы.
Многомерные характеристически-представимые алгоритмы глобального поиска на основе адаптивной многошаговой схемы редукции размерности
Представленное в предшествующем параграфе описание адаптивной многошаговой схемы редукции размерности может служить алгоритмической основой для построения разнообразных алгоритмов многомерной многоэкстремальной оптимизации. Для получения определенного алгоритма оптимизации в рамках данного подхода необходимо конкретизировать следующие общие правила адаптивной многошаговой схемы:
Детализация перечисленных правил может быть получена в рамках класса характеристически-представимых алгоритмов глобального поиска — см. 1.2 Главы 1. При последующем описании правил алгоритмической схемы используем, как и ранее, понятие поисковой информации а к из (1.5) U A={(X ,Z ,/ ):1 / }, (ЗЛО) представляющей точки x ,\ i k, всех ранее выполненных итераций поиска, значения z ,l i k, минимизируемой функции в этих точках и номера задач Г,\ і к, порожденных для вычисления значений z ,\ i k. В рамках многошаговой схемы формирование поисковой информации целесообразно проводить отдельно для каждой решаемой задачи из семейства F[ из (3.8)-для указания принадлежности поисковой информации определенной задаче будем использовать номер этой задачи, т.е.
Важно отметить, что имеющиеся в поисковой информации значения z {j):\ i kj для функций уровня меньшего, чем N, могут изменяться, так как эти величины представляют собой оценки минимальных значений функций f,, а эти оценки могут уточняться в ходе проведения вычислений. С учетом введенных обозначений описание правил многомерных характеристически-представимых алгоритмов глобального поиска может быть выполнено следующим образом (см. Описание схемы характеристически-представимых алгоритмов в 1.2):
Многомерные характеристически-представимые алгоритмы глобального поиска на основе адаптивной многошаговой схемы редукции размерности
Получаемая схема организации параллельных вычислений при использовании характеристически представимых асинхронных параллельных алгоритмов многоэкстремальной оптимизации представлена на рис. 4.1. В рамках этой схемы один из имеющихся процессоров выделяется в качестве управляющего. Назначение управляющего процессора - выполнение представленной выше алгоритмической схемы характеристической представимости, вычисление и передачу свободным процессорам точек очередных испытаний, получение и обработку результатов испытаний от всех других процессоров системы. Все другие имеющиеся процессоры (кроме управляющего) являются исполнительными. Эти процессоры получают от управляющего процессора точки очередных испытаний, проводят вычисление значений оптимизируемой функции и передают результаты выполненных испытаний управляющему процессору. Подобная схема параллельных вычислений соответствует одному из широко используемых способов организации параллельных вычислений «менеджер-исполнители» (см., например, [22]); а происходящие в ходе вычислений процессы приема-передачи данных определяют одну из типовых топологий многопроцессорных систем в виде «звезды».
Отметим, что представленная схема характеристической представимости является асинхронной, т.е. каждый процессор-исполнитель взаимодействует с управляющим процессором совершенно независимо от других процессоров и получает точки, если есть свободный интервал, для проведения новых испытаний незамедлительно сразу после завершения своих вычислений для ранее полученных точек. Данный момент является важным, если время проведения испытаний может различаться (что и имеет место при частичной вычислимости функционалов оптимизационной задачи с ограничениями, при использовании многошаговой схемы редукции размерности и др.).
Как и ранее, характеристическая схема представимости параллельных алгоритмов глобального поиска, может быть детализирована для получения того или иного метода многоэкстремальной оптимизации указанием правила вычисления характеристики интервалов (4.2) и правила определения точки очередного испытания (4.3). Принципиально важный момент состоит в том, что в качестве этих правил могут быть использованы правила любого существующего последовательного характеристически представимого алгоритма поиска глобального поиска и, как результат, на его основе может быть сформирован параллельный метод многоэкстремальной оптимизации, соответствующий исходному последовательному алгоритму. Так, в частности, могут быть задействованы правила метода последовательного сканирования, метода ломаных (см. 1.2 Главы 1), а также правила всех информационно-статистических алгоритмов, рассмотренных в Главах 1-2.
Значимость схемы характеристической представимости как общей формы описания широкого класса параллельных алгоритмов глобального поиска, как и ранее, состоит в том, что в рамках этой схемы с единых позиций могут быть получены общие теоретические утверждения о свойствах исследуемых алгоритмов (необходимые и достаточные условия сходимости, характер и скорость сходимости и т.д.) — дополнительная информация в этом направлении может быть получена в [31].
В завершение описания характеристической схемы приведем из [31] результаты численных экспериментов для полученного в рамках этой схемы параллельного многомерного информационно-статистического алгоритма глобального поиска при многошаговом способе редукции размерности.
Пример 4.1. Для проведения вычислительных экспериментов использовался класс тестовых задач многоэкстремальной оптимизации из примера 3.1. При проведении вычислений для алгоритма глобального поиска использовался параметр надежности г=2 и точности поиска 0.01 по каждой переменной. Для получения надежных результатов для каждого количества процессоров решалось 100 задач данного тестового класса и затем результаты расчетов усреднялись. Результаты экспериментов приведены на рис. 4.2.
Ускорение, получаемое при использоваании параллельного многомерного информационно-статистического алгоритма глобального поиска при многошаговом способе редукции размерности на классе тестовых задач из примера 3.1. На рис. 4.2. по горизонтали указывается количество используемых процессоров в виде (Ри Pi), Р= Р\ Pi, где р\ есть количество процессоров, используемых для решения задачи первого уровня многошаговой схемы редукции, а рг есть количество процессоров, используемых для решения задачи второго уровня соответственно (тем самым, общее количество используемых процессоров оказывается равнымр= р\ р2).
Ось ординат на рис. 4.2. соответствует ускорению вычислений, получаемого за счет использования нескольких процессоров. Верхний график показывает идеальное ускорение (S=p), средний же график соответствует реальному получаемому ускорению при использовании параллельного многомерного информационно-статистического алгоритма глобального поиска при многошаговом способе редукции размерности. Для сравнения, на рис. 4.2 нижний график показывает получаемое ускорение для того же метода глобального поиска при использовании синхронного способа организации параллельных вычислений.
Распределенная схема параллельного глобального поиска для адаптивной многошаговой схемы редукции размерности
Система IHR (см., например, [76-77, 87-89, ПО, 117, 118, 123-124, 144-146, 151, 177, 187, 194]) использует случайный поиск на основе алгоритмов глобальной оптимизации, которые могут использоваться для решения непрерывных и дискретных проблем оптимизации. IHR генерирует случайную точку в области поиска в случайном направлении. Для выбора случайного направления используются разные подходы, например, выбираются несколько направлений вдоль, которых генерируются точки. Алгоритм позволяет решать задачи с ограничениями в виде неравенства. IHR используется для решения глобальных задач оптимизации в различных областях приложений.
Система MINBIS (см., например, [76-77, 87-89, ПО, 117, 118, 123-124, 144-146, 151, 177, 187, 194]) использует для глобальной оптимизации методы на основе интервальной арифметики. Следующим шагом на основе топологической характеристики отделяется минимумы от максимумов и седловые точки, данная информация позволяет определить глобальное решение. Система использовалась для решения задач оптимизации, в которых оптимизируемые функции вычисляются с погрешностями.
Системы INTGLO, INTGLOB (см., например, [76-77, 87-89, ПО, 117, 118, 123-124, 144-146, 151, 177, 187, 194]) решают задачи глобальной оптимизации с ограничениями и без ограничений с помощью интегральной технологии. Данный подход включает возможность использования разрывных функций штрафа для решения проблем оптимизации с ограничениями. При этом данный метод позволяет использовать до ста переменных. В данный пакет включены ряд тестовых задач, включая задачи с ограничениями и без ограничений, проблемы вогнутой минимизации, мультикритериальные программы.
- Система LGO (см., например, [76-77, 87-89, ПО, 117, 118, 123-124, 144-146, 151, 177, 187, 194]) позволяет решать общие задачи глобальной оптимизации. LGO осуществляет интеграцию нескольких глобальных (адаптивное разделение и поиск на случайно основе) и локальных (тип сопряженных направлений) стратегий, которые могут использоваться в автоматическом и ручном режиме. Версия программы для персональных компьютеров имеет интерактивный интерфейс, предоставляющий возможность обучения, информацию о программе и возможности визуализации.
Система MAGESTIC (см., например, [76-77, 87-89, ПО, 117, 118, 123-124, 144-146, 151, 177, 187, 194]) для автоматической глобальной 107 оптимизации на основе модифицированного метода Гаусса-Ньютона комбинированный с методами Монте-Карло. MAGESTIC обрабатывает различные варианты настройки модели. Может использоваться совместно с множителями Лагранжа для оптимизации с ограничениями.
Приведенный краткий обзор систем оптимизации показывает, что, при достаточном большом спектре программ оптимизации, по прежнему, использование высокопроизводительных вычислительных систем для решения задач глобальной оптимизации является ограниченным.
В данной главе приводится описание программного комплекса глобальной оптимизации GloptiCom, в котором реализованы разработанные в рамках диссертационной работы параллельные методы многоэкстремальной оптимизации.
Разработанный комплекс глобальной оптимизации GloptiCom предназначен для параллельного решения многоэкстремальных многомерных задач оптимизации при наличии нелинейных ограничений на многопроцессорных вычислительных системах. Предполагается, что функционалы решаемых задач оптимизации удовлетворяют условию Липшица и задаются вычислительно-трудоемкими процедурами расчета.
Алгоритмическую основу комплекса GloptiCom составляют алгоритмы глобального поиска, представленные в Главах 1-4. В состав комплекса GloptiCom входят три системы оптимизации (см. рис. 5.1): Система GloptiCom-1, ориентированная на решение задач одномерной многоэкстремальной оптимизации. Данная система предназначена для проведения вычислительных экспериментов с целью оценки эффективности одномерных алгоритмов глобального поиска,
Система GloptiCom-2, ориентированная на решение задач двухмерной многоэкстремальной оптимизации. Данная система предназначена для проведения вычислительных экспериментов с целью исследования адаптивной многошаговой схемы редукции размерности,
Система GloptiCom+ является основной в комплексе и ориентирована на параллельное решение задач многомерной многоэкстремальной оптимизации.
Структура каждой системы комплекса GloptiCom построена по общей схеме (см. рис. 5.2) — в составе системы выделяются оптимизационная компонента и компонента управления. Оптимизационная компонента содержит программные модули, реализующие алгоритмы глобального поиска. Компонента управления обеспечивает использование и выполнение системы оптимизации и организует взаимодействие с пользователем системы, управление вычислениями, визуализацию результатов и др.
Основное назначение системы GloptiCom-1 состоит в обеспечении возможности проведения вычислительных экспериментов с целью оценки эффективности одномерных алгоритмов глобального поиска. Алгоритмическую основу системы GloptiCom-1 составляют информационно-статистические алгоритмы многоэкстремальной оптимизации, представленные в характеристической форме: - Алгоритм глобального поиска (АГП), - Алгоритм глобального поиска с локальной настройкой константой при использовании минимаксной (АГП-ЛМ) и аддитивной (АГП-ЛА) сверток — см. параграф 2.2,
