Large-Scale Portfolio Optimization Problem Under Cardinality Constraint With Enhanced Multi-Objective Evolutionary Algorithms

당신이 긴 여정을 위해 궁극의 배낭을 만들려는 보물 사냥꾼이라고 상상해 보십시오. 당신은 두 가지를 원합니다. 가장 가치 있는 금화(높은 수익)와 가장 가볍고 안전한 짐(낮은 위험)입니다. 하지만 제약 조건이 하나 있습니다. 당신의 배낭에는 엄격한 규칙이 있습니다. 지도 곳에 흩어진 보물의 개수와 상관없이, 오직 특정 범위 내의 서로 다른 아이템들만 담을 수 있어야 합니다. 예를 들어 3개에서 10개 사이여야 합니다. 이것이 바로 "카디널리티 제약 포트폴리오 최적화(Cardinality-Constrained Portfolio Optimization)" 문제입니다.

수십 년 동안 투자자들은 이 문제를 해결하기 위해 "정확한(exact)" 수학적 방법들을 사용해 왔습니다. 이는 마치 해변의 모래알 하나하나를 다 세어서 완벽한 한 움큼을 찾으려는 것과 같습니다. 이 논문은 이러한 접근 방식이 마치 소방 호스로 물을 마시려는 것과 같다고 설명합니다. 너무 느리고, 자산(모래알)의 수가 엄청나게 많아지면 길을 잃기 때문입니다. 실제로 저자들은 이러한 현실 세계의 규칙들을 추가하는 것이 컴퓨터에게는 "NP-hard"라고 불리는 악몽이 되어, 전통적인 수학 도구들이 포기하거나 영원히 걸리게 만든다는 점을 언급했습니다.

핵심 아이디어: 새로운 배낭 설계
모든 모래알을 세는 대신, 저자들은 새로운 종류의 배낭과 그것을 채우는 새로운 규칙을 만들었습니다. 그들은 NSGA-II라고 불리는 인기 있는 도구(똑똑하게 진화하며 다양한 배낭 조합을 시도하는 로봇이라고 생각하십시오)를 가져와 대대적으로 업그레이드했습니다.

이들의 새로운 시스템이 어떻게 작동하는지는 다음과 같은 비유와 메커니즘을 통해 설명할 수 있습니다.

1. "고정 크기" 배낭 (새로운 인코딩)
기존 방식은 가능한 모든 보물의 목록을 들고 다니며 어떤 것을 가져갈지 표시하려고 했습니다. 만약 보물이 225개라면, 단 10개만 가져가더라도 목록은 항상 225개 아이템의 길이를 유지했습니다. 이로 인해 로봇은 빈 슬롯을 확인하는 데 시간을 낭비했습니다.
저자들은 배낭 자체를 바꿨습니다. 이제 배낭은 정확히 Kmax(가져갈 수 있는 최대 아이템 수)만큼의 슬롯을 가집니다. 만약 5개까지 가질 수 있다면, 배낭은 정확히 5개의 슬롯을 가집니다.

• 비결: 만약 같은 보물을 두 개의 슬롯에 넣는다면, 그것은 하나의 아이템으로 계산되지만 무게(돈)는 합산됩니다. 이렇게 하면 로봇이 규칙을 어기고 있는지 훨씬 쉽게 확인할 수 있습니다. 만약 배낭에 고유한 아이템이 Kmin보다 적다면(예를 들어 최소 3개가 필요한데 고유 아이템이 2개뿐이라면), 로봇은 새로운 보물을 교체해 넣어야 한다는 것을 알게 됩니다.

2. "2단계" 사냥 (교배 전략)
로봇은 단순히 무작위로 추측하지 않습니다. 로봇은 사건을 해결하는 탐정처럼 두 가지 뚜렷한 단계로 사냥합니다.

• 1단계 (넓은 그물 던지기): 시작 단계에서 로봇은 거칠게 움직입니다. 보물의 최적의 조합을 찾기 위해 "Knee-based(니 기반)" 전략을 사용합니다. 이들은 곡선의 "무릎(knee)" 부분, 즉 추가적인 무게 대비 가장 많은 금을 얻을 수 있는 스윗 스팟을 찾습니다. 이들은 최적의 지점에 가까운 솔루션들을 교배하여 자산의 적절한 혼합을 빠르게 찾아냅니다.
• 2단계 (미세 조정): 일단 좋은 보물 목록을 확보하면, 로봇은 더 이상 새로운 것을 찾는 것을 멈추고 각 보물의 양을 조절하기 시작합니다. 이들은 "Similarity-based(유사성 기반)" 전략을 사용하여, 이미 동일한 보물을 가지고 있지만 무게가 다른 배낭들을 교배함으로써 정확한 균형을 미세하게 조정합니다.

3. "탐험가(Explorer)" 도구
때때로 로봇은 아이템이 너무 적거나 많은 고장 난 배낭을 고칠 때, 단순히 무작위로 아이템을 갈아 끼웁니다. 하지만 저자들은 이것이 서투른 방식이라는 것을 깨달았습니다. 그래서 그들은 **"탐험가(Explorer)"**라는 새로운 도구를 발명했습니다.
배낭에 아이템이 부족한 상황을 상상해 보십시오. 단순히 눈에 보이는 첫 번째 돌을 집어 드는 대신, 탐험가는 빈 공간을 채울 몇 가지 다른 방법들을 살펴봅니다. 탐험가는 다섯 가지 다른 "휴리스틱(heuristic)" 방법(예: 돈을 균등하게 배분하거나, 더 안전한 아이템에 더 많은 돈을 주는 방식 등)을 시도하여 어떤 것이 배낭을 더 좋게 만드는지 확인합니다. 그런 다음 가장 좋은 버전을 선택하고, 심지어 이전 배낭과 새 배낭 사이의 "미지의" 공간으로 조금 더 나아가 더 나은 것을 찾을 수 있는지 확인합니다. 이는 수정 작업이 단순히 "괜찮은" 수준이 아니라, 실제로 개선된 결과가 되도록 보장합니다.

4. "수리팀" (제약 조건 처리)
로봇이 실수로 규칙을 어겼을 때(예: 너무 많은 아이템을 선택하거나 한 아이템에 너무 많은 돈을 넣었을 때), 로봇은 그냥 배낭을 버리지 않습니다. 대신 전문 수리팀을 운용합니다.

• 연관성 팀 (Association Crew): 현재 그룹 내의 다른 성공적인 배낭들이 무엇을 담고 있는지 살펴보고 그 패턴을 복사합니다.
• 점수 팀 (Score Crew): 보물들을 함께 수행 능력이 좋은 그룹별로 분류하고 가장 좋은 그룹을 선택합니다.
• 임계값 팀 (Threshold Crew): 특히 다른 것들과 동기화되어 움직이지 않는(낮은 상관관계) 보물들을 찾아 다양성을 확보합니다.

결과 (무엇을 발견했는가)
저자들은 이 새로운 시스템을 네 가지 실제 시장인 DAX 100(독일), S&P 100(미국), Nikkei 225(일본), 그리고 **테헤란 증권거래소(TSE)**를 대상으로 테스트했습니다.

• 테스트 규모: 각각 85, 98, 225, 418개의 자산을 가진 데이터셋을 사용했습니다.
• 규칙: 배낭이 Kmin과 Kmax 사이의 아이템을 보유하도록 설정했습니다(예: 2개에서 10개 사이, 또는 정확히 10개).
• 결과: 100번의 반복 실행과 100개의 솔루션 인구수를 적용한 시뮬레이션에서, 업그레이드된 로봇은 일관되게 더 나은 배낭을 찾아냈습니다.
  • 이들은 이론적인 완벽한 한계치에 더 가까운 솔루션을 찾았습니다(IGD라는 지표로 측정됨).
  • 이들은 더 넓은 범위의 좋은 옵션들을 확보했습니다(Hypervolume으로 측정됨).
  • 특히 자산의 수가 많아질 때, 이들은 더 빠르고 안정적으로 이를 수행했습니다.

무엇을 명시적으로 제외했는가
논문은 이 특정 문제에 대해 무엇이 잘 작동하지 않는지 매우 명확하게 밝히고 있습니다.

• 정확한 방법 (Exact Methods): 저자들은 이 문제가 NP-hard이기 때문에 전통적인 정확한 수학적 방법들이 비효율적이라고 주장합니다. 이 방법들은 규모가 큰 시장에서는 너무 느리다고 제안합니다.
• 패널티 함수 (Penalty Functions): 일부 연구자들은 규칙을 어긴 배낭에 낮은 점수를 주는 "패널티 함수"를 사용하지만, 이 논문은 성공적인 연구의 대다수가 **수리 메커니즘(repair mechanisms, 배낭을 고치는 것)**을 사용한다는 점을 명시적으로 밝히고 있습니다. 그들은 솔루션을 처벌하기보다 수리하는 쪽을 택했습니다.
• 무작위 추측 (Random Guessing): 단순히 초기에 무작위 솔루션을 교배하는 것은 시간을 낭비한다는 것을 보여줍니다. 그들의 "Knee-based" 선택이 탐색을 유도하는 데 필수적입니다.

얼마나 확신하는가?
저자들은 자신의 결과에 자신감을 가지고 있지만, 언어 사용에 있어서는 신중합니다. 그들은 시뮬레이션 100회 실행을 바탕으로 자신들의 접근 방식이 우월함을 "나타내고(indicates)" "입증한다(demonstrates)"고 기술했습니다. 그들은 결과가 단순히 운이 아니었음을 증명하기 위해 통계적 검정(Sign Test 및 Wilcoxon Signed-Rank Test)을 사용했습니다.

• 예를 들어, TSE 시장에서 그들의 방법은 Hypervolume 지표에 대해 표준 방식보다 10번 중 10번 모두 승리했습니다.
• 그러나 DAX 100 시장의 경우, 특정 지표(MGD)에서의 개선이 가장 엄격한 수준에서 통계적으로 유의미하지는 않았으나, 평균적으로는 더 나았다고 언급했습니다.

결론
이 논문은 문제를 표현하는 방식(고정 크기 배낭), 솔루션을 찾는 방식(2단계 사냥), 그리고 실수를 고치는 방식(탐험가 도구)을 바꿈으로써 더 나은 투자 포트폴리오를 훨씬 더 빠르게 찾을 수 있음을 시사합니다. 이는 특히 시장에 수백 개의 자산이 몰려 있을 때 더욱 그렇습니다. 저자들은 자신들의 방법이 강력한 개선책이긴 하지만 마법의 지팡이는 아니라고 결론짓습니다. 즉, 투자자들이 나중에 거래 비용과 같은 더 복잡한 규칙을 추가하고자 한다면 여전히 적응이 필요합니다. 하지만 현재로서는, 이것이 훨씬 더 똑똑한 방식으로 배낭을 싸는 방법입니다.