7.154 다중 목적 경로 최적화와 파레토 최적해

1. 다중 목적 최적화의 정의

다중 목적 최적화(multi-objective optimization)는 두 개 이상의 목적 함수를 동시에 최적화하는 문제이다.

$\min_{\mathbf{x} \in \mathcal{F}} \quad \mathbf{f}(\mathbf{x}) = [f_1(\mathbf{x}), f_2(\mathbf{x}), \ldots, f_k(\mathbf{x})]^T$

일반적으로 $k$ 개의 목적 함수를 동시에 최소화하는 단일 해는 존재하지 않으며, 목적 함수들 사이에 상충 관계(trade-off)가 존재한다.

2. 파레토 최적성

2.1 파레토 지배(Pareto Dominance)

해 $\mathbf{x}^1$ 이 해 $\mathbf{x}^2$ 를 파레토 지배한다는 것은, 모든 목적에서 $\mathbf{x}^1$ 이 $\mathbf{x}^2$ 보다 나쁘지 않고, 적어도 하나의 목적에서 엄격히 나은 경우이다.

$f_i(\mathbf{x}^1) \leq f_i(\mathbf{x}^2), \; \forall i \quad \text{and} \quad \exists j : f_j(\mathbf{x}^1) < f_j(\mathbf{x}^2)$

2.2 파레토 최적해

어떤 다른 허용 해에 의해서도 파레토 지배되지 않는 해를 파레토 최적(Pareto optimal)이라 한다. 파레토 최적해의 집합을 파레토 집합(Pareto set)이라 하고, 목적 함수 공간에서의 상을 파레토 전선(Pareto front)이라 한다.

파레토 전선 위의 모든 점은 어떤 목적 함수를 개선하려면 반드시 다른 목적 함수를 악화시켜야 하는 상충 관계를 나타낸다.

3. 로봇 경로 계획에서의 다중 목적

3.1 전형적 목적 함수 쌍

시간 vs. 에너지: 빠른 이동은 큰 가속을 요구하여 에너지 소비가 증가한다.

경로 길이 vs. 안전성: 최단 경로는 장애물에 가까이 지나갈 수 있어 안전 마진이 줄어든다.

매끄러움 vs. 시간: 매끄러운 궤적은 급격한 가감속을 회피하지만 이동 시간이 증가한다.

정밀도 vs. 속도: 작업 정밀도를 높이면 이동 속도를 줄여야 한다.

4. 해법 접근

4.1 가중 합법(Weighted Sum Method)

다수의 목적을 단일 스칼라 비용으로 결합한다.

$\min_{\mathbf{x}} \quad \sum_{i=1}^{k} w_i f_i(\mathbf{x}), \quad w_i \geq 0, \; \sum w_i = 1$

가중치 $\mathbf{w}$ 를 변화시키면서 반복적으로 풀면 파레토 전선의 다양한 점을 산출할 수 있다. 장점은 단일 목적 최적화로 환원된다는 점이며, 단점은 비볼록 파레토 전선의 오목 부분을 탐색하지 못한다는 점이다.

4.2 $\epsilon$ -제약법( $\epsilon$ -Constraint Method)

하나의 목적을 최적화하고, 나머지 목적에 상한 제약을 부과한다.

$\min_{\mathbf{x}} \quad f_1(\mathbf{x}) \quad \text{s.t.} \quad f_i(\mathbf{x}) \leq \epsilon_i, \; i = 2, \ldots, k$

$\epsilon_i$ 를 체계적으로 변화시키면 파레토 전선을 균일하게 샘플링할 수 있다. 비볼록 파레토 전선도 탐색 가능하다.

4.3 진화적 다목적 최적화

NSGA-II, MOEA/D 등의 진화 알고리즘이 모집단 기반 탐색으로 파레토 전선의 다양한 해를 동시에 산출한다. 단일 실행으로 파레토 전선의 근사를 얻을 수 있으며, 비볼록·비연속 파레토 전선에도 적용 가능하다.

5. 경로 계획에서의 파레토 분석

5.1 시간-에너지 파레토 전선

로봇 궤적의 시간-에너지 파레토 전선은 최소 시간 궤적(최대 가속, 최대 에너지)에서 최소 에너지 궤적(느린 등속, 최소 가속)까지의 연속적 상충을 나타낸다. 설계자는 파레토 전선을 시각화하여 응용에 적합한 상충점을 선택한다.

5.2 안전-효율 파레토 전선

장애물로부터의 최소 거리(안전성)와 경로 길이(효율)의 파레토 분석이 자율 주행 경로 계획에서 수행된다. 안전 마진을 지나치게 크게 설정하면 경로가 비효율적으로 길어지고, 마진을 줄이면 충돌 위험이 증가하는 상충 관계를 정량적으로 분석한다.

6. 사후 의사 결정

파레토 전선이 산출된 후, 최종 해의 선택은 설계자의 선호(preference)에 의해 결정된다.

무릎점(Knee Point): 파레토 전선에서 곡률이 가장 큰 점으로, 목적 함수 간의 교환 비율(exchange rate)이 급변하는 지점이다. 실용적으로 양호한 절충점으로 간주된다.

사전 우선순위: 안전이 최우선인 경우, 안전 제약을 만족하는 해 중에서 효율을 최적화하는 사전순위적(lexicographic) 접근이 사용된다.

7. 참고 문헌

Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.” IEEE Transactions on Evolutionary Computation, 6(2), 182–197.
Miettinen, K. (1999). Nonlinear Multiobjective Optimization. Springer.
Ehrgott, M. (2005). Multicriteria Optimization (2nd ed.). Springer.

version: 1.0