Метод отсечений для решения одного класса задач условной псевдобулевой оптимизации

Метод локального поиска является основой большинства регулярных алгоритмов, разработанных для решения различных задач псевдобулевой оптимизации. Это самый простой и наиболее универсальный метод дискретной оптимизации. Для некоторых классов задач безусловной и условной оптимизации псевдобулевых функций (преимущественно монотонных) разработаны алгоритмы локального поиска, позволяющие найти локальный минимум за полиномиальное число вычислений. Однако для произвольных функций, в том числе и алгоритмически или неявно заданных, метод локального поиска не гарантирует своего вырождения в полный перебор. Поэтому в работах [1...3] автором был предложен метод отсечений, решающий эту проблему Метод гарантирует исключение полного перебора при нахождении локального минимума любой функции на всем пространстве булевых переменных.

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

Свойства пространства булевых переменных. Общая постановка задачи псевдобулевой оптимизации имеет вид f (X) ^ extr , (1) где f: S ^ R; S с B 2; B2 = B2 х B2 х...х B2; B 2 = {0,1}.

Задача условной оптимизации, которую автор предлагает решать методом отсечений, имеет своим множеством допустимых решений векторы с фиксированным числом ненулевых компонент:

n

S = { X е B ² : £ x j = m , m <  n } . (2) ⁿ j = 1

Приведем необходимые определения и утверждения, принятые и доказанные в [4].

Определение 1. Точки X 1 , X ² е B ₂ назовем к -сосед-ними, если они отличаются значениями к координат, k = 1, n . Однососедние точки будем называть просто соседними точками.

Определение 2. Множество O k ( X ) е B n всех точек, которые являются к -соседними к точке X , будем называть к -м уровнем точки Х , к = 1, n . При этом O о ( X ) = X .

В соответствии с этим определением, задачу (1), (2) можно называть задачей на т -м уровне нулевой точки X 0 (0,0, ...,0) .

Определение 3. Будем называть точку X е B ₂ , для которой выполняется условие f ( X ) <  f ( X ) V X е O 1 ( X ) , локальным минимумом функции/} X).

Определение 4. Если псевдобулевая функция имеет только один локальный минимум на B n , то будем говорить, что эта функция унимодальная.

Определение 5. Множество точек W ( X ⁰, X l ) = { X ⁰, X 1 , X ²,..., X i ,..., X l ^{- 1}, X l ) с B 2 назовем путем длины / между точками X ⁰ и X l , если V 1 = 1, l точка X¹ является соседней к точке X^{1 1} .

Определение 6. Если X ¹ е O k ( X ⁰) с B ₂ , то в случае когда I = к, путь W ( X ⁰, X ¹ ) будем называть кратчайшим.

Определение 7. Унимодальную функцию/} X) назовем разнозначной на B n , если для каждого кратчайшего ²

пути W ( X ^о, X ) , X = X выполняется условие f ( X ¹ ) Ф f ( X ^j ) при i * j , где X ¹ , X ^j е W ( X ⁰, X ^l ) , 1 = 0, l , j = 0, l .

Определение 8. Путь W - ( X ⁰, X ^l ) с B ₂ назовем путем невозрастания функции / ( X ), если V X ¹ , X ^{1 - 1} е W ^f ( X ⁰, X ^l ) , 1 = 1, l выполняется условие f ( X ¹ ) <  f ( X ¹ -¹) , и путем убывания функции, если это неравенство строгое.

Лемма 1 [4]. V X е B ₂ : card O k ( X ) = C nk , где C n -число сочетаний из п по к , к = 0, n ■

Лемма 2 [4]. V X е B ₂ : B ₂ = n O_k ( X ) .

к = 0

Лемма 3 [4]. Для любой унимодальной разнозначной на B ₂ функции / } X) в каждой точке X е B ₂ \{ X } среди точек X ^j е O 1 ( X ) , 1 = 1, n найдется хотя бы одна такая точка X ^j , что f ( X ^j ) <  f ( X ) .

