시뮬레이티드 어닐링/유전자 알고리즘

저번 장에서 최적화 중 local minimum에 빠지는 것을 방지하기 위한 방법으로 두가지를 제시하였고, 본 장에서 예시를 통해 이어서 설명해보록 한다.

 

1. 시뮬레이티드 어닐링(Simulated Annealing): 물리학에서 영감을 받은 최적화 기법이다.. 어닐링이란 합금을 가열한 후 천천히 냉각하는 과정을 말한다. 원자는 주변을 뛰어다니다가 점차 낮은 에너지 준위로 정착하기 때문에, 원자들은 가장 낮은 에너지 배치를 찾을 수 있다. 각설하고, 시뮬레이티드 어닐링은 계속해서 좋은 방향으로 움직인다. 처음에는 좋지 않은 해답으로 시작할 순 있지만 점차 끝에 이르러서는 더 좋은 해답만을 선택하게 된다..

매 반복마다 해답 내 숫자들 중 하나를 무작위로 선택하고 특정한 방향으로 변경한다.

큰 비용을 가진 해답을 선택할 확률을 아래 공식으로 결정한다. 

$p = e^{((-highcost-lowcost)/temperature)}$     : 온도(더 나쁜 해답을 선택할 가능성)가 매우 높으면 지수가 거의 0에 가까워져 확률은 거의 1이 된다. 온도를 내리면 높은 비용과 낮은 비용과의 차이 값이 더 중요해진다.  큰 차이는 더 적은 확률을 말하기 때문에 알고리즘은 아주 나쁜 해답들에 비해 약간 나쁜 해답들을 더 선호하게 된다.

 

이 알고리즘의 구현

 

def annealingoptimize(domain, costf, T=10000.0, cool=0.95, step=1):
    #무작위 값으로 초기화함
    vec=[random.randint(domain[i][0], domain[i][1]) for i in range(len(domain))] # 0~9 까지 각각 한자리 정수를 출력 (n1, n2)
    
    while T>0.1:
        #인덱스 중 한 개를 선택함
        i=random.randint(0,len(domain)-1) #0에서 11까지의 12개 정수 중에서 한 값을 출력.
        
        #변경할 방향을 선택함
        dir=random.randint(-step, step) # 0 or 1 or -1
        
        #변경할 값 중의 하나로 새로운 리스트를 만듦
        vecb=vec[:]
        vecb[i]+=dir
        if vecb[i]<domain[i][0]:vecb[i]=domain[i][0]
        elif vecb[i]>domain[i][1]: vecb[i]=domain[i][1]
        
        #현재 비용과 새로운 비용을 계산함
        ea=costf(vec)
        eb=costf(vecb)
        r=round((-eb-ea)/T,4) # 기존에 있던 비용이
        print(r)
        p=round(pow(math.e, r),4) # 더 큰비용을 선택할 확률. 즉 비용이 많이 드는걸 선택할 확률. 안좋은거 선택할 확률.
        print(p)
        
        #더 좋은지, 또는 확률이 차단 기준 이하인지 판단함
        if (eb<ea or random.random()<p):
            vec=vecb
            
        #온도를 줄임
        print(T)
        T=T*cool
    return vec


annealingoptimize(domain, schedulecost, T=10000.0, cool=0.95, step=1)

s=annealingoptimize(domain, schedulecost, T=10000.0, cool=0.95, step=1)
schedulecost(s)
#결과: 2795

printschedule(s)

 

 

생각보다 결과가 .. 눈에 띄게 좋진 않다. 뭐 데이터가 많지도 않고, 저 결과도 사실 엄청 뚜드리다가 나온거 올린거라서 .. 아무튼.

 

어닐링 과정을 요약하면,

 domain 인자로 규정된 범위안에 있는 모든 값들로 적절한 길이의 무작위로 해답을 만든다.

 T(temperature)와 cool (cooling)은 파라메타 값이다.

 각 방향마다 해답 내 무작위 인덱스를 정해 i에 넣고, -step, step -1, 0 , 1사이의 숫잘 dir에 할당하고 현재 비용과 dir만큼 i에 있는 값을 변경했던 비용도 계산한다.

 확률을 계산한 부분에서는 T가 작아질수록 값이 작아진다. 0과1 사이의 랜덤으로 생성한 소수가 이 값보다 작거나, 새로운 해답이 더 좋은 경우 이 함수는 새로운 해답을 선택한다. 이 함수는 온도가 거의 0이 될때까지 매번 온도에 냉각 속도를 곱하면서 루프를 돈다.

 

