Практическое приложение для решателя ограничений. Изучение других технологий может сэкономить вам несколько дней на очистку данных и обучение модели.

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

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

Решение реальной проблемы

Рассмотрим фактическую и весьма актуальную проблему.

Пандемия растет. Больницы должны быстро организовываться для лечения больных.

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

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

Однако у такого подхода есть недостатки:

  • Модель нуждается в обучении, следовательно, необходимы исторические данные по предыдущим случаям,
  • Было бы потрачено много времени на очистку и консолидацию набора данных,
  • Потребуется протестировать различные архитектуры с помощью длительных тренировок.

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

Заявление об ограничении ответственности: цель этой публикации - кратко рассказать о CSP. Теория и постановка проблемы будут сильно упущены. Для более строгого подхода см. [2] [3] [4].

Абстрагирование от проблемы

В этом посте будет мягкое введение в программирование с ограничениями с целью разрешить этот пример. Эта карта пандемии (1) иллюстрирует результат нашего алгоритма, который сопоставляет инфицированных людей с больницами. Существует несколько структур для решения ограничений. Инструменты оптимизации Google (также известные как OR-Tools) - это программный пакет с открытым исходным кодом для решения задач комбинаторной оптимизации. Наша проблема будет смоделирована с использованием этого фреймворка на Python.

from ortools.sat.python import cp_model


Просмотрите интерактивную записную книжку для этого сообщения
Подберите больных и больницы во время пандемии colab.research.google.com



Параметры

А пока давайте упростим задачу до 4 параметров (1):

  • Расположение зараженных людей
  • Степень тяжести зараженных людей
  • Расположение больниц
  • Количество коек в каждой больнице

Давайте определим эти параметры в Python:

# Number of hospitals
n_hospitals = 3
# Number of infected people
n_patients = 200
# Number of beds in every hospital
n_beds_in_hospitals = [30,50,20]
# Location of infected people -- random integer tuple (x,y)
patients_loc = [(randint(0, 100), randint(0, 100)) for _ in range(n_patients)]
# Location of hospitals -- random integer tuple (x,y)
hospitals_loc = [(randint(0, 100), randint(0, 100)) for _ in range(n_hospitals)]  
# Illness severity -- 1 = mild -> 5 = severe
patients_severity = [randint(1, 5) for _ in range(n_patients)]

Переменные

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

  • Пусть Я будет множеством больниц
  • Пусть Jᵢ будет набором коек в больнице i
  • Пусть K будет набором пациентов.

Определим как наше индексированное семейство переменных:

Если в больнице i, кровать j занимает человек k, тогда xᵢⱼₖ = 1. Чтобы связать каждую койку в больнице с больным человеком, цель состоит в том, чтобы найти набор переменных, который удовлетворяет всем нашим ограничениям.

Мы можем добавить эти переменные в нашу модель:

model = cp_model.CpModel()
x = {}
for i in range(n_hospitals):
  for j in range(n_beds_in_hospitals[i]):
    for k in range(n_patients):
      x[(i,j,k)] = model.NewBoolVar("x(%d,%d,%d)" % (i,j,k))

Жесткие ограничения

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

  • На каждой кровати должен находиться максимум один человек,
  • Каждому человеку должна быть назначена максимум односпальная кровать.

Давайте сосредоточимся на первом жестком ограничении. Для каждой койки j в каждой больнице i:

  • Либо есть уникальный пациент k,
  • Либо кровать пуста.

Следовательно, это можно выразить следующим образом:

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

Затем это неравенство можно добавить к нашей модели.

# Each bed must host at most one person
for i in range(n_hospitals):
  for j in range(n_beds_in_hospitals[i]):
    model.Add(sum(x[(i,j,k)] for k in range(n_patients)) <= 1)

Затем второе жесткое ограничение: для каждого пациента k:

  • Либо он находится в уникальной койке j в уникальной больнице i,
  • Либо он дома.

Таким же образом можно перевести в целочисленное неравенство:

Наконец, это ограничение можно добавить в модель.

