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

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

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

Вершина О является началом всех маршрутов.A’={(ni+,nj–),(ni+,nj+),(ni–,nj–)|i,j[1..n],ij}{(O,ni+),(O,ni–)|i[1..n]}–множество ребер. Вершины, соответствующие одной работе, ребрами не связаны.Алгоритм построения расписания по заданной последовательности работполностью аналогичен предыдущему, за исключением того, что в п.4 при размещенииработы, соответствующей вершине nj– текущее окно закрывается принудительно(происходит переход к п.6).

Расписание, построенное при помощи такого алгоритма,также будет удовлетворять условиям корректности.100Заметим, что расписания, которые строятся приведенными алгоритмами (какбазовым, так и модифицированным), помимо условий корректности, обладаютследующими свойствами:ta j SWij  2  Fi  Si-длинавременногоинтервала окна является минимальнодопустимой. max ( s j ), i  1a j SWiSi  ( s j , Fi 1  1), i  1amaxj SWi-времяоткрытия окна является минимальным,без нарушения ограничений 2 и 4.Покажем, что модифицированный алгоритм всегда может построить оптимальноерасписание по некоторому пути в G’.Теорема.

ДлялюбогокорректногорасписанияSPможнонайтитакуюпоследовательность вершин SL, что по данной последовательности модифицированныйалгоритм восстановления расписания построит такое корректное расписание SP*, чтоi[1..k]:SWi*=SWi , количество окон в SP* не меньше количества окон в SP.Доказательство:построимискомуюпоследовательностьSL={nip|nipN’,i[1..n],p{+,–}} следующим образом: SL=SL1SL2…SLm, где SLi –последовательность из вершин, соответствующих работам из i-го окна такая, что всевершины, за исключением последней соответствуют размещению работы без закрытияокна. Т.е., фактически, данная последовательность состоит из размещенных работ,упорядоченных по времени открытия окна, в которое они размещены.

Вершины,соответствующиеработам,неразмещеннымвSP,добавляютсявконецпоследовательности SL в произвольном порядке (добавляется одна произвольная вершинаиз двух). При этом в последовательности SL присутствует только одна вершина,соответствующая каждой работе.Докажем совпадение списков работ в окнах расписания SP* и расписания SP поиндукции.17.

Базис индукции: Т.к. все вершины, соответствующие работам из первого окна,стоят в последовательности вершин друг за другом, не прерываютсявершиной с закрытием окна, то они будут размещаться в одно и то же окно.Т.к. исходное расписание является корректным, это возможно без нарушенияусловий корректности 1-5. Следовательно, списки работ в первом окне в SP и101SP* будут совпадать (поскольку список вершин, соответствующих работам изпервого окна, заканчивается вершиной с закрытием окна, в данное окно непопадут «лишние» работы). Время открытия и закрытия первого окна могутразличаться в SP* и SP, но при этом из свойств (1) и (2) следует, что S*1S1,F*1F1.18.

Шаг индукции: F*i-1Fi-1, и, следовательно (из свойства (2)), S*iSi, F*iFi; далееповторяя предыдущие рассуждения, получаем, что корректность i-го окна вSP гарантирует корректность соответствующего окна в SP* и совпадениесписка работ, размещенных в них.Неразмещенные в SP работы могут оказаться добавлены только в новые окна, т.к.последовательность вершин, соответствующих размещенным в SP работам, заканчиваетсявершиной с закрытием окна.Теорема доказана.Из утверждения теоремы также следует, что значение целевой функции длярасписания SP* не меньше, чем для SP.

Таким образом, доказано, что для любогокорректного расписания SP существует последовательность вершин графа G’ такая, чтомодифицированный алгоритм способен построить корректное расписание, по крайнеймере, не хуже данного с точки зрения целевой функции.Следствие. Если SP0 корректное оптимальное расписание для множества работ SW,то существует такая последовательность вершин SL, что модифицированный алгоритмпостроит по ней корректное оптимальное расписание. Построенное расписание будетсовпадать с расписанием SP0 по количеству размещенных в нем работ, количеству окон,по множеству работ выполняемых внутри каждого окна, но может отличаться по времениоткрытия и закрытия окон.С материалами данного раздела можно ознакомиться в работах:3.Балаханов В.А., Костенко В.А.

