Когда ИИ может в оптимизацию…

2024-12-09 в 6:16, admin, рубрики: mip, TSP, задача коммивояжёра, искусственный интеллект, оптимизация, точное решение

Всем привет!

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

Про ИИ

Очередная волна развития искусственного интеллекта почти никого не обошла стороной. Конечно я тоже обнаружил в себе своеобразный ген ИИ безумия. Корректнее сказать, я был всегда носителем этого гена, но долго и тщательно готовился встретить его проявление во всеоружии. А раз я готовился и предвкушал, то значит мне есть, что рассказать. Что-то другое и особенное, нежели просто удивление от того как электрическая машинка пишет SQL запрос, попутно галлюцинируя всякие забавные глупости.

Известно, что в ящичке инструментов современного программиста много всего разного: удобная среда разработки, система версионного контроля, всякие CI/CD и контейнеры, верхнеуровневые языки программирования типа R и Python, готовые пакеты/фреймворки, markdown документация, поисковики и стек оверфлоу. Интересно, какое место в этом списке по приоритету находятся ИИ помощники? Не исключаю, что где-то на одном из последних, но осознание этой истины не меняет ожиданий бизнеса от ИИ как о некой технологической миссии, способной перевернуть мир и обеспечить неслыханный прорыв в продуктивности белых воротничков. Возможно, кстати, так оно и будет.

Оставим на время в покое корпоративных визионеров и напомним, что основные технологические ИИ прорывы последнего времени происходили в области компьютерного зрения, слуха и позже пришли генеративные нейронные сети, способные создавать новый контент и в каком-то роде имитировать мыслительный процесс, обернутый в чат-бот. На данном этапе лично у меня возник вопрос, а насколько современные архитектуры нейронных систем действительно способны “мыслить” и принимать решения при заданных условиях оптимальности? Способны ли нейронные сети, будучи универсальным аппроксиматором, аппроксимировать идеальные или почти идеальные управленческие решения? Конечно речь идет не о широком круге управленческих решений, но о задачах оптимизации оперативного и тактического характера. Такие задачи обычно сопровождаются большим контекстом, который слабо умещается в черепную коробку человека. Действительно, сложно представить, чтобы человек держал в голове сотни единиц ресурсов(техники), их текущее состояния(расположение) и далее принимал оптимальное решение о назначение такого ресурса на очередную работу. На помощь приходят модели оптимизации, способные найти оптимальное или почти оптимальное решение. Кроме того, хитрые кожаные мешки способны мыслить на ином уровне абстракции с использованием эвристик. Действительно, не обязательно держать всю картинку в голове, но можно установить политику или простое правило для управления ресурсом, например, выполнять работу, которая ближе/проще всего и такая политика будет работать почти всегда или очень часто. Можно вспомнить задачу коммивояжера, где продавец должен объездить все города и ему хотелось бы это сделать по минимально-возможному маршруту. Самое простое решение для такой задачи будет посещение ближайшего города. Оно будет не идеальным, но определенно лучше рандомного маршрута.

Хорошо, эвристики не идеальны и субъективны, но есть же точные алгоритмы решения такой задачи. Все предельно просто на первый взгляд: берем решатель-солвер и вперед к оптимальному решению. Простейшие солверы можно найти в экселе и следовательно подразумевается их широкая доступность. Однако, если посмотреть на алгоритмы, которые решают задачу коммивояжера, то мы начинаем ощущать, как заглядываем в черную дыру знаний прошлых поколений, где быстро теряется свет собственного разума. Выясняется, что солвер решает эту проблему не лобовой атакой, но скорее дополнительной эвристикой в формулировке MTZ, которая ограничивает формирования бессмысленных под-маршрутов. Более того, при достижении кого-нибудь значения 20-30-100 городов солверы начинают стремительно погибать (привет NP-hard problems). Но на этом трудности на заканчиваются. Допустим, мы потратили пару часов или даже день чтобы посчитать оптимальный маршрут, но вдруг какой-то город закрыли на карантин или перекрыли дорогу. Маршрут придется пересчитать полностью и с этим ничего не поделаешь. Стохастические (неточные) методы могут помочь решить проблему, но все равно нужны эвристики, нужно время на расчет в каждый раз снова и снова, снова и снова.

