birmaga.ru
добавить свой файл

  1 2 3

Сетевой оператор - это ориентированный граф, обладающий следующими свойствами [2-5]:

а) в графе отсутствуют циклы;

б) к любому узлу, который не является источником, имеется хотя бы один путь от узла-источника;

в) от любого узла, который не является стоком, имеется хотя бы один путь до узла-стока;

г) каждому узлу-источнику соответствует элемент из множества переменных или из множества параметров ;

д) каждому узлу соответствует бинарная операция из множества бинарных операций;

е) каждой дуге графа соответствует унарная операция из множества унарных операций.

Вычисления по сетевому оператору включают три этапа. На первом этапе находим узел, который имеет выходящие дуги, но не имеет ни одной входящей дуги. На втором этапе выполняем унарную и бинарную операции. Унарная операция соответствует дуге, выходящей из найденного узла. В качестве аргумента унарной операции используем значение, которое хранится в найденном узле. Бинарная операция соответствует узлу, в который дуга входит. В качестве первого аргумента бинарной операции используем либо единицу, либо результат последнего вычисления, который хранится в данном узле. В качестве второго аргумента используем результат вычисления унарной операции. На третьем этапе исключаем узел и дугу из графа. Найденный узел исключаем в том случае, если этот узел не является узлом-стоком и не имеет ни одной выходящей дуги. Дугу исключаем во всех случаях, если операция, которая соответствует данной дуге, выполнена.

Этапы вычислений выполняем до тех пор, пока в сетевом операторе не останутся только узлы-стоки, в которых хранятся результаты вычислений. Выполнение унарной операции согласно выходящей из узла дуге, осуществляем только в том случае, если в узел, из которого данная дуга выходит, не входит ни одна дуга.


Для любой формулы, заданной в графической записи, можно построить сетевой оператор, вычисления по которому будут давать те же результаты, что и вычисления по формуле.

Введем в рассмотрение целочисленные векторы. Вектор номеров входных переменных , где - номер узла-источника в сетевом операторе, с которым связана переменная , . Вектор номеров параметров , где - номер узла-источника в сетевом операторе, с которым связан параметр , . Вектор номеров выходных переменных , где - номер узла сетевого оператора, который соответствует выходной переменной , - количество выходных переменных.

Для формального описания сетевого оператора в матрице смежности сетевого оператора вместо единиц, которые соответствуют дугам графа, записываем соответствующие номера унарных операций из множества , а на диагонали – соответствующие номера бинарных операций из множества .


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

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

Для удобства вычислений и хранения промежуточных результатов введем вектор узлов , размерность которого равна количеству узлов сетевого оператора. Зададим начальные значения вектору узлов. Если узел является источником, то в качестве начального значения возьмем соответствующий элемент из множеств переменных или параметров , , , .

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

После задания начального значения вектора узлов , , последовательно проходим в матрице сетевого оператора все строки по столбцам. Если встречаем в строке в столбце не нулевой элемент, то выполняем сначала унарную операцию, номер которой определяем по элементу матрицы сетевого оператора, над значением элемента вектора узлов. Затем над результатом вычислений выполняем бинарную операцию, номер которой определяем по элементу матрицы сетевого оператора, причем первым аргументом бинарной операции является последнее значение элемента вектора узлов. Результат вычислений присваиваем элементу вектора узлов , где - значение -й компоненты вектора узлов после прохождения -й строки, .


После прохождения всех строк матрицы сетевого оператора результат вычислений будут содержать компоненты вектора узлов, которые определяются по номерам выходных переменных , .

Из-за верхнего треугольного вида матрицы сетевого оператора компонента вектора узлов не будет изменяться, если пройдена строка , поэтому справедливо соотношение , .

В третьем разделе приведена разработка генетического алгоритма для решения задачи синтеза на основе метода сетевого оператора.

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

