r - Rで整数パラメータ(およびその他の不連続パラメータ空間)を最適化する方法は?

Question

パラメータ空間が整数のみの場合 (または不連続である場合)、どのように最適化しますか?

optim() で整数チェックを使用しても機能しないようで、とにかく非常に非効率的です。

fr <- function(x) {   ## Rosenbrock Banana function
  x1 <- x[1]
  x2 <- x[2]
  value<-100 * (x2 - x1 * x1)^2 + (1 - x1)^2

  check.integer <- function(N){
    !length(grep("[^[:digit:]]", as.character(N)))
  }

  if(!all(check.integer(abs(x1)), check.integer(abs(x2)))){
   value<-NA 
  }
  return(value)

}
optim(c(-2,1), fr)

score 55 · Accepted Answer

ここにいくつかのアイデアがあります。

1. 不利な最適化。 目的関数の引数を丸め、非整数にペナルティを追加できます。しかし、これは多くの局所的な極値を作成するので、微分進化や粒子群最適化など、より堅牢な最適化ルーチンを好むかもしれません。

fr <- function(x) {
  x1 <- round( x[1] )
  x2 <- round( x[2] )
  value <- 100 * (x2 - x1 * x1)^2 + (1 - x1)^2
  penalty <- (x1 - x[1])^2 + (x2 - x[2])^2
  value + 1e3 * penalty
}

# Plot the function
x <- seq(-3,3,length=200)
z <- outer(x,x, Vectorize( function(u,v) fr(c(u,v)) ))
persp(x,x,z,
  theta = 30, phi = 30, expand = 0.5, col = "lightblue", border=NA,
  ltheta = 120, shade = 0.75, ticktype = "detailed")

透視図

library(RColorBrewer)
image(x,x,z, 
  las=1, useRaster=TRUE,
  col=brewer.pal(11,"RdYlBu"),
  xlab="x", ylab="y"
)

画像プロット

# Minimize
library(DEoptim)
library(NMOF)
library(pso)
DEoptim(fr, c(-3,-3), c(3,3))$optim$bestmem
psoptim(c(-2,1), fr, lower=c(-3,-3), upper=c(3,3))
DEopt(fr, list(min=c(-3,-3), max=c(3,3)))$xbest
PSopt(fr, list(min=c(-3,-3), max=c(3,3)))$xbest

2. 徹底的な検索。 検索スペースが小さい場合は、グリッド検索も使用できます。

library(NMOF)
gridSearch(fr, list(seq(-3,3), seq(-3,3)))$minlevels

3. ユーザーが指定した地域でのローカル検索。 目的関数を微調整せずに、調べるポイントを指定できる何らかの形式のローカル検索を使用できます。これははるかに高速ですが、近傍関数の選択に非常に敏感です。

# Unmodified function
f <- function(x) 
  100 * (x[2] - x[1] * x[1])^2 + (1 - x[1])^2

# Neighbour function
# Beware: in this example, with a smaller neighbourhood, it does not converge.
neighbour <- function(x,...)
  x + sample(seq(-3,3), length(x), replace=TRUE)

# Local search (will get stuck in local extrema)
library(NMOF)
LSopt(f, list(x0=c(-2,1), neighbour=neighbour))$xbest
# Threshold Accepting
TAopt(f, list(x0=c(-2,1), neighbour=neighbour))$xbest

4.タブー検索。 同じポイントを何度も探索するのを避けるために、タブー検索を使用できます。つまり、最後の k ポイントを記憶して、再度アクセスしないようにします。