Обратите внимание как описанная ситуация отличается от человеческих эвристик, которые работают всегда или почти всегда, и которые не требует пересчета. Отсюда вопрос – способна ли ИИ заменить человека в поисках таких эвристик? Более того, за счет фактически безлимитных в сравнении с черепной коробкой человека ресурсов хранения памяти такая сетка могла бы иметь в арсенале сразу много эвристик со способностью своевременно переключаться в зависимости от текущего контекста. Такая формулировка звучит уже существенно более интересно чем ~~продажа подслащенной водички~~ задача написания рекламного слогана чат-ботом.

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

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

Базовое решение MIP

Рассмотрим базовую проблему коммивояжера, известную как TSP (Travelling Salesman Problem) и найдем оптимальный маршрут движения для набора из 16 городов со случайными координатами из интервала от 0 до 100. Пусть стартовая точка №1 имеет координаты x=0, y=0.

library(ggplot2)

# Формирование задачи коммивояжера для 16 городов
n_cities <- 16

set.seed(2021)
cities <- data.frame(x=0, y= 0) |> # первая точка всегда в начале координат
  rbind(data.frame(x = runif(n_cities-1, max = 100), 
                   y = runif(n_cities-1, max = 100))) 

# Визуальное представление задачи
p0 <- transform(cities, n=seq_len(n_cities)) |>
  ggplot(aes(x, y)) + 
  geom_point() + 
  geom_point(data = data.frame(n=1, x=0, y=0), shape = 21, size = 5, col = "firebrick") +
  geom_text(aes(label = n), nudge_x = 3, nudge_y = 3) 

p0 + labs(title = "Задача коммивояжера для 16 городов")

Точное решение задачи можно получить, сформулировав задачу в виде MIP (Mixed Integer Problem) и воспользоваться пакетом, который позволяет моделировать такие задачи на уровне относительно простых правил. В данном случае будет использован пакет ompr. Есть несколько подходов к моделированию задачи, но по моим субъективным ощущениям наиболее распространенной является формулировка в виде ранее упомянутой MTZ (Miller–Tucker–Zemlin). Код оптимизационного решения может выглядеть следующим образом:

library(ompr) # пакет для MIP оптимизации
library(ompr.roi) # пакет интеграции с солверами
library(ROI.plugin.glpk) # GLPK солвер

# Матрица расстояний для городов
dist_mtrx <- as.matrix(dist(cities))

mdl_MIP <- MIPModel() |>
  # переменная, которая принимает значение 1 если коммивояжер следует из города i в город j
  add_variable(x[i, j], i = 1:n_cities, j = 1:n_cities, type = "integer", lb = 0, ub = 1) |>
  # вспомогательная переменная для MTZ формулировки задачи коммивояжер
  # add_variable(u[i], i = 1:n_cities, lb = 1, ub = n_cities) |> 
  # целевая функция минимизации маршрута 
  set_objective(sum_expr(dist_mtrx[i, j] * x[i, j], i = 1:n_cities, j = 1:n_cities), "min") |>
  # указание на невозможность движения из города в тот же город 
  set_bounds(x[i, i], ub = 0, i = 1:n_cities) |>
  # ограничение гарантирующие, что каждый город будет покинут один и только один раз
  add_constraint(sum_expr(x[i, j], j = 1:n_cities) == 1, i = 1:n_cities) |>
  # ограничение гарантирующие, что каждый город будет посещен один и только один раз
  add_constraint(sum_expr(x[i, j], i = 1:n_cities) == 1, j = 1:n_cities) # |>
  # исключение подмаршрутов
  # add_constraint(u[i] >= 2, i = 2:n_cities) #|> 
  # add_constraint(u[i] - u[j] + 1 <= (n_cities - 1) * (1 - x[i, j]), i = 2:n_cities, j = 2:n_cities)

