유전 알고리듬(Genetic Algorithm) [algorithm] by 바죠

유전 알고리듬 (Genetic Algorithm)

http://en.wikipedia.org/wiki/Genetic_algorithm

http://en.wikipedia.org/wiki/John_Henry_Holland

유전 알고리듬 (Genetic algorithm)

유전 알고리듬은 컴퓨터 알고리듬이다. 다윈의 적자생존에 근간한 컴퓨터 알고리듬이고 광역 최적화 알고리듬으로 잘 알려져 있다. 목적함수 (objective function) 값이 최적화된 해를 찾는데 사용된다. 목적함수 최적화는 최대화 또는 최소화를 말한다. 사실, 여기서는 최대화나 최소화는 같은 의미를 가진다. 목적함수에 부호("+"  -->  "-")를 바꾸면 이들은 사실 같은 의미를 가지고 있다.


유전 알고리듬은 항상 정답을 보장하지 못한다. 결정론적 문제 풀이 방식이 아니다. 하지만, 범용적으로 사용될 수 있는 계산 방법이다. 유전 알고리듬은 발견법(heuristic method) 분류에 속한다. 유전체 그리고 자연선택설 개념을 사용하여 좀 더 발전된 발견법으로 평가되어 metaheuristic method(상위 발견법)라고 불린다. 유전 알고리듬에서는 유전체와 자연선택설을 키워드로 고려한다. 돌연변이는 유전된다. 아울러, 자손은 부모의 유전자를 일정 부분 각각 물려받는다. 이들은 각각 변이와 교차를 의미한다. 유전체가 시간에 따라서 변화하는 것을 지칭한다.


유전 알고리듬은 소위 NP-hard 문제를 풀 때 유용하다. 매우 특수한 분야에서 잘 개발된 문제풀이 방식이 결코 아니다. 특별한 문제를 풀기 위해서 고안되지 않았기 때문이다. 쉽게 설명하면 매우 어려운 문제풀이에 사용된다.


유전 알고리듬은 상당히 일반적이어서 다양한 응용이 가능하다. 자연선택설, 유전체 : 선택, 교차, 변이, 대치 가 기본 개념이다.
시도해(후보해)는 암호화 된다. 해독하면 응용문제의 시도해가 된다. 간단한 문제의 경우 암호화가 필요치 않다. 유전자형, 표현형 사이의 암호화/해독화가 필요한 경우는 복잡한 응용문제 풀이에서 필요하다.



다수의 시도해(trial solution)를 동시에 취급

문제풀이의 시도해는 자연선택설의 개체에 해당한다. 문제풀이에서 동시에 여러 개의 시도해들을 고려한다. 이러한 무리를 세대라고 한다. 새로운 세대는 기존의 세대에서 만들어진다. 여러 개의 시도해들을 동시에 취급하기 때문에 유전 알고리듬은 아주 좋은 병렬 알고리듬의 예가 된다. 풀림 시늉(simulated annealing)에서처럼 단일 시도해를 상정하는 것이 아니고, 여러 개의 시도해들을 동시에 고려한다. 여러 개의 시도해들을 점진적으로 변화시켜 나가려고 한다. 유전 알고리듬은 진화 시늉(simulated evolution)이라고 볼 수 있다. 



선택

