Построение единой программной среды для решения задач глобальной оптимизации (стр. 7 из 9)
1. Основой каждого алгоритма служат элементарные операции с вещественными числами, но на вычислительном устройстве вещественные числа аппроксимируются дискретным множеством машинно-представимых чисел, в результате чего возникают ошибки округлений, которые нужно учитывать.
2. Алгоритм оперирует функциями одной или многих переменных, полученными во входных данных, поэтому должна быть возможность проведения некоторого начального анализа этих функций, такого как расчет производных, поиск общих подформул, оптимизация записи функции, с целью уменьшения количества элементарных операций и т.д.
3. Количество операций с такими структурами как вещественные вектора, интервальные вектора и вектора с координатами в виде аффинных форм даже для самых простых задач очень велико, поэтому стандартные распределители динамической памяти мало пригодны и для повышения скорости выполнения алгоритма требуется реализовать свой распределитель памяти.
4. Результатом выполнения алгоритма, реализующего метод ветвей и границ со стандартной схемой разбиения, является множество параллелепипедов. Характер этого множества может быть очень сложным, поэтому для дальнейшей его обработки требуется некоторый способ упорядочивания данного множества, например, с помощью BSP дерева.
5. Если задача такова, что ее решением является гиперповерхность, то любой метод поиска всех решений, возвращающий результат в виде некоторого надмножества решения оказывается практически неприменим даже для небольшой точности из-за огромного объема требуемой памяти. Хороший алгоритм должен идентифицировать такой случай и специальным образом его обработать.
Проблемы 1 – 4 так или иначе решаются путем применения интервальной или аффинной арифметики, методов, разработанных для автоматического анализа функций и с помощью методов структурирования геометрических объектов (подробности смотрите в следующих параграфах). Проблема 5 даже при поверхностном рассмотрении оказывается очень сложной и требующей дополнительного исследования, выходящего за рамки данной работы.
Автором разработаны соответствующие алгоритмы на языке программирования C++ для решения проблем 1 – 4, причем главная цель, которая здесь преследовалась, состояла не в реализации отдельных методов, а в построении общей вычислительной среды или системы, основанной на самых современных принципах программирования, в которой разработка конкретных методов оказалась бы тривиальной задачей. В качестве примера, демонстрирующего возможности этой системы, с помощью нее разработан алгоритм, реализующий метод ветвей и границ с градиентной проверкой, и протестирован на нескольких тестовых задачах.
Автоматический анализ функций
Пусть целевая функция подается на вход оптимизатора в виде символьной строки и списка имен переменных, от которых она зависит (для простоты здесь полагается, что функция задана в виде суперпозиции известных элементарных функций, а не алгоритмически). Если полученные данные корректны, то, производя лексический и синтаксический разбор входной символьной строки эту функцию всегда можно представить в виде дерева, с узлами, содержащими данные трех типов: константы (t_constant_data), переменные (t_variable_data) и операторы (t_operator_data). Как известно, между обычными и бинарными деревьями существует взаимно однозначное соответствие. Поэтому обычные деревья удобнее обрабатывать и хранить именно в виде право-прошитых бинарных деревьев [15], которые во всех дальнейших рассуждениях, для краткости, называются просто деревьями. На C++ такое дерево может быть описано в виде класса t_function_node, определив операции над объектами которого (по сути операции над деревьями) можно строить сколь угодно сложные суперпозиции функций. Например, если T1 и T2 деревья (или объекты класса t_function_node), то T1 + T2 есть дерево с корнем, содержащем данные типа “binary_plus_operator” и имеющее в качестве левого поддерева дерево T1, а в качестве правого подде
рева дерево T2 (см. рис. 2).
 |
 |
 |
 |
После этого остается только для каждой элементарной операции или функции задать нужные свойства, такие как вычисление производной, проведение элементарных сокращений (умножение на 1, сложение с нулем и т.д.), упорядочивание аргументов (в случае коммутативности), проведение вычислений над вещественными, интервальными и аффинными аргументами. Теперь, делая рекурсивные вызовы от корня к поддеревьям, мы имеем возможность проводить свертывание констант, упрощать запись функции, строить по данной функции ее частные производные любого порядка по любым переменным, находить общие подформулы и вычислять значение функции в нужной арифметике.
Касательно метода ветвей и границ можно сделать одно замечание. Если используется схема разбиения области плоскостями, ортогональными осям координат, то часто при последовательных вычислениях значений функции изменению подвергается только одна переменная. Но, если в функции есть подформулы, не зависящие от этой переменной, то их значения от шага к шагу не меняется, а значит вычислять их заново не имеет смысла. Поэтому в каждом узле дерева удобно хранить значения, полученные на предыдущем этапе вычисления и обновлять их только по мере надобности.