Локальный поиск: hill climbing, имитация отжига, tabu search

В предыдущей статье — Пространство поиска, представление решения и фитнес-функция — мы договорились о трёх вещах: как закодировать решение, как измерить его качество и что считать «соседом». Этого достаточно, чтобы запустить первый настоящий поисковый алгоритм.

Локальный поиск (local search, он же траекторный поиск) — самое простое семейство метаэвристик: мы держим в руках одно решение и шаг за шагом заменяем его на соседнее. Никаких популяций, кроссоверов и поколений — только текущая точка и правило перехода. Именно поэтому с него нужно начинать: почти всё, что делают генетические алгоритмы, роевые методы и NSGA-II, строится поверх тех же идей — исследовать пространство и не застревать.

И ещё одна причина: в software engineering локальный поиск часто выигрывает. Классическая работа Марка Хармана и Фила МакМинна «A Theoretical and Empirical Study of Search-Based Testing: Local, Global, and Hybrid Search» (IEEE TSE, 2010) показала: на большой доле реальных ветвей программ обычный hill climbing достигает покрытия быстрее генетического алгоритма — потому что ландшафты фитнеса в тестировании часто «почти унимодальны», и тратить бюджет на популяцию бессмысленно. Так что это не «алгоритм для разминки», а рабочая лошадка.

Формальная рамка

Задача оптимизации в SBSE задаётся тройкой:

• пространство поиска $S$ — множество всех допустимых решений (векторов входных данных, разбиений на модули, подмножеств требований, патчей);
• целевая функция $f: S \to \mathbb{R}$ — фитнес (максимизируем) или стоимость (минимизируем);
• оператор соседства $N: S \to 2^{S}$ — какие решения считаются «в одном шаге».

Локальный поиск — это правило, порождающее траекторию $s_0 \to s_1 \to s_2 \to \dots$, где каждое $s_{t+1} \in N(s_t)$. Всё различие между hill climbing, отжигом и tabu search сводится к правилу выбора следующей точки и к тому, что алгоритм помнит.

Ключевое определение: $s^\ast $ — локальный оптимум относительно $N$, если $f(s^\ast ) \ge f(s)$ для всех $s \in N(s^\ast )$. Обратите внимание: локальность определена не задачей, а оператором соседства. Смените $N$ — и та же точка перестанет быть локальным оптимумом. Это самый недооценённый рычаг в локальном поиске: проектирование соседства важнее выбора метаэвристики.

Хорошее соседство должно быть:

1. Связным — из любой точки достижима любая другая за конечное число шагов (иначе часть пространства недоступна в принципе).
2. Малого диаметра — оптимум достижим за разумное число ходов.
3. Дешёвым — генерация и оценка соседа не должны стоить дороже, чем шаг даёт информации.
4. Локальным по фитнесу — маленькое изменение решения должно давать маленькое изменение $f$. Это свойство называют locality; без него ландшафт превращается в белый шум и никакой поиск не поможет.

Картинка выше — вся суть статьи на одном рисунке. Hill climbing со старта справа скатывается в ближайший локальный минимум и останавливается: все его соседи хуже. Имитация отжига умеет временно подниматься, перебираясь через барьеры в соседние бассейны притяжения. Плато (участок, где все соседи равны) — отдельная патология: градиента нет, направление выбрать не из чего.

Общий каркас

Все три алгоритма — это один цикл с разными подстановками:

Обратите внимание на разделение s и best. Текущее решение может ухудшаться (в отжиге и tabu это норма), но рекорд мы запоминаем отдельно. Забыть про best — ошибка номер один у новичков: алгоритм отработал 100 000 итераций, побывал в отличной точке и вернул мусор, в котором случайно оказался на последнем шаге.

Сквозной пример: Next Release Problem

Чтобы сравнивать алгоритмы честно, зафиксируем одну задачу. Next Release Problem (Bagnall, Rayward-Smith, Whittley, 2001) — классика requirements engineering: есть $n$ требований, у каждого своя ценность для заказчика $v_i$ и стоимость реализации $c_i$; надо выбрать подмножество, максимизирующее суммарную ценность при бюджете $B$. Это NP-трудная задача (по сути 0/1 knapsack), представление — битовый вектор длины $n$, соседство — инверсия одного бита.