# Each person must be placed in at most one bed
for k in range(n_patients):
  inner_sum = []
  for i in range(n_hospitals):
    inner_sum.append(sum(x[(i,j,k)] for j in range(n_beds_in_hospitals[i]))) 
  model.Add(sum(inner_sum) <= 1)

Мягкие ограничения

Далее, есть мягкие ограничения. Это очень желательно: наше решение должно пытаться удовлетворить их как можно больше, но они не являются необходимыми для поиска решения:

  • Каждого больного следует уложить в кровать,
  • С каждым человеком должен работать ближайший госпиталь,
  • Больных в тяжелом состоянии следует лечить в первую очередь, когда не хватает коек.

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

Пусть Ω - множество всех решений, удовлетворяющих жестким ограничениям.

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

С каждым человеком должна обращаться ближайшая больница, чтобы минимизировать расстояние между каждым пациентом и назначенной ему больницей.

При нехватке коек в первую очередь следует обращаться с больными в тяжелом состоянии, чтобы максимально повысить общую тяжесть состояния всех обслуживаемых пациентов. Обозначая sev (k) степень тяжести пациента k:

Тогда мы можем свести все мягкие ограничения к одной цели:

Тогда нужно быть осторожным: эти мягкие ограничения не относятся к одной и той же области.

  • Ограничение максимизации пациентов варьируется от 0 до n, где n - количество пациентов,
  • Ограничение серьезности варьируется от 0 до 5n.
  • Ограничение расстояния варьируется от 0 до максимального евклидова расстояния для всех i и k.

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

Вот соответствующий код:

# Integer distance function
idist = lambda xy1, xy2: int(((xy1[0]-xy2[0])**2 + (xy1[1]-xy2[1])**2)**0.5)
# Gain factors (1/penalty factors)
gain_max_patients = 140
gain_severity = int(140/5)
gain_distance = -1
# Maximization objective
soft_csts = []
for i in range(n_hospitals):
  for j in range(n_beds_in_hospitals[i]):
    for k in range(n_patients):
      factor = \
        gain_max_patients \
        + gain_distance * idist(hospitals_loc[i], patients_loc[k]) \
        + gain_severity * patients_severity[k]
      soft_csts.append(factor * x[(i,j,k)])
model.Maximize(sum(soft_csts))

Решатель

Теперь мы можем запустить решатель. Он попытается найти оптимальное решение в указанный срок. Если ему не удастся найти оптимальное решение, он вернет ближайшее неоптимальное решение.

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60.0
status = solver.Solve(model)

В нашем случае решающая программа возвращает оптимальное решение за 2,5 секунды (2).

Заключение

Чтобы создать это решение, достаточно 1 часа исследований и 30 минут программирования.

Для аналога Deep Learning можно спрогнозировать несколько дней очистки данных, по крайней мере, день для тестирования различных архитектур и еще один день для обучения.

Более того, модель CP-SAT очень устойчива, если хорошо смоделирована. Ниже представлены результаты с различными параметрами моделирования (3). Результаты по-прежнему согласованы во многих различных случаях, и с увеличением параметров моделирования (3000 пациентов, 1000 коек) вывод решения занял немногим менее 3 минут.

Конечно, CSP вряд ли применимы к таким темам, как компьютерное зрение и NLP, где глубокое обучение иногда является лучшим подходом. Тем не менее, в логистике, составлении графиков и планировании это часто правильный путь.

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

Особая благодарность Лорану Перрону и его команде по исследованию операций в Google за их фантастическую работу и за время, которое они потратили на ответы на технические вопросы о StackOverflow, GitHub и группах Google.

Антуан Чемпион, 1 апреля 2020 г.

использованная литература

[1] Цзинчао Чен, Решение кубика Рубика с помощью SAT-решателей, arXiv: 1105.1436, 2011.

[2] Биере А., Хеул М. и ван Маарен Х. Справочник по выполнимости, том 185. IOS Press, 2009a

[3] Кнут, Д. Э., Искусство компьютерного программирования, Том 4, Часть 6: Удовлетворенность. Эддисон-Уэсли Профессионал, 2015

[4] Випин Кумар, Алгоритмы для задач удовлетворения ограничений: обзор, AI Magazine Volume 13, Issue 1, 1992.