Оптимизация
Метаэвристики: GA, SA, ACO
1983 год: физики Kirkpatrick, Gelatt и Vecchi публикуют статью в Science - они берут термодинамику плавления металла и превращают её в алгоритм оптимизации. Идея: иногда надо принять худшее решение, чтобы выбраться из локального минимума. Отжиг нашёл лучшие решения задач компоновки СБИС, чем все детерминированные методы того времени.
- **NAS (Neural Architecture Search):** evolutionary strategies (CMA-ES, NEAT) ищут архитектуры нейросетей - Google NASNet, EfficientNet созданы с участием EA
- **Расписания:** SA и GA оптимизируют расписания авиакомпаний, больниц, производств когда ILP слишком медленен
- **Hyperparameter optimization:** Optuna использует TPE (Tree-structured Parzen Estimator) - вариант BO; EA (CMA-ES) - для NAS
Предварительные знания
Имитация отжига (SA)
**Simulated Annealing** вдохновлена физическим процессом отжига металлов: медленное охлаждение позволяет атомам найти глобально минимальное энергетическое состояние. В оптимизации: принимаем «плохие» решения с вероятностью exp(-ΔE/T), которая убывает с температурой T. Это позволяет вырываться из локальных минимумов.
| Параметр | Маленькое значение | Большое значение |
|---|---|---|
| T0 (начальная температура) | Мало exploration, быстро застрянем | Много exploration, медленная сходимость |
| alpha (скорость охлаждения) | Быстрое охлаждение, может застрять | Медленное охлаждение, лучше качество |
| max_iter | Мало шагов, слабое решение | Хорошее качество, дорого |
SA принимает «плохое» решение с вероятностью exp(-ΔE/T). Зачем принимать ухудшающие решения?
Генетические алгоритмы
**Генетические алгоритмы (GA)** моделируют эволюцию: популяция решений («хромосом») эволюционирует через селекцию (отбор лучших), кроссовер (смешение родителей) и мутацию (случайные изменения). Принцип: «выживает наиболее приспособленный».
**Evolutionary Strategies (ES)** для continuous optimization: шаг мутации σ адаптируется (self-adaptive). CMA-ES (Covariance Matrix Adaptation) - state-of-the-art вариант, используется в OpenAI для HPO и NAS (Neural Architecture Search).
В GA высокая mutation_rate (0.5) vs низкая (0.001). Что произойдёт с высокой mutation rate?
Муравьиные колонии (ACO)
**Ant Colony Optimization (ACO)** моделирует поведение муравьёв: каждый муравей строит решение, следуя феромонным следам. Хорошие решения оставляют больше феромонов, привлекая других муравьёв. Испарение феромонов предотвращает застревание в локальных оптимумах.
**ACO vs SA vs GA:** ACO лучше для задач на графах (TSP, routing) где естественна «тропинка». SA лучше для continuous optimization с гладким ландшафтом. GA лучше для задач с хорошо разделимыми компонентами (поддерживает building blocks через кроссовер).
Зачем в ACO нужно испарение феромонов (evaporation)?
Когда использовать метаэвристики
Метаэвристики - не первый выбор. Их используют когда: 1. задача NP-сложная и нет аппроксимации с гарантией 2. функция недифференцируемая или чёрный ящик 3. пространство поиска смешанное (continuous + discrete) 4. нужна интерпретируемая структура решения.
Метаэвристики не гарантируют глобальный оптимум. Результат зависит от начальной инициализации, гиперпараметров (T0, alpha, population size) и случайности. Для воспроизводимости всегда фиксируйте random seed и запускайте несколько раз.
Метаэвристики - всегда лучший выбор для сложных реальных задач
Метаэвристики - последний выбор, когда точные методы и аппроксимации недоступны. Для выпуклых задач - IPM/BFGS. Для NP-сложных с аппроксимацией - специализированный алгоритм. Для HPO - Bayesian Optimization.
Метаэвристики не дают гарантий качества и требуют тюнинга собственных гиперпараметров (T0, population size). Для задач со структурой (выпуклость, граф, LP-relax) специализированные алгоритмы лучше. Метаэвристики незаменимы только для black-box задач и задач без известной структуры.
Задача оптимизации гиперпараметров нейросети: batch_size, lr, n_layers - все дискретные. Функция - val_accuracy (чёрный ящик, дорогой). Какой метод выбрать?
Ключевые идеи
- **SA:** принимает плохие решения с вероятностью exp(-ΔE/T) для выхода из локальных минимумов; лучше всего для smooth continuous landscape
- **GA:** популяция решений + отбор + кроссовер + мутация; evolutionary strategies (CMA-ES) - state-of-the-art вариант для continuous HPO
- **ACO:** феромонные следы усиливают хорошие пути; испарение предотвращает преждевременную сходимость; лучше для задач на графах
- **Выбор:** метаэвристики - последний вариант; для HPO - Bayesian Optimization; для комбинаторики с ILP - Branch & Cut
Связанные темы
Метаэвристики - инструмент когда другие методы не работают:
- Комбинаторная оптимизация — Метаэвристики используются для NP-сложных задач (TSP, scheduling) без аппроксимаций
- Bayesian Optimization — BO - умная альтернатива для black-box HPO: суррогатная модель вместо случайного поиска
- Multi-Objective Optimization — NSGA-II - генетический алгоритм для многокритериальных задач (Pareto front)
Вопросы для размышления
- SA и GA оба могут выходить из локальных минимумов: SA через температуру, GA через популяцию. В чём принципиальное различие механизмов? Для каких задач каждый лучше?
- ACO изначально разработан для TSP, но применяется и в других задачах. Что должно быть у задачи, чтобы ACO работал хорошо?
- Как бы вы объяснили бизнес-стейкхолдеру, почему SA/GA для расписания не гарантирует оптимального решения, но всё равно полезен?