Пусть целевая функция подается на вход оптимизатора в виде символьной строки и списка имен переменных, от которых она зависит (для простоты здесь полагается, что функция задана в виде суперпозиции известных элементарных функций, а не алгоритмически). Если полученные данные корректны, то, производя лексический и синтаксический разбор входной символьной строки эту функцию всегда можно представить в виде дерева, с узлами, содержащими данные трех типов: константы (t_constant_data), переменные (t_variable_data) и операторы (t_operator_data). Как известно, между обычными и бинарными деревьями существует взаимно однозначное соответствие. Поэтому обычные деревья удобнее обрабатывать и хранить именно в виде право-прошитых бинарных деревьев [15], которые во всех дальнейших рассуждениях, для краткости, называются просто деревьями. На C++ такое дерево может быть описано в виде класса t_function_node, определив операции над объектами которого (по сути операции над деревьями) можно строить сколь угодно сложные суперпозиции функций. Например, если T 1 и T 2 деревья (или объекты класса t_function_node), то T 1 + T 2 есть дерево с корнем, содержащем данные типа “binary_plus_operator” и имеющее в качестве левого поддерева дерево T 1, а в качестве правого подде
рева дерево T 2 (см. рис. 2).
|
| |  |
После этого остается только для каждой элементарной операции или функции задать нужные свойства, такие как вычисление производной, проведение элементарных сокращений (умножение на 1, сложение с нулем и т.д.), упорядочивание аргументов (в случае коммутативности), проведение вычислений над вещественными, интервальными и аффинными аргументами. Теперь, делая рекурсивные вызовы от корня к поддеревьям, мы имеем возможность проводить свертывание констант, упрощать запись функции, строить по данной функции ее частные производные любого порядка по любым переменным, находить общие подформулы и вычислять значение функции в нужной арифметике.
Касательно метода ветвей и границ можно сделать одно замечание. Если используется схема разбиения области плоскостями, ортогональными осям координат, то часто при последовательных вычислениях значений функции изменению подвергается только одна переменная. Но, если в функции есть подформулы, не зависящие от этой переменной, то их значения от шага к шагу не меняется, а значит вычислять их заново не имеет смысла. Поэтому в каждом узле дерева удобно хранить значения, полученные на предыдущем этапе вычисления и обновлять их только по мере надобности.
Нужно сказать, что данная методика может быть перенесена и на случай алгоритмического задания целевой функции. Для этого требуется только знать точное описание синтаксиса языка такого задания.
2020-01-14
133
