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

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

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

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

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