В. А. Костенко 119899, Москва, гсп-3, Воробьевы горы, мгу, 2-й учебный корпус, ф-т вмиК, тел icon

В. А. Костенко 119899, Москва, гсп-3, Воробьевы горы, мгу, 2-й учебный корпус, ф-т вмиК, тел



Смотрите также:
В. А. Костенко мгу им. М. В. Ломоносова Россия, 119899, Москва, гсп-3, Воробьевы горы, мгу...
Монархическое движение в россии: 1905-1917 гг. (На материалах уфимской губернии)...
С. А. Остроумов Биологический факультет мгу им. М. В. Ломоносова, кафедра гидробиологии, Москва...
«глобалистика – 2009» Пути выхода из глобального кризиса и модели нового мироустройства...
«интеллектуальные системы» проводит с 20 по 23 мая 2009 года международный научный конгресс...
Эффективность государственных адресных социальных программ...
Управленческая отчетность коммерческого банка...
Республики в системе взаимоотношений «центр регионы»: политологический анализ российского и...
Славяне и финны на северо-западе древнерусского государства...
Программа учебного курса Инженерная геология, часть 2...
Xvi международные рождественские образовательные чтения...
Формирование словообразовательной компетенции филолога-русиста (русский язык как иностранный)...



скачать
Труды Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения" (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, которая может быть использована для организации поиска решения сложной задачи оптимизации с ограничениями.


^ Схема построения алгоритмов, опирающихся на метод проб и ошибок.

Для решения сложных задач оптимизации из области совместного проектирования аппаратных и программных средств ВС проанализированы преимущества и недостатки следующих алгоритмов:

  • алгоритмы случайного поиска (ненаправленного, направленного, направленного с самообучением)[4],

  • генетические и эволюционные алгоритмы [1,5-7],

  • алгоритмы имитации отжига [8],

Схематично работу всех этих алгоритмов можно представить следующим образом:

  1. Задать начальное приближение X0.

  2. Вычислить целевую функцию f(Xk) и проверить выполнение ограничений gi(Xk) и XkS (если в п.3 возможно получение недопустимых значений вектора X).

  3. Получить вектор Xk+1=D(Xk, f(Xk)).

  4. Если критерий останова не достигнут, то перейти к п.2, в противном завершить работу алгоритма.

Алгоритмы случайного поиска и имитации отжига на каждой итерации работают с одним значением вектора ^ X, генетические и эволюционные алгоритмы - с некоторым множеством значений {X} (популяцией). Основную вычислительную сложность в данных алгоритмах при решении задач синтеза архитектур, как правило, составляет п.2 (вычисление значений целевой функции и ограничений, связанных с динамическими характеристиками функционирования ВС). В предельном случае их значения могут вычисляться с помощью имитационной модели параметризованной по параметрам, включенным в вектор X. Все рассматриваемые алгоритмы при формировании Xk+1 включают элемент случайности, но имеют различную динамику (получение вектора Xk+1=D(Xk, f(Xk)), п.3). Следовательно, они могут существенно отличаться по числу итераций и достижимому качеству получаемых решений за конечное число итераций. Ниже коротко рассмотрим основные принципы построения рассматриваемых алгоритмов. Более подробное описание алгоритмов можно найти в указанной литературе.


^ Алгоритмы случайного поиска.

О
сновой методов случайного поиска служит итерационный процесс:

где k – величина шага, (1,,n) – некоторая реализация n-мерного случайного вектора .

Н
енаправленный случайный поиск (метод Монте-Карло) заключается в многократном случайном выборе допустимых вариантов решений и запоминании наилучшего из них:

Все алгоритмы направленного случайного поиска без самообучения делают шаг от текущего значения Xk оптимизируемых параметров. Известны следующие алгоритмы направленного случайного поиска без самообучения [4]: алгоритм с парной пробой, алгоритм с возвратом при неудачном шаге, алгоритм с пересчетом при неудачном шаге, алгоритм с линейной экстраполяцией, алгоритм наилучшей пробы, алгоритм статистического градиента.

