본 논문은 다목적 진화 알고리즘에서 교차 연산자의 역할에 초점을 맞춘 이론적 연구입니다. 특히, 두 개 이상의 목적 함수를 갖는 문제에서 교차 연산의 장점은 잘 이해되지 않고 있으며, 교차 연산을 포함한 엄밀한 실행 시간 분석은 실제 사용에 비해 크게 뒤쳐져 있습니다. 본 논문에서는 두 가지 다목적 문제인 $RR_{\text{RO}}$와 $uRR_{\text{RO}}$를 제시하고, GSEMO 알고리즘과 널리 사용되는 NSGA-III 알고리즘에 대한 이론적 실행 시간 분석을 통해 $RR_{\text{RO}}$에서의 단일점 교차와 $uRR_{\text{RO}}$에서의 균일 교차가 실행 시간을 기하급수적으로 단축시킬 수 있음을 보여줍니다. 목표 함수의 개수가 일정할 때, 교차 연산을 사용하면 이 알고리즘들이 두 문제의 Pareto 집합을 기대 다항 시간 내에 찾을 수 있지만, 교차 연산 없이는 단일 Pareto 최적점조차 찾는 데 기하급수적 시간이 필요합니다. 또한, 목표 함수의 개수에 대한 특정 초상수 매개변수 영역에서 상당한 성능 차이를 보임을 보여줍니다. 본 논문은 두 개 이상의 목적 함수에 대해 교차 연산을 사용할 때 기하급수적인 성능 차이를 보여주는 최초의 엄밀한 실행 시간 분석 중 하나이며, 목표 함수의 개수가 반드시 일정하지 않은 경우를 포함하는 최초의 실행 시간 분석입니다.