Как следует по лемме 2, пространство B ₂ всегда можно представить в виде объединения п уровней произвольной точки X е B 2П (в дальнейшем эту точку будем обозначать X ⁰ ). При этом любой уровень O k ( X ⁰) , k = 1, n - 1 разбивает пространство B ₂ на два непустых непересекающихся подпространства, состоящих из объединения полных уровней x 0 :

^k — ¹                      n

V 1 = U O 1 (X ⁰), V 2 = U O 1 (X ⁰).

= 0                   i = k + 1

Метод отсечений. На основании приведенных определений и утверждений автором в [1] был доказан ряд утверждений и предложен метод отсечений, общая схе- ма которого для задачи безусловной псевдобулевой оптимизации выглядит следующим образом.

• 1.    На первом этапе пространство решений B n делим на два подпространства некоторым уровнем O k ( X ⁰) , k = 1, n - 1 . Он назван отсекающим уровнем.

• 2.    Вычисляем значения функции в точках отсекающего уровня и делаем заключение, в каком из исследуемых подпространств находится минимум. Если минимум находится на отсекающем уровне, то останавливаем поиск и переходим к п. 4 схемы.

• 3.    Подпространство, в котором находится минимум, снова делим на два подпространства новым отсекающим уровнем и переходим к п. 2 схемы.

• 4.    Останавливаем поиск.

Подробное описание метода для задачи безусловной оптимизации приводится в [1].

Заметим, что деление подпространств на два проводится до тех пор, пока подпространство, содержащее X , не будет состоять из одного уровня (если, конечно, до этого не будет определен минимум). На этом последнем уровне и лежит точка, доставляющая минимальное значение функции.

Свобода выбора отсекающего уровня на каждом этапе позволяет строить ряд алгоритмов, отличающихся правилом определения номера отсекающего уровня в пп. 1 и 3 схемы. При отсутствии априорных сведений о функции естественно рассматривать средние уровни на каждом этапе алгоритма, а в качестве X ⁰ - нулевую точку. Под средним уровнем на этапе можно понимать уровень с номером, равным среднему арифметическому (целой части) номеров I и L , или же уровень, разбивающий подпространство, исследуемое на этапе, на два равномощных или максимально близких по мощностям.

В работах [2; 5] автором строятся три алгоритма метода отсечений для задачи безусловной оптимизации унимодальной разнозначной функции.

Приведем верхнюю и нижнюю оценки числа вычислений для алгоритма 1, в котором средний уровень определяется как среднее арифметическое крайних уровней исследуемого подпространства.

Теорема 1 [2]. Определение точки минимума ^ * унимодальной разнозначной на B 2 функции алгоритмом 1 метода отсечений требует вычисления ее значений не менее чем в C ⁿ / ² 1 + _n и не более чем в Т ₁ ( п ) точках B n ( п> 4):

• L ^log 2 ⁽ n ^{- 1)} J j .

• T 1 ( n ) = S C^J n‘ + n L log 2 ( n - 1) J ,

i = 1

где j о = 0 j i = \n /2 ] ; J; = f ( J; — I + J 1 )I2 \ ; i = 2, L log 2 ( n - 1) J .

Следствие 1 : li_m card B ² = ^ .

n ^~ T 1 ( n )

Следствие 2. T ₁ ( п ) <  2 ""' для п >  13.

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

Метод отсечений на уровне. Рассмотрим теперь возможность использования метода отсечений для задачи (1), (2). Для этого введем несколько новых определений и докажем утверждения необходимых для исследования свойств множества допустимых решений вида (2).

Лемма 4. Любая точка X е O m ( X ⁰) имеет только 2 к -соседние к себе точки, лежащие на этом же уровне точки X ⁰ . При этом число 2 к -соседних кХ точек, лежащих на т- м уровне X ⁰ , определяется формулой C_mC_n - m , k = 1,min{ m , n - m } .

