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

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

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

Алгоритмы распознавания нештатного поведения динамическихсистемустойчивыекнелинейнымискажениямфазовыхтраекторийсистемы//ТрудыМеждународной научно-практической конференции «Передовые информационные технологии,средства и системы автоматизации и их внедрение на российских предприятиях» AITA-2011. – М.:Институт проблем управления им.

В. А. Трапезникова РАН, 2011. – С. 897–905.3.D. Kovalenko, V. Kostenko A Genetic Algorithm for Construction of Recognizers of Anomalies inBehaviour of Dynamical Systems// Proceedings of the IEEE Fifth International Conference on Bio-InspiredComputing: Theories and Applications, IEEE Press, China. 2010. - pp.258-263.834.Коваленко Д.С. Методы и программные средства обучения алгоритмов распознавания участковфазовых траекторий: дис. кан. физ.-мат. наук: 05.13.11/ МГУ им. М.В. Ломоносова. – М.: 2011. –168с.4.4 Генетический алгоритм для решения задачи о рюкзакеБудет прочитан на основе материалов раздела 3.1.

учебного пособия [Скобцов Ю.А.Основы эволюционных вычислений. Донецк.: ДонНТУ, 2008.- 326с.].4.5. Генетический алгоритм для решения задачи определения минимальнонеобходимого числа процессоров и построения расписания выполненияфункциональных задач со временем выполнения не превышающимзаданный директивный срок4.5.1. Математическая формулировка задачиЗадачу построения расписания как задачуусловнойоптимизацииможносформулировать следующим образом (см. раздел 1.4.1.).Дано: H(PR)=(P,  )- модель программы, T=f(HP,HW)- функция вычисления временивыполнения расписания HP на архитектуре HW (целевая функция), T dir - директивныйсрок выполнения программы.Требуется построить: HP– расписание выполнения программы такое, что:min M ( HP, HW )HPT  f ( HP, HW )  T dirHP  HP1*5Здесь M ( HP, HW ) - число процессоров, на котором выполняется расписание.Функциявычислениявременивыполнениярасписанияможетбытьзаданаваналитическом виде или в виде имитационной модели.4.5.2.

Кодирование решенийВ данном разделе рассмотрим математические структуры для параметрическогопредставления расписаний, соответствующие алгоритмы восстановления расписания поего параметрическому представлению не нарушающие ограничений 1-5, введем операцииизменения параметров, докажем возможность задания любого допустимого расписанияпараметрическим представлением с использованием приоритетов и соответствующихбыстрых алгоритмов восстановления и введем способ кодирования решений на основепараметрического представления расписаний.Параметрическое представление расписаний с использованием приоритетов84Расписание задается вектором YN+K :KYN  K  ( YPR i )i 1YPR i  ( YE i  YP )NiYP  ( YP j )j 1KK - число процессов в H, Ni – число рабочих интервалов в i-ом процессе, N   N i i 1число рабочих интервалов в H, Y  ( y1  y 2 ) - операция построения вектораY  ( y1, y 2) из параметров y1 и y 2 .ПараметрYE i  [1,  , K ]  Zсодержитномерпроцессора,выполняются рабочие интервалы i-го процесса, т.е.

параметрынаYEкоторомоднозначноопределяют распределение рабочих интервалов по SP (привязку). Параметры YE могутпринимать значения от 1 до K. Если значения всех параметров YE равны, то все рабочиеинтервалы выполняются на одном процессоре, если все значения различны, то рабочиеинтервалы каждого процессора выполняются на своем процессоре. В силу ограничения 5,максимальное число не пустых процессоров равно числу процессов K в H.ПараметрыYP  [1,  , L]  Zиспользуютсяалгоритмомвосстановлениярасписания (определение отношения полного порядка в каждом SPi) в качествеприоритетов рабочих интервалов.При данном способе представления расписания число целочисленных переменныхравно N+K.Для описания алгоритма восстановления, множество рабочих интервалов разобьемна три подмножества:P  P1  P 2  P3 .

