PSO 알고리즘 한 줄 요약 새 떼가 집단 행동을 하는 방식에서 착안한 최적해 탐색 기법 주요 용어 - 위치, 속도: 각 개체의 위치와 이동 속도 - 관성: 각 개체가 이동하는 방향으로 가려는 힘 (inertia) - 가중치 w - pbest(Particle best): 각 개체가 경험한 개인 최적 위치 (indivisual best) - cognitive: 각 개체가 pbest로 가려는 힘, 가중치 c1 - gbest(Global best): 군집이 경험한 최적 위치 (swarm best) - social: gbest로 가려는 힘, 가중치 c2 - 새로운 속도 = w * 기존 속도 [inertia] + c1 * (pbest - 현재 위치) [cognitive] + c2 * (gbest - 현재 위치) ..

Nelder-Mead Method 한 줄 요약 Downhill Simplex라고도 불리며 다면체(Simplex)를 이용하여 함수의 최대/최소를 찾아가는 기법 주요 용어 - 함수의 최솟값을 찾는 경우 - 중심점: 최댓값을 갖는 점을 제외한 나머지 점들의 평균 - Reflection: 최솟값에서 가장 먼 점에서의 반대방향은 최솟값에 더 가까울 것이라는 가정을 하여 중심점 기준으로 Reflect(반사) - Expansion: 반사되어 간 좌표가 새로운 최솟값인 경우, 그 방향으로 조금 더 가면 최솟값이 있을 것이라는 가정을 하여 반사되었던 방향으로 Expanse(확장) - Contraction: 반사되어 간 좌표가 값이 큰 경우, 그 방향으로 덜 가면 더 작은 함수값을 찾을 수 있을 것이라는 가정을 하여 Co..

2024.02.02 - [데이터 분석/최적화 알고리즘] - 유전 알고리즘 python 코드를 통해 알아보기 2024.01.31 - [데이터 분석/최적화 알고리즘] - 유전 알고리즘 간단 소개 Nelder-Mead Method 한 줄 요약 유전 알고리즘처럼 유전자를 가지고 진화하는 최적화 기법, 변화 방식이 유전 알고리즘과 다르다. 주요 용어 - 유전자(Gene): 각 해의 값(feature) - 세대(Population): 최적해를 탐색하기 위한 후보해 - PN(Population Size): 일반적으로 PN=10n (n=x의 차원) - 적합도(Fitness): 후보해가 최적해인지 구하는 함수 - ex) Find x s.t. f(x) = 10 → fitness(x) = | f(x) - 10 | - 변이(..

2024.01.31 - [데이터 분석/알고리즘] - 유전 알고리즘 간단 소개 유전 알고리즘 간단 소개에 이어서 이번엔 자세한 설명을 python 코드와 함께 진행하고자 한다. 0. 기본 배경 0-1. 목적 유전 알고리즘은 "최적해 탐색 알고리즘"이다. $y=f(x)$라는 함수가 있을 때, 어떤 $x$가 $y=0$으로 만드는 지를 알고 싶은 상황이 생길 수 있다. 이럴 때 사용하는 것이 "최적해 탐색 알고리즘"이며, 여기서 함수 $f$가 머신 러닝 등 수식적으로 파악할 수 없는(Blackbox) 모델인 경우를 "Blackbox Optimization", 통칭 BBO라고 부른다. 참고로 수식적으로 파악할 수 있는 모델은 수치 최적화 또는 최적해 탐색(root finding)이라고 부르며 다음 링크를 확인하자..

알고리즘 명 목적 장점 단점 Bisection Search $f(x)=0$이 되게 하는 $x$ 탐색 초기 두 점의 부호가 다르면 반드시 해를 찾을 수 있음 비교적 오래 걸림 Newton's Method $f(x)=0$이 되게 하는 $x$ 탐색 비교적 빠름 함수가 미분 가능해야 함 Secant Method $f(x)=0$이 되게 하는 $x$ 탐색 미분 불가능한 함수에도 적용할 수 있음 두 지점이 함수값이 같아지면 더 이상 탐색할 수 없음 False Position Method $f(x)=0$이 되게 하는 $x$ 탐색 미분 불가능한 함수에도 적용할 수 있음 Bisection보다 빠르지만 다른 방법에 비해 느림 Newton's Method (Quadratic interpolation with 2nd deriv..

2024.02.02 - [데이터 분석/최적화 알고리즘] - Fibonacci Search 설명 (python 구현) Lagrange Polynomial Interpolation 서로 다른 점 n개를 지나는 가장 낮은 차수의 함수를 찾는 보간법 수식 서로 다른 점 n개를 지나는 가장 낮은 차수의 함수를 찾는 보간법 - $y= \left(\frac{x-x_1}{x_0-x_1} \right)y_0 + \left(\frac{x-x_0}{x_1-x_0} \right)y_1$ - $y= \left(\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} \right)y_0 + \left(\frac{(x-x_2)(x-x_0)}{(x_1-x_2)(x_1-x_0)} \right)y_1 + \left(\..

2024.02.02 - [데이터 분석/최적화 알고리즘] - Newton's Method (Quadratic interpolation with 2nd derivative) 설명 (python 구현) Fibonacci Search 함수 $f(x)$가 최소가 되게 하는 $x$를 찾는 알고리즘 수식 0. 피보나치 수열 N개를 만든다. 1. 최소값이 포함된 구간 $[a, b]$를 잡는다. 2. 양 끝점에 대해 $x_1=a+\frac{F_{N-2}}{F_N}L$, $x_2=b-\frac{F_{N-2}}{F_N}L$를 계산한다. - $L=b-a$ 3. 최소값이 존재하지 않는 구간을 제거한다. - 만약 $f(x_1) 2: L = self.b - self.a x1 = self.a + fi[M-3] / fi[M-1] * ..

2024.02.02 - [데이터 분석/최적화 알고리즘] - Golden Section Search 설명 (python 구현) Newton's Method (Quadratic interpolation with 2nd derivative) 방정식 $f(x) = 0$이 되게 하는 $x$를 찾는 알고리즘 수식 함수 $f(x)$가 해 $x*$ 근처에서 연속이고 두 번 미분가능할 때 - 임의의 점 $x_0$에서 테일러 급수를 2차 함수까지 전개 - 해당 2차 함수의 근을 $x_1$으로 삼아 반복 - 또는 2차 함수가 근을 갖지 않는 경우, local minimum이 되게 하는 $x$를 $x_1$으로 삼아 반복 - $|x_{n+1}-x_{n}| \le \text{tol}$일 때까지 반복, `tol`은 임의의 작은 수..

2024.02.02 - [데이터 분석/최적화 알고리즘] - False Position Method 설명 (python 구현) Golden Section Search 함수 $f(x)$가 최소가 되게 하는 $x$를 찾는 알고리즘으로 bisection method와 거의 동일하다. 수식 1. 최소값이 포함된 구간 $[x_l, x_u]$를 잡는다. 2. 양 끝점에 대해 $x_1=x_l+d$, $x_2=x_u-d$를 계산한다. - $d=(\phi -1)(x_u-x_l)$, $\phi = \frac{1+\sqrt5}{2}$ - 만약 $f(x_1)

2024.02.02 - [데이터 분석/최적화 알고리즘] - Secant Method 설명 (python 구현) False Position Method (Regula Falsi) 방정식 $f(x) = 0$이 되게 하는 $x$를 찾는 알고리즘 수식 1. 구간 $[a, b]$를 잡는다. - $f(a) \times f(b)