Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

CONTROL SYSTEM PROBLEM SOLUTION BY VARIATIONAL GENETIC PROGRAMMING METHOD

Ibadulla S.I. 1 Diveev A.I. 2 Sofronova E.A. 1
1 Peoples Friendship University of Russia
2 Institution of Russian Academy of Science Dorodnicyn Computing Centre of RAS
We examine the problem of synthesis of control systems, where we need to find the control as a function of the space coordinates of the object´s state. To solve the problem it is proposed to use a new method of variational genetic programming. A description of the method of variational genetic programming is given. In contrast to the classical method of genetic programming in a new variational method for genetic programming all genetic operations are performed on sets of vectors describing small variations of possible solutions. Small variations in genetic programming are defined and a data structure as an integer vector to describe a small variation is proposed. To describe a possible solution there proposed to use an ordered set of vectors of the two components, the first one of which indicates the number of arguments to a function, and the second one indicates the function index. To describe a small variation a three components´ vector there used. The first component indicates the index of variation, the second part sets the points of variation, and the third component indicates the function index, if it is necessary while realizing the variation. There is a numerical example of the synthesis of mobile robot controlling system under spatial constraints conditions.
genetic programming
the method of variation of the basis solutions
control systems synthesis

Введение

Задача синтеза системы управления требует для своего решения нахождения многомерной функции, описывающей зависимость управления от координат пространства состояний объекта. Одним из эффективных численных методов ее решения является метод сетевого оператора [1-3]. По сравнению с другими численными методами символьной регрессии, методом генетического программирования [4, 5], методом грамматической эволюции [6] или методом аналитического программирования [7], использует при поиске принцип малых вариаций базисного решения. Это позволят ввести метрику на пространстве математических выражений, ограничить область поиска в этом пространстве и определить направление поиска, задав успешное базисное решение близкое к оптимальному решению. Чем лучше разработчик на основе опыта и результатов исследования задачи задал базисное решение, тем эффективнее алгоритм поиска решения.

Метод сетевого оператора ищет математические выражения, построенные на множестве операций с одним или двумя аргументами. Это ограничение не позволяет, например, синтезировать математические выражения, включающие оператор условия. Данный оператор необходим при синтезе систем с блоком принятия решений, но его реализация требует наличия не менее трех аргументов. Метод сетевого оператора при синтезе логико-функционального управления использует функцию дискретизации с применением функции Хэвисайда и поиск решения на множестве логических операций методом логического сетевого оператора [1, 2].

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

Постановка задачи

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

, (1)

где , , , - ограниченное замкнутое множество.

Задано множество начальных состояний

. (2)

Задано терминальное состояние в форме мерного многообразия

, , (3)

где - время управления, определяемое выполнением условия (3)

Задан критерий качества управления

. (4)

Необходимо найти управление в виде

, (5)

где функция

(6)

после подстановке в систему (1) позволяет получить решение системы , которое для любого начального состояния из (2) попадает в терминальное состояние (3) при выполнении ограничений

(7)

и минимизирует функционал (4).

При численном решении задачи заменим функционал (4) суммой функционалов, вычисленных для каждого начального состояния из (2)

. (8)

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

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

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

, (9)

где

, , (10)

- функция под номером с количеством аргументов .

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

, (11)

где - количество аргументов функции, - номер функции в множестве .

Согласно принятым обозначениям для функции получаем

. (12)

Математическое выражение представляет собой упорядоченное множество кодов функций

, (13)

где , .

Рассмотрим пример. Пусть имеем математическое выражение

.

Для данного выражения имеем следующие множества функций

, , .

Запишем функции в кодах

, , ,

где - множество кодов функций множества .

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

.

Запись математического выражения в кодах имеет вид

.

При составлении кода математического выражения используем правила:

а) код первого аргумента функции следует непосредственно сразу после кода функции;

б) коды второго и следующих аргументов функции следуют после кода функции с нулевым количеством аргументов;

в) каждый код аргумента относится к ближайшей слева функции с недостающим количеством аргументов.

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

Введём понятие индекса для символа записи математического выражения. Индекс символа математического выражения (13) указывает на минимальное количество недостающих справа кодов символов

