Genetic Algorithm

유전알고리즘은 최적화 알고리즘의 한 종류로,

 

적절한 정보의 Coding을 통해서 유전/진화 Modeling을 구축하고, 최적해를 구하는 알고리즘 입니다.

우월한 유전자를 가진 자손이 상대적으로 후대에 유전정보를 전달할 가능성이 높다!

말 그대로 유전, 적자생존 + 돌연변이발생이라는 생명체의 진화과정을 모사한 알고리즘이라 할 수 있습니다.

 

이때, 각 자손은 유전자(Parameter)를 가지고 있고, 이 유전자에 따른 우월성을 따지게 됩니다.

 

적자생존 이기 때문에, 우월한 유전자는 상대적으로 유리하게 살아남아 유전자를 다음 세대로 전달하고

 

그렇지 못한 유전자는 사라지게 됩니다.

 

이때 유전알고리즘의 특징으로 교차와 돌연변이가 있습니다.

 

 

두개의 개체를 선택하여, 유전자를 교차하는 방법론

1. 교차

교차는 두개의 개체를 임의 or 우월성에 따라 추출하고, 두 개체의 교배(유잔자 혼합)을 하는것을 의미합니다.

 

개체를 선택하는 방법은 랜덤, 우월성에 따른 가중치, Ranking등이 존재하며

(이번 소스코드에서는 우월성을 기준으로 선택하는 방법을 사용했습니다.)

 

우월한 개체일 수록 뽑힐 확률이 높으며, 이렇게 뽑힌 2개의 개체를

 

단일점, 두점, 균등 등 정해진 or 혼합하여 교차, 교차한 결과를 다음 자손개체로 물려주게 됩니다.

 

 

 

유전자의 변이(유전자의 랜덤한 위치에서 값을 바꿔줍니다!)

2. 돌연변이

돌연변이는 선별된 우수한 유전자에서, 추가적인 Noise를 인가해서 추가적인 변이를 유발,

 

기존과 다른 특성이나 개선된 특성이 나오게 유도합니다.

(유전자가 숫자로 되어있는 경우 작은 값을 plus or minus해주고, 

범주형일 경우 해당 범주를 다른 범주값으로 random하게 변화를 줍니다.)

 

특정 형태에서 진화가 멈추는것을 막기 위한 장치라고 보시면 쉬울것 같습니다 :)

 

돌연변이를 진행하는 이유

돌연변이를 진행하지 않을 경우, 정체위치(Local Maximum)에 갖쳐서 빠져나오지 못하는 경우가 발생합니다.

(이때 대부분의 우월한 개체들이 전체위치에 몰려, 아무리 교차를 진행해도 해당 위치를 빠져나오지 못합니다)

 

이러한 경우를 방지하고, Global Maximum에 도달하기위한 보조적인 장치라고 볼 수 있습니다 :)

 

아래는 Multiple Linear Regression의 최적해를 유전알고리즘으로 구하는 Python소스코드입니다.

import random

