Conformational Space Annealing (CSA) [algorithm] by 바죠

Conformational Space Annealing (CSA)

Conformational Space Annealing (CSA) [algorithm]
형태 공간 풀림

CSA 알고리듬은 하나의 광역 최적화 (global optimization) 방법이다. 유전 알고리듬(genetic algorithm; GA), 목적함수 국소 최소화,  그리고 "온도를 천천히 낮추어가면서 고체 결정화를 이루는 과정을 모사한" 풀림 시늉(simulated annealing; SA) 방법을  적절히 결합한 광역 최적화 방법이다. 실질적으로는 목적 함수(objective function)를 최소화 하는 방법이다.  (최소화와 최대화는 +f(x)  ---> -f(x) 에서 처럼 함수의 부호차이에 지나지 않는다.)

유전 알고리듬에서처럼 서로 다른 여러개의 해(solution, x로 표현)를 적극적으로 찾는 방법이다. 풀림 시늉(simulated annealing; SA)에서처럼 하나의 해만을 취급하는 방법이 아니다. 여러 해들을 동시에 취급하면서 목적 함수 최적화 계산을 진행하게 된다.
서로 다른 해들( {x} ) 사이의 '거리'를 정의해 이를 적극적으로 활용한다.  이것은 얻어진 해들의 다양성 확보를 위한 장치로 볼 수 있다. 확률론적 문제 풀이 방식이다. 유전 알고리듬에 기반을 두고 있고  유전 알고리듬과 마찬가지로 항상 정답을 보장할 수 없는 알고리듬이다.  대신에 일반적인 문제 풀이 방식이 될 수 있고 병렬 효율성이 뛰어나서 매우 복잡한  문제 풀이에 적합한 알고리듬이다.  확률론적 접근법으로 독립변수들이 매우 많은 경우, 즉, 충분히 어려운 광역 최적화 문제 풀이에 일반적으로 적용 가능하다. 특히, 목적 함수 국소 에너지 최소화를 포함하여 매우 많은 목적 함수 계산을 수반하게 된다. 프로그램 병렬화를 통하여 계산의 속도를 가속화할 수 있다. 물론 더 많은 CPU 를 사용한다. 병렬 효율성이 아주 좋고, 프로그램 병렬화가 아주 간단한 알고리듬이다.  결론적으로 매우 어려운 광역 최적화 문제 풀이에 일반적으로 적용 가능하고, 매우 다양한 해들을 동시에 찾아주는 계산 방법이다.

유전 알고리듬(genetic algorithm)에서 처럼, 여러 개의 잠정적으로 얻어진 해들을 동시에 취급한다.  (population size 고정, particle swarm optimization(PSO) 방법에서도 마찬가지이다.) 국소 최적화 알고리듬을 가능하면 활용한다. (특히, 해석적인 미분을 바탕으로 하지않는 경우에도 이를 수행한다. 예를 들어 Monte Carlo 방식으로 국소 최적화를 수행한다. simulated annealing에서 온도가 0에 해당하는 경우,  에너지가 낮아질 경우에만 x ---> x' 변환이 받아 들여지게 된다. 그렇지 않은 경우 x'은 거부된다. 이러한 계산은 부분적인 국소 최적화를 수행하는 방법이 될 수 있다.  해석적인 미분이 얻어진 경우에는 LBFGS 방법으로 국소 최소화를 달성한다.) http://incredible.egloos.com/3042973
 