get_neighbour_function <- function(memory_size = 100, df=4, scale=1){
  # Static variables
  already_visited <- NULL
  i <- 1
  # Define the neighbourhood
  values <- seq(-10,10)
  probabilities <- dt(values/scale, df=df)
  probabilities <- probabilities / sum(probabilities)
  # The function itself
  function(x,...) {
    if( is.null(already_visited) ) {
      already_visited <<- matrix( x, nr=length(x), nc=memory_size )
    }
    # Do not reuse the function for problems of a different size
    stopifnot( nrow(already_visited) == length(x) )
    candidate <- x
    for(k in seq_len(memory_size)) {
      candidate <- x + sample( values, p=probabilities, length(x), replace=TRUE )
      if( ! any(apply(already_visited == candidate, 2, all)) )
        break
    }
    if( k == memory_size ) {
      cat("Are you sure the neighbourhood is large enough?\n")
    } 
    if( k > 1 ) {
      cat("Rejected", k - 1, "candidates\n")
    }
    if( k != memory_size ) {
      already_visited[,i] <<- candidate
      i <<- (i %% memory_size) + 1
    }
    candidate
  }
}

次の例では、実際には機能しません。最も近い極小値に移動するだけです。高次元になると事態はさらに悪化します。近傍が非常に大きいため、既に訪れたポイントのキャッシュにヒットすることはありません。

f <- function(x) {
  result <- prod( 2 + ((x-10)/1000)^2 - cos( (x-10) / 2 ) )  
  cat(result, " (", paste(x,collapse=","), ")\n", sep="")
  result
}
plot( seq(0,1e3), Vectorize(f)( seq(0,1e3) ) )

LSopt(f, list(x0=c(0,0), neighbour=get_neighbour_function()))$xbest
TAopt(f, list(x0=c(0,0), neighbour=get_neighbour_function()))$xbest
optim(c(0,0), f, gr=get_neighbour_function(), method="SANN")$par

微分進化の方がうまく機能します。局所的な最小値しか得られませんが、最も近いものよりも優れています。

g <- function(x) 
  f(x) + 1000 * sum( (x-round(x))^2 )
DEoptim(g, c(0,0), c(1000,1000))$optim$bestmem

タブー検索は、純粋に組み合わせの問題 (検索空間がツリーまたはグラフのセットである場合など) によく使用され、整数の問題には適していないようです。

score 14 · Accepted Answer

整数計画法 (IP) には独自のルールとアルゴリズムがあります。連続ソルバーを使用してもあまり意味がありません。R には特殊な整数計画法ソルバーはありませんが、以下を試すことができます。

関数が線形の場合は、lp_solve (R では "lpSolve") やGLPK (R では " Rglpk ") などの混合整数計画法ソルバーのいずれかを使用します。
それ以外の場合は、シミュレートされたアニーリングアプローチである "SANN" メソッドを使用して最適化を試みることができます。ドキュメントには次のように記載されています。

"It uses only function values but is relatively slow... If a function to generate a new candidate point is given, method 'SANN' can also be used to solve combinatorial optimization problems... Note that the 'SANN' method depends critically on the settings of the control parameters."

以下は、変換された球関数を使用した例です[-10,10]x[-10,10]。

fun <- function(x) sum((x-c(3.2, 6.7))^2)
nextfun <- function(x) sample(-10:10, 2, replace=TRUE)

optim(fn=fun, par=c(-10,-10), gr=nextfun, method="SANN", 
      control=list(maxit=1000,fnscale=1,trace=10))

# sann objective function values
# initial       value 458.000000
# iter      999 value 0.000000
# final         value 0.000000
# sann stopped after 999 iterations
# $par
# [1] 3 7
# $value
# [1] 0.13

ただし、他に何も役に立たない場合は、ランダムサンプリングよりもインテリジェントな「勾配」を適用するか、整数のドメインを完全に検索する必要があります。もちろん、高次元では特殊なアプローチが必要になります。

score 9 · Accepted Answer

R で利用可能な新しいパッケージがあり、最適化プログラムで不連続な入力パラメーター (整数など) を使用できます。それらの1つはrgenoudです

オプション「data.type.int=TRUE」を使用し、正しい境界を設定することにより、関数は整数のみを使用して特定の関数を最小化または最大化します。

rgenoud の下で、最適化のために stats::optim() を使用します。したがって、ユーザーは、通常は optim() に渡す任意のオプションを rgenoud に渡すことができます。

r - Rで整数パラメータ(およびその他の不連続パラメータ空間)を最適化する方法は?

3 に答える 3

Related

Reference