, (14)

где

, , (15)

, (16)

- количество символов в математическом выражении.

Рассмотрим малые вариации записей математического выражения (13).

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

Любая вариация записи не должна нарушать условия (15), (16). Удовлетворяющие условиям (15), (16) записи математических выражений считаем допустимыми.

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

. (17)

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

, где . (18)

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

0 – изменение значения второй компоненты кода элемента;

1 – удаление кода элемента с единичным значением первой компоненты;

2 – вставка в заданную позицию кода элемента с единичным значением первой компоненты;

3 – увеличение значения первой компоненты кода элемента на единицу и добавление в последнюю позицию кода с нулевым значением первой компоненты;

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

Для описания малой вариации используем вектор из трех компонент

, (19)

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

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

Для удобства вычислений определим нулевой вектор вариаций

.

Нулевой вектор вариаций не выполняет вариации с записью кода

.

Множество функций без аргументов разделим на подмножества переменных и параметров

, , , (20)

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

Приведем этапы генетического алгоритма

Задаём базисное решение

, , (21)

где - базисное значение вектора параметров.

Базисное решение определяем в виде вектора из строк кодов элементов

, (22)

где , .

Базисное значение вектора параметров кодируем в форме кода Грея

, (23)

где , , - число бит для целой части числа, - число бит для дробной части числа.

Каждое решение определяем с помощью набора заданной длины из векторов вариаций.

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

, (24)

где , .

Генерируем множество возможных решений в виде пар из кодов параметров и наборов векторов вариаций

(25)

Каждое возможное решение для вычисления значений функционалов преобразуем в записи кодов и векторы параметров

, (26)

где ,

. . (27)

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

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

, ,

,,

, ,

,.

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

,

, .

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

Для синтеза систем управления в большинстве случаев достаточно использовать множества из аргументов и параметров

, (28)

и следующие множества из функций с одним, двумя и тремя аргументами

, , , , , , , , , , , , , , , , , , , ,

, , (29)

, , , , ,

, , (30)

, , , , (31)

Рассмотрим пример. На рис. 1 приведена схема управления и геометрические параметры мобильного робота.

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

, (32)

, (33)

, (34)

где , - координаты центра масс мобильного робота; - угол направления вектора скорости, - обобщенный габаритный параметр мобильного робота.

Рис. 1 Схема управления мобильным роботом

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

,, , (35)

, , (36)

, , (37)

, , (38)

, , (39)

Значения управлений ограничены

, , (40)

Задано множество начальных условий

. (41)

Задано терминальное многообразие

, , . (42)

где , , - координаты терминального положения центра масс робота.

Заданы пространственные ограничения в виде логических функций

, (43)

где , , , - число препятствий.

Необходимо найти управление в форме функций от координат пространства состояний

, (44)

Управление (44) должно обеспечивать перемещение робота из любого заданного в (41) начального состояния в терминальное положение (42), удовлетворяя ограничениям (43) для углов робота за минимальное время

. (45)

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

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

Задаем базисное решение в виде

, ,

где , , , , .

С учетом множеств функций (28)-(31) запись базисного решения имеет вид

, .

Для учета ограничения использовали функцию штрафа, которая добавлялась к значению функционала (45)

, ,

где , .

При расчетах были использованы следующие параметры генетического алгоритма: количество возможных решений в начальной популяции ; число поколений 128; число попыток скрещиваний в одном поколении 512; число вариаций одного возможного решения 8; число бит для кода целой части параметра 4; число бит для кода дробной части параметра 12; число поколений между сменой базисного решения 24.

В результате синтеза было получено следующее решение

,

.
, , .

На рис. 2-4 приведены результаты моделирования синтезированной системы управления.

Рис. 2 Траектории движения центра масс объекта для различных начальных состояний

Рис. 3 Графики управлений для начального состояния , ,

Рис. 4 Траектории движения углов объекта для начального состояния , ,

Рецензенты:

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

Никульчев Е.В., д.т.н., профессор, проректор по научной работе НОУ ВПО Московский технологический институт "ВТУ", г.Москва.