제조 공정에서 최적화란?
딥러닝을 공부한 사람이라면 최적화(Optimization)이라는 단어를 많이 들어보았을 것이다.
딥러닝에서 모델을 학습하는 과정에서 Cost function 값을 최소화 시키기 위한 Weight들의 최적 조합을 찾아가는 과정을 최적화라 표현한다.
가장 대표적인 알고리즘으로 GD(Gradien Decent), Adam, Momentum 등이 있다.
제조 공정에서도 최고 품질의 제품을 개발하거나, 원가를 절감을 위한 의사결정 과정에서 최적화 알고리즘이 요구된다.
예를 들어,
① 공정 수율을 최대화 하기 위한 공정 운전 조건(ex 4개의 온도 조합) 최적화나
② 원가 절감을 위해 품질에 영향을 주지 않는 선에서 셀 전압을 낮추기 위한 최적 셀 전압 조합 찾기 등이 있다.
예시 ① 을 딥러닝 최적화에 대입시켜보면
Cost function = 온도 조합을 X변수(독립변수)로 넣고 수율을 Y(target, 종속변수)로 학습한 모델
Weight = 4개의 온도 조합
이 되겠다.
이런 최적화를 위한 다양한 알고리즘이 존재하는데, 그 중 GA(Genetic Algorithm)에 대해 설명하겠다.
Genetic Algorithm(유전 알고리즘)이란?
GA는 말 그대로 생물학적 진화에 바탕을 둔 통계적 모델이다.
위키피디아에 따르면 GA를 다음과 같이 설명하고 있다.
유전 알고리즘은 자연계의 생물 유전학에 기본 이론을 두며, 병렬적이고 전역적인 탐색 알고리즘으로서, 다윈의 적자생존 이론을 기본 개념으로 한다. 유전 알고리즘은 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 낸다. 여기에서 해들을 나타내는 자료구조는 유전자, 이들을 변형함으로써 점점 더 좋은 해를 만들어 내는 과정은 진화로 표현할 수 있다.
달리 표현하면, 유전 알고리즘은 어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한(Simulated evolution) 탐색 알고리즘이라고 말할 수 있다.
유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라기 보다는 문제를 풀기 위한 접근방법에 가까우며, 유전 알고리즘에서 사용할 수 있는 형식으로 바꾸어 표현할 수 있는 모든 문제에 대해서 적용할 수 있다. 일반적으로 문제가 계산 불가능할 정도로 지나치게 복잡할 경우 유전 알고리즘을 통하여, 실제 최적해를 구하지는 못하더라도 최적해에 가까운 답을 얻기 위한 방안으로써 접근할 수 있다. 이 경우 해당 문제를 푸는 데 최적화되어 있는 알고리즘보다 좋은 성능을 보여주지는 못하지만, 대부분 받아들일 수 있는 수준의 해를 보여줄 수 있다.
이러한 생물의 진화 과정, 즉 자연 선택과 유전 법칙 등을 모방한 알고리즘들로 진화 전략(Evolutionary strategies), 유전 프로그래밍(Genetic programming) 등 여러 형태의 이론과 기법들이 최근에 활발히 연구되고 있다. 유전 알고리즘은 이 중에서 가장 기본이 되고 대표적인 알고리즘으로, 자연과학/공학 및 인문 사회 과학 분야에서 비선형 또는 계산 불가능한 복잡한 문제를 해결하는 데 널리 응용되고 있다.
GA 동작 원리
동작 원리를 간단하게 설명하면,
먼저, random한 초기 염색체(최적의 해가 될 후보들)를 생성하고, 이 중 자연 선택된 염색체들끼리 교차(Crossover)&변이(Mutation) 연산을 하여 자식 세대를 생성한다. 이 과정을 반복하면서 점차 최적의 해를 찾아간다.
유전알고리즘이 어떻게 동작하는지 자세한 과정은 각 step 별로 R로 구현한 코드와 함께 설명하겠다.
R코드는 이 사이트를 참고하였다. (참고한 사이트에서는 코드에서의 값과 설명을 위한 예시가 달라 좀 헷갈렸다. 본 포스팅에서는 코드의 값과 설명을 위한 예시를 같이 하여 진행하겠다.)
Step 0. 문제 정의
먼저, 최적화 하고 싶은 문제를 정의한다.
문제는 다음과 같다.
$ 2a^2 + b = 57 $ 를 만족하는 최적의 a와 b를 추정해보자.
위 식은 다음과 같이 쓰일 수 있으며,
$ f(a,b) = 2a^2 + b - 57 $ 에서 f(a,b) = 0이 되는 a와 b를 찾는 문제로 재해석 할 수 있다.
Step 1. Initialize Population
위 문제를 해결하기 위해 먼저 random한 초기 염색체를 생성해준다.
여기서 염색체란 최적값일수도, 아닐수도 있는 a와 b의 모음이다.
이를 구현하는 R코드는 다음과 같다.
set.seed(3)
intial_popu <- NULL
x <- 1
repeat {
crm <- runif(2,1,10)
crm <- as.integer(crm)
intial_popu <- rbind(intial_popu,crm)
x = x+1
if (x == 7){
break
}
}
rownames(intial_popu) <- c('Cromosome1','Cromosome2','Cromosome3','Cromosome4','Cromosome5','Cromosome6')
print(intial_popu)
(처음에 set.seed(3) 은 매 번 같은 결과를 내기 위해 seed를 설정해준 코드로, 생략 가능하다.)
결과는 다음과 같다.
첫번째 열이 a, 두 번째 열이 b로 random한 6개의 초기 염색체가 생성되었다.
(6이라는 숫자는 hyper parameter로, 이미 R에 구현된 GA라이브러리에서는 popSize라는 파라미터를 의미한다.)
Step 2. Selection
이번 step은 위에서 생성한 초기 염색체 집단(population) 중 더 좋은 염색체를 선택하는 단계이다.
실제 생물학적으로도 더 우월한 유전자가 선택되어 살아남고, 그렇지 못한 유전자는 도태되는 것과 같은 원리이다.
여기서 선택된 염색체만이 자식을 낳아 다음 새대로 이어질 수 있다.
Genetic Algorithm에서 염색체를 선택하는 방법은 다음과 같다.
1. 초기 염색체를 정의된 function에 fitting하여 값을 계산한다.
2. 계산된 값이 얼마나 적합한지 적합도를 계산한다.
3. 적합도에 기반하여 다음 세대에 생존할 염색체를 선택한다.
각 단계를 코드로 보면 다음과 같다.
1. 초기 염색체를 정의된 문제에 적합하여 값을 계산한다.
fit <- function(A){
a <- A[1]
b <- A[2]
return(((2*a^2 + b) - 57))
}
fitness <- apply(intial_popu, 1, FUN = 'fit')
초기 염색체로 정의된 intial_popu를 정의한 식에 넣어 값을 계산한다.
결과는 다음과 같다.
2. 계산된 값이 얼마나 적합한지 적합도를 계산한다.
여기서 적합도는 확률을 의미한다.
즉, 6개의 염색체가 각각 주어진 function에얼마나 적합한지 0~1 사이의 값으로 나타나며, 합은 1이어야 한다.
적합도를 계산하는 코드는 다음과 같다.
fitness <- abs(fitness)
fitting <- 1/(fitness) # to maximize
probfitting <- fitting/sum(fitting)
최적화 하고자 하는 문제가 f(a,b) = 0이 되는 a와 b를 찾는 것이므로,
값이 0과 얼마나 떨어져있는지를 계산하기 위해 abs()를 씌워주었고,
값이 더 적합할 수록 큰 값을 가져야 하므로 1/fitness를 해주었다.
즉, 계산된 값이 0에 가까울수록 fitting은 큰 값을 가지게 된다.
이후, 각각의 값을 모두 더한 값으로 나누어주면 각 염색체가 function에 얼마나 적합한지 적합도(즉, 확률)를 계산할 수 있다.
(만약 그냥 function을 최대화 시키는 값을 찾는 문제라면, 위 코드에서 첫번째와 두번째 줄은 생략하고 fitting된 값으로 바로 적합도를 계산하면 된다.)
결과는 다음과 같다.
3. 적합도에 기반하여 다음 세대에 생존할 염색체를 선택한다.
여기서 Roulette wheel 이라는 개념이 나오는데, 적합도에 기반하여 확률적으로 룰렛판을 돌려 다음 세대에 생존할 염색체를 선택하는 방법이다.
위에서 계산한 적합도를 룰렛판으로 만들면 다음과 같다.
주황색부터 시계방향으로 Cromosome1, 2, 3, ..., 6의 적합도를 의미한다.
(R에서 파이차트 그리는 방법은 여기를 참고하면 된다.)
이제 이 룰렛판을 돌려 다음 세대에 자식을 물려줄 염색체를 선택한다.
룰렛판을 돌려서 선택한다는 개념을 알고리즘에 적용하는 방법은 다음과 같다.
먼저, 0~1 사이의 random한 값을 6개 뽑아준다.
6개인 이유는 이전 세대와 다음 세대가 같은 수의 염색체를 가져야 하기 때문이다.
set.seed(1)
prob_gen <- runif(6,0,1)
다음으로, 룰렛휠에서 생성한 6개 값(prob_gen)이 가리키는 염색체를 선택한다.
좀 더 쉬운 설명을 위해 파이 차트 형태의 룰렛을 누적합의 형태로 일자로 피면 다음과 같다.
여기에 위에서 random하게 생성한 6개 숫자의 위치를 나타내면 다음과 같다.
즉, 6개 숫자의 위치가 가리키는 4, 5, 6, 6, 6, 6번째 염색체가 선택되는 것이다.
0에 가장 가까운 6번째 염색체가 많이 선택된 것을 볼 수 있다.
이를 R 코드로 나타내면 다음과 같다.
newpopulation <- NULL
for(rr in prob_gen){
# cat("=============================
# rr : ", rr,"\n\n")
sum <- 0
for(prob in probfitting){
# cat("prob : ",prob,"\n")
sum <- sum + prob
# cat("-> sum : ", sum, "\n")
if(rr < sum){
cat("\n in if \n")
bin <- prob
cromosomeS <- which(probfitting == bin, arr.ind = T)
# cat("cromosomeS : ", cromosomeS,"\n")
if(length(cromosomeS)>1){
cromosomeS <- cromosomeS[1]
} else{
cromosomeS <- cromosomeS
}
cromname <- paste0('Cromosome',cromosomeS[1])
newcromosome <- intial_popu[which(rownames(intial_popu) == cromname),]
break
}
}
newpopulation <- rbind(newpopulation,newcromosome,deparse.level = 2)
}
rownames(newpopulation) <- rownames(intial_popu)
(주석처리 해 놓은 cat() 부분에 주석을 풀면 각 for loop마다 어떤 결과를 찍는지 확인할 수 있다.)
초기 population과 선택된 새로운 population은 다음과 같다.
기존의 초기 population(intial_popu)에서 Cromosome4, 5, 6이 선택된 것을 확인할 수 있다.
Step 3. Crossover
이제 이 선택된 염색체들을 교차&변이 하여 자식 염색체를 만든다.
이번 step은 그 중 교차에 해당하는 단계이다.
Crossover를 수행하기에 앞서, 염색체들을 2진수로 바꾸어 합쳐준다.
즉, Cromosome1의 a=6과 b=6은 01100110으로,
Cromosome2의 a=5과 b=5은 01010101으로,
Cromosome5의 a=2과 b=3은 00100011으로 바꾸어준다.
이 때, 2진수로 변경된 각각의 값을 유전자라 한다.
이를 수행하는 코드는 다음과 같다.
binary_popu <- matrix(NA,nrow = 6,ncol = 8)
for(i in 1:nrow(newpopulation)){
x <- decimal2binary(newpopulation[i,1],4)
binary_popu[i,1:4] <- x
y <- decimal2binary(newpopulation[i,2],4)
binary_popu[i,5:8] <- y
}
rownames(binary_popu) <- rownames(newpopulation)
이후, 교차율에 해당하는 염색체 수 만큼, 임의로 선택한 위치의 값을 교차한다.
교차율은 0~1 사이의 확률값이며, 전체 population 중 몇 %의 염색체를 교차할 지 정하는 hyper parameter값이다.
즉, Step 2에서 자연 선택되었어도 모두 교차하여 자식을 낳을 수 있는 것은 아니고, 확률에 의해 선택된 염색체만 교차할 수 있다.
(GA 라이브러리에서는 pcrossover라는 파라미터로 이 값을 정한다.)
교차율을 0.5로 지정하고, 교차할 염색체를 선택한다.
cross_paramter <- 0.5 # pcrossover in ga(R)
crom_cross <- sample(1:6,cross_paramter*6)
1, 2, 5번 염색체가 교차할 염색체로 선택되었다.
이 1, 2, 5번 염색체가 바로 부모 염색체가 된다.
parents <- binary_popu[crom_cross,]
이후, 교차를 진행할 임의의 위치를 정하고 부모 염색체간 교차를 진행하여 자식 염색체를 생성한다.
position = 2 ##crossover position
cross_parent <- parents
cross_parent[1,1:position] <- parents[2,1:position]
cross_parent[2,1:position] <- parents[3,1:position]
cross_parent[3,1:position] <- parents[1,1:position]
2번째 위치의 염색체를 임의로 지정하여 교차를 진행해 주었다.
결과는 다음과 같다.
교차하는 위치가 꼭 1개일 필요는 없다. 원하는 개수, 원하는 위치를 지정하여 교차해주면 된다.
Crossover 다른 예시
이제 생성한 자식을 원래 population에 대체해준다.
listofindex <- which(row.names(binary_popu) %in% row.names(cross_parent))
offSpring <- binary_popu
offSpring[listofindex,] <- cross_parent
1, 2, 5번 염색체가 자식 염색체를 생성했으므로, 그 위치에 대체해준다.
Step 4. Mutation
변이 단계는 유전자의 값을 변경하는 단계이다.
자연에서 발생하는 변이는 안좋게 보이는 경향이 있으나, 유전 알고리즘에서는 적합도를 증가시킬 수 있는 방법이다.
물론 더 좋지 않은 결과를 만들 수도 있지만,
변이 과정이 없다면 선택과 교차만을 반복하다 어느새 동질적인 해 집단에 정체되어, 적합도가 향상되지 못하고 local minimum에 빠질 수 있다.
변이과정은 염색체에서 임의로 선택한 유전자의 값을 반대로 뒤집는다. (0->1, 1->0)
몇 개의 유전자를 변경할지는 하이퍼 파라미터로, GA 라이브러리에서는 pmutation이라는 parameter로 확률 값을 전달한다.
GA 라이브러리에서 pmutation의 default값은 0.1이다. 즉, 다른 값을 입력해주지 않으면 전체 유전자 중 10%의 유전자에 변이를 일으킨다는 뜻이다.
본 예시로 보면, 각 8개의 유전자로 이루어진 6개의 염색체가 있으므로 총 48개의 유전자가 있다. 이 중 10%는 4~5개가 되겠다.
random하게 4개 or 5개의 유전자 값을 반대로 바꾸어준다.
R로 구현한 코드는 다음과 같다.
mutation_paramter <- 0.1 # pmutation in ga
no.of.mutations <- floor(nrow(offSpring) * ncol(offSpring) * mutation_paramter) # 4
set.seed(1)
randrow <- round(runif(no.of.mutations,1,nrow(offSpring))) # 돌연변이를 일으킬 raw
# 2 3 4 6
set.seed(1)
rancol <- round(runif(no.of.mutations,1,ncol(offSpring)))
# 3 4 5 7
for(r in 1:length(randrow)){
if(offSpring[randrow[r],rancol[r]] == 0){
offSpring[randrow[r],rancol[r]] <- 1
}else{
offSpring[randrow[r],rancol[r]] <- 0
}
}
몇 %의 유전자를 변형할 지 mutation_parameter로 지정해주고, 몇 개의 유전자를 변형할 지 계산하여 no.of.mutations 변수에 넣어준다.
다음, random하게 돌연변이를 일으킨 raw와 col의 위치를 뽑아 각각 randrow와 rancol 변수에 넣어준다.
마지막으로, 해당 위치의 유전자 값을 바꾸어준다.
결과는 다음과 같다.
이를 그림으로 설명하면 다음과 같다.
이제 이진수로 변경되어있는 염색체들을 다시 10진수로 바꾸어주고, 해결하고자 하는 function에 얼마나 적합한지 계산한다.
2진수 값을 10진수로 변경하는 코드는 다음과 같다.
offSpring_inter <- matrix(NA,6,2)
for(i in 1:nrow(offSpring)){
a <- binary2decimal(offSpring[i,1:4])
b <- binary2decimal(offSpring[i,5:8])
offSpring_inter[i,1] <- a
offSpring_inter[i,2] <- b
}
rownames(offSpring_inter) <- rownames(offSpring)
이를 다시 function에 fitting 하면 다음과 같다.
6번째 염색체에서 적합시키고자 했던 0이라는 숫자가 나왔다.
즉, $ 2a^2 + b = 57 $ 을 만족시키는 최적의 a와 b는 5와 7임을 GA 알고리즘을 통해 찾았다.
본 포스팅에서 다룬 문제는 매우 간단하여 반복없이 한 번에 최적값을 찾을 수 있었으나, 일반적으로는 Step 4에서 다시 Step 2로 돌아가 선택 -> 교차 -> 변이 -> 선택 -> ... 과정을 반복한다.
반복을 멈추는 조건은
이번 문제처럼 원하는 값이 뚜렷한 경우에는 해당 값을 찾을 때 까지 반복할 수도 있으나,
일반적으로 GA는 주어진 function을 최대화 시킬 수 있는 최적의 값을 찾는 것이 목적이다.
이럴 때는, 자식 세대의 염색체 적합도 평균이 부모 세대의 엽색체 적합도 평균보다 나아지지 않으면 멈추거나, 혹은 maxiter를 지정해 준다. (GA 라이브러리에서 maxiter의 default값은 100이다. 즉, Step2 ~ Step4의 과정을 최대 100번 반복한다.)
GA알고리즘은 다양한 분야에 최적화 기법으로 사용되고 있다.
아래 링크는 하이퍼 파라미터 튜닝에 GA를 사용하는 방법을 소개하고 있으며,
https://towardsdatascience.com/genetic-algorithm-in-r-hyperparameter-tuning-5fc6439d2962
Genetic Algorithm in R: Hyperparameter Tuning
Tune your model’s hyperparameter using a Genetic Algorithm in R
towardsdatascience.com
아래 링크는 GA를 사용하여 Feature Selection하는 방법을 소개하고 있다.
type을 binary로 하여 각 변수를 선택할지 안할지 1과 0으로 찾아간다.
https://towardsdatascience.com/feature-selection-using-genetic-algorithms-in-r-3d9252f1aa66
Feature Selection using Genetic Algorithms in R
Introduction and tutorial on using feature selection using genetic algorithms in R.
towardsdatascience.com
외에 R에서 GA라이브러리를 활용하는 코드는 여기에 정리해 두었다.
GA는 일반적으로 주어진 function을 최대화 하는 것이 목표이다. GA 라이브러리 역시 그러하다.
이럴 때, 최소화 시킬 수 있는 값을 찾는 방법과 특정 값으로 최적화 시킬 수 있는 방법 역시 함께 정리해 두었다.