Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

На правах рукописи

Бураков Сергей Васильевич

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

Специальность 05.13.01 - Системный анализ, управление и обработка информации (космические и информационные технологии)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Красноярск - 2012

Работа выполнена в Институте математики ФГАОУ ВПО Сибирский федеральный университет, г. Красноярск

Научный руководитель:  доктор технических наук, профессор

Семенкин Евгений Станиславович

Официальные оппоненты:  Сенашов Сергей Иванович

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

Миркес Евгений Моисеевич

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

Ведущая организация:       ФГБОУ ВПО Национальный

исследовательский Томский политехнический университет

Защита состоится 18 мая 2012 г.  в 14 ч. на заседании диссертационного совета Д 212.249.02 в ФГБОУ ВПО Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева по адресу 660014, г. Красноярск, проспект имени газеты Красноярский рабочий, 31

С диссертацией можно ознакомиться в научной библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева

Автореферат разослан л  апреля 2012 г.

Ученый секретарь диссертационного совета

доктор физико-математических наук                                А.А.Кузнецов

Общая характеристика работы

Актуальность. Обыкновенные дифференциальные уравнения (ОДУ) являются теоретической основой многих процессов, протекающих в науке и технике. Такие процессы отражаются в физике, химии, биологии и многих других областях науки. Особенно часто о решении ОДУ приходится говорить применительно к теории колебаний и теории автоматического управления. Такие процессы как колебание маятника, процесс распада радиоактивного вещества, процессы изменения численности популяции биологических видов хорошо описываются ОДУ. Решение ОДУ представляется важной задачей для многих сфер деятельности человека, а также играет важную роль в познании окружающего мира.

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

Решить ОДУ численно означает нахождение частного решения ОДУ, по поставленной задаче Коши или краевой задаче. Решение получают, используя ЭВМ, что означает получение приближенного результата. Этот результат записывается в виде последовательности (таблицы) чисел, представляющих аргументы и соответствующие значения искомой функции. Результат решения в виде таблицы чисел может значительно затруднять анализ и дальнейшее его применение. Определение условий сходимости и устойчивости метода может накладывать дополнительные ограничения на процесс решения.

Вариационное исчисление - область, связанная с ОДУ, описывающая методы решения вариационных задач. Вариационная задача состоит в поиске экстремума заданного функционала. Вариационные задачи широко используются в решении практических задач. Решение вариационной задачи может быть получено с использованием уравнения Эйлера, являющегося необходимым условием существования экстремума функционала. Уравнение Эйлера получают из заданного функционала, оно представляет собой ОДУ, что в совокупности с границами интервала (и значениями подынтегральной функции), на котором задан функционал, дает краевую задачу. Решение этой краевой задачи может быть экстремумом функционала, что требует проверки. Краевая задача на практике решается чаще всего численными методами, о недостатках которых говорилось выше.

Таким образом, методы решения ОДУ и вариационных задач, применяемые традиционно, часто (а на практике особенно часто) не дают желаемого результата - функции в символьном виде, причем единственной. Однако, если решение таких задач рассматривать как процедуру поиска оптимального бинарного дерева, представляющего собой математическую функцию, то для такого поиска можно использовать алгоритмы генетического программирования (ГП), широко и успешно применяемые в области интеллектуального анализа данных. Нужно отметить, что поиск такого дерева, состоящего из многих узлов и содержащего вещественные коэффициенты, является сложной оптимизационной задачей. Метод, использующий алгоритм ГП, в качестве результата может выдавать точные символьные решения, если таковые существуют. То есть такой метод позволяет обойти недостатки традиционных способов решения, а следовательно разработка алгоритмов ГП для поиска символьных решений задач Коши, краевых задач и задач вариационного исчисления является актуальной научно-технической задачей.

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

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

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

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

3. Разработать подходы для применения таких алгоритмов при решении различных типов задач теории ОДУ и вариационного исчисления при разных условиях.

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

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

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

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

1. Разработан новый эволюционный метод на базе алгоритма генетического программирования для получения на заданном множестве функций символьных решений задачи Коши для ОДУ.
2. Разработан новый гибридный метод приближенного решения задачи Коши для ОДУ, состоящий в применении численного метода для получения приближенного решения и алгоритма генетического программирования, решающего задачу символьной регрессии на основе этих результатов, для получения символьного решения.
3. Разработан новый эволюционный метод на базе алгоритма генетического программирования для получения на заданном множестве символьных решений функций краевых задач для ОДУ.
4. Разработан новый эволюционный метод на базе алгоритма генетического программирования для решения задач вариационного исчисления в символьном виде.

