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

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

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

АЛГОРИТМЫ ГЕНЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ СИМВОЛЬНОГО РЕШЕНИЯ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

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

АВТОРЕФЕРАТ

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

1 О [.Г ~>

* ' ' * " 1 ^ I

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

005042627

005042627

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

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

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

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

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

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

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

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

исследовательский Томский политехнический университет» Защита состоится 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 Международных и одной зарубежной конференциях.

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

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

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

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

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

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

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

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

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

Р(х,у, у', у", ... ,у(п))=0 (1)

и начальные условия у (х0)=У0, у' (х<))=У0,..., у*"'1' (хо)= У0(п'1). (2) Требуется найти функцию (в символьном виде), которая удовлетворяла бы заданному уравнешио и начальным условиям.

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

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

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

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

1. Инициализация начальной популяции (случайным образом).

2. Оценка пригодности каждого индивида.

3. Адаптация индивидов.

4. Применение генетических операторов к имеющимся индивидам для получения новой популяции.

5. Если критерий остановки не выполнен, то переход ко второму этапу.

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

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

Fit{Pk) =---» (3)

1 + E(Pk) + K\-D(Pk)

Е(Рк) = ±Ь±--+К2- X Ь>(Л(х0)-Г0^ > (4)

N 7=0' I

где Рк(Рк) - значение функции пригодности к-го индивида, Е(Рк) - ошибка аппроксимации, вычисляемая по всем точкам выборки (К - объем выборки), К1

- коэффициент штрафа за сложность дерева, 0(Рк) - число вершин дерева Рк, К2

- коэффициент штрафа за начальные условия (п - количество начальных

условий), Уо^ - заданные начальные условия, о) - производная j-гo

порядка в точке хо (у*-0-* (*о) = у(х^)), ¡Рк(хг-)| - отклонение (например, среднеквадратическое) функции Б из выражения (1) от нуля, получаемое при подстановке решения Р^ в ОДУ в выбранных точках (хг-) - точки из интервала могут быть выбраны равномерно, случайно или каким-либо специальным образом. При этом вычисление пригодности включает вычисление производных которые входят в уравнение. Производные можно определять как численно -строить разностные оценки производных в точке, так и "аналитически" - строить бинарное дерево, в котором закодирована производная искомой функции. Способ вычисления производной должен выбираться в зависимости от поставленной задачи, а также доступности ресурсов.

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

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

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

у" = -2 5ш(х), у(0)=0 Д у'(0)= 2.0,

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

у(х)=1.999611801 х - 0.3330926297-х3 + 0.01662624753-х5-0.0003886344121 х7+ 0.4403- 10"5-х9.

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

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

№ Уравнение Р(х,у, у'...)=о Начальные условия Точное решение Полученные алгоритмом решения

1 х у+(х+1) -у'=0 1.000 [0;3] (х+1)ехр(-х) (х+1)-ехр(-1х)

2 х3-(у"-х)-у2=0 0.000078285 Г0.01;0.9] х2-х2/(1оё(х» (х-х/(1оя(х))) X

3 х-у'-2-у-2-х4=0 2.0000 [-1;1] х2+х4 ((х-х) • ((х х)+1))

4 у'+у-1§(х)-зес(х) 1.0000 [0;6] зт(х)+со5(х) (бш(х)+С05(х))

5 2-х-(х2+у)-у' 4.139327065 [-1.4; 1.4] ехр(х2)-х2-1 ехр(хх)-(х-х+1)

6 х-у'+(х+1) -у-3-х2-ехр(-х) 2.718281828 [-1;5] 4.126402996 [-1;5] х^/(ехр(-х)) ху=(х3+1)ехр(-X) (((х)/(ехр(х)))-(х)) (1/х+х2)/ехр(х)

7 (у-1/х+у'/у) 5.4545454 [1.2;10] 2х/(х2-1) х-2/(х2-5ш(64.400))

8 (х2+31он(у))у-ху' 0.003606563 [-1.5;1.5] ехр(х3)-х2 ехр((х-х)(соз(-34.600)+х))

9 у'2+х-у-у2-х-у' 0.135335283 [-2;2] 4.389056099 Г-2;2] Ехр(х) ехр(-х)+х-1 ехр(х) х+1+ехр(-х)

10 у'2-2-х-у'-8-х-х 8.0 [-2;2] 2-х2 2х2+Бш(ехр(-29))

11 («У")' (У")) +((У')-(Х- (у")))) 6.00 -6.00 [-1;5] -4.333 4.000 [-4;4] х1- 4х+1 х3/12+1 (1+(х-(х-4))) 1.00+0.083579х

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

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

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

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

Прямой алгоритм Гибридный алгоритм

Средний процент точных решений 64 39

Средний процент условно-точных решений 22 7

Средний процент приближенных решений 14 54

Среднее количество поколений ГП 117 250

Среднее время работы (мин.) 147 26

Количество точных решений для наиболее сложной задачи 2 0

Количество приближенных решений для наиболее сложпой задачи 4 10

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

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

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

X,

\Г(х,у(х),у'(х))с1х. (5)

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

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

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

р , у ск У

■ О или Р,, — Р

ху

-Р 'У

УУ

-Р ' 'У

У У

= 0

(6)

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

У(хо)=Уо,у(хы)=Ун. (7)

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

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

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

Р»(Рк ) =-1-, (8)

1 + Е(Рк) + К1-ЩРк)

Д

Е(Рк) = -+ К2 • Вя*о) - 7о| + ) - Ч-1]. (9)

где Рп(Рк) - значение функции пригодности к-го индивида, Е(Рк) - ошибка аппроксимации, вычисляемая по всем точкам выборки (Ы - объем выборки), К1

- коэффициент штрафа за сложность дерева, В(Рк) — число вершин дерева Рь К2

- коэффициент штрафа за граничные условия, Уд > ~ заданные граничные условия, у(ху ) - значение искомой функции в точке х,-, |Рк(х,- )| - отклонение от нуля (например, среднеквадратическое) функции Б из уравнения (2), получаемое при подстановке решения Рк в ОДУ в выбранных точках (х; ) - точки из интервала могут быть выбраны равномерно, случайно или каким-либо специальным образом.

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

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

трк)=---,--

