В. А. Костенко 119899, Москва, гсп-3, Воробьевы горы, мгу, 2-й учебный корпус, ф-т вмиК, тел
| скачать Труды Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения" (30 октября - 2 ноября 2000 г., Черноголовка). -М.: Изд-во МГУ, 2000, С.123-127. АЛГОРИТМЫ ОПТИМИЗАЦИИ, ОПИРАЮЩИЕСЯ НА МЕТОДПРОБ И ОШИБОК, В COВМЕСТНОМ ПРОЕКТИРОВАНИИ АППАРАТНЫХ И ПРОГРАММНЫХ СРЕДСТВ ВС. В.А. Костенко119899, Москва, ГСП-3, Воробьевы горы, МГУ, 2-й учебный корпус, ф-т ВМиК, тел.: (095) 939-46-71, е-mail: kost@cs.msu.su Задача синтеза архитектур и построения расписаний. Задача синтеза архитектур ВС под заданное приложение является одной из подзадач совместного проектирования аппаратных и программных средств ВС. Данная задача в самом общем виде может быть поставлена следующим образом. Для заданного поведения программы требуется синтезировать архитектуру ВС и построить расписание выполнения программы на полученной архитектуре. При этом должны оптимизироваться критерии оценки качества решения и выполняться ограничения на допустимые решения. Поведение программы задается в инвариантной форме относительно архитектуры ВС. В качестве параметров оптимизации (X) выступают варьируемые параметры архитектуры ВС и расписания выполнения программы. Критерии оценки качества решения, ограничения на допустимые решения и варьируемые параметры определяются при конкретизации задачи синтеза архитектур. Задача синтеза архитектур может быть представлена как экстремальная задача с ограничениями [1] и заключается в нахождении компонентов вектора X = (x1,,xn) (оптимизируемых параметров) минимизирующих целевую функцию f(X) при выполнении ограничений gi(X) и X S: min f(X) gi(X) 0, i=1,,m (1) X S По свойствам функций f,gi и определению множества S можно ввести классификацию различных задач оптимизации [2]. Например, если функции f,gi – линейные и S Zn , то задача (1) относится к классу задач целочисленного линейного программирования. Под сложными задачами оптимизации с ограничениями будем понимать задачи (1) для которых отсутствует априорная информация о функциях f,gi и множестве S, которая может быть использована для организации поиска оптимального решения, или сложность получения этой информации неприемлема. В большинстве практических вариантов постановок, задачи синтеза архитектур и построения расписаний относятся к классу сложных задач оптимизации с ограничениями. Можно выделить следующие основные особенности сложных задач оптимизации: 1. Функций f,gi могут быть операторами, заданными правилами/алгоритмами их вычисления, т.е. их аналитическая структура не может быть использована для организации поиска оптимального решения задачи (1). 2. Негладкий характер функций f,gi. 3. Отсутствие информации о производных функций f,gi или их производные не являются непрерывными. 4. Множество S может быть компонентно разнородным: S = SR SZ SF SKS, т.е. различные компоненты вектора X могут принадлежать подмножествам множества действительных чисел (R), целых чисел (Z), функций (F) и комбинаторных структур (KS). Комбинаторные структуры в задачах синтеза архитектур могут быть: расписаниями, перестановками, размещениями и сочетаниями. В качестве метрики в SKS используется длина цепочки операций из набора O, необходимая для перехода от одного варианта решения к другому. Где O – минимальный функционально полный набор операций для соответствующей комбинаторной структуры. Указанные выше особенности делают проблематичным применение оптимальных и эвристических методов, использующих некоторые априорно известные свойства для организации поиска оптимального решения. При больших размерности и/или размерах задачи (1) методы полного перебора допустимых решений также оказываются неприемлемыми по сложности. Идея о целесообразности случайного поведения, при наличии неопределенности, т.е. отсутствии достаточной информации, которая может быть использована для организации поиска оптимального решения/поведения, впервые в четкой форме была сформулирована У.Р. Эшби в работе [3] и реализована в известном гомеостате (гомеостат Эшби). Применительно к сложным задачам оптимизации, алгоритм поиска оптимального решения должен опираться на метод проб и ошибок. Только такой процесс позволяет извлечь информацию, необходимую для организации поиска решения. Метод проб и ошибок основан на понятии случайного эксперимента: случайного выбора значений компонентов вектора X, что дает возможность получить информацию о функциях f,gi и множестве S, которая может быть использована для организации поиска решения сложной задачи оптимизации с ограничениями. ^ Для решения сложных задач оптимизации из области совместного проектирования аппаратных и программных средств ВС проанализированы преимущества и недостатки следующих алгоритмов:
Схематично работу всех этих алгоритмов можно представить следующим образом:
Алгоритмы случайного поиска и имитации отжига на каждой итерации работают с одним значением вектора ^ , генетические и эволюционные алгоритмы - с некоторым множеством значений {X} (популяцией). Основную вычислительную сложность в данных алгоритмах при решении задач синтеза архитектур, как правило, составляет п.2 (вычисление значений целевой функции и ограничений, связанных с динамическими характеристиками функционирования ВС). В предельном случае их значения могут вычисляться с помощью имитационной модели параметризованной по параметрам, включенным в вектор X. Все рассматриваемые алгоритмы при формировании Xk+1 включают элемент случайности, но имеют различную динамику (получение вектора Xk+1=D(Xk, f(Xk)), п.3). Следовательно, они могут существенно отличаться по числу итераций и достижимому качеству получаемых решений за конечное число итераций. Ниже коротко рассмотрим основные принципы построения рассматриваемых алгоритмов. Более подробное описание алгоритмов можно найти в указанной литературе. ^ О  сновой методов случайного поиска служит итерационный процесс: где k – величина шага, (1,,n) – некоторая реализация n-мерного случайного вектора . Н  енаправленный случайный поиск (метод Монте-Карло) заключается в многократном случайном выборе допустимых вариантов решений и запоминании наилучшего из них: Все алгоритмы направленного случайного поиска без самообучения делают шаг от текущего значения Xk оптимизируемых параметров. Известны следующие алгоритмы направленного случайного поиска без самообучения [4]: алгоритм с парной пробой, алгоритм с возвратом при неудачном шаге, алгоритм с пересчетом при неудачном шаге, алгоритм с линейной экстраполяцией, алгоритм наилучшей пробы, алгоритм статистического градиента. Алгоритмы случайного направленного поиска с самообучением заключаются в перестройке вероятностных характеристик поиска, т.е. в определенном целенаправленном воздействии на случайный вектор . Он уже перестает быть равновероятным и в результате самообучения приобретает определенное преимущество в направлениях наилучших шагов. Это достигается введением вектора  , где  - вероятность выбора положительного направления по j-ой координате на k-ом шаге. Алгоритм рекуррентно корректирует значение компонентов этого вектора на каждой итерации в зависимости от того, насколько удачным/неудачным (изменилось значение целевой функции) был сделанный шаг. Описание и анализ различных способов коррекции вектора Pk приведены в [4].^ Концепцию построения генетических алгоритмов, предложенную Холландом [5], схематично можно представить следующим образом:
Популяция - это множество битовых строк для генетических алгоритмов и множество строк, состоящих из символов конечного алфавита, для эволюционных алгоритмов. Каждая строка представляет в закодированном виде одно из возможных решений задачи. По строке может быть вычислена целевая функция, которая характеризует качество решения. В качестве начальной популяции может быть использован произвольный набор строк. Основные операции алгоритма: селекция, скрещивание и мутация выполняются над элементами популяции. Результатом их выполнения является очередная популяция. Данный процесс продолжается итерационно до тех пор, пока не будет, достигнут критерий останова. ГА отличаются от эволюционных алгоритмов в основном способом кодирования и универсальностью основных операций. В дальнейшем будем рассматривать лишь ГА (при кодировании решений допустим лишь бинарный алфавит). Операция селекции обеспечивает формирование на очередной итерации алгоритма из строк, полученных на шагах 4 и 5, новой популяции. В данной работе приведем лишь два наиболее часто используемых варианта выполнения операции: схема пропорциональной селекции и схема рулетки. В схеме пропорциональной селекции, строка со значением целевой функции  даёт в новую популяцию  потомков, где  - среднее значение целевой функции для популяции. В схеме рулетки каждой строке выделяется сектор рулетки с центральным углом  . Строка получает потомка, если случайно сгенерированное число в пределах от 0 до  попадает в сектор соответствующий этой строке. Эти действия выполняются до тех пор, пока не будет полностью получен новый набор строк.Простейший вариант операции скрещивания (одноточечное скрещивание) выполняется следующим образом: 1)вся популяция случайным образом разбивается на пары; 2)для каждой пары случайным образом генерируется число  , если  , то выбирается случайное целое число i в интервале (1, l-1) и строки обмениваются фрагментами, находящимися после i-го бита, в противном случае ничего не происходит. Где l - длина строки,  - вероятность скрещивания. При многоточечном скрещивании выбирается несколько точек разрыва строки.Операция мутации заключается в инвертировании каждого бита с заданной вероятностью. Параметр операции - вероятность мутации (  ). Операция выполняется следующим образом: 1)для каждого бита генерируется случайное число  ; 2) если  , то бит инвертируется.В большинстве алгоритмов используется один или некоторая комбинация следующих способов останова: 1)выполнение алгоритмом априорно заданного числа итераций K*; 2)выполнение алгоритмом априорно заданного числа итераций без улучшения целевой функции K*; 3)достижение некоторого априорно заданного значения целевой функции f*. Алгоритмы имитации отжига. Алгоритмы имитации отжига с некоторой вероятностью допускают переход в состояние с более высоким значением целевой функции:  где T- некоторая температура,  . Поиск минимума начинается при высоком значении температуры T. В ходе работы алгоритма эта температура постепенно снижается (например, на 5% после выполнения заданного числа итераций). Поиск продолжается до тех пор, пока система не захватывается минимумом, из которого она уже не может выйти за счет тепловых флуктуаций.^ В таблице 1 приведены результаты анализа рассматриваемых алгоритмов. Сокращения: ГА – генетические алгоритмы, ОТЖ – алгоритмы имитации отжига, алгоритмы случайного поиска (СП - ненаправленного, НСП - направленного, НСПС - направленного с самообучением), все параметры алгоритмов, приведенные в строке 2, соответствуют параметрам, используемым при описании алгоритмов. Проблема настройки параметров алгоритмов характеризует сложность их применения и разработки. Под сложностью f(X) понимаем размер вектора X и степень не гладкости (не монотонности) f. Под локальной адаптацией к характеристикам f понимаем настройку на свойства f лишь в некоторой окрестности точки, в которой находится алгоритм, под глобальной - настройку на характеристики f на всем допустимом пространстве решений. Из алгоритмов направленного случайного поиска без самообучения следует выделить алгоритм с линейной экстраполяцией. Алгоритм работает в предположении, что целевую функцию в зоне поиска можно считать линейной. В случае неудачного пробного шага алгоритм делает двойной рабочий шаг в противоположном направлении, но целевая функция и ограничения в этой точке не вычисляются, а экстраполируются. Данный алгоритм обладает повышенной сходимостью и пониженной вычислительной сложностью по сравнению со всеми остальными алгоритмами случайного поиска без самообучения. Однако, он плохо работает в случае нелинейности целевой функции в зоне поиска и требует введения направления изменения комбинаторных параметров. Скорость сходимости алгоритмов направленного случайного поиска с самообучением при росте сложности целевой функции стремится к скорости сходимости алгоритмов случайного поиска без самообучения. Например, для модельной целевой функции уже при размере вектора X равном 5, алгоритм с самообучением делает лишь в 2 раза меньше итераций. Алгоритмы имитации отжига в принципе всегда позволяют находить экстремум достаточно близкий к глобальному при очень медленном понижении T, но требуют для этого неприемлемо большого числа итераций. При более быстром понижении T число итераций уменьшается, но в этом случае система может быть захвачена локальным минимумом, из которого она уже не может выйти. Проблема выбора режима понижения T, соответствующего сложности целевой функции, на настоящий момент времени остается не решенной. Генетические алгоритмы являются более универсальными по сравнению с остальными рассматриваемыми алгоритмами и, как правило, требуют (при правильной настройке параметров) наименьшего числа итераций. Однако, проблема разработки и настройки генетических алгоритмов, обладающих универсальностью в широком диапазоне характеристик f и высокой скоростью сходимости, является наиболее сложной. Таблица 1
Литература.
|
Ваша оценка этого документа будет первой.
Ваша оценка: 