import random, math
from dataclasses import dataclass

@dataclass
class NRP:
    value: list   # ценность каждого требования
    cost: list    # стоимость реализации
    budget: int   # бюджет релиза

    def fitness(self, sol):
        """Максимизируем ценность; превышение бюджета штрафуем линейно."""
        total_cost = sum(c for c, b in zip(self.cost, sol) if b)
        total_val = sum(v for v, b in zip(self.value, sol) if b)
        overrun = max(0, total_cost - self.budget)
        # штраф 3.0 за единицу перерасхода — «мягкое» ограничение:
        # недопустимые решения разрешены, но невыгодны
        return total_val - 3.0 * overrun


def make_instance(n=60, seed=7):
    rng = random.Random(seed)
    value = [rng.randint(1, 40) for _ in range(n)]
    cost = [rng.randint(1, 30) for _ in range(n)]
    return NRP(value, cost, budget=int(0.4 * sum(cost)))


def neighbors(sol):
    """Соседство «инвертируй один бит»: ровно n соседей, связное, диаметр n."""
    for i in range(len(sol)):
        nb = list(sol)
        nb[i] ^= 1
        yield i, nb

Здесь уже спрятан важный дизайнерский выбор — мягкие ограничения вместо жёстких. Можно было бы запретить решения, выходящие за бюджет (жёсткое ограничение), но тогда поиск не может «пройти через» недопустимую область, а часто именно там лежит короткая дорога к оптимуму. Линейный штраф превращает ограничение в часть ландшафта. Коэффициент штрафа — гиперпараметр: слишком маленький, и алгоритм спокойно уедет за бюджет; слишком большой — вернётся жёсткое ограничение со всеми его обрывами.

Hill climbing

Идея тривиальна: смотри на соседей, переходи в того, кто лучше; остановись, когда лучших нет. Псевдокод:

HILL-CLIMBING(s0):
    s ← s0
    повторять:
        C ← N(s)                       # соседи текущего решения
        c ← выбрать кандидата из C      # см. варианты ниже
        если f(c) ≤ f(s): вернуть s     # локальный оптимум
        s ← c

Вариантов «выбрать кандидата» три, и они дают заметно разное поведение:

def hill_climb_steepest(inst, sol, max_evals=20_000):
    """Крутейший подъём: на каждом шаге перебираем ВСЁ соседство."""
    cur, cur_f, evals = list(sol), inst.fitness(sol), 1
    while evals < max_evals:
        best_nb, best_f = None, cur_f
        for _, nb in neighbors(cur):
            f = inst.fitness(nb); evals += 1
            if f > best_f:
                best_nb, best_f = nb, f
        if best_nb is None:          # ни один сосед не лучше — локальный оптимум
            break
        cur, cur_f = best_nb, best_f
    return cur, cur_f, evals


def hill_climb_first(inst, sol, rng, max_evals=20_000):
    """Первое улучшение: шаг делается сразу, как только нашли лучшего соседа."""
    cur, cur_f, evals = list(sol), inst.fitness(sol), 1
    improved = True
    while improved and evals < max_evals:
        improved = False
        idx = list(range(len(cur)))
        rng.shuffle(idx)             # случайный порядок — важно, иначе смещение к первым битам
        for i in idx:
            nb = list(cur); nb[i] ^= 1
            f = inst.fitness(nb); evals += 1
            if f > cur_f:
                cur, cur_f, improved = nb, f, True
                break                # не досматриваем остальных
    return cur, cur_f, evals

Сложность. Пусть $|N| = n$ (размер соседства), а $k$ — число шагов до локального оптимума. Steepest тратит $O(kn)$ вычислений фитнеса, first improvement — в среднем $O(k \cdot n/2)$ на неудачных проходах, но $k$ обычно больше. Память в обоих случаях $O(n)$ — только текущее решение и один кандидат. Никаких гарантий на $k$ в общем случае нет: для некоторых задач (например, локальный поиск для MAX-2-SAT) достижение локального оптимума PLS-полно, то есть экспоненциально трудно в худшем случае. На практике $k$ мал.

