ЛПТау-последовательность является примеров равномерно распределенной последовательности. Ее полное название - последовательность, любой двоичный участок которой представляет собой - сетку. Приведем исходный алгоритм
1. Имеется таблица числителей направляющих чисел , 1j51, 1l20
2. Направляющие числа рассчитываются по формуле
= 2-l
3. В двоичной системе номер точки i записывается в форме i=em...e2e1 , а декартовы координаты точки Qi=(qi,1,...,qi,n) вычисляются по единой формуле (j=1,2,..n):
qi,j=e1 *e2*...*em (1)
где * означает поразрядное сложение по модулю 2 в двоичной системе.
Арифметический алгоритм, реализованный на ЭВМ выглядит так
1. По заданному номеру i вычисляем m=1+[ln i/ ln 2]
2. Для j=1,2,...n вычисляем
qi,j=2-k+1 (2)
причем использовано обозначение [z] - целая часть числа, {z}- дробная часть числа z.
Алгоритм нахождения точек равномерно распределенной последовательности в произвольной области по известному распределению в единичном многомерном кубе.
Для нахождения точек ЛПтау последовательности в произвольной области используем следующие Леммы
Лемма 1 . Если точки с декартовыми координатами (,,...) образуют равномерно распределенную последовательность в , то точки с декартовыми координатами (αi,1,,...αi,n) , где при j=1,2...n:
αi,j=aj+(bj-aj)qi,j (9)
образуют равномерно распределенную последовательность в параллелепипеде , состоящем из точек (α1,...αn) , координаты которых удовлетворяют неравенствам ajαjbj
Лемма 2 . Пусть ,..., - последовательность точек , равномерно распределенных в , а - произвольная область с положительным объемом VG >0. Если среди точек отобрать все точки, принадлежащие , то получим последовательность точек , равномерно распределенных в .
Использование метода ЛПТау последовательности
Точки ЛПТау - последовательности в простейшем случае ( один критерий) можно использовать как пробные в случайном поиске. Выбираем N точек , равномерно распределенных в рассматриваемой области , вычисляем значения функционала и находим точку , где он принимает минимальное значение.
Однако особый интерес использование этих последовательностей имеет в двух классах задач.
1. Задачи, в которых требуется одновременно оценить максимумы и (или ) минимумы нескольких функций( это можно сделать по одним и тем же пробным точкам
2. Задачи, в которых для отыскания глобального экстремума многоэкстремальной функции используют локальные методы оптимизации (при этом, чтобы не попасть вместо глобального экстремума в какой- либо из локальных, приходится повторять локальный поиск много раз, начиная с различных начальных точек. Очевидно, что начальные точки должны быть равномерно расположены. Самым эффективным способом выбора начальных точек оказалось использование точек ЛПТау - последовательности.