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

Размещено на http://www.allbest.ru/

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

Введение

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

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

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

1. Решение ОДУ с помощью алгоритма ГП

генетический программирование задача коши

1.1 Постановка задачи и метод решения

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

F(x, y, yґ, yґґ, …, y⁽ⁿ⁾)=0 1.1)

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

y (x₀)=Y₀, yґ (x₀)=Yґ₀, …, y^(n-1) (x₀)= Y₀^(n-1), (1.2)

где y(x) - искомое решение, yґ, yґґ,…, y⁽ⁿ⁾ - производные функции y(x); Y_0, Y₀ґ, Y₀ґґ,…, Y₀^(n-1) - заданные вещественные константы. Требуется найти функцию y(x), удовлетворяющую уравнению (1.1) и начальным условиям (1.2). В теории обыкновенных дифференциальных уравнений доказана теорема существования и единственности решения для уравнения n-го порядка Петровский, 1984. Далее будем считать, что требования теоремы удовлетворены. Аналогично можно поставить краевую задачу, однако в этом случае не гарантирована единственность решения.

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

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

Для разработки алгоритма определим концепцию работы алгоритма: данные, как и в теоретической задаче, - это уравнение (символьное выражение) и набор начальных данных (вещественный вектор), в зависимости от порядка ОДУ, искомым решением задачи будем считать символьную запись точного решения (с точностью до элементарных преобразований) или приближенное (с наибольшее возможной точностью) символьное выражение в случае, когда решение нельзя представить элементарными функциями. Решение задачи должно удовлетворять уравнению и начальным условиям с малой погрешностью. Решение-кандидат называется индивидом, множество решений - популяцией, а операторы преобразования решений - селекция, скрещивание, мутация. Способ вычисления погрешности не является принципиальным. Значение функции ошибки преобразуется в число, называемое пригодностью индивида (чем меньше ошибка, тем более пригоден индивид). В рамках данной задачи символьное представление решения задано бинарным деревом, состоящим из элементов функционального множества (+,-,*,/,sin, cos, exp, log) и элементов терминального множества (термов , , а также вещественных коэффициентов). Для решения общих задач терминальное и функциональное множества могут быть дополнены.

Упрощенно схему алгоритма можно представить Koza, 1992, состоящей из следующий основных шагов:

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

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

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

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

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

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

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

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

,

,

где, Fit(P_k) - значение функции пригодности k-го индивида, E(P_k) - ошибка аппроксимации, вычисляемая по всем точкам выборки (N - объем выборки), K1 - коэффициент штрафа за сложность дерева, D(P_k) - число вершин дерева P_k, К2 - коэффициент штрафа за начальные условия (n - количество начальных условий), Y₀^(j) - заданные начальные условия, - производная j-го порядка в точке x₀ (y⁽⁰⁾(x₀)=y(x₀)), |P_k(x_i)| - отклонение (например, среднеквадратическое) функции F из выражения (1) от нуля, получаемое при подстановке решения P_k в ОДУ в выбранных точках (x_i) - точки из интервала могут быть выбраны равномерно, случайно или каким-либо специальным образом. Здесь при вычислении ошибки соответствия решения ОДУ требуется вычисление производных в точках выборки. Производные вычисляются численно (с определенным порядком малости) или аналитически - строится дерево производной функции. В случае краевой задачи вместо начальных условий проверяется соответствие функции краевым условиям.

На третьем этапе производится адаптация каждого индивида из популяции. Индивид, лучше адаптирующийся в условиях поставленной задачи, имеет более высокую пригодность, а, следовательно, более высокую вероятность быть отобранным для порождения потомков. Адаптация индивида означает изменение его частей так, чтобы решение имело меньшую погрешность, то есть означает оптимизацию решения - изменение вещественных коэффициентов и/или функционального набора бинарного дерева. Если зафиксировать все вершины дерева кроме какого-то одного узла, то его (дерево) можно рассматривать как функцию одной переменной, например, можно воспользоваться методом Хука-Дживса, отличающимся простотой и эффективностью Банди, 1988. Бинарное дерево (решение ОДУ) может в общем случае содержать много вещественных коэффициентов и узлов-операций, это делает целесообразным при оптимизации проведение лишь небольшого числа итераций. Для ускорения поиска решения можно варьировать и функциональный набор, содержащийся в дереве.

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

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

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

1.3 Комбинация алгоритма генетического программирования и численного метода

Задачу отыскания решения задачи Коши в символьном виде можно решать, используя комбинацию численного метода и алгоритма генетического программирования. Для этого предварительно ОДУ решается численно, например, методом Рунге-Кутта с четвертым порядком точности Самарский, 1989. Решение численным методом предполагает предварительное видоизменение уравнения в пригодную для решения форму, вследствие чего некоторые частные решения должны быть рассмотрены отдельно. Если уравнение (1) является уравнением первого порядка, преобразуем его, если это возможно, к виду пригодному для итерационной процедуры численного метода:

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

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

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

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

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

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

Рассмотрим тестовую задачу: yґґ = -2·sin(x), y(0) = 0.0, yґ(0) = 2.0.

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

y(x)=1.999611801x-0.3330926297x³+0.01662624753x⁵-0.0003886344121x⁷+0.440310^-5x⁹.

Легко видеть, что это выражение является представлением точного решения (y = 2·sin(x)) с помощью формулы Тейлора с остаточным членом достаточно высокого порядка малости.

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

Табл. 1.

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

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

Табл. 2.

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

Заключение

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

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

Список литературы

1.Банди, 1988 Банди Б. Методы оптимизации (вводный курс). - М.: Радио и связь, 1988.

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

3.Самарский, 1989 Самарский А.А. Теория разностных схем. - М: Наука, 1989.

4.Филиппов, 2003 Филиппов А.Ф. Сборник задач по дифференциальным уравнениям. - Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2003.

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

6.Koza, 1992 Koza J.R.. Genetic Programming: On Programming Computer by Means of Natural Selection and Genetics. Cambridge, MA: The MIT Press, 1992.

Размещено на Allbest.ru