P1 - множество рабочих интерваловраспределенных в SP (определен порядковый номер рабочего интервала) алгоритмомвосстановления на предыдущих шагах; P2 - множество рабочих интервалов, у которых всепредшественники принадлежат P1; P3 - множество рабочих интервалов, у которых хотябы один из предшественников не принадлежит P1.Алгоритм восстановления полного порядка рабочих интервалов в SP (A1).1. Начальное разбиение множества P:P1=;85P 2  { p j : j , k  [1,  , N ]  jk  }-множестворабочихинтерваловвHбезпредшественников;P3  { p j : p j  P \ P 2} - множество рабочих интервалов в H, у которых имеютсяпредшественники.2.

Находим в P2 рабочий интервал с наименьшим значением параметра YP (еслитаких интервалов более одного, то выбираем интервал с наименьшим номером):размещаем его в конец соответствующего списка SP (номер списка определяетсязначением параметра YE );переносим его из P2 в P1.3.

Проверяем P3 с целью возможности переноса рабочих интервалов в P2:если есть рабочие интервалы, у которых все предшественники принадлежат P1, топереносим их в P2.4. Если P2, то к п.2, иначе завершить работу.Утверждение1.АлгоритмA1восстановлениярасписанияпоегопараметрическому представлению YN+K получает расписание HP  HP1* 5 , и расписаниевосстанавливается однозначно.Доказательство. Ограничение 5 не нарушается в силу того, что все рабочиеинтервалы, принадлежащие одному и тому же процессу, имеют одно и тоже значениепараметра YE и будут размещены (п.2 алгоритма) в один и тот же список.Ограничения 1,2 не нарушается в силу того, что каждый рабочий интервалпереносится из P2 в соответствующий SP, причем перенос осуществляется лишь один разв ходе работы алгоритма.Выполнение ограничений 3,4 и однозначность восстановления расписаниядокажем показав, что алгоритм A1 получает на каждом шаге допустимое частичноерасписание и это расписание получается однозначно. Будем представлять расписание вярусной форме максимальной высоты.

Расписание, полученное после размещения первоговыбранного из P2 рабочего интервала, всегда удовлетворяет ограничениям 3,4.МножествоP2определенооднозначно(содержитрабочиеинтервалыбезпредшественников), выбор рабочего интервала из P2 однозначен и его порядковый номерв соответствующем SP определен однозначно, равен 1 (п.2 алгоритма). Пусть частичноерасписание, полученное после размещения (j-1) рабочих интервалов допустимо иоднозначно.

Покажем, что на j-м шаге рабочий интервал выбирается и размещаетсяалгоритмом A1 в расписание однозначно и полученное частичное расписание86удовлетворяет ограничениям 3,4. Множество P2 на j-м шаге алгоритма A1 определяетсяоднозначно рабочими интервалами, размещенными в расписание на предыдущих шагах.Выбор рабочего интервала из P2 однозначен и его порядковый номер в соответствующемSP определен однозначно, максимальный порядковый номер рабочего интервала в данномSP плюс 1 (п.2 алгоритма).

Данный рабочий интервал размещается на j-й ярус. Посколькувсе его предшественники (в соответствии с определением множества P2) ужераспределены на предыдущих шагах на ярусы с меньшими номерами, то отношениячастичного порядка заданное в H не нарушается (выполняется ограничение 3).Ограничение 4 выполняется в силу того, что полученное промежуточное расписаниепредставлено в ярусной форме. Таким образом, после выполнения алгоритмом A1 N шаговполученное расписание будет удовлетворять ограничениям 3,4 и порядковые номерарабочих интервалов в списках определяются однозначно.Теорема 2. Любое допустимое расписание HP  HP1* 5может быть заданопараметрическим представлением с использованием приоритетов (YN+K) и однозначновосстановлено алгоритмом A1, если допустимая верхняя граница L значений параметровYP больше или равна числу рабочих интервалов (LN).Доказательство.