여러 개의 해들을  동시에 고려하고 있다. 얻어진 해들에게 목적 함수 값 기준으로 랭킹을 매긴다.  이들 사이의 랭킹은 무조건 존재한다. 목적 함수 값 오름 차순으로 정렬한다. (sorting 알고리듬을 활용한다.)  목적 함수가 낮을수록 랭킹은 높다. 이것은 현재 우리가  목적 함수 최소화를 고려하기 때문이다.  잠정적으로 얻어진 임의의 서로 다른 두 해들을 이용하여 crossover(교배, 교차) 과정을 통해서 새로운 시도 해(trial solution)들을 만들어 낸다.  여러 가지 다양한 방법으로 crossover를 만들 수 있다.  실제 계산에서는 확률적으로 선택해서 다양한 crossover 중 하나를 수행한다.  계산이 계속해서 진행되면 결국 준비한 모든 종류의 crossover 방법들이 모두 사용될 것이다. crossover 방법이외에 임의로 선택된 하나의 해를 이용하여 mutation(변이, 돌연변이) 시키는 방법을 정의한다. 새로운 시도 해를 찾을 수 있는 기반을 마련한다.  일반적으로 다양한 mutation 과정으로 부터 시도 해를 만들어 낼 수 있어야 한다. 다양한 방법들 중 하나를 확률론적으로 선택하여 사용한다.  mutation(변이), crossover(교차) 각각 여러 가지 방법들이 가능하다. 여러 가지 방법들을 확률적으로 선택해서 골고루 사용한다.  crossover, mutation 둘 중의 선택도 골고루 이루어질 수 있도록 한다. 물론, 통상 crossover를 보다 더 많이 선택한다.  이 또한 확률론적으로 결정할 수 있다. 얻어질 다양성 확보를 위해서는 mutation 사용이 절대적이다. crossover 방법을 활용하는 것에는 이미 얻어진 좋은 해들을 적극적으로 활용하고자 하는 의미를 담고 있다. crossover, mutation 두 가지 방법에는 서로 다른 의미가 있다.
x ----> x'
새로운 시도해의 도입: mutation, crossover를 통하여 이루어진다.  이전에 만들어 놓은 시도해가 전혀 없는 경우에는, 예를 들어 계산을 처음 시작할 때와 같이, 순수하게 무작위 방법으로 만들어 낸다.  여러 해들을 동시에 고려하면 아래와 같이 적어야 할 지도 모른다.  특정 무리의 집합에서 새로운 집합으로 시도 해들을 만드는 것이 보다 일반적인 경우에 해당한다.  
{x} ----> {x'}
사실 유전 알고리듬에서는 우수한 해들의 조합으로 부터 우수한 해들이 재생산 할 수 있는 부모가 된다.   이 사실을 염두에 두고 있어야 한다. 그리하여 우수한 집단의 해들을 동시에 취급하는 것이다.  풀림 시늉(simulated annealing; SA) 방법에서는 하나의 해만 취급하기 때문에 x ----> x'형식의 변환만 존재할 수밖에 없다. 하지만, 여러 해들을 동시에 고려할 경우, 일반으로 {x} ----> {x'} 같은 형식의 보다 일반적인 시도 해 생성이 가능해진다.  이 부분에서 유전 알고리듬 또는 particle swarm optimization 방법이 simulated annealing (SA) 방법보다 유리한 점이다.  보다 더 일반적이고 효율적인 시도해를 x'을 만들어 낼 수 있다.  특별히, 유전 알고리듬에서는 1차원 형식인 bit string 표현 방식을 사용한다.  아울러 differential evolution 알고리듬에서는 실수형 표현을 사용한다. 역사적으로 그렇게 발전해 왔다. 실수형 또는 bit string 형으로 해를 표현하는 방법이 이루어져 왔다.  하지만, 실질적으로는 문제의 특성에 따라서 보다 물리적인 분류가 가능할 수 있다.  문제의 특성에 맞추어서 해를 표현하는 방법을 개발할 필요가 있다.  해를 표현하는 방법은 crossover, mutation 방법과도 밀접한 연관성이 있는 것이다. 신중하게 표현해야 한다.  입자 군집 최적화(Particle swarm optimization, PSO) 방법에서는 crossover, mutation이란 개념을 활용하지 않는다.  순수하게 집단 속에 속한 개체들 사이의 정보 공유 특성을 고려하는 방식이다.

임의의 서로 다른 두 해들 (x1, x2) 사이에 '거리'를 정의한다. d(x1, x2) 처럼 '거리'를 정의할 수 있다.  '거리' 값이  충분히 큰 경우, 서로 다른 형식의 것들이라고 볼 수 있다.  '거리' 값이 충분히 작으면 두 해가 동일한 타입으로 취급한다.  해들 사이의 '거리'는 해들이 얼마나 서로 다른 특징을 가지고 있는지로 정의한다.  '거리'를 정의하는 여러 가지 방법이 가능하지만 한 가지로 선택하여 사용한다. 서로 다른 양식, 특징을 가진 잠정적인 해들을 무시하지 않고 가급적 동시에 취급하기 위한 장치이다.  다양한 해들을 골고루 찾아 내기 위한 인위적인 판단 기준으로 활용된다. 

