Теорема про відсутність безкоштовних сніданків у пошуку та оптимізації
З Вікіпедії, безкоштовно encyclopedia
В обчислювальних процесах є обставини, за яких усі методи розв'язку однієї задачі виявляються статистично ідентичними. Мальовничим способом представлення таких обставин, запропонованим Девідом Вульпертом та Вільямом Дж. Маккріді в зв'язку з проблемами пошуку та оптимізації, є вислів — «Безкоштовних сніданків не існує». Перед цим Вульперт вивів цю теорему для машинного навчання (статистичного висновування). Перед публікацією роботи Вульперта, Каллен Шаффер підсумував переддруковану версію роботи Вульперта, але використав іншу термінологію.
В розгорненні метафори про безкоштовні сніданки, кожен «ресторан» (процедура, що розв'язує проблему) має «меню», асоціюючи кожну «страву» (проблему) з ціною (продуктивністю процедури, що вирішує цю проблему). Меню ресторанів ідентичні за винятком однієї деталі — ціни перемішані від одного ресторану до іншого. Для всеядної істоти, яка буде куштувати будь-яку страву, середня вартість обіду не залежить від вибору ресторану. Але вегетаріанець, що регулярно снідає разом з плотоядним та бажає заощадити, платить високу середню ціну за один сніданок. Для поступового зниження середньої вартості, потрібно мати поглиблені знання про a) власне саме замовлення та b) вартість цієї страви в усіх ресторанах. Таким чином, підвищення продуктивності розв'язання проблем потребує використання попередньої інформації для зіставлення процедур і проблем.
В формальному значенні, вільних сніданків не існує коли ймовірнісний розподіл випадків проблеми такий, що всі розв'язувані проблеми мають однаково розподілені результати. У випадку пошуку, кожен екземпляр проблеми є цільовою функцією, а результатом — послідовність значень, отриманих оцінкою допустимих розв'язків в області значень функції. В типовій інтерпретації результатів, пошук — це процес оптимізації. Безкоштовних сніданків у пошуку немає у випадку, коли і тільки коли розподіл цільової функції є константою з перестановок на множині допустимих розв'язків. Ця умова не виконується точно на практиці, але теорема про (майже) не існуючі безкоштовні сніданки пропонує її наближене виконання.