R：比较随机搜索的时间
R: Comparing the Time for Random Searches
我正在使用 R 编程语言。
我正在尝试使用带替换的随机搜索和不带替换的随机搜索来优化 Rastrign 函数：
Rastrigin <- function(x1, x2)
{
20 + x1^2 + x2^2 - 10*(cos(2*pi*x1) + cos(2*pi*x2))
}
x1 <- x2 <- seq(-5.12, 5.12, by = 0.1)
f <- outer(x1, x2, Rastrigin)
第 1 部分：带替换的随机搜索：
为了进行替换采样，我生成了 100 个点（我将这些点转换为整数格式，以便更容易看出哪些点与 第 2 部分 重复），然后进行评估这 100 个点的函数。然后我提取了与函数的最小值对应的数据行。我也记录了用时：
start.time <- Sys.time()
x1 = as.integer(rnorm(100,5,5))
x2 = as.integer(rnorm(100,5,5))
func_value = 20 + x1^2 + x2^2 - 10*(cos(2*pi*x1) + cos(2*pi*x2))
frame = data.frame(x1,x2,func_value)
sort_frame <- frame[order(func_value),]
final_answer = sort_frame[1,]
end.time <- Sys.time()
time.taken <- end.time - start.time
time.taken
Time difference of 0.01810408 secs
第 2 部分：无替换随机搜索：
因为我不知道如何编写传统方法的代码来进行无替换随机搜索（即生成随机值，看看这个生成的值是否已经出现：如果没有，则根据这个值评估函数，否则生成新值，直到生成一个看不见的值）——因为我想用 100 个值来评估函数，所以我决定生成 200 个值，希望这 200 个值中至少有 100 个值是唯一的。然后，我重复了上面的过程：
start.time <- Sys.time()
x1 = as.integer(rnorm(200,5,5))
x2 = as.integer(rnorm(200,5,5))
frame = data.frame(x1,x2)
de_duplicated = frame[!(duplicated(frame) | duplicated(frame, fromLast = TRUE)), ]
#check to make sure at least 100 values in "de_duplicated"
ifelse(nrow(de_duplicated)<100, "BAD", "GOOD")
[1] "GOOD"
#only keep 100 values in de_duplicated:
de_duplicated = de_duplicated[1:100,]
func_value = 20 + de_duplicated$x1^2 + de_duplicated$x2^2 - 10*(cos(2*pi*de_duplicated$x1) + cos(2*pi*de_duplicated$x2))
final_frame = data.frame(de_duplicated$x1,de_duplicated$x2,func_value)
sort_frame <- final_frame[order(func_value),]
final_answer = sort_frame[1,]
end.time <- Sys.time()
time.taken <- end.time - start.time
time.taken
Time difference of 0.03689885 secs
我的问题： 因为我有兴趣比较 第 1 部分 和 第 2 部分[=47] 的时间=] - 我认为这不公平，因为我以非常“笨拙”的方式编写了 第 2 部分 的代码。
如果您以更“传统”的方式编写 第 2 部分 的代码，即使用“while 循环”- 这会减少 [=35] 所需的时间吗=]第 2 部分？ C有人请告诉我如何做到这一点 - 正在编写无替换随机搜索（即 第 2 部分）使用“while 循环”实际上是执行此操作的传统方法?
谢谢！
您不会在没有替换的情况下使用 while 循环进行采样。
要么使用 sample，它有一个参数 replace。
或者使用某种形式的指定向量的随机排序：
x <- 1:10
## [1] 1 2 3 4 5 6 7 8 9 10
x[order(runif(length(x)))]
## [1] 6 8 2 5 3 7 1 10 9 4
以下是我可以使用或不使用替换的整数值对函数进行采样的示例方法：
set.seed(123)
fSearchReplace <- function() {
# sampling with replacement
x1 <- as.integer(rnorm(100, 5, 5))
x2 <- as.integer(rnorm(100, 5, 5))
func_value <- 20 + x1^2 + x2^2 - 10*(cos(2*pi*x1) + cos(2*pi*x2))
idxMin <- which.min(func_value)
frame <- data.frame(x1 = x1[idxMin], x2 = x2[idxMin], func_value = func_value[idxMin])
}
fSearchNoReplace1 <- function() {
# sampling without replacement by rejection
frame <- unique.data.frame(data.frame(x1 = as.integer(rnorm(200, 5, 5)), x2 = as.integer(rnorm(200, 5, 5))))
while (nrow(frame) < 100L) {
sz <- (100L - nrow(frame))*2L
frame <- unique.data.frame(rbind(frame, data.frame(x1 = as.integer(rnorm(sz,5,5)), x2 = as.integer(rnorm(sz, 5, 5)))))
}
func_value <- 20 + frame[1:100,]$x1^2 + frame[1:100,]$x2^2 - 10*(cos(2*pi*frame[1:100,]$x1) + cos(2*pi*frame[1:100,]$x2))
idxMin <- which.min(func_value)
frame <- data.frame(x1 = frame$x1[idxMin], x2 = frame$x2[idxMin], func_value = func_value[idxMin])
}
fSearchNoReplace2 <- function() {
# sampling without replacement using weights
p <- diff(pnorm(-15.5:5.5, 5, 5))
w1 <- c(p, rev(head(p, -1)))
frame <- setNames(expand.grid(rep(list(-15:25), 2))[sample(1681, 100, prob = outer(w1, w1)),], c("x1", "x2"))
frame$func_value <- 20 + frame$x1^2 + frame$x2^2 - 10*(cos(2*pi*frame$x1) + cos(2*pi*frame$x2))
frame <- frame[which.min(frame$func_value),]
}
print(fSearchReplace(), row.names = FALSE)
#> x1 x2 func_value
#> 0 0 0
print(fSearchNoReplace1(), row.names = FALSE)
#> x1 x2 func_value
#> 1 0 1
print(fSearchNoReplace2(), row.names = FALSE)
#> x1 x2 func_value
#> 0 0 0
microbenchmark::microbenchmark(fSearchReplace(), fSearchNoReplace1(), fSearchNoReplace2())
#> Unit: microseconds
#> expr min lq mean median uq max neval
#> fSearchReplace() 220.7 255.65 298.925 291.60 324.40 490.8 100
#> fSearchNoReplace1() 802.0 880.55 1043.916 1027.65 1132.70 2036.8 100
#> fSearchNoReplace2() 495.7 530.85 650.703 610.35 679.65 2779.4 100
注意：如果搜索不是限制为整数，rnorm可以视为无放回抽样。从 100 个中得到两对相同的 x1 和 x2 的概率几乎为 0（这就是为什么 rnorm 没有 replace 参数）。
我正在使用 R 编程语言。
我正在尝试使用带替换的随机搜索和不带替换的随机搜索来优化 Rastrign 函数：
Rastrigin <- function(x1, x2)
{
20 + x1^2 + x2^2 - 10*(cos(2*pi*x1) + cos(2*pi*x2))
}
x1 <- x2 <- seq(-5.12, 5.12, by = 0.1)
f <- outer(x1, x2, Rastrigin)
第 1 部分：带替换的随机搜索：
为了进行替换采样，我生成了 100 个点（我将这些点转换为整数格式，以便更容易看出哪些点与 第 2 部分 重复），然后进行评估这 100 个点的函数。然后我提取了与函数的最小值对应的数据行。我也记录了用时：
start.time <- Sys.time()
x1 = as.integer(rnorm(100,5,5))
x2 = as.integer(rnorm(100,5,5))
func_value = 20 + x1^2 + x2^2 - 10*(cos(2*pi*x1) + cos(2*pi*x2))
frame = data.frame(x1,x2,func_value)
sort_frame <- frame[order(func_value),]
final_answer = sort_frame[1,]
end.time <- Sys.time()
time.taken <- end.time - start.time
time.taken
Time difference of 0.01810408 secs
第 2 部分：无替换随机搜索：
因为我不知道如何编写传统方法的代码来进行无替换随机搜索（即生成随机值，看看这个生成的值是否已经出现：如果没有，则根据这个值评估函数，否则生成新值，直到生成一个看不见的值）——因为我想用 100 个值来评估函数，所以我决定生成 200 个值，希望这 200 个值中至少有 100 个值是唯一的。然后，我重复了上面的过程：
start.time <- Sys.time()
x1 = as.integer(rnorm(200,5,5))
x2 = as.integer(rnorm(200,5,5))
frame = data.frame(x1,x2)
de_duplicated = frame[!(duplicated(frame) | duplicated(frame, fromLast = TRUE)), ]
#check to make sure at least 100 values in "de_duplicated"
ifelse(nrow(de_duplicated)<100, "BAD", "GOOD")
[1] "GOOD"
#only keep 100 values in de_duplicated:
de_duplicated = de_duplicated[1:100,]
func_value = 20 + de_duplicated$x1^2 + de_duplicated$x2^2 - 10*(cos(2*pi*de_duplicated$x1) + cos(2*pi*de_duplicated$x2))
final_frame = data.frame(de_duplicated$x1,de_duplicated$x2,func_value)
sort_frame <- final_frame[order(func_value),]
final_answer = sort_frame[1,]
end.time <- Sys.time()
time.taken <- end.time - start.time
time.taken
Time difference of 0.03689885 secs
我的问题： 因为我有兴趣比较 第 1 部分 和 第 2 部分[=47] 的时间=] - 我认为这不公平，因为我以非常“笨拙”的方式编写了 第 2 部分 的代码。
如果您以更“传统”的方式编写 第 2 部分 的代码，即使用“while 循环”- 这会减少 [=35] 所需的时间吗=]第 2 部分？ C有人请告诉我如何做到这一点 - 正在编写无替换随机搜索（即 第 2 部分）使用“while 循环”实际上是执行此操作的传统方法?
谢谢！
您不会在没有替换的情况下使用 while 循环进行采样。
要么使用 sample，它有一个参数 replace。
或者使用某种形式的指定向量的随机排序：
x <- 1:10
## [1] 1 2 3 4 5 6 7 8 9 10
x[order(runif(length(x)))]
## [1] 6 8 2 5 3 7 1 10 9 4
以下是我可以使用或不使用替换的整数值对函数进行采样的示例方法：
set.seed(123)
fSearchReplace <- function() {
# sampling with replacement
x1 <- as.integer(rnorm(100, 5, 5))
x2 <- as.integer(rnorm(100, 5, 5))
func_value <- 20 + x1^2 + x2^2 - 10*(cos(2*pi*x1) + cos(2*pi*x2))
idxMin <- which.min(func_value)
frame <- data.frame(x1 = x1[idxMin], x2 = x2[idxMin], func_value = func_value[idxMin])
}
fSearchNoReplace1 <- function() {
# sampling without replacement by rejection
frame <- unique.data.frame(data.frame(x1 = as.integer(rnorm(200, 5, 5)), x2 = as.integer(rnorm(200, 5, 5))))
while (nrow(frame) < 100L) {
sz <- (100L - nrow(frame))*2L
frame <- unique.data.frame(rbind(frame, data.frame(x1 = as.integer(rnorm(sz,5,5)), x2 = as.integer(rnorm(sz, 5, 5)))))
}
func_value <- 20 + frame[1:100,]$x1^2 + frame[1:100,]$x2^2 - 10*(cos(2*pi*frame[1:100,]$x1) + cos(2*pi*frame[1:100,]$x2))
idxMin <- which.min(func_value)
frame <- data.frame(x1 = frame$x1[idxMin], x2 = frame$x2[idxMin], func_value = func_value[idxMin])
}
fSearchNoReplace2 <- function() {
# sampling without replacement using weights
p <- diff(pnorm(-15.5:5.5, 5, 5))
w1 <- c(p, rev(head(p, -1)))
frame <- setNames(expand.grid(rep(list(-15:25), 2))[sample(1681, 100, prob = outer(w1, w1)),], c("x1", "x2"))
frame$func_value <- 20 + frame$x1^2 + frame$x2^2 - 10*(cos(2*pi*frame$x1) + cos(2*pi*frame$x2))
frame <- frame[which.min(frame$func_value),]
}
print(fSearchReplace(), row.names = FALSE)
#> x1 x2 func_value
#> 0 0 0
print(fSearchNoReplace1(), row.names = FALSE)
#> x1 x2 func_value
#> 1 0 1
print(fSearchNoReplace2(), row.names = FALSE)
#> x1 x2 func_value
#> 0 0 0
microbenchmark::microbenchmark(fSearchReplace(), fSearchNoReplace1(), fSearchNoReplace2())
#> Unit: microseconds
#> expr min lq mean median uq max neval
#> fSearchReplace() 220.7 255.65 298.925 291.60 324.40 490.8 100
#> fSearchNoReplace1() 802.0 880.55 1043.916 1027.65 1132.70 2036.8 100
#> fSearchNoReplace2() 495.7 530.85 650.703 610.35 679.65 2779.4 100
注意：如果搜索不是限制为整数，rnorm可以视为无放回抽样。从 100 个中得到两对相同的 x1 和 x2 的概率几乎为 0（这就是为什么 rnorm 没有 replace 参数）。