다중값 유전자 알고리즘의 비밀: r-cGA는 어떻게 OneMax와 LeadingOnes를 더 빠르게 정복했나?

“유전 알고리즘은 이진수만 다룬다?”

그렇지 않다. 이제는 0과 1을 넘어, 0·1·2·3… 여러 값을 동시에 다루는 시대다. 그리고 그 중심에 바로 multi-valued EDA, 그중에서도 r-cGA가 있다.

2026년, 국제 저널 Artificial Intelligence에 실린 한 편의 논문이 이 분야의 판을 흔들었다. 덴마크 공과대학의 Sumit Adak과 Carsten Witt 연구팀은 다중값 확률모형 기반 진화 알고리즘의 수학적 실행 시간(runtime)을 처음으로 정밀하게 분석했다. 그 결과는 단순한 이론을 넘어, AI 최적화의 미래를 가늠하게 한다.

왜 여러 값을 다루는 알고리즘이 중요한가?

현실의 문제는 0 아니면 1로만 나뉘지 않는다.

스마트 공장 스케줄링, 자율주행 의사결정, 신경망 구조 탐색… 이런 문제들은 각 변수에 여러 선택지가 존재한다.

기존의 binary EDA는 한 칸에 0 또는 1만 넣을 수 있었다. 하지만 실제 세상은 더 복잡하다. 한 칸에 0·1·2·3·…·(r-1)까지 들어갈 수 있다면? 탐색 공간은 폭발적으로 커진다.

여기서 등장한 것이 바로 r-valued compact genetic algorithm, 줄여서 r-cGA다.

이 알고리즘은 단순히 후보 해를 섞는 대신, 확률 분포를 학습한다.

좋은 해가 나오면 그 방향으로 확률을 조금 올리고, 나쁜 방향은 조금 낮춘다. 마치 똑똑해지는 주사위처럼 말이다.

그런데 문제는 이것이었다.

이 알고리즘이 얼마나 빨리 최적해에 도달하는지, 아무도 정확히 몰랐다.

연구팀이 던진 질문: r-cGA는 얼마나 빠른가?

연구진은 두 가지 대표 문제를 분석했다.

r-LeadingOnes
r-OneMax

이 두 문제는 진화 알고리즘 분야에서 일종의 “기초 체력 테스트” 같은 존재다.

1️⃣ r-OneMax란 무엇인가?

모든 위치에서 값이 (r-1)이면 최고 점수다.
즉, (r-1)을 많이 맞출수록 점수가 높아진다.

초등학생도 이해할 수 있다.
“정답 칸이 r-1이고, 많이 맞추면 이긴다.”

2️⃣ r-LeadingOnes란 무엇인가?

앞에서부터 연속으로 (r-1)을 얼마나 길게 맞추는지가 점수다.
첫 번째가 틀리면 바로 끝이다.

이건 좀 더 까다롭다.
앞부분이 완벽해야 뒤로 갈 수 있다. 마치 도미노처럼.

알고리즘 내부에서는 무슨 일이 벌어질까?

r-cGA는 매 단계마다 두 개의 해를 뽑는다.
더 좋은 해를 기준으로 확률을 조금씩 조정한다.

핵심은 확률 행렬이다.

각 위치 i, 각 값 j에 대해 확률 p(i,j)를 유지한다.

처음에는 모두 1/r이다. 완전 공평하다.
하지만 좋은 해가 반복되면 특정 값의 확률이 점점 커진다.

문제는 여기서 발생한다.

유전적 표류(genetic drift)

때로는 성능과 무관하게 확률이 우연히 치우친다.
마치 동전 던지기를 오래 하면 어느 한쪽이 몰리는 것처럼.

이 현상은 알고리즘을 엉뚱한 방향으로 몰고 갈 수 있다.

연구팀은 이를 martingale 이론과 negative drift theorem을 이용해 정밀 분석했다. 수학적으로 확률이 얼마나 흔들리는지 계산해낸 것이다.

드디어 나온 결정적 결과

r-LeadingOnes에 대한 최초의 실행 시간 상한

연구진은 다음을 증명했다.

실행 시간 = O(n² r² log³n log²r)

작은 r일 경우, 즉 r이 상수라면 거의 O(n²) 수준이다.
이는 이진 LeadingOnes 문제에서의 전통적 결과와 거의 같다.

이 말은 무엇인가?

다중값이 되었다고 해서 성능이 폭망하지 않는다는 뜻이다!

r-OneMax 실행 시간 대폭 개선

이전 연구보다 log n 항 하나를 제거했다.

새로운 실행 시간:

O(n r log n log r)

이 개선은 단순한 숫자 감소가 아니다.
큰 n에서 체감 차이가 엄청나다.

주목할 또 하나의 혁신: frequency borders

연구는 확률이 0이나 1에 완전히 고정되지 않도록 경계값을 두는 방식을 분석에 처음 포함했다.

경계는 이렇게 설정된다.

최소값: 1 / ((r-1)n)
최대값: 1 - 1/n

이 장치는 알고리즘이 “확률 0” 상태에 빠져 복구 불가능해지는 것을 막는다.

이제 이 장치까지 포함한 수학적 분석이 완성되었다.
이론과 실제 구현의 간극이 크게 줄어든 것이다.

왜 이 연구가 중요한가?

이 논문은 단순히 하나의 알고리즘을 분석한 것이 아니다.

다음 세 가지 의미가 있다.

1️⃣ 다중값 EDA 이론의 기초를 세웠다

지금까지는 거의 미개척 영역이었다.

2️⃣ 유전적 표류를 통제하는 방법을 제시했다

확률이 우연히 흔들리는 현상을 수학적으로 제어했다.

3️⃣ 실제 AI 문제로 확장 가능성을 열었다

신경망 구조 탐색, 다중목표 최적화, 스케줄링 문제 등으로 확장 가능하다.

이 연구가 여는 미래

AI는 점점 더 복잡한 선택지를 다룬다.
단순한 이진 선택은 한계가 있다.

이제 우리는 묻는다.

다중값 확률 모델은 어디까지 확장될 수 있을까?

r-cGA의 수학적 분석은 시작일 뿐이다.
이제는 더 복잡한 함수, 더 큰 r, 더 현실적인 문제로 확장될 것이다.

그리고 그 중심에는 확률을 학습하는 진화 알고리즘이 있다.

한 문장으로 정리하자면

r-cGA는 다중값 최적화에서도 이론적으로 빠르고 안정적이라는 것이 처음으로 증명되었다.

이것이 2026년, 진화 알고리즘 연구의 가장 큰 뉴스 중 하나다.

출처: Adak, S., & Witt, C. (2026). Mathematical runtime analysis of a multi-Valued estimation of distribution algorithm. Artificial Intelligence, 353, 104501. https://doi.org/10.1016/j.artint.2026.104501