Ключевая оптимизация — инкрементальный фитнес. В коде выше fitness пересчитывает суммы за $O(n)$, значит один шаг steepest стоит $O(n^2)$. Но инверсия бита $i$ меняет стоимость ровно на $\pm c_i$, а ценность на $\pm v_i$ — пересчёт за $O(1)$. Это ускорение на два порядка, и в реальных SBSE-задачах (кластеризация модулей, планирование тестов) оно решает, отработает алгоритм за минуту или за сутки. Всегда спрашивайте себя: можно ли оценить дельту вместо полного пересчёта?

Три способа застрять

• Локальный оптимум — все соседи строго хуже. Лечится приёмом ухудшений (отжиг), памятью (tabu) или рестартами.
• Плато — все соседи равны. Градиента нет; чистый hill climbing останавливается, хотя за плато может быть спуск. Лечится боковыми ходами (sideways moves): разрешаем ходы с $\Delta f = 0$, но ограничиваем их число, иначе получим бесконечное блуждание. В SBSE плато возникают постоянно: например, фитнес «число покрытых ветвей» — ступенчатая функция, и на ступеньке все соседи равны. Именно поэтому в тестировании используют не число ветвей, а branch distance — непрерывную меру «насколько близко условие было к срабатыванию» (об этом ниже и в статье Автоматическая генерация тестов).
• Хребет (ridge) — улучшение достижимо, но только если изменить две переменные одновременно; каждое одиночное изменение ухудшает. Это дефект соседства, а не алгоритма. Лечится расширением $N$ (например, swap-ходы: «выключить требование $i$ и включить $j$ одним ходом»).

Рестарты и итеративный локальный поиск

Самое дешёвое лекарство — random restart hill climbing: запускаем спуск много раз из случайных точек, возвращаем лучший результат. Если вероятность попасть в бассейн глобального оптимума равна $p$, то за $r$ рестартов вероятность успеха $1 - (1-p)^r$ — то есть растёт экспоненциально. Проблема: каждый рестарт выбрасывает всю накопленную информацию.

Умнее — Iterated Local Search (ILS): не начинать с нуля, а «встряхнуть» найденный локальный оптимум небольшим возмущением (инвертировать $k$ случайных битов) и спускаться снова. Возмущение должно быть сильнее одного хода соседства (иначе вернёмся туда же), но слабее полного рестарта. Каноническое описание — глава Lourenço, Martin, Stützle «Iterated Local Search» в Handbook of Metaheuristics.

def random_restart(inst, restarts, rng):
    best, best_f, used = None, float("-inf"), 0
    for _ in range(restarts):
        s = [rng.randint(0, 1) for _ in range(len(inst.value))]
        s, f, e = hill_climb_first(inst, s, rng)
        used += e
        if f > best_f:
            best, best_f = s, f
    return best, best_f, used

Имитация отжига (simulated annealing)

Идея пришла из металлургии и статистической физики. При отжиге металл нагревают и медленно охлаждают: при высокой температуре атомы свободно перескакивают между конфигурациями, при низкой — «замерзают» в решётке с минимальной энергией. Быстрое охлаждение (закалка) фиксирует дефекты — аналог локального оптимума.

Kirkpatrick, Gelatt и Vecchi в «Optimization by Simulated Annealing» (Science, 1983) перенесли это на оптимизацию, взяв критерий Метрополиса из алгоритма Metropolis–Hastings (1953). Правило приёма: ход, улучшающий решение, принимается всегда; ухудшающий на $\Delta$ — с вероятностью

$$P(\text{принять}) = \exp!\left(\frac{\Delta}{T}\right), \quad \Delta = f(c) - f(s) < 0.$$

Здесь два предельных случая. При $T \to \infty$ вероятность стремится к 1 — это случайное блуждание, полное исследование без всякой эксплуатации. При $T \to 0$ вероятность стремится к 0 — это чистый hill climbing. Отжиг — это непрерывная интерполяция между случайным поиском и жадным спуском, управляемая одним числом. В этом его красота.

