Стаття Алгоритми оптимізації · ≈ 9 хв читання

Метаевристики: теорема no free lunch

Кожні кілька років хтось стверджує, що його новий алгоритм, натхненний природою, "перевершує генетичні алгоритми та оптимізацію роєм часток на кожному бенчмарку". Теорема 1997 року доводить, що це не може бути правдою в загальному випадку — і розуміння чому змінює те, як насправді слід обирати алгоритм оптимізації.

Коротко: Теорема No Free Lunch Волперта і Макріді (1997) доводить, що усереднено по всіх можливих задачах жоден алгоритм оптимізації не кращий за інші — тож GA, PSO, ACO чи SA не можуть бути універсально найкращими. На практиці важливо не шукати "магічний" алгоритм, а підбирати структуру алгоритму під структуру конкретної задачі.

Автор: MySimulator Team · Рецензент: MySimulator Editorial Review · Оновлено: 9 липня 2026

1. Що таке метаевристика

Метаевристика — це загальна стратегія пошуку, що спрямовує базову евристику до хороших рішень у великому чи погано вивченому просторі пошуку, не будучи адаптованою під одну конкретну задачу. Генетичні алгоритми (GA), оптимізація роєм часток (PSO), оптимізація мурашиною колонією (ACO) та імітація відпалу (SA) — всі є метаевристиками: вони трактують цільову функцію як чорну скриньку, оцінюють кандидатів-рішення і адаптують пошук лише на основі отриманих оцінок.

Ця властивість чорної скриньки саме те, що робить метаевристики настільки широко застосовними — і саме те, що обмежує теорема No Free Lunch.

2. Теорема No Free Lunch

У 1997 році Девід Волперт і Вільям Макріді опублікували "No Free Lunch Theorems for Optimization", довівши оманливо простий, але далекосяжний результат: усереднено по всіх можливих цільових функціях, кожен алгоритм оптимізації працює однаково. Випадковий пошук справляється так само добре, в середньому, як і найвитонченіший генетичний алгоритм — за умови, що середнє береться по всьому простору мислимих задач, включно з тими, що не мають жодної експлуатованої структури.

Чому це не так похмуро, як звучить

"Середнє по всіх функціях" включає цільові функції, що є чистим шумом, активно оманливими чи фрактально розривними — ландшафти, які жодна реальна інженерна задача ніколи не породжує. NFL — це твердження про простір усіх математично можливих задач, а не про простір задач, які люди справді розв'язують.

3. Математичне формулювання

Розглянемо скінченний простір пошуку X і скінченний простір можливих значень Y, тож цільова функція — це відображення f: X → Y. Нехай P(d_y^m | f, m, a) позначає ймовірність того, що алгоритм a спостерігає конкретну послідовність з m вибраних значень d_y^m після m обчислень функції f.

No Free Lunch (неформальне формулювання) Σ_f P(d_y^m | f, m, a₁) = Σ_f P(d_y^m | f, m, a₂)

для будь-яких двох алгоритмів a₁ і a₂, підсумовано по всіх можливих цільових функціях f. Словами: сума (а отже і середнє) ефективності по всьому простору функцій однакова для кожного алгоритму.

Інтуїція: оскільки простір пошуку всіх функцій f: X → Y комбінаторно величезний і включає кожну можливу перестановку виходів, будь-яка структура, яку алгоритм використовує, щоб добре працювати на деяких функціях, точно компенсується рівною кількістю функцій, де ця сама структура активно вводить його в оману.

4. Наслідки: немає універсально найкращого алгоритму

  • Твердження на кшталт "алгоритм X — найкраща метаевристика" безглузді без уточнення класу задач, що розв'язуються.
  • Порівняння бенчмарків (GA проти PSO на 30 стандартних тестових функціях) розповідають лише про ефективність на цих конкретних функціях — не про універсальний рейтинг.
  • Алгоритм, що експлуатує реальну структуру (гладкість, сепарабельність, відому симетрію) у вашому реальному класі задач, послідовно перевершуватиме загальний пошук на цьому класі — NFL цього не забороняє, вона забороняє лише універсальну перевагу.

Ось чому вибір алгоритму на практиці — це емпірична, специфічна для домену вправа, а не пошук одного "найкращого" методу.

