AlphaEvolve
AlphaEvolve는 2025년에 구글에서 어려운 수학/코딩 최적화/칩설계 문제를 LLM으로 해결하기 위해 제안한 Evolutionary Search기반의 코딩에이전트이다.
아래에서 원문을 읽어볼 수 있다.
https://arxiv.org/abs/2506.13131
'Evolve'라는 이름이 시사하는 것처럼, AlphaEvolve의 전략은 Evolutionary Search이다. 여러 프로그램이 경쟁하여, 높은 점수를 받은 프로그램들이 살아남는다. 그리고 살아남은 프로그램들을 가지고 LLM이 수정해서 (변이) 새로운 child 프로그램들을 낳는다.
이 포스트에서는 AlphaEvolve의 원리와 구현, 그리고 실제 어려운 문제에의 적용까지 살펴볼 것이다. 내가 알기로는 AlphaEvolve는 오픈소스가 아니다. 따라서 아래의 코드는 claude와 논문을 읽으며 독립적으로 구현한 것이다. 따라서 저자들의 구현과 다른 부분이 있을 수 있다.
이 포스트는 주인장의 공부기록일 뿐, 전문적인 튜토리얼로 사용될 수 없습니다. 틀린 내용은 댓글로 지적 바랍니다.
Seed(Initial Program)
진화의 시작은 최초의 조상부터이다. 태초의 프로그램은 아주 멍청하다. 예를 들어, 박스 안에 구 여러개를 쌓으려면 어떻게 쌓아야 가장 많이들어갈까..라는 문제라면 태초의 프로그램은 그냥 네모네모하게 쌓는다. 또 convolution을 사용한 O(NLogN)풀이가 필요한 어려운 프로그래밍대회문제는 그냥 naive dp로 O(N^2)에 푸는 프로그램이 씨앗이 될 수 있다.
중요한 것은 이 Initial Program이 진화의 시작점이 된다는 것이다. Initial Program의 퀄리티나 다양성(꼭 하나의 Initial Program을 넣으라는 법도 없어 보인다)이 최종 결과에 미치는 영향을 보는것도 재밌을것 같다.
Mutation = Rewrite
Parent program이 있다. 자식 프로그램은 parent program을 이래저래 패치한 버전이다. 패치 또는 rewrite는 llm이 담당한다. llm은 parent program의 소스코드를 input으로 받는다. 소스코드에는 주석으로 해당 코드의 핵심 'idea'가 쓰여있다.llm은 소스코드를 읽고 아이디어를 소화한다. 그리고 어디를 수정할지 결정한다.
추상적인 설명보다 input과 output을 딱 보고싶은 이과 독자들을 위해 바로 prompt로 넘어가보겠다.
================================================================================
SYSTEM PROMPT
================================================================================
You are an expert scientist and software engineer. Your task is to iteratively improve the program below so that it scores as highly as possible on the evaluation metrics described. You will be shown the current program, its score, and optionally some other high-performing or diverse programs for inspiration. Propose ONE focused, creative change per turn rather than a grab-bag of unrelated tweaks. Ground your proposal in the problem context and in what has and hasn't worked so far.
You must rewrite the code inside each EVOLVE-BLOCK-START / EVOLVE-BLOCK-END region from
scratch. Reply with one fenced code block per EVOLVE-BLOCK region, in the same order they
appear in the current program, each containing the FULL new content for that region (do
not include the EVOLVE-BLOCK-START/END marker lines themselves).
Before the code block(s), write 1-3 sentences explaining the idea behind your change.
Example (single region):
I'll replace the constant heuristic with a greedy nearest-neighbor search.
```python
def heuristic(state):
return greedy_nearest_neighbor(state)
``
================================================================================
USER PROMPT
================================================================================
# Problem
# AtCoder Regular Contest 223 F - Zonal Score Maximization
**Time limit: 4 seconds.** Memory limit: 1024 MB (AtCoder default; not independently confirmed).
Source: https://atcoder.jp/contests/arc223/tasks/arc223_f
## Problem statement
Define the *score* of a sequence of length 2 or more as the sum of its maximum and
minimum values.
For a positive-integer sequence `A` of length 2 or more, let `f(A)` be the maximum
possible total score obtainable by partitioning `A` into one or more contiguous
subsequences, each of length 2 or more, and summing the score of each part.
You are given an integer sequence `Q = (Q_1, ..., Q_N)` of length `N`, where each
`Q_i` is either an integer in `[1, N]` or `-1`, and a positive integer `X`.
Count, modulo `998244353`, the number of permutations `P = (P_1, ..., P_N)` of
`(1, 2, ..., N)` such that:
- for every `i` with `Q_i != -1`, `P_i == Q_i` (positions with `Q_i == -1` are free);
- `f(P) == X`.
Solve `T` independent test cases per input.
# Current program
This is the program you must improve. Propose a modification to it below.
--- Current program (score=998.917, metrics: combined_score=998.917, correctness_fraction=0.994949, files_passed=4, files_total=6, speed_bonus=3.96756, max_elapsed=6.0087) ---
// ARC223 F - Zonal Score Maximization (see problem.md)
//
// This is a deliberately naive, straightforward starting point: it uses the same
// high-level characterization (N even is trivial; N odd reduces to counting
// permutations by a min-of-medians threshold, via a 0/1 indicator sequence B_i =
// [P_i >= p] that must satisfy a local window constraint) but computes the count
// with a direct O(N) x O(N) dynamic program over (previous two B-values, running
// ones-count) instead of any generating-function / convolution trick. This is
// correct for all N, but its O(N^2) per-threshold cost is far too slow for the
// large end of the constraints (N, sum N <= 1e5, T <= 1e5) - there is a lot of
// room to do better.
// EVOLVE-BLOCK-START
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
vector<ll> fact;
void precompute_factorials(int maxn) {
fact.assign(maxn + 1, 1);
for (int i = 1; i <= maxn; i++) fact[i] = fact[i - 1] * i % MOD;
}
// #{permutations P consistent with Q : min-of-medians M(P) >= p}, via a direct
// O(N^2) DP over B-patterns (no generating functions).
ll count_at_least(const vector<int>& Q, ll p, int n) {
int c = 0;
for (int v : Q) if (v == -1) c++;
if (p <= 1) return fact[c];
if (p > n) return 0;
auto forced = [&](int pos1indexed) -> int { // -1 = free, else forced 0/1
int v = Q[pos1indexed - 1];
if (v == -1) return -1;
return (v >= p) ? 1 : 0;
};
// dp[bprev][bcur][k]: ways to assign B_1..B_j so far (j = current position),
// with B_{j-1}=bprev, B_j=bcur, exactly k ones total, and every COMPLETED
// window (i.e. every window fully within 1..j) satisfied. Shape is explicitly
// 2 x 2 x (n+1) -- NOT vector<array<array<ll,2>,2>>(n+1,...), which puts n+1 in
// the wrong (outer) slot and silently overruns the size-2 inner dimension.
auto make_dp = [&]() {
return vector<vector<vector<ll>>>(2, vector<vector<ll>>(2, vector<ll>(n + 1, 0)));
};
vector<vector<vector<ll>>> dp = make_dp();
int f1 = forced(1);
for (int b1 = 0; b1 < 2; b1++) {
if (f1 != -1 && b1 != f1) continue;
dp[0][b1][b1] = 1; // bprev=0 placeholder for j=1 (no real predecessor yet)
}
..(너무길어서 중략)
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
precompute_factorials(100000);
int T;
cin >> T;
while (T--) {
int n;
ll X;
cin >> n >> X;
vector<int> Q(n);
for (int i = 0; i < n; i++) cin >> Q[i];
cout << solve_case(n, X, Q) << "\n";
cout.flush();
}
return 0;
}
// EVOLVE-BLOCK-END
# Task
Suggest one focused idea to improve the current program's score, informed by the problem description and, if useful, the inspiration programs. Rewrite the EVOLVE-BLOCK region(s) in full.
-
system prompt: 과학자/소프트웨어 엔지니어로써의 역할을 부여하고, 주어진 코드의 EVOLVE-BLOCK-START와 EVOLVE-BLOCK-END 사이를 rewrite하도록 지시한다.
-
user prompt: 해결하려는 문제와 현재 코드
- Problem: 해결하려는 문제에 대한 설명. 이경우에는, 지난달 Atcoder 프로그래밍 대회의 F번을 풀라고 시켜봤다.
- Current Program: llm이 개선해야 하는 대상 프로그램. 'Parent' 라고 부른다
- Task:EVOLVE-BLOCK-START/END 사이를 다시 쓰라는 지시사항을 반복한다.
실제로 위 프롬프트를 Deepseek V4-Flash/Pro에 먹인 결과 아래와 같은 응답을 받았다
================================================================================
RAW LLM RESPONSE
================================================================================
The current O(N²) DP is too slow for large N. The key realization is that the binary constraint (every window of length 3 with odd starting index must have at least 2 ones) can be counted using a transfer-matrix / automaton approach with generating functions instead of tracking the full count dimension. Since no ones are forced except by the threshold pattern, the count of valid B-sequences with a given number of ones is a **binomial coefficient**, because the constraint only couples adjacent positions in a linear chain (a 2-state automaton).
Specifically: for odd N, valid B-patterns are exactly those where B_1, B_3, B_5, ... form an arbitrary sequence, and each B_{2k} (even position) is forced to equal B_{2k-1} OR B_{2k+1}? Actually let's derive: windows are (1,2,3), (3,4,5), ... each must have ≥2 ones. This is equivalent to: for each odd i, at least 2 of {B_i, B_{i+1}, B_{i+2}} are 1. This is a local constraint that can be counted with a DP over just the previous bit, but the number of ones is still needed for the threshold. However, we can use a generating function: the transfer matrix for the automaton is a 2×2 matrix of polynomials in x, and the final count of patterns with exactly k ones is the coefficient of x^k in the product of these matrices (with initial/final states). This can be computed via polynomial multiplication, but the polynomial degree is O(N), and multiplying two degree-N polynomials takes O(N log N) with NTT.
Given the time constraints and that N ≤ 1e5, I'll implement a fast O(N log N) approach using NTT-based polynomial exponentiation of a 2×2 matrix. But this is complex.
A simpler but effective improvement: since the constraint is local and the positions are independent given the odd positions, we can count **valid B-patterns** as follows: For each odd index i, the triple (B_i, B_{i+1}, B_{i+2}) must have ≥2 ones. This is a constraint between consecutive odd positions (via the shared even position). In fact, the sequence of odd-position bits determines the even bits: B_{2k} can be 0 or 1 freely, but it must satisfy all windows it belongs to. For window starting at odd i=2k-1, it involves B_{2k-1}, B_{2k}, B_{2k+1}. So given the odd bits, each even bit B_{2k} must be ≥ (2 - B_{2k-1} - B_{2k+1}) if that is positive. This is a simple condition that can be counted combinatorially.
Let me implement an O(N) per threshold DP that tracks only the previous bit and the count of ones (still O(N²) worst-case), but with a major optimization: instead of running the full DP for each threshold p, we can precompute a polynomial `G(x) = sum_{valid patterns} x^{number of ones}` for the unrestricted case (no forced positions), then for each test case we only need to adjust for the forced positions. However, forced positions break the translation invariance.
Given the complexity, a more practical improvement: use a faster DP that doesn't allocate a new (n+1)-sized vector for each of the 4 states each iteration, but instead uses two flat arrays and iterates only over reachable k values. Also, we can reduce the number of thresholds computed: we only need p and p+1 where p = total - X. But p can be any value from 2 to n, so still O(N²) in worst case.
A better idea: note that the DP is essentially counting sequences with a local constraint. This can be transformed into a **linear recurrence** on the number of ones. For the unrestricted case (no forced), the number of valid B-patterns with exactly k ones is a known combinatorial sequence: it's the number of ways to place k ones such that every odd-starting window of length 3 has at least 2 ones. This is equivalent to: no two consecutive zeros? Actually, with windows (1,2,3), (3,4,5), ..., the condition is that no window has ≤1 one. That means you cannot have a pattern of 0,0,0 or 0,0,1? Let's analyze: For window (i,i+1,i+2) with i odd, need ≥2 ones. So possible triples: 111, 110, 101, 011. Not allowed: 001, 010, 100, 000. This is a constraint on length-3 blocks that overlap on one position (the middle? no, they overlap on position i+2 = next odd? Actually window (1,2,3) and (3,4,5) share position 3). This is a second-order Markov chain. The number of valid sequences with exactly k ones can be computed via a DP that tracks the last two bits, and the transition is constant. This DP is O(N*K) but can be optimized using a generating function where the transition matrix is a 2×2 matrix of polynomials. For each threshold, the coefficient extraction can be done via polynomial multiplication.
Given the time, I'll propose a change that substantially improves the constant factor: use a flat 2×2×(N+1) array, avoid reallocating each step, and precompute the transition for the "no forced" case to get a closed-form combinatorial count. The key insight: for odd N, valid B-sequences are exactly those where the odd-indexed bits form an arbitrary sequence, and each even-indexed bit is forced to be 1 if both adjacent odd bits are 0, otherwise it can be 0 or 1. This yields a product formula.
Let me derive that more carefully:
For odd N, windows are (1,2,3), (3,4,5), ..., (N-2,N-1,N). Each window (2k-1, 2k, 2k+1) for k=1..(N-1)/2 must have ≥2 ones.
Consider the sequence of odd-indexed bits: O_1=B_1, O_2=B_3, ..., O_m where m=(N+1)/2. The even bits E_k = B_{2k} for k=1..(N-1)/2 connect windows k and k+1 (except edge).
For a given odd-bit sequence, the constraints on even bits are:
- For each k=1..m-1, window k involves O_k, E_k, O_{k+1} → need O_k + E_k + O_{k+1} ≥ 2.
- So E_k must be ≥ max(0, 2 - O_k - O_{k+1}).
If O_k + O_{k+1} ≥ 2, then E_k can be 0 or 1 (2 choices).
If O_k + O_{k+1} = 1, then E_k must be 1 (1 choice).
If O_k + O_{k+1} = 0, then E_k must be 2? But E_k is binary, so impossible. Thus we cannot have consecutive odd bits both 0. So the odd-bit sequence cannot contain "00" (adjacent odd positions).
Therefore valid B-sequences correspond exactly to: an odd-bit sequence O_1..O_m with no consecutive 0s, and for each adjacent pair (O_k,O_{k+1}), the number of choices for E_k is:
- 2 if both are 1 (sum=2)
- 1 if one is 0, one is 1 (sum=1)
- impossible if both 0.
So the number of valid B-sequences with a given odd-bit pattern is 2^(# of adjacent 11 pairs). The total number of ones in B is: sum(O_k) + sum(E_k), where E_k is chosen: if both odd are 1, E_k can be 0 or 1; if one is 1, E_k must be 1.
Now the count for a given threshold p is: sum over odd-bit sequences with no consecutive 0s, and for each such sequence, sum over choices of E_k (which are independent given the odd bits) of the number of patterns that have total ones = target. This is still complex but can be computed via DP over odd positions tracking the previous odd bit and the number of ones, but now the DP has only 2 states (for odd bits) and each step processes one odd position plus one even position. This reduces the DP dimension from 4 states to 2 states, and the number of steps from N to (N+1)/2. Still O(N²) in the count dimension, but with a much smaller constant.
A further improvement: we can use polynomial multiplication to compute the generating function for the number of valid B-patterns with a given number of ones, in O(N log N) using NTT. Since N ≤ 1e5, this is feasible. The transfer matrix for the automaton (state = previous odd bit) is a 2×2 matrix of polynomials in x representing the contribution to the count of ones: going from O_k to O_{k+1}, we include O_k and E_k. The generating function for the whole sequence is the product of these matrices, and the coefficient of x^k gives the number of valid patterns with k ones.
I'll implement this with NTT. But given the complexity, I'll instead implement a simpler but still much faster approach: precompute the DP for the unrestricted case (no forced positions) for all thresholds using a single polynomial multiplication via combinatorial formulas, and handle forced positions by adjusting. However, forced positions break the simple product formula.
Given the constraints and the fact that the current program already passes 4/6 files, the main issue is speed on large N. I'll implement a more efficient DP that uses only 2 states and processes odd positions, reducing the constant factor significantly. This should pass more test cases.
Let me write the improved code.I'll replace the O(N²) 4-state DP with a 2-state DP over odd positions. The key insight: for odd N, valid B-sequences are characterized by the odd-indexed bits (no two consecutive zeros), and each adjacent pair (O_k, O_{k+1}) gives either 2 choices for the even bit (if both are 1) or 1 choice (if exactly one is 1). This reduces the state space and halves the number of DP steps, dramatically improving speed while keeping the same correctness.
```cpp
// ARC223 F - Zonal Score Maximization
// Improved: 2-state DP over odd positions, O(N^2) per threshold but with ~4x fewer states and steps.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
vector<ll> fact;
void precompute_factorials(int maxn) {
fact.assign(maxn + 1, 1);
for (int i = 1; i <= maxn; i++) fact[i] = fact[i - 1] * i % MOD;
}
...(코드는 너무 길어서 중략)...
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
precompute_factorials(100000);
int T;
cin >> T;
while (T--) {
int n;
ll X;
cin >> n >> X;
vector<int> Q(n);
for (int i = 0; i < n; i++) cin >> Q[i];
cout << solve_case(n, X, Q) << "\n";
}
return 0;
}이 특정 응답의 경우, NTT(푸리에변환에 기반한 convolution 쓰려고..)라는 방향을 비교적 빠르게 잡아냈다.
Given the time constraints and that N ≤ 1e5, I'll implement a fast O(N log N) approach using NTT-based polynomial exponentiation of a 2×2 matrix.그러다가 그게 구현이 '너무 복잡하다'며 O(N^2) 복잡도를 유지하는 대신 dp의 constant factor를 개선하겠다고 후퇴하는 모습을 보인다.
실제로 돌려본 결과, 약 1분 후 15번째 generation에서 DeepSeek V4 Pro모델이 NTT가 꼭 필요함을 인지하고, 맞는 코드를 생성했다.
구현된 코드는, 클로드 코드(Sonnet)가 해설을 보고 구현한 코드보다 빨랐다.
llm이 parent program을 rewrite하는 단계는 진화의 핵심고리(변이)에 해당하지만,아직 '경쟁'과 '선택 압력'이라는 요소는 언급하지 않았다.
이제 evolution을 drive하는 선택압을 시뮬레이션하는 코드를 살펴보자.
Local Competition with MAP-Elites
가장 간단한 선택 모델은 global competition이다. 모든 개체가 다른 모든 개체와 경쟁하여 조금이라도 더 score가 높은 개체가 살아남는다.
하지만 global competition은 local optima 에 빠질 가능성이 높다. 다른 블로그에서 이런 문장을 본적이 있다: 아프리카의 치타가 남극의 펭귄과 경쟁하지는 않는다. 실제 자연에서는 경쟁이 local하다. 비슷한 지역에서 살아가고, 같은 시간에 깨어있고, 비슷한 먹이를 먹는 개체들끼리 경쟁한다.
이러한 local competition은 서로 다른 종류의 개체들끼리 경쟁을 제한하여, 저마다의 다양한 생존 방식을 존중한다. 조금 더 score가 높은 프로그램이, 아예 다른 방식으로 동작하는 프로그램이 생존할 기회를 박탈하지 못하게 한다.
local competition은 Program들의 'multidimensional grid'로 구현한다. grid의 각 차원은 어떤 behavioural trait에 대응한다. 코드의 경우, 코드의 길이와 실행시간이 서로 다른 두 축이 될 수 있겠다. 신약 개발의 경우, 분자량과 원료의 가격이 두 축이 될 수 있다. 반도체 설계의 경우, 게이트 개수와 delay가 축이 될 수 있다.
각 차원을 적당히 몇개의 구간으로 쪼개서 만들어진 각 칸들을 cell이라고 부른다. 경쟁은 같은 cell안의 프로그램끼리 한다. 새로 만들어진 프로그램이 이미 그 cell에 있던 기존의 best program보다 나으면, 기존 프로그램을 제치고 해당 셀의 새로운 Elite가 된다.
이것이 local competition을 구현하는 방식은, 다른 grid cell에 있는 프로그램은 건드리지 않는다는 것이다. 다른 grid cell의 프로그램은 나와 성질이 다른 것이다. 비록 나보다 느릴지언정, 길이가 더 짧거나(->구현 버그 확률을 낮춰주고 유지보수를 쉽게한다), 메모리를 적게 먹는다거나, 병렬화가 가능하다든가.. cell안에서의 local경쟁은,이런 성질이 다른 프로그램이 생존할 수 있게 돕는다.
(출처 https://github.com/jbmouret/map_elites_tutorial)
그리드에 새로운 프로그램을 더하는 코드는 아래와 같다.
def add(self, program: Program) -> bool:
"""Add a scored program to its island's MAP-Elites grid.
Returns True if the program became the elite of its cell.
"""
if program.combined_score is None:
raise ValueError("cannot add an unscored program to the database")
self.all_programs[program.id] = program
self._update_score_range(program.combined_score)
island = self.islands[program.island_idx % len(self.islands)]
cell = self._cell(program) //이 프로그램이 들어갈 셀을 계산한다.
incumbent = island.get(cell)
became_elite = incumbent is None or program.combined_score > incumbent.combined_score //점수로 비교해서 기존보다 나은지 본다.
if became_elite:
island[cell] = program //해당 셀을 업데이트한다.
if self.best_program is None or program.combined_score > self.best_program.combined_score:
self.best_program = program
return became_elite위 방식은 근본없는 휴리스틱이 아니라, MAP-Elites라는 논문에서 제시한 방법이다. 관심이 있다면 아래 논문을 읽어보자.
https://arxiv.org/abs/1504.04909
Database of Islands
우리의 프로그램 데이터베이스에는 그리드가 한개만 있는게 아니다. 'island(섬)'가 여러개 있고,각 island마다 저마다의 grid를 가지고 있다.
중고등학교때 배운 진화론을 떠올려보면 뭐 마다가스카르는 육지와 떨어져 있어서 독립적인 생태계를 발전시켰으며.. 섬에 사는 새들이 육지와는 다른 부리 모양을 가지고.. 뭐 이런 내용이 기억난다.
아마 여러개의 island도 그런 자연의 특성을 모델링한게 아닐까 싶다. 거의 독립적인 진화를 여러개 병렬적으로 돌린다고 보면 된다. 매 step마다, 어떤 island를 진화시킬지 랜덤으로 결정한다. 이를 통해 score가 지금은 낮은 island라도 진화할 기회를 얻게 된다.
아래 코드는 진화시킬 parent program을 선택하는 코드이다. 보면 island를 먼저 random하게 고르고, island내의 grid에선 score가 높은 프로그램에 높은 가중치를 주어 'hill-climbing'을 유도하는 것을 알 수 있다.
def sample(self) -> tuple[Program, list[Program]]:
"""Pick a parent (weighted sample within a random island) plus inspirations
(the global best, and top elites from a few other islands) for prompt context.
"""
nonempty = [isl for isl in self.islands if isl]
if not nonempty:
raise RuntimeError("database is empty; seed every island before sampling")
island = self.rng.choice(nonempty)
parent = self._weighted_cell_sample(island)
inspirations: list[Program] = []
seen_ids = {parent.id}
if self.best_program is not None and self.best_program.id not in seen_ids:
inspirations.append(self.best_program)
seen_ids.add(self.best_program.id)
other_islands = [isl for isl in self.islands if isl is not island and isl]
self.rng.shuffle(other_islands)
for isl in other_islands:
if len(inspirations) >= self.config.num_inspirations:
break
best_in_island = max(isl.values(), key=lambda p: p.combined_score)
if best_in_island.id not in seen_ids:
inspirations.append(best_in_island)
seen_ids.add(best_in_island.id)
return parent, inspirations[: self.config.num_inspirations]각 island가 완전히 독립적인 것은 아니다. migration(이주)이라는 메커니즘이 존재한다. 새가 한 섬에서 다른 섬으로 씨앗을 물어다주고, 또 날라온 다른 섬의 새와 교배하는 것처럼, 다른 섬끼리도 유전자의 이동이 있다.
migration의 역할은, 한 섬에서 시작된 breakthrough(돌파구/획기적인 개선)가 다른 섬들에도 결국 전파되게 하는 것이다. 그렇다고 너무 migration이 잦으면,모든 섬이 동질화될것이다. 따라서 적절한 migration빈도를 고르는 것이 중요하다.
아래는 migration코드이다.
def migrate(self) -> None:
"""Copy each island's top elites into the next island (ring topology)."""
n = len(self.islands)
if n < 2:
return
snapshots = []
for island in self.islands:
top = sorted(island.values(), key=lambda p: p.combined_score, reverse=True)
snapshots.append(top[: self.config.migration_size])
for i, top in enumerate(snapshots):
target = self.islands[(i + 1) % n]
for program in top:
cell = self._cell(program)
incumbent = target.get(cell)
if incumbent is None or program.combined_score > incumbent.combined_score:
target[cell] = program정리하면 아래 그림과 같다.
마무리
이 포스트에서는 LLM의 코드 수정 능력에 진화 알고리즘을 붙여, 정말 어려운 문제에 대한 솔루션을 단계적으로 진화시켜나가는 AlphaEvolve모델의 개념과 구현에 대해 알아보았다.
다음 포스트에서는, '어려운 문제'가 에이전트 외부에 존재하는 것이 아니라, '에이전트 자기 자신을 개선하는 것'일때 어떤 일이 일어나는지 다뤄보겠다.
달콤즈 메모리즈 git @AliceOfSNU, 백준 dalcomi20