SPEA2$^+$: 증명 가능한 실행 시간 보장을 갖춘 SPEA2의 개선된 밀도 추정

Strength Pareto Evolutionary Algorithm 2 (SPEA2)는 다목적 최적화 문제를 해결하는 데 사용되는 인기 있고 대표적인 진화 알고리즘입니다. 이러한 인기도에도 불구하고, SPEA2에 대한 이론적 분석은 최근에야 등장했습니다. 더욱이, 이 분석들은 오직 SPEA2가 비지배 해(non-dominated solutions)를 처리하는 방식에만 초점을 맞추고, 지배 해(dominated solutions)를 처리하는 데 책임이 있는 알고리즘 구성 요소는 무시합니다. 우리는 이러한 구성 요소들이 분석된 SPEA2의 최초 실행 시간 분석을 수행합니다. 우리는 같은 상수 개체군 크기 및 중복 제거 설정 하에서 NSGA-II, NSGA-III, SMS-EMOA를 포함한 다른 대표적인 알고리즘들과 달리, SPEA2가 OneTrapZeroTrap 벤치마크의 파레토 전선(Pareto front)을 효율적으로 커버하지 못한다는 것을 증명합니다. 우리의 결과는 적합도 할당에 k번째 최근접 이웃 거리(k-th nearest-neighbour distance)를 사용하는 것이 지배 개체들 사이의 다양성을 유지하기에 불충분한 신호를 제공함을 나타냅니다. 이 문제를 해결하기 위해, 우리는 모든 쌍별 거리를 고려하는 개선된 변형인 SPEA2$^+$를 제안합니다. 새로운 알고리즘은 OneTrapZeroTrap에서 다른 대표적인 알고리즘들과 동일한 성능 보장을 달성하며, 더 간단한 문제에서는 원래의 SPEA2와 성능을 일치시킵니다. 실험 결과는 우리의 이론적 발견들을 보완합니다.