Алгоритмы случайного направленного поиска с самообучением заключаются в перестройке вероятностных характеристик поиска, т.е. в определенном целенаправленном воздействии на случайный вектор . Он уже перестает быть равновероятным и в результате самообучения приобретает определенное преимущество в направлениях наилучших шагов. Это достигается введением вектора , где - вероятность выбора положительного направления по j-ой координате на k-ом шаге. Алгоритм рекуррентно корректирует значение компонентов этого вектора на каждой итерации в зависимости от того, насколько удачным/неудачным (изменилось значение целевой функции) был сделанный шаг. Описание и анализ различных способов коррекции вектора Pk приведены в [4].


^ Генетические и эволюционные алгоритмы.

Концепцию построения генетических алгоритмов, предложенную Холландом [5], схематично можно представить следующим образом:

  1. Сгенерировать случайным образом популяцию размера P;

  2. Вычислить целевую функцию для каждой строки популяции;

  3. Выполнить операцию селекции;

  4. Выполнить операцию скрещивания;

  5. Выполнить операцию мутации;

  6. Если критерий останова не достигнут, перейти к шагу 2, иначе завершить работу.

Популяция - это множество битовых строк для генетических алгоритмов и множество строк, состоящих из символов конечного алфавита, для эволюционных алгоритмов. Каждая строка представляет в закодированном виде одно из возможных решений задачи. По строке может быть вычислена целевая функция, которая характеризует качество решения. В качестве начальной популяции может быть использован произвольный набор строк. Основные операции алгоритма: селекция, скрещивание и мутация выполняются над элементами популяции. Результатом их выполнения является очередная популяция. Данный процесс продолжается итерационно до тех пор, пока не будет, достигнут критерий останова.

ГА отличаются от эволюционных алгоритмов в основном способом кодирования и универсальностью основных операций. В дальнейшем будем рассматривать лишь ГА (при кодировании решений допустим лишь бинарный алфавит).

Операция селекции обеспечивает формирование на очередной итерации алгоритма из строк, полученных на шагах 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




ГА

ОТЖ

НСПС

НСП

СП


Проблема настройки параметров алгоритма

Да

(P, pc, pm, K*,f*)

Да

(режим понижения T)

Да


(k, способ коррекции Pk)

Да


(k)

(в некоторых модификациях нет)

Нет


Адаптация к характеристи-кам f

Высокая


(сочетание локальной и глобальной)

Высокая


(при медленном снижении T)

Низкая


(локальная)

Нет

Нет


Скорость сходимости

Не зависит от сложности f

Уменьшается с возрастанием сложности f

Значительно уменьшается с возрастанием сложности f

Низкая

Низкая

Проблема направления движения для xiSKS

Нет

Нет


(в некоторых модификациях да)

Да

Нет


(в некоторых модификациях да)

Нет



Литература.

  1. Костенко В.А., Трекин А.Г. Генетические алгоритмы решения смешанных задач целочисленной и комбинаторной оптимизации при синтезе архитектур ВС// Искусственный интеллект (Донецк), 2000, No 2, c.90-96.

  2. М. Мину. Математическое программирование. Теория и алгоритмы.- М.: Наука, 1990.

  3. У. Росс Эшби. Конструкция мозга.- М.:, ИЛ, 1962.

  4. Л.А. Растригин. Статистические методы поиска.- М.: Наука, 1968.

  5. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.

  6. Костенко В.А. Принципы построения генетических алгоритмов и их использование для решения задач оптимизации// Труды IV Международной конференции "Дискретные модели в теории управляющих систем" (19-25 июня 2000 г.) с.49-55.

  7. Костенко В.А., Смелянский Р.Л., Трекин А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов// Программирование, 2000, N 5.

  8. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика.- М.: Мир, 1992.




Скачать 127,61 Kb.
оставить комментарий
Дата29.09.2011
Размер127,61 Kb.
ТипЗадача, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх