Linear Proposal Operators and Stochastic Search Geometry in SOMA and Differential Evolution

당신이 수많은 언덕, 굴곡, 그리고 숨겨진 구덩이들로 가득 찬, 안개 낀 광활한 계곡에서 가장 낮은 지점을 찾으려 한다고 상상해 보십시오. 당신은 전체 지도를 볼 수 없으며, "아래쪽"을 가리키는 나침반도 가지고 있지 않습니다. 이것이 바로 컴퓨터가 "블랙박스(black-box)" 최적화 문제를 해결하려고 할 때 겪는 일상적인 삶입니다. 이를 위해 과학자들은 **진화 알고리즘(evolutionary algorithms)**이라 불리는 특별한 프로그램들을 사용합니다. 이것을 디지털 생태계라고 생각하면 쉽습니다. 이곳에는 가상 탐험가 팀(하나의 "집단")이 돌아다닙니다. 그들은 단순히 무작위로 걷는 것이 아닙니다. 그들은 서로로부터 배웁니다. 어떤 탐험가들은 "리더"(지금까지 가장 좋은 지점을 찾아낸 이들)가 되며, 다른 이들은 리더를 향해 움직이거나, 혹은 더 나은 무언가를 찾기 위해 다른 탐험가들과 자신들의 경로를 섞기도 합니다. 두 가지 유명한 탐험가 팀으로는 SOMA(Self-Organizing Migrating Algorithm)와 Differential Evolution(DE)이 있습니다. 이들은 오랫동안 존재해 왔지만, 종종 그 자체로 "블랙박스"처럼 취급받곤 했습니다. 즉, 우리는 그것들이 작동한다는 것은 알지만, 그 안에서 탐험가들이 단계별로 어떻게 움직이는지에 대한 정확한 기하학적 구조는 완전히 이해하지 못하고 있습니다.

Vojtěch Novák과 Ivan Zelinka가 작성한 이 논문은 이 블랙박스를 분해하여 내부의 톱니바퀴를 들여다보기로 결정했습니다. 저자들은 탐험가들이 움직이고, 지치고, 교체되는 이 혼란스러운 과정 전체를 관찰하는 대신, "움직임(movement)" 부분과 "판단(judgment)" 부분을 분리했습니다. 그들은 이 알고리즘들이 새로운 단계를 제안하는 방식이 실제로는 보이는 것보다 훨씬 단순하고 수학적이라는 것을 발견했습니다. 그들은 이 탐험가들의 움직임을 직선과 단순한 수학 공식(선형 연산자)을 사용하여 설명할 수 있다는 것을 찾아냈습니다. 비록 전체 시스템은 혼란스러워 보일지라도 말입니다. 이 숨겨된 기하학을 이해함으로써, 저자들은 탐험가들이 정확히 얼마나 멀리, 어느 방향으로 점프해야 하는지 알 수 있는 더 똑똑한 버전의 탐험가들을 구축할 수 있었습니다.

"제안(Proposal)" 대 "심판(Judge)"의 마법

당신이 0에서 100 사이의 비밀 숫자를 맞혀야 하는 게임을 하고 있다고 상상해 보십시오. 당신에게는 당신을 돕는 친구 팀이 있습니다. 기존의 방식에서는 전체 과정이 흐릿합니다. 친구가 숫자를 제안하고, 당신은 그것이 맞는지 확인하고, 만약 너무 높다면 아마도 그것을 수정하고, 그런 다음 누가 게임에 남을지 결정합니다. 왜 친구가 특정 숫자를 제안했는지 설명하기가 어렵습니다.

이 논문의 저자들은 여기서 실제로 두 가지 뚜렷한 단계가 일어나고 있으며, 이를 별도로 다루어야 한다는 것을 깨달았습니다:

1. 제안 (The "What If"): 친구가 자신의 위치와 리더의 위치를 바탕으로 새로운 숫자를 제안합니다. 이 단계는 순수하게 기하학적입니다. 그것은 지도 위에 선을 긋는 것과 같습니다.
2. 선택 (The "Judge"): 당신은 그 제안을 보고 "이것이 우리가 가진 것보다 더 나은가?"를 결정합니다. 이 단계는 특정 문제(적합도, fitness)에 따라 달라지며, 복잡하고 비선형적입니다.

이 논문의 큰 돌파구는 SOMA와 Differential Evolution 모두에서 제안 단계가 사실은 깨끗한 직선이라는 것을 보여준 데 있습니다. 전체 게임이 복잡하게 느껴질지라도, 새로운 후보를 생성하는 행위는 단순한 수학 연산입니다. 즉, 현재 위치를 잡고, 리더를 바라보고, 그 경로를 따라 일정 거리만큼 이동하는 것입니다.

점프의 기하학

저자들은 이를 증명하기 위해 영리한 트릭을 사용했습니다. 그들은 "이주자(migrant, 움직이는 탐험가)"와 "리더(leader, 최고의 탐험가)"를 공간상의 두 점으로 상상했습니다. 그들은 새로운 위치가 어떤 마법 같고 예측 불가능한 점프가 아님을 보여주었습니다. 그것은 정확히 **선형 변환(linear transformation)**입니다.

이렇게 생각해 보십시오. 당신이 점 A에 서 있고 당신의 리더가 점 B에 있다면, 알고리즘은 단순히 어디로 갈지 "추측"하는 것이 아닙니다. 당신과 리더 사이의 직선을 긋습니다. 그런 다음 그 선 위의 한 지점을 선택합니다.

• 보간(Interpolation): 당신과 리더의 중간 지점을 선택할 수도 있습니다.
• 투영(Projection): 리더가 있는 바로 그 지점을 선택할 수도 있습니다.
• 오버슈팅(Overshooting): 마치 너무 빨리 달려서 리더의 뒤쪽까지 확인해야 하는 것처럼, 리더를 지나쳐 그 너머의 지점을 선택할 수도 있습니다.

논문은 이 움직임이 몇 가지 단순한 조절 장치(knobs)에 의해 제어된다는 것을 보여줍니다.

• 경로 매개변수 ($t$): 선을 따라 얼마나 멀리 가는가?
• 마스크 (PRT 또는 CR): 이것은 마치 일부 방향을 차단하는 선글라스와 같습니다. 만약 마스크가 "북쪽 방향으로는 움직이지 마"라고 한다면, 탐험가는 동, 남, 서쪽으로만 움직입니다. 이는 한 번에 일부 좌표만 변화하는 "희소한(sparse)" 움직임을 만들어냅니다.

저자들은 마스크를 확률 분포(베르누이 분포)로 취급함으로써, 탐험가의 평균적인 행동을 계산할 수 있었습니다. 그들은 다음과 같은 것들에 대한 공식을 찾아냈습니다:

• 평균적으로 탐험가는 얼마나 멀리 점프하는가?
• 점프에 있어서의 "퍼짐(spread)"이나 불확실성은 어느 정도인가?
• 탐험가가 실제로 움직이는 방향(차원)은 몇 개인가?

그들은 심지어 "마스크(선글라스)"가 단순히 무작위로 방향을 차단하는 것이 아니라, 특정한 형태의 불확실성을 만들어낸다는 것을 발견했습니다. 마스크 확률이 낮으면 탐험가는 매우 적은 방향으로 움직입니다. 확률이 높으면 많은 방향으로 움직입니다. 가장 "혼란스러운(최대 분산)" 움직임은 마스크가 완전히 열려 있거나 완전히 닫혀 있을 때가 아니라, 50%로 설정되었을 때 발생합니다.

더 나은 탐험가 만들기: 새로운 변형들

저자들은 움직임의 수학적 원리를 이해한 후, 이론에만 머물지 않았습니다. 그들은 이 공식들을 사용하여 개선된 세 가지 버전의 SOMA 알고리즘을 구축했습니다.

1. 기하학 제어 SOMA (Geometry-Controlled SOMA, GC-SOMA):
   얼마나 많은 방향으로 움직일지 추측하는 대신, 이 버전은 사용자에게 "나는 탐험가가 정확히 5개 방향으로 움직이길 원한다"라거나 "나는 탐험가가 리더에게 90%만큼 도달하길 원한다"라고 말할 수 있게 해줍니다. 그러면 알고리즘은 그 특정 기하학적 목표를 달려 달성하기 위해 필요한 설정값(마스크 확률 및 경로 길이)이 정확히 무엇인지 수학 공식을 통해 계산합니다. 이것은 자동차에게 "정확히 50마일을 달려"라고 말하면, 자동차의 컴퓨터가 가속 페달을 얼마나 길게 밟아야 하는지 계산하는 것과 같습니다.

2. 회전 인식 SOMA (Rotation-Aware SOMA, RA-SOMA):
   표준 알고리즘은 격자선(북, 남, 동, 서)을 따라 움직입니다. 하지만 만약 계곡이 기울어져 있다면 어떨까요? 만약 최적의 경로가 대각선이라면요? 표준 알고리즘은 격자선을 따라 움직여야 하므로 어려움을 겪습니다. RA-SOMA는 탐험가 그룹 전체를 살펴보고, 그들이 있는 계곡의 "모양"을 파악한 뒤, 그 모양에 맞춰 움직임을 회전시킵니다. 이것은 등산객이 격자 모양으로 걷는 것을 멈추고, 산이 기울어져 있다는 것을 깨달은 뒤 경사에 맞춰 대각선으로 걷는 것과 같습니다. 이를 통해 이 알고리즘은 까다롭고 뒤틀린 문제들을 훨씬 더 잘 해결할 수 있습니다.

