397.53 파레토 최적성(Pareto Optimality)과 해 선택

1. 개요

파레토 최적성(Pareto optimality)은 다목적 최적화(multi-objective optimization)에서 해의 품질을 평가하는 핵심적 개념으로서, 어떤 목적도 다른 목적의 성능을 저하시키지 않고서는 더 이상 개선할 수 없는 상태를 의미한다. 로봇 임무 계획에서 복수의 상충하는 목적(이동 시간, 에너지 소모, 위험 노출 등)을 동시에 고려할 때, 파레토 최적성은 비교 불가능한(incomparable) 해 집합을 체계적으로 정의하고, 의사 결정자(운영자)가 합리적으로 해를 선택할 수 있는 이론적 기반을 제공한다.

파레토 개념은 경제학자 Vilfredo Pareto(1896)에 의해 최초로 도입되었으며, 이후 공학 최적화, 게임 이론, 사회 선택 이론 등 다양한 분야로 확장되었다. 로봇 임무 계획에서는 파레토 최적 해 집합의 구조를 분석하고, 운영 상황에 적합한 단일 해를 선택하는 의사 결정 프로세스가 필수적이다.

2. 수학적 정의와 기본 개념

2.1 지배 관계(Dominance Relation)

k개의 목적 함수 f_1, f_2, \ldots, f_k를 최소화하는 다목적 최적화 문제에서, 두 실행 가능 해 \mathbf{x}_1, \mathbf{x}_2 \in \mathcal{X} 사이의 지배 관계는 다음과 같이 정의된다.

지배(Dominance): \mathbf{x}_1이 \mathbf{x}_2를 지배한다(\mathbf{x}_1 \prec \mathbf{x}_2)는 것은 다음과 동치이다:

\forall i \in \{1, \ldots, k\} : f_i(\mathbf{x}_1) \leq f_i(\mathbf{x}_2) \quad \wedge \quad \exists j \in \{1, \ldots, k\} : f_j(\mathbf{x}_1) < f_j(\mathbf{x}_2)

약 지배(Weak dominance): \mathbf{x}_1이 \mathbf{x}_2를 약 지배한다(\mathbf{x}_1 \preceq \mathbf{x}_2)는 것은 모든 목적에서 \mathbf{x}_1이 \mathbf{x}_2 이하의 값을 가짐을 의미한다:

\forall i \in \{1, \ldots, k\} : f_i(\mathbf{x}_1) \leq f_i(\mathbf{x}_2)

비지배(Non-dominance): \mathbf{x}_1과 \mathbf{x}_2가 상호 비지배적이라 함은 \mathbf{x}_1 \nprec \mathbf{x}_2이고 \mathbf{x}_2 \nprec \mathbf{x}_1인 경우이다. 이러한 두 해는 비교 불가능(incomparable)하다.

2.2 파레토 최적성의 정의

해 \mathbf{x}^* \in \mathcal{X}가 파레토 최적(Pareto-optimal)이라 함은, \mathbf{x}^*를 지배하는 다른 실행 가능 해가 실행 가능 영역 내에 존재하지 않음을 의미한다:

\nexists \mathbf{x} \in \mathcal{X} : \mathbf{x} \prec \mathbf{x}^*

2.3 파레토 집합과 파레토 전선

파레토 집합(Pareto set) \mathcal{P}_S는 결정 공간(decision space)에서의 모든 파레토 최적 해의 집합이다:

\mathcal{P}_S = \{\mathbf{x}^* \in \mathcal{X} \mid \nexists \mathbf{x} \in \mathcal{X} : \mathbf{x} \prec \mathbf{x}^*\}

파레토 전선(Pareto front) \mathcal{P}_F는 목적 공간(objective space)에 투영된 파레토 집합이다:

\mathcal{P}_F = \{\mathbf{f}(\mathbf{x}^*) \mid \mathbf{x}^* \in \mathcal{P}_S\}

파레토 전선은 k-차원 목적 공간에서 비열등 해들이 형성하는 경계면이며, 의사 결정자가 해를 선택하는 탐색 대상이 된다.

2.4 파레토 전선의 형상 유형

파레토 전선의 기하학적 형상은 문제의 특성을 반영한다:

• 볼록(Convex) 전선: 목적 함수 간 상충이 크고 균형적인 경우 나타난다. 가중합 방법으로 전체 전선의 탐색이 가능하다.
• 비볼록(Non-convex) 전선: 일부 영역에서 급격한 상충이 존재하는 경우 나타난다. 가중합 방법으로는 비볼록 영역의 해를 도출할 수 없다.
• 불연속(Discontinuous) 전선: 실행 가능 영역의 제약으로 인해 전선이 연결되지 않는 경우 발생한다.
• 퇴화(Degenerate) 전선: 일부 목적 함수가 사실상 독립적이지 않아 전선의 차원이 줄어드는 경우이다.

3. 약화된 파레토 최적성 개념

3.1 ε-파레토 최적성

