AI/Optimization

[R] GA 특정 값으로 최적화 하는 방법 (no Maximizing) :: How to optimize with GA specific values in R

슈퍼짱짱 2020. 9. 14. 18:53
반응형

R에서 GA 최대값으로 최적화 하지 않고, 지정된 값으로 최적화 하는 방법

 

Genetic Algorithm(GA - 유전 알고리즘) 최적화 문제를 해결하는 기법 중 하나로, 생물의 진화를 모방한 방법이다.

 

R에서는 GA 패키지로 제공되고 있으며, 기본적으로 주어진 fitness function을 최대화 하는 방향으로 최적화 한다. (function에 -(minus)를 붙여주면 최솟값으로 최적화 할 수도 있다. 자세한 방법은 아래 실습에서 다루겠다.)

 

1. Maximizing

 

우선, 주어진 function을 최대화 하는 기본적인 코드는 다음과 같다.

 

주어진 function은 다음과 같고, 찾고자 하는 x의 범위는 -10 ~ 10라 하자.

$$ function : (x^2+x)*cos(x) $$

 

해당 function을 정의하고 그래프를 그리는 코드는 다음과 같다.

 

1
2
f <- function(x)  (x^2+x)*cos(x) # -10 < x < 10
curve(f, -10, 10)
cs

 

이를 GA로 최적화 하는 코드는 다음과 같다.

매번 같은 값을 return하기 위해 seed를 지정해 주었다. 이는 생략 가능하다.

 

1
2
3
4
GA <- ga(type = "real-valued", 
         fitness = f, 
         lower = -10, upper = 10,
         seed = 1)
cs

 

GA로 찾아진 최적값은 다음과 같다(red vertical line). 정확한 값은 GA@solution으로 볼 수 있다.

 

> GA@solution
           x1
[1,] 6.560307

 

1
2
curve(f, -10, 10)
abline(v = GA@solution, lty = 3, col = "red")
cs

 

GA가 최적 해를 찾아가는 과정을 실시간으로 monitoring 하고 싶다면 monitor function을 지정해 주면 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
monitor <- function(obj) 
  curve(f, -10, 10, main = paste("iteration =", obj@iter)) ## iter에 따라 결과 확인
  points(obj@population, obj@fitness, pch = 20, col = 2) ## 최적값 
  rug(obj@population, col = 2) ## 최적값 x축 
  Sys.sleep(0.2) ## 그래프가 너무 빨리 지나가지 않도록 sleep
}
 
GA <- ga(type = "real-valued", 
         fitness = f, 
         lower = -10, upper = 10, 
         # monitor = monitor,
         seed=1)
 
monitor(GA)
abline(v = GA@solution, lty = 3, col = "red")
cs

 

위 코드를 R에서 실행해 보면 각 iter에 따라 찾아진 최적값을 눈으로 볼 수 있다. (default iteration = 100)

최종 결과는 다음과 같다.

 

빨간색 점들이 f(x) 최댓값 근처에 분포해 있으며, vertical line(찾아진 최적해) 이 f(x)의 최댓값을 잘 찾아준 것을 볼 수 있다.

(단, 최적화 할 x가 다차원인 경우는 monitoring에 한계가 있다.)

 


2. Minimizing :: Optimizing to Minimum with GA in R

반대로 Minimizing하는 방법은 function을 뒤집어 주면 된다. 즉, 가장 컸던 값이 가장 작아지도록, 가장 작았던 값이 가장 커지도록 목적함수를 바꿔주면 된다.

 

1
2
f <- function(x)  -(x^2+x)*cos(x)
curve(f, -10, 10)
cs

 

function에 -(minus)를 붙여주니 최대값과 최소값이 뒤집어 진 것을 볼 수 있다.

이후 과정은 위와 마찬가지로 해주면 결과는 다음과 같다.

 

주어진 function을 최소화 해주는 x값을 잘 찾아 주었다.

 


3. GA로 최대값이나 최소값이 아닌, 특정 값을 찾아주는 방법 

마지막으로 최대, 최소가 아니라 특정 값으로 최적화 해주는 방법은 역시 목적함수(fitness function)를 고쳐주는 것이다.

 

function = 0가 되는 최적의 x값을 찾는다고 가정하자.

즉, function이 최대값도, 최소값도 아닌 중간의 어느 지점을 찾아야 한다. 참고로 이 때의 x 값(찾아야 하는 최적값)은 -1 이다. 

 

이를 찾기 위한 목적함수는 다음과 같이 정의한다.

 

1
2
3
4
5
y_want = 0
f <- function(x) {
  y_hat <- (x^2+x)*cos(x)
 -(y_want-y_hat)^2
}
cs

 

(y_want는 function안에 parameter로 전달해 줄 수 도 있으며, 본 과정에서는 편의상 전역변수로 지정해 주었다.)

기존에는 그냥 return 하던 부분을 y_hat에 넣어주고, 원하는 y값과 y_hat의 차이를 최대화 하도록 식을 수정해 주었다.

 

MSE(Mean Square Error)와 비슷한 원리라고 생각하면 된다. (Linear Regression은 MSE를 최소화 하도록 모델을 업데이트 한다. GA는 기본적으로 최소화가 아닌 최대화기 때문에 -(minus)를 붙여준 것이다.)

 