Теоретическая значимость работы  состоит в том, что разработанный подход позволяет автоматически получать символьные решения задач Коши и краевых задач для ОДУ и вариационных задач с различными типами уравнений (подынтегральных функций). При этом такой метод обладает преимуществами как аналитического метода решения (находит решения в символьном виде), так и численного метода решения (способен решать те задачи, которые не решаются в квадратурах или не представимы элементарными функциями), а также позволяет решать задачи, для которых не выполнены условия единственности решения или непрерывности решения по входным данным.

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

Реализация результатов работы

По итогам работы реализованы 4 программные системы, зарегистрированные в Роспатенте, а также 2 программные реализации для  кластерных ЭВМ.

Результаты диссертационной работы включены в отчеты по госбюджетным НИР Б8.5541.2011 Развитие теоретических основ автоматизации математического моделирования физических систем на основе экспериментальных данных, Б1.7.08 Разработка теоретических основ решения задач автоматизации проектирования распределенных многопроцессорных вычислительных комплексов интеллектуального анализа данных в режиме реального времени и НК-409П/49 Разработка устойчивого гибридного генетического алгоритма для определения кристаллических структур химических соединений из данных порошковой дифракции мероприятия 1.2.1 Федеральной целевой программы Научные и научно-педагогические кадры инновационной России на 2009Ц2013 годы.

Основные защищаемые положения

1. Алгоритм генетического программирования решения задачи Коши для ОДУ позволяет получить на заданном множестве функций точное символьное решение, если оно существует.
2. Гибридный метод приближенного решения задачи Коши для ОДУ позволяет получить требуемый результат при меньших затратах вычислительных ресурсов.
3. Алгоритм генетического программирования решения краевых задач для ОДУ позволяет получить на заданном множестве функций точное символьное решение, если оно  существует.
4. Алгоритм генетического программирования для решения задач вариационного исчисления позволяет получить на заданном множестве функций символьное решение, если оно существует.

Публикации по теме диссертации опубликовано 18 работ, в том числе 2 в изданиях из перечня ВАК и 4 свидетельства о регистрации компьютерных программ в Роспатенте.

Апробация работы. Результаты работы были доложены на 7 Всероссийских, 4 Международных и одной зарубежной конференциях.

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

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

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

Аналитический метод решения задачи Коши представляет последовательность математических операций, целью которых является получение класса функций, удовлетворяющих заданному дифференциальному уравнению. Решение ОДУ называют сведением  к квадратурам или интегрированием. Затем, учитывая начальные условия, из полученного класса функций исключаются все решения кроме одного. Заранее предполагается, что требования теорем существования и единственности удовлетворены. В случаях когда задача не обеспечивает единственность решения, каждое из решений рассматривается отдельно. Возможно решить аналитически лишь небольшой класс задач с определенными типами ОДУ. Типы ОДУ и методы решения хорошо известны из теории ОДУ. Хотя даже в случае когда существует определенный метод решения конкретного ОДУ (т.е. задача сводится к квадратурам) при вычислении могут возникнуть сложности с определением функции, являющейся значением интеграла. В силу того, что далеко не каждое уравнение можно свести к квадратурам, и не каждый интеграл может быть представлен элементарными функциями, получить символьную запись решения ОДУ (а затем и задачи Коши для последнего) возможно лишь для узкого класса задач. Практические задачи редко приводятся к задачам с теоретически детерминированными подходами к решению.

На практике задачи Коши для обыкновенных дифференциальных уравнений решаются численными методами с использованием (иногда мощных) ЭВМ. Численный метод решения состоит в получении числовой таблицы значений, представляющих функцию. Для этого должна быть построена разностная схема. Затем должна быть доказана сходимость метода, должен быть определен порядок точности, что может накладывать дополнительные ограничения на метод решения.  Получение производных в точках предполагает использование конечно-разностных оценок (с определенным порядком точности). Интегралы получают численно, используя формулы прямоугольников, трапеций, Симпсона и др. Численный метод работает, если решение задачи существует, единственно и непрерывно зависит от входных данных. В случаях когда какое-то из этих условий не выполняется, численное решение возможно лишь с использованием специальных схем. Более того, даже когда решение численным методом не требует дополнительных усилий результат в виде таблицы значений во многом неудобен для обработки и может сильно ограничивать дальнейший анализ и применение. Однако за отсутствием других подходов численные методы получили широкое распространение (особенно с развитием вычислительной техники).

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

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

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

               F(x, y, y, y, Е , y(n))=0                                                (1)