Расписания могут отличаться друг от друга привязкой ипорядком рабочих интервалов (смотри раздел 3). Любая допустимая привязка(распределение рабочих интервалов по SP) может быть задана соответствующимизначениями параметров YE  [1,  , K ] и однозначно восстановлена алгоритмом A1.Возможность задания любого допустимого порядка для фиксированной привязкиможно доказать методом математической индукции. Для любого произвольно выбранногоSPk можно показать, что для рабочего интервала с порядковым номером равным 1,значение параметра YP для этого рабочего интервала можно выбрать таким образом, чтоон может иметь любой допустимый порядковый номер в SPk, который однозначнополучает алгоритм A1 (место возможного размещения рабочего интервала определяетсяразмещением его последователей в HP с использованием ярусной формы HP).

Далееполагаем, что для (i-1) рабочих интервалов из списка SPk с наименьшими порядковыминомерами,можнополучитьлюбыедопустимыевариантыпорядка,выбираясоответствующий набор значений параметров YP . Можно показать, что для рабочегоинтервала с порядковым номером равным i, значение параметра YP для этого рабочегоинтервала можно выбрать таким образом, что он может иметь любой допустимыйпорядковый номер в SPk, который однозначно получает алгоритм A1 (место возможного87размещения рабочего интервала определяется размещением его предшественников ипоследователей в HP с использованием ярусной формы HP).Выбор значений параметров YP , позволяющих получить требуемое расписаниеалгоритмомвосстановленияA1,можносделать,проведясоответствующуютопологическую сортировку вершин требуемого расписания.

Поскольку, в P2 максимумможет находиться N рабочих интервалов, то для получения любого допустимого вариантапорядка может потребоваться максимум N различных значений параметров YP , т.е.может потребоваться полная топологическая сортировка.Кодирование решений выполняется следующим образом:Y  Ytask  Y priority – закодированное решение,KYtask   YEi 1Ki– привязка,NiYpriority   YPi 1 j 1j– приоритеты,Здесь K – число процессов в H, Ni – число рабочих интервалов в i-ом процессе,KN   N i – число рабочих интервалов в H,  – оператор конкатенации строк.i 1ПараметрYE i  [1,  , N ]  Zсодержитномерпроцессора,выполняются рабочие интервалы i-го процесса, т.е.

параметрыYEнакоторомоднозначноопределяют распределение рабочих интервалов по SP (привязку) и число процессоров вВС. Параметры YE могут принимать значения от 1 до K. Если значения всех параметровYEравны, то все рабочие интервалы выполняются на одном процессоре, если всезначения различны, то рабочие интервалы каждого процесса выполняются на своемпроцессоре. В силу ограничения 5, максимальное число непустых процессоров равночислу процессов K в H.Параметры YP j  Z используются алгоритмом восстановления расписания (дляданного представления расписания – определение отношения полного порядка в каждомSPi) в качестве приоритетов рабочих интервалов.Операции преобразования решенияПри параметрическом представлении расписания с использованием приоритетовоперации преобразования решения могут быть введены как операции изменения значенийпараметров YE и YP :881) параметрыYEмогут принимать целочисленные значения в диапазонеYPмогут принимать целочисленные значения в диапазоне[1,…,K],2) параметры[1,…,L],3) количество изменяемых параметров может изменяться от 1 до N+K.Операциипреобразованиярешений,удовлетворяющиеусловиям1-3прииспользовании алгоритма восстановления A1, будут получать решения удовлетворяющиеограничениям на корректность расписаний 1-5, что следует непосредственно изутверждения 1.

Из теоремы 2 следует, что данные операции преобразования решения иалгоритм восстановления A1 позволяют получить любой допустимый вариант решения.4.5.3. Операции генетического алгоритмаОперация селекции.Предложенная в работе [Костенко В.А., Смелянский Р.Л., Трекин А.Г. Синтез структурвычислительныхсистемреальноговремениПрограммирование, 2000., №5, С.63-72.]сиспользованиемгенетическихалгоритмов//комбинированная операция селекции позволяетсочетать преимущество схемы пропорциональной селекции и схемы рулетки.комбинированномвариантеоперациидлявычисленияцелогочислаВпотомковиспользуется схема пропорциональной селекции, а для распределения остатка – схемарулетки.

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

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