목차
1. 정의
유전 알고리즘(Genetic Algorithm)은 자연 세계의 진화과정을 전역 최적화 문제에 도입한 방식이다. 유전 알고리즘에서 활용하는 유전적 방식들은 다음과 같다.
1.
우수한(생존에 적합한) 유전자는 살아날 확률이 높다.
2.
부모의 유전자는 자식 유전자로 계승된다.
3.
유전자에는 돌연변이가 발생한다.
여기서 유전자는 solution으로, 돌연변이는 neighborhood로 볼 수 있다. 그리고 이 두 가지 전제를 이용하여 좀 더 자세하게 Update Step을 살펴보자.
2. Update Step
다른 알고리즘들과 달리 유전 알고리즘은 고유의 Step별 이름이 존재하는 것이 특징이다. 그리고 그 이름들은 각각 진화방식과 관련되어 있다. 각 진화방식에 맞추어 알고리즘 단계를 살펴보자.
Initial Population
우선 아무것도 없는 상태에서 자손이 나타날 수는 없기 때문에 맨 처음 세대가 필요하다. 이를 Initial Population이라고 부른다. 이 Initial Population은 완전히 Random하게 선택된다.
Fitness Function
앞선 정의에서 유전 알고리즘의 전제 중 하나는 우수한 유전자가 살아날 확률이 높다는 것이었다. 그렇다면 우리는 우리가 찾은 유전자(solution)가 우수한지를 먼저 판단해야 된다. 이때 판단의 기준이 Fitness Function(적합함수)의 Fitness Score(적합도)다. 진화에 적합한지(Fit) Fitness Function에 유전자를 넣어 Score를 도출하여 판단하는 것. Fitness Function은 고정되어 있지 않고 문제나 사용자에 따라 변할 수 있다. 이전 알고리즘들에서 나왔던 목적함수라고 생각하면 편한다.
Selection
Fitness Score에 따라서 확률적으로 부모가 될 유전자들을 선택한다. 이때 score가 높은 유전자는 여러 번 선택될 가능성이 올라가게 된다. 주의할 점은 단순히 Fitness Function을 내림차순하여 부모 유전자를 결정해서는 안 되고 결과값이 높은 유전자가 선택될 가능성이 높도록 설정해야 한다.
Crossover
부와 모가 결정되었으면 특정한 기준으로 부와 모의 유전자를 섞어서 자식 유전자를 만든다. 일반적으로는 랜덤하게 선을 그어서 Swap을 하는 방식을 택한다(이는 뒤에 그림을 보면 더 잘 이해가 될 것).
Mutation
자식 유전자에서 임의의 확률로 돌연변이가 나타나도록 만든다. 여기서 돌연변이는 neighborhood로 볼 수 있다. 주의할 점은 돌연변이는 항상 나타나는 것이 아니라 나타날 수도 있고 나타나지 않을 수도 있다.
그리고 Fitness Function부터 Mutation까지의 과정을 원하는 solution을 찾을 때까지 반복한다.
아래는 위의 과정을 설명하는 그림이다.
3. 장단점
장점
•
비선형 또는 계산이 복잡한 문제에 쉽게 활용될 수 있다.
단점
•
실제로 사용하기에 비효율적일 수 있다.
4. Code 및 활용
Hill-Climbing Search 과 Simulated Annealing 에서 예시로 들었던 Baseball Salary 문제를 Genetic Algorithm으로 해결해보자.
기본 셋팅
•
각 Generation의 크기는 20이다.
•
Iteration은 100번이다.
•
mutation rate는 0.01로 설정하고 이는 각 변수가 flip될(포함되면 제외 제외되면 포함) 확률이다.
•
finess score는 AIC의 rank를 활용한다.
•
부모 중 첫번째는 fitness score를 기준으로 뽑고 두 번째는 완전히 랜덤으로 뽑는다.
•
Crossover는 Swap 방식을 사용한다.
Code
R을 사용하여 작성하였다.
## INITIAL VALUES
baseball.dat = read.table('baseball.dat',header=TRUE)
baseball.dat$freeagent = factor(baseball.dat$freeagent)
baseball.dat$arbitration = factor(baseball.dat$arbitration)
baseball.sub = baseball.dat[,-1]
salary.log = log(baseball.dat$salary)
n = length(salary.log)
m = length(baseball.sub[1,])
P = 20 #각 generation의 크기
itr = 100 #generation을 몇 번 돌릴 것인지
m.rate = .01 #mutation rate
r = matrix(0,P,1) #Generation의 AIC rank
phi = matrix(0,P,1)#Generation의 fitness values
runs = matrix(0,P,m)
runs.next = matrix(0,P,m)
runs.aic = matrix(0,P,1)
aics = matrix(0,P,itr)
run = NULL
best.aic = 0
best.aic.gen = rep(0,itr)
#Starting generation 설정, FITNESS VALUES
set.seed(1234)
for(i in 1:P){
runs[i,] = rbinom(m,1,.5) #random으로 variable selection
run.vars = baseball.sub[,runs[i,]==1]
g = lm(salary.log~.,run.vars)
runs.aic[i] = extractAIC(g)[2]
aics[i,1] = runs.aic[i]
if(runs.aic[i] < best.aic){
run = runs[i,]
best.aic = runs.aic[i]
}
}
r = rank(-runs.aic) #starting genertation의 aic에 rank를 매겨주자.
phi = 2*r/(P*(P+1)) #rank를 이용하여 fitness value 구해줌.
best.aic.gen[1]=best.aic #starting genertation의 best.aic값.
## MAIN
for(j in 1:itr-1){
# Generation을 이어가자. 부모 중 첫 번째는 Fitness value를 기준으로 좋은 것을 뽑고
# 두 번째는 완전히 랜덤으로 뽑는다.
for(i in 1:10){
p1 = sample(1:P,1,prob=phi)
parent.1 = runs[p1,]
parent.2 = runs[sample(c(1:P)[-p1],1),] #중복이 되지 않도록 하자.
pos = sample(1:(m-1),1) #분리가 되는 지점을 정해주자.
mutate = rbinom(m,1,m.rate) #mutation rate에 기반해서 돌연변이가 일어나는 변수를 선택
runs.next[i,] = c(parent.1[1:pos],parent.2[(pos+1):m]) #다음 세대 앞 부분(돌연변이 적용 전)
runs.next[i,] = (runs.next[i,]+mutate)%%2 #다음 세대 앞 부분(돌연변이 적용)
mutate = rbinom(m,1,m.rate)
runs.next[P+1-i,] = c(parent.2[1:pos],parent.1[(pos+1):m]) #다음 세대 뒷 부분(돌연변이 적용 전)
runs.next[P+1-i,] = (runs.next[P+1-i,]+mutate)%%2 #다음 세대 뒷 부분(돌연변이 적용)
}
runs = runs.next
# New generation에서의 aic와 fitness value 업데이트.
for(i in 1:P){
run.vars = baseball.sub[,runs[i,]==1]
g = lm(salary.log~.,run.vars)
runs.aic[i] = extractAIC(g)[2]
aics[i,j+1] = runs.aic[i]
if(runs.aic[i] < best.aic){
run = runs[i,]
best.aic = runs.aic[i]
}
}
best.aic.gen[j+1]=best.aic
r = rank(-runs.aic)
phi = 2*r/(P*(P+1))
}
## OUTPUT
run # BEST LIST OF PREDICTORS FOUND
best.aic # AIC VALUE
R
복사
[1] 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0
[1] -416.8813
## PLOT OF AIC VALUES
plot(-aics,xlim=c(0,itr),ylim=c(50,425),type="n",ylab="Negative AIC",
xlab="Generation",main="AIC Values For Genetic Algorithm")
for(i in 1:itr){points(rep(i,P),-aics[,i],pch=20)}
R
복사
→ Generation이 높아질수록 Negative AIC가 높은 쪽에 Solution이 몰리는 것을 확인할 수 있다.