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
f <- function(x) {
y_hat <- (x^2+x)*cos(x)
-(y_want-y_hat)^2
}
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 |
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를 사용하여 최적의 해를 찾는것이다.
참고