hccode0419 님의 블로그

1. Genetic Algorithm생물체가 환경에 적응해 나가면서 진화하는 모습(적자생존)을 모방하여 최적의 value를 찾는 알고리즘이다.  적자생존- 환경에 적합한 개체는 살아남는다.- 살아남은 개체는 자손을 낳는다. - 이때 자손은 부모의 유전자를 받고, 때때로는 돌연변이가 나타난다. 위 알고리즘을 모방한 것이 Genetic Algorithm이다. 1) 초기 염색체 집합을 생성2) 초기 염색체들에 대한 적합도 계산while :    3) 자손 염색체 생성    4) 자손 염색체들에 대한 적합도 계산    5) 부모 염색체와 자손 염색체 적합도 비교 XR = 0.1mR = 0.9popSize = 100limitEval = 100000resolution = 10DELTA = 0.01numEval = ..

1. Simulated Annealing Steepest Ascent, First Choice, Stochatic 알고리즘은 모두 current state에서 좋은 쪽으로만 이동하려고한다.Simulated Annealing은 확률적으로 value가 더 안 좋은 곳으로 state를 update 하면서 local min에서 벗어나 더 좋은 min으로 이동하게 만든다.  아래 예시를 보면 현재 state에서 확률적으로 값이 value가 좋아질 수도, 안 좋아질 수도 있다. 계속 좋은 쪽으로만 이동하면, local min에 빠지지만, 확률적으로 안 좋은 쪽으로 이동하고 계속 이동하다 보면, 보라색 점인 global min으로 이동할 수 있다.  이때 annealing이란 담금질을 의미하는데 금속을 녹이고 서서히..

1. StochasticSteepest Ascent는 너무 Greedy한 알고리즘이다. 즉 너무 현재상태에서만 좋은 값을 구하려고 한다. 그래서 초기값에 따라 너무 의존적으로 local에 빠지기 쉽다.  Stochastic은 neighbors를 구할 때 확률적인 요소를 추가하여 항상 best한 이웃을 구하는 것이 아닌, 조금 안 좋은 이웃을 선택할 수 있다.  그렇게 구한 neighrbor의 value와 current value를 비교하여 더 좋으면 update한다. 어떻게 확률적으로 이동하는지는 아래에서 살펴보자.  1) 현재 위치를 random으로 초기화2) 현재 위치의 value 계산while:    3) 현재 위치를 기준으로 모든 neighbors를 구함.    4) neighbors 중 stoc..

1. First Choicesteepest ascent와 다르게 neighbor을 하나만 결정하여  min을 찾는 알고리즘이다. 이웃을 구할 때 random하게 이웃을 하나 결정한 후 current value보다 좋으면 update하고 안 좋으면 이동하지 않는 알고리즘이다. 1) 현재 위치를 random으로 초기화2) 현재 위치의 value 계산while:    3) 현재 위치를 기준으로 랜덤하게 neighbor(successor)를 구함.    4) successor의 value를 구함.    5) best value와 current value 비교def firstChoice(p): current = randomInit(p) valueC = evaluate(current, p) i..

1. Steepest Ascent현재 위치에서 주변의 모든 neighbors를 보고 그중 가장 좋은(best) value인 state로 이동하면서 min을 찾는 알고리즘이다.  domain이 x1일 때를 예를 들어보자. 현재 state에서 neighbors를 구해보면 x'1과 x''1이다. 이 중 best value는 x'1이므로 current state를 x'1으로 update한다. 이 과정을 더 이상 더 좋은 이웃이 없을 때까지 반복한다.1) 현재 위치를 random으로 초기화2) 현재 위치의 value 계산while:    3) 현재 위치를 기준으로 모든 neighbors를 구함.    4) neighbors 중 best value를 구함.    5) best value와 current value ..