근사 해법과 휴리스틱 알고리즘

정수계획법 및 혼합 정수계획법에서 완벽한 해를 찾는 것은 NP-난해한 문제로 분류되며, 해결 시간과 자원의 소모가 매우 크기 때문에 현실적으로 불가능할 수 있다. 따라서 근사 해법과 휴리스틱 알고리즘은 효율적인 계산 시간 내에 만족스러운 해를 얻기 위한 중요한 방법이다.

근사 해법

근사 해법은 정확한 해를 찾지 않고, 시간 복잡도를 줄이기 위해 최적해에 가까운 해를 찾아내는 방법론이다. 이러한 해법은 보통 다음과 같은 성질을 갖는다.

최적해에 대한 근사도 보장
계산 효율성 (주로 다항 시간 복잡도)
시간 내에 문제 해결이 가능함

정수계획법에서 근사 해법은 다양한 기법들이 적용되며, 일반적으로 특정 문제 유형에 맞추어 설계된다. 근사 해법 중에서는 그리디 알고리즘, 라그랑지안 이완 기법, 유전자 알고리즘 등이 있다.

그리디 알고리즘

그리디 알고리즘은 문제 해결을 위해 각 단계에서 최선의 선택을 하는 방식으로, 최적해에 가까운 해를 찾는다. 이는 각 단계에서 가장 이익이 크거나, 손해가 적은 선택을 연속적으로 수행하여 전체 문제를 해결한다. 그리디 알고리즘의 예시로는 다음과 같은 경우를 생각할 수 있다.

주어진 정수계획 문제:

$\text{maximize} \quad \mathbf{c}^\top \mathbf{x}$

$\text{subject to} \quad \mathbf{A} \mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \in \mathbb{Z}^{n}_{+}$

이때, 각 단계에서 $\mathbf{x}$ 의 각 요소를 결정할 때마다 이득이 가장 큰 요소를 먼저 선택하는 방식이다. 이러한 방식은 일반적으로 최적해를 보장하지는 않지만, 매우 빠른 시간 안에 근사해를 도출할 수 있다.

라그랑지안 이완 기법

라그랑지안 이완(Lagrangian Relaxation)은 제약 조건을 목적 함수에 포함시켜 제약 조건을 완화시키는 기법이다. 이는 라그랑지 승수를 활용하여 제약 조건을 만족시키는 문제를 풀기가 어렵거나 시간이 오래 걸릴 때 사용된다. 문제를 다음과 같이 변환한다.

$\mathcal{L}(\mathbf{x}, \lambda) = \mathbf{c}^\top \mathbf{x} + \lambda^\top (\mathbf{b} - \mathbf{A} \mathbf{x})$

여기서 $\lambda$ 는 라그랑지 승수이며, 이 함수를 최대화시키는 $\mathbf{x}$ 를 찾아낸다. 이 기법은 원래의 제약 조건을 완화시킨 문제를 풀기 때문에 해를 더 쉽게 도출할 수 있지만, 최적해와의 거리를 측정하는 것이 필요하다.

유전자 알고리즘

유전자 알고리즘(Genetic Algorithm, GA)은 자연 선택과 유전적 진화를 모방한 휴리스틱 기법으로, 주로 비선형 최적화 문제를 해결하는 데 사용된다. 하지만 정수계획법에도 적용이 가능하며, 해 집합을 ‘개체’로 보고 이들 개체들이 유전적 교차, 돌연변이 등의 연산을 통해 새로운 세대를 만들어내며 점차 최적해에 가까워지도록 한다.

유전자 알고리즘은 다음의 절차를 따른다.

초기 집단 생성: 해를 표현하는 여러 개체(해 집합)를 무작위로 생성한다.
적합도 평가: 각 개체에 대해 목적 함수 값을 계산하여 그 적합도를 평가한다.
선택(Selection): 적합도가 높은 개체들을 선택하여 교배(parent selection)를 진행한다.
교차(Crossover): 선택된 부모 개체들 사이에서 교차 연산을 통해 새로운 개체를 생성한다.
돌연변이(Mutation): 일정 확률로 새로운 개체에 돌연변이 연산을 적용하여 해 집합에 다양성을 부여한다.
세대 교체: 새로운 세대로 교체하며 적합도가 높은 개체들이 계속해서 선택될 확률을 높인다.
종료 조건: 일정 세대가 지난 후, 또는 적합도가 충분히 높은 해가 나타나면 알고리즘을 종료한다.

