Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

1.4. Циклическая схема обмена даннымиВ схеме без подциклов возможны следующие дополнительные ограничения (gi):4) число работ в цепочке не должно превышать заданного значения;5) суммарная длительность выполнения работ цепочки не должна превышатьзаданного значения;6) интервал времени между последовательными цепочками должен быть неменьше заданного значения;7) сдвиг работы «вправо» по временной оси на время, не превышающеезначение равное заданному проценту от интервала «время начала выполненияработы минус время начала цепочки» не должен приводить к нарушениюдирективного времени завершения работы или требования к минимальномуинтервалу времени между последовательными цепочками.С материалами данного раздела можно ознакомиться в работах:С материалами данного раздела можно ознакомиться в работах:1.Костенко В.А., Гурьянов Е.С.

Алгоритм построения расписаний обменов по шине сцентрализованным управлением и исследование его эффективности// Программирование, 2005.,N6. - С.67-76.2.Балашов В.В. Алгоритмы формирования рекомендаций при планировании информационногообмена по каналу с централизованным управлением// Известия РАН. Теория и системыуправления, 2007, N.6, с. 76-84.243.Балашов В.В., Костенко В.А. Задачи планирования вычислений для одноприборных систем,входящих в состав вычислительных систем реального времени// Методы и средства обработкиинформации: Третья Всероссийская научная конференция.

Труды конференции. - М.:Издательский отдел факультета ВМиК МГУ имени М.В. Ломоносова; МАКС Пресс, 2009. С.193-203.4.Костенко В.А. Алгоритмы построения расписаний для одноприборных систем, входящих всостав систем реального времени// Методы и средства обработки информации: ТретьяВсероссийская научная конференция. Труды конференции. - М.: Издательский отдел факультетаВМиК МГУ имени М.В. Ломоносова; МАКС Пресс, 2009.

- С.245-258.5.Р. Смелянский, В. Костенко, В. Балашов, В. Балаханов. Инструментальная система построениярасписания обмена данными по каналу с централизованным управлением// Современныетехнологии автоматизации, 2011., N.3, С.78-84.252. Алгоритмы случайного поискаОсновой методов случайного поиска служит итерационный процесс:X k 1  X k   k, k  0,1, ,где k – величина шага,   (1,,n) – некоторая реализация n-мерного случайноговектора .Ненаправленныйслучайныйпоиск(методМонте-Карло)заключаетсявX k 1   ,   S , g i ( )  0, k  0,1,  , i  1,  , m.многократном случайном выборе допустимых вариантов решений и запоминаниинаилучшего из них:Все алгоритмы направленного случайного поиска без самообучения делают шаг оттекущего значения Xk оптимизируемых параметров. Известны следующие алгоритмынаправленного случайного поиска без самообучения [Л.А.

Растригин. Статистические методыпоиска.- М.: Наука, 1968.]: алгоритм с парной пробой, алгоритм с возвратом при неудачномшаге, алгоритм с пересчетом при неудачном шаге, алгоритм с линейной экстраполяцией,алгоритм наилучшей пробы, алгоритм статистического градиента.Алгоритмы случайного направленного поиска с самообучением заключаются вперестройке вероятностных характеристик поиска, т.е. в определенном целенаправленномвоздействии на случайный вектор .

Он уже перестает быть равновероятным и врезультате самообучения приобретает определенное преимущество в направленияхнаилучших шагов. Это достигается введением вектора P k  ( p1k , p 2k , , p nk ) , где p kj -вероятность выбора положительного направления по j-ой координате на k-ом шаге.Алгоритм рекуррентно корректирует значение компонентов этого вектора на каждойитерации в зависимости от того, насколько удачным/неудачным (изменилось значениецелевой функции) был сделанный шаг.Разделы 2.1.

и 2.2. будут читаться в соответствии с [Л.А. Растригин.Статистические методы поиска.- М.: Наука, 1968.].2.1. Ненаправленный случайный поиск (метод Монте-Карло)262.2. Алгоритмы направленного случайного поиска без самообучения2.2.1. Алгоритм с парной пробой2.2.2. Алгоритм с возвратом при неудачном шаге2.2.3.

Алгоритм с пересчетом при неудачном шаге2.2.4. Алгоритм с линейной экстраполяцией2.2.5. Алгоритм наилучшей пробы2.2.6. Алгоритм статистического градиента2.3. Алгоритмы случайного направленного поиска с самообучением.Различные способы коррекции вектора направления наилучших шагов273. Алгоритмы имитации отжига3.1. Концепция построения алгоритмовАлгоритмы имитации отжига в процессе поиска оптимального решения снекоторой вероятностью допускают переход в состояние с более высоким значениемцелевой функции. Это свойство позволяет им выходить из локальных оптимумов.Принципы, положенные в основу работы алгоритмов, можно объяснить на следующейфизической аналогии [Уоссермен Ф.

Нейрокомпьютерная техника. Теория и практика.- М.: Мир, 1992. –240с.]. На рис.3.1. изображен шарик в коробке, внутренняя поверхность которойсоответствует ландшафту целевой функции. При сильном встряхивании коробки вгоризонтальном направлении шарик может переместиться из любой точки в любуюдругую. При постепенном уменьшении силы встряхивания будет достигнуто условие,когда сила встряхивания достаточна для перемещения шарика из точки А в точку В, нонедостаточна для того, чтобы шарик мог переместиться из В в А. При дальнейшемуменьшении силы встряхивания до нуля шарик остановится в точке В - точке глобальногоминимума.