5. Практичний висновок

Оскільки жоден алгоритм не домінує універсально, справжня точка важеля — це відповідність структури алгоритму структурі задачі та впровадження доменних знань, де це можливо:

  • Гладкі, диференційовні ландшафти — градієнтні методи зазвичай прямо перевершують метаевристики; чорна скринька взагалі не потрібна.
  • Комбінаторні, графові задачі (маршрутизація, планування) — феромонна структура ACO напряму кодує інформацію про вартість шляху.
  • Неперервні, мультимодальні ландшафти — швидкісне дослідження PSO експлуатує гладку локальність; кросовер GA експлуатує структуру будівельних блоків, коли підрішення добре комбінуються.
  • Пересічені ландшафти з багатьма локальними оптимумами і малою структурою — контрольована випадковість імітації відпалу опирається потраплянню в пастку, ціною повільнішої збіжності.
Доменні знання перевершують загальну потужність

Добре спроєктоване кодування, хороша початкова здогадка чи власний крок локального пошуку, адаптований під специфічну структуру вашої задачі, зазвичай перевершує перемикання між загальними метаевристиками — теорема NFL, по суті, є аргументом на користь вбудовування доменних знань в алгоритм, а не пошуку магічного універсального рішення.

6. GA проти PSO проти SA на різних ландшафтах

🧬

Генетичний алгоритм

Переважає, коли хороші "будівельні блоки" рішення можна рекомбінувати — наприклад, дискретні, модульні задачі, як планування чи відбір ознак.

🐦

PSO

Переважає на неперервних, плавно змінюваних ландшафтах, де близькі точки простору параметрів мають подібну якість — наприклад, налаштування гіперпараметрів нейромережі.

🌡️

Імітація відпалу

Переважає на пересічених, багатовимірних ландшафтах з багатьма оманливими локальними оптимумами, де контрольована температурою випадковість запобігає передчасній збіжності.

На бенчмарку типу функції Растригіна (сильно мультимодальна, але симетрична й гладка) PSO чи GA зазвичай сходяться найшвидше. На справді оманливому ландшафті, сконструйованому щоб вводити в оману градієнтну поведінку, чисто випадкове збурення імітації відпалу може перевершити обидва — саме такий ландшафт, який, за NFL, існує для кожного алгоритму.

7. Ілюстрація теореми

// Концептуальна ілюстрація: середня ефективність по УСІХ
// можливих цільових функціях однакова для будь-якого алгоритму

function averagePerformance(algorithm, allPossibleFunctions):
  total = 0
  for each f in allPossibleFunctions:
    total += runAlgorithm(algorithm, f, budget = M)
  return total / allPossibleFunctions.length

  // Теорема NFL: це середнє ОДНАКОВЕ для кожного алгоритму,
  // бо allPossibleFunctions включає кожну перестановку виходів —
  // для кожної функції, яку алгоритм обробляє добре, існує
  // "дзеркальна" функція, де він обробляє так само погано,
  // скасовуючи будь-яку чисту перевагу.

  // Що насправді має значення на практиці:
  averagePerformance(algorithm, yourRealProblemClass)
  // ← ЦЕ середнє може і справді відрізняється між алгоритмами,
  // бо реальні класи задач — це крихітна, структурована підмножина
  // "усіх можливих функцій".

Ось чому кожне надійне бенчмарк-дослідження звітує результати на конкретному, названому тестовому наборі (CEC, BBOB, Растригін, Розенброк), а не заявляє про універсальну перевагу — твердження завжди неявно означає "найкращий на цьому структурованому класі задач", ніколи "найкращий на всіх мислимих цільових функціях".

Часті запитання

Що таке теорема No Free Lunch?

Теорема No Free Lunch, доведена Волпертом і Макріді у 1997 році, стверджує, що усереднено по всіх можливих цільових функціях, кожен алгоритм оптимізації має точно однакову очікувану ефективність. Жоден алгоритм не може бути універсально кращим за інший без експлуатації структури, специфічної для класу задач.

Чи означає No Free Lunch, що всі алгоритми однаково хороші на практиці?