정수계획 문제에 유전자 알고리즘을 적용할 경우, 해를 표현하는 개체는 정수로 구성된 벡터 형태를 갖는다. 예를 들어, 문제의 해가 $\mathbf{x} \in \mathbb{Z}^{n}_{+}$ 로 표현된다면, 각 개체는 다음과 같은 형태이다.

$\mathbf{x}^{(i)} = (x_1^{(i)}, x_2^{(i)}, \dots, x_n^{(i)})$

여기서 $i$ 는 개체의 인덱스를 나타낸다. 각 세대마다 이 개체들의 적합도가 높아지면서 최적해에 가까워지게 된다.

근사 해법의 평가

근사 해법은 일반적으로 다음과 같은 측면에서 평가된다.

근사 비율: 근사 해법이 최적해에 얼마나 가까운지를 평가하는 지표이다. 이는 다음과 같이 정의된다.

$\text{근사 비율 } = \frac{f(\mathbf{x}_{\text{근사}})}{f(\mathbf{x}_{\text{최적}})}$

여기서 $f(\mathbf{x}_{\text{근사}})$ 는 근사 해법으로 얻은 해의 목적 함수 값, $f(\mathbf{x}_{\text{최적}})$ 은 최적해의 목적 함수 값이다.

시간 복잡도: 알고리즘이 문제를 푸는 데 걸리는 시간을 분석하는 것으로, 일반적으로 다항 시간 내에 동작하는지 평가한다.
공간 복잡도: 알고리즘이 사용하는 메모리의 양을 평가하는 지표이다.

근사 해법은 이러한 평가를 통해 문제의 크기와 복잡도에 따라 적절히 선택되어야 한다.

휴리스틱 알고리즘

휴리스틱 알고리즘은 경험적 규칙이나 직관에 기반하여 해를 도출하는 방법으로, 문제의 구조나 성질을 이용하여 가능한 한 빠르게 만족할 만한 해를 구하는 방식이다. 이 방식은 보통 최적해를 보장하지는 않지만, 계산 효율성이 매우 높다.

휴리스틱 알고리즘의 몇 가지 주요 유형을 살펴보면 다음과 같다.

탐욕적 휴리스틱

탐욕적 알고리즘은 각 단계에서 가장 좋은 선택을 하며, 이를 반복하여 전체 문제를 해결한다. 탐욕적 휴리스틱은 일부 문제에서 최적해를 보장하지 않더라도 매우 효율적인 해법을 제공한다.

예를 들어, 특정 정수계획 문제에서 탐욕적 휴리스틱을 적용하는 경우, 가장 높은 가치를 가진 아이템부터 선택하거나, 비용 대비 효율성이 가장 높은 선택을 연속적으로 진행할 수 있다.

탐사 기반 휴리스틱

탐사 기반 휴리스틱(Exploration-based heuristic)은 문제의 해를 찾기 위해 다양한 방향으로 해를 탐사하는 방식이다. 탐사 기반 알고리즘은 주로 다음과 같은 기법들을 포함한다.

탐욕적 탐사: 문제의 해를 계속해서 발전시키는 방식
무작위 탐사: 해의 공간을 무작위로 탐사하여 해결책을 찾는 방식

이런 방법들은 주로 큰 해 공간을 가진 문제에 적합한다.

메타 휴리스틱 (Metaheuristic)

메타 휴리스틱은 보다 넓은 범위에서 최적화를 탐색하는 알고리즘으로, 전역 최적화를 목표로 한다. 이는 지역 최적화에 빠지지 않도록 설계되어 있어 복잡한 최적화 문제에서 자주 사용된다. 대표적인 메타 휴리스틱 방법으로는 모의 담금질(Simulated Annealing), 탐색 알고리즘(Search Algorithm), 유전자 알고리즘(Genetic Algorithm) 등이 있다.

모의 담금질(Simulated Annealing)

모의 담금질은 금속을 서서히 냉각하는 물리적 공정을 모방하여 최적화를 수행하는 방법이다. 이 알고리즘은 초기 해로부터 출발해, 서서히 온도를 낮추면서 더 나은 해를 찾도록 설계되었다. 이 과정에서 새로운 해를 탐색할 때, 무작위로 선택된 해가 현재 해보다 나쁠 경우에도 일정 확률로 그 해를 채택할 수 있으며, 이를 통해 지역 최적화에서 벗어나 전역 최적화를 추구한다.

