Министерство образования и науки Российской Федерации
Федеральное Государственное бюджетное образовательное учреждение высшего профессионального образования “Саратовский государственный университет имени Н.Г.Чернышевского” (СГУ)
УДК 004.4, 681.3.06, 681.322
-
УТВЕРЖДАЮ
|
Ректор Федерального государственного бюджетного образовательного учреждения высшего профессионального образования “Саратовский государственный
университет имени Н.Г.Чернышевского”
_____________________ Л.Ю.Коссович
«_____» _________________2011г.
МП
|
ОТЧЕТ
О НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЕ
по Государственному контракту от 7 сентября 2011 года № 07.Р20.11.0029
“Подготовка и переподготовка профильных специалистов на базе центров образования и разработок в сфере информационных технологий в Южном и Северо-Кавказском федеральных округах”
Тема НИР: “РАЗРАБОТКА АЛГОРИТМОВ ПОИСКА ГЛОБАЛЬНЫХ ЭКСТРЕМУМОВ ПРИ НАЛИЧИИ ЯВНЫХ И НЕЯВНЫХ ОГРАНИЧЕНИЙ НА ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ”
Научный руководитель А.Н.Савин
Саратов 2011
Список исполнителей
Научный руководитель НИР,
доцент кафедры ДМиИТ,
к.ф.-м.н.
|
_________________
подпись, дата
|
А.Н.Савин (реферат, введение, раздел 1, заключение)
|
Исполнители темы
|
|
|
Студент 5 курса факультета КНиИТ СГУ
|
_________________
подпись, дата
|
А.А. Ерофтиев (раздел 2, раздел 4, приложение А, приложение В)
|
Студент 5 курса факультета КНиИТ СГУ
|
______________
подпись, дата
|
И.В. Дружинин(раздел 3, раздел 4, приложение Б, приложение В)
|
Реферат
Отчет 88с.,20 рис., 4 табл., 10 источников,3 прил.
УСЛОВНАЯ ОПТИМИЗАЦИЯ КОМПЛЕКСНЫМ МЕТОДОМ БОКСА, ОПТИМИЗАЦИЯ МЕТОДОМ ИМИТАЦИИ ОТЖИГА, ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ,МНОГОЭКСТРЕМАЛЬНАЯ ЦЕЛЕВАЯ ФУНКЦИЯ, ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ
Научно-исследовательская работа по теме «Разработка алгоритмов поиска глобальных экстремумов при наличии явных и неявных ограничений на параллельных вычислительных системах» выполняется в рамках федеральной целевой программы развития образования на 2011-2015 годы по Государственному контракту от 7 сентября 2011 года №07.Р20.11.0029.
Объектом исследования являются различные алгоритмы нахождения глобального экстремума многопараметрических целевых функций при наличии явных и неявных ограничений.
Цель работы – исследование возможности распараллеливания известных алгоритмов нахождения глобального минимума многоэкстремальной целевой функции многих переменных с явными и неявными ограничениями, а также оценка их эффективности при выполнения на параллельных вычислительных системах.
В процессе работы предложены варианты распараллеливания комплексного метода оптимизации Бокса, алгоритма оптимизации, основанного на методе имитации отжига и генетического алгоритма оптимизации. Проведены экспериментальные исследования по оценке их эффективности и надёжности в сравнении с исходными алгоритмами.
В результате исследования для комплексного метода оптимизации Боксаопределено оптимальное число узлов вычислительной системы с точки зрения требуемой точности вычислений и стабильности результатов. При этом время выполнения программы оказалось в несколько раз меньше, чем на одной ЭВМ, а надёжность нахождения глобального экстремума значительно выше за счёт одновременного исследования целевой функции в нескольких областях факторного пространства.
Для алгоритма оптимизации, основанного на методе имитации отжига определены зависимостинадёжности нахождения глобального минимума от количества узлов параллельной вычислительной системы. Показано, что распараллеленный вариант алгоритма имитации отжига, использующий схему Больцмановского тушения, позволяет за небольшое время надёжно находить область глобального минимума.
Для параллельного варианта классического генетического алгоритма оптимизации найдены зависимости надёжностии времени нахождения глобального минимума от количества узлов параллельной вычислительной системы.Определены оптимальные параметры алгоритма, обеспечивающие достаточно быструю сходимость.
Результаты работы могут использоваться при решении оптимизационных задач в различных технических областях, в том числе при разработкеи исследованиях нано- и метаматериалов.
Степень внедрения – научные публикации, программы для ЭВМ.
Настоящий отчет является заключительным. Работа в рамках проекта завершена в соответствии с календарным планом Государственного контракта от 7 сентября 2011 года №07.Р20.11.0029.
Определения
В настоящем отчете используются следующие определения:
Условная оптимизация
|
Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функциимногих переменных (целевой)при наличии различных ограничений на них
|
Многоэкстремальная целевая функция
|
Целевая функция, имеющая как локальные, так и глобальный экстремумы
|
Глобальный экстремум
|
Крайнее значение числовой функции на всем множестве значений, принимаемых этой функцией, т. е. ее глобальный максимум или глобальный минимум
|
Параллельные вычислительные системы
|
Это физические компьютерные, а также программные системы, реализующие тем или иным способом параллельную обработку данных на многих вычислительных узлах
|
Обозначения и сокращения
В настоящем отчете использованы следующие обозначения и сокращения:
ВС
|
вычислительная система
|
ЦФ
|
целевая функция
|
ГА
|
генетический алгоритм
|
Содержание
Список исполнителей
|
2
|
Реферат
|
3
|
Определения
|
4
|
Обозначения и сокращения
|
5
|
Содержание
|
7
|
Нормативные ссылки
|
8
|
Введение
|
9
|
1 Постановка задачи поиска глобального минимума при наличии ограничений
|
10
|
2 Поиск глобального минимума модифицированным комплексным методом Бокса
|
12
|
2.1 Адаптация алгоритма оптимизации модифицированным комплексным методом Бокса для использования на параллельной ВС
|
15
|
2.2 Оценка эффективности распараллеленного алгоритма оптимизации модифицированным комплексным методом Бокса
|
18
|
3 Поиск глобального минимума методом имитации отжига
|
27
|
3.1 Адаптация алгоритма оптимизации методом имитации отжига для использования на параллельной ВС
|
30
|
3.2 Оценка эффективности распараллеленного алгоритма оптимизации методом имитации отжига
|
32
|
4 Поиск глобального минимума с использованием генетического алгоритма
|
37
|
4.1 Адаптация генетического алгоритма оптимизации для использования на параллельной ВС
|
40
|
4.2 Оценка эффективности оптимизации с использованием параллельных вариантов генетического алгоритма
|
44
|
Заключение
|
53
|
Список использованных источников
|
55
|
Приложение А
|
56
|
Приложение Б
|
69
|
Приложение В
|
76
|
Нормативные ссылки
В настоящем отчете использованы ссылки на следующие стандарты.
ГОСТ 15.101–98
|
Система разработки и постановки продукции на производство. Порядок выполнения научно-исследовательских работ
|
ГОСТ 19.001-77
|
ЕСПД. Общие положения.
|
ГОСТ 19.401-78
|
ЕСПД. Текст программы. Требования к содержанию и оформлению
|
ГОСТ 7.1-2003
|
Система стандартов по информации, библиотечному и издательскому делу. Библиографическая запись. Библиографическое описание. Общие требования и правила составления
|
ГОСТ 7.32-2001
|
Система стандартов по информации, библиотечному и издательскому делу. Отчет о научно-исследовательской работе. Структура и правила оформления
|
Введение
Основанием для проведения научно-исследовательской работы (НИР) является Государственный контракт от 7 сентября 2009 года № 07.Р20.11.0029. Начало работ: 10 октября 2011 г., окончание работ: 28 ноября 2011 г.
Многие сферы деятельности человека в настоящее время, такие как разработка новых материалов и устройств, телекоммуникационные сети, требуют решения оптимизационных задач. Как известно, подобные задачи сводятся к поиску экстремумов ЦФ различными методами [1].
Задачи оптимизации,как правило, содержат явные ограничения на значения параметров и различные дополнительные условия – неявные ограничения. При этом ЦФ часто оказываются многоэкстремальными. Существующие для решения таких задач методы условной оптимизации, как градиентные, так и случайного поиска, не гарантируют нахождение глобального экстремума и требуют больших вычислительных затрат [1].
Проблема нехватки вычислительных ресурсов может быть решена применением современных параллельных и распределённых систем вычислений, в сочетании с эффективно работающими на этих системах алгоритмами условной оптимизации, учитывающими особенности конкретных задач [1].
Соответственно, разработка таких алгоритмов является актуальной задачей.
Целью данной работы является изучение возможностей распараллеливания модифицированного комплексного метода оптимизации Бокса [2, 3], алгоритма оптимизации, основанного на методе имитации отжига [4-7] и генетических алгоритмов оптимизации [8, 9], применяемых при поиске глобальных экстремумов, а также оценка эффективности и надёжности этих алгоритмов при выполнении на параллельных ВС.
Данная работа тесно связана с плановыми научно-исследовательскими работами, проводимыми на кафедре дискретной математики и информационных технологий СГУ. Уровень разработки определяется имеющимися по теме публикациями студентов, аспирантов и сотрудников кафедры, их выступлениями на различных научных конференциях.
1 Постановка задачипоиска глобального минимума при наличии ограничений
Поиск глобального минимума функции  при наличии ограничений осуществляется на некотором собственном подмножестве  метрического пространства  [2]:
 , (1)