Доказательство. Не нарушая общности суждений, можно считать, что X ⁰ есть точка со всеми нулевыми компонентами. Тогда все точки, лежащие на т- м уровне точки X ⁰ , имеют ровно т единичных компонент. Таким образом, множество всех точек уровня получается всевозможными перестановками нулей и единиц. При этом не трудно видеть, что каждая перестановка меняет значение одной нулевой и одной единичной компоненты. Это ведет к тому, что все точки отличаются между собой только четным числом компонент. Конкретное же число 2 к -соседних к Х точек, лежащих на т- м уровне X ⁰ , определяется прямым подсчетом числа возможных перестановок единичных компонент.

Следствие 3. Множество всех точек т-го уровня точки X0 е B-) может быть представлено как объединение всех 2к-соседних точек произвольной точки X е Om (X0). При этом l m kk Cn X CnCn - m , k=0

где l = min{ m , n - m } .

Доказательство. Следует непосредственно по лемме 1 и лемме 4.

Определение 9. Назовем множество всех точек, 2 к -соседних к X m и лежащих на т- м уровне точки X ⁰ , к -м условным уровнем (или к- м подуровнем) точки X_m е O_m ( X ) . Обозначим это множество O k ( x ° , X m ) = O m ( x 0 ) п о 2 k ( X m ) .

Лемма 5. V X е O_k ( X ⁰, X m ) :

O 2 ( X ) п O k - 1 ( X ⁰, X m ) = k ^{2 ,}

O 2 ( X ) п O k + 1 ( X ^, X m ) = ( m - k )( n - m - k ) ^, O 2 ( X ) п O k ( X ⁰, X ⁰) = k ( n - 2 k ) .

Доказательство. Первые два равенства получаются простым комбинаторными вычислениями. Для удобства подсчета за X ⁰ следует взять нулевую точку, а за X m - точку с т единичными компонентами на первых т местах. Последнее равенство также можно получить прямым подсчетом или как разность: m ( n - m ) - { k ² + ( m - k )( n - m - k )} , где m ( n - m ) = C m C n - _m - общее число двусоседних куточек, лежащих на O_m ( X ⁰) .

Определение 10. Точку X_m е B 2 будем называть ло- 0 n кальным минимумом т- го уровня точки X е B 2 , если V X е O m ( X ⁰) выполняется условие f ( X m ) <  f ( X ) .

Подобным же образом определения 4^8 переносятся на т- й уровень точки X ⁰ е B 2 .В этих определениях будет справедлив и аналог леммы 3 на уровне.

Нетрудно видеть, что любой к -й условный уровень точки X m е O_m ( X ⁰) ( k = 1,min{ m , n - m } - 1 ) разбивает множество O_m ( X ⁰) на два непустых непересекающихся подпространства, состоящих из объединения полных условных уровней точки X m :

к - 1                       min{ m , n - m }

V 1^m = и O i ( X ⁰ , X m ) , V m = U     O i ( X ⁰, X 0 ) .

i = 0                             i = к + 1

Заметим, что в соответствии с леммой 4 максимальное число условных уровней на т-м уровне точки Xm равно min{m, n - m} и не может превосходить и / 2, причем достигаться значение и / 2 может только на среднем уровне точки X0 для четных значений и. И, в отличие от распределения точек B2 по уровням точки X0, распределение точек на ее т-м уровне уже не будет симметрич- ным относительно какого-либо условного уровня, кро ме случая когда т = и / 2, а и - четное.

Обозначим через X m k точку, определяемую по ус *                      ,

I -

ловию f ( X m k ) = min f ( X ) . Иначе говоря, „ ’ X e O k ( X ⁰, X 0 )

точка X m k доставляет наименьшее значение функции К X) на к -м условном уровне точки X m . При этом она может быть не единственной.

Л емма 6. Для V к = 0,min{ m , n - m } - 2 , m = 2, n - 2 любая точка X ' e O k ( X ⁰, X m ) не имеет двусоседних точек на условном уровне O k ₊ 2 ( X ⁰, X m ) .