и начальные условия        y (x0)=Y0, y (x0)=Y0, Е, y(n-1) (x0)= Y0(n-1).        (2)

Требуется найти функцию (в символьном виде), которая удовлетворяла бы заданному уравнению и начальным условиям.

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

Второй вариант - гибридный метод решения - предполагает предварительное решение  задачи Коши одним из численных методов решения ОДУ. Для решения был использован метод Рунге-Кутта четвертого порядка точности. Численный метод решения дает не аналитический результат, а числовую таблицу его представляющую. Чтобы найти решение задачи в символьном виде, также предлагается использовать  алгоритм генетического программирования. В таком случае решение задачи Коши для ОДУ (используя численное решение) сводится к задаче символьной регрессии.

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

1. Инициализация начальной популяции (случайным образом).
2. Оценка пригодности каждого индивида.
3. Адаптация индивидов.
4. Применение генетических операторов к имеющимся индивидам для получения новой популяции.
5. Если критерий остановки не выполнен, то переход ко второму этапу.

На первом этапе случайным образом создается начальная популяция. Каждый индивид - это бинарное дерево, состоящее из элементов функционального (+, -, *, /, sin, cos, exp, log) и терминального множества (вещественные коэффициенты, компоненты вектора независимой переменной). Эти множества определяются поставленной задачей и могут быть расширены. Глубина первоначального дерева (деревьев начальной популяции) задается пользователем и определяется сложностью поставленной задачи, а также доступностью ресурсов. Слишком малая глубина дерева дает маленький набор вариантов для дальнейшего процесса поиска решения, слишком большая - существенно замедляет работу алгоритма. Представление определенного решения в виде бинарного дерева, вообще говоря, может быть не единственно.

На втором этапе производится оценка индивидов. Чем лучше индивид удовлетворяет поставленной задаче: заданному уравнению (1) и начальным условиям (2), тем большую пригодность он должен иметь. Оценка должна характеризовать решение (индивида) качественно - чем меньше погрешность по уравнению и начальным условиям, тем лучше, и количественно: при одинаковом качестве решения лучше тот индивид, который имеет более короткую запись. Для оценки индивида одним из самых простых способов является вычисление среднеквадратического отклонения. Формулу по которой вычисляется пригодность можно записать следующим образом:

       ,                                                (3)                ,                (4)

где Fit(Pk) - значение функции пригодности k-го индивида, E(Pk) - ошибка аппроксимации, вычисляемая по всем точкам выборки (N - объем выборки), K1 - коэффициент штрафа за сложность дерева, D(Pk) - число вершин дерева Pk, К2 - коэффициент штрафа за начальные условия (n - количество начальных условий), - заданные начальные условия, - производная j-го порядка в точке x0 (), |Pk()| - отклонение (например, среднеквадратическое) функции F из выражения (1) от нуля, получаемое при подстановке решения Pk в ОДУ в выбранных точках () - точки из интервала могут быть выбраны равномерно, случайно или каким-либо специальным образом. При этом вычисление пригодности включает вычисление производных которые входят в уравнение. Производные можно определять как численно - строить разностные оценки производных в точке, так и "аналитически" - строить бинарное дерево, в котором закодирована производная искомой функции. Способ вычисления производной должен выбираться в зависимости от поставленной задачи, а также доступности ресурсов.

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

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

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

y'' = Ц2 sin(x), y(0)=0.0, y(0)= 2.0,

получается решение

y(x)=1.999611801x - 0.3330926297x3 + 0.01662624753x5 - 0.0003886344121x7 + 0.440310-5x9.

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

Таблица 1. Примеры решенных задач

