Практическая реализация алгоритмов

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

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

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

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

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

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

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

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