AI 수학59 시뮬레이티드 어닐링 (SA)의 TSP 적용 시뮬레이티드 어닐링 (SA, simulated annealing)은 처음에 순회외판원문제(TSP, traveling salesman problem)와 같은 조합 최적화(combinatorial optimization) 문제를 해결하기 위해 도입되었다. 대표적인 조합 최적화 문제인 TSP는 \(n\) 개의 서로 다른 도시의 좌표 \((x,y)\) 가 주어졌을 때, 각 도시를 한번씩 모두 방문하는 최단 경로를 찾는 문제다. TSP는 이동 경로 계획, 생산 계획, 적재 계획, 마이크로칩 설계, 유전학 등 응용 분야가 꽤 넓다. 조합 최적화 문제의 대부분은 NP-hard문제에 해당하기 때문에 다항식 시간 최적해를 구할 수 없다. 이 때문에 개별 개체의 수가 매우 큰 경우에는 최적해 대신에 빠르고 효율적으로 계산.. 2025. 2. 12. 시뮬레이티드 어닐링 (Simulated Annealing) 시뮬레이티드 어닐링 (SA, simulated annealing)은 1983년에 커크패트릭(Kirkpatrick)이 개발한 최적화 알고리즘으로서 물리적 어닐링 과정을 최적화의 관점에서 모방하여 알고리즘을 개발했다고 한다. 시뮬레이티드 어닐링(SA)은 처음에 순회외판원문제(TSP, traveling salesman problem)와 같은 조합 최적화 문제를 해결하기 위해 도입되었지만 최근에는 연속형 최적화 문제 해결에도 적용되고 있다. 물리적 어닐링은 금속을 가열하여 액체 상태로 만든 다음 규칙적인 결정성 구조를 형성할 때까지 천천히 냉각시키는 방법이다. 냉각 과정에는 냉각이 시작되는 초기 온도와 냉각 속도 등 두가지 주요 파라미터가 있는데, 이 값에 따라 고체 상태의 금속의 강성과 원자 구조의 규칙성이 .. 2025. 2. 12. [MCMC] 메트로폴리스-헤이스팅스 알고리즘 앞선 게시글 (https://pasus.tistory.com/358)에서, 천이 커널(transition kernel) \(K\) 를 목표 확률밀도함수(pdf) \(p(\mathbf{x})\) 가 정상(stationary) 분포가 되도록 설계할 수 있다면, 마르코프 체인을 통해 목표 확률 분포에서 추출한 것과 동일한 샘플을 생성할 수 있음을 확인했다. 그렇다면, 우리가 원하는 목표 확률밀도함수에 대해 천이 커널을 어떻게 설계할 수 있을까? 메트로폴리스(Metropolis)가 처음 제안하고 이후 헤이스팅스(Hastings)가 일반화한 방법에 따르면, 이산(discrete) 상태 공간에서도 계산이 어려운 천이 커널의 명시적인 함수를 구하는 대신, 이전 샘플이 주어졌을 때 새로운 샘플을 추출하는 절차를 명확히.. 2025. 2. 1. [MCMC] MCMC 개요 어떤 확률분포를 가진 랜덤변수에서 데이터를 생성하는 과정을 샘플링(sampling)이라고 한다. 파이썬(Python)이나 매트랩(Matlab)과 같은 많은 컴퓨터 언어에서는 기본적으로 가우시안 확률분포나 균등 확률분포와 같은 표준 형태의 확률밀도함수로부터 샘플을 추출할 수 있는 함수를 제공한다. 하지만 그렇지 않은 경우에는 어떤 방법으로 샘플을 추출해야할까. 먼저 직접적인 방법이 있다 (https://pasus.tistory.com/49). 누적분포함수(cumulative distribution function)의 역함수를 이용하는 방법으로서 정확한 샘플링 방법이다. 하지만 랜덤변수가 다차원(multi-dimension)을 갖거나 복잡한 확률밀도함수를 갖는 경우에는 이 방법을 적용하기가 어렵다. .. 2024. 12. 26. 파티클 군집 최적화 (Particle Swarm Optimization) 파티클 군집 최적화(PSO, particle swarm optimization)는 1995년에 에버하트(Eberhart)와 케네디(Kennedy)가 개발한 최적화 알고리즘으로서 먹이를 찾는 새(bird)들의 군집 행동을 모방해서 개념을 정립했다고 한다. 새 떼는 무리 내부의 리더(leader)나 무리 외부의 통제자 없이 새들간의 상호 작용을 통해 먹이를 찾는다고 한다. 이러한 새들의 집단적 행동을 모방하여 최적화 문제를 풀기 위해서는 군집 지능(swarm intelligence)이라는 전제가 필요하다. 군집 지능은 단순하게 행동하는 개별 에이전트들을 군집으로 적절히 연결하면 그들의 집단적 행동이 매우 지능적인 결과를 만들 수 있다는 것을 의미한다. 즉 멍청한 에이전트들을 연결해 놓으면 전체적으로 똑똑한 .. 2024. 12. 20. 크로넥커 곱 (Kronecker Product) 두 행렬 \(A \in \mathbb{R}^{n \times m}, \ B \in \mathbb{R}^{p \times q}\) 의 크로넥커 곱(Kronecker product) \(A \otimes B\) 는 다음과 같이 정의된다. \[ \begin{align} A \otimes B= \begin{bmatrix} a_{11} B & ⋯ & a_{1m} B \\ ⋮ & ⋱ & ⋮ \\ a_{n1} B & ⋯ & a_{nm} B \end{bmatrix} \in \mathbb{R}^{np \times mq} \end{align} \] 예를 들어서 행렬 A와 B가 각각 다음과 같을 때, \[ \begin{align} A= \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix},.. 2024. 12. 10. 정상 시퀀스 (Stationary Sequence) 랜덤 시퀀스의 정상성(stationarity)이란 랜덤 시퀀스의 확률적 특성 일부 또는 전부가 시불변(time-invariant)이라는 뜻이다. 정상 시퀀스에는 엄밀한 의미의 정상(SSS, strict-sense stationary) 시퀀스와 넓은 의미의 정상(WSS, wide-sense stationary) 시퀀스로 두 가지가 있다. SSS 시퀀스는 임의의 싯점 \(t\) 와 임의의 차수 \(n\) 에 대해서 시퀀스 \( ( \mathbf{x}_t, \mathbf{x}_{t+1}, ... , \mathbf{x}_{t+n-1 }) \) 과 임의의 정수 \(h\) 만큼 시프트된 시퀀스 \((\mathbf{x}_{t+h}, \mathbf{x}_{t+1+h}, ... , \mathbf{x}_{t+n-1+h.. 2024. 11. 6. 벡터 항등식과 벡터 미분 항등식 먼저 쓸모가 많은 벡터 항등식 4개를 소개한다. 필요할 때 참고하면 된다. 증명은 복잡하긴 해도 어렵진 않다. 여기서 모든 벡터는 3차원 벡터이다. \begin{align} & \mathbf{a} \cdot (\mathbf{b} \times \mathbf{c})= \mathbf{b} \cdot (\mathbf{c} \times \mathbf{a})= \mathbf{c} \cdot (\mathbf{a} \times \mathbf{b}) \\ \\ & \mathbf{a} \times (\mathbf{b} \times \mathbf{c})=(\mathbf{a} \cdot \mathbf{c})\mathbf{b}-(\mathbf{a} \cdot \mathbf{b})\mathbf{c} \\ \\ & (\math.. 2024. 9. 5. 케일리-해밀톤 정리 (Cayley-Hamilton Theorem) 정방 행렬 또는 정사각형 행렬 (square matrix) \(A \in \mathbb{R}^{n \times n}\) 의 특성 다항식(characteristic polynomial)은 다음과 같이 정의된다. \[ \begin{align} \Delta (\lambda)= \det (\lambda I-A)= \lambda^n+c_{n-1} \lambda^{n-1}+ \cdots +c_1 \lambda+c_0 \tag{1} \end{align} \] 참고로 특성 방정식 \(\Delta (\lambda)=0\) 의 해는 행렬 A의 고유값(eigenvalue)이다. 행렬 \(A\) 의 특성 다항식은 식 (1)과 계수가 똑같은 행렬 다항식으로서 다음과 같이 정의된다. \[ \begin{align} \Del.. 2024. 7. 14. 플롭 (Flop) 선형대수 수치 알고리즘의 복잡성을 표현하는 방법 중의 하나로 알고리즘을 수행하는 데 필요한 부동소수점 연산의 총 횟수를 사용한다. 부동소수점 연산 (floating point operation)을 간단히 플롭(flop)이라고 하는데, flop은 두 개의 부동소수점 숫자의 덧셈, 뺄셈, 곱셈 또는 나눗셈 등을 한 번 수행하는 것으로 정의한다. 컴퓨터의 성능을 수치로 나타내는 단위로서 사용되는 FLOPS도 있다. 이 때의 FLOPS는 FLoating point Operations Per Second의 약자로 해당 컴퓨터가 처리할 수 있는 초당 얼마나 많은 연산을 처리하는 지를 나타내는 단위다. 여기서는 부동소수점 연산(flop)의 횟수(count) 라는 의미의 flops에 대해서 설명한다. 플롭의 횟수, 즉.. 2023. 11. 9. 이전 1 2 3 4 ··· 6 다음