정확한 파레토 최적 해를 구하는 것이 계산적으로 어려운 경우, ε-근사 파레토 최적성(ε-approximate Pareto optimality)이 사용된다. 해 \mathbf{x}가 ε-파레토 최적이라 함은, 모든 목적에서 \mathbf{x}보다 (1 + \epsilon) 비율 이상 개선하는 해가 존재하지 않음이다:

\nexists \mathbf{x}' \in \mathcal{X} : \forall i, f_i(\mathbf{x}') \leq \frac{f_i(\mathbf{x})}{1+\epsilon}

ε-파레토 전선은 원래 파레토 전선의 근사이며, 적절한 ε 선택을 통해 해 집합의 크기를 유한하게 제한할 수 있다. Papadimitriou와 Yannakakis(2000)는 이산 다목적 문제에서 다항 크기의 ε-파레토 전선이 항상 존재함을 증명하였다.

3.2 약 파레토 최적성

약 파레토 최적(weakly Pareto-optimal) 해 \mathbf{x}^*는 모든 목적을 동시에 엄격히 개선하는 해가 존재하지 않는 경우이다:

\nexists \mathbf{x} \in \mathcal{X} : \forall i, f_i(\mathbf{x}) < f_i(\mathbf{x}^*)

약 파레토 최적 해 집합은 파레토 최적 해 집합을 포함하며 더 넓다.

4. 로봇 임무 계획에서의 파레토 해 탐색

4.1 정확 알고리즘

소규모 문제에서는 정확한 파레토 전선을 완전히 열거할 수 있다. 이산 조합 최적화 문제에서의 대표적 정확 알고리즘은 다음과 같다:

1. 다목적 라벨링 알고리즘: 단일 출발점 최단 경로의 다목적 확장으로, 각 노드에 비지배 라벨(non-dominated label)의 집합을 유지하며 전파한다. 2-목적 최단 경로 문제에서 파레토 최적 경로의 수가 지수적으로 증가할 수 있으므로, 최악 시간 복잡도는 의사다항 시간(pseudo-polynomial time)이다.

2. 다목적 동적 계획법: Bellman 원리의 다목적 일반화로, 각 부분 문제에 대해 비지배 해의 집합을 유지한다.

4.2 메타휴리스틱 알고리즘

대규모 문제에서는 메타휴리스틱(metaheuristic) 접근법을 통해 파레토 전선의 근사 집합을 탐색한다:

• NSGA-II: 비지배 정렬과 군집 거리(crowding distance)를 기반으로 파레토 전선의 균일한 분포를 추구한다(Deb et al., 2002).
• NSGA-III: 참조점(reference point) 기반 선택을 도입하여 다수(3개 이상)의 목적 함수를 가지는 문제에 적합하다(Deb, Jain, 2014).
• MOEA/D: 분해 기반 접근으로, 각 가중 벡터에 대응하는 부분 문제를 이웃 해의 정보를 활용하여 풀어낸다(Zhang, Li, 2007).
• SPEA2: 강도 파레토 진화 알고리즘(Strength Pareto Evolutionary Algorithm 2)으로, 외부 보관소(archive)에 비지배 해를 유지하며 밀도 기반 선택을 수행한다(Zitzler, Laumanns, Thiele, 2001).

4.3 형식 명세 하의 파레토 경로

LTL 임무 명세를 만족하는 래소(lasso) 경로 중 파레토 최적 경로를 탐색하는 문제에서는, 제품 오토마톤 위에서의 다목적 경로 탐색이 수행된다. 접두사 비용 벡터 \mathbf{c}_{\text{prefix}}와 주기 비용 벡터 \mathbf{c}_{\text{cycle}}을 정의하고, 결합 비용 벡터에 대한 파레토 전선을 도출한다.

5. 해 선택 기법

5.1 이상점 기반 거리 최소화

이상점(utopia point) \mathbf{z}^*는 각 목적의 개별 최적값으로 구성된 점이다:

\mathbf{z}^* = \left( \min_{\mathbf{x}} f_1(\mathbf{x}), \min_{\mathbf{x}} f_2(\mathbf{x}), \ldots, \min_{\mathbf{x}} f_k(\mathbf{x}) \right)

이상점은 일반적으로 실행 가능하지 않으나, 모든 파레토 최적 해가 추구하는 이상적 목표를 나타낸다. 이상점으로부터의 거리를 최소화하는 해를 타협 해(compromise solution)로 선택한다:

\mathbf{x}^* = \arg\min_{\mathbf{x} \in \mathcal{P}_S} \left\| \mathbf{f}(\mathbf{x}) - \mathbf{z}^* \right\|_p

여기서 p-노름의 선택에 따라 서로 다른 해가 선택된다. p = 2이면 유클리드 최소 거리 해, p = \infty이면 체비셰프 해가 된다.

5.2 나디르점과 정규화

나디르점(nadir point) \mathbf{z}^{\text{nad}}는 파레토 전선의 각 목적에 대한 최악값으로 구성된다:

z_i^{\text{nad}} = \max_{\mathbf{x} \in \mathcal{P}_S} f_i(\mathbf{x})

이상점과 나디르점을 활용한 목적 함수의 정규화(normalization)는 목적 함수 간 스케일 차이를 보정하여 공정한 비교를 가능하게 한다:

