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

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

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

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

При этом возникают следующие вопросы:

• 1. Какие из этих алгоритмов быстрее находят решение задачи?
• 2. Какие из этих алгоритмов чаще находят решение задачи (как уже было сказано, задача является алгоритмически неразрешимой)?
• 3. Способны ли алгоритмы к нахождению множества решений задач (если они присутствуют)?

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

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

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

Для реализации необходимо решить ряд задач:

• 1) обзор основных методов решения систем нелинейных уравнений;
• 2) реализация существующих алгоритмов решения систем уравнений (как эволюционных алгоритмов, так и численных);
• 3) разработка и реализация собственных решений систем уравнений базирующаяся на эволюционных алгоритмах;
• 4) генерация большого числа тестов для всех алгоритмов;
• 5) сбор статистики решения тестов алгоритмами;
• 6) определение наилучшего алгоритма по результатам тестов.

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

• 1) генетические алгоритмы;
• 2) алгоритм птичьих стай;
• 3) численные алгоритмы.

Объектами исследования являются:

• 1) классы систем нелинейных уравнений, наиболее хорошо решаемые каждым из рассмотренных методов;
• 2) оптимальные параметры методов для каждого класса исходных систем;
• 3) точность результатов, полученных различными способами.

Для достижения поставленной цели, предполагается проведение следующих этапов исследования:

• 1) реализация различных методов решения систем нелинейных уравнений в виде программного продукта;
• 2) генерация большого числа систем нелинейных уравнений с заранее известными ответами;
• 3) поиск корней у сгенерированных систем;
• 4) сравнение полученных результатов для разных типов систем.

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

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

На рис. 1 представлена архитектура системы.

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

• 1) начальное приближение;
• 2) количество итераций/поколений и т.п.;
• 3) дистанция обзора птицы (в алгоритме птичьих стай);
• 4) способ подсчёта «фитнесфункции»;
• 5) алгоритм кроссинговера и т.п.;
• 6) другое.

Кроме того каждый метод решения должен содержать параметры по умолчанию.

Анализатор уравнений (Parser) получает в качестве входных данных уравнения системы и список переменных с их текущими значениями, возвращает же он значение левой части уравнения при заданных значениях переменных.

Генерация систем уравнений (RandomGenerator) любой сложности c заранее известным ответом может быть осуществлена достаточно просто. Для этого предполагается выполнить следующую последовательность шагов:

• 1) задать количество уравнений и переменных в системе;
• 2) сгенерировать произвольную систему с заданными на первом шаге параметрами;
• 3) вместо каждой переменной в системе подставить произвольно выбранную константу;
• 4) вычислить значение левой части каждого уравнения системы;
• 5) прировнять левые части каждого уравнения системы к найденным значениям;
• 6) провести обратную замену (левые части исходной системы необходимо прировнять к найденным значениям);
• 7) вектор ответа - это вектор замен, произведённых на шаге 3.

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

• 1) уровень вложенности функций;
• 2) вид уравнений системы;
• a) экспоненциальные;
• b) полиномиальные;
• c) тригонометрические;
• d) смешанные;
• 3) значения констант;
• 4) другое.

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

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

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