Локальный поиск: сосед, улучшение и локальный оптимум

Если ты знаешь, из чего состоит локальный поиск, почему он останавливается, чем локальный оптимум отличается от глобального и где у локального оптимума есть гарантия, листай до «Теперь сам».

Как думаешь, где он остановится

Офис из десяти человек надо разбить на две смены так, чтобы как можно больше пар «эти двое мешают друг другу» оказались в разных сменах. Пар 24. Правило простое: если у человека в его смене конфликтов больше, чем в чужой, переводим его в другую смену. Повторяем, пока есть кого переводить.

Ответь себе до чтения: остановится ли этот процесс или люди будут бегать туда-сюда? И если остановится, насколько хорош результат - сколько из 24 пар окажутся разведены? Окажется, что процесс всегда останавливается не больше чем за 24 перевода, а разведены будут хотя бы 12 пар. Лучше бы 18, но 12 гарантировано любым порядком переводов.

На что это похоже

Альпинист в густом тумане ищет вершину. Видит он только землю вокруг ботинок. Стратегия: шагнуть туда, где выше; если во все стороны ниже - объявить, что пришёл. Он всегда куда-нибудь придёт: подъём не может длиться вечно. Но пришёл он на ближайший холм, а не обязательно на высшую точку хребта. С другой стоянки он пришёл бы на другой холм.

Туман - это то, что мы видим только соседей текущего решения, а не всё пространство. Холм - локальный оптимум. Всё, что дальше в главе, - способы не застрять на холме: правильно выбрать, кто считается соседом, иногда шагать вниз, начинать с разных стоянок.

Механизм: три детали и два вопроса

Локальный поиск собирается из трёх деталей:

ПРОСТРАНСТВО   какие решения допустимы      разбиения людей на две смены
СОСЕДСТВО      какие правки - один шаг       перевести одного человека
ЦЕЛЬ           что улучшаем                  число разведённых пар

шаг: пока у текущего решения есть сосед лучше - перейти к нему
стоп: соседа лучше нет - это ЛОКАЛЬНЫЙ ОПТИМУМ

Почему остановится. Цель при каждом шаге строго растёт, а значений у неё конечное число. В задаче о сменах цель - целое число от 0 до числа пар m, каждый перевод увеличивает её хотя бы на единицу, значит, переводов не больше m. Если цель вещественная, число шагов бывает огромным, и на практике ставят порог: шаг засчитывается, только если выигрыш больше маленького числа.

Насколько хорошо. Задача о сменах - это наибольший разрез графа: вершины - люди, рёбра - пары, разрез - рёбра между сменами. В локальном оптимуме перевод любой вершины не помогает, то есть у каждой вершины разрезанных рёбер не меньше, чем неразрезанных, - хотя бы половина её рёбер. Сложим по всем вершинам: каждое разрезанное ребро посчитано дважды, по разу у каждого конца, а сумма степеней равна 2m. Получается 2 · разрез ≥ m, то есть разрез не меньше m / 2. Наибольший разрез не больше m, поэтому любой локальный оптимум не хуже наилучшего вдвое. Та же половина получалась в разделе о случайности монеткой - здесь она получена без случайности и с остановкой за m шагов.

Глобальный и локальный. Локальный оптимум - решение, у которого нет соседа лучше. Глобальный оптимум - лучшее решение вообще. Любой глобальный оптимум локален, обратное неверно. Исключение, которое стоит помнить: в линейном программировании любой локальный оптимум глобален, и симплекс-метод из раздела о потоках - это локальный поиск по вершинам многогранника, которому застревать негде.

Правило

Локальный поиск = пространство решений + соседство + цель; он переходит к соседу лучше текущего, пока такой есть, и останавливается в локальном оптимуме. Остановку гарантирует строгий рост цели. Качество локального оптимума - отдельный вопрос: иногда у него есть доказанная гарантия (наибольший разрез: не меньше половины рёбер), но обычно его определяет старт.

Разбор: смены в офисе

sluchajnyj_graf строит граф конфликтов с зерном - чтобы вывод совпадал с настоящим Python. lokalnyj обходит людей по кругу и переводит каждого, у кого своих конфликтов больше, чем чужих. luchshij - перебор всех разбиений для сверки: вершина 0 всегда в первой смене, потому что разбиение и его зеркало режут одни и те же рёбра, - отсюда 2^(n − 1) вариантов, а не 2ⁿ.

import random

def sluchajnyj_graf(n, m, zerno):
    random.seed(zerno)
    ryobra = []
    while len(ryobra) < m:
        a = random.randrange(n)
        b = random.randrange(n)
        if a != b and [a, b] not in ryobra and [b, a] not in ryobra:
            ryobra.append([a, b])
    return ryobra

def razrez(ryobra, storona):
    s = 0
    for r in ryobra:
        if storona[r[0]] != storona[r[1]]:
            s = s + 1
    return s

def lokalnyj(n, ryobra, storona):
    perevorotov = 0
    uluchshilos = True
    while uluchshilos:
        uluchshilos = False
        for v in range(n):
            svoi = 0
            chuzhie = 0
            for r in ryobra:
                if r[0] == v or r[1] == v:
                    drugoj = r[0] + r[1] - v
                    if storona[drugoj] == storona[v]:
                        svoi = svoi + 1
                    else:
                        chuzhie = chuzhie + 1
            if svoi > chuzhie:
                storona[v] = 1 - storona[v]
                perevorotov = perevorotov + 1
                uluchshilos = True
    return perevorotov