class Genetic:
    def __init__(self, x, y, batch_size, change_rate, trans_rate):
        self.y = y
        #y값에 Standard Scaler(Max에서 해당 값을 빼고, Range로 나눠줌) 적용        
        temp_max, temp_min = [max(self.y),min(self.y)]         
        for i in range(len(self.y)):
            self.y[i] = (self.y[i] - temp_min)/(temp_max - temp_min)
        self.x = x
        #x값에 Standard Scaler 적용
        for i in range(len(self.x[0])):
            temp_max, temp_min = [max(self.x[i]),min(self.x[i])]             
            for j in range(len(self.y)):
                self.x[j][i] = (self.x[j][i] - temp_min)/(temp_max - temp_min)
        #자손을 만들 Size를 저장해줍니다.
        self.batch_size = batch_size
        #x변수만큼 Weight 생성(-100~100사이 랜덤)
        self.weight = [[random.uniform(-1,1) for i in range(len(x[0]))] for j in range(self.batch_size)]
        #유전알고리즘의 HyperParameter Change_rate 와 Trans_rate를 선언
        #Hyperparameter는 추론으로 구하는 값이 아니라, 사용자가 입력해주는 값을 뜻합니다.
        self.change_rate = change_rate
        self.trans_rate = trans_rate
        #실제 Y값과 비교할 최적화된 y값을 저장합니다.
        self.predict_y_opt = []
        #진화 과정에 따른 MSE값을 저장하는 List를 생성합니다.
        self.history = []
        #각 자손들에 대한 Y예측값을 저장합니다.
        self.predict_y = [[] for i in range(self.batch_size)]
        #이제 X를 가지고 Y를 예측할때 단순다중회귀식을 이용합니다.
        #Y_pred = B1X1 + B2X2.... BnXn(이때 n은 X변수의 개수)로 계산해줍니다.        
        for k in range(batch_size):
            for i in range(len(self.y)):
                temp = 0
                for j in range(len(self.x[i])):
                    temp = temp + self.x[i][j]*self.weight[k][j]
                self.predict_y[k] = self.predict_y[k] + [temp]
        self.delta = [0 for i in range(self.batch_size)]
        #모든 자손(Batch Set)에서 계산된 Y_pred을 가지고
        #각 자손들의 우열성을 가리기 위해서 (Y-Y_pred)^2의 합(Mean Squared Error)을 계산합니다.
        for k in range(batch_size):
            self.delta[k] = sum([pow(self.y[i] - self.predict_y[k][i],2) for i in range(len(self.y))])
        
    def evol(self):        
        #MSE(Mean Squared Error)값이 작은 상위 N%의 유전자(Weight)를 추출        
        temp = sorted(list(zip(self.delta, self.weight)))
        self.history = self.history + [temp[0][0]]
        #zip을 사용할 경우 tuple이 되기 때문에, 추가적으로 List로 변환작업을 진행하였습니다.
        temp = [list(temp[i]) for i in range(len(temp))]
        #코드 내에서는 20%를 사용하였습니다
        temp = temp[0:int(0.2*len(self.delta))]
        #20%의 상위 유전자의 MSE값을 기준으로 MSE값이 낮은수록 높은 비율을 할당합니다.        
        #이번 Case에서는 MSE의 역수값을 기준으로 우선순위를 만들었습니다.
        #역수값을 통해서 역수값의 누적값을 구하기 위해서 MSE의 역수값을 합을 미리 구합니다.
        tot_sum = 0
        for i in range(len(temp)):
            tot_sum = 1/temp[i][0] + tot_sum
        #MSE역수값에서 MSE역수의 총합을 나눠, 각 자손별 우선순위를 설정해줍니다.
        area = 0        
        for i in range(len(temp)):
            area = (1/temp[i][0])/tot_sum + area
            temp[i][0] = area
        #이제 기존 자손들의 Weight값들을 초기화하고, 자손들을 가지고 교배된 유전자를 저장합니다.
        self.weight = []
        for _ in range(self.batch_size):
            #교차 코스
            #이제 Random한 값을 만들어, 2개의 Random한 자손을 추출하여 교배(교차)를 진행합니다.
            #이때 자손의 선택은 MSE의 역수값이 클수록 우선순위를 갖게 됩니다.
            #이제 설정한 Change_rate를 기준으로 난수의 값에따라 교차를 진행하거나, 아니면 랜덤한 자손은 생성합니다.
            if random.uniform(0, 1)<self.change_rate:
                temp_desc = [] #선별된 2개의 자손을 저장할 List        
                opt_weight = [0 for i in range(len(self.x[0]))]                                    
                for i in range(2):
                    this_num = random.uniform(0,1)
                    for j in range(len(temp)):                    
                        if (j==0 and this_num<=temp[j][0]) or (this_num>=temp[j][0]):
                            temp_desc = temp_desc + [temp[j][1]]
                            break        
                #이제 선택된 자손들을 가지고 교차를 진행합니다.
                for i in range(len(temp_desc[0])):
                    if random.uniform(0,1)>0.5:
                        opt_weight[i] = opt_weight[i] + temp_desc[0][i]
                    else:
                        opt_weight[i] = opt_weight[i] + temp_desc[1][i]
            else:
                opt_weight = [random.uniform(-1,1) for i in range(len(self.x[0]))]           
            
            #변이 코스
            #교차완료 된 Weight에서 변이를 진행할 지 말지를 결정합니다.            
            for i in range(len(opt_weight)):
                #각 유전자마다 Random한 값을 산출해서, 유저가 설정한 변이확률을 넘어서면
                #해당 유전자에 작은 random한 값을 더해줍니다. 이번 소스코드에서는 -0.01~0.01 사이값을 사용
                if self.trans_rate>random.uniform(0,1):    
                    opt_weight[i] = opt_weight[i] + random.uniform(-0.01, 0.01)
                else:            
                    pass  
            self.weight = self.weight + [opt_weight]                    
        #새로생긴 우월한자손을 이용해서, 다시 Y_pred을 계산하고 새로운 우월한 자손을 선별합니다.
        self.predict_y = [[] for i in range(self.batch_size)]
        for k in range(self.batch_size):
            for i in range(len(self.y)):
                temp = 0
                for j in range(len(self.x[i])):
                    temp = temp + self.x[i][j]*self.weight[k][j]
                self.predict_y[k] = self.predict_y[k] + [temp]
        self.delta = [0 for i in range(self.batch_size)]
        #이때 가장 우월한 결과를 보여준 자손 하나의 결과를 Optimum 값으로 저장해줍니다.
        temp = 99999999999999        
        for k in range(self.batch_size):
            self.delta[k] = sum([pow(self.y[i] - self.predict_y[k][i],2) for i in range(len(self.y))])
            if self.delta[k]<temp:
                temp = self.delta[k]
                self.predict_y_opt = self.predict_y[k]
        
        
#X의 경우 X1~X00까지 변수가 각각 1~20 까지의 값을 갖으며, 이 셋트가 500개 있습니다.
#Y의 경우 이 500셋트에 해당하는 값을 1~100 사이로 랜덤하게 부여합니다.
x = [[random.randint(1,20) for i in range(100)] for j in range(500)]        
y = [random.randint(1,100) for i in range(500)]

#유전알고리즘을 생성합니다. 이때 교차확률을 90%, 변이확률은 80%로 설정하였습니다.
test = Genetic(x,y,30,0.9,0.8)
#10000회의 진화를 반복합니다.
for i in range(10000):
    test.evol()

temp_max,temp_min = [max(test.predict_y_opt),min(test.predict_y_opt)] 
for i in range(len(test.predict_y_opt)):
    test.predict_y_opt[i] = (test.predict_y_opt[i]-temp_min)/(temp_max - temp_min)
import matplotlib.pyplot as plt
plt.scatter(test.y, test.predict_y_opt)
plt.scatter([i for i in range(len(test.history))],test.history)

10000번의 반복 결과 시각화, 진화를 진행할 수록 예측과 실제 오차가 줄어드는 것을 확인할 수 있다.