def simulated_annealing(inst, sol, rng, t0=40.0, alpha=0.995, max_evals=20_000):
    cur, cur_f = list(sol), inst.fitness(sol)
    best, best_f = list(cur), cur_f
    t = t0
    for _ in range(max_evals):
        i = rng.randrange(len(cur))
        cur[i] ^= 1                       # пробный ход: инвертируем случайный бит
        f = inst.fitness(cur)
        delta = f - cur_f                 # максимизация: delta > 0 — улучшение

        if delta >= 0 or rng.random() < math.exp(delta / max(t, 1e-9)):
            cur_f = f                     # ход принят (возможно, ухудшающий)
            if f > best_f:
                best, best_f = list(cur), f   # рекорд запоминаем ОТДЕЛЬНО
        else:
            cur[i] ^= 1                   # откат: инверсия — сама себе обратная операция

        t *= alpha                        # геометрическое охлаждение
    return best, best_f, max_evals

Заметьте приём с откатом: вместо копирования массива на каждой итерации мы применяем ход «на месте» и отменяем его при отказе. На векторе из 60 бит это мелочь, а на решении в 10 000 элементов — разница между $O(1)$ и $O(n)$ на итерацию.

Расписание охлаждения

Расписание $T(t)$ — главный гиперпараметр отжига. Основные варианты:

Теорема Geman & Geman (1984) утверждает: при логарифмическом охлаждении $T_k \ge c/\log(k+1)$ с достаточно большим $c$ отжиг сходится к глобальному оптимуму с вероятностью 1. Красиво — и практически бесполезно: скорость такова, что для гарантии нужно больше итераций, чем полный перебор пространства. Гарантия сходимости у отжига есть, но пользоваться ею нельзя. На практике берут геометрическое расписание и подбирают $\alpha$ так, чтобы температура успела упасть почти до нуля к концу отведённого бюджета.

Как выбрать $T_0$? Не на глаз, а через целевую приёмистость. Сделайте 100–1000 случайных ходов, соберите модули ухудшений $|\Delta_i|$, и решите уравнение относительно $T_0$:

$$\frac{1}{m}\sum_i \exp!\left(-\frac{|\Delta_i|}{T_0}\right) \approx 0.8.$$

То есть в начале принимается ~80% ухудшающих ходов. Аналогично $T_{\text{final}}$ выбирают из целевой приёмистости ~1–5%. Это делает настройку переносимой между задачами с разным масштабом фитнеса — иначе t0=40 из примера выше при переходе на задачу с фитнесом порядка $10^6$ мгновенно превратит отжиг в hill climbing.

Tabu search

Отжиг борется с локальными оптимумами случайностью. Fred Glover в 1986 году («Future Paths for Integer Programming and Links to Artificial Intelligence») предложил бороться памятью, и это принципиально другой ответ.

Правило tabu search: на каждой итерации мы обязаны сделать ход — переходим в лучшего соседа, даже если он хуже текущего. Чтобы не свалиться обратно в только что покинутый оптимум, недавно сделанные ходы (или их атрибуты) заносятся в tabu-список и запрещаются на $t$ итераций (tenure, срок запрета).

Что именно запрещать — важнейший дизайнерский вопрос:

• Запрет решений (хранить посещённые $s$ целиком) — точный, но дорогой по памяти и слабый: конкретное решение всё равно вряд ли повторится.
• Запрет атрибутов хода (в нашем случае — «индекс инвертированного бита») — дешёвый, $O(n)$ памяти, но грубый: запрещая бит $i$, мы отсекаем целый класс решений, среди которых могут быть хорошие.

Именно из-за грубости атрибутивного запрета нужен критерий аспирации (aspiration criterion): если запрещённый ход приводит к решению лучше глобального рекорда, запрет снимается. Логика простая — раз мы там никогда не были, запрет заведомо ложное срабатывание.