def luchshij(n, ryobra):
    best = 0
    for maska in range(2 ** (n - 1)):
        storona = [0] * n
        for v in range(1, n):
            storona[v] = maska >> (v - 1) & 1
        best = max(best, razrez(ryobra, storona))
    return best

n = 10
ryobra = sluchajnyj_graf(n, 24, 3)
storona = [0] * n
k = lokalnyj(n, ryobra, storona)
print(len(ryobra), k, razrez(ryobra, storona), storona)
print(luchshij(n, ryobra))

24 7 16 [0, 1, 1, 1, 1, 0, 0, 0, 1, 0]
18

Все начали в одной смене: разрез 0. Семь переводов - и поиск остановился с 16 разведёнными парами. Гарантия обещала не меньше 12, наилучшее разбиение даёт 18. Локальный оптимум оказался посередине - типичная картина: лучше гарантии и хуже оптимума.

Почему остановился именно на 16. У каждого человека теперь своих конфликтов не больше, чем чужих, - перевод одного человека ничего не даёт. Но перевод сразу двоих мог бы дать: соседство «один человек» этого не видит. Чем шире соседство, тем меньше плохих локальных оптимумов и тем дороже каждый шаг: соседей «один человек» десять, «двое сразу» - сорок пять.

Разбор: алгоритм Ллойда застревает

Кластеризация k-средних: разбить числа на k групп так, чтобы сумма квадратов отклонений от среднего своей группы была наименьшей. Алгоритм Ллойда - локальный поиск: назначить каждое число ближайшему центру, пересчитать центры как средние групп, повторить, пока центры меняются (программа ставит предел в 20 шагов; здесь хватает двух). Каждый такой шаг не увеличивает ошибку. Девять чисел, три естественные группы, три разных старта.

def lloyd(tochki, centry):
    for shag in range(20):
        gruppy = []
        for c in centry:
            gruppy.append([])
        for x in tochki:
            j = 0
            for i in range(len(centry)):
                if abs(x - centry[i]) < abs(x - centry[j]):
                    j = i
            gruppy[j].append(x)
        novye = []
        for i in range(len(centry)):
            if len(gruppy[i]) > 0:
                novye.append(sum(gruppy[i]) / len(gruppy[i]))
            else:
                novye.append(centry[i])
        if novye == centry:
            break
        centry = novye
    oshibka = 0
    for i in range(len(centry)):
        for x in gruppy[i]:
            oshibka = oshibka + (x - centry[i]) ** 2
    return [shag, centry, round(oshibka, 2)]

tochki = [1, 2, 3, 10, 11, 12, 20, 21, 22]
print(lloyd(tochki, [1, 11, 21]))
print(lloyd(tochki, [1, 2, 3]))
print(lloyd(tochki, [1, 10, 12]))

[1, [2.0, 11.0, 21.0], 6.0]
[2, [1.0, 2.5, 16.0], 154.5]
[2, [2.0, 11.0, 21.0], 6.0]

Первая строка: центры стартовали по одному в каждой группе - один шаг, и найдено разбиение с ошибкой 6. Вторая: все три центра стартовали в левой группе. Один центр остался на единице, второй взял 2, 3, а третий утащил обе правые группы и встал на 16. Дальше ни одно число не хочет менять центр, и это локальный оптимум с ошибкой 154,5 - почти в 26 раз хуже. Третья строка: два центра в средней группе, и алгоритм сам выбрался, отпустив один центр вправо. Плохой старт - не приговор, но и не случайность, которую можно не учитывать.

Что ломается без этого

Принимают равные шаги. Если переходить к соседу «не хуже» вместо «лучше», поиск на плато ходит по кругу вечно. Строгое улучшение - не педантизм, а условие остановки.

Соседство выбрано наугад. Слишком узкое - много плохих локальных оптимумов. Слишком широкое - один шаг стоит как перебор: соседство «перевести любые три вершины» на тысяче вершин - это 1,7 · 10⁸ соседей на шаг.

Один запуск из одного старта. Ответ Ллойда зависит от того, где стартовали центры, и библиотеки поэтому запускают его несколько раз и берут лучший. Один прогон - это одна стоянка альпиниста.

Считают локальный оптимум глобальным. «Алгоритм сошёлся» значит «соседи не лучше», а не «лучше нельзя».

Зачем это в работе

Кластеризация клиентов, расстановка серверов по стойкам, раскладка шардов, улучшение расписания, которое уже собрал жадный алгоритм. Во всех этих задачах есть готовое решение - вчерашнее, жадное, ручное - и вопрос «как его улучшить, не пересчитывая с нуля». Локальный поиск отвечает именно на него: маленькие правки, каждая с проверкой «стало лучше». Его же используют, когда точный алгоритм есть, но вход меняется по чуть-чуть: из вчерашнего оптимума сегодняшний часто находится за несколько шагов.

Теперь сам

1. Граф - цикл из пяти вершин, все в одной смене. Каков разрез в начале, какой может получиться после локального поиска и каков наибольший разрез?
2. Почему в задаче о сменах поиск сделает не больше m переводов, даже если обходить людей в любом порядке?
3. Числа 0, 1, 9, 10, два центра. Ллойд стартует с центров 0 и 1. Где он остановится и какова ошибка? А из старта 0 и 10?