목적 함수값이 다소 높더라도, 다시 말해서, 랭킹이 다소 좋지 못하더라도, 해당 해가 기존에 찾아진 랭킹이 낮은 해들과는 다른 형식,  양식, 특징이 있다면 가능성이 있는 해로 취급하기 위함이다.  '거리'가 클수록 서로 다르다고 정의한 것이다.  '거리'값이 클수록 서로 다른 형식이라고 인정하는 것이다.  해들의 다양성을 최대한 확보하려고 하는 노력의 일환이다.  해들 사이의 다양성을 적극적으로 유지한다. (유전 알고리듬에서도 마찬가지이다.) 목적 함수 값이 다소 높더라도 아주 멀리 떨어진 거리를 가지고 있는 해들은 신중하게 고려해 줄 필요가 있다.

매우 다양한 시도해를 만들어 내고 동시에 얻어진 해들 사이의 특징적인 '거리'를 정의해서 사용한다. 얻어진 해들 사이의 근접도를 평가하고 근접하지 않은 해를 새로운 형식의 해로 인정한다.  랭킹상으로는 불리해도 새로운 형식의 해는 랭킹을 무시하고 받아 들인다.  물론, 같은 형식, 양식이면 대표로 하나의 해만 저장한다.  더 낮은 목적 함수 값을 가지는 것만 취급한다.  현 상황에서 가장 랭킹이 좋지 못한 해를 포기하고  새로운 형식의 해를 받아들일것인지 아닌지는 해당 해들의 목적 함수 값들을 조사하여 결정할 수 있다. 핵심은 population size 가 고정되어 있다는 점이다. 새로운 하나를 받아 들이려고 하면 기존의 또 다른 하나를 반드시 포기해야만 한다.
 
결국 서로 다른 형식의 해를 존중해서 전체 풀(population)에 소속시킨다. 전체 풀의 크기는 정해져 있다.  비슷한 형식의 해, 서로 다른 형식의 해를 구분할 수 있게 한다.  전반적으로 다양성(diversity)이 높은 상태를 유지하면서 여러개의 해들을 동시에 취급한다. 일반으로 임의의 구조를 무작위로 도입하는 것은 다양성 제고에 도움이 된다.  하지만, 너무나 일반적인 방법으로 그 효율성은 매우 낮을 수 있다. 

'차단 거리' 파라메터를 정의해서 사용한다.  '차단 거리' (Dcut) 보다 작은 경우, 즉, 서로 다른 두 해의 거리가 '차단 거리' 보다 작은 경우, 우리는 이들 해를 동일한 형식의 해라고 판단한다.  이러할 경우, 유사한 형식을 대표하는 하나의 해만을 선택해서 취급한다. 목적 함수가 낮은 해를 취급하게 된다.  새로운 형식의 해인지 그렇지 않은지에 대한 판단의 근거는 현재 사용하고 있는 '차단거리' 파라메터를 참조하여  최종 평가하게된다. 최적화 과정을 통해서, 전반적으로, '차단거리' 파라메터는 줄여나가는 방법을 취한다. 마치, simulated annealng(SA) 방법에서 온도 파라메터를 점차적으로 줄여나가듯이 '차단거리' 파라메터를 줄여나간다.

특정 갯수의 시도해를 만들어 낸다. 무작위로 만들어 낸다.  국소 최적화 과정을 통해서 시도해를 수정한다. 잠정적으로 얻어진 해들에 대해서 랭킹을 매긴다. 초기 '차단 거리' 설정: 임의로 만들어진 서로 다른 해들 사이의 거리를 다 계산하고,  그 평균값의 절반을 초기 '차단 거리' (Dcut)라고 정의한다.