Ні. NFL застосовується до середнього по простору УСІХ можливих цільових функцій, включно з чистим випадковим шумом, що не репрезентує реальні задачі. Реальні задачі оптимізації мають експлуатовану структуру, тож алгоритм, підібраний під цю структуру, може значно перевершити інші на задачах, які дійсно важливі.

Що таке метаевристика?

Метаевристика — це загальна, незалежна від задачі стратегія для спрямування пошуку простором рішень, наприклад генетичні алгоритми, оптимізація роєм часток, імітація відпалу чи оптимізація мурашиною колонією. Метаевристики не гарантують глобальний оптимум, але зазвичай швидко знаходять хороші рішення для великих чи складних просторів пошуку.

Хто довів теорему No Free Lunch і коли?
Девід Волперт і Вільям Макріді довели її у праці 1997 року "No Free Lunch Theorems for Optimization", опублікованій в IEEE Transactions on Evolutionary Computation. Результат спирався на попередню пов'язану роботу Волперта про навчання з учителем, розширену на контекст пошуку та оптимізації.
Чи застосовується NFL до вибору моделі машинного навчання теж?
Так — оригінальні результати No Free Lunch спершу розроблялись для навчання з учителем, показуючи, що жоден єдиний алгоритм навчання не узагальнюється найкраще по всіх можливих розподілах генерації даних. Версія для оптимізації — тісно пов'язана теорема в тому ж дусі, застосована до пошуку, а не до висновку.
Чому статті постійно стверджують, що їхній новий алгоритм перевершує GA і PSO на бенчмарках?
Бо ці твердження неявно обмежені конкретним, названим набором бенчмарків (структурованою підмножиною всіх можливих функцій), що повністю узгоджується з NFL. Теорема забороняє лише твердження про універсальну перевагу по кожній мислимій цільовій функції — вона не забороняє одному алгоритму перевершувати інший на добре визначеному класі реалістичних задач.
Як насправді обирати між GA, PSO, ACO і SA для реальної задачі?
Відповідайте структуру алгоритму структурі задачі: використовуйте ACO для графових/маршрутизаційних задач з чітко визначеними вартостями ребер, PSO для неперервних гладких ландшафтів, GA для задач з рекомбінованими будівельними блоками, а імітацію відпалу для пересічених ландшафтів з багатьма оманливими локальними оптимумами. Якщо сумніваєтесь — протестуйте кілька кандидатів на репрезентативних екземплярах вашої реальної задачі, а не довіряйте загальним твердженням.
Чи порушує додавання доменних знань теорему No Free Lunch?
Ні — NFL саме та теорема, що мотивує додавання доменних знань. Вона доводить, що загальний алгоритм без знань не може бути універсально найкращим, тож єдиний спосіб надійно перевершити інші підходи на вашій конкретній задачі — це впровадити структуру: розумніше кодування, специфічний для домену крок локального пошуку чи ініціалізацію, що враховує задачу.
Чи справді випадковий пошук такий самий хороший, як генетичний алгоритм у середньому?
Лише коли усереднено буквально по кожній мислимій цільовій функції, включно зі штучно сконструйованими без жодної експлуатованої регулярності — набір, що включає майже жодну задачу, яку хтось насправді хоче розв'язати. На структурованих, гладких чи графових задачах, що виникають на практиці, добре підібрана метаевристика надійно й суттєво перевершує випадковий пошук.
Що означає "безкоштовний обід" у назві цієї теореми?
Назва відсилає до ідіоми "не буває безкоштовного обіду" — означаючи, що не можна отримати щось (універсально найкращу ефективність оптимізації) задарма (без сплати ціни спеціалізації під конкретний клас задач). Теорема формалізує, що будь-який виграш ефективності на деяких задачах має бути сплачений еквівалентною втратою на інших, якщо усереднити по всьому простору можливих задач.
▶ Жива демонстрація

🐜 Побачте, як метаевристика експлуатує реальну структуру

Симуляція мурашиної колонії показує ACO — метаевристику, налаштовану на експлуатацію графової структури задач найкоротшого шляху, а не універсальний оптимізатор.

Відкрити симуляцію →

🔗 Пов'язані симуляції

🐜Мурахи 🧬Генетика