시뮬레이티드 알고리즘은 처음에 비탈길을 빠르게 올라갈 수 있어서 언덕등반 알고리즘이 가졌던 local minimum에 빠지는 경우를 생각할 필요가 없다. 관건은 $p = e^{((-highcost-lowcost)/temperature)}$ 식 안에 현재 비용과 다음 비용을 넣어 주는 것이고, 그 다음 비용을 구하기 위한 해답을 어떻게(랜덤으로) 지정할 것이냐에 달려있는 것이다. wiki: "전역 최적화 문제에 대한 일반적인 확률적 메타 알고리즘이다. 이 기법은 광대한 탐색 공간 안에서, 주어진 함수의 전역 최적해에 대한 좋은 근사를 준다"

 

 

 

 

 

 

 

2. 유전자 알고리즘(enetic algorithm)

 이 알고리즘은 개체군(population)이란 무작위 해답들을 생성하면서 시작된다. 최적화 단계마다 전체 개체군별 비용 함수가 계산되어 해답의 순위 목록을 만든다. 

 해답의 순위 목록을 만든 후에는 다음 세대의 새로운 개체군을 만든다. 먼저, 현재의 개체군에 대한 최상위 해답을 새로운 개체군에 추가한다. 이 과정일 엘리트 선발(elitism)이라고 한다. 이 새로운 개체군의 나머지는 최고 해법을 수정하여 만든 완전히 새로운 해법을 구성한다.

 해답을 변경하는 두가지 방법

 1. 돌연변이(mutation): 소량의 간단하고 무작위적인 변화를 기존 해답에 적용시키는 방법이다. 해답 안에 있는 숫자 중 한 개를 선택하고 증가 또는 감소시켜 만드는 것이다.

 2. 교배(crossover)와 번식(breeding): 최적 해답 두 개를 골라 어떤 방식으로 그 둘을 결합하는 것이다. 간단한 방법은 한 해답에서 무작위로 몇 개 요소들을 선택하고, 다른 해답에서 나머지를 선택하여 만드는 것이다. 일반적으로 기존과 동일한 크기인 새로운 해답은 최적 해답을 무작위로 돌연변이시키거나 번식시켜 만든다. 그런 다음 새로운 개체군에 순서를 매긴 후 다른 개체군을 만드는 과정을 계속 반복한다. 이 과정을 정해진 횟수만큼 계속하거나 몇 세대에 걸쳐 개선이 없을 때까지 계속한다.

 

 

 

 

 

def geneticoptimize(domain, costf, popsize=50,step=1,mutprob=0.2,elite=0.2,maxiter=100):
    
    #돌연변이 연산
    def mutate(vec):
        i=random.randint(0,len(domain)-1)
        if random.random()<0.5 and vec[i]>domain[i][0]:
            return vec[0:i] + [vec[i]-step]+vec[i+1:]
        elif vec[i]<domain[i][1]:
            return vec[0:i]+[vec[i]+step]+vec[i+1:]
        
    #교배 연산
    def crossover(r1,r2):
        i=random.randint(1,len(domain)-2)
        return r1[0:i]+r2[i:]
    
    #초기 개체군을 생성함
    pop=[]
    for i in range(popsize):
        vec=[random.randint(domain[i][0], domain[i][1]) for i in range(len(domain))]
        pop.append(vec)
        
    #각 세대의 선발된 엘리트 개체군 수를 계산함
    topelite=int(elite*popsize)
    
    #메인루프
    for i in range(maxiter):
        scores=[(costf(v),v) for v in pop]
        scores.sort()
        ranked=[v for (s,v) in scores]
        
        #생존자들로 시작함
        pop=ranked[0:topelite]
        
        #생존자에 돌연변이와 번식을 수행함
        while len(pop) < popsize:
            if random.random()<mutprob:
                
                #돌연변이
                c=random.randint(0,topelite)
                pop.append(mutate(ranked[c]))
            else:
                #교배
                c1=random.randint(0,topelite)
                c2=random.randint(0,topelite)
                pop.append(crossover(ranked[c1],ranked[c2]))
                
        #현재 최고 점수를 출력함
        print(scores[0][0])
    return scores[0][1]

 

s=geneticoptimize(domain,schedulecost)
schedulecost(s)

...

...

 

상당히 재미있는 알고리즘이라고 생각이들고 성능도 괜찮은 것 같다. 후에 이 유전자 알고리즘의 확장에 대해 더 알아보기로 한다.

 

유전자 알고리즘이 생소하여 마침 설명이 잘 되어 있는 사이트를 찾았다. 완전히 이해가 가지는 않지만 생물학에서 사용하는 진화론적 이론을 응용하는 것 자체가 참신하다는 생각도 들고, 모든 분야는 서로 연결되어 있지 않지 않구나! 라는걸 느낀다 ..

 

유전자 알고리즘 흐름도

 

참조사이트: http://www.aistudy.co.kr/biology/genetic/genetic_jeong.htm