Табу искать в R - PullRequest
Новая
       30

Табу искать в R

0 голосов
/ 24 июня 2018

Добрый вечер,

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

Я не нашел ни одного R или Python примера ни в Google, ни в YouTube, так что я действительно молюсь, чтобы я нашел здесь что-нибудь.

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

Мне нужно найти 5 hubs, а общая емкость для каждого равна 120

nodes <- structure(list(node_number = 1:50, 
               x = c(2L, 80L, 36L, 57L, 33L, 76L, 77L, 94L, 
                     89L, 59L, 39L, 87L, 44L, 2L, 19L, 5L, 
                     58L, 14L, 43L, 87L, 11L, 31L, 51L, 55L, 
                     84L, 12L, 53L, 53L, 33L, 69L, 43L, 10L, 
                     8L, 3L, 96L, 6L, 59L, 66L, 22L, 75L, 4L, 
                     41L, 92L, 12L, 60L, 35L, 38L, 9L, 54L, 1L), 
               y = c(62L, 25L, 88L, 23L, 17L, 43L, 85L, 6L, 11L, 
                     72L, 82L, 24L, 76L, 83L, 43L, 27L, 72L, 50L, 
                     18L, 7L, 56L, 16L, 94L, 13L, 57L, 2L, 33L, 10L, 
                     32L, 67L, 5L, 75L, 26L, 1L, 22L, 48L, 22L, 69L,
                     50L, 21L, 81L, 97L, 34L, 64L, 84L, 100L, 2L, 9L, 59L, 58L), 
               node_demand = c(3L, 14L, 1L, 14L, 19L, 2L, 14L, 6L, 
                               7L, 6L, 10L, 18L, 3L, 6L, 20L, 4L, 
                               14L, 11L, 19L,  15L, 15L, 4L, 13L, 
                               13L, 5L, 16L, 3L, 7L, 14L, 17L, 
                               3L, 3L, 12L, 14L, 20L, 13L, 10L, 
                               9L, 6L, 18L, 7L, 20L, 9L, 1L, 8L, 
                               5L, 1L, 7L, 9L, 2L)), 
          .Names = c("node_number", "x", "y", "node_demand"), 
          class = "data.frame", row.names = c(NA, -50L))


hubs_required = 5
total_capacity = 120

Моя стратегия состояла в том, чтобы создать distance matrix, затем я создам еще одну матрицу 50 x 50, чтобы представить, становится ли узел центром или нет, и, наконец, я умножу оба и добавлю все расстояния, чтобы получить общее расстояние.

Я создал фрейм данных: 

nodes_df <- as.data.frame(nodes)
colnames(nodes_df) <- c("x", "y", "node_demand")
rownames(nodes_df) <- paste('Node',1:50)

Я создал матрицу расстояний 

distance_df <-as.data.frame(as.matrix(round(dist(nodes_df,method = "euclidean",diag = TRUE,upper = TRUE))))
colnames(distance_df) <- paste("Node",1:50)

Я создал матрицу спроса узла: 

demand <- as.vector(rep(c(nodes_df[,'node_demand']),50)) 
demand_matrix <- matrix(demand,nrow=50,ncol=50,byrow = TRUE)
diag(demand_matrix) <- 0
demand_matrix <- as.data.frame(demand_matrix)

Я создал пустую матрицу, чтобы показать, становится ли node hub "1" или нет "0"

hubs_matrix <- matrix(0,nrow = 50,ncol = 50,byrow = TRUE)
colnames(hubs_matrix) <- paste("Hub",1:50)
rownames(hubs_matrix) <- paste("Node",1:50)

Затем для создания исходного решения я случайным образом назначаю Hubs и вычисляю расстояние и спрос. 

set.seed(37)
hubs_matrix <- do.call("cbind", lapply(1:50, function(x) sample(c(1, rep(0, 49)), 50)))
sum_distances <- (hubs_matrix * distance_df)
sum(rowSums(sum_distances))

Идея состоит в том, чтобы попробовать разные комбинации «1» и «0», чтобы минимизировать общее расстояние, но у меня возникают следующие проблемы:

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

  • Я понятия не имел, как запретить R использовать лучшее решение в течение определенного периода времени, то есть список Табу

  • Я понятия не имел, как бороться с ограничением поставок для каждого узла (суммарный спрос каждого узла <120), я мог бы сделать это с помощью цикла, но так как в этом случае я умножаю матрицы, я довольно потерян. </p>

Кто-нибудь может мне помочь ???

Большое спасибо!

...