\bar{f}_i(\mathbf{x}) = \frac{f_i(\mathbf{x}) - z_i^*}{z_i^{\text{nad}} - z_i^*}

5.3 무릎점(Knee Point) 선택

무릎점(knee point)은 파레토 전선에서 곡률(curvature)이 최대인 지점으로, 하나의 목적에서 소량의 양보로 다른 목적에서 대폭의 개선을 얻을 수 있는 최적의 균형점을 나타낸다.

2-목적 문제에서 무릎점은 파레토 전선 상의 점 \mathbf{f}(\mathbf{x})에서 이상점과 나디르점을 연결하는 직선까지의 수직 거리가 최대인 점으로 식별된다. Branke, Deb, Dierolf(2004)는 다목적 진화 알고리즘에서 무릎 영역을 자동으로 식별하는 방법을 제안하였다.

5.4 TOPSIS 방법

TOPSIS(Technique for Order of Preference by Similarity to Ideal Solution)는 이상점에의 유사성에 기반한 다기준 의사 결정 방법이다(Hwang, Yoon, 1981). 각 대안(파레토 해)에 대해 이상적 해로의 유클리드 거리 d_i^+와 반이상적 해(나디르점)로의 유클리드 거리 d_i^-를 계산하고, 상대적 근접도(relative closeness) C_i를 산출한다:

C_i = \frac{d_i^-}{d_i^+ + d_i^-}, \quad C_i \in [0, 1]

C_i가 1에 가까울수록 이상적 해에 근접한 것이며, 최대 C_i를 갖는 해를 최종 선택한다.

5.5 AHP(Analytic Hierarchy Process)

AHP는 Saaty(1980)가 제안한 계층적 의사 결정 방법으로, 운영자가 목적 함수 쌍에 대한 상대적 중요도를 쌍대 비교(pairwise comparison) 행렬로 제시하면, 고유벡터(eigenvector) 분석을 통해 가중치 벡터를 도출한다. 도출된 가중치를 가중합 방법에 적용하여 최종 해를 선택한다.

AHP의 장점은 운영자의 주관적 선호를 체계적으로 정량화할 수 있다는 것이며, 한계는 쌍대 비교의 일관성(consistency) 확보가 어려울 수 있다는 것이다.

6. 로봇 임무 계획에서의 해 선택 전략

6.1 실시간 해 선택

동적 환경에서 로봇이 실시간으로 해를 선택해야 하는 경우, 사전 계산된 파레토 전선으로부터 현재 임무 상황에 적합한 해를 신속히 검색하는 메커니즘이 필요하다. 주요 접근법은 다음과 같다:

1. 상태 기반 가중치 전환: 현재 배터리 잔량, 위험 수준, 긴급도 등의 상태 변수에 따라 목적 함수의 가중치를 실시간으로 조정하여 해를 재선택한다.
2. 참조점 갱신: 임무 진행에 따라 이상점이나 참조점을 갱신하고, 갱신된 참조점에 가장 근접한 파레토 해를 선택한다.
3. 운영자 인터페이스: 파레토 전선을 시각적으로 제시하고 운영자가 상호작용적으로 해를 선택하는 인간-로봇 협력 방식이다.

6.2 파레토 해의 품질 지표

MOOP 알고리즘이 산출한 근사 파레토 전선의 품질을 평가하는 대표적 지표는 다음과 같다:

초부피(hypervolume) 지표는 파레토 전선의 수렴성과 다양성을 동시에 측정하는 유일한 단항 지표로서, 가장 널리 사용된다(Zitzler, Thiele, 1998).

7. 참고 문헌

• Pareto, V. (1896). Cours d’Économie Politique. F. Rouge, Lausanne.
• Saaty, T.L. (1980). The Analytic Hierarchy Process. McGraw-Hill.
• Hwang, C.L., Yoon, K. (1981). Multiple Attribute Decision Making: Methods and Applications. Springer-Verlag.
• Zitzler, E., Thiele, L. (1998). “Multiobjective Optimization Using Evolutionary Algorithms — A Comparative Case Study.” Proceedings of PPSN V, LNCS, vol. 1498, pp. 292–301.
• Papadimitriou, C.H., Yannakakis, M. (2000). “On the Approximability of Trade-offs and Optimal Access of Web Sources.” Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pp. 86–92.
• Zitzler, E., Laumanns, M., Thiele, L. (2001). “SPEA2: Improving the Strength Pareto Evolutionary Algorithm.” TIK-Report 103, ETH Zurich.
• 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), pp. 182–197.
• Branke, J., Deb, K., Dierolf, H. (2004). “Finding Knees in Multi-Objective Optimization.” Proceedings of PPSN VIII, LNCS, vol. 3242, pp. 722–731.
• Zhang, Q., Li, H. (2007). “MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition.” IEEE Transactions on Evolutionary Computation, 11(6), pp. 712–731.
• Deb, K., Jain, H. (2014). “An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems with Box Constraints.” IEEE Transactions on Evolutionary Computation, 18(4), pp. 577–601.

버전: 2026-03-24
출처: Robotics Engineering 서적, Volume 9, Part 53, Chapter 397