Дидактические цели
Как искать самую низкую точку ландшафта, которого не видно? У оптимизатора нет формулы: он может лишь указать точку и спросить, сколько там стоит функция, и каждый вопрос чего-то стоит — в реальной задаче это может быть восьмичасовой расчёт. Лаборатория проходит семь способов тратить эти вопросы — от случайных дротиков до роёв и эволюционирующих популяций — и заставляет их соревноваться при одном бюджете на очень разных рельефах. Вторая из трилогии по оптимизации, после Линейной оптимизации. Рассчитана на университетский уровень.
Чему учит
- Измерять поиск: вычисление функции как единица стоимости, кривая сходимости в логарифмическом масштабе и различие между ошибкой значения и ошибкой положения (залы 1-8).
- Компромисс между исследованием и использованием, который возвращается в каждом методе под новым именем — шаг, температура, инерция, давление отбора — и в котором всегда есть два способа ошибиться (зал 9).
- Почему число переменных топит методы, работающие вслепую: проклятие размерности и его практические следствия, в том числе для поиска по сетке (залы 10-11).
- Локальный поиск, его локальные оптимумы и два единственных выхода: рестарты (залы 12-15) и принятие ухудшений, ведущее к имитации отжига с критерием Метрополиса и расписанием охлаждения (залы 16-19).
- Популяционные методы: рой частиц с когнитивным и социальным притяжением и инерцией (залы 20-23) и генетический алгоритм с отбором, скрещиванием, мутацией и элитизмом (залы 24-26).
- Два детерминированных метода: симплекс Нелдера — Мида и градиентный спуск, а также четыре конкретных способа, которыми градиент разбивается (залы 27-29).
- Строго сравнивать: один бюджет, несколько зёрен и победители, меняющиеся при добавлении шума или измерений. Теорема об отсутствии бесплатных обедов и что именно она утверждает (залы 30-35).
Ключевые математические идеи
- Сравнение двух методов требует дать им одно и то же, а единственное, что можно посчитать одинаково для всех, — число вычислений целевой функции. Не секунды, которые меряют компьютер, и не итерации, которые в рое и в локальном поиске значат разное. В этой валюте градиент, приближённый конечными разностями, не бесплатен: он стоит d+1 вычисление на шаг.
- Поскольку все эти методы используют случайность, один запуск — не результат. Честно приводить медиану нескольких и указывать их число. Вероятность того, что хотя бы одна из N попыток удастся, равна P = 1 − (1 − p)^N — формула, возвращающаяся в рестартах и в размере роя, с той оговоркой, что при фиксированном бюджете p каждой попытки зависит от числа попыток.
- Случайный поиск улучшается как N^(−2/d): в двойном логарифмическом масштабе это прямая с наклоном −2/d. Выигрыш одного разряда точности стоит умножения вычислений на 10^(d/2).
- Метод, принимающий только улучшения, не может выйти из локального минимума по определению. Его вероятность успеха равна площади бассейна притяжения глобального оптимума, делённой на общую площадь.
- Критерий Метрополиса, P = e^(−Δf/T), переводит физический отжиг на язык оптимизации: температура измеряется в единицах функции, а логарифмическое охлаждение, гарантирующее глобальный оптимум, занимает больше времени, чем возраст Вселенной.
- В логарифмическом масштабе убывающая прямая — линейная сходимость (ошибка умножается на постоянный множитель), а выполаживающаяся кривая — сублинейная: обычная цена отказа от производных.
- Скрещивание в генетическом алгоритме — ставка на структуру задачи: оно кратно повышает качество на сепарабельных функциях и не даёт ничего, когда переменные сцеплены (эпистаз).
- Теорема Уолперта и Макреди гласит, что усреднённо по всем возможным целевым функциям все методы работают одинаково. Она не говорит, что выбор метода неважен: она говорит, что преимущество метода всегда происходит из предположения о задаче и что почти ни одна мыслимая функция этим предположениям не удовлетворяет. Методы работают потому, что структуру имеет мир.
Содержание по залам
Зал 1 · Невидимая горная гряда
Племя ищет самую низкую долину в горах, вечно затянутых туманом, и может отправить всего 7 экспедиций: каждый клик по карте рассеивает туман вокруг точки и приносит её высоту. В конце открывается вся карта: долин было две, и со дна одной другую не видно. Зал закладывает идею, на которой держится вся лаборатория: оптимизатор не видит рельеф, он может лишь спрашивать значение функции в конкретных точках, и каждый вопрос чего-то стоит. Спойлер определяет локальный и глобальный минимум.
Задания для ученика
- Найти самую низкую долину за 7 экспедиций, читая высоты и решая, куда идти дальше.
- Понять, какой информацией на самом деле располагает метод оптимизации.
- Решить, что можно заключить, когда со дна долины во все стороны идёт подъём.
Зал 2 · Бросаем дротики
Чистый случайный поиск: N равномерных точек, оставить лучшую. Ползунок управляет N, переключатель меняет ландшафт. Вводится нормированная ошибка (0 в оптимуме, около 1 в случайной точке), делающая сравнимыми ландшафты очень разных масштабов, а спойлер объясняет, что ошибка убывает как N^(−2/d): при удвоении числа дротиков в размерности 2 ошибка уменьшается вдвое.
Задания для ученика
- Бросать мало и много дротиков и описать, как меняется ошибка.
- При 200 дротиках упорядочить четыре ландшафта по оставшейся ошибке.
- Назвать достоинство, которое есть только у этого метода: он не может застрять в локальном минимуме.
Зал 3 · Каталог местностей
Восемь функций, с которыми работает вся остальная лаборатория (горная гряда, чаша, кривая долина, лоток для яиц, плато, лестница, иглы и иголка в стоге сена), у каждой — книжное название (сфера, Розенброк, Растригин, Экли, Швефель…), формула и метод, который она должна сломать. Карта рисуется в размерности 2, но все функции определены для любого числа переменных. Зал завершает предупреждение: в реальных задачах у f нет формулы, и иголка в стоге сена напоминает об этом.
Задания для ученика
- Найти ландшафт, у которого минимум — целая область, а не точка.
- Отметить ландшафты с множеством локальных минимумов.
- Узнать ландшафт, где нет никакой подсказки, за которой можно идти.
Зал 4 · Один запуск — не результат
Одна и та же конфигурация запускается пятьдесят раз, строится гистограмма ошибок с медианой и процентилями. Зал учит честно сообщать о стохастическом методе, и отсюда выходит формула P = 1 − (1 − p)^N, которая ещё вернётся в лаборатории.
Задания для ученика
- Оценить отчёт, в котором приведена ошибка одного запуска.
- Сказать, что происходит с медианой ошибки при увеличении числа дротиков.
- Вычислить, сколько независимых запусков нужно для заданной надёжности.
Зал 5 · Валюта лаборатории
Фиксируется единица измерения всей лаборатории: вычисление целевой функции. Не секунды (они меряют компьютер) и не итерации (в разных методах они значат разное). Таблица показывает четыре очень разные на вид конфигурации, стоящие ровно одинаково.
Задания для ученика
- Посчитать, сколько вычислений тратит заданная конфигурация роя.
- Решить, что занимает больше всего времени в реальной задаче, где функция не задана формулой.
Зал 6 · Кривая сходимости
Вводится представление, по которому будут судить все методы: лучшее найденное значение против потраченных вычислений, вертикальная ось в логарифмическом масштабе. Три кривые одного метода в размерностях 2, 3 и 5 показывают, что с размерностью меняется не форма, а наклон.
Задания для ученика
- Прочитать по кривой, сколько вычислений нужно для заданной точности.
- Истолковать, что значит (и чего не значит) выход кривой на плато.
Зал 7 · Ошибка чего?
Ошибка значения отделяется от ошибки положения: клик по любой точке карты показывает обе сразу. В кривой долине и в чаше можно быть далеко от оптимума при почти идеальном значении, а на лестнице минимум — не точка, а целая область.
Задания для ученика
- Решить, какая ошибка важна в конкретном приложении.
- Найти кликами по карте, в каких функциях малая ошибка значения может сочетаться с большой ошибкой положения.
Зал 8 · Что значит сходиться
Четыре реальные кривые лаборатории с четырьмя разными финалами: сходимость к глобальному, к локальному, застой и отсутствие сходимости. Ученики узнают, что в логарифмическом масштабе прямая означает линейную сходимость (ошибка умножается на постоянный множитель), а выполаживающаяся кривая — сублинейную.
Задания для ученика
- Отметить, какие из четырёх кривых действительно доходят до минимума.
- Истолковать прямую в логарифмическом масштабе и кривую, остающуюся плоской 500 вычислений.
- Вычислить, сколько вычислений нужно линейно сходящемуся методу для заданной точности.
Зал 9 · Исследовать или использовать
Узловой зал лаборатории. Одна ручка — величина прыжка σ — с двумя видимыми провалами на лотке для яиц: при малом σ метод не выходит из ямки, куда упал, при большом — никогда не доуточняет. Типичная ошибка по 21 запуску показывает, что ни одна крайность не выигрывает, и объявляется, что все следующие методы — разные способы крутить ту же ручку: температура, инерция, давление отбора.
Задания для ученика
- По плоской кривой определить, в какую сторону крутить ручку.
- Пройти ползунком и найти σ с наименьшей типичной ошибкой на лотке для яиц.
- Решить, как распределять исследование и использование по ходу одного запуска.
Зал 10 · Проклятие размерности
При коробке со стороной 10 и хорошей зоне со стороной 1 каждое добавленное измерение умножает нужное число дротиков на десять: N(d) = 10^d. Таблица доходит до 10^10 в размерности 10, а живой эксперимент на чаше (медиана 11 запусков) показывает, что случайному поиску, чтобы опуститься ниже ошибки 0,05, нужно 25 вычислений в размерности 2 и около 825 в размерности 5.
Задания для ученика
- Вычислить ожидаемое число дротиков для попадания в размерности 6.
- Проверить в эксперименте порядок числа вычислений в размерности 5.
Зал 11 · Случай или сетка?
Поиск по сетке (grid search): k значений на переменную стоят k^d вычислений, а недоделанная сетка бесполезна. Два рисунка по 25 точек сравнивают её со случайным выбором: сетка 5 × 5 пробует лишь 5 разных значений каждой переменной, а 25 случайных точек — 25. К тому же случайный поиск можно остановить на полпути, и сделанное всё равно будет выборкой по всей области.
Задания для ученика
- Вычислить стоимость полной сетки при 5 переменных и 4 значениях каждой.
- Посчитать, сколько разных значений x₁ пробует сетка 7 × 7.
- Объяснить, почему случайный выбор обычно лучше сетки с тем же числом точек.
Зал 12 · Смотреть вокруг
Первый метод, использующий увиденное: оставаться там, где хорошо, и предлагать близкую точку. Появляется первый настоящий параметр σ, и бюджетное задание просит выбрать его так, чтобы поиск опустился ниже ошибки 0,00002 на чаше всего за 200 вычислений, с проверкой по 21 зерну, чтобы не засчитывалась случайная удача.
Задания для ученика
- Двигать σ и наблюдать за следом поиска на карте.
- Пройти бюджетное задание, выбрав σ, работающее хотя бы на половине зёрен.
- Объяснить, почему плохо, что при очень малом σ почти все предложения дают улучшение.
Зал 13 · Ловушка
Тот же метод на лотке для яиц, где лишь 1% запусков достигает глобального минимума. Карта раскрашена по бассейнам притяжения, и ученик кликает в любую точку, чтобы запустить поиск оттуда и увидеть, где он окажется. Определяются локальный минимум и бассейн притяжения, и становится ясно, что метод, принимающий только улучшения, никогда не выйдет из локального минимума.
Задания для ученика
- Запускать поиски из разных точек и смотреть, сколько доходит до глобального минимума.
- Сказать, что доказано, если поиск уже 300 вычислений не улучшается.
- Вычислить, сколько стартов нужно для заданной вероятности успеха.
Зал 14 · Начать заново
Первый выход: разделить бюджет между несколькими рестартами. Если пройти по числу рестартов (от 1 до 500), типичная ошибка плоха на обоих концах, ведь каждый дополнительный рестарт укорачивает все прочие. Формула зала 4 обобщается на случай, когда вероятность успеха зависит от самого числа попыток.
Задания для ученика
- Ползунком найти число рестартов, минимизирующее типичную ошибку.
- Объяснить, почему очень большое число рестартов превращает метод в случайный поиск.
Зал 15 · Шаг, который учится
Правило одной пятой Рехенберга заставляет σ настраиваться само по доле принятия. График показывает, как σ убывает само собой. Зал заканчивается неудобным результатом: в чаше адаптивный шаг улучшает на шесть порядков, а в лотке ухудшает вдесятеро, потому что внутри ложной ямки высокая доля принятия заставляет σ замкнуться на себе.
Задания для ученика
- Назвать целевую долю принятия в правиле одной пятой.
- Сравнить фиксированное и адаптивное σ на двух ландшафтах.
- Определить, почему механизм проваливается именно тогда, когда хорошо работает.
Зал 16 · Шаг назад
Второй выход из локальных оптимумов: принимать ухудшение с фиксированной вероятностью p. Две крайности — уже знакомые методы (p = 0 — локальный поиск, p = 1 — случайное блуждание), а оптимум около 0,2, в семь раз лучше, чем не принимать никогда. Зал завершается указанием на изъян фиксированного p: оно одинаково относится к мелкой оступке и к катастрофе.
Задания для ученика
- Найти вероятность, минимизирующую типичную ошибку на лотке.
- Объяснить, почему принимать всё тоже плохо.
Зал 17 · Температура
Критерий Метрополиса: P = e^(−Δf/T). Интерактивный график показывает вероятность принятия в зависимости от величины ухудшения при разных температурах. Подчёркивается редко объясняемая деталь: T измеряется в единицах f, поэтому тепловатая температура на одном ландшафте на другом заморожена.
Задания для ученика
- Вычислить конкретные вероятности принятия по формуле.
- Найти температуру, принимающую заданное ухудшение в половине случаев.
- Сказать, что делает формула с предложением, которое даёт улучшение.
Зал 18 · Охлаждение
До формул отжиг показывают в движении: каждый шаг пути окрашен по тому, перешёл ли метод в лучшее место, принял худшее или отверг предложение, а три полосы показывают потраченный бюджет, вероятность принять ухудшение и число уже принятых ухудшений. Затем появляются T₀ и коэффициент охлаждения α, график температуры во времени стоит над порождаемой ею кривой сходимости, и три расписания показывают, от чего гибнет каждое: мгновенное замерзание, всегда горячо и холодный старт. Бюджетное задание просит пару (T₀, α), решающую иглы хотя бы в 4 из 5 зёрен за 3000 вычислений.
Задания для ученика
- Посчитать, сколько ухудшений принимает расписание «всегда горячо» за полный запуск.
- Вычислить, что остаётся от начальной температуры при α = 0,99 через 2000 шагов.
- Пройти задание, найдя пару (T₀, α), работающую на большинстве зёрен.
Зал 19 · Дуэль: отжиг против локального поиска
Сначала дуэль вживую: оба метода стартуют из одной точки, с одним бюджетом и одним прыжком, на каждом из пяти ландшафтов. Затем таблица: 1500 вычислений, σ = 0,02, сорок одно зерно. Результат намеренно неудобен: отжиг выигрывает там, где есть ловушки (лоток, иглы), и явно проигрывает там, где их нет (чаша, долина), ведь каждое принятое ухудшение — вычисление, потраченное на движение назад. Это первое явное появление тезиса лаборатории.
Задания для ученика
- Посмотреть пять дуэлей и отметить ландшафты, где выигрывает отжиг.
- Объяснить, почему более изощрённый метод проигрывает в чаше.
- Решить, что разумнее всего делать с новой задачей, о которой ничего не известно.
Зал 20 · Рой
Несколько искателей сразу, бюджет делится между ними. Пока без общения, чтобы выделить эффект количества. Бюджетное задание этого зала — самое эффектное в лаборатории: ровно за десять шагов надо найти минимальное число частиц, при котором медиана 21 запуска опускается ниже ошибки 0,1 на иглах, и скачок оказывается очень резким.
Задания для ученика
- Сравнить мало частиц с многими шагами против многих частиц с малым числом шагов.
- Найти минимальное число частиц, преодолевающее порог за десять шагов.
- Объяснить, что не так с роем из 100 частиц, который при 1000 вычислений успевает сделать лишь 9 шагов.
Зал 21 · Что знает группа
Включается общение: каждая частица притягивается и к своей лучшей позиции (когнитивное притяжение, c₁), и к лучшей во всём рое (социальное притяжение, c₂). При 1500 вычислениях каждое изменение регулятора запускает новый поиск, а табло показывает, сколько из 21 запуска доходят до глобального минимума, и медиану ошибки, потому что на иглах результат — всё или ничего. Обе крайности проваливаются по противоположным причинам с одинаковым итоговым числом, что заставляет смотреть на рой, а не только на ошибку: при нулевом социальном притяжении это независимые поиски, при нулевом когнитивном рой преждевременно схлопывается.
Задания для ученика
- Поставить c₁ = 0 на иглах и описать, что происходит с роем.
- Решить, проваливается ли c₂ = 0 по той же причине, что c₁ = 0.
- Найти отношение c₁/c₂, при котором рой чаще всего доходит до глобального минимума на иглах.
- Сравнить чашу и иглы, увеличивая число частиц с 3 до 20.
Зал 22 · Инерция
Третий коэффициент роя с особенностью, ценной дидактически: в какую сторону его крутить, зависит от ландшафта. Две карты рядом при одном значении показывают, что в чаше чем меньше инерция, тем лучше, а на иглах есть чёткий оптимум, и оба провала видны: ниже него рой замирает, выше — частицы отскакивают от стенок.
Задания для ученика
- Найти наибольшее w, при котором все частицы в чаше сходятся в одну точку.
- Вывести из условия устойчивости, после какого значения частицы перестают оседать.
- Объяснить, что говорит о выборе параметров то, что в чаше лучший вариант — w = 0.
Зал 23 · Рой во многих измерениях
Горизонтальная ось перестаёт быть временем и становится размерностью. При одном бюджете в 3000 вычислений три метода сравниваются на лотке для яиц в размерностях 2, 3, 5, 10 и 20: важен не победитель столбца, а наклон каждой кривой. Бюджетное задание в размерности 10, с проекцией роя на x₁ и x₂ и кривой сходимости, к тому же показывает, что слишком много частиц — так же плохо, как слишком мало.
Задания для ученика
- Читать график по наклону: что происходит с дротиками при переходе от d = 2 к d = 10.
- Найти число частиц, при котором медиана 21 запуска опускается ниже 0,07 в размерности 10.
- Объяснить, почему 300 частиц при 3000 вычислениях дают гораздо худший результат, чем 20.
Зал 24 · Выбирать лучших
Генетический блок начинается без скрещивания, изолируя отбор: потомки — мутировавшие копии родителя, выбранного турниром из k, то есть давлением отбора. Два регулятора, турнир и размер популяции, и два ландшафта; бюджет в 1500 вычислений не меняется, так что вдвое большая популяция живёт вдвое меньше поколений. На иглах, где глобальная структура обманывает, результат очень чёткий: из ошибки 0,14 метод выводит популяция, а не давление, потому что отбор не может выбрать то, чего не принесла ни одна начальная особь (формула зала 4).
Задания для ученика
- Пройти оба регулятора на иглах и решить, какой из них выводит метод из 0,14.
- Найти пару (k, популяция), при которой медиана 41 запуска опускается ниже 0,01 на иглах.
- Объяснить, во что превращается метод при полном отсутствии отбора.
Зал 25 · Смешать два решения
Однородное скрещивание и гипотеза строительных блоков с измеренным пределом. При двух регуляторах, вероятности скрещивания p и давлении k, один эксперимент на двух ландшафтах: на сепарабельном лотке скрещивание улучшает результат почти втрое; в кривой долине, где переменные сцеплены, оно не даёт ничего. Вводится слово эпистаз и объясняется, почему историческое обещание скрещивания не сбылось. Заключительная заметка представляет скрещивание BLX-0,5, самое распространённое при непрерывных переменных.
Задания для ученика
- При p = 1 пройти по давлению и увидеть, от чего зависит выигрыш от скрещивания.
- По формуле определить, поможет ли скрещивание.
- Посчитать, сколько разных потомков может дать однородное скрещивание двух родителей в размерности 2.
Зал 26 · Мутировать, не теряя лучшего
Две детали, не дающие генетическому алгоритму сломаться. Мутация — единственный источник нового материала: без неё метод лишь перекомбинирует то, что уже было в начальной популяции. Элитизм показан графически: без него кривая лучшего в популяции перестаёт быть монотонной и подскакивает вверх при каждой потере лидера.
Задания для ученика
- Сравнить кривые лучшего в популяции с элитизмом и без него.
- Подобрать мутацию и число элит (от 0 до 4), чтобы медиана 21 запуска опустилась ниже 10^(−6) на иглах при 2000 вычислений.
- Сказать, что происходит с методом, если все координаты всех потомков мутируют всегда.
Зал 27 · Катящийся треугольник
Симплекс Нелдера — Мида, детерминированный и безградиентный, с четырьмя ходами, анимированными шаг за шагом. Разобранный пример с целыми числами вычисляет отражённую точку вручную. Четыре ландшафта показывают, куда он доходит: в чаше — 21 раз из 21, в кривой долине — 20 из 21, на лотке — 5 из 21, на иглах — ни разу. Спойлер рассказывает, что это самый используемый в мире безградиентный оптимизатор и что при этом у него нет теоремы о сходимости в размерности больше единицы.
Задания для ученика
- Посмотреть, как треугольник катится шаг за шагом на четырёх ландшафтах, и распознать каждый ход.
- Объяснить, почему отражение всегда заменяет худшую вершину.
- Сказать, что делает метод, если отражённая точка лучше всех трёх вершин.
- Определить, в какой ситуации этому методу приходится хуже, чем остальным.
Зал 28 · Использовать наклон
Очевидный вопрос — почему не использовать производную? — с честным ответом: градиент, оценённый разностями, стоит d+1 вычисление на шаг, и даже с этой платой ему нужно 16 вычислений, чтобы опуститься ниже ошибки 10^(−6) в чаше, тогда как рою нужно 586, а случайный поиск не справляется и за 20 000. Ползунок скорости η на трёх ландшафтах показывает расходимость при большой скорости в чаше, зигзаг в кривой долине и, на лотке, безупречный спуск в первую же ямку.
Задания для ученика
- Прочитать таблицу необходимых вычислений по методам.
- Вывести из формулы, после какой скорости обучения метод перестаёт сходиться.
- Решить, значат ли 16 против 586, что рой — плохой метод.
- Объяснить, почему на лотке градиент останавливается на высокой и устойчивой ошибке.
Зал 29 · Где разбиваются точные методы
Четыре теста и четыре разные причины: нулевая производная на лестнице, производная чистого шума в тумане, локальные минимумы в лотке и плохая геометрия в долине. Локальный поиск стоит рядом как контроль. Здесь оправдано существование всего предыдущего: эвристики существуют не потому, что никто не умеет дифференцировать, а потому, что во многих задачах производной нет, её нельзя оценить или она никуда не ведёт.
Задания для ученика
- Запустить четыре теста и сравнить градиент с локальным поиском в каждом.
- Найти тест, в котором виноват не градиент, а ландшафт.
- Объяснить, почему туман влияет на градиент гораздо сильнее, чем на локальный поиск.
Зал 30 · Все методы вместе
Повторение перед состязанием: карточки семи методов (название, параметры и псевдокод) и стенд, на котором выбирают ландшафт, метод, размерность (2, 3, 5 или 10) и бюджет, настраивают параметры и запускают один раз или тридцать, с медианой, лучшим и худшим результатом.
Задания для ученика
- Запустить один метод один раз и тридцать раз и сказать, что дают тридцать запусков.
- Испытать семь методов в чаше, на плато и на иглах и сказать, какой выделяется на каждом ландшафте.
Зал 31 · Турнир
Семь методов, пять ландшафтов, один бюджет в 2000 вычислений и по двадцать одному зерну на клетку. Ставка делается до таблицы, чтобы это было настоящим предсказанием. Результат честен и слегка неудобен: полностью зелёной строки нет, а старейший детерминированный метод выигрывает три столбца из пяти на самом благоприятном рельефе. Заметка объясняет, почему отжиг не выигрывает ни одного столбца: его стихия — комбинаторные задачи, а не эти непрерывные ландшафты.
Задания для ученика
- Предсказать до запуска турнира, какой метод выиграет на иглах.
- Прочитать таблицу и определить, кто последний в чаше.
Зал 32 · Когда нельзя доверять измерению
Шум измерений: каждое вычисление возвращает значение с ошибкой внутри, как симуляция со случайными зёрнами или физическое измерение. Выбирают ландшафт (из пяти) и размерность (2 или 10), и график показывает ошибку семи методов по мере роста шума от 0% до 20%. В чаше Нелдер — Мид без шума опускается до 4,6·10^(−87), а при 1% шума — лишь до 1,9·10^(−3); при этом 1% все методы попадают в одну полосу, а начиная с 5% популяционные методы отрываются и выигрывают.
Задания для ученика
- Объяснить, почему немного шума отбрасывает Нелдера — Мида на столько порядков.
- Объяснить, почему популяция переносит шум лучше, чем одна точка.
- Указать, чего не хватает в рассуждении того, кто выбирает метод для новой задачи по тому, как он сработал на другой.
Зал 33 · Бесплатных обедов не бывает
Ландшафт, где учиться не на чем: плоский везде, кроме одной спрятанной коробочки. Таблица — не ничья, а нечто лучшее: чистая случайность находит её в 98% случаев, а градиент никогда, потому что все изощрённые методы разделяют один изъян — перестают смотреть широко, как только им кажется, что они что-то нашли. Отсюда формулируется теорема Уолперта и Макреди с упором на то, чего она НЕ говорит.
Задания для ученика
- Запустить поиск и сравнить доли нахождения у семи методов.
- Назвать изъян, общий здесь для изощрённых методов.
- Отличить верную формулировку теоремы от её преувеличенных прочтений.
Зал 34 · Задание
Практический экзамен перед последним залом: функция, которой нет в каталоге и которую не видно до самого конца, и 120 измерений, расходуемых четырьмя заходами по 30. Перед каждым заходом выбирают метод и параметры, а лучшая найденная точка переходит в следующий заход. В конце открывается рельеф (шесть неправильно расположенных ям, одна большая служит приманкой), результат сравнивается с медианой 120 случайных дротиков, а последняя конфигурация перезапускается 21 раз, чтобы отделить расчёт от везения.
Задания для ученика
- Потратить 120 измерений, выбирая метод и параметры в каждом заходе.
- Объяснить, почему отжиг с очень короткими прыжками и высокой температурой — худшая из возможных конфигураций.
- Сделать честный вывод по гистограмме своей конфигурации, перезапущенной 21 раз.
Зал 35 · Выберите метод
Финальный диагностический зал. Шесть реальных ситуаций — очень дорогое вычисление, шумная функция, двести переменных, выпуклая функция без производной, комбинаторная задача и спрятанный далеко глобальный минимум, — и в каждой надо выбрать метод, с которого начать. Нового не учат: применяют всё прежнее. Зал завершается полным набором инструментов и мостиком к лаборатории биоинспирированной оптимизации.
Задания для ученика
- Выбрать подходящий метод в каждой из шести ситуаций.
- Обосновать выбор тем, что было в предыдущих блоках.
Залы для показа
Самые наглядные для показа и обсуждения в классе.