V Международная студенческая научная конференция Студенческий научный форум - 2013

Введение

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

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

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

Если итерационный процесс сходится, то предельное значение является решением данной системы уравнений. При этом, поскольку численные методы для решения подобных задач хорошо изучены, для них получены достаточные условия сходимости и оценки точности [3].

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

Возможности существующих программных комплексовдля решения систем трансцендентных уравнений

В настоящее время при выполнении сложных научных и инженерно-технических расчетов, проведении прикладных исследований применяются различные коммерческие программные продукты. Лидерами рынка среди них являются программные комплексы «Wolfram Mathematica» и «Mathcad».

«Wolfram Mathematica» является одним из лидеров на рынке программных комплексов для различных математических вычислений. Программа предоставляет много возможностей для решения большого числа различных математических задач. В частности, с её помощью можно решать «простые» системы трансцендентных уравнений в символьном виде, а также находить численное решение систем трансцендентных уравнений приближенными методами. Программа является платной (стоимость около 300$ США). Имеется возможность доступа к программе через интерфейс API, что позволяет использовать возможности программного комплекса при разработке собственных программных продуктов.

Пакет «Mathcad» – ещё один лидер на рынке программных комплексов для математических вычислений. Программа является платной (стоимость около 80 тыс. руб.). Как и в случае с пакетом «Wolfram Mathematica», к программе «Mathcad» можно обращаться через интерфейс API.

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

Постановка задачи

Алгебраическое уравнение – уравнение вида P(x₁,x₂,…,xn) = 0, где P – многочлен от переменных x₁, x₂,…, xn, которые называются неизвестными.

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

Требуется найти корни системы из m трансцендентных уравнений c n неизвестными:

(1)

Иногда бывает достаточно найти хотя бы одно решение – точное или приближенное (с требуемой точностью) – из указанной области.

Например, система

(2)

имеет корни: x= 1, y = 2, z = 3. Решение указанной системы являлось одним из тестовых заданий, на котором проверялись возможности генетических алгоритмов.

Таким образом авторами решались следующие задачи:

1. Разработка генетических алгоритмов для решения систем трансцендентных уравнений.

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

3. Генерация тестовых заданий и тестирование разработанного программного комплекса.

Генетические алгоритмы (далее ГА) – представляет собой адаптивный поисковый метод, который основан на селекции лучших элементов в популяции подобно эволюционной системе Чарльза Дарвина [1]. Генетический алгоритм работает на основе начальной информации, в качестве которой выступает подмножество множества допустимых решений (начальная популяция). Каждый элемент начальной и последующих популяций (поколений), как правило, представляет собой одну или несколько хромосом (особей), состоящих из генов. Цель работы ГА – оптимизация целевой функции (фитнесс-функции) на заданном множестве, которое может быть как дискретным, так и непрерывным.

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

Постановка задачи решения трансцендентных систем уравнений

Пусть дана система трансцендентных уравнений:

, ⁽³⁾

или в векторной форме , где

. ⁽⁴⁾

Необходимо найти корни этой системы.

Каждое – некоторая функция, которая может в качестве элементов содержать определённые интегралы.

Тогда задача решения системы трансцендентных уравнений с помощью комбинации генетических алгоритмов представима в виде тройки {GA, N, E}, где GA – генетический алгоритм, определяемый с помощью множества параметров:

• способ кодирования особей:

пусть In – особь с номером n, BIT(X_in) – побитовое представление переменнойX_in, тогда In ≡ ∪{BIT(X_in) } ⇒In – битовый массив;

• фитнес-функция:

Fit(In)=∑(f_i(In))², где f_i – уравнения системы;

• вероятность мутации:

пусть In – особь с номером n, I_in – (i-й) бит этой особи, P(Event, I_in) – вероятность события Event с I_in, Event – один из видов мутации, тогда ∀Event ∀n₁∀n₂∀i₁∀i₂P(Event,I_i1n¹)=P(Event,I_i2n²);

• вероятность скрещивания:

пусть In – особь с номером n, MARK(In) – событие, при котором In выбран для селекции, P(Event, I_in¹, I_in²| MARK(In¹), MARK(In²)) – вероятность, что особи In¹ и In² будут скрещены, Event – один из видов скрещивания;

• способы скрещивания:

пусть SELECT(In¹,In²) =In³, обобщённый вид функции скрещивания, функции скрещивания, используемые в программе:

•  

  • AVG(In¹, In²) ≡ ∪_i{( In¹+ In²)/2};

  • POINT(In¹, In²) ≡ ∀i, RANDOM(0, LENGTH(In¹), i), ∪_j{jFit(Ip))→I^k ∈ GENERATION(n))));

    • способ формирования начальной популяции – случайный:

    GENERATION(0) = ∪{RANDOMBIT()};

    • критерий останова:

    ∃n, Fit(In)

Код для цитирования: Скопировать