아인슈타인의 논문 by 바죠

공유하기 버튼

 

러시아 전 반드시 득점해라! by 바죠

2014 브라질 대 러시아전 반드시 득점해라!

제2의 안정환 세러머니가 필요하다.

기억하라. 2002년 6월 10일 대 미국전, 안정환의 골과 쇼트트랙 세러머니를. (김동성 기를 살려준 것이다.)

이번에는 채점을 엉터리로 하는 다소 고난이도의 세레머니 디자인이 필요하다.

한국도 예외가 아니었다. 개최국으로서 실로 쪽팔리는 금메달 장사를 했었다.

올림픽 최고의 오심 사례로 1988서울 올림픽 남자 복싱 경기를 기억한다. 최대의 피해자는 로이 존스 쥬니어 선수였다.

하지만, 실력은 어디가지 않는 법이다. 매우 휼륭한 프로 복서로서 명성을 날렸다. 
http://en.wikipedia.org/wiki/Roy_Jones,_Jr.

이번에도 개최국이 개쪽을 팔아가면선 금메달을 가져갔다.

다들 목적을 이루려고만 한다.

제대로 해야한다. 쪽팔리는 줄 알아야 한다.

역사적 오명은 금메달로 가려지지 않는다.

국가 신임도 떨어뜨리는 짓이다.

소탐대실이다.

러시아 소치 올림픽 경기장 및 부대 시설 준비는 아주  미비했지만, 심판진 구성에서는 아주 열심히 한 올림픽으로 기억될 것이다.

일차 쇼트 프로그램 심판진이 크게 말을 듣지 않자 다시 재빨리 2차 행동을 보였다.

갈아 치운것이다. 말을 듣지 않는 심판들을 제거한 것이다.

그들에게 천만 다행인것은 러시아 선수가 크게 실수를 하지 않는 것이였다. 

그들을 마지막까지 괴롭힌건, 김연아 선수가 넘어지지 않은 것이다.
 


출처:
https://www.google.co.kr/search?q=%EC%95%88%EC%A0%95%ED%99%98+%EC%98%A4%EB%85%B8+%EC%84%B8%EB%A0%88%EB%AA%A8%EB%8B%88&newwindow=1&tbm=isch&imgil=EK8ITMb38SEuNM%253A%253Bhttps%253A%252F%252Fencrypted-tbn0.gstatic.com%252Fimages%253Fq%253Dtbn%253AANd9GcT35ltdyYHa_Zk5g9wbggitk3A59XKvF8dlr2je4vqvk8D-Goru9w%253B567%253B420%253BYq028UlJJZo5jM%253Bhttp%25253A%25252F%25252Fblog.daum.net%25252F_blog%25252Fhdn%25252FArticleContentsView.do%25253Fblogid%2525253D0FDEx%25252526articleno%2525253D11024109%25252526looping%2525253D0%25252526longOpen%2525253D&source=iu&usg=__4JpEK-2ID2OaFWPsY-gudAm0yd4%3D&sa=X&ei=1x0HU5jKDae0iQehl4G4AQ&sqi=2&ved=0CFYQ9QEwBQ&biw=1272&bih=1282#facrc=_&imgdii=_&imgrc=hgLhYB42miXicM%253A%3BhIcpehgOhNUwJM%3Bhttp%253A%252F%252Fcfile25.uf.tistory.com%252Fimage%252F15365D1549AFF6CAA3895D%3Bhttp%253A%252F%252Fmeguri.tistory.com%252F35%3B250%3B272

공유하기 버튼

 

Genetic Algorithm [algorithm] by 바죠

Genetic Algorithm

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

Genetic algorithm

 컴퓨터 알고리듬이다. 다윈의 적자 생존에 기반한 알고리듬이고 최적화 알고리듬으로 잘 알려져 있다. 목적함수 값이 가장 좋은 해를 찾는데 사용된다. 목적함수 최적화는 최대화 또는 최소화를 말한다. 사실여기서는 최대화나 최소화는 같은 의미를 가진다. 목적함수에 부호(+ --> -)를 바꾸면 이들은 사실 같은 의미를 가지고 있다. Genetic algorithm 항상 정답을 보장하지 못한다. 결정론적 문제 풀이 방식이 아니다. 그렇게 쉽게 풀리는 문제 풀이 방식이 아니기 때문이다
