On effectiveness of solving pseudo-boolean systems of linear inequalities by simulated annealing, balas algorithm and in.pdf Введение Одной из важных прикладных задач является решение псевдобулевых систем линейных неравенств (СЛН). Методы сведения булевых систем нелинейных уравнений (СНУ) к псевдобулевым СЛН предложены в [1, 2]. Общий метод решения СЛН для неотрицательных значений действительных переменных приведён в [3], однако его трудоёмкость не является полиномиальной в общем случае, верхняя оценка является экспоненциальной и эксперименты показывают быстрый рост числа экстремальных лучей при увеличении числа неравенств. Необходимость решения СЛН обусловила привлечение эвристических методов для решения СЛН. В частности, разработаны полиномиальные алгоритмы решения действительных СЛН, такие, как алгоритм Хачияна (эллипсоидов) [4], алгоритм Кармаркара (внутренней точки) [5]. Алгоритм Хачияна можно применить для решения псевдобулевых СЛН с использованием релаксационного подхода [6]. В работе исследуется возможность применения алгоритма Кармаркара для решения псевдобулевых СЛН. Нетривиальность указанной задачи обусловлена, во-первых, тем, что алгоритм Кармаркара в оригинальной публикации разработан для решения задач линейного программирования (ЛП), и, во-вторых, особенностями использования линейной целевой функции в вычислениях алгоритма Кармаркара. Напомним, что лобовое (стандартное) сведение решения СЛН к задаче ЛП требует минимизации кусочно-линейной целевой функции с линейными ограничениями. 1. Псевдобулевые системы линейных неравенств Определение 1. Под псевдобулевой системой линейных неравенств (ПСЛН) понимается система вида Ax ^ b, (1) где A е Zm,n - целочисленная матрица размера m x n с элементами aij, i = 1,... ,m, j = 1,... ,n, и b е Zm - целочисленный вектор. Искомые булевы переменные составляют вектор x е V2n. Рассмотрим функцию tob(x') : [0,1]n ^ V2n, которая отображает действительный вектор x' е [0,1]n в булев x е V2n покоординатно, т. е. xi = [[x'i]], где [[а]] - ближайшее к а по модулю целое число. Значение [[1/2]] определяется произвольным фиксированным образом. Определение 2. Под релаксацией ПСЛН будем понимать ослабление требования булевости переменных до произвольных действительных значений. Заметим, что такой приём является эвристическим и позволяет использовать для решения задачи алгоритмы, ориентированные на непрерывные переменные. Надёжность решения с использованием релаксации меньше единицы в силу ошибок округления при возврате в булеву область. Как правило, исследование надёжности алгоритмов, построенных на основе релаксации исходной задачи и последующего применения непрерывных алгоритмов, например алгоритмов решения непрерывных задач линейного программирования, представляет собой самостоятельную проблему. Экспериментальный анализ надёжности алгоритма решения ПСЛН с помощью алгоритма Кармаркара изложен далее в п.5. 2. Сведение задачи решения ПСЛН к стандартной задаче ЛП n Определение 3. Пусть задана некая линейная функция J(x) = £ CiXi на мноi=1 жестве U = {x Е Rn : Ax ^ b}. Задача ЛП заключается в нахождении минимума функции J (x) на множестве U, элементы которого называются допустимыми точками, решениями и т. п. Задачу ЛП можно записать следующим образом: J(x)-- inf : U = {x Е Rn : Ax ^ b}. Определение 4. Стандартной задачей ЛП (СЗЛП) называется задача ЛП вида т c x - min, ( Ax ^ b, (2) [x ^ 0, где x = (x1,..., xn )T Е Rn; c Е Zn; A Е Zm,n. Здесь и далее под векторами понимаются вектор-столбцы. Чтобы свести задачу решения ПСЛН к СЗЛП, используем следующие понятия. Определение 5. Невязкой линейного неравенства Ux ^ v, где U Е Zn и v Е Z, называется неотрицательная кусочно-линейная функция 0, если неравенство выполнено, FU,v(x) = < ТТ I v - Ux в противном случае. Определение 6. Невязкой системы линейных неравенств вида (1) называется m функция FA,b(x) = £ FAi,bi(x). i=1 Замечание 1. Как и невязка линейного неравенства, невязка ПСЛН, вообще говоря, не является линейной функцией. Однако в алгоритме Кармаркара по существу используется линейная целевая функция (ц.ф.). Введём в рассмотрение функцию g(A) : Rm,n - Rn, заданную следующим образом: m 9 (A) = У = (Уъ.. .,Уn), где Vi = £ ati. t=1 Традиционно, например в алгоритме Балаша, невязка СЛН для решения задачи ЛП используется в качестве её ц.ф. В алгоритме Кармаркара линейная ц.ф. по существу используется для вычисления очередного состояния алгоритма, поэтому применение невязок из алгоритмов Балаша и Хачияна (невязка в алгоритме Хачияна получается заменой суммирования на взятие максимума в определении 6) не представляется возможным. Поэтому в настоящей работе в качестве ц.ф. алгоритма Кармаркара используется линейная функция g(A)Tx. В качестве возможных вариантов ц.ф. в дальнейших исследованиях могут быть рассмотрены функции взятия среднего значения или взвешенная сумма. Алгоритм А1 описывает преобразование задачи решения ПСЛН к СЗЛП. Алгоритм 1. А1 Вход: A е Zm,n, b е Zm. Инициализация переменных A' е Zm+n>n, b' е Zm+n, c е Zn 1: A':=0, b' :=-1, c := 0 // покоординатная инициализация константами / 1... m- \\ 2: AM I'' j := A // добавление к матрице A' неравенств исходной системы. В левой части использовано обозначение для подматрицы матрицы A', образованной элементами на пересечении строк с номерами 1.. .m и столбцов с номерами 1.. .n 3: b' (1 ...m) := b. Релаксация исходной задачи // Заключается в ослаблении требований булевости к переменным ПСЛН, т.е. 0 ^ xi ^ 1. Ограничение x ^ 0 является требованием алгоритма Кармаркара. Для учёта ограничения x ^ 1 дополним систему n неравенствами вида xi ^ 1, i = 1, 2,... ,n, или, что то же самое, неравенствами - x ^ -1. 4: A' (i,i - m) := -1, i = m + 1,...,m + n. Вычисление коэффициентов линейной целевой функции 5: Для j = 1,... ,n 6: Для i =1,...m + n 7: cj : cj + A ij . Выход: A', b', c. 3. Сведение стандартной задачи линейного программирования к форме Кармаркара Определение 7. Формой Кармаркара задачи ЛП будем называть задачу ЛП, если она имеет вид T c x - mm, Ax = 0, Z xi = 1, i x ^ 0, где x = (xi,...,xn) е Rn, c е Zn, A е Zm,n. Сформулируем план действий по преобразованию СЗЛП к ЗЛП в форме Кармаркара, следуя [5]: 1) Рассмотрим двойственную к СЗЛП (2) задачу bT u - max, ATu ^ c, u > 0. 2) Комбинируем прямую и двойственную задачи: 'Ax ^ b, ATu ^ c, cTx - bTu = 0, x > 0, u > 0. Согласно теории двойственности, эта комбинированная задача допустима, если и только если исходная СЗЛП имеет конечный оптимум. 3) Введём вспомогательные переменные для перехода от неравенств к равенствам в системах ограничений: у Ax - y = b, ATu + v = c, cTx - bTu = 0, x ^ 0, v ^ 0, yy ^ 0, u ^ 0. 4) Введём фиктивную переменную А, чтобы получить внутреннюю допустимую начальную точку. Пусть x0,y0,v0,u0 - строго внутренние точки соответствующих неотрицательных ортантов размерностей n, m, n, m. Рассмотрим следующую задачу: A- min, 'Ax - y + (b - Ax0 + yo)A = b, ATu + v + (c - ATu0 + v0)A = c, cTx - bTu + (-cTx0 - bT u0)A = 0, I ^ 0, u ^ 0, y ^ 0, v ^ 0, A ^ 0. Заметим, что x = x0, y = y0, v = v0, u = u0, A =1 - строго внутреннее допустимое решение, которое можно выбрать в качестве начальной (стартовой) точки. Минимальное значение A равно 0, если и только если задача в п. 3 допустима. 5) Для удобства дальнейшего описания сделаем замену обозначений и запишем задачу из п. 4 в виде A2z = b2, z > 0, t c2 z-V min при ограничениях где m2 = m + n + 1; n2 = 2m + 2n +1; Ш2ХЯ2 Г (b - Ax0 + y0)mx1 A ■rLmxn 0mxm - E ^ mxm 0 A 2 = (c - ATu0 + v0) nx 1 0nxn AT nxm 0 E (- cTx0 - bTu0) T с u1xn bT u 1xm 0 0 zT = (A,x,u,y,v) и cT = (1,0,0,0,0) -векторы размера n2; bT = (b, c0) имеет размер m2. 6) Опишем отображение неотрицательного ортанта в симплекс. Пусть P+ = {z £ Rn2 : z ^ 0} -неотрицательный ортант, А = |z' £ Mn2+1 : z' ^ 0, n2 + 1 л Е z'i = 1 >. Обозначим через a = (1, x0, y0, v0, u0) некоторую строго внутреннюю i=1 ' точку P+. Зададим T : P+ - А следующим образом: пусть z' = T (z), тогда z' = = (z'l, . . . , z'n2 + 1) и / zi/ai ■ Л I ^ I z i = 1 i W-/-\\, 1 =1,...,n2, z n2 + 1 = 1 - E z i. 1 + E (zj/aj) i=1 Заметим, что отображение T обладает следующими свойствами: 1) T биективно. Обратное отображение T-1 (z') задаётся следующим образом: aiz i . Zi = -'-, г = 1,... ,n2. Z П2+1 ^ 2) T отображает точку a в центр симплекса а0 = -1, где I - вектор из единиц. П2 + 1 Выражая переменные zi через - i в системе из п. 5, получаем ' AA2- = 0, !-2 Е z'i = 1, i= 1 . zZ > 0, где A2 = (A2 ■ diag (ai,..., a^), -b2). Завершает приведение СЗЛП к форме Кармаркара преобразование целевой функции c^z в c2Tz', где (c2)i = (c2)iai для г = 1,..., n и (c2)n2+1 = 0. Замечание 2. Если применение алгоритма внутренней точки к этой задаче даст решение с нулевым значением c'2Tz', то обратное отображение T-1 даст оптимальное решение исходной задачи. В случае получения решения с положительным значением целевой функции исходная задача не имеет конечного оптимума, т. е. либо она недопустима, либо не ограничена. 4. Алгоритм внутренней точки для решения ПСЛН Алгоритм внутренней точки опубликован в 1984 г. [5]. Он имеет полиномиальную сложность. Этот алгоритм в идейном плане близок к алгоритму эллипсоидов и применяется к задачам линейного программирования, приведённым к некоторой специальной форме. Кармаркар предложил свой алгоритм в качестве замены алгоритма эллипсоидов, поскольку последний имеет проигрыш по времени работы по отношению к алгоритму внутренней точки порядка O(n2'5). Алгоритм 2 вырабатывает последовательность точек x(0), x(1),... x(i),... пространства поиска. Алгоритм 2. Алгоритм внутренней точки для решения ПСЛН Вход: ПСЛН с m неравенствами и n переменными. Выход: решение ПСЛН или символ 1: С помощью алгоритма А1 преобразовать задачу решения ПСЛН в СЗЛП. 2: С помощью процедуры п. 3 преобразовать СЗЛП в форму Кармаркара. 3: Задать стартовую точку x(0) := а0 (центр симплекса в пространстве размерности 2 (m + 2n + 1)), г := 0. 4: Вычислить очередную точку последовательности: г := г + 1, x(i) := // Функция p полностью соответствует оригинальному описанию [5] и здесь не приводится. Это же замечание справедливо для следующих двух шагов. 5: Проверить допустимость полученного результата. Если не выполняется условие допустимости x(i), то завершить алгоритм и вернуть 6: Проверить оптимальность. Если не выполняется условие оптимальности для x(i), то перейти на шаг 4. 7: Преобразовать полученное решение в решение ПСЛН. Пусть z £ Rn2+1 -решение задачи ЛП в форме Кармаркара, полученное в результате работы алгоритма Кармаркара, а z' = z (2,... , n + 1) -подвектор этого решения размерности n, где n - число неизвестных исходной СЗЛП. Тогда решением исходной СЗЛП является вектор x £ Rn, такой, что zj (a0)j . xj = -, J = 1, ... ,n. zn2+1 Переход к булевому решению исходной ПСЛН заключается в применении к вектору x функции tob. 5. Сравнение надёжностей решения ПСЛН алгоритмами внутренней точки, имитации отжига, Балаша и БИО Для оценки надёжности описанного выше способа (использующего эвристические приемы) применения алгоритма внутренней точки (АВТ) к решению ПСЛН проведены экспериментальные исследования. План эксперимента в точности совпадает с таковым из работы [7], что позволяет провести сравнительный анализ надёжности АВТ с другими ранее применёнными эвристическими алгоритмами. Для АВТ используются значения параметров a = 0,25, q = 5, все координаты векторов x0, y0, v0, u0 выбраны равными 2. План эксперимента предполагает применение алгоритма к 9600 случайным совместным ПСЛН, которые разбиваются на 12 серий по 800 систем в зависимости от сочетания трёх параметров. Один из этих параметров ограничивает максимальный абсолютный вес коэффициентов, остальные подробно описаны в [7]. В каждой серии системы делятся на 8 подсерий по 100 систем. Подсерия определяется числом переменных (30 или 60) и числом неравенств, которое выражается через число переменных с помощью мультипликативного фактора со значениями 1, 2, 3, 10. Смысл рассмотрения двух выбранных вариантов числа переменных заключается в том, что число переменных 30 позволяет перебрать все булевы векторы этой размерности, следовательно, при увеличении числа шагов эвристического алгоритма доля опробованных векторов может составить заметную долю всего пространства поиска. Для 60 переменных перебрать за приемлемое время на персональном компьютере сколько-нибудь заметную часть пространства поиска не представляется возможным. В работах [7, 8] произведено сравнение надёжностей эвристических алгоритмов имитации отжига, Балаша и их сочетания, названного в [8] алгоритмом БИО. Последний применялся в двух вариантах - с различными целевыми функциями (невязками) на основе суммирования или взятия максимума. Результаты экспериментов продемонстрировали преимущество алгоритма БИО, хотя по скорости работы он уступает алгоритму Балаша. По этим соображениям, а также с целью придания большей наглядности АВТ сравнивается ниже только с алгоритмом БИО, который вычисляет невязку системы как сумму невязок отдельных неравенств. Результаты этого сравнения по сериям и факторам приведены в табл. 1. Средняя надёжность АВТ превосходит надежность алгоритма БИО на 2%, что может считаться статистической погрешностью, и по этому показателю оба алгоритма не имеют явных преимуществ друг перед другом. Однако только в двух сериях (7 и 8) АВТ проигрывает БИО со средним проигрышем 73%. В остальных 10 сериях АВТ выигрывает у БИО со средним значением выигрыша 16 % (при этом средняя надёжность по 10 сериям равна 99 %). Такое контрастное поведение АВТ не характерно для других рассмотренных в [7, 8] алгоритмов, для которых надёжность ни по одной подсерии не падает ниже 50 %. АВТ демонстрирует относительную независимость надёжности решения от размера системы, в то время как другие эвристические алгоритмы более чувствительны Таблица 1 Сравнение усреднённых значений надёжностей АВТ и БИО по сериям и в зависимости от размера системы Серия Отношение числа неравенств к числу переменных Итого 1 2 3 10 БИО АВТ БИО АВТ БИО АВТ БИО АВТ БИО АВТ 1 57% 99% 96% 100% 100% 100% 100% 100% 88% 100% 2 48% 99% 78% 100% 92% 100% 96% 100% 78% 100% 3 33% 100% 93% 100% 100% 100% 100% 100% 82% 100% 4 36% 100% 91% 100% 100% 100% 100% 100% 82% 100% 5 33% 100% 94% 100% 100% 100% 100% 100% 82% 100% 6 26% 100% 91% 100% 100% 100% 100% 100% 79% 100% 7 100% 17% 100% 7% 99% 6% 100% 80% 100% 28% 8 100% 4% 99% 1% 97% 1% 100% 96% 99% 26% 9 41% 71% 95% 100% 100% 100% 100% 100% 84% 93% 10 42% 75% 94% 100% 100% 100% 100% 100% 84% 94% 11 34% 99% 91% 99% 99% 100% 100% 100% 81% 100% 12 34% 99% 93% 100% 100% 100% 100% 100% 82% 100% Итого 49% 80% 93% 84% 99% 84% 100% 98% 85% 86% к этому показателю, хотя для переопределённых систем (с фактором 10) все алгоритмы успешно справляются почти со всеми системами. По результатам работы [7] можно убедиться, что разные эвристические алгоритмы по-разному добиваются успеха. Так, таблица корреляции успехов из [7] показывает, что 22 % всех систем не решили оба алгоритма (имитации отжига и Балаша), однако алгоритм отжига решил 15% от общего числа систем, которые не решил алгоритм Балаша. Аналогично, алгоритм Балаш решил 2 % систем, с которыми не справился алгоритм имитации отжига. Экспериментальный анализ АВТ позволил выявить две труднорешаемые им серии систем. В табл. 2 приводятся сведения о суммарном покрытии в смысле решения систем линейных неравенств обоими алгоритмами (БИО и АВТ). Для наглядности приведены результаты как для варианта алгоритма БИО со взятием максимума (БИО MAX), так и для варианта с суммированием при вычислении невязки (БИО SUM). Легко видеть, что в каждой серии есть задачи, которые представляют трудности для каждого алгоритма. Так, в первой и второй сериях ни одним алгоритмом не решены одни и те же четыре системы. В то же время суммарное покрытие для АВТ и БИО SUM составило 98,9 %. Серии 7 и 8 оказались трудны для АВТ, БИО MAX справился с ними более чем в 2 раза эффективнее, а БИО SUM решил практически все системы из этих серий (доля нерешённых 0,7%). С другой стороны, по сериям 3-6 АВТ решил все 609 систем, с которыми не справился алгоритм БИО SUM, и показал на этих сериях надёжность 100 %. Таблица 2 Суммарное покрытие СЛН алгоритмом БИО и АВТ Серия Количество нерешённых задач АВТ АВТ и БИО МАХ АВТ и БИО SUM % шт. % шт. % шт. 1 0,4 3 0,4 3 0,4 3 2 0,1 1 0,1 1 0,1 1 3, 4, 5, 6 0 0 0 7 72,6 581 25,0 200 0,4 3 8 74,6 597 23,8 190 1,0 8 9 7,4 59 5,0 40 6,0 48 10 6,4 51 4,8 38 5,8 46 11 0,2 2 0 0,1 1 12 1,1 9 0,1 1 0 Итого 13,6 1303 4,9 473 1,1 110 Заключение Проведённое исследование показало, что алгоритм внутренней точки может быть применен к задаче решения псевдобулевых систем линейных неравенств в модифицированном виде, так как оригинальный алгоритм не рассчитан на решение дискретных задач. Модификация характеризуется высокой средней надёжностью решения ПСЛН - 86 %. Аналогичные показатели имеет и другой эвристический алгоритм БИО с невязкой на основе суммирования, сочетающий в своем поведении алгоритмы Балаша и имитации отжига. Детальный анализ выявляет, что как для модификации алгоритма внутренней точки, так и для алгоритма БИО находятся псевдобулевы системы линейных неравенств, которые один алгоритм решает, а другой нет. В целом, оба алгоритма не справились только с 1,1 % систем, поэтому в качестве практической рекомендации при решении ПСЛН можно предложить последовательное использование алгоритмов внутренней точки и БИО. Отметим, что алгоритм внутренней точки требует проведения большого числа матричных вычислений, при этом размерности матриц в соответствии с выбранным способом сведения исходной задачи решения ПСЛН к форме Кармаркара задачи линейного программирования включают в себя сумму числа неравенств и числа переменных. Указанное обстоятельство может приводить к значительным затратам (или даже нехватке) вычислительных ресурсов при больших значениях указанных параметров СЛН, решаемых с помощью алгоритма внутренней точки.

Скачать электронную версию публикации