Минимизировать/максимально возможно в clojure/core.logic?

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

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

В настоящее время я смотрю на core.logic и у меня сложилось впечатление, что модуль не будет выполнять ни макс, ни миним. Насколько я понимаю, эта функциональность обычно обозначается как CLP. В Core.logic упоминается CLP(FD) (https://github.com/clojure/core.logic/wiki/Features), но, глядя на описание, у меня возникают серьезные сомнения.

Может ли кто-нибудь прокомментировать это, поскольку, я думаю, мне было бы слишком много читать всю книгу Reasoned Schemer?


clojure clojure-core.logic
person vanhemt    schedule 09.05.2020    source источник
comment
Не могли бы вы привести пример задачи оптимизации, которая представляет тип проблемы, которую вы хотите решить? Что такое целевая функция? Каковы ограничения? Неизвестные вещественные или целые?   -  person Rulle    schedule 10.05.2020
comment
@Rulle Например, спецификация, в которой вам нужно найти оптимальное сочетание из множества потенциальных поставщиков, каждый из которых предлагает какой-либо необходимый товар, но цена и качество в каждом случае различаются. Итак, вы хотите минимизировать затраты, соблюдая при этом стандарты качества.   -  person vanhemt    schedule 10.05.2020
comment
Это похоже на линейное программирование (en.wikipedia.org/wiki/Linear_programming) проблема для меня. И ojAlgo, о котором я упоминал в своем ответе, подходит для этого. Если вы конкретно и точно укажете, какова целевая функция, что это за предметы, каковы стандарты качества и т. Д., Тогда кто-то сможет помочь.   -  person Rulle    schedule 10.05.2020
comment
Спасибо. Думаю, мне придется поиграть с библиотекой, которую вы предлагаете, прежде чем я смогу задать хороший вопрос.   -  person vanhemt    schedule 10.05.2020
comment
Пожалуйста. Я предлагаю вам начать с перечисления ваших переменных, которые, вероятно, будут количеством каждого товара от каждого поставщика. Целевой функцией для минимизации будет сумма всех количеств, взвешенных по их цене за единицу. И тогда будет одно ограничение линейного неравенства для каждого типа элемента для минимально приемлемого качества. Вы можете использовать пример в моем ответе в качестве шаблона.   -  person Rulle    schedule 11.05.2020
comment
@Rulle На самом деле у меня есть вопрос. Есть ли способ настроить пример так, чтобы минимизировать возвращаемое значение функции Clojure? Допустим, функция возвращает (+ x (* y 2)). Итак, тот же смысл, но как бы вы передали в ojAlgo вектор аргументов?   -  person vanhemt    schedule 12.05.2020
comment
В ojAlgo нет функций для разбора (+ x (* y 2)). Конечно, пока форма вашей проблемы является целевой функцией членов с линейными и квадратичными членами и линейными ограничениями, вы можете легко написать анализатор самостоятельно для преобразования таких выражений, как (+ x (* y 2)), в вызовы .addExpression, .set и т. д. Но если у вас просто есть функция Clojure, которую вы хотите свести к минимуму, и вы не знаете ее реализацию, вам придется использовать какой-то другой алгоритм, например CMA-ES.   -  person Rulle    schedule 12.05.2020
comment
Значит, это парсер. Функция будет сгенерирована только во время выполнения. Спасибо.   -  person vanhemt    schedule 12.05.2020
comment
Поскольку вы анализируете структуру данных, такую ​​как (+ (* y 2)), вы можете использовать Spec (clojure.org/guides/spec), чтобы убедиться, что это действительное выражение, которое может обработать решатель.   -  person Rulle    schedule 12.05.2020

Ответы (1)


arrow_upward
1
arrow_downward

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

Однако многие задачи оптимизации, возникающие в технике, состоят из целевых функций с линейными и квадратичными членами, линейными ограничениями, действительными и целыми переменными. Библиотека ojAlgo отлично подходит для решения этих проблем. Например, если мы хотим минимизировать f(x, y) = x + 2y с целыми числами x и y и тремя линейными ограничениями x >= 2, y >= 3 и x + y >= 14.2, вот как решить эту проблему с помощью ojAlgo в Clojure:

(ns playground.ojalgo
  (:import [org.ojalgo.optimisation ExpressionsBasedModel]))

(defn demo []
  (let [model (ExpressionsBasedModel.)
        ;; Declare variables

        ;; X has lower limit 2
        x (-> (.addVariable model)
              (.lower 2)
              (.integer true))

        ;; Y has lower limit 3
        y (-> (.addVariable model)
              (.lower 3)
              (.integer true))]

    ;; Objective function: Minimize x + 2y
    (-> (.addExpression model)
        (.set x 1.0)
        (.set y 2.0)
        (.weight 1.0)) ;; <-- Terms in the objective function
                       ;;     need a weight.

    ;; Linear constraint: x + y >= 14.2
    (-> (.addExpression model)
        (.set x 1.0)
        (.set y 1.0)
        (.lower 14.2))

    (let [result (.minimise model)]
      (println "Result" result)
      (println "Objective function value: " (.getValue result))
      (println "Optimal X value: " (.getValue x))
      (println "Optimal Y value: " (.getValue y)))))

Который будет отображать

Result #object[org.ojalgo.optimisation.Optimisation$Result 0xb755873 OPTIMAL 18.0 @ { 12, 3 }]
Objective function value:  18.0
Optimal X value:  12M
Optimal Y value:  3M

Скорее всего, ваша проблема (расплывчато сформулированная как "расход бензина на маршруте, который также должен удовлетворять другим ограничениям") может быть выражена в формате, который может обрабатывать этот решатель. Но без подробностей трудно дать более точный ответ, чем этот.

Чтобы использовать ojAlgo, вам нужно добавить зависимость [org.ojalgo/ojalgo "48.1.0"] к вашему файлу Leiningen project.clj.

person Rulle    schedule 10.05.2020
comment
Спасибо. Я думаю, что этого функционала достаточно. Задача, которую я решаю, довольно проста с математической точки зрения - я просто был удивлен, что родной инструмент Clojure не покрывает случай, когда кого-то интересует оптимальное решение. - person vanhemt; 10.05.2020