Multi-Objective 최적화 (2) - NSGA-2

Multi-Objective 최적화 (1) - 파레토 (pareto) 최적

---

 

Multi-Objective 최적화는 결국 전체 solution 중에 파레토 최적인 solution 집합을 찾는 문제입니다. 먼저 문제를 단순화하여 여러 개의 목적을 하나의 목적으로 단순화하는 방법은 없을까요? 지난 포스트에서 봤던 일반적인 최적화 수식을 생각해 본다면 다음처럼 1) 특정한 목적 함수만 남기고 나머지 목적 함수를 constaint 조건으로 보내거나 ($\epsilon$ constrained), 2) 여러 목적 함수의 가중치 합으로 하나의 목적 함수로 표현하는 것이 가능하겠죠. (weighted sum) 

하지만 이 방법들의 문제점은 각 목적 함수 별로의 가중치 $w_m$나 제한 조건 $\epsilon$을 정하기 쉽지 않다는 데 있습니다. 이번 포스트에서 다룰 내용은 Multi-Objective 최적화에서 가장 대표적인 알고리즘인 NSGA-2 (Non-Dominated Sorting Genetic Algorithm)입니다.

 

Non-Dominated Sorting Genetic Algorithm

Non-domiated

먼저 연봉과 키가 높거나 클수록 좋은 상황에서 어떤 사람이 파레토 최적해가 될까요? C는 A, B에 비해서 키, 연봉 모두 작으므로 A, B에 의해 파레토 열위를 당하고 D는 C에게조차 파레토 열위를 당하는 상황입니다. 하지만 A는 B보다 키가 크지만 연봉이 낮고 B는 A보다 키는 작지만 연봉이 높습니다. 즉, 누구에게도 열위를 당하지 않으면서 서로 비교가 불가능한 파레토 최적해가 됩니다. 즉, "Non-dominated"입니다.

$n_p$, $S_p$

파레토 최적해끼리는 비교가 불가능하지만 파레토 비최적해끼리는 열위/우위 비교가 가능합니다. 따라서 모든 해마다 1) $n_p$:$p$ 샘플에 대해 파레토 우위를 점하는 샘플 수, 2) $S_p$: $p$ 샘플이 파레토 우위를 점하는 샘플 집합을 정의할 수 있습니다. 위의 예에서 A, B에 대해 우위를 점하는 샘플은 아무도 없으므로 A, B의 $n_p$는 0이 되고 C는 A, B가 해당되어 2, D는 A, B, C가 해당되어 3이 됩니다.

여기서 파레토 front level을 정의할 수 있는데, $n_p$를 정렬하여 가장 작은 $n_p$를 가진 (0) 샘플들은 파레토 front level 1에 할당됩니다. 그리고 순서대로 2, 3 level에 할당되죠. (이 개념에서부터 NSGA의 Non-domiated Sorting 이란 이름이 붙었습니다.)

Name	Height	Salary	$n_p$	$S_p$	Pareto front level
A	190	80K	0	C,D	1
B	170	85K	0	C,D	1
C	165	70K	2	D	2
D	160	22K	3	-	3

 

Non-dominated Sorting

NSGA 알고리즘은 먼저 모든 샘플에 대해 Non-dominated Sorting을 수행하여 각 샘플마다 $n_p, S_p$를 정하고 파레토 front level을 설정하는 것에서부터 출발합니다. 밑의 알고리즘에서처럼 먼저 각 샘플에 대해 $p$ 다른 모든 샘플 $q$와의 파레토 열위/우위 검사를 수행하고 (서로 비교가 불가능하면 skip 합니다.) $n_p=0$인 샘플에 대해 front level (rank) 1을 부여합니다. 

이 과정이 종료되면 모든 샘플마다 $n, S$가 정의되는데, 이후에는 front level이 같은 샘플끼리 모으는 작업이 필요합니다. 먼저 front level 1인 집합 ($F_1$) 의 원소를 순회하면서 다음 front level 집합 ($F_2$) 을 형성합니다. 이때 중요한 점은 $F_i$에서 뽑힌 $p$의 $S_p$에서 원소 $q$가 선택될 때 $n_q$값은 자신에 대해 우위를 점하는 샘플 $p$가 이미 level이 할당되었으므로 1이 빠진다는 점입니다. ($n_q=n_q-1$ 부분) 따라서 $n_q=0$이 되면 다음 front level 집합으로 할당됩니다.

Non-dominated Sorting

 

Crowding distance

위의 과정을 거쳐 파레토 front level 별로 샘플 sorting이 완료되었으면 front level이 가장 낮은 샘플을 추출하면 됩니다. 하지만 추출할 샘플 수는 정해져 있고 남아 있는 front level에 속한 샘플 수가 추출한 샘플 수보다 많다면 어떤 것을 뽑아야 할까요? NSGA-2 알고리즘에서는 목적 함숫값을 이용한 crowding distance를 사용합니다.

Crowding distance는 말 그대로 해당 샘플이 같은 파레토 front level에 속한 다른 샘플들과 위치를 비교했을 때 붐비는 곳에 있는지를 보는 지표입니다. 각 샘플 별로 목적 함숫값을 뽑아 정렬하고 각 목적 함수의 최소/최댓값을 이용하여 근처 샘플과 어느 정도 떨어져 있는지를 보는 것인데, 이 값이 ($cd(i)$)이 높을수록 클수록 근처 샘플과 멀리 떨어져 있다는 것이므로 최적화의 다양성을 위해 같은 front level이라면 $cd$값이 높은 샘플을 추출하게 됩니다. (또한, 경곗값들은 무한대가 assign 되었으므로 무조건 선택되겠죠. 경계이면 보통 근처 샘플과 멀리 떨어져 있을 확률이 높아서 그렇습니다.)

Crowding Distance

 

전체적인 흐름

NSGA-2 알고리즘을 정리하면 1) 각 샘플 별로 $n_p, S_p$를 정하고 파레토 front level로 그룹화하는 Non-dominated Sorting을 수행하고 2) 같은 front level 끼리 있으면 crowding distance를 계산해서 crowding distnace가 큰 샘플이 먼저 추출되도록 하는 과정을 거칩니다.

이를 그림으로 표현하면 다음과 같습니다. 먼저 $P_t$로부터 genetic algorithm의 mutation, selection, crossover를 이용하여 $Q_t$를 만들고 $P_t + Q_t$로부터 1) Non-dominated Sorting, 2) Crowding distance sorting을 수행하여 $P_{t+1}$ 집합을 만들게 되고 이 과정을 정해진 iteration 수 $T$만큼 반복합니다.

 

참조

• NSGA review paper

 

---

Multi-Objective 최적화 (3) - NSGA-3