1 + Е(Рк) + К1-ЩРк) + К2- 2

у=0' Л

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

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

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

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

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

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

№ Функция Р(х,у(х),у (х)) Граничные условия Точное решение Полученные алгоритмом решения

1 (у')2+12ху -3.0; 5.0 [-2;2] х3-2х+1 ((((х'х)-2.0) -х)-(-1.0))

2 (у')2_у2 -0.7; -0.28 [-3;3] 1.5зіп(х)+0.5со5(х) 61.9/(-39.1) ■зш(1о£(31.900)+х)

3 (у'^+гуу'-ібу2 -1.076; 1.076 [1.7708 0.585398] ' 1.58іп(4х)) ((яп((4.000) • (х))) • (1.500))

4 ху'+(у')2 -4.0;-1.0 [-2;4] -хг/4+х-1 (((х- ((-4)+х))+4)/(-4.0))

5 (У')2х2+У' 4.0; -0.667 [0.4;6] 2/х-1 (((2.000)-(х))/(х))

6 (у')2х+у у' -2.3;1.79 Г0.1;б1 1п(х) 0ов(х))

7 (у')2-2ху 1.0;-1.0[-3;3] (7х-х3)/б (((х-45.5)+((х-х) ■ (х-(-6.500))))/39.000)

8 (у')2-у2+4усо5(х) 0.141 ;0.7 [-3;3] (х+2)зіп(х) І0ц(схр(5іп(х) • (2.0+х)))

9 (у')2-2ху -0.81 2.43 [-2.5;3.5] 13х-х3/6+2 ((((х/(-6.0» -х-х)+((х + (2.0))-(х/(-6.0))))+х)

10 (у')2+у2+2уе* -4.19;-0.43[-1;5] 1.85914хех-0.5 + 0.5е'х ((-4.1)-((((х/((ехр(-17.9)) ■ (-24.4)+соз(3.9 )))-ехр(5іп(17.4))) ■ ехр(0.3))/ехр(х)))+^ (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. Бураков C.B. Решение задачи Коши для обыкновенных дифференциальных уравлений методом генетического программирования / C.B. Бураков, Е.С. Семенкин // Журнал СФУ - "Математика и физика" - Том 4, вып. 1. - 2011 - С. 61-69.

2. Бураков C.B. О решении вариационной задачи методом генетического программирования / C.B. Бураков, Е.С. Семенкин И Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнёваю -№5(38).-2011. -С. 19-24.

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

3. Burakov, S., Semenkin Е. 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. Бураков C.B. Алгоритм генетического программирования как возможный метод решения обыкновенных дифференциальных уравнений и их систем / C.B. Бураков // Сборник трудов VII Всероссийской научно-практической конференции «Молодежь и современные информационные технологии». - Томск: Издательство СПБ Графике, 2009 - Часть 1. - С. 95-97.

5. Бураков C.B. Алгоритм генетического программирования для решения обыкновенных дифференциальных уравнений и их систем в символьном виде / C.B. Бураков // Сборник докладов X международной научно-технической копфереиции «Киберпетика и высокие технологии XXI века». - Т. 1. — Воронеж: ВГУ, 2009. - С. 338345.

6. Бураков C.B. О решении задачи Коши для обыкновенных дифференциальных уравнений и их систем методом генетического программирования в символьном виде. / C.B. Бураков // Информационные технологии и математическое моделирование. Материалы VIII Всероссийской научно-практической конференции с международным участием. Томск: Издательство Томского университета, 2009 - Часть 2. - С. 193 - 198.

7. Бураков C.B. Алгоритм генетического программирования как метод для решения обыкновенных дифференциальных уравнений и их систем в символьном виде. / C.B. Бураков // Материалы трудов конгресса по интеллектуальным системам и информационным технологиям "AIS-IT09". Научное издание в 4-х томах. М: Физматлит. 2009 г. - Т. 1. - С. 9 -17.

8. Бураков C.B. Получение аналитических решений дифференциальных уравнений и их систем методом генетического программирования / C.B. Бураков // Труды шестой Всероссийской научной конференции с международным участием "Математическое моделирование и краевые задачи". Часть 4. Самара: издательство Самарского государственного технического университета, 2009 - Часть 4. - С. 25-28.

9. Бураков C.B. О возможностях алгоритма генетического программирования для задачи решения обыкновенных дифференциальных уравнений и их систем в символьном виде / C.B. Бураков // Материалы всероссийской конференции «Математическое моделирование и вычислительно-информационные технологии в междиспиплипарпых исследованиях». — Иркутск: Институт динамики и теории управления СО РАН, 2009.

10. Бураков C.B. О нахождении точных и приближенных символьных решений обыкновенных дифференциальных уравнений и их систем методом генетического

программирования. / C.B. Бураков // Сборник научных трудов по материалам международной научно-практической конференции "Перспективные инновации в науке, образовании, производстве и транспорте '2009". - Одесса: Черноморье, 2009 -Т.4. - С. 40 - 47.

11. Бураков C.B. Алгоритм генетического программирования для задачи символьного решения обыкновенных дифференциальных уравнений. / C.B. Бураков // Информационные технологии и математическое моделирование. Материалы VII Всероссийской научно-практической конференции с международным участием. Издательство Томского университета, 2008 - Часть 2 - С. 89 - 94.

12. Бураков C.B. Решение обыкновенных дифференциальных уравнений в символьном виде методом генетического программирования. / C.B. Бураков // «Решетневские чтения». Материалы XII Международной научной конференции, посвященной памяти генерального конструктора ракетно-космических систем академика М.Ф. Решетнёва. Красноярск: СибГАУ, 2008. - С. 258 - 260.

13. Бураков C.B. Трудоемкость получения аналитических решений произвольных обыкновегшых дифференциальных уравнений и перспективы применения алгоритма генетического программирования / C.B. Бураков // «Наука. Технологии. Инновации». Материалы всероссийской научной конференции. - Часть 1. -Новосибирск: НГТУ, 2008. - С. 101-103.

14. Бураков C.B. Аналитические решения обыкновенных дифференциальных уравнений в науке и образовании и их получение методом эволюционного программирования. / C.B. Бураков // Современные информационные технологии в науке, образовании и практике. Материалы VII Всероссийской научно-практической конференции с международным участием. Оренбург 2008 - С. 286 - 293.

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

15. Бураков C.B. Алгоритм генетического программирования для приближенного аналитического решения задач вариационного исчисления. / C.B. Бураков, Е.С. Семенкин. М.: Реестр программ для ЭВМ, 2012 - № гос. per. 2012612021.

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

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

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

Бураков Сергей Васильевич Алгоритмы генетического программирования для символьного решения обыкновенных дифференциальных уравнений Автореферат Подписано к печати 2012 Формат 60x84/16 Уч. изд. л. 1.0 Тираж 100 экз. Заказ № //<5* Отпечатано в отделе копировальной и множительной техники СибГАУ. 660014, г. Красноярск, пр. им. газ. «Красноярский рабочий», 31

ВВЕДЕНИЕ

ГЛАВА 1. Обзор методов решения обыкновенных дифференциальных 10 уравнений и вариационных задач

1.1. Аналитические методы решения

1.2. Численные методы решения

1.3. Алгоритмы генетического программирования

Выводы

ГЛАВА 2. Алгоритм генетического программирования и методы его 33 применения для решения задачи Коши в символьном виде для обыкновенных дифференциальных уравнений

2.1. Постановка задачи и предлагаемые подходы к решению

2.2. Алгоритм генетического программирования для решения задачи 37 Коши в символьном виде

2.3. Полученные результаты

Выводы

ГЛАВА 3. Алгоритм генетического программирования и методы его 73 применения для решения в символьном виде задач вариационного исчисления

3.1. Постановка задачи и предлагаемые подходы к решению

3.2. Алгоритм генетического программирования для решения 76 краевых задач и вариационных задач

3.3. Результаты численных экспериментов 81 Выводы

ГЛАВА 4. Программная реализация алгоритмов генетического программирования для решения задач Коши, краевых задач, вариационных задач

4.1. Программная система для решения задачи Коши

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

4.3. Реализация программ для работы алгоритма ГП на 114 распределенных и кластерных вычислительных системах

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

Выводы

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

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

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

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

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

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

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

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

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 Международных и одной зарубежной конференциях.

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

Выводы

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

Решение же прямым методом дает однозначно экстремальное решение, но лишь

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

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

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

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

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

1. Айне Э.JI. Обыкновенные дифференциальные уравнения. // НТИ Украины, 1939.

2. Арнольд В.И. Обыкновенные дифференциальные уравнения. // Ижевск: УдмГУ, 2000.

3. Банди Б. Методы оптимизации. Вводный курс. / Б. Банди. // М.: Радио и связь, 1988.

4. Бахвалов Н.С. Численные методы. / Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. // М.: Наука, 1987.

5. Бибиков Ю.Н. Общий курс обыкновенных дифференциальных уравнений. // СПб, 2005.

6. Блисс Г.А. Лекции по вариационному исчислению. // М.: Издательство иностранной литературы, 1950.

7. Боресков A.B. Основы работы с технологией CUDA. / A.B. Боресков, A.A. Харламов. // ДМК Пресс, 2010.

8. Боярчук А.К. Дифференциальные уравнения в примерах и задачах. / А.К. Боярчук, Г.П. Головач. // М.: Эдиториал УРСС, 2001.

9. Вержбицкий В.М. Основы численных методов. // М.: Высш.шк. 2002.

10. Вержбицкий В.М. Численные методы. Линейная алгебра и нелинейные уравнения. / В.М. Вержбицкий. // Высш.шк., 2000.

11. Ворожейкин А.Ю. Разработка и исследование адаптивноговероятностного генетического алгоритма для многокритериальныхзадач условной оптимизации / А.Ю. Ворожейкин, Е.С. Семенкин. //127

12. Труды международных научно-технических конференций «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD-2008). М.: Физматлит, 2008, Т.1. - С. 15-21.

13. Гельфанд И. М. Вариационное исчисление. / И.М. Гельфанд, C.B. Фомин. // М., Наука, 1969.

14. Гладков JI.A. Генетические алгоритмы. / JI.A. Гладков, В.В. Курейчик, В.М. Курейчик. // Ростов-на-Дону: Росиздат, 2004.

15. Данилина Н.И. Численные методы. / Н.И. Данилина, Н.С. Дубровская, О.П. Кваша, Г.Л. Смирнов, Г.И. Феклисов. // М.: Высшая школа, 1976.

16. Зайцев В.Ф. Справочник по обыкновенным дифференциальным уравнениям. / В.Ф. Зайцев, А.Д. Полянин. // М.: Физматлит, 2001

17. Зеликин М.И. Оптимальное управление и вариационное исчисление. // М.: Едиториал УРСС, 2004.

18. Калиткин H.H. Численные методы. // М.:Наука,1978

19. Камке Э. Справочник по обыкновенным дифференциальным уравнениям. // М. :Наука:1Физматлит,;1971.

20. Канторович Л.В. Приближенные методы высшего анализа. /Л.В. Канторович, В.И. Крылов. //М.: Физматлит, 1962.

21. Карташев А.П. Обыкновенные дифференциальные уравнения и основы вариационного исчисления. / А.П. Карташев, Б.Л. Рождественский. // М., Наука, 1980.

22. Коддингтон Э.А. Теория обыкновенных дифференциальных уравнений. / Э.А. Коддингтон, Н. Левинсон // М.: Изд. иностранной лит-ры, 1958.

23. Корнев В.Д. Параллельное программирование в MPI. / В.Д. Корнев // Новосибирск: ИВМиМГ СО РАН, 2002.

24. Краснов JI. М. Вариационное исчисление. / JI.M. Краснов, Г.И. Макаренко Г. И., А.И. Киселёв // М.: Наука, 1973.

25. Круглински Д. Программирование на Microsoft Visual С++ 6.0 для профессионалов. / Д. Круглински, С. Уингоу, Дж. Шеферд// СПб Питер, 2004.

26. Курейчик В.М. и др. Методы генетического поиска / Под редакцией В.М. Курейчика. //-Таганрог: Изд-во ТРТУ, 2002

27. Марчук Г.И. Методы вычислительной математики. // М.:Наука,1989

28. Матвеев Н.М. Методы интегрирования обыкновенных дифференциальных уравнений. // М.: Высшая школа, 1967

29. Мейерс С. Наиболее эффективное использование С++. // М.: ДМК Пресс, 2000.

30. Ортега Дж. Введение в численные методы решения дифференциальных уравнений. / Дж. Ортега, У. Пул. // М.: Наука. 1986.

31. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. М: Наука, 1984.

32. Подбельский В.В. Язык Си++: Учеб. пособие. — 5-е изд. // М.: Финансы и статистика, 2003.

33. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. // М: Наука, 1974.

34. Романенко В.К. Курс дифференциальных уравнений и вариационного исчисления. М.: Физматлит, 2001

35. Рубан А.И. Методы оптимизации: учеб. пособие / А. И. Рубан. // Красноярск: НИИ ИЛУ, 2001.

36. Самарский A.A. Введение в численные методы. М.: Наука, 1982.

37. Самарский A.A. Численные методы./ A.A. Самарский, A.B. Гулин. // М.:Наука, 1989.

38. Семенкин Е.С. Оптимизация технических систем. Учебное пособие / Е.С. Семенкин, О.Э. Семенкина, С.П. Коробейников. //-Красноярск: СИБУП, 1996.-284 с.

39. Сопов Е.А. Вероятностный генетический алгоритм и его исследование // VII Королевские чтения. Том 5. Самара: Изд-во Самарского научного центра РАН, 2003. - С. 38-39.

40. Сопов Е.А. Вероятностный генетический алгоритм решения сложных задач оптимизации и его исследование // Молодежь Сибири науке России. - Красноярск: СИБУП, 2004. - С. 26-29

41. Сопов Е.А. Вероятностный генетический алгоритм с прогнозированием сходимости // Вестник университетского комплекса. Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2004. - Вып 1 (15). - С. 219-227

42. Сопов Е.А. О вероятностном генетическом алгоритме // Современные техника и технологии. В 2-х т. Томск: Изд-во Томского политехи, унта, 2004. - Т.2. - С. 197-199

43. Степанов В.В. Курс дифференциальных уравнений. // Эдиториал УРСС, 2004.

44. Страуструпп Б. Язык программирования С++. //СПб: Бином 2004

45. Тихонов А.Н. Дифференциальные уравнения. / А.Н. Тихонов, А.Б.Васильева, А.Г.Свешников// М.: Наука, Физматлит, 1998 г.

46. Тихонов А.Н. Численные методы решения некорректных задач. / А.Н. Тихонов, A.B. Гончарский, В.В. Степанов, А.Г. Ягола. // М.: Наука, 1990.

47. Турчак Л.И. Основы численных методов. /Л.И. Турчак, П.В. Плотников. //М.: Физматлит, 2003.

48. Филиппов А.Ф. Сборник задач по дифференциальным уравнениям. // М.: Интеграл-пресс, 1998.

49. Флетчер К. Численные методы на основе метода Галёркина. // SpringerVerlag, 1984.

50. Хартман Ф. Обыкновенные дифференциальные уравнения. // М.: Мир, 1970г.

51. Хьюз К. Параллельное и распределенное программирование с использованием С++. / К. Хьюз, Т. Хьюз. // М.: "Вильяме", 2004.

52. Цлаф Л.Я. Вариационное исчисление и интегральные уравнения. // М.: Наука, 1970.

53. Шилдт Г. Полный справочник по С++. // М.: "Вильяме", 2003.

54. Шпаковский Г.И. Программирование для многоядерных систем в стандарте MPI. / Г.И. Шпаковский, Н.В. Серикова. // Минск: БГУ, 2002.

55. Элджер Д. Библиотека программиста С++. // СПб: Питер, 1999.

56. Эльсгольц Л.Э. Дифференциальные уравнения и вариационное исчисление. //М.: Наука, 1965.

57. Эхтер Ш. Многоядерное программирование. / Ш. Эхтер, Д. Роберте. // СПб.: Питер, 2010.

58. Abell, M.L. Differential Equations with Maple V. / M.L. Abell, J.P. Braselton // Academic Press, London, 2000.

59. Banzhaf W. Genetic Programming. An Introduction. / W. Banzhaf, P. Nordin, R.E. Keller, F.D. Francone. // Morgan Kaufman Publishers, 1998.

60. Burgess G. Finding approximate analytic solutions to differential equations using genetic programming. / G. Burgess. //Surveillance Systems Division, Electronics and Surveillance Research Laboratory, Department of Defense, Australia, 1999.

61. Chapman B. Using OpenMP. Portable shared vevory parallel programming. / B. Chapman, G. Jost, R. Van Der Pas. // MIT press, 2008.

62. Cao H. Evolutionary Modelling of Systems of Ordinary Differential Equations with Genetic Programming. / H. Cao, K.Lishan, Y. Chen. // 2000.

63. Diver D.A. Applications of genetic algorithms to the solution of ordinary differential equations. J. Phys. A: Math. Gen. 26, 3503-3513 Analytic Solutions to Differential Equations 243, 1993.

64. Durrbaum A. Comparison of Automatic and Symbolic Differentiation in Mathematical Modeling and Computer Simulation of Rigid-Body Systems. / A. Durrbaum, W. Klier, H. Hahn. // Multibody System Dynamics 7, 331355, 2002.

65. Esparcia-Alcazar A. Learning schemes for genetic programming / A. Esparcia-Alcazar, K. Sharman. // In Proceedings Late Breaking Papers at the Genetic Programming Conference, pp. 57-65, Stanford University, 1997.

66. Fasshauer G.E. Solving partial differential equations by collocation with radial basis functions, in Surface Fitting and Multiresolution Methods. / A. LeMhaut, C. Rabut, L. Schumaker. // Eds. Nashville, TN: Vanderbilt Univ. Press, 1997.

67. Fasshauer G.E. Solving differential equations with radial basis functions: Multilevel methods and smoothing. Advances in Comput. Math., vol. 11, no. 2-3, pp. 139-159, 1999.

68. Fox C. An Introduction to the Calculus of Variations. Dover Publ., 1987.

69. Franke C. Solving partial differential equations by collocation using radial basis functions. / C. Franke, R. Schaback. //Appl. Math. Comput., vol. 93, pp. 73-83, 1998.

70. Clegg, J.C. Calculus of Variations. //Interscience Publishers Inc., 1968.

71. Goldberg D.E. Genetic algorithms in search, Optimization and Machine Learning. // Addision Wesley, 1989.

72. Howard D. Genetic Programming Solution of the Convection Diffusion Equation, / D. Howard, S.C. Roberts. // GECCO, 2001.

73. Howard D. Solution of differential equations with Genetic Programming and the Stochastic Bernstein Interpolation. / D. Howard, J. Kolibal // University of Limerick, 2005.

74. Iba H. Inference of differential equation models by genetic programming / H. Iba, E. Sakamoto. //Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), 2002, pp. 788-795.

75. Kamke E. Differential Equations. Solution Methods and Solutions. // Teubner, Stuttgart, 1983.

76. Kinnear K.E. Alternatives in Automatic Definition of Functions: A Comparison of Performance. Advances in Genetic Programming, Ch. 6, MIT Press, 1994.

77. Kirk D.B. Programming Massively Parallel Processors: A Hands-on Approach. / B.D. Kirk, Wen-mei, W. Hwu // Applications of GPU Computing Series, 2004.

78. Kirstukas SJ. A hybrid genetic programming approach for the analytical solution of differential equations. / S.J. Kirstukas , K.M. Bryden. // Ashlock International Journal of General Systems 34, 279-299, 2005.

79. Koza J.R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. // MIT Press, Cambridge, MA, 1992.

80. Koza J.R. Genetic Programming II: Automatic Discovery of Reusable Programs. // MIT Press, 1994.

81. Koza J.R. Hierarchical genetic algorithms operating on populations of computer programs. // Proceedings of the 11th International Joint Conference on Artificial Intelligence, Vol. 1. Morgan Kauffman, 1989.

82. Kumaresan N. Solution of Fuzzy Differential Equation under Generalized Differentiability by Genetic Programming / N. Kumaresan, J. Kavikumar, M. Kumudthaa, and Kuru Ratnavelu // World Academy of Science, 2011.

83. Langdon W.B. Data Structures and Genetic Programming: Genetic Programming + Data Structures = Automatic Programming. // Kluwer, Boston, 1998.

84. Montelora C. Solving the nonlinear schrodinger equation with an unsupervised neural network: Estimation of error in solution, / C. Montelora, C. Saloma // Opt. Commun., vol. 222, no. 1-6, pp. 331-339, 2003.

85. Morton K.W. Numerical Solution of Convection Diffusion Problems. // Chapman & Hall, 1996.

86. Murphy G.M. Ordinary Differential Equations and Their Solution // Princeton, NJ: VanNostrand, 1960.

87. Poli R. A field guide to genetic programming. / R Poli W Langdon N.F. McPhee. // http://www.gp-field-guide.org.uk 2008.

88. Poli R. Solving high-order boolean parity problems with smooth uniform crossover, sub-machine code GP and demes, / R. Poli, J. Page. // Genetic Programming And Evolvable Machines, 1(1/2), 37-56, 2000.

89. Press W. Numeric recipes. / W. Press, S. Teukolsky, W. Vetterling, B. Flannery. // Cambridge University Press, 2007.

90. Prosise J. Programming Windows with MFC 2nd Edition. // Microsoft Press, 1999.

91. Rauber T. Parallel programming for multicore and cluster systems. / T. Rauber, G. Riinger. // Springer, 2010.

92. Sanders J. CUDA by Example: An Introduction to General-Purpose GPU Programming / J. Sanders, E. Kandrot. // Addison-Wesley, 2010.

93. Scmidt M. Comparison of Tree and Graph Encodings as Function of Problem Complexity. / M. Scmidt, L. Hod. // In: Genetic and Evolutionary Computation Conference, pp. 1674-1679, 2007.

94. Tsoulos I. G. Solving differential equations with genetic programming. /1. G. Tsoulos, I. E.Lagaris. // Genet. Program Evolvable Mach, 7, 2006.

95. Wendland H. Meshless Galerkin methods using radial basis functions. // Math. Comput., vol. 68, no. 228, pp. 1521-1531, 1999.

96. Wu C.X. Approximate solutions, existence and uniqueness of the Cauchy problem of fuzzy differential equations. / С. X. Wu, S. Song, Stanley Lee. // J. Math. Anal. Appl., 202, 629-644, 1996.

97. Wu C.X. Existence theorem to the Cauchy problem of fuzzy differential equations under compactness-type conditions, / С. X. Wu, S. Song. // Inform. Sciences, 108, 123-134, 1998.1. СПИСОК ПУБЛИКАЦИЙ АВТОРА

98. Бураков С.В. Решение задачи Коши для обыкновенных дифференциальных уравнений методом генетического программирования / С.В. Бураков, Е.С. Семенкин // Журнал СФУ -"Математика и физика" Том 4, вып. 1. - 2011 - С. 61-69.

99. Бураков С.В. О решении вариационной задачи методом генетического программирования / С.В. Бураков, Е.С. Семенкин // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнёваю №5 (38). - 2011. - С. 19-24.

100. 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.

101. Бураков C.B. Алгоритм генетического программирования для приближенного аналитического решения задач вариационного исчисления. / C.B. Бураков, Е.С. Семенкин. М.: Реестр программ для ЭВМ, 2012-№ гос. per. 2012612021.

102. Бураков C.B. Алгоритм генетического программирования дляприближенного аналитического решения задачи Коши для139обыкновенных дифференциальных уравнений. / C.B. Бураков, Е.С. Семенкин. М.: Реестр программ для ЭВМ, 2012 № гос. per. 2012612022.

103. Бураков C.B. Алгоритм генетического программирования для приближенного аналитического решения краевой задачи для обыкновенных дифференциальных уравнений. / C.B. Бураков, Е.С. Семенкин. М.: Реестр программ для ЭВМ, 2012 № гос. per. 2012612111.

104. Бураков C.B. Алгоритм генетического программирования для приближенного аналитического решения задачи Коши для систем обыкновенных дифференциальных уравнений. / C.B. Бураков, Е.С. Семенкин. М.: Реестр программ для ЭВМ, 2012 № гос. per. 2012612023.