4.2 Грамматическая эволюция

В данной дипломной работе был применён метод грамматической эволюции для решения задачи синтеза, и для реализации этого использовался язык программирования Python [16] в среде Eclipse [17].

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

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

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

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

Эклипс (Eclipse) - это свободная интегрированная среда разработки модульных кроссплатформенных приложений, которая поддерживает язык Python.

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

Таблица. 3. Продукционные правила для синтеза системы управления

В Таблице 3 представлено множество продукционных правил в форме БНФ для реализации генетического алгоритма в данной работе.

Множество состоит из пяти нетерминалов, где expr - это выражение, которое можно разложить на 4 вида:

1) expr op expr - операция из множества op, которая находится между двумя выражениями.

2) fun1(expr) - функции принимающие один аргумент.

3) fun2(expr,expr) - функции принимающие два аргумента.

4) var - множество терминалов, которое состоит из переменных.

Множество op состоит из любых возможных математических операторов.

Множество var состоит из переменных xk[0], xk[1] и параметров q1 и q2, где xk[0] - это , xk[1] - это

, (19)

коэффициенты функции управления.

Множество fun1 и fun2 состоят из следующих функций:

1) sqr соответствует;

2) sign соответствует ;

3) atan соответствует ;

4) minus соответствует ;

5) sqrtX соответствует ;

6) sin соответствует ;

7) step соответствует ;

8) plfun1 соответствует

9) plfun2 соответствует

10) divX соответствует делению с некоторыми ограничениями.

Пример работы ГЭ в проекте:

Вектор чисел = [17,14,40,55,23,32,45,57,11,8]

С помощью продукционных правил в таблице 3 можно получить функцию по следующей схеме:

Рис. 8.

После получения функции sin(q2 * minus(xk[0])) и замены параметров и значений переменных, функция ограничивается множеством допустимых решений.

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

Эффективность по Парето

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

Таким образом, по словам самого Парето: «Всякое изменение, которое никому не приносит убытков, а некоторым людям приносит пользу (по их собственной оценке), является улучшением». Значит, признаётся право на все изменения, которые не приносят никому дополнительного вреда.

Множество решений, оптимальных по Парето, называют «множеством Парето».

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

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

Рис. 9.

Круглые точки на графике показывают возможные решения (лучшие решения те, которые меньшие по значению).

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

Точки А и В находятся на границе и ни одна из них не доминирует над другой.

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