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

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

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

ComplexSystems, 1991, v.5, p.31.), (Nix A., Vose M.D. Ann. Math. and Artificial Intelligence, 1991, v.5, N 79, p.88.)],чтостроится система детерминированных уравнений, которая определяет вероятность того,что каждая конкретная строка будет присутствовать в популяции в момент времени t cучетом вероятностей для момента времени t-1. Динамика работы ГА может быть описанавероятностями появления каждой строки (вектором размера 2l на каждой итерации ГА).Поскольку мутация является линейной операцией, она описывается матрицей размера2l2l, операция скрещивания является двухместной и описывается тензором размера2l2l2l. Следует также отметить, что Марковские модели не учитывают конечный размерпопуляции и предполагают выбор родителей в операции скрещивания лишь всоответствии с равновероятным выбором.МакроскопическийуровеньописаниядинамикиработыГА.Переходнамакроскопический уровень описания динамики работы ГА заключается в описании ГА втерминах статистических свойств популяции, т.е.

вместо описания каждой возможнойстроки, описываются выделенные статистические свойства, характеризующие популяциюв целом [(Golberg D.E., Deb K., Clark J.N. Complex Systems, 1992, v.6, p.333.),( Bulmer M.G. MathematicalTheory of Quantitative Genetics. Cambridge: Claredon Press, 1980.)].Таким образом, динамика системы63с огромным числом степеней свободы сводится к динамике системы всего с несколькимипараметрами, которая может быть легко рассчитана или смоделирована.