3. iL-SHOMA-RA:
   이것은 회전 기술과 다른 스마트한 기능들을 결합한 "강력한" 버전입니다. 이 알고리즘은 과거에 어떤 움직임이 효과적이었는지 기억하며(성공 이력, success-history), 솔루션에 가까워질수록 탐험가의 수를 서서히 줄입니다(집단 감소, population reduction). 이것은 수색대가 100명으로 시작하지만, 보물에 가까워질수록 대부분의 사람을 집으로 보내고 가장 뛰어난 정찰병들만 남겨서, 이제 완벽한 방향으로 걷게 하는 것과 같습니다.

결과: 실제로 효과가 있는가?

저자들은 이 새로운 탐험가들을 다양한 모양과 난이도를 가진 24개의 유명한 "계곡"(BBOB 벤치마크라고 불림)에서 테스트했습니다. 그들은 이를 원래의 SOMA 및 가장 뛰어난 Differential Evolution 알고리즘들(예: iL-SHADE)과 비교했습니다.

결과는 명확했습니다:

• 원본의 패배: 수정되지 않은 표준 SOMA는 보통 최악의 성능을 보였습니다. 속도가 느리고 자주 막혔습니다.
• 새로운 버전의 강세: 세 가지 새로운 버전(GC-SOMA, RA-SOMA, iL-SHOMA-RA) 모두 원래의 SOMA보다 훨씬 뛰어났습니다.
• 회전이 핵심이다: 회전 인식(Rotation-Aware) 버전은 저차원 문제(변수가 5개 또는 10개인 경우)에서 스타였습니다. 일부 경우에는 최고의 Differential Evolution 알고리즘들을 이기기도 했습니다. 이는 움직임을 문제의 형태에 맞춰 "기울이는" 것이 엄청난 이점이 된다는 것을 증명합니다.
• 예산이 중요하다: "강력한" 버전(iL-SHOMA-RA)은 컴퓨터 계산 시간이 많지 않을 때(낮은 "예산") 특히 유용했습니다. 이들은 빠르게 좋은 솔루션을 찾아냈습니다.
• 만능 약은 아니다: 그러나 논문은 이 새로운 방법들이 모든 것에서 승리한 것은 아니라고 신중하게 밝히고 있습니다. 매우 높은 차원(변수 20개)이나 특정 유형의 문제에서는 기존의 Differential Evolution 알고리즘들이 여전히 더 나았습니다. 이 새로운 방법들이 모든 최적화 문제를 해결한 것은 아니지만, 기존 SOMA에 비하면 엄청난 발전입니다.

이것이 왜 중요한가

이 논문은 우리가 이러한 알고리즘을 생각하는 방식을 바꾸기 때문에 중요합니다. 오랫동안 우리는 이것들을 신비로운 블랙박스로 취급해 왔습니다. 이 논문은 그 상자를 열고 내부의 톱니바퀴를 보여줍니다. 이는 이 알고리즘들의 "움직임" 부분이 실제로는 단순한 선형 수학 연산임을 입증합니다.

기하학을 이해함으로써, 우리는 추측하는 것을 멈추고 설계하기 시작할 수 있습니다. 우리는 단순히 랜덤한 설정이 잘 작동하기를 바라는 것이 아니라, 알고리즘이 정확히 어떻게 움직여야 하는지 지시할 수 있습니다. 저자들은 "점프의 모양(기하학)"을 제어함으로써 이러한 알고리즘을 훨씬 더 효율적으로 만들 수 있음을 보여주었습니다.

논문은 결론적으로, 이 새로운 방법들이 큰 진전이긴 하지만 이야기가 끝난 것은 아니라고 말합니다. 최고의 알고리즘은 특정 문제, 변수의 개수, 그리고 가용 시간(예산)에 따라 달라집니다. 하지만 이제 우리는 미래를 위한 더 나은 탐험가를 만들기 위한 지도와 나침반을 갖게 되었습니다. 저자들은 향로, 더 복잡하거나 노이즈가 있거나 제약이 있는 환경에서도 이러한 기하학적 아이디어들이 어떻게 작동하는지 살펴보아야 한다고 제안하지만, 현재로서는 혼란스러운 탐색을 정밀하고 수학적으로 안내되는 여정으로 성공적으로 전환시켰습니다.