초기화: 초기 해 $\mathbf{x}_0$ 와 초기 온도 $T_0$ 를 설정한다.
반복: 다음 절차를 온도가 충분히 낮아질 때까지 반복한다.
이웃 해 탐색: 현재 해의 이웃 해 $\mathbf{x}'$ 를 무작위로 선택한다.
수용 여부 결정: 새로운 해가 더 나은 경우 채택한다. 그렇지 않은 경우, 확률적으로 나쁜 해도 채택할 수 있다. 그 확률은 다음과 같이 주어진다.

$P = \exp\left( \frac{f(\mathbf{x}) - f(\mathbf{x}')}{T} \right)$

여기서 $f(\mathbf{x})$ 는 해의 목적 함수 값이고, $T$ 는 현재 온도를 나타낸다.

온도 감소: 온도를 점차 낮추어가며 탐색을 제한한다. 온도 감소는 보통 다음과 같은 방식으로 수행된다.

$T_{k+1} = \alpha T_k, \quad 0 < \alpha < 1$

이 방법은 계산 시간이 길지만, 전역 최적화를 찾아내는 데 효과적일 수 있다.

금단 탐색 (Tabu Search)

금단 탐색(Taboo Search)은 탐색 과정에서 이미 방문했던 해를 기억하여 다시 탐색하지 않도록 금지하는 방법이다. 이 과정은 지역 최적화에 빠지는 것을 방지하고, 해를 넓게 탐사할 수 있게 한다. 금단 탐색의 주요 절차는 다음과 같다.

초기화: 초기 해 $\mathbf{x}_0$ 와 금단 목록을 초기화한다.
탐색: 현재 해의 이웃 해들 중에서 최적의 해를 찾는다.
해 갱신: 새로운 해를 현재 해로 설정하고, 금단 목록에 현재 해를 추가하여 다시 선택되지 않도록 한다.
반복: 최적해를 찾거나 종료 조건을 만족할 때까지 반복한다.

금단 탐색의 핵심은 금단 목록을 사용해 해의 중복 선택을 방지함으로써, 보다 다양한 해를 탐색할 수 있도록 돕는 것이다. 이 방법은 복잡한 문제에서 빠른 시간 안에 좋은 해를 찾을 수 있는 효과적인 방식으로 사용된다.

파티클 스웜 최적화 (Particle Swarm Optimization, PSO)

PSO는 자연에서 벌이나 물고기 무리의 행동을 모방한 알고리즘으로, 각 개체(입자)가 해 공간에서 탐색하면서 상호작용을 통해 최적해를 찾는 방법이다. PSO는 주로 연속 최적화 문제에서 사용되지만, 정수계획 문제에도 확장될 수 있다.

PSO의 절차는 다음과 같다.

초기화: 각 입자들의 위치 $\mathbf{x}_i$ 와 속도 $\mathbf{v}_i$ 를 무작위로 설정한다.
적합도 평가: 각 입자의 적합도를 평가하여, 그 중 최적의 위치 $\mathbf{x}_{\text{best}}$ 를 기억한다.
속도 및 위치 업데이트: 각 입자의 속도와 위치는 다음과 같이 업데이트된다.

$\mathbf{v}_i(t+1) = w \mathbf{v}_i(t) + c_1 r_1 (\mathbf{p}_i - \mathbf{x}_i(t)) + c_2 r_2 (\mathbf{g} - \mathbf{x}_i(t))$

$\mathbf{x}_i(t+1) = \mathbf{x}_i(t) + \mathbf{v}_i(t+1)$

여기서 $w$ 는 관성 계수, $c_1, c_2$ 는 가속 계수, $r_1, r_2$ 는 무작위 값이며, $\mathbf{p}_i$ 는 입자 $i$ 의 최적 위치, $\mathbf{g}$ 는 전체 군집의 최적 위치이다.

이와 같은 과정은 전체 입자들이 최적의 해를 찾아갈 때까지 반복된다.

휴리스틱 알고리즘의 평가

휴리스틱 알고리즘은 일반적으로 다음과 같은 측면에서 평가된다.

해의 질: 최적해와 비교했을 때 얼마나 근접한가를 평가한다.
계산 시간: 알고리즘이 실행되는 시간을 평가한다. 휴리스틱 알고리즘은 보통 시간 복잡도가 낮아 빠르게 해를 도출한다.
유연성: 문제 유형에 따라 다양한 형태로 변형 가능성을 평가한다.

이러한 평가를 통해 각 휴리스틱 방법은 문제의 특성에 맞게 선택된다.