Для использования принципа базисного решения сначала необходимо определить малые вариации графа сетевого оператора [2]. Каждая вариация должна изменять граф сетевого оператора, сохраняя его свойства. Малые вариации графа приведены в таблице 3.1.

Таблица 3.1.

Малые вариации графа


Название малой вариации

Номер вариации

Замена унарной операции на дуге графа

0

Замена бинарной операции в узле графа


1

Добавление дуги

2

Удаление дуги

3

Удаление узла

4

Добавление узла

5


Все вариации формально могут быть описаны целочисленным вектором вариаций из четырех компонент , где - номер вариации, - номер строки матрицы сетевого оператора, - номер столбца матрицы сетевого оператора, - номер бинарной или унарной операции, в зависимости от номера вариации.

При реализации генетического алгоритма на основе принципа базисного решения в качестве хромосомы используем упорядоченный набор векторов вариаций.

Помимо основных параметров генетического алгоритма, количества хромосом, поколений и скрещиваемых пар, количество векторов вариаций в хромосоме является еще одним настраиваемым параметром. Этот параметр называем длиной хромосомы. Большая длина хромосомы увеличивает вариабельность решений, но усложняет вычисления

Чтобы обеспечить достаточную вариабельность решений при малой длине хромосомы необходимо периодически изменять базисное решение. Базисное решение целесообразно менять после нескольких поколений, которые являются основными циклами генетического алгоритма. Для смены базисного решения введем еще один настраиваемый параметр генетического алгоритма – эпоха.


Эпоха – это количество поколений в генетическом алгоритме, при котором базисное решение гарантированно остается неизменным.

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

Для решения задачи (1.1)-(1.4) на основе сетевого оператора необходимо определить конструктивные множества: переменных, параметров, унарных и бинарных операций. Затем установить размерность сетевого оператора, определить множество вариаций и выбрать базисные решения. После этого можно построить генетический алгоритм для поиска решений.

Выбор множества переменных , 1, , для практических задач не вызывает особой сложности. В большинстве случаев переменными могут являться наблюдаемые и измеряемые компоненты вектора состояний объекта.

Для выбора множества параметров , , , достаточно определить лишь мощность этого множества, т.к. значения параметров подбираются в процессе синтеза. Большое количество параметров увеличивает разнообразие решения, но усложняет процесс оптимизации. Как правило, число параметров не превосходит число переменных.

Множество бинарных операций ,

1121, 1, 1, , в подавляющем большинстве случаев содержит две операции – умножение и сложение. Эти операции являются коммутативными, ассоциативными и для них определены единичные элементы.


Определение множества унарных операций , 11, 1, 1, , является наиболее сложным. Набор конкретных операций подбирается для решаемой задачи. В множество следует ввести тождественную операцию.

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

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

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


При генерации вектора вариаций используем только вариации, которые не влияют на размерность сетевого оператора, т.е. вариации 0-3.

Вторая часть хромосомы влияет на значения параметров системы управления и представляет собой битовую строку, закодированную кодом Грея, , где , .

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

Первоначально создаем популяцию из хромосом, состоящих из структурной и параметрической частей. Для каждой хромосомы вычисляем значения функций приспособленности, которые соответствуют функционалам.

Для того, чтобы вычислить значения функционалов, из структурной части каждой хромосомы получаем матрицу сетевого оператора , , где - матрица сетевого оператора базисного решения.

Полученная матрица сетевого оператора и вектор параметров определяют одно из возможных решений (1.4) рассматриваемой задачи синтеза .


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

Условное множество Парето представляет собой совокупность возможных решений или хромосом , , для которых не существует хромосом, более лучших в смысле отношения Парето.

Чтобы построить условное множество Парето на популяции хромосом, введем характеристику, расстояние от текущей хромосомы до условного множества Парето

, (3.1)

где .

В качестве функции приспособленности для оценки решения используем расстояние до условного множества Парето. Хромосомы, имеющие нулевое расстояние, принадлежат условному множеству Парето

. (3.2)

Для репродукции хромосом в популяции случайно отбираем пару и . Определяем вероятность скрещивания по условию