В алгоритмах имитации отжига аналогом силы встряхивания являетсявероятность перехода в состояние с более высоким значением целевой функции. В началеработы алгоритма эта вероятность должна быть достаточно велика, чтобы былавозможность перехода от выбранного начального решения к любому другому решению. Впроцессе работы алгоритма вероятность перехода уменьшается в соответствии свыбранным законом.Рис. 3.1. Иллюстрация принципов работы алгоритмов имитации отжига.283.2.

Общая схема алгоритмов и проблемы построения алгоритмов длярешения задач условной оптимизацииДля решения задач условной оптимизации схему имитации отжига можнопредставить следующим образом:Ш а г 1. Задать начальное корректное решение X0S и считать его текущим вариантомрешения (X=X0).Ш а г 2. Установить начальную температуру Т0, приняв ее текущей (Т=Т0).Ш а г 3. Применить операции преобразования решения к текущему решению X и получитьновый корректный вариант решения X’ S.Шаг4.НайтиизменениефункционалаоценкикачестварешенияF  F ( f ( X ' ), g i ( X ' ))  F ( f ( X ), g i ( X )) :o если F  0 (решение улучшилось), то новый вариант решения считатьтекущим (X=X');o если F  0 (решение ухудшилось), то принять с вероятностью p  e FTвкачестве текущего решения новый вариант решения X'.Ш а г 5. Повторить заданное число раз шаги 3 и 4 без изменения текущей температуры.Ш а г 6.

Если критерий останова выполнен, то завершение работы алгоритма.Ш а г 7. Понизить текущую температуру в соответствии с выбранным законом пониженияи перейти к шагу 3.Для построения алгоритма имитации отжига для решения конкретной задачиусловной оптимизации требуется решить следующие задачи:1. Разработать способ представления решения X и операций преобразования текущегорешения на шаге 3.2.

Разработать стратегию применения операций преобразования текущего решения нашаге 3: какую операцию применять, к какому элементу X, как изменять егозначение.3. Выбрать закон понижения температуры на шаге 7.4. Определить функционал F ( f ( X ), g i ( X )) , используемый для оценки качестватекущего решения на шаге 4.5. Выбрать критерий останова алгоритма, используемый на шаге 6.Если есть gi не вошедшие в функционал F ( f ( X ), g i ( X )) , то на шаге 3 послепримененияоперацийпреобразованиярешения,должнополучатьсярешение,29удовлетворяющее этим ограничениям.

Наиболее часто функционал F ( f ( X ), g i ( X ))строится с использованием функций штрафа или барьерных функций [Мину].Способ представления решения X и операции преобразования текущего решениядолжны удовлетворять условиям замкнутости (после применения любой операции ккорректному решению получается корректное решение) и полноты (для двух любыхкорректных решений X, X* существует конечная последовательность операций,приводящая X к X*, такая, что все промежуточные решения корректны).

Условиязамкнутостииполнотысистемыоперацийпреобразованиярешенийявляютсядостаточными условиями того, что алгоритм за конечное число итераций может перейтиот начально-заданного решения к оптимальному решению.Стратегия применения операций преобразования текущего решения и законпонижения температуры определяют вычислительную сложность и точность алгоритма.При построении алгоритмов имитации отжига наиболее часто используютсяследующие законы понижения температуры:Закон Больцмана: T Закон Коши: T T  T0T0.ln(1  x )T0.1 xln(1  x ).1 xЗдесь T - текущая температура алгоритма, T0 - начальная температура, x - номер итерацииалгоритма. Начальная температура является параметром алгоритма и задается в качествеисходных данных.Использование этих законов понижения понижение температуры в алгоритмахимитации отжига для обучения нейросетей прямого распространения (т.е.

для решенияквадратичных задач безусловной оптимизации) выявило следующие их недостатки[Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика.- М.: Мир, 1992. – 240с.]. Так,использование закона понижения температуры Больцмана требует очень высокихначальных температур и чрезмерно большого числа итераций для получения приемлемогопо точности решения. При относительно невысоких температурах алгоритм с даннымрежимом понижения температуры не находит приемлемых по точности решений.Использование закона понижения температуры Коши значительно уменьшается числоитераций, производимых алгоритмом, однако при этом возможно “зависание” алгоритма влокальных оптимумах.

Характеристики

Список файлов лекций