처음으로 만들어진 시도해들로 부터 mutation 그리고 crossover를 실행한다. 새로운 시도해를 계속해서 동시에 찾아 나간다. 병렬화하여 찾는것이 가능하다.  국소 최적화 알고리듬을 적극 활용한다. (해석적으로 지원이 되지 않는 경우는 수치적으로  국소 최적화 과정을 수행을 한다.) 국소 최적화된 시도해를 가지고 아래의 계산을 수행한다. 일반적으로 국소 최소화 과정에서 많은 계산 시간을 필요로한다.   새로 얻어진 구조를 이용하여 풀내에 있는 모든 구조들과의 '거리'를 측정한다. 가장 가까운 구조 하나를 정한다. 현재의 차단 거리와 비교한다. '차단 거리' 보다 클 경우, 서로 다른 구조로 인식한다. 작을 경우, 같은 형식의 구조로 인식한다. 두 개중 하나의 구조만 목적함수 기준으로 선택한다.  낮은 목적 함수를 가지는 구조만 선택하고 나머지는 버린다. 더이상 취급하지 않는다.  해당 사항이 없으면 얻어진 시도해는 더이상 취급하지 않는다. 파기한다.  서로 다른 구조로 인식한 경우, 여러 개의 해들로 구성 된 풀에 소속 시킨다.  (이때 조건이 있다. 풀 내부에서 가장 높은 목적 함수 값과 새로 찾은 해의 목적 함수를 비교한다.  만약 새로 찾은 해의 목적 함수 값이 더 작으면 새롭게 찾은 서로 다른 형식의 해를 받아 들인다.  가장 높은 목적 함수 값을 가지는 해를 버린다. 새로운 해의 목적 함수 값이 풀 내부의 가장 목적함수 값 보다 큰 경우에는 새로운 찾은 해를 버린다.)  설사 랭킹이 높지 않더라도 새로운 해를 우대해서 풀에 소속시킨다.  하지만 새로운 형식의 해라고 하더라도 충분히 낮은 목적 함수를 가지지 않으면 풀에 들어 올 수 없다.  군집, 무리, 또는 풀을 업데이트하고 나면 모든 해들에 대해서 또 다시 랭킹을 매긴다.  목적 함수 값을 기준으로 해들을 오름차순으로 또다시 정렬해 둔다.

유전 알고리듬에 의하면, 랭킹이 높은 해들일수록 더 많은 crossover, mutation의 기회를 부여받게 되어 있다.  conformational space annealing 에서도 이점을 적극 활용한다.  소위 selecton pressure라는 개념이다. 다시 말해서, selection pressure가 높다고 표현하면,  랭킹 지상주의로 가겠다는 것이다. 철저하게 랭킹이 높은 것들 위주로 crossover, mutation의 기회를 준다는 의미이다.  너무 높은 selection pressure는 일반적으로 바람직하지 않다.  이렇게 할 경우, 광역 최적화 작업 초반부터 너무 한 쪽으로 편중된 해들만 취급하게 된다.  다시 말해서 다양성을 초반에 잃어 버릴 수 있다.  유전 알고리듬에서 논하는 소위 Elitism을 이용한다.  부모 세대와 자식 세대를 구별하지 않고 목적 함수가 낮은 해는 무조건적으로 풀에 넣어서 계산을 수행한다.

유전 알고리듬에서는 세대(generation)라는 개념이 존재한다. 세대를 무시하고 광역 최적화를 진행할 수 있다.  이를 elitism 이라고 한다.  elitist을 계속해서 유지해야만 해들이 표류하지 않는다. 세대를 넘어서 목적 함수 값이 낮은 해들은 계속해서 풀에 남아 있게 된다.  광역 최적화가 퇴보하지 않는다.  conformational space annealing(CSA) 방법에서는 elitism 채택한다.

mutation, crossover 시키는 방법은 문제 풀이마다 고유의 방식으로 새로 정의해야만 한다. 각각 다양한 방법들이 존재할 수 있다.
가능한 한 많은 방법들을 만들어서 적용 할 수록 좋다.  일반적으로 취급할 수 있는 방법이 있을 수 있다.  하지만, 임의의 방법으로 만들다 보면, 풀고있는 문제의 해가 애초에 되지 못하는 경우도 있기 마련이다.  예를 들어, genetic algorithm, differential evolution 알고리듬에서 처럼,  매우 일반적인 방법으로 mutation, crossover를 각각 정의할 수 있다.  그렇지만, 그 효율성을 장담할 수는 없다. 문제마다 고유의 특성을 살려야만 한다. 이것 또한 효율성을 위한 것이다.  또 하나의 문제점은, mutation, crossover를 통해서 만들어낸 잠정적인 해가  우리가 풀고있는 문제의 해로서 전혀 적합한 해가 아닐 수도 있다는 점이다.  이 문제를  반드시 해결해야만 한다. 시도 해가 최소한으로 만족해야 하는 조건들을 반드시 체크해야만 한다. 최소한의 조건을 만족하면 국소 최적화 과정을 수행한다. 그 다음 목적 함수 값을 계산한다.  목적 함수값이 계산되는 즉시 다음 시도해를 만들고 다시 국소 최적화 작업을 수행하는 방식을 채택한다.  왜냐하면 일반으로 국소 최적화 과정이 계산을 많이 필요로 하는 과정이기 때문이다. 병렬적으로 수행해야한다.