, (3.3)

где .

Если условие (3.3) выполняется, то производим скрещивание хромосом. Случайно выбираем точки скрещивания

Обмениваем части хромосом и получаем четыре новых хромосомы–потомка , , , .

В хромосомах , сохраняется структура родителей, но изменяется параметрическая часть. В хромосомах , изменяются и структурная и параметрическая части.

Для новых хромосом выполняем операцию мутации с заданной вероятностью . Вычисляем значения функционалов для новых хромосом , , .

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


Если расстояние до условного множества Парето у наихудшей хромосомы больше, чем у новой хромосомы , то заменяем наихудшую хромосому на новую , , .

Пересчитываем расстояния до условного множества Парето для всех хромосом в популяции ,.

Алгоритм завершает свою работу после выполнения заданного числа основных циклов, поколений. Результатом работы является условное множество Парето, построенное на конечной популяции хромосом.

Алгоритм также может завершить свою работу, если условное множество Парето не изменяется на протяжении заданного количества поколений.

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

, (3.4)

где - номер наилучшей хромосомы в популяции, - наилучшее значение критерия , .

В четвертом разделе рассмотрена задача синтеза управления для стабилизации углового движения космического аппарата.


Математическая модель объекта управления имеет следующий вид

, (4.1)

, (4.2)

, (4.3)

где , , - угловые координаты спутника, , , - управляющие воздействия.

Для системы (4.1)-(4.3) заданы начальные условия , , .

Процесс стабилизации должен сопровождаться минимальным расходом топлива и отсутствием вращения спутника относительно начала координат

, (4.4)

. (4.5)

Рассматривались две постановки задачи. В первой постановке на управление были наложены ограничения , а во второй - ,


Для проверки робастности полученных решений, систем управления, для одной из систем проводилось моделирование с другими начальными значениями , , .

Для решения задачи использовались следующие параметры генетического алгоритма: размерность популяции – 200, количество скрещиваемый пар в поколении – 64, количество поколений – 50, число поколений между эпохами – 10, длина структурной части хромосомы – 12, количество критериев – 2, число постоянных параметров – 3, количество бит под целую часть параметра – 2, количество бит под дробную часть параметра – 6, вероятность мутации – 0,8, шаг интегрирования – 0,001, шаг печати – 0,01, время переходного процесса – 1, размерность матрицы сетевого оператора – 16, мощность множества констант – 3, мощность множества переменных – 3, размерность вектора управления – 3.

В качестве базисного решения использовалась линейная обратная связь по угловым координатам

,

где , , ,

Множества переменных и параметров имели следующий вид , . Векторы номеров входных переменных, параметров и выходных переменных имели следующие значения , , .


Матрица базисного сетевого оператора имела следующий вид

.

Н

а рис. 1 представлено множество Парето для задачи (4.1)-(4.5).





Рис. 1. Условное множество Парето

Было проведено моделирование для разных решений, принадлежащих условному множеству Парето. Для одного из полученных решений были найдены следующие значения критериев качества , и параметров , , .

Матрица сетевого оператора для данного решения имела вид

.

Более крупным шрифтом отмечены элементы, значения которых отличаются от значений в базисной матрице.

По матрице сетевого оператора получено управление в виде

, , (4.6)

где , , , , ,


, , , , , , , , , , , .

Начальное значение вектора узлов матрицы имел следующий вид .

Для проверки робастности синтезированной системы управления было проведено моделирование для управления (4.6) со значениями начальных условий, увеличенных на 10%. Результаты эксперимента показали, что полученная нелинейная система управления обеспечивает стабилизацию космического аппарата, и значения функционалов изменились не более чем на 12%. Система является робастной по отношению к изменению начальных условий.

Расчеты проводились на персональном компьютере с процессором AMD Athlon 64, с тактовой частотой 1ГГц. Время расчета составило не более 10 минут.


<< предыдущая страница   следующая страница >>