쉽게 말해서 매우 어려운 문제를 풀기 때문에 생기는 현상이라고 볼 수 있다.

Genetic algorithm
은 상당히 일반적이어서 다양한 응용이 가능하다. 문제 풀이에서 동시에 여러 개의 시도 해들을 고려한다따라서 아주 좋은 병렬 알고리듬의 예가 된다. Simulated annealing (담금질 시늉)에서처럼 단일 시도 해(trial solution)를 상정하는 것이 아니고, 여러 개의 해들을 동시에 고려한다. 여러 개의 시도 해들을 점진적으로 변화시켜 나가려고 한다. Simulated evolution (진화 시늉)이라고 볼 수 있다.  Genetic algorithm은 자연과학/공학/인문사회 문제 풀이에 널리 이용된다. 목적함수 값이 좋은 해들, 예를 들어두 개의 좋은 해들 사이의 교차 연산 crossover를 도입한다. 교배연산이라고 생각할 수 있다. 특정한 하나의 시도 해의 mutation (변이)를 또한 도입한다. 이렇게 함으로써, 부모보다 자식에서 보다 좋은 목적함수를 가지게 하는 것이다. 부모 세대와 다른 새로운 세대를 만든다고 볼 수 있다.

Genetic algorithm에서 새로운 세대를 만들어 내는 방식은 crossover/mutation 을 통해서 이루어진다한 가지 확실한 점은 이것이다. Genetic algorithm에서는 위에서처럼 현재 해 두 개를 이용하여 대략 절반씩 바꾸어서 새로운 해가 될 수 있을 지를 시험하게 해준다. 이것이 다른 최적화 방법과 근본적으로 다른 점이다쉽게 말해서 굉장히 멀리 떨어진 구조로 쉽게 이동해서 목적함수를 평가할 수 있게 한다. 대부분의 계산들에서 이런 것들이 허용되지 않는다.  예를 들어, 분자 동역학 계산에서는 어느 정도 유사한 분자 모양 사이를 돌아 다니게 되어 있다. 물론, 온도가 높을 수록 더 넓은 분자 모양 공간을 돌아 다닐 수 있다. 하지만, 여전히 한계가 있다. 반면, Genetic algorithm에서는 보다 더 넓은 분자 모양 공간을 둘러다 볼 기회가 많이 제공된다. 소위 Markov chain에서 벋어난 전이가 쉽게 이루어 질 수 있다는 점이다. 이 점이 바로 genetic algorithm이 다른 여러 알고리듬에 비해서 우월한 최적화 방법이 되는 부분적인 원인이 된다. 오히려 Monte Carlo에서 새로운 변형 형태로 받아 들여도 상관이 없다. x---> x'이라는 변형이 아주 자유롭다. 모든 것은 min[1, exp(-(E'-E)/(kT))]로 판단되기 때문이다. 어떠한 변형을 취해도 이론적으로 문제가 없다. 다만, 현실적으로 그렇게 효율적인 변형을 잘 만들어 내지 못하고 있다. 또한 문제에 따라서 그 변형이 많이 달라질 수도 있다. 아무튼 이 부분이 아주 어려운 부분이다.

