matlab code17 시뮬레이티드 어닐링 (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. [B-Plane] B-평면 타켓팅 - 2 행성 간 임무를 수행하는 동안 우주비행체는 섭동력의 영향을 받아 원하는 임무 궤도에서 벗어날 수 있으므로 실제 B-벡터도 설계한 값과 차이가 발생한다. 이러한 오차를 조정하기 위해서 슈팅방법(shooting method) 기반의 B-평면 타겟팅 방법을 사용하여 우주비행체의 속도벡터를 조정하는데 이를 궤적수정기동(TCM, trajectory correction manuever)이라고 한다. 목표로 하는 B-벡터를 \(\vec{B}^\star\), 현재의 B-벡터를 \(\vec{B}\) 라고 하고 테일러 시리즈를 이용하여 전개한 후 1차 절삭하면 B-벡터의 오차 \( \Delta \vec{B}= \vec{B}^\star- \vec{B}\) 와 속도벡터 섭동 \(\Delta \vec{v}\) 의 관계를 .. 2025. 1. 31. [B-Plane] B-평면 타켓팅 - 1 B-평면 타겟팅(B-plane targeting)은 우주 탐사에서 행성 플라이바이(flyby)나 행성의 접근 경로를 설계할 때 사용되는 중요한 개념이다. B-평면 타켓팅의 목표는 B-평면 상에서 특정 목표점을 맞추는 것이며 이 과정을 통해서 행성 플라이바이, 궤도 진입 (orbit insertion) 또는 행성 착륙 목표 지점 타겟팅의 조건을 만족시킬 수 있다. 또한 행성 간 임무를 수행하는 동안 우주비행체는 섭동력의 영향을 받아 궤도가 원하는 임무 궤도에서 벗어날 수 있으므로 현재 우주비행체의 상태벡터와 목표점 좌표를 바탕으로 오차를 보정하기 위한 궤적수정기동(TCM, trajectory correction manuever)을 설계하는 데에도 B-평면 타겟팅을 적용할 수 있다. 먼저 B-평면 타.. 2025. 1. 30. HiPPO - 3 이전 게시글(https://pasus.tistory.com/363)에서 함수 \(f(x), \ 0 \lt x \le t\) 를 N차원 부분 함수공간으로 투사한 근사 함수 \(g(x), \ 0 \lt x \le t\) 를 다음과 같이 유도하였다. \[ \begin{align}& g(x)= \sum_{n=0}^{N-1} c_n (t) \sqrt{(2n+1)} P_n \left( \frac{2x}{t}-1 \right) \tag{1} \\ \\& \dot{\mathbf{c}}(t)= - \frac{1}{t} A \mathbf{c}(t)+ \frac{1}{t} Bf(t) \end{align} \] 식 (1)에 의하면 HiPPO는 본질적으로 연속시간(continuous-time) 에서 정의된 상미분 .. 2025. 1. 12. 파티클 군집 최적화 (Particle Swarm Optimization) 파티클 군집 최적화(PSO, particle swarm optimization)는 1995년에 에버하트(Eberhart)와 케네디(Kennedy)가 개발한 최적화 알고리즘으로서 먹이를 찾는 새(bird)들의 군집 행동을 모방해서 개념을 정립했다고 한다. 새 떼는 무리 내부의 리더(leader)나 무리 외부의 통제자 없이 새들간의 상호 작용을 통해 먹이를 찾는다고 한다. 이러한 새들의 집단적 행동을 모방하여 최적화 문제를 풀기 위해서는 군집 지능(swarm intelligence)이라는 전제가 필요하다. 군집 지능은 단순하게 행동하는 개별 에이전트들을 군집으로 적절히 연결하면 그들의 집단적 행동이 매우 지능적인 결과를 만들 수 있다는 것을 의미한다. 즉 멍청한 에이전트들을 연결해 놓으면 전체적으로 똑똑한 .. 2024. 12. 20. 두빈스 경로 (Dubins Path) - 1 평면상에서 시작점과 끝점을 연결하는 최단거리 경로를 구하려고 한다. 단 시작점과 끝점에서 각각 출발 방향과 도착 방향이 정해져 있고 경로가 가질 수 있는 최대 곡률(curvature)에 제한이 있는 경우다. 이 문제는 제약조건이 있는 최적화 문제로서 최단거리 경로는 최대 곡률을 갖는 원형 호와 직선을 결합하여 만들어진다는 것이 증명되었다. 이 최단거리 경로를 두빈스 경로 (Dubins path)라고 한다. 두빈스 경로는 기하학적인 방법으로 간단히 생성할 수 있기 때문에 이동 로봇, 드론, 무인 잠수정 등의 운동체 경로 계획 방법으로 널리 사용되고 있다. 두빈스 경로는 CSC 또는 CCC 경로 중 하나다. 여기서 C는 원호(circular arc), S는 직선(straight line)을 나타낸다. CCC.. 2024. 5. 25. 다중 슈팅방법 (Multiple Shooting Method) 예제 Ascher의 책 'Computer Methods for Ordinary Dierential Equations and Dierential-Algebraic Equations' 에 나와 있는 예제를 다중 슈팅방법(multiple shooting method)을 이용하여 풀어보고자 한다. 미분방정식은 다음과 같다. \[ \begin{align} \dot{\mathbf{x}} = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ -2 \lambda^3 & \lambda^2 & 2 \lambda \end{bmatrix} \mathbf{x}+ \begin{bmatrix} 0 \\ 0 \\ q(t) \end{bmatrix} \tag{1} \end{align} \] 여기서 \(\math.. 2024. 5. 14. 감시정찰 (Surveillance and Reconnaissance) 영역 계산 한국군 최초의 정찰위성 1호가 2023년 12월 2일 발사에 성공하였다. 2024년에는 정찰위성 2호부터 4호까지 차례로 발사될 예정이라고 한다. 최근에는 전통적인 군사 영역은 물론이고 민간 영역에서도 우주 자산을 이용한 감시 및 정찰 활동이 빠르게 증가하고 있다. 참고로 감시(surveillance)와 정찰(reconnaissance)은 모두 정보 수집을 위한 활동이지만 시간과 임무의 구체성에서 차이가 있다. 감시는 주로 장기적으로 특정 지역이나 대상을 모니터링하여 정보를 수집하는 과정이다. 예를 들어 군사적인 목적으로 특정 지역을 지속적으로 관찰하는 것이 여기에 해당한다. 정찰은 일반적으로 특정 목적을 위한 한시적이고 전략적인 정보 수집에 중점을 둔다. 예를 들어 새로운 또는 알려지지 않은 지역의 상.. 2023. 12. 26. 이전 1 2 다음