Способы сведения задачи построения статико-динамическогооднопроцессорного расписания для систем реального времени к задаче нахождения на графемаршрута // Программные системы и инструменты. Тематический сборник № 8, М.: Изд-вофакультета ВМиК МГУ, 2007. – С.148-156.4.Балаханов В.А., Кокарев В. Муравьиный алгоритм построения статико-динамических расписаний иисследование его эффективности// Программные системы и инструменты. Тематический сборник №8, М.: Изд-во факультета ВМиК МГУ, 2008.5.5.

Муравьиный алгоритм для решения задачи построения расписанияобменов по шине с централизованным управлениемБудет прочитан на основе материалов статей:1021. Костенко В.А. Алгоритмы построения расписаний для одноприборных систем, входящих в составсистем реального времени// Методы и средства обработки информации: Третья Всероссийскаянаучная конференция. Труды конференции. - М.: Издательский отдел факультета ВМиК МГУимени М.В. Ломоносова; МАКС Пресс, 2009. - С.245-258.2. Balashov V.V., Balakhanov V.A., Kostenko V.A., Smeliansky R.L., Kokarev V.A., Shestov P.E.A technology for scheduling of data exchange over bus with centralized control in onboard avionicssystems // Proc. Institute of Mechanical Engineering, Part G: Journal of Aerospace Engineering.

– 2010. –Vol. 224, No. 9. – P. 993–1004.1036. Алгоритмы, использующие аппроксимирующую модельцелевой функцииЭтот класс алгоритмов представляет особый интерес для задач с "дорогой" целевойфункцией.Задачивычислительнымис"дорогой"затратамицелевойнафункциейвычислениехарактеризуютсяцелевойфункции.большимиСоответственноэффективные алгоритмы должны минимизировать количество ее вычислений длянахождения оптимального решения X или поддерживать возможность параллельнойработы.Дляпростотыизложенияалгоритмовоптимизации,использующихаппроксимирующую модель целевой функции будем полагать, что вычисление функцийограничений g i (x) не требует существенных затрат ресурсов (хотя все рассмотренныениже подходы могут быть обобщены и на этот случай).

