Построение единой программной среды для решения задач глобальной оптимизации (стр. 8 из 9)
Нужно сказать, что данная методика может быть перенесена и на случай алгоритмического задания целевой функции. Для этого требуется только знать точное описание синтаксиса языка такого задания.
Эффективное распределение памяти
При тестировании метода ветвей и границ на некоторых задачах обнаружилась интересная особенность. На первых этапах выполнения алгоритма скорость вычислений, произведенных с аффинными формами и с интервалами, в среднем равнялась нескольких тысячам в секунду. После того, как количество параллелепипедов в допустимом множестве достигало определенного количества, скорость вычислений неожиданно падала до нескольких сотен или даже десятков операций в секунду, даже при наличии свободной оперативной памяти. Этот эффект можно объяснить только тем, что алгоритму очень большое число раз приходится хаотично распределять и освобождать память под объекты небольшого размера, такие как параллелепипеды или вектора из аффинных форм. В результате оперативная память оказывается сильно сегментированной, и стандартный распределитель памяти становится недопустимо медлителен. Для решения этой проблемы был разработан собственный распределить памяти, базирующийся на стандартном. Общий принцип работы этого распределителя следующий. Память для объектов фиксированного размера size распределяется заранее и представляется в виде списка сегментов некоторого, достаточно большого размера, которые в свою очередь разбиты на блоки размера size, представленные в виде двух списков – свободного и занятого. Теперь, если программа затребовала кусок памяти размером size, то распределитель просто переносит блок из свободного списка в занятый и возвращает на него указатель. Это происходит, конечно, только в том случае, если свободный список не пуст, иначе распределятся новый сегмент размером, равным сумме размеров уже распределенных сегментов (т.е. итоговый размер удваивается), разбивается на блоки размера size которые, в свою очередь, добавляются в свободный список, после чего процедура повторяется. Механизм освобождения памяти происходит аналогично, нужно только определить момент, когда список сегментов не будет содержать занятых блоков и тогда освободить весь этот список.
На практике данный буферизированный распределитель оказался очень эффективным и легко применимым. Например, в одной из задач результат выполнения алгоритма содержал около полумиллиона параллелепипедов и функция разбиения этого множества на односвязные подмножества с помощью BSP-дерева (см. ниже), основанная на стандартном распределителе памяти затрачивала около 20 минут. При использовании же буферизированного распределителя потребовалось всего 6 секунд.
Структурирование результатов
На этапе завершения метода ветвей и границ результирующий список параллелепипедов может очень большим, поэтому получение такой информации как количество и содержимое связных областей, расстояние между этими областями, плотность распределения параллелепипедов в пространстве, границы результата и т.д. будет сопряжено со значительными трудностями. Поэтому нужен некоторый способ структурирования результирующего списка. В случае выбора двоичной схемы разбиения список удобно представлять в виде BSP-дерева, а в случае разбиения на k частей, в виде k-дерева. Такое дерево содержит узлы с информацией о параметрах разбиения и листья, являющиеся параллелепипедами из списка, и строится по мере выполнения алгоритма. Здесь возникает проблема построения сложных структур данных, когда один объект может одновременно принадлежать нескольким структурам данных (как, например, параллелепипеды принадлежат одновременно списку и дереву). Эта проблема может быть легко и элегантно решена путем применения механизма шаблонов языка C++.
После структурирования списка, операции по поиску какой-либо специфической информации о результате могут быть проведены быстро и эффективно.
Все описанные выше методы, а именно автоматический анализ функций, буферизированное распределение памяти и структурирование результатов были разработаны автором в виде библиотек на языке C++ и успешно протестированы на широком классе задач.
Численные результаты
Для сравнения возможностей интервальной и аффинной арифметики было проведено множество тестовых оценок примерных функций (некоторые из них показаны на графиках в приложении). Эти тесты показали, что способность аффинной арифметики учитывать взаимосвязи операндов обеспечивает в большинстве случаев значительно более точные оценки, чем в интервальной арифметике.
Ниже сравнивается выполнение IA, AA и AAIA при решении некоторых хорошо известных задач глобальной оптимизации тремя видами интервальных BAB методов: чистые модели, ускорение с локальным поиском; с ускорениями первого порядка (интервальная градиентная проверка); а также с Back-Boxing’ом. Данные для таблиц, а также рисунки разбиения областей взяты из [7].
Поиски останавливались, когда в главном списке L не оставалось прямоугольников большего диаметра, чем определенная точность. При решении задач использовалась возрастающая точность (10-3, 10-6 и 10-9) для определения влияния точности на выполнение. В таблицах ниже приведено CPU время в секундах, необходимое для решения каждой задачи каждым из вариантов, а также число прямоугольников, остающихся в L после завершения. Время ¥ означает, что программа не была завершена в течении 15 минут CPU времени.
Также даются рисунки разложений области при использовании градиентного теста и точности 0.0625% от диаметра области. На них прямоугольники, показанные белыми, были отброшены, а серые прямоугольники остались после завершения.
Задачи были запущены на машине 166Hz Pentium под Linux, используя компилятор GNU g++.
1. Функция Буфа (таблица 1, рис.3)
¦(x, y) = (x + 2y - 7)2 + (2x + y - 5)2
Глобальный минимум ¦ в квадрате W = [-10, 10]´[-10,10] равен ¦* = 0 = ¦(1, 3). Таблица 1 содержит результаты решения этой задачи всеми вариантами.
Эта задача была выбрана потому, что она выделяет главную слабость AA: как обсуждалось ранее, AA может выполняться плохо на функциях, которые являются суммами квадратов или когда зависимость между операндами незначительна. Это привело к большему времени для AA, но только на множитель k
[2,3].2. Функция Exp2 (таблица 2, рис. 4)
¦(x,y) = exy(4x2 + 2y2 + 4xy + 2y + 1).
Глобальный минимум ¦ в квадрате W = [-10, 10]´[-10,10] есть ¦* = 0 = ¦(0.5, -1). Квадратичная часть этой функции содержит зависимости, которые позволяют AA делать намного лучшие оценки. IA-оценки возле глобального минимума оказались мало точны, что явилось следствием очень большого числа прямоугольников в списке для чистых BAB методов. С другой стороны, AA-оценки для экспоненциальной части были хуже, чем IA-оценки; как следствие метод не смог отбросить много прямоугольников, удаленных от глобального минимума.
Таблица 1. Результаты выполнения алгоритмов для функции Буфа
| BAB-метод | Чистый | С град. проверкой | С Back-Boxing’ом | ||||
| Точность | Ариф-метика | Время | колич. | Время | колич. | время | колич. |
| 10-3 | IA AA AAIA | 0.07 0.18 0.12 | 4 10 4 | 0.07 0.16 0.11 | 4 5 4 | 0.00 0.01 0.02 | 1 1 1 |
| 10-6 | IA AA AAIA | 0.12 0.34 0.19 | 4 10 4 | 0.12 0.27 0.21 | 4 5 4 | 0.00 0.01 0.00 | 1 1 1 |
| 10-9 | IA AA AAIA | 0.21 0.52 0.29 | 4 10 4 | 0.20 0.43 0.32 | 4 5 4 | 0.00 0.00 0.00 | 1 1 1 |
 |