Доказательство. Не нарушая общности суждений, будем полагать, что у X0 все координаты нулевые, а Xm имеет ровно т единичных компонент, которые сто ят на первых т местах. Тогда любая точка X 'e Ok (X 0, Xm) будет иметь т-кединиц среди первых т компонент и к единиц среди последних (и - т) компонент. Любая же точка X"e Ok+2 (X0, Xm) будет иметь т - (к + 2) единиц среди первых т компонент и (к + 2) единицы среди последних (и - т) компонент. Таким образом, точки X', X" отличаются как минимум двумя компонентами, стоящими на первых т местах, и не менее чем двумя компонентами, стоящими на последних (и - т) позициях. Следовательно, эти точки четырехсоседние или имеют еще большее четное соседство.

Лемма 7. Если/(X)-унимодальнаяна Om(X0) функция и для некоторого Xe O1 (X0,Xm,к), k =11,min{m*n - m} -1    выполняется условие f (X) < f (Xm^), то точки X и Xm принадлежат одно-m му подпространству: V или V2 ■

_ Доказательство. Предположим противное: X e V ^m , X * e V m ._Таккак / ( X) -унимодальная на O_m ( X ⁰) функция, то из точки X всегда существует путь невозрастания W _ ^f ( X , X m ) = { X , X ¹, _ , X ^s , X m } с O m ( X ⁰1 . По определению, пути на уровне пары точек X и X 1, ..., X¹ и X^{1 + 1},... , X ^s и X_m являются двусоседними по отношению друг к другу. В соответствии с леммой 6 точка X , как и все точки подпространства V ^m , не имеет двусоседних точек в подпространстве V m и, следовательно, путь W _ ^f ( X , X_m ) не может проходить через подпространство V m .

Следствие 4. Если для псевдобулевой функции /Х ) существуют такие точки X 1 e O 1 ( X ⁰, X_m , k ) П O k - 1 ( X ⁰, X m ) и ^точк^а X 2 e O 1 ( X ° , X m , k ) A O k + 1 ( X ⁰, X m ) , ^что f ( X 1 ) <  f ( X m , k ), f ( X 2 ) <  f ( X m , k ) , ^{то ф}у^нкция / ^{( X )} имеет по крайней мере два локальных минимума X m ¹, X m ², где X m ¹ e V m , X m ² e V m .

Доказательство. Непосредственно следует по лемме 7.

Доказанные утверждения позволяют строить алгоритмы метода отсечений на уровне. Заметим, что все они являются аналогами утверждений, доказанных в [2; 5] для задачи безусловной псевдобулевой оптимизации. Однако одно из утверждений, справедливое для задачи безусловной оптимизации, не имеет аналога на уровне, так как не всегда выполняется на нем. Об этом утверждении бу дет сказано ниже.

Для унимодальной разнозначной на уровне O_m ( X ⁰) функции_ / ( X ) схема метода отсечений будет выглядеть следующим образом.

• 1.    Выбираем произвольную точку X m e O_m ( X ⁰) и некоторый ее условный уровень O k ( X ⁰, X m ) ( k = 1,min{ m , n - m } - 1 ). Полагаем I = 0 ,1L= min{ т , и-т }.

• 2.    Определяем X_m , k и X m , k по условиям:

f ( X m , k ) <  f ( X ) , V X e O k ( X ⁰, X m ) ,

• - П * f ( X k ) <  f ( X m , k ) ^,_{n n} X k e O 1 ( X ⁰, X m , k ) П { O k - 1 ( X ⁰, X m ) и O k + 1 ( X ⁰, X m )} .

