Глобальная оптимизация: от муравьёв до температуры в LLM
Задача коммивояжёра для 100 городов имеет {\sim}10^{156} возможных маршрутов. Перебирать все — дольше, чем возраст Вселенной. Но природа решает подобные задачи каждый день: муравьи находят короткий путь к пище, металл при охлаждении принимает кристаллическую структуру с минимальной энергией, а стая птиц координируется без лидера. Четыре метаэвристики — генетический алгоритм, муравьиный алгоритм, роевой интеллект и имитация отжига — переносят эти идеи в код. А та же «температура» из отжига неожиданно появляется при генерации текста в ChatGPT.
Задача коммивояжёра (TSP) как полигон
n городов, матрица расстояний D_{ij}. Найти перестановку \pi, минимизирующую суммарную длину тура:
L(\pi) = \sum_{i=1}^{n-1} D_{\pi(i), \pi(i+1)} + D_{\pi(n), \pi(1)}.
TSP — NP-трудна. Полный перебор становится безнадёжным очень быстро: уже при n \gtrsim 28 он займёт дольше возраста Вселенной (при скорости 10^9 маршрутов/с). Точный решатель Concorde справляется с тысячами городов, но платит за доказательство оптимальности временем: на рекордном разобранном экземпляре в 85 900 городов ушло больше 136 лет процессорного времени. LKH — не точный алгоритм, а эвристика Лина — Кернигана — Хельсгауна: оптимума она не гарантирует, хотя на практике попадает в него очень часто и работает несравнимо быстрее. Метаэвристики из этой статьи проще и грубее, зато находят решения, близкие к оптимуму, за секунды.
Генетический алгоритм (GA)
Holland (1975)1 — имитация эволюции:
1 Holland, J.H. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.
1. Популяция. P случайных туров (перестановок).
2. Приспособленность (fitness). f(\pi) = 1 / L(\pi) — чем короче тур, тем она выше.
3. Селекция. Турнирный отбор: из случайной пары выбираем лучшего.
4. Кроссовер (Order Crossover, OX). Берём кусок маршрута из родителя A, оставшиеся позиции заполняем городами из родителя B в порядке появления.
5. Мутация. С малой вероятностью p_m \approx 0{,}01 меняем местами два случайных города.
6. Следующее поколение. Потомки замещают популяцию целиком — элитизма нет, родители не выживают. Поэтому лучший найденный тур запоминаем отдельно, иначе его можно потерять между поколениями.
import numpy as np
def solve_tsp_ga(D, pop_size=200, generations=500, mutation_rate=0.02):
n = D.shape[0]
def tour_length(tour):
return sum(D[tour[i], tour[(i+1) % n]] for i in range(n))
# Инициализация
population = [np.random.permutation(n) for _ in range(pop_size)]
best_ever = min(population, key=tour_length)
best_len = tour_length(best_ever)
history = []
for gen in range(generations):
fitness = np.array([1.0 / tour_length(p) for p in population])
new_pop = []
for _ in range(pop_size):
# Турнирная селекция
i, j = np.random.choice(pop_size, 2, replace=False)
parent_a = population[i] if fitness[i] > fitness[j] else population[j]
i, j = np.random.choice(pop_size, 2, replace=False)
parent_b = population[i] if fitness[i] > fitness[j] else population[j]
# Order Crossover (OX)
child = np.full(n, -1)
start, end = sorted(np.random.choice(n, 2, replace=False))
child[start:end] = parent_a[start:end]
fill = [g for g in parent_b if g not in child[start:end]]
idx = 0
for k in range(n):
if child[k] == -1:
child[k] = fill[idx]
idx += 1
# Мутация (swap)
if np.random.rand() < mutation_rate:
i, j = np.random.choice(n, 2, replace=False)
child[i], child[j] = child[j], child[i]
new_pop.append(child)
population = new_pop
current_best = min(population, key=tour_length)
current_len = tour_length(current_best)
if current_len < best_len:
best_ever = current_best.copy()
best_len = current_len
history.append(best_len)
return best_ever, best_len, history
# Пример: 50 случайных городов
n_cities = 50
np.random.seed(42)
coords = np.random.rand(n_cities, 2) * 100
D = np.sqrt(((coords[:, None] - coords[None, :]) ** 2).sum(axis=2))
best_tour, best_length, history = solve_tsp_ga(D)
print(f"GA: лучший тур = {best_length:.2f}")Муравьиный алгоритм (ACO)
Муравьи действительно умеют то, ради чего мы всё это затеяли. В опыте с раздвоенным мостиком колония аргентинских муравьёв через несколько минут собирается на короткой ветке2 — хотя ни один муравей не видит мостик целиком. Механизм такой: муравей на ходу оставляет феромон; по короткой ветке путь туда и обратно занимает меньше времени, поэтому феромон на ней копится быстрее; следующие муравьи охотнее сворачивают туда, где пахнет сильнее. Положительная обратная связь.
2 Goss, Aron, Deneubourg, Pasteels. Self-organized shortcuts in the Argentine ant, Naturwissenschaften, 1989.
3 Dorigo, Maniezzo, Colorni. Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics — Part B, 1996.
Dorigo, Maniezzo и Colorni3 перенесли это в алгоритм для TSP.
Алгоритм: феромон и испарение
На каждом ребре (i, j) живёт число \tau_{ij} — «феромон», общая память колонии. Отдельно считается видимость \eta_{ij} = 1 / D_{ij}: близкий город привлекателен сам по себе, безо всякой памяти.
1. Построение тура. Муравей стоит в городе i и выбирает следующий город j из ещё не посещённых N_i с вероятностью
p_{ij} = \frac{\tau_{ij}^{\alpha} \, \eta_{ij}^{\beta}} {\sum_{l \in N_i} \tau_{il}^{\alpha} \, \eta_{il}^{\beta}},
где \alpha задаёт вес коллективной памяти, \beta — вес сиюминутной жадности.
2. Испарение. Когда все муравьи прошли, феромон везде слабеет: \tau_{ij} \leftarrow (1 - \rho)\, \tau_{ij}, где \rho \in (0, 1) — скорость испарения.
3. Подкрепление. Каждый муравей k доливает феромон на рёбра своего тура, и тем больше, чем короче тур:
\tau_{ij} \leftarrow \tau_{ij} + \sum_k \Delta \tau^k_{ij}, \quad \Delta \tau^k_{ij} = \begin{cases} Q / L_k, & \text{если ребро } (i, j) \text{ входит в тур } k, \\ 0, & \text{иначе}. \end{cases}
Испарение — это забывание, подкрепление — запоминание. Без испарения первая же случайно удачная тропа зацементируется, и колония перестанет искать; при слишком быстром — накопленный опыт не успевает влиять на выбор.
import numpy as np
def solve_tsp_aco(D, n_ants=30, n_iter=200, alpha=1.0, beta=3.0,
rho=0.1, Q=1.0):
n = D.shape[0]
eta = 1.0 / (D + np.eye(n)) # видимость 1/D, диагональ не используется
tau = np.ones((n, n)) # начальный феромон
best_tour, best_len = None, np.inf
def tour_length(t):
return sum(D[t[i], t[(i+1) % n]] for i in range(n))
for it in range(n_iter):
tours = []
for _ in range(n_ants):
start = np.random.randint(n)
tour = [start]
unvisited = set(range(n)) - {start}
while unvisited:
i = tour[-1]
cand = np.array(sorted(unvisited))
w = tau[i, cand]**alpha * eta[i, cand]**beta
p = w / w.sum()
tour.append(int(np.random.choice(cand, p=p)))
unvisited.remove(tour[-1])
tours.append(np.array(tour))
tau *= (1 - rho) # испарение
# Подкрепление: чем короче тур, тем больше феромона
for tour in tours:
L = tour_length(tour)
if L < best_len:
best_tour, best_len = tour.copy(), L
for i in range(n):
a, b = tour[i], tour[(i+1) % n]
tau[a, b] += Q / L
tau[b, a] += Q / L
return best_tour, best_len
best_aco, len_aco = solve_tsp_aco(D)
print(f"ACO: лучший тур = {len_aco:.2f}")Роевой интеллект (PSO)
Kennedy и Eberhart (1995)4 — вдохновлены стаей птиц и косяком рыб.
4 Kennedy, Eberhart. Particle Swarm Optimization, IEEE ICNN, 1995.
Алгоритм
Каждая «частица» i имеет:
- позицию x_i \in \mathbb{R}^d
- скорость v_i \in \mathbb{R}^d
- лучшую личную позицию p_i (personal best)
- лучшую позицию всей стаи g (global best)
На каждом шаге:
v_i \leftarrow \underbrace{w \cdot v_i}_{\text{инерция}} + \underbrace{c_1 r_1 (p_i - x_i)}_{\text{когнитивная}} + \underbrace{c_2 r_2 (g - x_i)}_{\text{социальная}},
x_i \leftarrow x_i + v_i,
где w \approx 0{,}7 — коэффициент инерции, c_1, c_2 \approx 1{,}5 — коэффициенты «доверия» к себе и стае, r_1, r_2 \sim U(0,1) — случайные числа.
- Инерция (w v_i): частица сохраняет прежнее направление — это исследование (exploration).
- Когнитивная (c_1 r_1 (p_i - x_i)): частица помнит своё лучшее место.
- Социальная (c_2 r_2 (g - x_i)): частица стремится к лучшему месту стаи.
Эффективность PSO зависит от баланса между исследованием (инерция) и использованием найденного (социальная сила). Слишком большая инерция — стая разлетается. Слишком сильная социальная сила — все слетаются к локальному минимуму.
import numpy as np
import matplotlib.pyplot as plt
def pso(f, bounds, n_particles=30, max_iter=200,
w=0.7, c1=1.5, c2=1.5):
"""Particle Swarm Optimization."""
d = len(bounds)
lo = np.array([b[0] for b in bounds])
hi = np.array([b[1] for b in bounds])
# Инициализация
x = np.random.uniform(lo, hi, (n_particles, d))
v = np.random.uniform(-(hi-lo)*0.1, (hi-lo)*0.1, (n_particles, d))
p_best = x.copy()
p_best_val = np.array([f(xi) for xi in x])
g_best = p_best[np.argmin(p_best_val)].copy()
g_best_val = p_best_val.min()
history = [g_best_val]
for t in range(max_iter):
r1 = np.random.rand(n_particles, d)
r2 = np.random.rand(n_particles, d)
v = w * v + c1 * r1 * (p_best - x) + c2 * r2 * (g_best - x)
x = x + v
x = np.clip(x, lo, hi)
vals = np.array([f(xi) for xi in x])
improved = vals < p_best_val
p_best[improved] = x[improved]
p_best_val[improved] = vals[improved]
if vals.min() < g_best_val:
g_best = x[np.argmin(vals)].copy()
g_best_val = vals.min()
history.append(g_best_val)
return g_best, g_best_val, history
# Функция Растригина: много локальных минимумов
def rastrigin(x):
return 10 * len(x) + sum(xi**2 - 10 * np.cos(2 * np.pi * xi)
for xi in x)
best, best_val, hist = pso(rastrigin, [(-5.12, 5.12)] * 10,
n_particles=50, max_iter=300)
print(f"PSO на Rastrigin (d=10): f* = {best_val:.6f}")
# Глобальный минимум = 0 при x = 0Визуализация роя
Имитация отжига (SA) и температура
Kirkpatrick et al. (1983)5 — прямая аналогия с физикой:
5 Kirkpatrick, Gelatt, Vecchi. Optimization by Simulated Annealing, Science, 1983.
При высокой температуре атомы металла свободно перемещаются (жидкость). При медленном охлаждении они упорядочиваются в кристалл — состояние с минимальной энергией.
Критерий Метрополиса
На каждом шаге предлагаем случайный переход x \to x' и считаем разницу \Delta E = f(x') - f(x):
P(\text{принять}) = \begin{cases} 1, & \text{если } \Delta E < 0 \text{ (улучшение)}, \\ \exp(-\Delta E / T), & \text{если } \Delta E \geq 0 \text{ (ухудшение)}. \end{cases}
При высоком T принимаем почти любое изменение — идёт исследование. При низком T — почти только улучшения.
Расписание охлаждения
T(t) = T_0 \cdot \alpha^t, \quad \alpha \in [0{,}95, 0{,}999].
Температура в LLM: то же распределение Больцмана
Совпадение не случайно: и у отжига, и у softmax под капотом распределение Больцмана из статистической физики. Мостик между ними — машина Больцмана, описанная в 1985 году Экли, Хинтоном и Сейновски6: сеть, которая ищет минимум энергии так же, как отжиг, — случайными переходами с температурой. Формула там своя, не метрополисовская: нейрон включается с вероятностью \sigma(\Delta E / T) = 1 / (1 + \exp(-\Delta E / T)), а не \exp(-\Delta E / T). Общее у них не выражение, а роль T: температура делит разницу энергий и тем самым задаёт, насколько охотно система идёт против сиюминутной выгоды. Оттуда температура и перешла в softmax при генерации текста языковыми моделями.
6 Ackley, Hinton, Sejnowski. A Learning Algorithm for Boltzmann Machines, Cognitive Science, 9, 147–169, 1985.
При генерации текста модель вычисляет логиты z_i для каждого токена i в словаре и применяет softmax:
P(i) = \frac{\exp(z_i / T)}{\sum_j \exp(z_j / T)}.
Параметр T — temperature — управляет «случайностью» генерации:
| T | Поведение | Аналогия |
|---|---|---|
| T \to 0 | Жадный выбор (argmax) | Замороженный кристалл |
| T = 1 | Стандартное распределение | Комнатная температура |
| T > 1 | Более равномерное, «креативное» | Нагретый металл |
Во всех методах ключевой параметр управляет балансом между исследованием нового (exploration) и использованием уже найденного (exploitation):
- GA: вероятность мутации p_m
- ACO: скорость испарения \rho vs вес феромона \alpha
- PSO: инерция w vs социальная сила c_2
- SA/LLM: температура T
Во всех трёх задачах — TSP, минимизация Растригина, генерация текста — надо выбрать хороший вариант в огромном дискретном или непрерывном пространстве и не застрять в первом попавшемся локальном оптимуме.
Покрутите температуру и посмотрите, как отжиг перекраивает маршрут: пока горячо, он принимает и ухудшения, поэтому выбирается из локальных минимумов; остывая — застывает в найденном. Кликайте по полю, чтобы добавить новый город.
Сравнение на TSP
# SA для TSP
def solve_tsp_sa(D, T0=100, alpha=0.9995, max_iter=100000):
n = D.shape[0]
tour = np.random.permutation(n)
def length(t):
return sum(D[t[i], t[(i+1)%n]] for i in range(n))
current_len = length(tour)
best_tour = tour.copy()
best_len = current_len
T = T0
for step in range(max_iter):
# Случайная перестановка двух городов
i, j = sorted(np.random.choice(n, 2, replace=False))
new_tour = tour.copy()
new_tour[i:j+1] = new_tour[i:j+1][::-1] # 2-opt move
new_len = length(new_tour)
dE = new_len - current_len
if dE < 0 or np.random.rand() < np.exp(-dE / T):
tour = new_tour
current_len = new_len
if current_len < best_len:
best_tour = tour.copy()
best_len = current_len
T *= alpha
return best_tour, best_len
best_sa, len_sa = solve_tsp_sa(D)
print(f"SA: лучший тур = {len_sa:.2f}")Резюме
| Метод | Вдохновение | Ключевой параметр | Сильная сторона |
|---|---|---|---|
| GA | Эволюция | Мутация, кроссовер | Комбинаторика, гибкость представления |
| ACO | Феромонные тропы муравьёв | Испарение \rho, веса \alpha, \beta | Задачи на графах, накопление общей памяти |
| PSO | Стая птиц | Инерция, социальная сила | Непрерывные задачи, простота |
| SA | Кристаллизация | Температура T | Богатая теория сходимости (гарантия — при логарифмическом охлаждении) |
| Генерация в LLM | SA / Больцман (1985) | Температура T | Управление случайностью генерации, баланс точность/разнообразие |
Все пять — варианты случайного поиска, и все крутят одну и ту же ручку: случайность → детерминизм.