Обобщение методов оптимальных покрытий на многомерный случай

Будем предполагать, что минимизируемая функция Q(x) в задаче принадлежит классу KL функций, удовлетворяющих условию типа условия Липшица с известной константой L:

|Q(x1) — Q(x2)| ≤ Lρ(x1, x2), x1, x2∈Dx, (6.10)

где ρ(x1, x2) — непрерывная, ограниченная функция, характеризующая расстояние между точками x1 и х2 (например,

ρ(x1, x2) = ||x1 — x2||

или

ρ(x1, x2) = max |xi1 — xi2|.

Рассмотрим вопрос построения для фиксированного числа испытаний N оптимальной пассивной стратегии Xn = (х1, х2, …, хN), являющейся решением следующей экстремальной задачи:

W(XN) = min max |Q* — Q(xk)|, (6.11)

Как было показано в поиске глобального минимума кривой с помощью стохастических автоматов, решение задачи (6.11) сводится к построению оптимального покрытия множества Dx совокупностью r-шаров S (xi, r*) с центрами в точках хi и радиусом r*:

∪S(xi, r*)⊃Dx, (6.12)

В этом случае оптимальная на классе KL пассивная стратегия ХN* не зависит от значения константы Липшица L, которая фигурирует только в оценке критерия эффективности алгоритма пассивного поиска:

W(XN*) = r(XN*)L. (6.13)

Задача оптимального покрытия прямоугольного параллелепипеда шарами одинакового радиуса (6.12) является нерешенной задачей дискретной геометрии. Поэтому рассмотрим частный случай этой задачи когда область Dx является двумерным координатным квадратом, который покрывается кругами одинакового радиуса.

Для изложения алгоритма построения оптимальной системы узлов XN* для двумерного квадрата D введем следующие определения.

Функция расстояния ρ(х, хi) между точками х и хi называется нормальной, если область r -шара S (хi, r)⊂D является односвязным множеством для любых r > 0.

Областью Дирихле S(хi) точки хi называется множество точен x∈D таких, что

ρ(х, хi) ≤ ρ(х, хk), k = 1, 2, …, N, k ≠ i.

Другими словами, область Дирихле точки хi включает точки, которые расположены от точки испытания хi не дальше, чем от остальных точек испытаний хk, k = 1,2, …, N, k ≠ i.

Точка хi называется неулучшаемой в квадрате D относительно системы узлов ХN, если не существует сколь угодно близкой к ней точки х’ такой, что

Ai(x’) = Ai(xi). (6.14)

В противном случае (при нарушении неравенства (6.14)) точка хi называется улучшаемой точкой, а процедура замены ее точкой х’ — улучшением.

Введенные определения позволяют описать алгоритм F36, реализующий пассивный поиск на двумерном квадрате D точки глобального минимума х*, в виде следующей последовательности действий.

1. Задаются любая произвольная система узлов ХN = (х1,…, хN) и вид нормальной функции ρ(х, хi) (например, ρ(х, хi) = ||х — хi||).

2. Для каждой точки испытания хi, i = 1, 2, …, N, вычисляется максимальное расстояние, допустимое в ее области Дирихле:

Ai = max ρ(х, хi). (6.15)

3. Из системы узлов XN выделяется та из улучшаемых точек, которая удовлетворяет условию

Ak(xk) = max Аjj),

где максимум берется только по улучшаемым точкам хj, j = 1, …, M.

4. Если в системе узлов ХN все точки хi являются неулучшаемыми точками, тогда процесс построения оптимального покрытия (6.12) закончен и задача (6.1) считается решенной. В противном случае вычисления продолжаются с п. 5.

5. Последовательной процедурой улучшения производится замена точки хk. полученной на п. 2, на неулучшаемую точку х’ и рассматривается новая система узлов, для которой все вычисления повторяются с п. 2.

Для любой точки xi нормальная функция ρ(х, хi) достигает своего максимального значения на границе области Дирихле S(xi) в характерны точках, под которыми понимаются следующие точки (рис. 6.5):



Рис. 6.5. Оптимальное покрытие квадрата семью кругами одинакового радиуса r* = 0,275 (сплошными линиями выделены области Дирихле для каждой точки испытаний, отмеченной крестиком)

1 тип — точки, являющиеся вершинами квадрата D;
2 тип — точки пересечения с границей области D линий.

Тогда процедура второго шага алгоритма может быть сведена к следующей последовательности действий:
1. Определяются все характерные точки {хp} системы узлов.
2. Для каждой точки испытания xi выделяются те характерные точки хp, которые находятся к точке хi ближе, чем к любой другой точке испытаний xk, k = 1, 2, …, N, k ≠ i (так называемые действительные характерные точки):

ρ(хp, хi) ≤ ρ(хp, хk) для всех k = 1, 2,…, N

(например, на рис. 6.5 для точки испытания С действительными характерными точками являются точки 1 — 5).

3. Для каждой точки хi в ее действительных характерных точках вычисляется функция ρ(хp, хi) и среди полученных значений выбирает-
ся максимальное в качестве параметра

Ai = Aii) = max ρ(х, хi).

Перед началом работы алгоритма все точки системы узлов XN считаются улучшаемыми, т. е. начальные значения признака αi принимаются равными нулю для всех точек испытаний х1,…, хN. При замене улучшаемой точки хk на неулучшаемую точку х’ (п. 5) параметр принимает значение, равное единице. Для любой другой точки х’ новой системы узлов (6.16) принимается αi = 0, если значение ρ(х, хi) в тех характерных точках области Дирихле S(хi), где ρ(х, хi) = Аi изменилось больше, чем на заданную величину δ, определяющую точность построения оптимального покрытия. Если αi = 1 для всех точек испытаний х’, i = 1, 2,…, N, то процесс поиска точки минимума x* закончен (п. 4). В противном случае, из тех точек испытаний, для которых αi = 0, для улучшения выбирается точка хk, которой соответствует наибольшее значение параметра Ak = Akk) (п. 3).

Процедура улучшения точки испытания хk на пятом шаге алгоритма представляет собой последовательный процесс, на каждом этапе которого необходимо определить достаточно малый вектор перемещения Δk = (Δx1k, Δx2k) такой, чтобы

Ak(xk + Δk) < Ak(xk). (6.20)

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

Ai(xi) < Ak(xk + Δk), i=1,2, …, N, i≠k.


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru