🤖 AI

A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures

본 논문은 최적화 문제의 프로그래밍 구현으로부터 할스테드 부피(Halstead volume)와 엔트로피를 계산함으로써 최적화 문제를 특성화하는 새로운 접근 방식을 제안하며, 이러한 코드 기반 복잡도 척도가 알고리즘 선택을 위한 효과적인 샘플링 불필요 예측 메타 특징(sampling-free predictive meta-features) 역할을 한다는 것을 입증한다.

원저자: Marcus Gallagher, Katherine M. Malan

게시일 2026-08-11

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Marcus Gallagher, Katherine M. Malan

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 로봇에게 미로를 푸는 법을 가르치려 한다고 상상해 보세요. 때로는 미로가 단순하고 곧은 복도일 수도 있고, 때로는 막다른 길과 함정이 있는 뒤틀리고 구불구불한 미궁일 수도 있습니다. 컴퓨터 과학의 세계에서 이것은 최적화(optimisation), 즉 문제에 대한 가능한 최선의 해결책을 찾는 것을 의미합니다. 하지만 여기서 까다로운 점은 모든 미로가 다 똑같지는 않다는 것입니다. 어떤 미로는 로봇이 풀기에 쉽지만, 어떤 미로는 가장 똑똑한 알고리즘조차 길을 잃게 만듭니다.

로봇이 적절한 전략을 선택할 수 있도록 돕기 위해, 과학자들은 로봇이 실행을 시작하기도 전에 이 미로들을 '특성화'하거나 기술하려고 노력합니다. 그들은 지면이 얼마나 울퉁불퉁한지, 혹은 막다른 길이 얼마나 많은지와 같은 단서들을 찾습니다. 보통 이러한 단서를 찾기 위해 로봇은 몇 걸음 움직여 보고, 주변을 둘러보며, 지형을 측정해야 합니다. 이는 마치 동굴을 지도화하기 위해 정찰병을 어둠 속으로 보내는 것과 같습니다. 하지만 만약 로봇이 발을 한 번도 들이지 않고도 미로의 '설계도'를 보고 그 문제를 푸는 것이 얼마나 어려울지 추측할 수 있다면 어떨까요? 그것이 바로 이 논문이 던지는 질문입니다. 이 논문은 문제가 작성된 방식이 그 문제를 해결하는 데 얼마나 어려운지를 알려주는 비밀을 담고 있을 수 있다고 제안합니다. 마치 요리법의 복잡함이 요리가 얼마나 어려울지를 암시하는 것과 마찬가지로 말입니다.

수정구슬로서의 코드

이 논문에서 마커스 갈라거(Marcus Gallagher)와 캐서린 말란(Katherine Malan)은 이 어려운 문제들을 바라보는 새롭고 약간은 마법 같은 방식을 제안합니다. 그들은 지형을 측정하기 위해 정찰병을 보내는 대신, 컴퓨터가 문제를 생성하는 데 사용하는 '레시피'를 읽자고 제안합니다.

최적화 문제를 비디오 게임 레벨이라고 생각해 보세요. 프로그래머는 이 레벨을 만들기 위해 코드를 작성합니다. 어떤 레벨은 단순합니다: "앞으로 이동하고, 구덩이를 뛰어넘고, 코인을 획득하라." 이 코드는 짧고 기본적인 명령어를 사용합니다. 다른 레벨은 혼란스럽습니다: "만약 하늘이 파란색이라면, 속도에 별의 개수를 곱하고, 체력의 제곱근을 뺀다. 단, 모자를 쓰고 있을 때만 해당한다." 이 코드는 길고 무질서하며, 매우 다양한 명령어를 사용합니다.

저자들의 핵심 아이디어는 이것입니다: 코드가 더 무질서하고 복잡할수록, 알고리즘이 문제를 해결하기 더 어려워진다.

그들은 이 '무질서함'을 측정하기 위해 소프트웨어 공학의 두 가지 도구를 빌려왔습니다.

할스테드 부피(Halstead Volume): 한 단락에 있는 모든 단어와 기호의 개수를 세는 것을 상상해 보세요. 만약 단순한 단어로 된 짧은 이야기라면 그 숫자가 낮을 것입니다. 만약 복잡한 어휘와 긴 문장을 가진 소설이라면 그 숫자가 높을 것입니다. 이 척도는 코드 내의 '연산자'(수학 기호 등)와 '피연산자'(숫자와 변수 등)의 개수를 계산합니다.
샤논 엔트로피(Shannon Entropy): 이것은 약간 '놀라움의 정도'를 측정하는 것과 비슷합니다. 만약 어떤 단락이 똑같은 다섯 단어를 계속 반복해서 사용한다면, 그것은 예측 가능합니다(낮은 엔트로피). 만약 아주 다양한 고유한 단어들을 무작위 순서로 사용한다면, 그것은 예측 불가능합니다(높로 엔트로피).

실험: 단순한 원에서 혼돈의 봉우리까지

이 이론을 테스트하기 위해, 저자들은 전 세계 과학자들이 사용하는 유명한 24개의 테스트 문제 세트(BBOB 스위트라고 알려짐)를 가져왔습니다. 이 문제들은 "구(Sphere)" 함수(매끄럽고 둥근 언덕이라서 아래로 굴러 내려가기 쉬운 형태)부터 "루나섹 비-라스트리진(Lunacek bi-Rastrigin)" 함수(수천 개의 작은 봉우리와 골짜기가 있는 들쭉날쭉하고 울퉁불퉁한 지형)까지 다양합니다.

그들은 각 24개 문제의 컴퓨터 코드를 기록했고, 그들의 '무질서함' 계산기를 실행했습니다. 결과는 그들이 기대했던 바와 정확히 일치했습니다:

단순하고 매끄러운 구(Sphere) 함수는 가장 낮은 복잡도 점수를 기록했습니다.
들쭉날쭉하고 어려운 루나섹(Lunacek) 함수는 가장 높은 복잡도 점수를 기록했습니다.
실제로, 루나섹 함수는 구 함수보다 코드 구조 측면에서 약 9.3배 더 복잡했습니다.

그들은 이 실험을 다른 종류의 문제, 즉 신경망(AI의 뇌 유형)을 훈련시키는 데에도 적용했습니다. 그들은 "Tanh" 활성화 함수를 사용하는 네트워크의 코드가 "ReLU"를 사용하는 것보다 약간 더 복잡하다는 것을 발견했으며, 이는 Tanh 버전이 풀기에 약간 더 어려운 퍼즐이라는 생각과 일치했습니다.

마법 같은 연결 고리: 코드 복잡도가 성능을 예측한다

진정한 마법은 이 코드 점수와 서로 다른 알고리즘이 실제로 수행한 성과를 비교할 때 일어납니다. 그들은 24개의 문제를 풀기 위해 다섯 가지 서로 다른 "로봇" 알고리즘의 데이터를 살펴보았습니다.

그들은 명확한 패턴을 발견했습니다: 코드가 더 복잡할수록, 로봇의 성과는 더 나빠졌습니다.

이는 음(-)의 관계입니다. 코드가 단순할 때(낮은 할스테드 부피), 로봇은 문제를 빠르고 쉽게 해결했습니다. 코드가 복잡할 때(높은 할스테드 부피), 로봇은 고전하거나, 시간이 오래 걸리거나, 혹은 막혔습니다. 예를 들어, 5차원 문제에서 코드 복잡도와 낮은 성과 사이의 연결 고리는 상당히 강력했습니다.

하지만 저자들은 이것이 완벽한 수정구슬은 아니라는 점을 주의 깊게 언급합니다. 코드는 매우 복잡하지만 로봇의 성과가 코드에서 암시하는 것만큼 나쁘지 않았던 몇몇 "예외적인(outlier)" 문제들이 있었습니다. 이는 코드 복잡도가 훌륭한 힌트는 될 수 있지만, 그것만이 유일하게 중요한 요소는 아니라는 점을 시사합니다.

이것이 왜 중요한가

이 접근 방식의 아름다움은 믿을 수 없을 정도로 빠르고 추가적인 작업이 필요 없다는 점입니다. 문제를 이해하기 위한 전통적인 방법들은 종-종 지형이 어떻게 생겼는지 확인하기 위해 알고리즘을 수천 번 실행해야 합니다. 이는 마치 지도를 그리기 위해 정찰병을 보내 미로 전체를 걷게 하는 것과 같습니다.

반면, 저자들의 방식은 미로의 설계도를 보는 것과 같습니다. 문제를 한 번도 실행하지 않고도 순식간에 코드의 복잡도를 계산할 수 있습니다. 이 방식은 문제의 크기나 차원이 얼마나 되는지에 상관하지 않습니다. 오직 명령의 구조만을 봅니다.

저자들은 이 새로운 "코드 복잡도" 측정법이 알고리즘을 설계하는 과학자들의 도구 상자에 도움이 될 수 있는 유용한 추가 요소가 될 수 있다고 제안합니다. 이것은 문제를 바라보는 기존의 방식들을 대체하는 것이 아니라, 문제를 풀기도 전에 그 문제가 얼마나 어려울지 짐작할 수 있는 새롭고 초고속인 방법을 더해주는 것입니다. 이는 단순히 명령어를 읽는 것만으로도 컴퓨터가 적절한 도구를 선택할 수 있도록 돕는 유망한 단계입니다.

기술 요약: 프로그래밍적 표현을 이용한 최적화 문제의 특성 규명

문제 정의
최적화 문제 인스턴스의 특성을 규명하는 것은 알고리즘의 동작을 이해하고, 알고리즘 선택을 용이하게 하며, 최적화 도구를 설정하는 데 있어 매우 중요하다. 탐색 공간을 샘플링하여 특징을 추출하는 탐색적 경관 분석(Exploratory Landscape Analysis, ELA)과 같은 기존 방식들은 실질적인 한계에 직면해 있다. 이러한 방법들은 비용이 많이 드는 목적 함수 평가를 소모하며, 샘플 크기와 전략에 민선하며, 복잡한 경관(landscape)에 대한 강건한 표현을 제공하지 못할 수 있다. 더욱이, 서로 다른 특징 집합들은 중복된 정보보다는 상호 보완적인 정보를 제공하는 경우가 많으므로, 다양한 특성 규명 접근 방식이 필요하다.

방법론
저자들은 탐색 공간을 샘플링하는 대신, 목적 함수의 **프로그래밍적 표현(programmatic representation)**을 기반으로 최적화 문제를 특성화하는 새로운 접근 방식을 제안한다. 핵심적인 직관은 목적 함수를 구현하는 데 필요한 코드의 복잡성이 결과적인 탐색 경관의 복잡도와 상관관계가 있다는 것이다. 단순한 수학적 구조는 단순한 코드를 생성하고 매끄러운 경관을 만드는 반면, 복잡한 함수는 더 길고 연산자가 많은 코드를 필요로 하며 불규칙한 경관을 나타낸다.

본 연구는 소프트웨어 공학 및 정보 이론에서 유래한 두 가지 특정 측정치를 활용한다:

할스테드 부피 (Halstead Volume, $V_H$ ): $V_H = (N_1 + N_2) \log_2(\eta_1 + \eta_2)$ 로 정의되는 프로그램 크기 및 복잡도의 척도이다. 여기서 $N$ 은 연산자/피연산자의 총 개수를, $\eta$ 는 고유한 연산자/피연산자의 개수를 나타낸다.
샤논 엔트로피 (Shannon Entropy, $H$ ): 토큰당 정보량을 나타내며, 전체 토큰 수( $N$ )에 의해 스케일링된다. 저자들은 균등 확률 가정 하에 $H$ 가 $V_H$ 에 근사한다고 언급하였다.

이러한 지표들은 목적 함수의 소스 코드(구체적으로 C 구현체)로부터 정적으로 계산된다. 본 연구는 다음을 대상으로 이 지표들을 평가하였다:

BBOB (Black-Box Optimisation Benchmarking) 무노이즈 테스트 스위트 (24개 함수).
신경망 가중치 최적화 과업 (ReLU 및 Tanh 활성화 함수를 사용하는 피드 포워드 네트워크 학습).

주요 기여 및 결과

정적, 샘플링 불필요 특성 규명: 제안된 방법은 탐색 공간의 샘플링이나 목적 함수 평가를 요구하지 않는다. 이는 변환(예: 회전, 컨디셔닝)에 대해 불변하며, 문제 차원(차원은 코드 구조 내에서 루프 횟수 또는 단일 피연산자로 취급됨)에 대해서도 불변이다.
알고리즘 성능과의 상관관계: BBOB 스위트에 적용했을 때, 할스테드 부피와 엔트로피는 알고리즘 성능(경험적 누적 분포 함수의 정규화된 AUC로 측정됨)과 음의 상관관계를 갖는 것으로 나타났다.
- 높은 복잡도 값(예: $f_{24}$ , Lunacek bi-Rastrigin)은 낮은 알고리즘 성능과 대응하였다.
- 낮은 복잡도 값(예: $f_1$ , Sphere)은 높은 알고리즘 성능과 대응하였다.
- 스피어만 순위 상관 계수는 테스트된 모든 알고리즘(dCMA, COBYLA, DE, mCMA, L-SHADE)과 차원(2D 및 5D)에서 음수였으나, 상관관계의 강도는 약함에서 중간 정도로 다양하게 나타났다.
문제 유형의 차별화: 이 지표들은 문제 클래스를 성공적으로 구분하였다. 예를 들어, 신경망 학습에서 복잡도 지표는 ReLU와 Tanh 활성화 함수를 사용하는 네트워크를 구분하였는데, 이는 특정 회귀 과업이나 네트워크 크기와 독립적으로 활성화 함수가 경관 특징의 핵심 구별 요소라는 기존의 연구 결과와 일치한다.
관찰된 한계점: 해당 지표들은 코드 구조를 크게 변화시키지 않는 특정 문제 파라미터, 예를 들어 Gallagher 함수( $f_{21}, f_{22}$ )의 피크(peak) 수나 문제의 차원을 포착하지 못했다. 또한, 매우 높은 $V_H$ 값을 가진 이상치(예: $f_7, f_{21}, f_{22}, f_{24}$ )의 경우, 복잡도 대 성능의 산점도에서 명확한 경향성을 보이지 않았다.

의의 및 주장
본 논문은 이러한 프로그래밍적 복잡도 측정을 기존의 경관 분석 방식의 대체재가 아닌 보완재로 위치시킨다. 저자들은 이 접근 방식이 다음과 같은 뚜렷한 장점을 제공한다고 주장한다:

효율성: 자동으로 매우 빠르게 계산할 수 있다.
불변성: 탐색 공간의 변환에 불변하며 샘플링 전략에 의존하지 않는다.
예측 잠재력: 알고리즘 성능과의 음의 상관관계는 이러한 지표들이 알고리즘 선택 및 설정을 위한 **예측 메타 특징(predictive meta-features)**으로서 잠재력이 있음을 시사한다.

저자들은 프로그래밍적 표현이 성능과 관련된 문제의 모든 속성을 포착할 수는 없지만, 샘플링의 계산 오버헤드를 피하면서 독특하고 정적인 관점을 제공한다고 결론짓는다. 그들은 향후 연구에서 광범이한 코드 실행을 포함하는 실제 문제(예: 수치 시뮬레이션)에 이 지표들을 적용하고, 알고리즘 선택 "위저드(wizard)"를 개선하는 데 이들의 유용성을 조사해야 한다고 제안한다.

수정구슬로서의 코드

실험: 단순한 원에서 혼돈의 봉우리까지

마법 같은 연결 고리: 코드 복잡도가 성능을 예측한다

이것이 왜 중요한가

유사한 논문