다중 목표 진화 알고리즘(Multi-Objective Evolutionary Algorithm, MOEA)는 진화 알고리즘을 통해 다중 목표 최적화 문제를 푸는 기법들을 칭한다. 다중 목표 최적화 문제는 목표가 여러 개 존재하는 최적화 문제로, 지난 글에서는 단일목표 최적화 문제로 변환시켜서 푸는 가중 합과, 입실론-조건 기법들을 소개했다면, 이번 글에서는 진화 알고리즘을 통해 다중목표 최적화 문제를 푸는 기법을 소개할 것이다.
진화 알고리즘은 모집단(population)을 반복적으로 변이시키고 선택하여 문제 목표에 가까운 모집단을 반복적으로 얻는 기법이다. 진화생물학에서 생물이 진화될수록 주어진 환경에 적합한 개체가 된다는 아이디어가 적용된 알고리즘으로, 이론적으로 얼마나 잘 작동하는 지에 대해서는 별로 알려져있지는 못한 휴리스틱이지만 다양한 문제를 효과적으로 풀어왔다. 예를 들면, 퍼징(fuzzing)은 소프트웨어 테스팅을 할 때 대표적으로 광범위하게 사용되는 기법으로 이것 또한 진화 알고리즘에 의해 작동한다.
진화 알고리즘은 개략적으로 위 그림과 같이 작동한다. 초기 모집단(initial population)에서, 이들 중 일부를 골라서(Selection) 교차(Crossover)와 변이(Mutation)을 통해 새로운 자손을 만들고, 모집단에 넣는다. 그리고 모집단 전체에서 목표에서 먼 구성원은 제외하고 목표에 가까운 구성원만 남기기도 하는데, 이를 엘리트주의(elitism)이라고 한다. 그리고 다시 일부를 고르고, 변이를 시켜서 새로운 자손을 만들고, 모집단을 갱신한다. 이를 반복적으로 수행하면 전체 모집단이 목표에 점점 가까워지고, 충분히 많은 반복으로 좋은 모집단을 얻었을 때 반복을 종료하고 모집단을 반환한다. (진화 알고리즘은 잘 알려진 메타휴리스틱이니 다른 글을 서치해도 좋을 것이다)
진화 알고리즘은 이미 존재하는 모집단을 기본으로 새로운 자손을 만들어내고, 엘리트주의(elitism)을 적용하여 목표에 가까운 구성원들을 남기는 과정을 반복하여 좋은 모집단을 조금씩 만들어가는 휴리스틱이다.
이제 진화 알고리즘을 통해 다중목표 최적화 문제를 푸는 접근들인 NSGA-II와 SPEA2를 소개하도록 하겠다. 진화 알고리즘에서 새로운 구성원을 만들어내는 교차/변이 부분은 도메인에 따라 다르므로 건너뛰고, 어떻게 좋은 모집단을 선택할건지에 대한, 즉 엘리트주의에 대해 앞으로 집중적으로 이야기한다.
NSGA-II
NSGA-II (Deb et al, 2002)는 Non-dominated Searching Genetic Algorithm의 약자이다 [1]. 어떤 모집단이 있을 때, 엘리트주의를 적용하기 위해 그 모집단을 정렬하는 방법으로 두 가지 기준을 사용하는데,
- non-dominated 랭킹
- 붐빔 거리 (crowding distance)
을 적용한다. 우선 non-dominated 랭킹의 순서대로 모집단 내 구성원들을 정렬하고, 같은 non-dominated 랭킹을 가지는 경우 두 구성원의 순서는 붐빔 거리를 통해 최대한 다양하게 선택되도록 결정한다. 지금부터 파레토 랭킹과 붐빔 거리의 의미에 대해 각각 알아보도록 하겠다.
어떤 집단의 파레토 전면(Pareto front)은 그보다 우성인 다른 해가 없는 해들로 집합으로, 그 집단이 모든 실현 가능한 해일 경우 그 해들은 파레토 최적해이며 이전 글에서 파레토 최적해들을 찾는 것이 다중목표 최적화 문제의 목표라고 소개하였다. 이것은 실현 가능한 해(feasible solution)을 모두 알고 있을 때 찾을 수 있는 경우이고, 진화 알고리즘을 적용할 때는 그의 일부인 모집단이 있을 뿐이다.
하지만 모집단 내에서 그보다 우성인 모집단의 다른 해가 없는 해들로 구성된 파레토 전면이 그나마 가장 정답에 가깝다고 평가할 수 있고, 모집단에서 높은 가치를 지닌다. 이들을 Rank 1이라고 하고 모집단에서 제외하였을 때, 같은 방식으로 남은 모집단에서 파레토 전면을 찾을 수 있고, 이들이 그 다음으로 높은 가치를 지닌다. 이들을 Rank 2라고 하고, 계속 제외해 나갈 수 있다. 이런 식으로 파레토 전면의 랭킹에 따라 모집단을 군집화하고 정렬하는 방식을 non-dominated 정렬이라고 한다.
같은 랭크인 경우에 어떤 구성원을 우선시해야 할까? 그 답이 붐빔 거리(crowding distance)이다. 어떤 점의 붐빔 거리는 그 점에 가까운 점들이 많아질수록 작아지는 값으로, 붐빔 거리가 크다는 것은, 해당 파레토 전면에서 그 해가 다른 해들과 멀리 떨어져있다는 의미이다. 즉, 붐빔 거리가 큰 점들을 뽑으면 자연스럽게 파레토 전면에서 '다양한' 개체들을 뽑을 수 있고, 다시 말해 어느 한 곳에 집중되게 분포하는 개체들을 뽑는 것을 피할 수 있다. 예를 들어, 6개의 개체로 구성된 파레토 전면인 위 그림의 (b)에서 3개를 뽑는다면, 첫 번째, 세 번째, 여섯 번째 점들을 뽑는 것이 좋을 것이다. 그래야 해당 파레토 전면을 대표하는 가장 다양한 점을 뽑을 수 있기 때문이다.
구체적으로 주어진 모집단 P은 다음과 같은 방식으로 정렬한다.
먼저 첫 번째 for 루프에서는 모집단 내의 각 개체 p에 대해, p가 dominate하는 해들로 구성된 집합 \(S_p\)와, \(p\)가 다른 개체에 의해 dominate된 회수인 domination counter \(n_p\)를 계산한다. 계산 이후 \(n_p\)가 0이라는 것은, 다른 어떤 모집단의 개체도 p를 dominate하지 못한다는 의미이므로, 이들이 첫 번째 파레토 전면이라는 의미이고, 이들의 랭크를 1로 적고, \(\mathcal{F}_1\)에 추가한다.
두 번째 for 루프에서는 i를 1씩 늘려가면서 랭크 2, 랭크 3, ... 파레토 전면을 찾게 된다. 그를 위해 첫 번째 파레토 전면에 있는 개체들을 제외했을 때 domination counter가 0이 되는 개체들을 찾아서 두 번째 파레토 전면을 얻을 것이다. 첫 번째 파레토 전면 \(\mathcal{F}_1\)의 각 개체에 대해 이들이 dominate하는 개체들을 찾아서 그들의 domination counter \(n_q\)를 줄이고, 그 중 domination counter가 0이 되는 개체를 두 번째 파레토 전면 \(\mathcal{F}_2\)에 추가한다. 세 번째 파레토 전면도 이런 방식으로 찾을 수 있고, 그렇게 모든 원소들이 몇 번째 파레토 전면에 위치하는지를 찾을 수 있다.
어떤 개체 \(x_i\)의 붐빔 거리(crowding distance)는 근처에 있는 개체들로부터 멀리 떨어져 있을수록 더 높아지는 측정값으로, \(f_1, \cdots, f_k\)가 목표 함수라고 하였을 때 다음과 같다.
\[cd(x_i) = \sum _{j=1} ^k \frac{f_j (x_{i+1}) - f_j (x_{i-1})}{f_j ^\text{max} - f_j ^\text{min}}\]
이 때 \(x_{i+1}\)과 \(x_{i-1}\)는 \(x\)에서 목표 함수 공간 \(f_1(x), \cdots f_k(x)\)에서 가장 가까운 거리에 있는 두 개체이고 \(f_j ^\text{max}\)과 \(f_j ^\text{min}\)는 전체 모집단에서 목표 함수 \(f_j\)의 최대/최소로, 일종의 \(f_j\)의 지름을 의미한다. 이렇게 지름으로 나누게 되면 언제나 1이하의 값으로 정규화하는 효과가 있다. 결론적으로 근처에 있는 개체의 목표 함수가 차이가 큰 차이가 날수록 전체 붐빔 거리가 높아지게 되고, 목표 함수가 높은 개체들을 우선적으로 모집단으로 선택한다면 최대한 다양한 개체들을 남겨 파레토 전면의 모양을 최대한 반영하는 모집단을 얻을 수 있다.
결국, NSGA-II는 초기 모집단 \(P_t\)와 교차/변이를 통해 얻은 자손 모집단 \(Q_t\)로 구성된 새로운 모집단 \(Q_t\)에서 non-dominated sorting으로 랭킹을 매긴 후, tie가 발생하는 경우는 crowing distance로 정렬을 하여 상위 n개의 모집단 \(P_{t+1}\)을 남기는 방식으로 엘리트주의를 구현한 진화 알고리즘이다.
NSGA-II 외의 진화 알고리즘에 대해서 더 궁금하다면 SPEA2, PSEA, Two-Archive와 같은 기법들을 알아보는 것도 좋다.
출처
[1] K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," in IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, April 2002, doi: 10.1109/4235.996017.
[2] Shanu Verma, Millie Pant and Vaclav Snasel, "A Comprehensive Review on NSGA-II for Multi-Objective Combinatorial Optimization Problems", https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9393947
'컴퓨터 과학 > 메타휴리스틱' 카테고리의 다른 글
| 개미 군집 알고리즘: 개미의 먹이 탐색으로부터 영감을 받다 (0) | 2025.01.26 |
|---|---|
| 다중 목표 최적화 문제 - 차원의 저주에 걸린 고전 기법들 (1) (0) | 2025.01.13 |