def tabu_search(inst, sol, tenure=7, max_iters=328):
    n = len(sol)
    cur, cur_f = list(sol), inst.fitness(sol)
    best, best_f = list(cur), cur_f
    tabu_until = [0] * n          # tabu_until[i] — итерация, до которой бит i запрещён
    evals = 1

    for it in range(1, max_iters + 1):
        cand, cand_f, cand_i = None, float("-inf"), -1
        for i, nb in neighbors(cur):
            f = inst.fitness(nb); evals += 1
            is_tabu = tabu_until[i] >= it
            # аспирация: запрет игнорируем, если бьём глобальный рекорд
            if is_tabu and not f > best_f:
                continue
            if f > cand_f:
                cand, cand_f, cand_i = nb, f, i

        if cand is None:          # всё соседство под запретом — редкий, но возможный случай
            break

        cur, cur_f = cand, cand_f            # ход делается ВСЕГДА, даже если хуже
        tabu_until[cand_i] = it + tenure
        if cur_f > best_f:
            best, best_f = list(cur), cur_f

    return best, best_f, evals

Tenure — критичный гиперпараметр. Слишком маленький — алгоритм зацикливается между двумя точками (то самое, от чего запрет и должен спасать). Слишком большой — запрещено столько ходов, что поиск теряет направление и деградирует до случайного блуждания. Практические ориентиры: $t \approx \sqrt{n}$ или $t \in [7, 20]$ для битовых представлений; ещё лучше — reactive tabu search (Battiti & Tecchiolli, 1994), где tenure растёт при обнаружении зацикливания и убывает при его отсутствии.

Помимо краткосрочной памяти (tabu-список) полноценная реализация использует:

• долгосрочную память частот — сколько раз каждый атрибут участвовал в ходах. Часто используемые атрибуты штрафуются, чтобы вытолкнуть поиск в неисследованные регионы (диверсификация);
• память элитных решений — периодический возврат к лучшим найденным точкам и тщательный поиск вокруг них (интенсификация).

Баланс интенсификации и диверсификации — центральная тема всех метаэвристик; в генетических алгоритмах ему соответствует баланс давления селекции и мутации, о чём в статье Генетические алгоритмы.

Кто побеждает: честный эксперимент

Сравним на одном экземпляре NRP ($n = 60$), равный бюджет 20 000 вычислений фитнеса, 30 независимых запусков, метрика — итоговая ценность (больше лучше):

Выводы, которые обобщаются далеко за пределы этого примера:

1. Одиночный hill climbing — не алгоритм, а компонент. Его разброс огромен (584…791): результат целиком определяется точкой старта.
2. Рестарты дают огромный прирост почти бесплатно. Если у вас есть локальный поиск и нет времени — добавьте рестарты, это лучшее соотношение «усилие/результат».
3. Tabu search выигрывает, потому что систематически перебирает всё соседство и не тратит ходы впустую. Обратная сторона — он в $n$ раз дороже на шаг; на задачах с дорогой фитнес-функцией (запуск тест-сьюта!) это может быть неприемлемо, и отжиг с его одной оценкой на итерацию окажется предпочтительнее.

Полезное упражнение — расположить в этих координатах генетический алгоритм: он окажется правее центра (стохастические операторы) и высоко по вертикали, потому что популяция — это тоже форма памяти, только распределённая.

Локальный поиск в реальном SBSE

Alternating Variable Method: генерация тестовых данных

Самое известное применение hill climbing в software engineering — метод Кореля (Bogdan Korel, «Automated Software Test Data Generation», IEEE TSE, 1990). Задача: подобрать входные данные, при которых выполнится нужная ветвь программы. Пространство поиска — векторы входов, фитнес — branch distance: насколько условие было близко к тому, чтобы стать истинным.

Для x == 42 расстояние равно $|x - 42|$; для y > 100 — $(100 - y) + K$, если условие ложно, и 0 иначе. Значения нормируют в $[0, 1)$ функцией $d/(d+1)$, чтобы вклад разных условий был сопоставим (нюансы нормализации разобраны у Аркури в «It Really Does Matter How You Normalize the Branch Distance», STVR 2013).

AVM — это hill climbing с двумя фазами: разведочные ходы ($\pm 1$ по одной переменной, чтобы определить направление) и ускоряющиеся ходы ($\pm 2, \pm 4, \pm 8, \dots$ — пока фитнес улучшается). Ускорение делает метод почти нечувствительным к масштабу входных данных.

def branch_distance(x, y):
    """Целевая ветвь: if (x == 42 && y > 100). 0.0 означает «ветвь достигнута»."""
    K = 1.0
    d1 = abs(x - 42)
    d2 = 0.0 if y > 100 else (100 - y) + K
    return d1 / (d1 + 1.0) + d2 / (d2 + 1.0)   # нормализация в [0, 1) на каждое условие


def avm(f, x0, max_evals=10_000):
    x, fx, evals = list(x0), f(*x0), 1
    improved = True
    while improved and fx > 0 and evals < max_evals:
        improved = False
        for i in range(len(x)):                    # по очереди по каждой переменной
            for direction in (+1, -1):
                probe = list(x); probe[i] += direction
                fp = f(*probe); evals += 1
                if fp >= fx:
                    continue                        # это направление не помогает
                x, fx, improved = probe, fp, True

                step = 2                            # ускоряющиеся ходы: 2, 4, 8, 16...
                while fx > 0 and evals < max_evals:
                    probe = list(x); probe[i] += direction * step
                    fp = f(*probe); evals += 1
                    if fp >= fx:
                        break                       # перелетели — вернёмся к шагу 1
                    x, fx = probe, fp
                    step *= 2
                break                               # переменная обработана, идём к следующей
    return x, fx, evals

Результаты запуска показывают, почему это работает:

старт [0, 0]                    -> x=[42, 127],     расстояние 0.0, 29  вычислений
старт [-100000, 900000]         -> x=[42, 900000],  расстояние 0.0, 89 вычислений
старт [10000000, -10000000]     -> x=[42, 6777215], расстояние 0.0, 191 вычисление

Сравните со случайным поиском: вероятность угадать x == 42 среди 32-битных целых равна $2^{-32}$, то есть в среднем 4 миллиарда попыток. AVM справляется за 29–191. Именно этот контраст — главный аргумент за search-based тестирование, и AVM до сих пор входит в инструментарий современных генераторов тестов наряду с эволюционными методами.

Кластеризация модулей

Вторая классическая ниша — автоматическая модуляризация: разбить граф зависимостей между классами на кластеры так, чтобы связность внутри кластеров была высокой, а между — низкой (метрика MQ, Modularization Quality). Инструмент Bunch (Mitchell & Mancoridis, IEEE TSE 2006) использует hill climbing поверх соседства «перенести класс в другой кластер». А работа Mahdavi, Harman, Hierons «A Multiple Hill Climbing Approach to Software Module Clustering» (ICSM 2003) показала любопытный трюк: запустить много hill climbing параллельно, затем зафиксировать те присвоения, на которых сошлось большинство запусков, и искать дальше только в оставшемся подпространстве. Это дешёвая форма коллективной памяти — по духу уже ближе к популяционным методам.

Где локальный поиск проигрывает

Честно перечислим случаи, когда стоит сразу брать что-то другое:

• Много критериев. Если целей несколько и они конфликтуют (покрытие vs. длина теста), сведение в один скаляр через веса теряет фронт Парето. См. Многокритериальную оптимизацию.
• Обманчивые (deceptive) ландшафты. Если градиент фитнеса систематически ведёт прочь от глобального оптимума, траекторный поиск обречён; популяция с кроссовером имеет шанс собрать решение из «строительных блоков».
• Плоские ландшафты. Если фитнес почти везде одинаков (типичная беда наивных фитнес-функций в автоматическом исправлении программ, где тест либо проходит, либо нет), никакая метаэвристика не поможет — надо чинить фитнес-функцию, а не алгоритм.
• Дорогая оценка. Если один вызов фитнеса — это сборка проекта и прогон тестов (минуты), любой метод с тысячами оценок нежизнеспособен без суррогатных моделей или параллелизма.

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

