Генетическое программирование

В генетических алгоритмах особь — это вектор фиксированной длины: 30 бит, 12 вещественных чисел, перестановка из 50 городов. Мы заранее знаем форму ответа и ищем только его содержание.

Генетическое программирование (GP) снимает это ограничение. Особь — это исполняемая структура переменного размера: выражение, функция, программа, регулярка, схема, конфигурация. Мы не знаем заранее ни длину ответа, ни его форму — эволюция придумывает и то и другое.

Разница фундаментальнее, чем кажется. GA отвечает на вопрос «какие параметры лучше?». GP отвечает на вопрос «какая программа решает эту задачу?» — то есть занимается автоматическим программированием методом проб и отбора. Именно поэтому GP стал двигателем самых эффектных результатов SBSE: автоматического исправления багов, синтеза эвристик, обнаружения физических законов из данных.

Интуиция: почему деревья

Возьмём задачу символьной регрессии: даны точки (x, y), найти формулу y = f(x). Обычная регрессия ищет коэффициенты при заранее заданной формуле (y = ax + b). Символьная регрессия ищет саму формулу — и её структуру, и её константы.

Как представить формулу так, чтобы её можно было случайно менять и скрещивать, и чтобы результат оставался синтаксически корректным? Строка символов не годится: разрежьте x*(y+2) пополам — получите x*(y — мусор. Нужно представление, замкнутое относительно операторов.

Ответ Джона Козы (1992): дерево разбора. Любое поддерево — само по себе валидное выражение. Значит, можно вырезать поддерево из одной программы и вставить на место поддерева в другой — и обе останутся корректными. Это ключевое свойство, на котором держится весь GP.

Два множества, которые решают всё

Перед запуском GP вы задаёте ровно две вещи, и это 80% успеха. Функциональное множество F — внутренние узлы: + − * / sin exp if-then-else and or и любые доменные операции (read_sensor, move_forward, sql_join). Терминальное множество T — листья: переменные задачи (x, y), константы, функции без аргументов (random, time()).

К ним предъявляются два требования из книги Козы:

1. Замкнутость (closure). Любая функция из F должна корректно принимать любое значение, которое может вернуть любой узел. Классическая ловушка — деление: x / 0. Решение — защищённые операции: pdiv(a,b) = a/b if |b|>ε else 1.0, plog(a) = log(|a|+ε). Альтернатива — типизированный GP (см. ниже), где типы не дают собрать бессмысленное выражение.
2. Достаточность (sufficiency). В F∪T должно существовать выражение, решающее задачу. Если целевая функция содержит sin, а в F только + − *, GP будет вечно строить ряды Тейлора чудовищного размера. Недостаточное множество — самая частая причина «GP не работает».

Есть и обратная опасность: чем больше F, тем больше пространство поиска. Каждая лишняя функция экспоненциально раздувает число деревьев заданной глубины. Правило практика: начинайте с минимального F, расширяйте только когда упёрлись.

Инициализация популяции

Три классических метода Козы: full (все ветви растут до максимальной глубины d, деревья плотные и одинаковые по форме), grow (узел на каждом уровне с некоторой вероятностью становится листом, деревья разнообразные и часто мелкие) и ramped half-and-half — популяция делится на группы с глубинами 2..d, в каждой половина строится full, половина grow. Последний — де-факто стандарт: даёт максимальное структурное разнообразие старта.

Почему разнообразие критично именно здесь? В GP нет мутации, способной «удлинить хромосому» так же плавно, как в GA. Если стартовая популяция состоит из мелких однотипных деревьев, кроссовер долго не сможет собрать нужную структуру — популяция сойдётся раньше, чем найдёт форму ответа.

Операторы: subtree crossover и его родня

Subtree crossover — главный оператор GP. В каждом родителе выбирается случайный узел, поддеревья обмениваются. Обратите внимание: размеры потомков отличаются от размеров родителей. Это источник и силы GP (он сам находит нужную сложность), и его главной болезни (раздувания).

Важная деталь реализации, которую все повторяют со времён Козы: 90/10 bias. Точка реза выбирается среди внутренних узлов с вероятностью 0.9 и среди листьев — с 0.1. Без этого смещения, поскольку в бинарном дереве листьев примерно половина, большинство «кроссоверов» сводилось бы к обмену одиночными переменными — то есть к точечной мутации, а не к обмену блоками функциональности.

Последний пункт стоит подчеркнуть. Чистый GP катастрофически неточен в константах: он найдёт структуру x³ − c·x² + sin(x), но c будет 0.49 вместо 0.5. Все современные системы символьной регрессии — гибриды: GP ищет структуру, а численный оптимизатор (Левенберг—Марквардт, BFGS) доводит коэффициенты. Это прямая аналогия с мемитическими алгоритмами из статьи про локальный поиск.

Полный цикл

Реализация с нуля: символьная регрессия

Ниже — рабочий GP на чистом Python, без библиотек. Задача: восстановить f(x) = x³ − 0.5x² + sin(x) по 51 точке на отрезке [−2.5, 2.5], зная только + − * / sin и константы.

Дерево представлено списком [Fn, потомок, ...]; лист — строка (переменная) или число. Такое представление компактно и позволяет персистентную замену поддерева: новое дерево разделяет неизменённые ветви со старым.

import math
import operator
import random
from dataclasses import dataclass
from typing import Callable, Iterator

# ---------- 1. Примитивы: функциональное и терминальное множества ----------

@dataclass(frozen=True)
class Fn:
    name: str
    arity: int
    call: Callable[..., float]

def pdiv(a: float, b: float) -> float:
    """Защищённое деление: гарантирует замкнутость (closure)."""
    return a / b if abs(b) > 1e-9 else 1.0

def psin(a: float) -> float:
    return math.sin(a) if abs(a) < 1e6 else 0.0

FUNCS = [Fn("+", 2, operator.add), Fn("-", 2, operator.sub),
         Fn("*", 2, operator.mul), Fn("/", 2, pdiv), Fn("sin", 1, psin)]
VARS = ["x"]

# Node := [Fn, потомок, ...] | str (переменная) | float (константа)

def rand_terminal(rng: random.Random):
    if rng.random() < 0.7:
        return rng.choice(VARS)
    return round(rng.uniform(-3.0, 3.0), 2)

# ---------- 2. Инициализация: full / grow / ramped half-and-half ----------

def gen_full(rng, depth):
    if depth == 0:
        return rand_terminal(rng)
    f = rng.choice(FUNCS)
    return [f] + [gen_full(rng, depth - 1) for _ in range(f.arity)]

def gen_grow(rng, depth, p_term=0.35):
    if depth == 0 or rng.random() < p_term:
        return rand_terminal(rng)
    f = rng.choice(FUNCS)
    return [f] + [gen_grow(rng, depth - 1, p_term) for _ in range(f.arity)]

def ramped_half_and_half(rng, n, dmin=2, dmax=6):
    pop = []
    while len(pop) < n:
        d = rng.randint(dmin, dmax)
        pop.append(gen_full(rng, d) if len(pop) % 2 == 0 else gen_grow(rng, d))
    return pop

# ---------- 3. Интерпретация и метрики дерева ----------

def evaluate(node, env) -> float:
    if isinstance(node, list):
        f = node[0]
        args = [evaluate(c, env) for c in node[1:]]
        try:
            v = f.call(*args)
        except (OverflowError, ValueError, ZeroDivisionError):
            return 1e12                       # «бесконечно плохо», но не падение
        return max(-1e12, min(1e12, v))       # обрезка: без неё inf/nan заражают фитнес
    if isinstance(node, str):
        return env[node]
    return node

def size(node) -> int:
    return 1 + sum(size(c) for c in node[1:]) if isinstance(node, list) else 1

def depth(node) -> int:
    return 1 + max(depth(c) for c in node[1:]) if isinstance(node, list) else 1

def render(node) -> str:
    if not isinstance(node, list):
        return str(node)
    f = node[0]
    return (f"({render(node[1])} {f.name} {render(node[2])})" if f.arity == 2
            else f"{f.name}({render(node[1])})")

# ---------- 4. Адресация узлов: путь как кортеж индексов ----------

def walk(tree, path=()) -> Iterator[tuple]:
    yield path, tree
    if isinstance(tree, list):
        for i, child in enumerate(tree[1:], start=1):
            yield from walk(child, path + (i,))

def at(tree, path):
    for i in path:
        tree = tree[i]
    return tree

def replace(tree, path, sub):
    """Персистентная замена: возвращает НОВОЕ дерево, оригинал не трогает."""
    if not path:
        return sub
    node = list(tree)                          # копируем только узлы по пути
    node[path[0]] = replace(tree[path[0]], path[1:], sub)
    return node

def pick_point(rng, tree, p_internal=0.9):
    """Смещение Козы: 90% — внутренние узлы, 10% — листья."""
    paths = [p for p, n in walk(tree)]
    internal = [p for p, n in walk(tree) if isinstance(n, list)]
    if internal and rng.random() < p_internal:
        return rng.choice(internal)
    return rng.choice(paths)

# ---------- 5. Операторы ----------

MAX_DEPTH = 17          # исторический лимит Козы

def crossover(rng, a, b):
    pa, pb = pick_point(rng, a), pick_point(rng, b)
    child = replace(a, pa, at(b, pb))
    return child if depth(child) <= MAX_DEPTH else a      # откат при переросте

def subtree_mutation(rng, t):
    p = pick_point(rng, t)
    child = replace(t, p, gen_grow(rng, rng.randint(1, 3)))
    return child if depth(child) <= MAX_DEPTH else t

def point_mutation(rng, t, p_node=0.15):
    """Точечная мутация: меняем символ, сохраняя арность и форму дерева."""
    def rec(n):
        if isinstance(n, list):
            f = n[0]
            if rng.random() < p_node:
                f = rng.choice([g for g in FUNCS if g.arity == f.arity])
            return [f] + [rec(c) for c in n[1:]]
        return rand_terminal(rng) if rng.random() < p_node else n
    return rec(t)

def hoist_mutation(rng, t):
    """Поднимаем случайное поддерево в корень — дешёвое средство против bloat."""
    return at(t, pick_point(rng, t))

# ---------- 6. Фитнес ----------

def target(x):
    return x * x * x - 0.5 * x * x + math.sin(x)

CASES = [(x / 10.0, target(x / 10.0)) for x in range(-25, 26)]

def errors(tree):
    """Вектор ошибок по каждому кейсу — нужен и для MAE, и для lexicase."""
    return [abs(evaluate(tree, {"x": x}) - y) for x, y in CASES]

def fitness(tree, parsimony=0.001):
    e = errors(tree)
    return sum(e) / len(e) + parsimony * size(tree)      # меньше — лучше

# ---------- 7. Селекция ----------

def tournament(rng, pop, fits, k=5):
    idx = min(rng.sample(range(len(pop)), k), key=lambda i: fits[i])
    return pop[idx]

def epsilon_lexicase(rng, pop, err_matrix):
    """Отбор по случайной последовательности отдельных тестов, а не по среднему."""
    cand = list(range(len(pop)))
    cases = list(range(len(err_matrix[0])))
    rng.shuffle(cases)                       # свой порядок кейсов для каждого родителя
    for c in cases:
        col = sorted((err_matrix[i][c], i) for i in cand)
        best, med = col[0][0], col[len(col) // 2][0]
        eps = sorted(abs(v - med) for v, _ in col)[len(col) // 2]  # медианное отклонение
        cand = [i for v, i in col if v <= best + eps]
        if len(cand) == 1:
            break
    return pop[rng.choice(cand)]

# ---------- 8. Главный цикл ----------

def run_gp(seed=7, pop_size=500, generations=40, p_cx=0.8, p_mut=0.15, elite=2):
    rng = random.Random(seed)
    pop = ramped_half_and_half(rng, pop_size)
    best, best_fit = None, float("inf")

    for gen in range(generations):
        fits = [fitness(t) for t in pop]
        for t, f in zip(pop, fits):
            if f < best_fit:
                best, best_fit = t, f
        if gen % 10 == 0:
            avg = sum(size(t) for t in pop) / len(pop)
            print(f"gen {gen:3d}  best={best_fit:.5f}  avg_size={avg:6.1f}")
        if best_fit < 1e-4:
            break

        order = sorted(range(pop_size), key=lambda i: fits[i])
        new = [pop[i] for i in order[:elite]]                     # элитизм
        while len(new) < pop_size:
            r = rng.random()
            if r < p_cx:
                new.append(crossover(rng, tournament(rng, pop, fits),
                                          tournament(rng, pop, fits)))
            elif r < p_cx + p_mut:
                parent = tournament(rng, pop, fits)
                new.append(subtree_mutation(rng, parent) if rng.random() < 0.5
                           else point_mutation(rng, parent))
            else:
                new.append(tournament(rng, pop, fits))            # репродукция
        pop = new
    return best, best_fit


if __name__ == "__main__":
    tree, fit = run_gp()
    print("fitness:", round(fit, 5), "| size:", size(tree), "| depth:", depth(tree))
    print("формула:", render(tree))

Реальный вывод запуска:

gen   0  best=1.39152  avg_size=  18.2
gen  10  best=0.26927  avg_size=  56.4
gen  20  best=0.04967  avg_size=  50.8
gen  30  best=0.03167  avg_size=  35.5
fitness: 0.03167 | size: 10 | depth: 5
формула: ((((x - 0.49) * x) * x) + sin(x))

GP восстановил (x − 0.49)·x·x + sin(x), то есть x³ − 0.49x² + sin(x) — структура целевой функции найдена точно, константа отличается на 0.01. Ровно тот случай, который надо добить численной оптимизацией.

Обратите внимание на avg_size: 18 → 56 → 51 → 35. Штраф за размер (parsimony=0.001) удержал популяцию; уберите его — и к 40-му поколению средний размер уйдёт за несколько сотен узлов при том же качестве.

Сложность

Пусть P — размер популяции, G — число поколений, N — число тестовых кейсов, S̄ — средний размер дерева.

• Оценка одной особи: O(N · S) — интерпретатор обходит дерево на каждом кейсе.
• Поколение: O(P · N · S̄) на фитнес + O(P · S̄) на операторы (walk и depth линейны по дереву).
• Весь прогон: O(G · P · N · S̄) по времени, O(P · S̄) по памяти.

Ключевой множитель здесь — S̄, и он не константа: без контроля bloat он растёт с поколениями, и реальное время оказывается заметно хуже линейного по G. Отсюда практическое правило: любая оптимизация в GP начинается с ограничения размера, а не с микрооптимизаций интерпретатора.

Дальнейшие ускорения по убыванию эффекта: векторизация (считать все N кейсов одним numpy-массивом — 10–100×), кэш семантики по хешу поддерева, подвыборка кейсов на поколение, компиляция дерева в замыкание вместо рекурсивной интерпретации.

Bloat: главная патология GP

Раздувание (bloat) — рост среднего размера программ без улучшения фитнеса. Через 50 поколений вы получаете дерево из 800 узлов, семантически эквивалентное дереву из 12. Это не косметическая проблема: оценка замедляется, память течёт, результат нечитаем, а обобщающая способность падает. Почему это происходит? Два взаимодополняющих объяснения:

1. Защитный код (replication accuracy). Большое дерево содержит интроны — семантически нейтральный код: (* x 1), (+ y 0), (− z z), ветви под всегда-ложным условием. Кроссовер, попавший в интрон, не портит поведение особи, поэтому у больших деревьев выше шанс произвести жизнеспособного потомка — и отбор косвенно вознаграждает размер. Сюда же removal bias: удаление большого поддерева чаще вредит, чем помогает, а вставка большого нейтральна — асимметрия даёт дрейф в сторону роста.
2. Crossover bias (Poli, Langdon, Dignum, 2007) — сегодня главное объяснение. Subtree crossover не меняет средний размер популяции, но сдвигает распределение размеров к распределению Лагранжа второго рода, у которого много очень мелких деревьев. Мелкие деревья почти всегда плохи по фитнесу и отсеиваются — в результате средний размер выживших растёт. То есть bloat возникает даже без всякой «защиты», из чистой комбинаторики оператора.

Контрмеры

Многокритериальный подход сегодня считается наиболее принципиальным: вместо магической константы c вы получаете фронт решений и сами выбираете точку компромисса — именно так устроен PySR.

Селекция: почему в GP турнир — не всегда лучший выбор

Усреднение ошибки по всем тестам теряет информацию. Особь A решает кейсы 1–10 идеально и проваливает 11–20; особь B — наоборот. У обеих средняя ошибка одинакова и посредственна, турнир их не различает — а между тем именно они содержат разные строительные блоки решения.

Lexicase selection (Spector, 2012) чинит это. Для выбора одного родителя:

1. Перемешать список тестовых кейсов.
2. Идти по кейсам, на каждом оставляя только тех кандидатов, кто на нём лучший (для вещественных ошибок — в пределах ε, отсюда ε-lexicase).
3. Остановиться, когда остался один (или кейсы кончились — тогда выбрать случайно из оставшихся).

Селекционное давление разное на каждом выборе родителя: специалист по редкому «трудному» кейсу почти всегда его выигрывает и попадает в родители, хотя по среднему он аутсайдер. Это резко поднимает разнообразие и на задачах с модальной структурой (разные кейсы требуют разной логики — типичный случай для генерации программ) даёт кратный выигрыш над турниром. В коде выше это epsilon_lexicase. Цена: O(P · N) в худшем случае на один выбор родителя против O(k) у турнира, поэтому матрицу ошибок считают один раз на поколение и переиспользуют.

Варианты GP

• Grammar-guided GP / Grammatical Evolution — то, что нужно, когда результат обязан быть валидным кодом на реальном языке или конфигом со схемой: грамматика гарантирует синтаксическую корректность конструктивно, а не проверками постфактум.
• Strongly-typed GP — правильный ответ на проблему замкнутости, когда в задаче есть разнородные типы (число, булево, строка, вектор). Вместо pdiv вы просто запрещаете собрать if(3.14).
• Geometric Semantic GP (Moraglio, Krawiec, Johnson, 2012) — красивая теория: операторы строятся так, что ландшафт фитнеса в семантическом пространстве гарантированно унимодален. Плата: потомок буквально содержит обоих родителей, размер растёт экспоненциально — спасают только представления с разделением структуры.

Эволюция области

Как GP применяют в SBSE и в проде

Автоматический ремонт программ. GenProg (Le Goues и др., 2012) представляет патч как программу-редактор: последовательность операций «удалить/вставить/заменить инструкцию», где новый код берётся из самой программы (гипотеза о том, что нужный фрагмент где-то уже написан). Фитнес — доля пройденных тестов. Это буквально GP над AST. Подробнее — в статье про автоматическое исправление программ.

Генерация тестов. EvoSuite эволюционирует тестовые наборы: особь — набор последовательностей вызовов с параметрами, то есть программа. Кроссовер обменивает подпоследовательности вызовов. См. автоматическую генерацию тестов.

Гипер-эвристики. Вместо того чтобы решать задачу планирования, GP эволюционирует правило приоритета, которое эту задачу решает: priority = processing_time / (due_date − now). Найденное правило потом работает миллисекунды на каждом решении, а обучалось часами один раз. Это доминирующий подход в диспетчеризации цехов и упаковке контейнеров.

Символьная регрессия в науке и инженерии. PySR и Operon находят интерпретируемые формулы там, где нейросеть даёт чёрный ящик: уравнения состояния, поправки к моделям турбулентности, эмпирические законы из данных наблюдений. Ключевой аргумент — не точность, а то, что формулу можно прочитать, проверить на размерность и экстраполировать.

Улучшение существующего кода (Genetic Improvement). GP-правки применяются к реальному репозиторию для ускорения, снижения энергопотребления или размера — при сохранении тестов зелёными; известны кратные ускорения биоинформатических инструментов за счёт правок, которые человек не написал бы, но которые прошли все тесты.

Инструменты, которые стоит знать:

• DEAP — самый гибкий Python-фреймворк, классический gp-модуль с PrimitiveSet; gplearn — символьная регрессия в scikit-learn API для быстрого старта.
• PySR — многопопуляционный GP + оптимизация констант на Julia-бэкенде, сегодня фактический стандарт; Operon — быстрый C++-движок.
• ECJ — зрелый Java-фреймворк (Sean Luke) со справочными реализациями академических вариантов; Jenetics — современная Java-альтернатива.
• SRBench — бенчмарк для честного сравнения методов символьной регрессии.

Типичные ошибки

1. Неверный размер функционального множества — в обе стороны. Если в F нет нужной операции, GP «не сходится» никогда: проверяйте достаточность до того, как крутить параметры. Если насыпали 25 функций «на всякий случай» — пространство поиска выросло на порядки, и каждая лишняя функция замедляет поиск.
2. Игнорирование bloat. Прогон стартует бодро и вязнет к 30-му поколению. Включайте лимит размера с первого запуска, не как оптимизацию потом.
3. Отсутствие валидационной выборки. GP переобучается охотнее большинства методов: достаточно длинное выражение подгонит любые точки. Всегда держите отложенный набор кейсов и выбирайте финальную модель по нему, а не по фитнесу.
4. Мутация в ноль. «Кроссовера достаточно» — нет. В GP кроссовер только перекомбинирует существующие поддеревья; если нужный примитив вымер из популяции, вернуть его может только мутация.
5. Слишком высокое селекционное давление. Турнир размера 15 при популяции 200 убивает разнообразие за 5 поколений, и дальше кроссовер скрещивает клонов. Проявляется как ранний выход на плато.
6. Отсутствие защиты от исключений и NaN. Одно inf в фитнесе — и сравнения ломаются молча. Обрезайте значения, ловите исключения (в коде выше — оба механизма).
7. Оценка «по среднему» на задачах с модальностью. Если разные кейсы требуют разной логики, переходите на lexicase — часто это единственное изменение, которое нужно.
8. Выводы по одному прогону. GP стохастичен: «стало лучше» на одном seed ничего не значит. Минимум 30 повторов и статистический тест (Манна—Уитни + величина эффекта Â₁₂) — стандарт де-факто в SBSE-публикациях.
9. Забыли упростить результат. Финальное выражение почти всегда содержит интроны — прогоните через sympy.simplify перед тем, как показывать людям.

GP и большие языковые модели

Естественный вопрос 2020-х: зачем эволюционировать программы, если LLM их просто пишет? Ответ, который дал FunSearch (Nature, 2023): это не конкуренты, а разные роли в одном цикле. LLM — отличный оператор мутации: он порождает осмысленные, синтаксически корректные, семантически правдоподобные варианты программы, чего случайный subtree crossover не умеет. Но LLM не умеет надёжно оценивать и отбирать — а эволюционный цикл с чётким фитнесом (тесты, метрика, верификатор) умеет именно это. FunSearch заменил случайную мутацию на «попроси LLM переписать эту функцию» и сохранил всё остальное: популяцию, островную модель, отбор по фитнесу — и получил новые математические результаты, включая рекорд в cap set problem.

Эта схема — LLM как оператор вариации, поиск как контур верификации — сейчас основной способ строить надёжные системы синтеза кода; подробнее об этом сдвиге — в статье про SBSE на практике.

Мини-итог

• GP эволюционирует структуры переменного размера; классическое представление — дерево разбора, потому что любое его поддерево валидно.
• Успех на 80% определяется выбором F и T: нужны замкнутость и достаточность, и при этом минимальность.
• Главный оператор — subtree crossover со смещением 90/10; мутация обязательна как источник нового материала.
• Bloat — не досадная мелочь, а системное свойство оператора кроссовера; лечится лимитами, parsimony pressure, Tarpeian или многокритериальным отбором. Сложность прогона O(G·P·N·S̄), и именно S̄ определяет реальное время.
• Чистый GP плохо подбирает константы — все серьёзные системы гибридны: GP ищет структуру, численный оптимизатор доводит числа. Lexicase вместо турнира — часто самое дешёвое улучшение на задачах, где разные тесты требуют разной логики.

Источники

• J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992. Материалы и результаты: genetic-programming.org
• R. Poli, W. B. Langdon, N. F. McPhee. A Field Guide to Genetic Programming, 2008 — бесплатная и лучшая современная вводная книга: gp-field-guide.org.uk
• W. B. Langdon, R. Poli. Foundations of Genetic Programming. Springer, 2002 — теория схем, bloat, ландшафты. Там же по теме: R. Poli, W. B. Langdon, S. Dignum. «On the Limiting Distribution of Program Sizes in Tree-based Genetic Programming», EuroGP 2007 — crossover bias как объяснение раздувания.
• L. Spector. «Assessment of Problem Modality by Differential Performance of Lexicase Selection», GECCO 2012 — введение lexicase; W. La Cava et al. «Epsilon-Lexicase Selection for Regression», GECCO 2016.
• A. Moraglio, K. Krawiec, C. G. Johnson. «Geometric Semantic Genetic Programming», PPSN 2012; M. O’Neill, C. Ryan. Grammatical Evolution, Springer, 2003; J. F. Miller. Cartesian Genetic Programming, Springer, 2011 — cartesiangp.com
• C. Le Goues, T. Nguyen, S. Forrest, W. Weimer. «GenProg: A Generic Method for Automatic Software Repair», IEEE TSE, 2012 — код: github.com/squaresLab/genprog-code
• M. Cranmer. «Interpretable Machine Learning for Science with PySR and SymbolicRegression.jl», arXiv:2305.01582
• B. Romera-Paredes et al. «Mathematical discoveries from program search with large language models», Nature, 2023 — nature.com/articles/s41586-023-06924-6
• Полная библиография области (более 15 000 работ): GP Bibliography

Что дальше

Мы дважды упирались в одну и ту же стену: точность и размер программы — два конфликтующих критерия, и склеивать их в одно число через магический коэффициент неудобно и хрупко. То же самое происходит в любой реальной SBSE-задаче: покрытие против времени выполнения тестов, связность против связанности модулей, скорость против памяти.

Следующая статья — Многокритериальная оптимизация: Парето, NSGA-II, SPEA2 — о том, как искать не одно решение, а весь фронт компромиссов, и почему это почти всегда честнее взвешенной суммы.