№	Уравнение F(x,y, y...)=0	Начальные условия	Точное решение	Полученные алгоритмом решения
1	xy+(x+1) y=0	1.000 [0;3]	(x+1)exp(-x)	(x+1)exp(-1x)
2	x3(y-x)-y2=0	0.000078285 [0.01;0.9]	x2-x2/(log(x))	(x-x/(log(x))) x
3	xy-2y-2x4=0	2.0000 [-1;1]	x2+x4	((xx) ((xx)+1))
4	y+ytg(x)-sec(x)	1.0000 [0;6]	sin(x)+cos(x)	(sin(x)+cos(x))
5	2x(x2+y)-y	4.139327065 [-1.4;1.4]	exp(x2)-x2-1	exp(xx)-(xx+1)
6	xy+(x+1) y-3x2exp(-x)	2.718281828 [-1;5] 4.126402996 [-1;5]	x2/(exp(-x)) xy=(x3+1)exp(-x)	(((x)/(exp(x)))(x)) (1/x+x2)/exp(x)
7	(y-1/x+y/y)	5.4545454 [1.2;10]	2x/(x2-1)	x2/(x2-sin(64.400))
8	(x2+3log(y))y-xy	0.003606563 [-1.5;1.5]	exp(x3)-x2	exp((xx)(cos(-34.600)+x))
9	y'2+xy-y2-xy	0.135335283 [-2;2] 4.389056099 [-2;2]	Exp(x) exp(-x)+x-1	exp(x) x+1+exp(-x)
10	y2-2xy-8xx	8.0 [-2;2]	2x2	2x2+sin(exp(-29))
11	(((y) (y)) +((y)-(x (y))))	6.00 -6.00 [-1;5] -4.333 4.000 [-4;4]	x2- 4 x+1 x3/12+1	(1+(x(x-4))) 1.00+0.083579x3

При решении полученные результаты можно разделить на три категории: символьно-точные решения - (((cos(0.000))+(x))/(exp(x)))),  которые имеют короткое представление и не требуют приближенного вычисления, а преобразования элементарны; символьные условно-точные -  (((x)+(sin(-4.700)))/(exp(x)))), которые имеют короткую форму записи, но требуют некоторых приближенных вычислений; символьные приближенные - (((((40.4)((1.1)+(x)))+(-4.1)))/(exp((3.7)+(x)))), которые имеют сложное представление (не приводятся элементарными преобразованиями).

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

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

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

	Прямой алгоритм	Гибридный алгоритм
Средний процент точных решений	64	39
Средний процент условно-точных решений	22	7
Средний процент приближенных решений	14	54
Среднее количество поколений ГП	117	250
Среднее время работы (мин.)	147	26
Количество точных решений для наиболее сложной задачи	2	0
Количество приближенных решений для наиболее сложной задачи	4	10

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

По итогам работы алгоритма можно отметить, что, во-первых, алгоритм ГП способен получать как точные, так и приближенные решения (в символьном виде) в зависимости от поставленной задачи. При получении точных решений задачи Коши для ОДУ алгоритм в большинстве случаев находит точные решения или решения, легко приводимые к точным. При решении гибридным методом требуется меньше вычислительных ресурсов, но решения имеют большую погрешность. При решении прямым методом алгоритм работает дольше, но надежность получения приемлемого решения выше. При решении прямым методом несущественным является требование единственности решения. Для задач, имеющих несколько решений, проходящих через заданную точку, достаточно добавить дополнительный компонент в функцию пригодности. Кроме того, предлагаемый алгоритм позволяет получать символьные представления для задач, не имеющих решения, представимого элементарными функциями, а также получать разложения функций в ряд Тейлора.

В третьей главе рассматривается вариационная задача в общем виде. Пусть задан функционал в виде:

.                                        (5)

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

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

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

или                        (6)

и граничные условия                        

y (x0)=Y0, y (xN)=YN.                                        (7)

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

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

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

,                                                (8)

,        (9)

где Fit(Pk) - значение функции пригодности k-го индивида, E(Pk) - ошибка аппроксимации, вычисляемая по всем точкам выборки (N - объем выборки), K1 - коэффициент штрафа за сложность дерева, D(Pk) - число вершин дерева Pk, К2 - коэффициент штрафа за граничные условия, - заданные граничные условия, - значение искомой функции в точке xj, |Pk()| - отклонение от нуля (например, среднеквадратическое) функции F из уравнения (2), получаемое при подстановке решения Pk в ОДУ в выбранных точках () - точки из интервала могут быть выбраны равномерно, случайно или каким-либо специальным образом.

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

               ,                