이를 시각화 하면 다음과 같다.

 

1
2
3
c <- curve(f, -10, 10)
abline(h = 0, col = "red")
abline(v = -6.6, col = "blue")
cs

 

f가 0인 지점 즉, 원하는 y값(y_want = 0)과 식을 통해 나온 값(y_hat)의 차이가 0이 되는 x를 찾는 것이 목적이다.

 

GA로 최적값 찾는 코드는 다음과 같다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
y_want = 0
<- function(x) {
  y_hat <- (x^2+x)*cos(x)
  -(y_want-y_hat)^2
}
 
monitor <- function(obj) 
  curve(f, -1010, main = paste("iteration =", obj@iter)) ## iter에 따라 결과 확인
  points(obj@population, obj@fitness, pch = 20, col = 2) ## 최적값 
  rug(obj@population, col = 2) ## 최적값 x축 
  Sys.sleep(0.2) ## 그래프가 너무 빨리 지나가지 않도록 sleep
}
 
GA <- ga(type = "real-valued"
         fitness = f, 
         lower = -10, upper = 10
         monitor = monitor,
         seed=1)
 
monitor(GA)
abline(v = GA@solution, lty = 3, col = "red")
cs

 

GA로 찾아진 최적값은 다음과 같다.

 

> GA@solution
             x1
[1,] -0.9999148

 

실제 -1과 아주 가까운 값이 찾아진 것을 확인할 수 있다.

 


참고로 fitness function에 실제 식이 아니라 Machnine Learning Model을 넣고 싶다면, 위 코드에서 y_hat에 model prediction을 넣으면 된다.

 

전체 코드는 다음과 같다.

위와 같은 function을 xgb 모델로 모델링하고, 만들어진 모델에 대해 원하는 y값을 만들어 주는 최적의 x값을 찾는다고 가정한다.

 

(modeling은 caret 패키지를 활용했다.)

 

1
2
3
4
x <- seq(-10, 10, by = 0.5)
y <- (x^2+x)*cos(x)
 
dat <- data.frame(y = y, x = x)
cs

 

x(독립변수)는 -10 ~ 10 의 값을 0.5간격으로 생성하고, y(종속변수, Target)는 위 식에 맞추어 생성해 주었다.

생성된 data set의 상위 5개는 다음과 같다.

 

> head(dat,5)
           y     x
1 -75.516438 -10.0
2 -80.521652  -9.5
3 -65.601379  -9.0
4 -38.378259  -8.5
5  -8.148002  -8.0

 

 

이를 caret 패키지로 modeling 한다.

 

1
2
3
model <- caret::train(y~x, data = dat,
                      method = "xgbLinear",
                      trControl = trainControl(method = "none"))
cs

 

참고로 이 모델로 predict한 결과는 다음과 같다.

 

1
2
y_hat <- predict(model, newdata = dat)
plot(x = x, y = y_hat)
cs

 

train 한 값을 그대로 prediction했기 때문에 결과가 실제값과 매우 흡사한 것은 당연하다.

이를 위 3번과 마찬가지로 y=0으로 만들어주는 최적의 x값을 찾고 싶다면 목적함수를 다음과 같이 정의하면 된다.

 

1
2
3
4
5
y_want <- 0
f <- function(x)  {
  y_hat <- predict(model, data.frame(x = x)) 
  -(y_want - y_hat)^2
}
cs

 

y_hat 부분에 직접 식을 넣는게 아니라 model prediction 을 넣었다.

linear 모델 같은 경우는 coef를 알 수 있기 때문에 수식을 직접 넣을 수 있지만, tree 모델 같이 수식을 직접 넣을 수 없을 때는 prediction을 바로 넣어주면 된다. 

 

최적값을 찾아주는 과정과 결과는 다음과 같다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
monitor <- function(obj) 
  plot(x = seq(-10, 10, by = 0.5), y = f(x), main = paste("iteration =", obj@iter))
  # plot(x = x, y = y_hat, main = paste("iteration =", obj@iter))
  points(obj@population, obj@fitness, pch = 20, col = 2)
  # rug(obj@population, col = 2)
  Sys.sleep(0.2)
}
 
GA <- ga(type = "real-valued", fitness = f, lower = -10, upper = 10, 
         maxiter = 50,
         monitor = NULL)
 
monitor(GA)
abline(v = GA@solution, lty = 3, col = "red")
cs

 

시간 단축을 위해 iter는 50번만 했다.

 

> GA@solution
            x1
[1,] -1.570911

 

본 과정처럼 찾고자 하는 x들의 차원이 단순하고, fitness function이 명확한 경우는 사실 GA를 할 필요가 없다. 직접 계산하거나, 눈으로 보아도 최적의 x값을 찾을 수 있기 때문이다.

 

하지만, 식이 매우 복잡하거나(like ML, DL Model), 찾고자 하는 해의 차원이 커지면 일일이 계산하는데 한계가 있다. 이럴 때 GA를 사용하여 최적의 해를 찾는것이다.


참고

 

cran.r-project.org/web/packages/GA/vignettes/GA.html

반응형