# mdl_MIP

system.time(res_MIP <- solve_model(mdl_MIP, with_ROI(solver = "glpk", verbose = FALSE)))

##    user  system elapsed 
##   0.078   0.002   0.082

res_MIP

## Status: success
## Objective value: 359.6007

Первая часть модели интерпретируется достаточно понятно:

Есть некая булевая переменная $x_{ij}$ , которая кодирует выбор или не выбор отрезка между городами: последовательность таких отрезков и формирует маршрут. Если значение переменной равно 1, то отрезок выбран для маршрута, если 0 то отрезок не выбран
Есть целевая функция, которая требует от модели минимизацию маршрута
Есть немного искусственное требование на невозможность движения из города в тот же город. Требование очевидно для человека, но машине нужно объяснять дополнительно
Также пара требований указывает на необходимость покинуть все города и прибыть во все города, что достаточно очевидно

Замешательство вызывает набор требований/ограничений, связанные с вспомогательной переменной , которая гарантирует отсутствие подмаршрутов. Что это вообще за подмаршруты такие? Для понимания этого вопроса можно просто запустить модель, убрав части, связанные с , собственно, что и было сделано в блоке кода выше. Получим следующее решение:

library(data.table) # пакет для работы с таблицами

# Извлечение решения из модели 
solution <- get_solution(res_MIP, x[i, j]) |> 
  subset(value > 0) 

# Необходимые преобразования для построения графика
route_MIP1 <- setDT(solution)[, .(i, j, trip_id = .I)] |>
  melt(id.vars = "trip_id", value.name = 'idx_val') |> 
  merge(data.table(cities)[,idx_val:=.I][], by ="idx_val")

# Непосредственно график
p_sol1 <- p0 + 
  geom_line(data = route_MIP1, aes(group = trip_id)) + 
  ggtitle(paste0("Оптимальный маршрут: ", round(objective_value(res_MIP), 2)))

p_sol1

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

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

Напомню, что переменная $x_{ij}$ , кодирующая выбор отрезка маршрута, принимает значения 1 или 0, а следовательно условие возрастающего индекса может быть записано следующим образом: $u_{j}geq u_{i}+1$ при $x_{ij}=1$ . Здесь вместо строго неравенства используется , что предпочтительно для линейного программирования. Соответственно для сохранения первоначального смысла в неравенство добавлена единица.

Теперь необходимо обобщить такое ограничение для случая $x_{ij}=0$ когда отрезок не выбран для маршрута. Проблема в том, что неравенство $u_{j}geq u_{i} + x_{ij}$ накладывает ограничения на тоже, хотя этого не хотелось бы. Точнее сказать, модель должна игнорировать такое неравенство, если отсутствует переход между городами.

Поэтому каноническая формулировка MTZ вводит комбинированное линейное ограничение следующего вида: $_{i}-u_{j}+1leq (n-1)(1-x_{ij})$ , которое гарантирует поиск единого неразрывного маршрута через все города:

Такое выражение при $x_{ij}=1$ преобразуется к неравенству $u_{i}-u_{j}+1leq 0$ , обеспечивающие рост вспомогательной переменной по мере посещения городов.
Далее, при $x_{ij}=0$ получается неравенство $u_{i}-u_{j}+1leq n-1$ , которое выполняется всегда и позволяет модели принимать любые значения $u_{i}, u_{j}$ что важно для поиска оптимального решения. В предельном случае имеем $u_{i}=16$ , $u_{j}=2$ следовательно – неравенство выполняется, а следовательно для всех прочих $u_{i}, u_{j}$ оно также выполняется. Можно ли выбрать просто некое большое значение вместо ? Можно и такая постановка задачи встречается в научных статья про оптимизацию, но имеет свои издержки, описание которых останутся за рамками данной заметки.

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