где E(Pk) - значение функционала на заданном интервале (остальные обозначения соответствуют формулам (8), (9)). В случае если функционал представлен в виде (5), значение E(Pk) может быть определено численно, например, по формуле Симпсона на заданном интервале, то есть последовательно находятся значения функции и производных на заданном множестве, затем численно находится значение интеграла.

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

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

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

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

Таблица 3. Примеры решенных задач вариационного исчисления

№	Функция	Граничные условия	Точное решение	Полученные алгоритмом решения
1	(y')2+12xy	-3.0; 5.0 [-2;2]	x3-2x+1	((((xx)-2.0) x)-(-1.0))
2	(y')2-y2	-0.7; -0.28 [-3;3]	1.5sin(x)+0.5cos(x)	61.9/(-39.1) sin(log(31.900)+x)
3	(y')2+2yy'-16y2	-1.076; 1.076 [-1.7708 0.585398]	1.5sin(4x))	((sin((4.000) (x))) (1.500))
4	xy'+(y')2	-4.0;-1.0 [-2;4]	-x2/4+x-1	(((x ((-4)+x))+4)/(-4.0))
5	(y')2x2+y'	4.0; -0.667 [0.4;6]	2/x-1	(((2.000)-(x))/(x))
6	(y')2x+y y'	-2.3;1.79 [0.1;6]	ln(x)	(log(x))
7	(y')2-2xy	1.0;-1.0 [-3;3]	(7x-x3)/6	(((x45.5)+((xx) (x (-6.500))))/39.000)
8	(y')2-y2+4ycos(x)	0.141;0.7 [-3;3]	(x+2)sin(x)	log(exp(sin(x) (2.0+x)))
9	(y')2-2xy	-0.81 2.43 [-2.5;3.5]	13x-x3/6+2	((((x/(-6.0)) xx)+((x + (2.0))-(x/(-6.0))))+x)
10	(y')2+y2+2yex	-4.19;-0.43[-1;5]	1.85914xex -0.5 + 0.5e-x	((-4.1)-((((x/((exp(-17.9)) (-24.4)+cos(3.9 )))-exp(sin(17.4))) exp(0.3))/exp(x)))+log(36.6)

Решения полученные алгоритмом ГП были разбиты на три группы аналогично подходу для решения задачи Коши. Результаты были проанализированы и усреднены. Суммарная информация представлена в таблице 4.

Таблица 4. Результаты анализа полученных решений вариационных задач

	Прямой метод	Метод Эйлера
Средний процент точных решений	35	62
Средний процент условно-точных решений	25	25
Средний процент приближенных решений	40	13
Среднее количество поколений ГП	127	78
Среднее время работы (мин.)	475	321
Количество точных решений для наиболее сложной задачи	0	10
Количество приближенных решений для наиболее сложной задачи	100	30

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

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

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

Первая программная система представляет собой инструмент для решения задачи Коши. Уравнение (1) и начальные условия (2) являются входными данными, наряду с интервалом в котором задача должна быть решена. Возможны два способа решения: одна программа позволяет решать задачу прямым методом, вторая программа - гибридным. Программы предоставляют схожий интерфейс. Окно программы состоит из основной вкладки с данными, необходимыми для работы алгоритма ГП, и дополнительной вкладки, содержащей схематичное представление графика решения, для удобства оценки получаемого решения непосредственно на этапе выполнения программы. При этом при решении прямым методом уравнение должно быть задано в символьном виде, а начальные условия в виде вектора вещественных чисел. Основные элементы управления программой предоставляют возможность запуска и остановки алгоритма, оценки (тестовой) функции относительно уравнения начальных условий, а также дополнительных факторов (например, сложность представления функции). В основном окне программы выводится и результат  решения задачи Коши в символьном виде.

Вторая программная система позволяет получать точные и приближенные решения вариационной задачи (5). Одна программа представляет решение задачи, используя необходимое условие (уравнение Эйлера), вторая осуществляет поиск экстремума функционала напрямую. Функционал задается символьным выражением, необходимы также границы интервала. Для решения с помощью уравнения Эйлера необходимы граничные условия. Окно программы для решения вариационной задачи аналогично окну программы для решения задачи Коши: функционал и дифференциальное уравнение представлены в символьном виде, задаются границы интервала (а также граничные условия для метода Эйлера), присутствует возможность настройки алгоритма ГП, отслеживаются лучшие решения, в дополнительной вкладке можно визуально оценить получаемые решения.

Программные системы, реализующие алгоритмы ГП и методы их применения для поставленных задач, были протестированы на различных задачах. По итогам тестовых запусков для различных задач Коши и вариационных задач можно сделать вывод о том что данный инструмент представляет эффективное средство решения таких задач. Для большинства задач были получены приемлемые результаты на начальных этапах работы программ, то есть для получения схематичного представления решения достаточно, чтобы алгоритм ГП отработал несколько десятков поколений. Для достижения большей точности требовалось значительно больше времени. Эту особенность (в общем характерную для алгоритмов ГП) можно дополнительно объяснить и спецификой задач: вычисление производных, интегралов.

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

Программы, реализующие параллельную работу алгоритмов ГП, были написаны на распространенном языке С++ с использованием стандарта MPI 2.0. Для распараллеливания был использован самый простой вариант, когда одно ядро (управляющее) осуществляет последовательные операции, а остальные  ядра - параллельные операции. Применительно к предложенной схеме алгоритма ГП управляющее ядро осуществляет инициализацию, запускает генетические операторы и осуществляет вывод. Оставшиеся ядра осуществляют вычисление пригодности и оптимизацию решений. Такая схема позволяет ограничить количество запрашиваемых ядер (максимальное их число) количеством индивидов в популяции. Учитывая, что вычисление пригодности в ГП самая дорогостоящая по затратам ресурсов операция, ускорение при распараллеливании эквивалентно числу ядер (эффективность параллельного алгоритма близка к единице).

Такая реализация дает возможность решения поставленных задач на распределенных вычислительных системах. В качестве распределенной системы  может быть, как простая локальная сеть (с условием наличия сети стандарта Fast Ethernet), так и мощные вычислительные ЭВМ кластерного типа. Алгоритм тестировался на кластерном компьютере ИВМ СО РАН - 14 лезвий (узлов) по 8 ядер: запрашивалось как правило 16, 24 или 32 ядра. Время работы сокращалось на порядок не только из-за количественного увеличения вычислительных ресурсов, но и качественно - в силу различия процессоров. Это давало возможность увеличивать точность получаемого результата и надежность работы алгоритмов.

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

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

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

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

4. Разработан гибридный метод решения вариационной задачи: решение краевой задачи с использованием уравнения Эйлера и прямой метод решения с использованием только заданного функционала.

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

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

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

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

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

Публикации по теме диссертации 

Статьи в ведущих рецензируемых научных журналах и изданиях

1. Бураков С.В. Решение задачи Коши для обыкновенных дифференциальных уравнений методом генетического программирования / С.В. Бураков, Е.С. Семенкин // Журнал СФУ - "Математика и физика"  - Том 4, вып. 1. - 2011 - С. 61-69.
2. Бураков С.В. О решении вариационной задачи методом генетического программирования / С.В. Бураков, Е.С. Семенкин // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнёваю - №5 (38). - 2011. - С. 19-24.

       Публикации в сборниках трудов конференций

3. Burakov, S., Semenkin E. Solving Variational and Cauchy Problems with Genetic Programming Algorithms. In: Proceedings of the 5th International Conference on Bioinspired Optimization Methods and their Applications (BIOMAТ2012). - Bohinj, Slovenia, 2012.
4. Бураков С.В. Алгоритм генетического программирования как возможный метод решения обыкновенных дифференциальных уравнений и их систем / С.В. Бураков // Сборник трудов VII Всероссийской научно-практической конференции Молодежь и современные информационные технологии. - Томск: Издательство СПБ Графикс, 2009 - Часть 1. - С. 95-97.
5. Бураков С.В. Алгоритм генетического программирования для решения обыкновенных дифференциальных уравнений и их систем в символьном виде / С.В. Бураков // Сборник докладов X международной научно-технической конференции Кибернетика и высокие технологии XXI века. - Т. 1. - Воронеж: ВГУ, 2009. - С. 338-345.
6. Бураков С.В. О решении задачи Коши для обыкновенных дифференциальных уравнений и их систем методом генетического программирования в символьном виде. / С.В. Бураков // Информационные технологии и математическое моделирование. Материалы VIII Всероссийской научно-практической конференции с международным участием. Томск: Издательство Томского университета, 2009 - Часть 2. - С. 193 - 198.
7. Бураков С.В. Алгоритм генетического программирования как метод для решения обыкновенных дифференциальных уравнений и их систем в символьном виде. / С.В. Бураков //  Материалы трудов конгресса по интеллектуальным системам и информационным технологиям "AIS-ITТ09". Научное издание в 4-х томах. М: Физматлит.  2009 г. - Т. 1. - С. 9 - 17.
8. Бураков С.В. Получение аналитических решений дифференциальных уравнений и их систем методом генетического программирования / С.В. Бураков // Труды шестой Всероссийской научной конференции с международным участием "Математическое моделирование и краевые задачи". Часть 4. Самара: издательство Самарского государственного технического университета, 2009 - Часть 4. - С. 25-28.
9. Бураков С.В. О возможностях алгоритма генетического программирования для задачи решения обыкновенных дифференциальных уравнений и их систем в символьном виде / С.В. Бураков // Материалы всероссийской конференции Математическое моделирование и вычислительно-информационные технологии в междисциплинарных исследованиях. - Иркутск: Институт динамики и теории управления СО РАН, 2009.
10. Бураков С.В. О нахождении точных и приближенных символьных решений обыкновенных дифференциальных уравнений и их систем методом генетического программирования. / С.В. Бураков // Сборник научных трудов по материалам международной научно-практической конференции "Перспективные инновации в науке, образовании, производстве и транспорте С2009". - Одесса: Черноморье, 2009 - Т.4. - С. 40 - 47.
11. Бураков С.В. Алгоритм генетического программирования для задачи символьного решения обыкновенных дифференциальных уравнений. / С.В. Бураков // Информационные технологии и математическое моделирование. Материалы VII Всероссийской научно-практической конференции с международным участием. Издательство Томского университета, 2008 - Часть 2 - С. 89 - 94.
12. Бураков С.В. Решение обыкновенных дифференциальных уравнений в символьном виде методом генетического программирования. / С.В. Бураков // Решетневские чтения. Материалы XII Международной научной конференции, посвященной памяти генерального конструктора ракетно-космических систем академика М.Ф. Решетнёва. Красноярск: СибГАУ, 2008.  - С. 258 - 260.
13. Бураков С.В. Трудоемкость получения аналитических решений произвольных обыкновенных дифференциальных уравнений и перспективы применения алгоритма генетического программирования / С.В. Бураков // Наука. Технологии. Инновации. Материалы всероссийской научной конференции. - Часть 1. - Новосибирск: НГТУ, 2008. - С. 101-103.
14. Бураков С.В. Аналитические решения обыкновенных дифференциальных уравнений в науке и образовании и их получение методом эволюционного программирования. / С.В. Бураков // Современные информационные технологии в науке, образовании и практике. Материалы VII Всероссийской научно-практической конференции с международным участием. Оренбург 2008 - С. 286 - 293.

Зарегистрированные программные системы

15. Бураков С.В. Алгоритм генетического программирования для приближенного аналитического решения задач вариационного исчисления. / С.В. Бураков, Е.С. Семенкин. М.: Реестр программ для ЭВМ, 2012 - №  гос. рег. 2012612021.
16. Бураков С.В. Алгоритм генетического программирования для приближенного аналитического решения задачи Коши для обыкновенных дифференциальных уравнений. / С.В. Бураков, Е.С. Семенкин. М.: Реестр программ для ЭВМ, 2012 - №  гос. рег. 2012612022.
17. Бураков С.В. Алгоритм генетического программирования для приближенного аналитического решения краевой задачи для обыкновенных дифференциальных уравнений. / С.В. Бураков, Е.С. Семенкин. М.: Реестр программ для ЭВМ, 2012 - №  гос. рег. 2012612111.
18. Бураков С.В. Алгоритм генетического программирования для приближенного аналитического решения задачи Коши для систем обыкновенных дифференциальных уравнений. / С.В. Бураков, Е.С. Семенкин. М.: Реестр программ для ЭВМ, 2012 - №  гос. рег. 2012612023.

Бураков Сергей Васильевич

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

Автореферат

Подписано к печати 2012 Формат 60х84/16

Уч. изд. л. 1.0 Тираж 100 экз. Заказ № ________

Отпечатано в отделе копировальной и множительной техники СибГАУ.

660014, г. Красноярск, пр. им. газ. Красноярский рабочий, 31

   Авторефераты по всем темам  >>  Авторефераты по техническим специальностям