MINIMUM 3

[Local Search Algorithms - Meta Heuristic Algorithm] Genetic Algorithm

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

[Local Search Algorithms] Gradient Descent

1. Gradient Descentgradient descent는 기울기를 이용하여 min을 찾는 알고리즘이다.  현재 state에서의 기울기를 계산하여 현재 위치에서 그 기울기만큼 뺀 것을 다음 state로 update하는 알고리즘이다. 만약 기울기가 음수이면, state가 양수방향으로 update되면서 local min에 다가갈 수 있고, 기울기가 양수면 state가 음수방향으로 update되면서 local min에 다가갈 수 있다.이때 알파는 learning rate다. learning rate가 크면 min으로 가는 step이 크지만, 수렴하는 것이 아닌 발산할 수 있다. learning rate가 작으면 수렴할 가능성이 크지만, 시간이 오래걸리는 단점이 있다.    1) 현재 위치를 random..

[Local Search Algorithms - Hill climbing Algorithms] First Choice

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..

반응형