Этот подход небудет исследовать свойств первичных элементов популяции, что затрудняет оценку еготочности. При использовании данного подхода возникают также нетривиальные задачиправильного выбора макропараметров (позволяющих потерять как можно меньшеинформации о популяции) и оценки влияния операций ГА на эти макропараметры.Известен подход к анализу динамики поведения ГА, основанный на принципахстатистической механики [Шапиро Дж., Рэттрэй М., Прюгель-Беннетт А.

Применение методовстатистической механики для изучения динамики генетического алгоритма// Обозрение прикладнойматематики. Серия “Методы оптимизации”. Эволюционные вычисления и генетические алгоритмы,1996.,Т.3, выпуск 5. - С.670-687.].Он позволяет изучать динамику поведения ГА при решениипростейших комбинаторных задач (цитируя авторов: “игрушечных задач”). Типдопустимой целевой функции в этих задачах жестко ограничен.

Целевая функция являетсяlфункцией от величины h: F=F(h), где h    wi xi ,wi - фиксированные весовыеi 1коэффициенты, xi - i-й бит строки с номером  в очередной популяции. Этот подходоснован на использовании статистической механики для расчета ожидаемых результатов(значений макропараметров: четыре семиинварианта h и корреляции между строками меры сходства строк) применения операций ГА, а также для расчета их отклонений отожидаемых значений.

Для описания макропараметра h используются четыре первыхсемиинварианта: матожидание, дисперсия, семиинварианты, связанные с асимметрией иэксцессом. Все они усредняются по строкам текущей популяции, а не по всемдопустимым строкам. То есть, они будут изменяться во времени вместе с популяцией.Если требуется информация, отличная от той, которая содержится в макропараметрах, тоона может быть получена из макропараметров методом максимума энтропии.

Данныйподход может оказаться наиболее перспективным для анализа динамики поведения ГАпри решении задач комбинаторной оптимизации, если он будет расширен для задач, вкоторых на целевую функцию не накладываются столь жесткие ограничения.4.3. Модификации генетических алгоритмов4.3.1. Алгоритмы, использующие функции значимости фрагментовДанный подход к построению генетических алгоритмов предполагает выделениефрагментов решения и введение для них функций значимости. Значение функциизначимости фрагмента является оценкой вклада фрагмента в значение функции64выживаемости. Значения параметров операций мутации и скрещивания фрагментовопределяются в зависимости от значений функций значимости фрагментов решения, т.е.

вэтом алгоритме вероятности мутации и скрещивания различных фрагментов различны.Скрещивание старается сохранить фрагменты решения с высоким значением функциизначимости, т.е. операция скрещивания является консервативной, что необходимо дляпринципиальной работоспособности генетического алгоритма. Мутация является неконсервативной операцией и позволяет изменять фрагменты решения. Сказанное вышепозволяет избежать решения проблемы выбора такой кодировки решения и выборазначений параметров операций мутации и скрещивания, что бы могли существоватьстроительные блоки. Напомним, что генетический алгоритм может работать, только еслив ходе работы алгоритма образуются строительные блоки.

В данном разделе покажемприменение этого подхода для построения алгоритмов распознавания участков фазовыхтраекторий динамических систем по обучающей выборке с помощью генетическихалгоритмов.Задача распознавания участков фазовых траекторий динамических системРассмотрим систему, которая окружена набором датчиков. Будем считать, чтодатчики, окружающие систему, опрашиваются с одинаковой постоянной частотой.Фазовая траектория X в пространстве показаний датчиков представляет собойпоследовательные измерения всех датчиков системы:X  ( x1 , x2 ,..., xn )где xi  x (t 0  i  ) – это точка в многомерном пространстве показаний датчиков (вфазовой плоскости);1– частота опроса датчиков.Состояние системы характеризуется показаниями датчиков, окружающих ее.

Современем система может изменять свое состояние. Последовательные изменениясостояния системы будем называть ее поведением. Состояния системы можно разделитьна два базовых типа:Штатное состояние. Это такое состояние наблюдаемой системы, при котором онастабильно выполняет заложенные в нее функции.Аварийное состояние. Это такое состояние системы, при котором она не выполняетчасть заложенных в нее функций или в скором времени гарантированно перестанетих выполнять.65Поведение системы, которое переводит ее из штатного состояния в аварийное,будем называть нештатным (или аварийным) поведением.

Может существовать несколькоклассов нештатного поведения, приводящих к аварийному состоянию системы.Будем считать, что каждому классу нештатного поведения соответствует некотораяхарактерная траектория X Anom , такие траектории будем называть эталонными.Пусть число классов нештатного поведения системы равно L. Обозначим:W  {w}ww1L  {0} – множество ответов, где 0 – соответствует штатному поведениюсистемы, w – соответствует нештатному поведению под номером w из L возможных.Участки траекторий, соответствующие различным классам нештатного поведения,могут входить в анализируемую траекторию X в искаженном относительно эталонныхтраекторий виде. Можно выделить следующие типы искажений:искажения по амплитуде,искажения по времени,наложение шума.Рисунок 4.1. Пример искаженных траекторий.Под искажением траектории по амплитуде будем понимать изменение абсолютныхзначений точек траектории, без изменения числа отсчетов.

Под искажением траектории повремени будем понимать изменение числа отсчетов, на которых определена траектория,то есть добавление в траекторию новых отсчетов или удаление из нее уже существующих.На рисунке показаны траектории, которые искажены по амплитуде и времени друготносительно друга.Задача распознавания нештатного поведения состоит в следующем:Дано:Наблюдаемая многомерная траектория X.Набор из L классов нештатного поведения системы, для каждого из которых заданаэталонная траекторияlX Anom.Ограничения на полноту и точность распознавания:e1  const1 и e2  const 266где:e1 – число ошибок распознавания первого рода;e2 – число ошибок распознавания второго рода;const1 , const2 – заданные числовые ограничения.Требуется с учетом ограничений на полноту и точность провести распознаваниенештатного поведения в работе системы.Под ошибкой распознавания первого рода будем понимать такую ошибкураспознавания, когда алгоритм распознал вхождение траектории нештатного поведения внаблюдаемую траекторию на тех отсчетах, на которых не наблюдается нештатногоповедения.

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

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