부모세대, 자식세대라는 개념이 자연스럽게 적용된다. 왜냐하면 crossover라는 개념을 적용하기 때문이다. 부모 세대, 자식 세대의 개체 수를 동시에 고려한다. 편이상 개체 수를 같게 둘 수 있다. 점수가 좋은 해, 두 개를 선택하고 crossover를 시켜서 자식 세대를 만들어 간다.(교차) 이것은 부모가 결혼해서 자식을 낳는 것과 같은 것이다. 하나의 교차에 의하면 두 개의 자식이 가능하다. 프로그램에 따라서는 하나만 고려하기도 한다. 물론 둘 다 고려해도 좋다. 부모의 특징을 자식이 직접 물려 받는 것이다. 엄마, 아빠의 특징을 자식이 대략 반반씩 직접 물려 받는 것이다. 부모로 부터 대략 절반씩 유전자를 물려 받아야 한다. 하지만, 꼭 절반이 될 필요는 없다. 꼭 절반을 못 만드는 상황도 실제 문제에서는 생긴다분자모형의 경우 원자 종류별로 절반에 가깝게 양분해서 각각 새로운 아들을 만들면 된다. 하나의 분자의 질량 중심을 원점으로 이동시킨 다음, z, y, x 축으로 무작위 회전시킨 다음, x 축 왼쪽, x 축 오른쪽으로 분류하면 원하는 분자의 절반을 쉽게 얻을 수 있다. 1/4+3/4, 1/3+2/3, 1/2+1/2 형식으로 아들을 만들 수 있다. 이러한 교차 작업이 큰 문제가 되질 않는다오히려 다양한 교차가 허용되는 것이 더 유리할 수 있다. 다시 말해서 교차에도 변종이 있을 수 있다. 한 가지만 가능한 것이 아니다. 적절한 확률을 부여하여 모두 다 사용 할 수 있다물론, 개체 변이 또한, 돌연 변이 형식으로 인정해서 유전이 될 수 있다.

사실 솔류션 표현에 관한 이쓔가 있다. 어떻게 표현하고 어떻게 교차,변이 시키는가와 밀접하게 연관되어 있다. 제일 중요한 점은 시도 해로서 만족해야 하는 조건을 만들어 두고 교차, 변이를 수행한 다음 조건들을 체크해야한다. 조건을 만족하지 못하면 다시 교차/변이로 새로운 형식의 시도해를 만들어 낸다.

가능하면, gradient벡터를 얻을 수 있다면, 국소 최적화 알고리듬을 genetic algorithm 동시에 사용하는 것이 좋다. 구하고자 하는 해를 bit (예를 들면, 010011010101)로 표현하는 것이 오리지날 Genetic algorithm이다. 또한 오리지날 알고리듬에서는 국소 최적화를 하지 않는다. 실전에서는 연속 variable로 해를 표현한다많은 경우, 국소 최적화를 한다. (가능하면 그렇게 한다.) bit로 표현하나 실수로 표현하나 물리적으로는 마찬가지이다. 자명한 사실이다쓸데 없이 bit로 변환하고 다시 실수로 변환하는 과정이 왜 필요한지 모를 지경이다. 물리적으로 나누어지면 되는 것이다. 실제는 대부분 병렬모드로 계산을 하게 된다선택, mutation, crossover 부분을 병렬화 시키고, 대치 부분만 한 노드에서 실행하면 된다:010011010101 또 다른 하나의 해:011010010111 가 알려 졌을 때, crossover는 아래와 같이 해서 또 다른 해를 만들어 낼 수 있다.
010011010101 
011010010111 
다시 말해서, 검은 색 부분만을 취해 낼 수 있다.  (교차의 위치는 바뀔 수 있다.) 010011010111 mutation은 보다 자명하다. (변이) 특정 위치의 1 0으로 (또는 1 0)으로 바꿀 수 있다. point mutation이라고 할 수 있겠다. Point mutation만 고집할 필요가 당연히 없다.


mutation보다는 crossover를 더 많이 한다. 왜냐하면 보다 효율적이기 때문이다. x1 : f(x1) : local minimization f(x1) : f(y1)x2 : f(x2) : local minimization : f(y2)x3 : f(x3) : local minimization : f(y3)처럼 많은 해들이 있다. x1,x2,x3 개인, , 시도 해. 국소 최적화된 해로 바뀌어 사용하면 x1--> y1으로 바뀌게 된다. 목적함수: f(x)는 주어진 것이다항상 f(x1) >=  f(y1)이 될 것이다. 이것으로 해들의 평가할 수 있다. 다시 말해서, 목적함수 값을 얻어낼 수 있다. 예를 들어, y1 y3 crossover를 만들어 낼 수 있다. 또한, y2 mutation 될 수 있다. , 새로운 시도 해가 될 수 있다. 예를 들어, x4 =  mutaion (y2) or crossover(y1,y3)국소 최적화를 통해서, x4 y4가 될 것이다.이렇게 만들어 진 자식세대인 y4는 기존 인구 풀에 들어 갈 수 있을 지 소멸시켜야 할지를 결정하게 된다.그것은 바로 f(y4)가 얼마나 좋은가에 의해서 결정된다. 이 값이 좋으면 다른 개체가 희생되고 이 해가 선택되어 전체 개체 풀에 들어 가게 된다. 그러하지 않으면 y4를 소멸시켜 버린다. (대치) 세대 차이가 나는 부모 세대 개체와 신 세대가 공존하기 마련이다. 왜냐하면 우수한 목적함수 값을 가지는 부모 세대의 시도 해들은 여전히 전체 개체 집단에 여전히 머물러 있을 수 있다.