• 3.    Если X k e O k - 1 ( X ⁰, X m l, то полагаем L = k , k = k - 1 ( 1 = 1, k - 1 - 1) .Е сли X k e O k + 1 ( X ⁰, X m ) , то полагаем l = k , k = k + 1 ( i = 1, L - k - 1) и переходим кп. 2.

• 4.    Останавливаем поиск.

Если X k не существует, то X m = X m k и переходим кп. 4.          _

Здесь I и L - номера первого и последнего условных уровней соответственно, рассматриваемых на каждом этапе подпространства.

Итак, схема метода отсечений на уровне подобна схеме метода отсечений для задачи без ограничений. Однако важно заметить, что для задачи (1), (2) поиск ведется до тех пор, пока исследуемое пространство не станет одним уровнем. И, в отличие от схемы метода для задачи безусловной оптимизации, здесь проверяется и последний уровень. Это отличие связано с тем, что на условных уровнях все точки имеют двусоседние к себе точки не только на соседних условных уровнях, но и на условном уровне, которому они принадлежат (см. лемму 5).

Как показали исследования метода отсечений на задаче без ограничений, оптимальным алгоритмом выбора отсекающих уровней здесь является алгоритм 3 [5]. Однако в связи с указанным выше отличием, аналог алгоритма 3 для задачи (1), (2) не будет иметь преимуществ перед аналогом алгоритма 2, где отсекающий уровень на каждом этапе разбивает исследуемое подпространство на два равномощных или максимально близких по мощности подпространства. Поэтому для решения задачи на уровне будем использовать алгоритм 2, превосходящий по своим оценкам алгоритм 1, который реализует схему выбора отсекающего уровня по правилу среднего арифметического номеров крайних уровней.

Теорема 2. Определение точки минимума X_m унимодальной разнозначной на O_m ( X ) функции алгоритмом 2 метода отсеченийтребует вычисления ее значений не менее чем в C mN ¹ C n - _m + { k ² + ( m - k )( n - m - k )} и не бол ее чем в 7 1 ^m ( n , m ) точках O_m ( X ⁰) с B 2 ( n >  4, m = 1, n - 1 ):

L ^lo § 2 ^{( s - 1)} J v v 7 m ( n , m) = E C mN C Nm +

=

Llog2 (s -1) J{ k 2 + (m - k)(n - m - k)}, где 5 = min{m, n - m} ;N.~ номера отсекающих уровней для наихудшего случая месторасположения Xm .

Доказательство. Оценка снизу в соответствии со схемой алгоритма и леммой 4 равна мощности первого из проверенных уровней ( C m ¹ C n - _m ) плюс множество двусоседнихк X_m точек,лежащихна O_m ( X ⁰) .Число последних равно k ² + ( m - k )( n - m - k ) (см. лемму 5).

Оценка сверху получена в соответствии со схемой алгоритма 2. Как было замечено выше, распределение точек по условным уровням не симметрично. Поэтому для конкретных значений п, т будем иметь конкретные распределения точек на уровне. При этом, очевидно, что для т-го и (п - т)- го уровней X 0 распределения совпадают. Заметим также, что в соответствии с формулой распределения точек на т-м уровне (CmCn-m ), чем больше т отличается от п / 2, тем больше первый и последующий за ним отсекающие уровни смещаются в сторону от точки xm.

Следствие 5:    li_m    card O m ^ X ^ = ^ .

n ^~ , m ^ n /2 T 1^m ( n , m )

Доказательство.

card O_m ( X ⁰) >

T m ( n , m ) "

>---------T—T--------------->

L log 2 ( 5 - 1) J{ C N ¹ C Nm + { k ² + ( m - k )( n - m - k )}

>

m C_n

L log 2 ( 5 - 1)J. C m ¹ C n - m

.

уровне выше (относительно мощности пространства решений), чем соответствующие оценки задачи без ограничений. Это связано с существенным различием в распределении точек по уровням точки X ⁰ в B 2 и по условным уровням ее конкретного уровня. Так, при т = п / 2 ( п- четное) оценка снизу для задачи (1), (2) составляет 1/(0,625 fn ) часть от множества допустимых решений, а для задачи безусловной оптимизации - только 1/(1,25 V n ) отмощности B 2 , т. е. ровно в два раза меньше.

Можно несколько сократить оценки снизу и сверху для задачи (1), (2), если разложить т- й уровень точки X ⁰ по условным уровням точки X m - 1 (или X m + 1 ), анепо подуровням X m ■ Число условных уровней останется прежним, но соседство с точкой X m - 1 (или X m ₊ 1 ) будет уже нечетным. При этом множество точек т- го уровня несколько перераспределится. Но такой прием не позволяет существенно улучшить оценки алгоритма и поэтому не представляет большого интереса для изучения.

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

Переходим к пределу и используем для замены

Г n /2 1 формулу, полученную в [5]:

Cn

2 ⁿ