통상의 경우 CSA 알고리듬은 MPI를 활용하여 병렬화가 가능하다. 일반적인 경우에 해당한다. 최고의 효율성을 얻을 수 있다.  하지만, 목적 함수 계산 자체가 굉장한 시간이 걸리고 메모리를 많이 필요로 하는 경우도 있을 수 있다. 심지어 병렬 계산을 해야만 하는 경우도 있을 수 있다.  상황이 이 정도 되면 MPI를 이용하는 것 보다 차라리 디렉토리를 여러 개 만들고 각각의 디렉토리에서  독립적인 병렬 계산을 수행하는 것이 더 유리할 수 있다.  이러할 경우 CSA 메인 프로그램은 serial 프로그램이 되고 각각의 디렉토리에서 제3의 프로그램이 수행한 계산 결과를 읽어 들이는 방식으로 목적함수를 계산할 수 있다.  이렇게 할 경우, PBS 같은 방식으로 단위 계산들이 제출되게 된다. 프로그램 시작할 때 계산 가능한 디렉토리 숫자를 지정할 수 있다.  (사용 가능한 디렉토리 갯수는 상황에 따라서 달라질 수 있다. 타 사용자들도 계산을 할 수 있게 해 주어야 한다.)  계산이 진행중인 디렉토리 그리고 계산이 끝이 난 디렉토리를  serial 메인 프로그램이 항시 구분할 수 있어야 한다. 계산이 끝난 디렉토리에서는 필요한 계산 결과를 serial 메인 프로그램이 직접 수집하고  해당 디렉토리에서 새로운 계산이 즉시 수행할 수 있도록 만들 수 있다.  (PBS 명령어를 이용해서 계산을  제출, serial 메인 프로그램에서 시스템의 이완을 고려해서 아주 작은 대기 시간을 준다.  sleep 시간을 확보한다.)  연속해서 계산할 수 있게 하고 필요한 데이터는 백업을 한다. 특별한 응용 프로그램이 있는 경우, 그 응용 프로그램의 출력 파일들을 분석해 낼 수 있는 프로그램을 만들어서 사용하는 것이 중요하다. CSA 알고리듬과 특별한 응용 프로그램 사이의 완전한 분리가 이루어지게해야한다. 물론, 특정 응용 프로그램 입출력 파일을 CSA 알고리듬에 해당하는 프로그램이 관리할 수 있게 한다. PBS 를 통한 계산 실행도  CSA 알고리듬에 해당하는 프로그램이 직접 실행한다. 아울러, 각 계산 디렉토리에서 단위 계산들이 종료되었는지를 CSA 알고리듬 프로그램이 직접 모니터링한다.
 
CSA 알고리듬의 특징:
1. crossover, mutation을 포함하는 유전 알고리듬에 기반한다.
2. 해들 사이의 '거리'를 정의하고 적극 활용한다.
3. 국소 최적화를 사용한다. 국소 최적화 되어진 해만 취급한다.
4. 해들 사이의 상이성을 조절해 가면서 (다양성을 보장해 가며서) 광역 최적화 과정을 진행한다.
5. 병렬 계산에 아주 유리하다. (국소 최적화 과정 그리고 목적 함수 값 계산을 많은 계산 노드에서 독립적으로 진행한다.
국소 최적화 과정이 일반적으로 많은 시간을 요구한다. 서로 다른 두 개의 국소 최적화는 일반으로 같은 CPU 시간을 요구하지 않는다. 하나의 국소 최적화가 끝나면 곧바로 다른 국소 최적화를 시도해야만 병렬 효율성을 얻을 수 있다.)
6. 지금 얻어낸 해와 가장 유사한 기존의 해를 찾아낼 수 있다. 두 해가 유사한 경우, 목적 함수값이 낮은 것이 대치된다. 하지만, 상이한 형식의 해를 얻을 경우 무리에 편입될 수있다. 즉, 차단 거리보다 더 큰 값의 거리를 가질 경우이다. 얻어낸 해와 가장 유사한 해들 사이의 거리가 차단 거리보다 클 경우이다. 무리 중에서 가장 가장 목적 함수값이 높은 해보다만 새로얻은 해의 목적 함수값이 낮으면 무리로 편입된다. 다시 말해서, 두 가지 양식의 편입이 있을 수 있다. 하나는 유사한 해들 사이에서 보다 더 낮은 목적 함수값을 가져서 편입되는 경우이다. 또 다른 하나는 유사한 해가 아니면서도 적절히 낮은 목적 함수값을 가지는 경우이다.   
 
CSA  알고리듬은 아래의 3가지 요소로 이루어져 있다.
 