두 개의 개체를 뽑아서 교차 crossover를 하려고 한다. 이 때, 목적함수가 좋은 두 개체를 더 많이 뽑아야 한다. 적어도 좋은 목적함수를 가진 개체는 뽑힐 확률이 높아야 한다. (선택)
이 요구 조건을 어디까지 받아 줄 것인지가 관건이다. 전적으로 받아 주어서도 안되고, 적당히 받아 주어야 한다. 적어도 확률은 높아야 한다. 좋은 목적함수를 받은 개체들이 부모가 될 확률은 높아야 한다. 하지만, 장기적인 관점에서 다양성을 확보하지 못하면 안 된다. 전체적인 퇴보가 올 수 있다. (광역 최적화에 실패한다.)따라서 최대한 다양성을 존중하는 절차가 반드시 내포되어 있어야 한다. 다시 말해서, 목적함수는 다소 좋지 않더라도 반드시 특이한 구조들은 받아 들여야 한다. 실제로 광역 최적화가 달성 되려고 하면 이렇게 해야 한다. 초반에는 국소 최적화 답안만 가지고 있는 상황이다. 초반 국소 최적화 결과가 좋다고 해서 그것들만 받아 들이면 광역최적화에 실패할 확률이 매우 높아 진다. 광역 최적화를 성공적으로 수행 하기 위해서는 다양성을 초기부터 확보해야만 한다이것이 목적 함수 값그 값 만으로 단순하게 부모를 선택해서는 안 되는 가장 큰 이유이다.

개체수, crossover/mutation 비율, 개체들에서 부모로 뽑는 방법, 이런 것들이 genetic algorithm에서의 파라메터라고 할 수 있다.crossover 80 퍼센트, mutation 20 퍼센트 정도 할 수 있다.전체 개체수는 50 정도로 할 수 있을 것이다. 물론, 큰 수일수록 좋은 계산이 되고 계산량은 엄청나게 늘어날 것이다. 하지만, 알고리듬은 놀라울 정도로 병렬 효율성이 뛰어날 수 있다. 컴퓨터 자원만 충분하다면, 충분히 큰 전체 개체 수를 잡을 수 있다. 목적함수 값들이 뛰어난 무리들을 부모로 선택하면 좋다. 예를 들어 상위 40-50 퍼센트에 들어오는 개체들을 부모가 되게 하면 좋을 것이다. 또한, 목적함수 값이 뛰어난 개체들은 좀 더 높은 확률로 부모가 되게 할 수 있고 그렇게 하는 것이 좀 더 유리하다 

random number 는 통상 [0,1) 사이의 값 형식으로 제공된다. 많은 컴퓨터 프로그램에서 사용되는 형식이다. 같은 함수 꼴이지만, 부를 때마다 다른 값이 나온다. 대부분의 컴퓨터 프로그램에서 그렇다. 물론, 초기화를 어떻게 시키느냐에 따라서 전혀 다른 순서로 random number가 연이어 나오게 된다. 초기화시키는 방법은 일반으로 정수를 사용한다. 특정 정수로 random number 생성기를 초기화 시킬 수 있다. 이렇게 하면, 항상 같은 random number를 만들어 낼 수 있다. 따라서, r 을 그렇게 만든 수라고 하면, r* 100 +1 이렇게 계산하면, 우리는 1,2,3,....100까지 숫자 중에 한 숫자를 얻게 된다. 그것도 완전히 균등한 확률로 1,2,3,....,100까지 숫자 중 하나를 선택할 수 있다. 이런 식으로 랜덤 넘버를 만들어서 사용할 수 있다. 또한, 확률 80 퍼센트로 crossover mutation보다 많이 할 경우, r > 0.2 이면 crossover를 하면 된다. 왜냐하면, r 값은 0.에서 1. 사이의 값인데, 0.8 : 0.2 로 구간을 나누어서 균등확률의 범위를 정해 버릴 수 있다.


