Многокритериальный синтез позиционного управления

1.1 Метод многокритериального позиционного управления на основе генетического программирования (МПУ-ГП)

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

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

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

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

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

y1=eq1x1sin (q2x2+q3).

В выражении q1, q2, q3 — параметры, а x1, x2 — переменные. Для символьной записи элементов математического выражения используем подстроки, состоящие из префиксного символа и номера. Для обозначения параметра используем подстроку вида qn, где символ q указывает на то, что подстрока описывает параметр, nномер параметра.

Для описания переменной используем подстроку xm, где префикс x указывает на описание переменной, m — номер переменной.

В математическом выражении выделим унарные и бинарные операции, соответственно с одним и двумя аргументами. Для описания унарной операции используем подстроку вида uj, где префикс u указывает на унарную операцию, числовой символ j — номер унарной операции. Для описания бинарной операции используем подстроку bi, где b — префикс бинарной операции, I — номер бинарной операции.

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

y1 = b1u1u2b1q1x1u3b2b1q2x2q3,.

где b1 — операция умножения, b2 — операция сложения, u1 — унарная операция вычисления экспоненты, u2 — унарная операция обращения знака или унарный минус, u3 — операция вычисления синуса.

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

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

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

Например, имеем еще математическое выражение.

y2 = (q1x1+x2)+sin (x1+q2).

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

y2=b2b1b2b1q1x1x2b2b1q1x1x2u3b2x1q2.

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

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

y3 = e-q1x1sin (q1x1+x2),.

y4 = (q2x2+q3)(q1x1+x2)+sin (x1+q2).

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

y3=b1u1u2b1q1x1u3b2b1q1x1x2,.

y4=b2b1b2b1q2x2q3b2b1q1x1x2u3b2x1q2.

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

При выполнении операции мутации в генетическом программировании меняют унарные или бинарные операции или параметры и переменные.

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

Для генетического программирования характерны следующие недостатки:

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

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