Использование Prolog и CLP(R) для системы ограничений

Я хочу использовать Prolog для генерации случайного вектора, удовлетворяющего системе ограничений.

Например, наш пользователь может предоставить нашему программному обеспечению следующую информацию во время выполнения:

Учитывая вектор <x1, x2, x3, ... x30>, у нас может быть два ограничения:

x1 > x2 + x3 + x4
x5 <= sin(x6 + x7)

то, что я хотел бы сделать, это создать программу Prolog, которая примерно соответствует форме:

:- random(0.0, 1.0, X1)
:- random(0.0, 1.0, X2)
#...
# its also concievable that the bounds are different than 0 to 1
:- random(0.0, 1.0, X30)

clp(r) :- constraints { 
   X1 > X2 + X3 + X4,
   X5 <= sin(X6 + X7)   
}

?- [ X1, X2, X3, X4, ... X30 ]

который выведет равномерно случайный вектор в 30-мерном пространстве.

Возможно ли это с помощью Пролога?

Существует также проблема потребления этого вывода. Что я хотел бы сделать, так это вызвать next() повторную генерацию нового вектора. В частности, мне нужно избегать перекомпиляции, так как я хотел бы иметь возможность генерировать примерно 10 000 таких векторов в секунду. Могу ли я достичь такого уровня производительности?

Я надеюсь использовать встроенный (в процессе) экземпляр SWI-Prolog на JVM, на котором работает остальная часть нашего программного обеспечения. Будет ли этого достаточно?


person Groostav    schedule 08.05.2017    source источник


Ответы (1)


It's OK!

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

Однако есть несколько тонкостей, которые необходимо решить.

Во-первых, давайте правильно разработаем синтаксис CLP(R):

vector([X1,X2,X3,X4,X5,X6,X7]) :-
        { X1 > X2 + X3 + X4,
          X5 =< sin(X6 + X7) }.

Обратите особое внимание на использование =<, а также на правильное использование {}/1 для обозначения ограничений CLP(R). Маркер <= избегается в арифметике Пролога, потому что он выглядит как стрелка, которая обычно обозначает импликацию в доказывающих.

Этого достаточно, чтобы получить первые ответы, даже если они еще не преобразованы в конкретные решения:

?- vector(Ls).
Ls = [_1028, _1034, _1040, _1046, _1052, _1058, _1064],
{_1046=_1028-_1034-_1040-_1088, _1088>0.0},
{_1052-sin(_1058+_1064)=<0.0},
{_1052-sin(_1058+_1064)=<0.0},
{_1052-sin(_1058+_1064)=<0.0}.

Используя random/1, мы можем присвоить случайные числа с плавающей запятой из (0,1) любой из переменных. Например:

?- vector([A,B,C,D,E,F,G]),
   random(A),
   random(B).
A = 0.33797712696696053,
B = 0.7039688010209147,
{D= -0.3659916740539542-C-_894, _894>0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0}.

Это решает одну часть задачи. Однако этот метод подводит нас в таких случаях, как:

?- vector([A,B,C,D,E,F,G]),
   random(A),
   random(B),
   random(C),
   random(D).
false.

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

zero_to_one(X) :- { 0 =< X, X =< 1 }.

Мы можем просто указать это ограничение как одно дополнительное требование:

?- vector([A,B,C,D,E,F,G]),
   maplist(zero_to_one, [A,B,C,D,E,F,G]),
   random(A),
   random(B),
   random(C).

Это снова дает false.

Способ 1: Больше того же

Один из способов решить описанную выше проблему — просто повторять рандомизированное назначение до тех пор, пока не будет найдено решение при возврате:

?- vector([A,B,C,D,E,F,G]),
   maplist(zero_to_one, [A,B,C,D,E,F,G]),
   random(A),
   random(B),
   repeat,
      random(C).
A = 0.9433451780634803,
B = 0.15859272177823736,
C = 0.706502025956454,
{D>=0.0, _2064=0.07825043032878898-D, D<0.07825043032878898},
{E>=0.0, E=<1.0, F>=0.0, F==0.0, G=<1.0, E-sin(...)=<0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0} .

Таким образом, мы на шаг ближе к конкретному решению, под которым мы подразумеваем полную реализацию вектора. Недостатки довольно очевидны: в крайних случаях мы никогда не найдем правильное присваивание таким образом. Если повезет, может потребоваться много попыток найти конкретное значение даже для одной дополнительной переменной.

Способ 2: максимизировать или минимизировать

Другой способ решить эту проблему — использовать maximize/1 и/или minimize/1 из CLP(R), чтобы использовать сам решатель ограничений для получения конкретных решений. Это работает только для линейных ограничений, и даже не для всех из них. Например, рассмотрим следующие запросы:

?- { X = sin(Y) },
   maplist(zero_to_one, [X,Y]),
   maximize(X).
false.

И даже:

?- { X < 1 }, maximize(X).
false.

Хотя в отличие:

?- { X =< 1 }, maximize(X).
X = 1.0 .

Теперь давайте воспользуемся следующим трюком, чтобы избавиться от всех нелинейных ограничений: мы просто назначаем случайные числа с плавающей запятой для X6 и X7, используя, например:

?- vector(Ls),
   Ls = [A,B,C,D,E,F,G],
   maplist(zero_to_one, Ls),
   random(F), random(G).

Опираясь на это, мы можем написать:

?- vector(Ls),
   Ls = [A,B,C,D,E,F,G],
   maplist(zero_to_one, Ls),
   random(F), random(G),
   maximize(A), minimize(B+C+D+E).
Ls = [1.0, 0.0, 0.0, 0.0, 0.0, 0.9702069686491169, 0.13220925936558517],
A = 1.0,
B = C, C = D, D = E, E = 0.0,
F = 0.9702069686491169,
G = 0.13220925936558517 .

Таким образом, мы получили конкретное решение, удовлетворяющее всем ограничениям и имеющее некоторые случайные составляющие.

Заключительные замечания

Во-первых, повторюсь, я думаю, что Prolog — хороший выбор для таких задач. Сокращение с помощью решателя ограничений может помочь устранить большие части пространства поиска, а сам решатель ограничений может помочь вам получить конкретные решения путем минимизации и максимизации. Во-вторых, есть еще несколько вопросов, о которых вам нужно помнить:

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

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

person mat    schedule 08.05.2017
comment
так что minimize и maximize даже в ситуациях, когда минимизация и максимизация не нужны сами по себе? - person Erik Kaplun; 03.10.2020