(1) genetic algorithm (GA):
crossover, mutation을 통한 새로운 시도해를 만들어 낸다. {x} ---> {x'} 만들어 내는 방법으로서의 그 효율성 잘 알려져 있다.
우수 집단에서 우수 집단의 시도해를 만들어 줄것이라는 가정하에 변환을 시도한다.  http://incredible.egloos.com/4856511

(2) Monte Carlo with Minimization (MCM):
국소 최소점들만 시도해로 받아 들인다.  항상 국소 최소화를 시도한다. x ---> x' ---> x'' 항상 국소 최소화 되어진다. 결국, x ---> x'로 표현 된다고 하더라도 실제는 국소 최소화 과정을 거친 시도해들만 다루게 된다.  좌우 모두 국소 최소화 과정을 거친 해들로 볼 수 있다. 국소 최적화 단계는 Nelder-Mead 알고리듬, BFGS 알고리듬 등을 이용한다. 목적함수 미분을 해석적으로 얻을 수 있다면 BFGS알고리듬을 사용한다. Nelder-Mead 알고리듬은 목적함수 미분을 얻을 수 없을 때 사용한다.

(3) simulated annealing (SA):
국소 최소화를 사용하지 않는다. 대신에 온도를 높은 값에서 낮은 값으로 유도한다. 시도해를 만들 때 Monte Carlo 방식의 움직임을 취한다. 온도가 높을 때는 시도해를 만드는 과정이 공격적일 수 있다.  광폭 행보를 허용한다.  에너지가 다소 과하게 높아지는 과정도 온도가 높을 때에는 확률적으로 허용되기도 한다. 온도가 낮아 지면 시도해를 만드는 과정에 광폭행보는 사라진다.  또한, 에너지가 다소 높아지는 경우에도 온도가 낮을 경우에는 확률이 급격히 떨어지게 된다. x--> x' 새로운 시도해가 만들어지고 받아 들여지는 확률을 취급한다. CSA 에서는 특별히 '차단 거리'가 있고 이 값을 기준으로 대치 작업을 수행한다. 이 값보다 거리가 작은 것은 유사한 시도해로 간주한다. 이 값보다 더 큰 거리는 상이한 형태의 시도해로 간주한다. '차단 거리'는 천천히 감소한다. http://incredible.egloos.com/4784592
 
 
주어진 광역 최적화 문제를 CSA 방법으로 풀려고 할 때 반드시 준비해야 할 것들:
해(x)를 표현하는 방법 준비, 사실, 이 부분은 mutation, crossover와 밀접하게 연관되어 있다. 목적 함수, f(x) 계산 (함수값 계산에 굉장히 시간이 소요될 수  있다.) 국소 최적화 과정 준비 (계산에 굉장한 시간이 소요될 수 있다.) distance 정의 (서로 다른 해들 사이의 거리 측정) 풀의 크기 또는 population size 결정하고 계산 시작한다. selection 방법 (너무 높은 selection pressure를 적용하지 않은 방법으로 준비) mutation 방법 (여러 가지 방식으로 준비) crossover 방법 (여러 가지 방식으로 준비) mutation과 crossover 선택 비율, 예를 들어 20%, 80% 비율 미리 설정해 둔다. 반드시 둘 다 사용한다.  시도해가 현재 문제풀이 과정에서 부적절한 해인지 판단하는 방법 준비  (시도해가 반드시 만족하는 조건들, 최소한 만족해야 하는 조건들 준비) 시도해가 문제마다 다르게 정의되는 해로서의 기본적인 조건을 만족하지 못할 경우, 시도해를 다시 생성해야만 한다. 완전히 무작위로 만들수도 있고, 다시 mutaion, crossover를 시도할 수 있다.  확률적으로 처리하기 때문에 무작위 숫자를 만들어내는 루틴을 준비해야한다.  
광역 최적화 방법이 적용될 수 있는 충분히 어려운 문제들 중에서 가장 간단한 것들로는 아래와 같은 것들이 있을 수 있다.
 
(1)
532 개의 도시들이 있고, 이 도시들을 모두 방문하고 돌아오는 방법이 있을 것이다. 단 한 번씩만 한 도시를 방문하고, 처음에 머물렀던 도시로 다시 돌아오는 방법들 중에서 가장 거리가 짧은 경로는 어떤 경로인가? 이 문제가 그 유명한 외판원 문제이다. travelling salesman problem 이다.  도시의 수를 N이라고 하면, (N-1)!/2 정도의 가능한 경로가 가능하다. 그중에서 거리가 가장 작은 경로가 하나 있을 것이다.  이 경우, 가능한 해는 도시들을 일렬로 세우는 방법이다.  중복되지 않게 세우고 반드시 제자리로 돌아오도록 만들어야 한다.  그렇지 않으면 결코 해가 될 수 없다. 국소 최소화가 해석적으로 될 수 없는 경우이다.  Monte Carlo 방식으로 국소 최소화를 할 수 있다.
(2)
그 다음 문제는 원자들 사이의 상호작용이 알려져 있을 때,  예를 들어 Lennard-Jones 형식의 포텐셜 에너지가 알려져 있을 때, 가장 에너지가 낮은 구조는 무엇인가?  물론, 주어진 원자 수에 대해서 문제가 정의 된다. 특히 38, 55, 75인 경우의 원자 배열은 무엇인가?  원자 수가 N으로 표현되면, 가능한 국소 에너지 최소값들은 N값에 지수적으로 증가하는 국소 최소값들이 존재한다.  그 중에서 가장 에너지 값이 낮은 것 하나가 있을 것이다.  국소 에너지 최소화가 가능하다. LBFGS 같은 방법으로 국소 에너지 최소화가 가능한 경우이다.
(3)
주어진 외부 압력하에서 엔탈피가 가장 낮은 결정 구조를 찾는 문제,  이 경우, 원자에 작용하는 힘, 결정 격자에 작용하는 스트레스가 계산되어야 한다.  a, b, c, alpha, beta, gamma, 그리고 내부 좌표들{RI}이 필요하다.  결정구조는 단위셀에 N개의 원자들이 있을 때, 3N+6개의 자유도를 최적화해야하는 문제가 된다. 보다 전문적으로 특수한 전자구조를 가지는 결정 구조를 찾아내는 방식으로로 응용이 가능하다. 결정 구조는 안정한 구조가 되어야 한다. 따라서, 국소 최적화 작업에 해당하는 부분이 반드시 필요하다. 제일원리 전자구조 계산으로 표현되는 목적함수를 광역 최적화하여 결정구조를 찾는 방법. http://incredible.egloos.com/7133499 
(4)
주어진 조건들(실험적으로 확인된 원자-원자 거리들, 특정한 원자들 사이의 거리들이 주어졌을 때)을 만족하는  분자 구조 결정하는 문제가 있다. 알려진 실험 사실을 만족하는 분자 구조 결정하기.
(5)
실험 데이터를 만족하는 이론 모델 피팅하기. 데이터가 주어지고 해당 모델을 기술하는 방정식이 있을 때,  방정식 속의 계수들을 결정할 수 있다. 최대한 데이터를 잘 표현하는 계수들을 얻을 수 있다.
(6)
NMR, X-dirffraction 실험 데이터 기반 분자 구조 결정하기 문제, 특별히 잘못된 정보가 동시에 포함된 경우.
(7)
네트워크 커뮤니티 구조 결정하기.
(8)
단백질 구조 예측 문제, 구조 결정, 바이오인포매틱스에서 서열정보 정렬 알고리듬. 다중-서열 정렬 문제, 곁가지 정렬 문제, 리간드-도킹 문제.
(9)
Onsager-Machlup 작용, 광역 최적화를 통해서 가장 확률이 높은 원자들의 집단 이동경로 계산. 화학반응 경로 계산, Action-CSA 방법  http://incredible.egloos.com/7303943

CSA 순서도에서 볼 수 있듯이 광역 최적화 작업은 병렬적으로 계산이 진행될 수 있다. 또한, 특수한 방식으로 다수의 해들이 저장 및 정렬되고 있음을 알 수 있다.  풀은 항상 목적 함수 값 기준으로 정렬된 상태를 유지한다. 그 상태에서 풀은 업데이트 된다.  다양성을 보장하는 방식으로 해들이 업데이트 된다.  현재 상황에서의 차단 거리 값과  계산된 거리 값의 직접적이고 종합적인 비교를 통하여  새로 구한 해가 저장 및 정렬 될 지 안될지를 결정되게 된다. 독특한 저장, 업데이트 방식이 있다.  해가 업데이트 되면 즉시 해들은 목적 함수 기준으로 순차적으로 정렬되게 된다.




 
2차원 판넬 3장은 순서대로 CSA를 통하여 에너지가 낮은 곳을 찾아가는 광역 최적화의 과정을 순차적으로 그리고 도식적으로 나타낸 것이다. 광역 최적화가 진행됨에 따라서 흩어진 낮은 에너지 구조들이 2차원 공간에서 어떻게 분포하는가를 순서적으로 표시했다. 붉은 동그라미들이 에너지가 낮은 해들을 표시하는 것이다.



일반적인 유전 알고리듬과 달리 국소 최적화 과정을 포함한 유전 알고리듬을 표시했다.  또한 전통적인 유전 알고리듬에서는 해를 일차원 bit string 방식으로 표현한다.  0과 1이 나열된 것으로 해를 표현하는 방법이다. 길이는 정해져 있고, 1차원으로 나열된 특징이 있다.  국소 최적화 과정을 수행할 경우, 특히 병렬 처리를 할 경우, 계산 시간이 서로 달라질 수 있다. 국소 최적화가 빨리 끝나는 해가 있고 늦게 끝나는 해가 있을 수 있다.  따라서, 국소 최소화가 빨리 끝나는 경우에는 즉시,  새로운 해를 만들고, 연속해서 새로운 국소 최적화를 수행할 수 있도록 병렬화를 해야만한다.  그렇게 해야 병렬 효율성을 높일 수 있다. 여러개의 국소 최소화가 모두 이루어질 때까지 기다릴 필요가 없다.  특히, 목적 함수 값 계산과 국소 최소화가 병렬 컴퓨터를 활용해야만 할 정도로 시간이 오래 걸리는 계산일수도 있다. 이러한 경우에는 여러개의 디렉토리드를 만들고 각각의 디렉토리들에서 병렬 계산을 독자적으로 수행되게 할 수도 있다.  각각의 디렉토리에서 계산이 종료되면 그 결과를 읽어 들이면 된다.

mating은 crossover를 다르게 표시한 것이다. 유전 알고리듬에서는 반드시 crossover와 mutationd을 모두 다 활용해야만 한다. 물론, crossover를 좀 더 많이 시도한다.  예를 들어, 8:2 =crossover : mutation 수준으로 mutation을 crossover 보다 많이 시도하지 않는다.  crossover 또는 mutation은 순차적으로 하는 것이 아니고, 그 때 그 때 마다, 확률적 선택으로   crossover 또는 mutation이 시도된다.   새로운 시도해를 만들었을 때, 시도해가 만족해야만 하는 조건을 항상 체크한다.  이 조건을 만족하지 못하면 새로운 시도해를 다시 만들어낸다. 유전 알고리듬에서는 문제마다 고유의 crossover, mutation 방법을 개발해야만 한다.  각각 다수의 서로 다른 방법들이 존재할 수 있다.  crossover 방법을 사용하는 이유는 최근까지 얻어낸 좋은 해들을 잘 이용하자는 것이다. mutation 방법을 사용하는 이유는 이것과 완전히 다르다. 지금과는 다른 것을 찾는 것이다. 새로운 공간으로의 탐험을 의미한다.

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

Genetic Algorithm (유전 알고리듬): http://incredible.egloos.com/4856511
Particle Swarm Optimization(입자 군집 최적화): http://incredible.egloos.com/4731015
Differential Evolution(격차 진화): http://incredible.egloos.com/5265158
Parallel Tempering: http://incredible.egloos.com/4784590
Replica-Exchange Molecular Dynamics: http://incredible.egloos.com/4587643
Simulated Annealing: http://incredible.egloos.com/4784592
Nelder-Mead method: http://incredible.egloos.com/4838059
--------------------------------------------------------------------------------------------------------

참고 논문:
J.Comput.Chem.18, 1222-1232 (1997).
Phys.Rev.Lett. 91, 080201 (2003).

Computer Physics Communications, 203, 110-121 (2016).
http://www.nature.com/articles/ncomms15443
https://www.sciencedirect.com/science/article/pii/S0010465516300261

핑백

덧글

  • 바죠 2018/04/25 09:15 #

    DNA 메틸화와 히스톤 단백질의 변형 --> epigenetics
  • 바죠 2019/02/14 08:58 #

    https://en.wikipedia.org/wiki/Evolutionary_multimodal_optimization

    https://news.joins.com/article/23294039?cloc=joongang|article|tagnews

    https://news.joins.com/article/23365280?cloc=joongang|article|tagnews

    https://en.wikipedia.org/wiki/Baldwin_effect
※ 로그인 사용자만 덧글을 남길 수 있습니다.

최근 포토로그