경쟁력 있는 개체(시도해)가 부모가 된다. 교차, 변이 두 가지가 허용된 개체들(부모)을 정할 때 사용한다. 부모가 될 두 개체를 뽑을 때, 소위 토나먼트 방식으로 뽑을 수 있다. 먼저 연속해서 서로 다른 두 개체를 무작위로 뽑는다. i, j라고 부른다. j /= i이다. 이 때, i 의 목적 함수가j의 것보다 더 좋다면, 우리는i를 부모로 선택한다. (토나먼트 승자: i)마찬가지로 부모가 될 또 다른 개체를 선택할 수 있다. 물론, 앞에서 구한 구조와는 서로 다른 구조이기만 하면 된다. 만약 같은 구조가 나왔다면, 다른 구조가 나올 때까지 다시 하면 될 것이다. 토나먼트를 여러 라운드로 할 수도 있을 것이다. 그렇게 하면 좀 더 목적함수가 좋은 개체가 부모가 될 확률일 더욱 더 증가하게 된다. 선택, 교차, 변이, 대치 이렇게 4가지 프로그램을 만들어야 한다. 두 개의 개체를 뽑아서 교차를 하려고 한다. 이 때, 목적 함수가 좋은 두 개체를 더 많이 뽑아야 한다. 적어도 좋은 목적 함수를 가진 개체는 뽑힐 확률이 높아야 한다. 이 요구 조건을 어디까지 받아 줄 것인지가 관건이다. 전적으로 받아 주면 곤란하다. 적당히 받아 주어야 한다. 적어도 확률은 높아야 한다. 좋은 목적함수를 받은 개체들이 부모가 될 확률은 높아야 한다. 하지만, 장기적인 관점에서 다양성을 확보하지 못하면 안 된다. 전체적인 퇴보가 올 수 있다. 따라서 최대한 다양성을 존중하는 절차가 반드시 내포되어 있어야 한다. 다시 말해서, 목적함수는 다소 좋지 않더라도 반드시 특이한 구조들은 받아 들여야 한다. 실제로 광역 최적화가 달성 되려고 하면 이렇게 해야 한다.



교차

자손의 유전자는 부모로부터 획득한다. 자손을 만들어 낼 때 사용한다. 교차 없이 변이만 사용할 경우, 유전 알고리듬은 무작위 탐색 방법이 된다. 목적함수 값이 좋은 해들, 예를 들어, 두 개의 좋은 해들 사이의 교차 (crossover) 연산을 도입한다. 교배 연산이라고 생각할 수 있다. 특정한 하나의 시도 해의 변이(mutation)를 또한 도입한다. 이렇게 함으로써, 부모보다 자식에서 보다 좋은 목적함수를 가지게 하는 것이다. 항상 성공하는 것은 아니다. 부모 세대와 다른 새로운 세대를 만든다고 볼 수 있다.  교차, 변이, 둘 중 하나만 사용하면 안 된다. 반드시 두 가지 모두를 사용해야 유전 알고리듬이라고 부른다. 유전 알고리듬에서 새로운 세대를 만들어 내는 방식은 교차, 변이를 통해서 이루어진다.  한 가지 확실한 점은 이것이다. 유전 알고리듬에서는 위에서처럼 현재 해 두 개를 이용하여 대략 절반씩 바꾸어서 새로운 해가 될 수 있을 지를 시험하게 해준다. 이것이 다른 최적화 방법과 근본적으로 다른 점이다. 쉽게 말해서 굉장히 멀리 떨어진 구조(서로 다르게 생긴 시도 해)로 쉽게 이동해서 목적함수를 평가할 수 있게 한다. 대부분의 계산들에서 이런 것들이 허용되지 않는다. 다양성 확보를 위해서 변이가 필요하고 효율적인 시도해의 활용을 위해서 교차가 필요하다. 예를 들어, 분자 동역학 계산에서는 어느 정도 유사한 분자 모양들을 추출한다. 물론, 온도가 높을수록 더 넓은 분자 모양 공간을 탐색할 수 있다. 하지만, 여전히 한계가 있다. 반면, 유전 알고리듬에서는 보다 더 넓은 분자 모양 공간을 둘러다 볼 기회가 많이 제공된다. 소위 마코프 사슬(Markov chain)에서 벗어난 전이가 쉽게 이루어 질 수 있기 때문이다. 이 점이 바로 유전 알고리듬이 다른 여러 최적화 알고리듬에 비해서 우월한 최적화 방법이 되는 부분적인 원인이 된다. 분자 모형의 경우 원자 종류별로 절반에 가깝게 양분해서 각각 새로운 자손을 만들면 된다. 하나의 분자의 질량 중심을 원점으로 이동시킨 다음, z, y, x 축으로 무작위 회전시킨 다음, x 축 왼쪽, x 축 오른쪽으로 분류하면 원하는 분자의 절반을 쉽게 얻을 수 있다. 1/4+3/4, 1/3+2/3, 1/2+1/2 형식으로 아들을 만들 수 있다. 이러한 교차 작업이 큰 문제가 되질 않는다.  오히려 다양한 교차가 허용되는 것이 더 유리할 수 있다.한 가지만 가능한 것이 아니다. 무작위 수를 생성시키는 방법으로 적절한 확률을 부여하여 모두 다 사용 할 수 있다.  물론, 개체 변이 또한, 돌연 변이 형식으로 인정해서 유전이 될 수 있다. 다양성을 확보하기 위해서는 선호하는 목적함수 비율로 선택하는 것이 꼭 좋은 것만은 아니다. 