где подмножество определяется явными ограничениями
 , (2)
а также неявными ограничениями
 . (3)
Пусть имеется некоторое множество  состоящее из элементов  , принадлежащих подмножеству  , и на нём определена скалярная функция  Говорят, что  имеет локальный минимум в точке  , если существует некоторая конечная  -окрестность этой точки, в которой выполняется условие:
  .
У функции может быть много локальных минимумов. Если выполняется неравенство   , где  – любая точка множества , то говорят о глобальном минимуме функции [10].
Например, многоэкстремальная функцияможет иметь вид:
 . (4)
Эта функция имеет множество локальных минимумов и глобальный минимум, равный -0.2 при  . Вид функции приведён на рисунке1.
Как указывается в [10],в случае наличия явных (2) и неявных ограничений (3) (вид которых в реальных задачах не слишком прост) поиск глобального минимумамногоэкстремальных функций становится очень сложной задачей.
Рисунок 1– Вид многоэкстремальной функциидвух переменных
2Поиск глобального минимума модифицированным комплексным методом Бокса
Поиск глобального минимума многоэкстремальной функции (1) при наличии явных (2) и неявных (3) ограничений на варьируемые параметры может быть осуществлён комплексным методом Бокса [2] с учётом его модификаций, предложенных в [3].
Комплексный метод Бокса использует при поиске экстремума только значения функции, а не её производные, то есть это метод прямого поиска. Он является модификацией симплексного метода Нелдера-Мида [2], основанного на применении процедуры симплекс-планирования при поиске экстремумов, однако позволяет учитывать явные и неявные ограничения на изменения варьируемых параметров.
Если функция  (1) выпукла и неявные ограничения  (3) тоже выпуклы, то сформулированная выше задача поиска минимума имеет единственное решение, которое успешно находится комплексным методом Бокса. Однако при наличии локальных невыпуклостей функции , т.е. при её многоэкстремальности данный метод имеет возможность зацикливания [2].
В [3] предложена модификация комплексного метода Бокса, исключающая возможность зацикливания. Она основана на дополнительном исследовании функции в текущей области изменения варьируемых параметров для выявления локальных невыпуклостей и на их обходе. Алгоритм оптимизации модифицированным комплексным методом Бокса приведён ниже.
Поиск глобального минимума ЦФ (1) начинается с определения количества параметров  , инициализации нижних и верхних границ явных ограничений (2) , ввода неявных ограничений(3) .
Строится комплекс из  случайным образом распределённых точек в области, заданной ограничениями (2) и (3) (Бокс использовал коэффициент умножения комплекса  ):
выбирается начальная точка  , удовлетворяющая ограничениям (2) и (3);
координаты остальных точек, удовлетворяющих ограничениям (2), выбираются следующим образом:
 , (5)
