서로 충돌하는 여러 목적함수(Objectives)를 동시에 고려할 때, 어느 하나의 목적을 개선하면 다른 목적이 반드시 악화되는 해들만을 남겨 최적해 집합을 구하는 방법
단일 최적해가 아니라 파레토 최적해 집합(Pareto optimal set)을 구하는 것이 특징
다목적 최적화(Multi-objective Optimization)의 가장 기본적인 개념
⭐ Pareto Optimality의 핵심 개념
✅ 1. 다목적 최적화 (Multi-objective Optimization)
두 개 이상 목적함수를 동시에 고려
예:
-
비용 최소화 + 서비스 수준 최대화
-
이동 거리 최소화 + 불균형 최소화
-
목적함수들은 일반적으로 서로 상충(trade-off) 관계
✅ 2. 파레토 지배 (Pareto Dominance)
해 A가 해 B를 파레토 지배한다는 의미:
모든 목적함수에서 A가 B보다 같거나 더 좋고 적어도 하나의 목적함수에서는 엄격히 더 좋음
📌 지배 관계 정의
A ≺ B ⇔
∀i, fᵢ(A) ≤ fᵢ(B) 이고
∃j, fⱼ(A) < fⱼ(B)
✅ 3. 파레토 최적해 (Pareto Optimal Solution)
-
어떤 다른 해에도 지배되지 않는 해
-
더 이상 “모든 목적에서 동시에 개선”할 수 없는 상태
→ 이런 해들의 집합을 Pareto Set이라 부름
✅ 4. 파레토 프론트 (Pareto Front)
-
목적함수 공간(objective space)에서 파레토 최적해들을 시각화한 경계선/곡면
-
의사결정자는 이 프론트 위에서 자신의 선호(preference)에 맞는 해를 선택
📌 Pareto Optimality의 절차
✅ 1. 목적함수 정의
최적화할 목적함수들을 명확히 정의
예:
f₁(x): 총 비용
f₂(x): 총 이동 거리
f₃(x): 불균형 페널티
✅ 2. 후보 해 생성
가능한 해(solution)들을 생성
방법:
완전 탐색
휴리스틱 / 메타휴리스틱
진화 알고리즘(NSGA-II 등)
✅ 3. 파레토 지배 관계 비교
-
모든 해 쌍에 대해 지배 여부 판단
-
지배되는 해 제거
✅ 4. 파레토 최적해 집합 추출
-
지배되지 않는 해들만 남김
-
결과는 하나의 해가 아닌 해 집합
❗ Pareto Optimality의 구현 방식
✅ 1. 완전 비교 방식 (Brute-force Pareto Filtering)
-
모든 해 쌍을 비교
-
시간복잡도: O(N²)
-
해 개수가 적을 때만 실용적
✅ 2. 메타휴리스틱 기반
-
NSGA-II, SPEA2, MOEA/D 등
-
대규모 문제에서 주로 사용
-
Pareto front를 점진적으로 근사
✅ 3. ε-constraint / 가중합과의 관계
-
Pareto method는 선호를 사전에 강제하지 않음
-
ε-constraint, weighted sum은:
-
Pareto 해 중 일부만 탐색
-
파라미터 설정에 따라 해가 달라짐
-
⚠️ Pareto Optimality의 장단점
✅ 장점
-
선호 독립적
-
의사결정자의 가중치 없이 해 집합 제공
-
Trade-off 구조 명확
-
목적 간 상충 관계를 직관적으로 파악 가능
-
의사결정 유연성
-
사후 선택(post-decision making) 가능
❌ 단점
-
해가 너무 많아질 수 있음
-
고차원 목적함수일수록 Pareto set 폭발
-
최종 선택은 여전히 사람의 몫
-
“어떤 해가 가장 좋은가?”는 자동으로 결정 불가
-
계산 비용
-
지배 비교 및 프론트 유지 비용 큼
📝 예제
🔹 다목적 문제 예시
해 비용(cost) ↓ 거리(distance) ↓
A 10 100
B 12 80
C 15 70
D 11 120🔹 파레토 분석
A vs D:
A는 비용↓, 거리↓ → A가 D 지배
A, B, C:
서로 한 목적씩 더 좋음 → 상호 비지배
📌 Pareto optimal set = {A, B, C}
📌 D는 제거됨
🔎 Pareto Optimality의 주요 활용 예시
✅ 1. 물류·운송 최적화
-
비용 최소화 vs 서비스 수준
-
이동 거리 vs 차량 불균형
✅ 2. 공공자전거 재배치 문제
-
총 이동거리 최소화
-
수요 불균형 최소화
-
작업 시간 제약 만족
→ 하나의 해가 아닌 Pareto front 제공 후 정책 선택
✅ 3. 공학 설계 문제
-
무게 vs 강도
-
비용 vs 성능