Также будем предполагать, чтовсе оптимизируемые параметры представимы в виде вещественных чисел (т.е. что областьS  R N ).поискаРасширениярассмотренныхнижеметодовнаслучайразнотипных/нечисловых оптимизируемых параметров в принципе возможны, однако, какправило, они не обладают достаточной общностью и строятся индивидуально для каждогокласса задач.В процессе работы алгоритма с использованием аппроксимирующей модели всевычисленные значения целевой функции (т.е. пары вида ( X , f ( X ))заносятся вспециальную базу данных (БД). БД используется для построения модели M целевойфункции f ( X ) на некотором подмножестве S cur множества S допустимых значенийпараметров (на текущей области поиска). Модель M аппроксимирует значение функцииf ( X ) на всем множестве S cur , а также, при необходимости, оценивает достоверностьаппроксимации (математическое ожидание ошибки аппроксимации) и производныефункции f ( X ) .

В процессе работы алгоритма модель периодически уточняется вместе спополнением БД. На основании анализа модели M алгоритм принимает решения обуточнении текущей области поиска S cur , и о направлении поиска.Базовая схема алгоритмов оптимизации с использованием аппроксимирующеймодели может быть представлена следующим образом.1. Спланировать и провести серию начальных испытаний (вычислений значенийфункции f ( X ) ) на множестве точек X T  { X i }, i  1,2,..., sinit .Инициализировать БД:T  { ( X, f(X)}, X  X T .1042.

Установить текущую область поиска S cur  S .3. Построить аппроксимационную модель M целевой функции f ( X ) на основанииинформации, содержащейся в БД T. Модель M состоит из:~ функции оценки значения целевой функции f ( X ) : S cur  R[опционально] функции оценки мат. ожидания квадрата ошибки2~аппроксимации ~ 2 ( X )  E f ( X )  f ( X ) , ~ 2 ( X ) : S cur  R[опционально] функции оценки значений производных целевой функции.4. Выбрать точку следующего испытания посредством решения т.н. задачиоптимизации на модели:min I ( X , M , T )X S curg i ( X )  0,i  1,2,..., k(6.1.)Здесь, I ( X , M , T ) - функция выбора точки след. испытания. Значение I ( X , M , T )позволяет оценить (используя модель М), насколько желательным является получениеинформации о значении "настоящей" целевой функции в точке X  S cur в плане решенияисходной задачи (1).

Вычисление значения I ( X , M , T ) не требует вычисления значения"настоящей" целевой функции f ( X ) . Различные способы построения I ( X , M , T ) будутрассмотрены ниже. Точку, доставляющую минимум функции I ( X , M , T ) , далее будемобозначать как X * .5. Вычислить значение "настоящей" целевой функции f ( X ) в точке X * .6. Дополнить БД : T  T  (X * , f(X * ))7. Уточнить область поиска S cur .8.

Обновить модель M с учетом дополненной БД и уточненной области поиска.9. Если не выполнен критерий завершения, перейти к шагу 4.10. Решением задачи (1) положить наилучшее из решений, сохраненных в БД:X min  arg min f ( X ) , f min  min f ( X ) .X TX TНа практике производительность алгоритма оптимизации с использованиемаппроксимирующей модели сильно зависит от выбора его параметров, в число которыхвходят:алгоритм планирования начальных испытаний;метод построения модели M;105стратегия выбора точки след. испытания (определяющая способ построенияфункции I ( X , M , T ) );алгоритм решения задачи оптимизации на модели (6.1.);алгоритм уточнения области поиска;критерий завершения.При удачном выборе параметров алгоритм часто бывает способен найти решениезадачи (1.1.) с удовлетворительной точностью за небольшое (порядка несколькихдесятков) число итераций, и, соответственно, небольшое число вычислений целевойфункции.Планирование начальных испытаний.

На данном этапе основной целью являетсяполучение наиболее общей информации о целевой функции, достаточной для построениямодели M "в первом приближении". Значение целевой функции вычисляется в небольшомчисле точек, распределенных по области S. На практике для выбора точек X i , в которыхдолжна быть вычислена целевая функция, часто используются следующие подходы:случайное распределение заданного числа точек по области S;покрытие области S равномерной сеткой;распределение точек X i с использованием классических методов планированияэксперимента (план "латинского гиперкуба", частичный/полный факториальныйплан, и т.д.).Метод построения модели M. Для построения модели М могут использоватьсямногие известные алгоритмы аппроксимации или интерполяции непрерывных функций(например, аппроксимация квадратичной формой, аппроксимация c помощью нейроннойсети). Результаты измерений целевой функции, занесенные в БД T  { ( X i , f(X i )}, X i  X T ,используются для формирования обучающей выборки (множества узлов аппроксимацииили интерполяции).Дляуспешногопримененияалгоритмаоптимизациисиспользованиемаппроксимирующей модели необходимым условием является адекватность моделицелевой функции.

Поэтому в процессе работы алгоритма необходимо постоянно (накаждой итерации) контролировать качество модели M. Для этого применяются такиеметоды, как использование тестового подмножества обучающей выборки, кросс-проверка.При невозможности обеспечить достаточное качество оценки в рамках выбранного методапостроения модели, алгоритм выполняет одну из следующих корректирующих операций:"переключение" на использование альтернативного метода построения модели;нелинейная трансформация множества значений целевой функции;106проведение серии дополнительных испытаний (вычислений целевой функции) сцелью получения дополнительной информации о целевой функции.Стратегия выбора точки следующего испытания. Наиболее распространенныеподходы описаны ниже.~Простейшая стратегия заключается в поиске точки, для которой оценка f ( X )значения целевой функции минимальна.

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

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