где  ,  ,  – псевдослучайная равномерно распределенная переменная в интервале  ;
если выбранная в соответствии с (5) точка  не удовлетворяет неявным ограничениям (3), то она смещается на половину расстояния до центра тяжести множества уже принятых точек– :  , т.е. формируется точка :
 ; (6)
точке присваивается значение смещённой точки  :  ;
если точка всё еще не является допустимой, то описанная соотношением (6) процедура повторяется до тех пор, пока точка не станет допустимой, а если функции  выпуклы, то, в конце концов, ограничения выполняться;
точки комплекса упорядочиваются в соответствии со значениями ЦФ:  .
Определяется наименьшее значение ЦФ – :  .
Определяются точка с наибольшим значением ЦФ– и центр тяжести остальных  точек – :  .
Вычисляется точка отражением худшей точки относительно центра тяжести, используя коэффициент отражения  :  .
Вычисляется значение ЦФ в центре тяжести точек  .
Осуществляется проверка ЦФ на выпуклость: если  , то ЦФ выпукла и переходим к шагу 8, иначе центр тяжести заменяется на лучшую точку –:  .
Выполняется проверка, является ли отражённая точка допустимой:
если не выполняются ограничения для , то  ;
если не выполняются ограничения для  , то  ;
если не выполняются неявные ограничения (3), то точка перемещается на половину расстояния между и центром тяжести :  , а отражённой точке присваивается значение  :  .
Производится повторная проверка отражённой точкина допустимость и шаг 8 повторяется до тех пор, пока не будет получена допустимая точка.
Осуществляется проверка на улучшение отражённой точки :
вычисляется значение ЦФ и сравнивается с  – наибольшим значением ЦФ в комплексе;
если , т.е. не лучше, чем наибольшее значение ЦФ, полученное ранее, то отражённая точка перемещается на половину расстояния между  и центром тяжести : , отражённой точке присваивается значение :  и процесс возвращается на шаг 8;
если  , то худшая точка заменяется на точку:  , то есть комплекс обновляется,а точки комплекса упорядочиваются в соответствии со значениями ЦФ: .
Оценивается значение ЦФ в лучшей точке – : если  , то есть наименьшее значение ЦФ – не уменьшено, то процесс возвращается на шаг 4. Иначе выполняется проверка сходимости:
вычисляется квадрат стандартного отклонения значений ЦФ для всех  точек комплекса – :  , где  ;
вычисляется максимальное расстояние между точками комплекса – :
 ;
если  и , где  достаточно малые заданные величины, то процедура поиска минимумацелевой функции  (1) заканчивается. Иначе осуществляется возврат на шаг 3 и продолжается поиск минимума.
Шаги 6 и 7, введённые в представленный в [2] исходный алгоритм комплексного метода Бокса, обеспечивают выявление и обход локальных невыпуклостей ЦФ. Соответственно, такие изменения, совместно со случайным выбором начальных точек в факторном пространстве позволяют использовать модифицированный комплексный метод Бокса для поиска глобального минимума многоэкстремальных ЦФ при наличии явных и неявных ограничений.
При этом, как установлено в [2], для проверки того, что был найден глобальный, а не локальный минимум требуется производить несколько запусков при различных начальных точках. Это приводит к пропорциональному увеличению вычислительных и, соответственно, временных затрат, что недопустимо для сложных, многопараметрических ЦФ.
В этом случае проблема повышения эффективности работы рассматриваемого алгоритма, с точки зрения минимизации времени вычислений, может быть решена путём его распараллеливания. |