Рис.3. Разбиение области при минимизации функции Буфа в IA (слева), AA (в центре) и AAIA (справа).
Таблица 2. Результаты выполнения алгоритмов для функции Exp2
| BAB-метод | Чистый | С град. проверкой | С Back-Boxing’ом | ||||
| Точность | Ариф-метика | Время | колич. | Время | колич. | время | колич. |
| 10-3 | IA AA AAIA | 496.07 23.50 0.41 | 20610 14 14 | 0.29 39.34 0.48 | 28 5 5 | 0.30 38.69 0.59 | 30 4 5 |
| 10-6 | IA AA AAIA | ¥ 23.43 0.69 | 36727 14 14 | 0.44 39.44 0.75 | 28 5 5 | 0.46 38.91 0.83 | 28 4 5 |
| 10-9 | IA AA AAIA | ¥ 36.61 12.25 | 36635 4922 4157 | 0.59 40.51 1.12 | 32 8 8 | 0.61 39.51 1.18 | 28 7 7 |
 |
Рис.4. Разбиение области при минимизации функции Exp2 в IA (слева), AA (в центре) и AAIA (справа).
Заключение
Интервальные методы ветвей и границ относительно просты для реализации и позволяют получить достаточно точные и надежные решения для широкого класса задач глобальной оптимизации. Кроме того, достаточно легко вместо интервальной арифметики использовать аффинную арифметику. Хотя аффинная арифметика действительно более точна, чем интервальная, она более сложна для реализации и более трудоемка для выполнения. Тем не менее, как показано многочисленными примерами, ее повышенная точность имеет дополнительные преимущества из-за более эффективного разбиения области, вследствие чего окончательный список параллелепипедов короче, и часто весь алгоритм работает быстрее.