부모가 될 두 개체를 뽑을 때, 소위 토나먼트 방식으로 뽑을 수 있다. 먼저 연속해서 서로 다른 두 개체를 무작위로 뽑는다. i, j라고 부른다. j /= i이다. 이 때, i 의 목적 함수가 j 의 것보다 더 좋다면, 우리는 i 를 부모로 선택한다. (토나먼트 승자: i)마찬가지로 부모가 될 또 다른 개체를 선택할 수 있다. 물론, 앞에서 구한 구조와는 서로 다른 구조이기만 하면 된다. 만약 같은 구조가 나왔다면, 다른 구조가 나올 때까지 다시 하면 될 것이다. 토나먼트를 여러 라운드로 할 수도 있을 것이다. 그렇게 하면 좀 더 목적함수가 좋은 개체가 부모가 될 확률일 더욱 더 증가하게 된다. 선택, 교차, 변이, 대치 이렇게 4가지 프로그램을 만들어야 한다. 기존세대 중에서 목적함수가 뛰어난 개체들을 다음 세대에서도 그대로 생존한다. 이것을 Elitism이라고 한다.

진지하게 따지고 보면 알고리듬이라기 보다는 접근 방법에 가깝다. 그것도 아주 일반적인 것이다.이 접근법을 구체적인 문제에 적용하면 실질적인 알고리듬이 될 것이긴 하다. 약점: 프로그램 종료 시점을 잘 정의할 수가 없다. 결정론적 정답을 주는 것은 아니다. 소위 발견법 분류에 속한다. 이상 살펴 보았듯이 genetic algorithm은 매우 단순한 형식의 프로그램이다랜덤 함수를 적절히 잘 이용하면 쉽게 구현할 수 있다. 물론 함정이 있다. 정확하게 풀리는 문제 풀이 방식이 아니기 때문에프로그램을 정확하게 만들었는지 테스트 하기가 다소 까다롭다. 당연히 병렬화 해야만 그 성능을 재대로 맛 볼 수 있다또한 당연하게 병렬 컴퓨터 자원을 확실하게 확보해야만 한다. 소위 모든 가능한 변수값을 다 나열하여 버리고각각에 대해서 목적함수를 평가하여 최적의 변수를 찾아 낼 수 있는 경우가 있을 수 있다. 이 경우는 정확하게 계산을 할 수도 있다모든 변수를 나열하는 것이 유한한 경우이고 또한 제법 빨리 모든 경우의 목적함수 값을 다 계산할 수 있는 경우는 문제 풀이가 가능하다. 그리고 완벽하게 문제를 푼 경우에 해당한다여기서 가정은 그럴듯한 시간 안에 답을 얻을 수 있다고 가정했다. 이런 문제는 제법 쉬운 문제 풀이에 해당한다. 그냥 하나 하나 대입해서 목적함수를 계산하고 나중에 비교하면 끝이다.

하지만, 많은 경우, 이렇게 가능한 변수들을 나열할 수 없다. 다시 말해서 무수하게 많은 가능성이 열려 있다. 모든 가능성에 대해서 테스트 하는 것이 거의 불가능하다. 많은 경우, 이것이 사실이다그래서 우리는 이러한 경우에 대해서 문제 풀이를 발견법(heuristic)이라는 방법으로 문제를 풀 수밖에 없다.



particle swarm optimization: http://incredible.egloos.com/4731015
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



공유하기 버튼

 

Atomic Simulation Environment by 바죠

Atomic Simulation Environment
https://wiki.fysik.dtu.dk/ase/


https://wiki.fysik.dtu.dk/ase/tutorials/tutorials.html

대단한 친구들이다. 그 꿈이 대단하다.
크게 기여하는 친구들이 만든 것이다.

공유하기 버튼

 

1 2 3 4 5 6 7 8 9 10 다음