hccode0419 님의 블로그

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

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

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

1. Local Search Algorithms인공지능을 공부하다 보면 항상 min을 찾으라고 한다.  local Serach Algorithms는 말 그대로 local min을 찾는 알고리즘이다. 2. Problem Local Search Algorithms를 풀기 위해 2개의 문제를 준비했다.1) Numeric연속함수의 Minimum을 구하는 것이 목표이다.  - Ackley위의 예시 사진은 변수가 2개이지만 준비된 Ackley는 변수가 5개인 함수이다.각 변수마다 범위가 (-30, 30)이다. 20 + math.e - 20 * math.exp(-(1/5) * math.sqrt((1/5) * (x1 ** 2 + x2 ** 2 + x3 ** 2 + x4 ** 2 + x5 ** 2))) - math.ex..