변이

돌연변이는 유전된다. 자손을 만들어 낼 때 사용한다. Monte Carlo 시뮬레이션에서 새로운 시도해의 변형 형태로 시도해를 바꾼다. 그 시도해를 만들어 내는 방식은 매우 일반적일 수 있다. 문제는 그 유용성에 있다. x ---> x'이라는 변형이 아주 자유롭다. 모든 것은 min[1, exp(-(E'-E)/(kBT))]로 판단되기 때문이다. 어떠한 변형을 취해도 이론적으로 문제가 없다. 다만, 현실적으로 그렇게 효율적인 변형을 잘 만들어 내지 못하고 있다. 또한, 풀고 있는  문제에 따라서 그 변형이 많이 달라질 수도 있다. 아무튼 이 부분이 실질적인 문제 풀이에서 아주 어려운 부분이다. 유전 알고리듬에서도 마찬가지이다. 새로운 시도해를 만들 수 있어야 한다. 가능하면 다양한 방법으로 만들수록 좋다. 유전 알고리듬에서 얻어진 새로운 해를 대치하는 방법과 다양성을 확보하는 방법 사이의 균형을 잡아줘야 한다. 나름 좋은 해를 찾았으면 이를 이용할 수 있어야 한다. 동시에 이들이 너무 득세하지 못하도록 다양한 시도해가 만들어질 수 있는 환경을 만들어 주어야 한다. 이 둘 사이의 균형을 잡아 주어야 한다. 예를 들어, 아주 공격적인 교차/변이를 사용할 경우, 많은 넓은 해의 공간을 탐색할 수 있다. 이 경우, 또한 좋은 목적 함수를 가지는 해들에 대해서 충분히 높은 부모가 될 수 있는 기회도 동시에 공급해야 한다. 변이는 다양성 확보를 의미한다. 반면, 교차는 현재까지 얻어진 우수한 개체를 적극적으로 사용하려고 하는 방법을 의미한다. 두 가지 방법들 사이의 균형이 필요하다. 새로운 탐험과 기존 데이터의 이용 두 가지 사이의 균형이 필요하다.



대치

자손이 부모 세대 중 하나의 개체를 대신하는 경우를 지칭한다. 충분한 경쟁력이 있을 떄 자손이 부모 세대 중 하나의 개체를 대치한다. 기존세대 중에서 목적함수가 뛰어난 개체들을 다음 세대에서도 그대로 생존한다. 이것을 엘리트주의(Elitism)라고 한다. 시도해 하나를 기존의 부모세대 중의 모든 개체와 직접 비교 경쟁하는 방식이다. overlapping-generation 모델 또는 non-overlapping generation 모델 둘 중 하나를 선택한다. 전자는 자손과 부모가 경쟁하는 모델이고 후자는 부모와 자손이 경쟁하지 않는 모델이다. 이 부분은 위에서 말한 대치의 방법 중 하나로 생각할 수 있다. 부모로서 개체가 선택되는 방법으로는 균등 확률 또는 목적함수에 의존하는 확률 두 가지를 간단하게 생각해 볼 수 있다. 후자는 목적함수 값이 최적화될수록 더 높은 확률로 부모가 될 수 있음을 의미한다. 선택하는 방법으로 어떠한 알고리듬을 사용하는가는 중요한 항목이다. 하지만, 일반으로, overlapping model을 활용하고 인구수를 늘이면 다양성을 확보할 수 있다. 우수한 목적함수 값을 가지는 부모 세대의 시도해들은 여전히 전체 개체 집단에 여전히 머물러 있을 수 있다. 