1. Не сохранять лучшее найденное решение. Отжиг и tabu намеренно ухудшают текущее решение; без отдельной переменной best вы вернёте случайную точку.
2. Настраивать $T_0$ «на глаз». Абсолютное значение температуры бессмысленно без масштаба $\Delta f$. Калибруйте по целевой приёмистости.
3. Сравнивать алгоритмы по итерациям, а не по вычислениям фитнеса. Итерация tabu стоит $n$ оценок, итерация отжига — одну. Единственная честная валюта — число вычислений фитнеса (или время).
4. Один запуск вместо распределения. Все эти алгоритмы стохастические. Сравнивать надо минимум 30 запусков с непараметрическим тестом (Манна–Уитни) и мерой размера эффекта $\hat{A}_ {12}$ Vargha–Delaney. Обязательное чтение — Arcuri & Briand, «A Hitchhiker’s Guide to Statistical Tests for Assessing Randomized Algorithms in Software Engineering» (STVR 2014).
5. Не сравнивать со случайным поиском. Random search — обязательный baseline. Если ваш отжиг не бьёт случайный поиск при равном бюджете, ландшафт не даёт поиску никакой информации, и проблема в фитнес-функции.
6. Полный пересчёт фитнеса вместо инкрементального. Самая частая причина того, что «алгоритм слишком медленный».
7. Слишком узкое соседство. Если улучшение требует двух одновременных изменений, добавьте составные ходы (swap) — это дешевле, чем менять метаэвристику.
8. Жёсткие ограничения там, где нужны мягкие. Запрет недопустимых решений разрывает пространство поиска на изолированные острова.

Мини-итог

• Локальный поиск = одно решение + оператор соседства + правило приёма. Всё остальное — вариации.
• Hill climbing принимает только улучшения: быстро, дёшево, застревает. Работает отлично на унимодальных ландшафтах — а в тестировании ПО их больше, чем кажется.
• Simulated annealing принимает ухудшения с вероятностью $\exp(\Delta/T)$: одна оценка на итерацию, один главный гиперпараметр (расписание), теоретическая сходимость без практической пользы.
• Tabu search делает ход всегда и использует память о недавних ходах плюс критерий аспирации: обычно лучшее качество, но $|N|$ оценок на итерацию.
• Соседство и фитнес-функция важнее выбора алгоритма. Прежде чем менять метаэвристику, проверьте locality ландшафта и наличие плато.
• Меряйте в вычислениях фитнеса, повторяйте 30 раз, сравнивайте статистически, всегда держите random search как baseline.

Источники

• S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi. Optimization by Simulated Annealing. Science, 1983. https://www.science.org/doi/10.1126/science.220.4598.671
• F. Glover. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers & Operations Research, 1986. https://www.sciencedirect.com/science/article/abs/pii/0305054886900481
• F. Glover, M. Laguna. Tabu Search. Kluwer, 1997. https://link.springer.com/book/10.1007/978-1-4615-6089-0
• H. H. Hoos, T. Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2004. https://www.sciencedirect.com/book/9781558608726/stochastic-local-search
• B. Korel. Automated Software Test Data Generation. IEEE TSE, 1990. https://ieeexplore.ieee.org/document/57624
• M. Harman, P. McMinn. A Theoretical and Empirical Study of Search-Based Testing: Local, Global, and Hybrid Search. IEEE TSE, 2010. https://ieeexplore.ieee.org/document/5210090
• B. Mitchell, S. Mancoridis. On the Automatic Modularization of Software Systems Using the Bunch Tool. IEEE TSE, 2006. https://ieeexplore.ieee.org/document/1610610
• A. Arcuri, L. Briand. A Hitchhiker’s Guide to Statistical Tests for Assessing Randomized Algorithms in Software Engineering. STVR, 2014. https://onlinelibrary.wiley.com/doi/10.1002/stvr.1486
• H. R. Lourenço, O. Martin, T. Stützle. Iterated Local Search. Handbook of Metaheuristics. https://link.springer.com/chapter/10.1007/978-1-4419-1665-5_12
• S. Russell, P. Norvig. Artificial Intelligence: A Modern Approach, гл. 4 «Search in Complex Environments». https://aima.cs.berkeley.edu/

Что дальше

Локальный поиск ведёт одну точку по ландшафту, и его главная слабость — отсутствие «второго мнения»: если траектория ушла не туда, спасают только рестарты и случайность. Следующий шаг — вести популяцию решений сразу и позволить им обмениваться информацией через кроссовер.

Читайте дальше: Генетические алгоритмы: селекция, кроссовер, мутация.