Использование prolog & clpr для системы ограничений

Question

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

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

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

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

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

:- 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() заново сгенерировать новый вектор. В частности, мне нужно избегать перекомпиляции, так как я хотел бы иметь возможность генерировать примерно 10000 этих векторов в секунду. Могу ли я достичь этого уровня производительности?

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

Answer 1

Все нормально!

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

Однако есть несколько тонкостей, которые вам нужно решить.

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

вектор ([X1,X2,X3,X4,X5,X6,X7]):-
        { X1 > X2 + X3 + X4,
          Х5 = <грех (Х6 + Х7)}.

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

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

? - вектор (Ls).
Ls = [_1028, _1034, _1040, _1046, _1052, _1058, _1064],
{_1046 = _1028-_1034-_1040-_1088, _1088> 0.0},
{_1052-син (+_1058 _1064)=<0,0},
{_1052-син (+_1058 _1064)=<0,0},
{_1052-син (+_1058 _1064)=<0,0}.

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

? - вектор ([A,B,C,D,E,F,G]),
   случайное (А),
   случайным образом (В).
A = 0,33797712696696053, 
 B = 0,7039688010209147,
{D = -0,3659916740539542-C-_894, _894>0,0},
{Е-син (F+G)=<0,0},
{Е-син (F+G)=<0,0},
{Е-син (F+G)=<0,0}.

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

? - вектор ([A,B,C,D,E,F,G]),
   случайное (А),
   случайным образом (В),
   случайное (С),
   случайным образом (D).
ложный.

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

zero_to_one (X): - {0 = 
Мы можем просто сформулировать это ограничение как одно дополнительное требование:
? - вектор ([A,B,C,D,E,F,G]),
   maplist (zero_to_one, [A, B, C, D, E, F, G]),
   случайное (А),
   случайным образом (В),
   случайное (С).
Это снова дает false,
 Способ 1: больше того же самого 
Одним из способов решения вышеуказанной проблемы является простое повторение рандомизированного назначения до тех пор, пока не будет найдено решение по возврату:
? - вектор ([A,B,C,D,E,F,G]),
   maplist(zero_to_one, [A,B,C,D,E,F,G]),
   случайное (А),
   случайным образом (В),
   повторить,
      случайное (С).
A = 0,9433451780634803,
B = 0,15859272177823736,
С = 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},
{Е-син (F+G)=<0,0},
{Е-син (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]),
   максимизировать (Х).
ложный.
И даже:
? - {X <1}, развернуть (X).
ложь
Хотя в отличие
?- { X =< 1 }, развернуть (X).
Х = 1,0.
Теперь давайте воспользуемся следующим приемом, чтобы избавиться от всех нелинейных ограничений: мы просто назначаем случайные числа с плавающей точкой X6 а также X7 используя, например:
? - вектор (Ls),
   Ls = [A,B,C,D,E,F,G],
   maplist(zero_to_one, Ls),
   случайный (F), случайный (G).
Основываясь на этом, мы можем написать:
? - вектор (Ls),
   Ls = [A,B,C,D,E,F,G],
   maplist(zero_to_one, Ls),
   случайный (F), случайный (G),
   максимизировать (A), минимизировать (B + C + D + E).
Ls = [1,0, 0,0, 0,0, 0,0, 0,0, 0,9702069686491169, 0,13220925936558517],
А = 1,0,
B = C, C = D, D = E, E = 0.0,
F = 0,9702069686491169,
G = 0,13220925936558517 .
Таким образом, мы получили конкретное решение, которое удовлетворяет всем ограничениям и имеет некоторые случайные компоненты.
 Заключительные замечания 
Во-первых, повторюсь, я думаю, Пролог является хорошим выбором для таких задач. Сокращение с помощью решателя ограничений может помочь исключить большие части пространства поиска, а сам решатель ограничений может помочь вам получить конкретные решения путем минимизации и максимизации. Во-вторых, есть еще несколько вопросов, которые нужно иметь в виду:
 Во-первых, решения, сгенерированные таким образом (любым способом), не являются случайными в том смысле, что каждое решение одинаково вероятно. Скорее, могут быть кластеры решений, которые могут появиться с большей вероятностью, чем другие. 
 Как показано выше, уравнения могут потребовать некоторых дополнительных рассуждений и экспериментов, как для сведения их к линейным уравнениям, так и для применения применимого направления оптимизации. Пролог хорошо подходит для таких рассуждений, и вы можете использовать его, чтобы легко попробовать разные стратегии. 
 Возможно, вам придется найти компромисс между рандомизацией и детерминированной оптимизацией для создания экземпляров оставшихся векторных компонентов. Компромисс может также зависеть от запутанности компонентов вектора. 
Наконец, очень важное замечание: неявные случайные состояния идут вразрез со свойствами, которые мы ожидаем от логических отношений, поскольку они могут привести к тому, что ваши предикаты будут вести себя совершенно по-разному при последующих вызовах, делая отладку и систематическое тестирование кошмаром. Поэтому я настоятельно рекомендую вам предусмотреть случайное начальное число или оставить в коде явное состояние генератора случайных чисел. Это поможет вам лучше понять поведение вашей программы и сделать ее полностью детерминированной. Позже вы можете изменить начальное число для создания различных коллекций решений.