В конечном итоге необходимо получить неразрывный маршрут прохода по всем городам и вернутся к первоначальному городу. Возврат к первоначальному городу нарушает правило возрастания вспомогательной переменной. Поэтому необходимо определить индексацию $u_{i}geq 2$ и исключить первый город из индексов для ограничения $u_{i}-u_{j}+1leq (n-1)(1-x_{ij})$ .

Итоговая формальная математическая запись модели будет следующей:

Целевая функция

$min sum_{i=1}^{n}sum_{jneq i,j=1}^{n}c_{ij}x_{ij} quad x_{ij} in {0,1} quad i,j=1,ldots ,n$

Два ограничения на посещения

$sum_{i=1,i neq j}^{n}x_{ij}, quad j=1,ldots ,n$ $sum_{j=1,j neq i}^{n}x_{ij}, quad j=1,ldots ,n$

Исключение подмаршрутов

$u_i - u_j + 1 leq (n - 1)(1 - x_{ij}), quad 2 leq i neq j leq n$

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

library(ompr) # пакет для MIP оптимизации
library(ompr.roi) # пакет интеграции с солверами
library(ROI.plugin.glpk) # GLPK солвер

# Матрица расстояний для городов
dist_mtrx <- as.matrix(dist(cities))

mdl_MIP <- MIPModel() |>
  # переменная, которая принимает значение 1 если коммивояжер следует из города i в город j
  add_variable(x[i, j], i = 1:n_cities, j = 1:n_cities, type = "integer", lb = 0, ub = 1) |>
  # вспомогательная переменная для MTZ формулировки задачи коммивояжер
  add_variable(u[i], i = 1:n_cities, lb = 1, ub = n_cities) |> 
  # целевая функция минимизации маршрута 
  set_objective(sum_expr(dist_mtrx[i, j] * x[i, j], i = 1:n_cities, j = 1:n_cities), "min") |>
  # указание на невозможность движения из города в тот же город 
  set_bounds(x[i, i], ub = 0, i = 1:n_cities) |>
  # ограничение гарантирующие, что каждый город будет покинут один и только один раз
  add_constraint(sum_expr(x[i, j], j = 1:n_cities) == 1, i = 1:n_cities) |>
  # ограничение гарантирующие, что каждый город будет посещен один и только один раз
  add_constraint(sum_expr(x[i, j], i = 1:n_cities) == 1, j = 1:n_cities)  |>
  # исключение подмаршрутов
  add_constraint(u[i] >= 2, i = 2:n_cities) |> 
  add_constraint(u[i] - u[j] + 1 <= (n_cities - 1) * (1 - x[i, j]), i = 2:n_cities, j = 2:n_cities)

system.time(res_MIP <- solve_model(mdl_MIP, with_ROI(solver = "glpk", verbose = FALSE)))

##    user  system elapsed 
##   0.151   0.001   0.152

res_MIP

## Status: success
## Objective value: 406.7583

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

# Извлечение решения из модели
solution <- get_solution(res_MIP, x[i, j]) |> 
  subset(value > 0) 

# Необходимые преобразования для построения графика
route_MIP1 <- setDT(solution)[, .(i, j, trip_id = .I)] |>
  melt(id.vars = "trip_id", value.name = 'idx_val') |> 
  merge(data.table(cities)[,idx_val:=.I][], by ="idx_val")

# Непосредственно график
p_sol2 <- p0 + 
  geom_line(data = route_MIP1, aes(group = trip_id)) + 
  ggtitle(paste0("Оптимальный маршрут: ", round(objective_value(res_MIP), 2)))

p_sol2

Построен оптимальный маршрут. Если у кого-то есть в этом сомнения, то можете попробовать построить свой вариант.

Послесловие

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

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

Оригинал заметки

Автор: welcome2hype

Источник

Информация

Обсуждаемое

Рекомендуем

Когда ИИ может в оптимизацию…

Про ИИ

Базовое решение MIP

Послесловие

Архив

Информация

Обсуждаемое

Рекомендуем

Когда ИИ может в оптимизацию…

Про ИИ

Базовое решение MIP

Послесловие

Рекомендованный контент

Новости

Актуальные темы

Архив