시도해의 일차원 표현 방식

어떻게 시도해를 표현하는가는 어떻게 교차, 변이를 시키는지와 밀접하게 연관되어 있다. 염색체는 유전자들의 일차원 나열이다. 후보해도 연속한 숫자들의 일차원 나열로 표현이 가능하다. 제일 중요한 점은 시도해로서 만족해야 하는 조건을 만들어 두고 교차, 변이를 수행한 다음 해당 조건들을 만족하는지 체크해야한다. 조건을 만족하지 못하면 새로운 교차, 변이로 시도해를 만들어 낸다. 전통적인 유전 알고리듬에서는 비트 문자열을 활용하여 시도해를 표현한다. 연속 변수를 활용하는 것이 더 유리하다. 국소 최적화를 포함하는 유전 알고리듬을 설계하려면 연속 변수 형식의 시도해를 사용해야만 한다. 시도해:010011010101 또 다른 하나의 시도해:011010010111 가 알려 졌을 때, 교차는 아래와 같이 해서 또 다른 해를 만들어 낼 수 있다. 010011010101 011010010111 다시 말해서, 검은 색 부분만을 취해 낼 수 있다. (교차의 위치는 바뀔 수 있다.) 010011010111 변이는 보다 자명하다. 특정 위치의 1을 0으로 (또는 1을 0)으로 바꿀 수 있다. 점변이(point mutation)이라고 할 수 있겠다. 점변이만을 고집할 필요가 당연히 없다.



국소 최적화

전통적인 유전 알고리듬에서는 국소 최적화 방법을 사용하지 않는 것이다. 사용하는 것이 더 효율적이다. 연속 변수를 사용하고 국소 최적화 방법을 활용하는 것이 더 일반적인 유전 알고리듬이다. 구배벡터가 알려진 경우, BFGS 방법을 활용한다. 그렇지 않은 경우, Nelder-Mead 방법을 활용한다. 목적함수를 최소화할 때, 가능하면, 구배벡터(gradient vector)를 얻을 수 있다면, 국소 최적화 알고리듬을 유전 알고리듬과 동시에 사용하는 것이 좋다. 연속 변수로 시도해를 표현한다. 많은 경우, 국소 최적화를 한다. (가능하면 그렇게 한다. 보다 효율적이기 때문이다.)   



유전 알고리듬의 병렬화

국소 최적화 과정이 가장 계산 시간이 올래 걸린다. 따라서, 국소 최적화 단위별로 병렬화를 시키면 최고의 병렬 효율성을 얻을 수 있다. 국소 최적화는 여러 해들에 대해서 동일한 CPU 시간을 보장하지 않는다. 국소 최적화에 도달하는 CPU 시간은 시도 해들에 따라서 다르다. 이 부분을 잘 고려해서 프로그램을 완성해야만 한다. 계산 빨리 끝나는 경우가 있고 그러할 경우 다른 계산이 연이어서 진행될 수 있도록 프로그램을 만들어야 한다. 병렬 효율성의 극대화를 위한 필수조치가 필요하다. 



주의 할 점들

유전 알고리듬 프로그램 종료 시점을 쉽게 정의할 수가 없다. 결정론적 정답을 주는 것은 아니다. 소위 발견법 분류에 속한다. 유전 알고리듬의 구현은 단순하다. 하지만, 그 실행 효율성을 검정하는 것은 매우 까다로운 과정을 거쳐야만 한다. 무작위 수 생성 함수를 적절히 잘 이용하면 쉽게 구현할 수 있다. 물론 함정이 있다. 정확하게 풀리는 문제 풀이 방식이 아니기 때문에, 프로그램을 정확하게 만들었는지 테스트하기가 다소 까다롭다. 당연히 병렬화 해야만 그 성능을 재대로 맛 볼 수 있다. 또한 당연하게 병렬 컴퓨터 자원을 확실하게 확보해야만 한다. 후보해들을 공간적으로 분리시켜서 경쟁시키는 니칭(Niching) 방법을 강구해야한다. 즉, 서로 다른 모양의 후보해들을 찾을 수 있는 방법이 필요하다. 거의 같은 목적함수 값을 주지만 실제로 매우 다양한 후보해들이 가능하다. 

 

 하나의 구간 근처에서만 해를 찾는 것이 아니라, 다른 구간 근처에서도 또 다른 해를 찾을 수 있어야 한다. 해들이 다양성을 확보하는 것과 틈새시장을 공략하는 전략 니칭은 거의 동일한 개념으로 볼 수도 있다.

  

https://stackoverflow.com/questions/13775810/what-is-niching-scheme

 

 

 

 

 



위에 표시된 그림에서는 전통적인 유전 알고리듬을 표시하고 있지는 않다. 국소 최소화 과정이 추가적으로 포함되어 있기 때문이다. 다시 말해서 후보해들이 연속적인 변수들로 구성되어 있다. mating은 교차를 의미한다. 전통적인 유전 알고리듬에서는 후보해를 표현하는 방법이 1차원 비트 문자열 방식이다. 교차와 변이방법들은 각각이 여러 가지 형식들이 있을 수 있다. 실제 사용에서는 활률적인 방법으로 여러 가지 방식의 교차와 변이를 골고루 사용할 수 있다. 위의 그림에서 표시된 부모선택(pair selection)이라는 부분도 여러 가지 방식이 가능하다. 통상 하나의 방식을 활용한다. 예를 들어, 단순하게 서로 다른 두 개를 균등한 확률로 취하는 방법이 가능하다. 목적 함수 값을 전혀 고려하지 않고 선택하는 방법이다. 목적함수 값이 더 최적화될수록 더 높은 확률로 부모가 될 수 있게 한다. 서로 다른 두 개를 임의로 선택한다. 그 다음 더 최적화된 목적함수 값을 가지는 개체를 선택한다. 마찬가지로 두 번째 부모도 동일한 방식으로 선택한다. 다만, 부모들은 서로 다른 개체가 되어야만 한다. 이렇게 하면, 한판의 경쟁에서 승리한 쪽만이 부모가 될 수 있다. 목적함수 값이 가장 큰(덜 최적화된) 개체는 결코 부모가 될 수 없다. tournament selection이라고 한다. 판이 아니고 여러 판에서의 승자를 고를 수도 있다. 경쟁 라운드 수를 더 많이 할 수 있다. 소위 selection pressure가 높을수록 round 수가 많은 tournament selection에 해당한다.

 

 

 

 


OnePointCrossover.svg



그림 출처:

 
1010010
101011

0

그림 출처:

그림 출처:

유전 알고리듬의 특징:
우월한 개체들로 부터 교차(교배) 그리고 돌연변이 (반드시 두 가지 모두 사용함.) 유도를 통해서 새로운 개체를 만들어내는 것이 핵심이다. 사실, simulated annealing 에서 처럼  x ---> x변환에서 매우 효율적인 것이 가능하면 우수한 알고리듬이 될 수 있다. 하지만, 이 변환에서 한계점을 많이 노출한다. 결국, 변환은 {x}  ---> {x'}, 집합 ---> 집합의 변환 방식으로 바뀌게 된다. 집합에서 보다 좋은 집합으로 변환할 수 있는 방법을 제공한다.  보다 일반적이고 효율적인 변환을 제공하는 것이 유전 알고리듬의 특징이다.  유전 알고리듬은 매우 일반적인 알고리듬으로 풀고자 하는 문제에 쉽게 적용할 수 있다. 많은 공학적 문제 풀이에 적용될 수 있다. 교배, 교차 등을 정의할 수 있다면 유전 알고리듬을 활용한 문제풀이는 가능하다. 국소 최적화가 효율적으로 수행될 수 있는 경우, 유전 알고리듬을 그대로 적용할 수 있다.
 
------------------------------------------------------------------------------------------------------
Particle Swarm Optimization: http://incredible.egloos.com/4731015
Differential Evolution: http://incredible.egloos.com/5265158
Replica-Exchange Molecular Dynamics: http://incredible.egloos.com/4587643
Simulated Annealing: http://incredible.egloos.com/4784592
Nelder-Mead method: http://incredible.egloos.com/4838059
Conformational Space Annealing (CSA) : http://incredible.egloos.com/6208916
------------------------------------------------------------------------------------------------------

cf.

ranmar()가 랜덤 넘버 생성기라고 하면,  [0.0,1.0) 사이의 값을 무작위로 반환하게 된다. 따라서, 실행하는 위치에 따라서 값들이 달라진다.

ranmar() 는 real 형이다. real*8 형이 아니다.


아래와 같이 실행하면,
       i=dble(n)*ranmar()
i가 가질 수 있는 숫자는 아래와 같다.
       0,1,2,...n-1

다시 말해서, 아래와 같이 수행하면
        i=dble(n)*ranmar()+1
i가 가질 수 있는 숫자는 아래와 같다.
        1,2,3,....,n

이렇게 하면, 특정 시도해를 임의로 추출할 수 있다.  (동일한 확률을 가정하고 무작위로 선택하는 방식이다.) 또한, 유한한 여러가지 방법들 중에서 하나의 방법을 선택할 수 있다. 실행 시간 기준으로 랜덤넘버 자동 씨드 만들기, 포트란 90 실제 포트란 90에서는 아래의 예제와 같이 랜덤넘버 생성기의 씨드를 임의로 조절할 수 있다.

생성기 호출: call random_number(tmp)
생성기 씨드 지정 호출: call init_seed()
가장 간단한 경우: call random_seed()을 이용한 초기화이다. call random_number(tmp) 처럼 무작위 수를 불러서 사용할 수 있다.
i=n*tmp 또는

i=n*tmp+1 처럼 활용할 수 있다.


!234567890
      program test
      implicit none
      real*8 tmp
      integer i

      call init_seed()

      do i=1,10
      call random_number(tmp)
      write(6,*) tmp
      enddo

      end program test

      subroutine init_seed()
      implicit none
      integer n, ival(8), v(3), i
      integer, allocatable :: seed(:)
      call date_and_time(values=ival)
      v(1) = ival(8) + 2048*ival(7)
      v(2) = ival(6) + 64*ival(5) ! value(4) isn't really 'random'
      v(3) = ival(3) + 32*ival(2) + 32*8*ival(1)
      call random_seed(size=n)
      allocate(seed(n))
      call random_seed()          ! Give the seed an implementation-dependent kick
      call random_seed(get=seed)
      do i=1, n
      seed(i) = seed(i) + v(mod(i-1, 3) + 1)
      enddo
      call random_seed(put=seed)
      deallocate(seed)
      end subroutine

------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------


유전 알고리듬의 근본적 속성:


[*] 새로운 해를 생성해내는 계산 방법이다. 교차와 변이가 핵심이다. 결국, 새로운 해를 제공하는 알고리듬이다. 계속해서 새로운 해를 제공한다.


유전 알고리듬, 근본적 약점과 보완:

[*] 광역 최적화에 도달했다는 정확한 정보를 주지 못한다.  단순 비교에 의해서만, 추가적인 비교에 의해서만 판단할 수 있다.

[*] 문제의 복잡도에 대한 특별한 대책이 없다. 주어진 문제에 대한 정보가 많을수록 문제풀이가 보다 용이해질 가능성은 얼마든지 존재한다. 문제를 풀고 있는 도메인(특정 연구 분야)에 대한 이해가 필수적이다. 매우 많은 목적함수(objective function) 평가가 반드시 수반되어야만 한다. 다행히 유전 알고리듬은 병렬화가 쉽게 된다. 목적함수 계산에 시간이 오래 걸린다고 하더라도 병렬화를 통하여 어느 정도 극복할 수 있다. 최근에는 매우 오래 걸리는 계산들에 대한 응용 연구가 활발히 진행되고 있다.

[*] 다양성을 확보할 수 있는 일반적인 방법은 없다. 임의의 구조를 무작위로 새로 도입하는 방법이 하나의 다양성 증가를 위해서 취할 수 있는 방법이기는 하다. random immigrants 도입 또는 mutation 확률 증가와 같은 부가적인 절차가 필요 할 경우도 있다. 이는 다양성 확보 차원에서 필요한 작업이다. 문제는 그 유용성이 낮을 수 있다는 한계가 있다. 다양성이 확보가 되지 않을 경우가 발생할 수 있다. 이렇게 되면 얻어지는 해의 질이 나빠질 수 있다. 광역 최적화에 쉽게 실패할 수 있다. 최적화되지 못한 개체도 부모가 될 수 있게 한다. 공간적으로 분리하여 개체들을 경쟁시킨다. 

[*] 일반적인 crossover, mutation 방법이 알려져 있지 않다. 문제마다 새롭게 정의해야만 한다. 앞서 이야기한 특정 연구 분야에 대한 지식이 필수적이다. 일반적으로 다양한 crossover, mutation 이 각각 가능하다. 많은 가능성을 염두에 두고 이들 연산 방법들을 고안해야만 한다. 자신이 풀고 있는 문제에 대한 확실한 이해가 필요하다. 즉, 도메인에 대한 이해가 필요하다. 학습법(heuristic)을 통해서 특정한 조건들을 만족하는 경우에 대해서만 최적화된 해를 찾을 수 있다. 이 역시 도메인 지식이 절대적으로 필요하다. 다시 말해서, 도메인 지식이 구현된 유전 알고리듬의 성능에 영향을 줄 수 있다. 해당 문제를 더 잘 이해할수록 더 좋은 유전 알고리듬 구현이 가능하다.  

[*] 후보해들 사이의 다양성을 의도적으로 지속적으로 유지할 수 있는 장치가 없다. 모든 개체가 부모가 될 수 있게한다. 니칭 방법을 활용한다. 임의의 후보해를 도입한다. 특정한 부모들을 모두 자손들로 대체한다. 

[*] 목적함수의 일차 미분이 쉽게 얻어질 때(해석적으로 얻을 수 있을 때)는 국소 최적화를 LBFGS 같은 방법으로 수행하는 것이 더욱 효율적이다. 일차 미분이 없은 경우에도 국소 최적화를 수행하는 것이 유리하다. Nelder-Mead 알고리듬을 이용할 수 있다. 목적 함수 값이 낮아지면 무조건 이동하는 방식을 적용하여 완전하지는 않지만 부분적으로 국소 최적화를 수행할 수 있다. 이러한 국소 최적화를 위해서는 bit string 과 같은 해의 표현 방식은 일반 실수 벡터 방식으로 바꾸어 사용하는 것을 의미한다. Monte Carlo quenching 에서는 T --> 0 극한을 취한 경우이다. 즉, 목적함수 값이 최적화되면 무조건 업데이트한다. 즉, 해를 받아들이는 작업을 수행한다. 일종의 국소 최적화 방법으로 볼 수 있다.효율성은 낮다.



------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------
위에서 나열된 유전 알고리듬의 약점들이 일부 보완된 알고리듬이 CSA 알고리듬이다. 해들의 다양성을 확보한 상태로 유전 알고리듬을 적용한 것이다. 아울러 simulated annealing 개념까지 추가시킨 알고리듬이다.
Conformational Space Annealing (CSA) : http://incredible.egloos.com/6208916

물리학과 첨단기술 2018 :
http://webzine.kps.or.kr/contents/data/webzine/webzine/15211841581.pdf


핑백

덧글

  • 바죠 2017/09/09 19:41 # 삭제

    그네 타기:
    https://www.youtube.com/watch?v=Yr_nRnqeDp0

    이족 보행:
    https://www.youtube.com/watch?v=c-qePE1GCQY

    swing robot:
    https://www.youtube.com/watch?v=fXgcp6ZRCrE
  • 2018/02/02 10:25 # 비공개

    비공개 덧글입니다.
  • 2018/02/06 14:02 # 비공개

    비공개 덧글입니다.
※ 로그인 사용자만 덧글을 남길 수 있습니다.

최근 포토로그