Оптимізація

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

Оптимізаційні задачі

Проблеми максимізації та мінімізації можна розв’язувати за допомогою тих самих методів, оскільки кожна задача максимізації може бути перетворена в задачу мінімізації (і навпаки) інвертуванням цільової функції. Однак різні методи відрізняються тим, чи можна їх використовувати в дискретному чи безперервному просторі (у безперервному просторі змінні можуть набувати довільних дійсних чисел) і чи може проблема містити обмежувальні умови.

Систематичний пошук

Найпростіший підхід — спробувати всі варіанти (груба сила). У безперервному просторі можливості нескінченні, але можна систематично пробувати всі комбінації значень із певною роздільною здатністю (пошук у сітці). Цей підхід застосовний лише до дуже невеликих проблем, оскільки кількість можливостей експоненціально зростає з кількістю змінних. Під час розв’язання задачі про рюкзак ми можемо брати або не брати кожен об’єкт, тому існує 2^n можливих комбінацій об’єктів.

Ефективніше призначати значення змінним поступово і постійно оцінювати найкраще можливе значення рішення з заданим частковим призначенням. Коли ця межа гірша за найкраще рішення, знайдене на даний момент, ми можемо пропустити всю гілку та бути впевненими, що ми не пропустили оптимальне рішення. Цей варіант пошуку дерева називається методом **розгалуження та зв’язку*. Щоб вибрати наступний стан для дослідження, можна використати голодний критерій – стан із найкращим граничним значенням (або іншою стратегією перегляду простору станів).

Голодний і випадковий пошук

Систематичний пошук гарантує знаходження глобального оптимуму, але дуже часто надто повільний для практичних завдань. Для прискорення необхідно відмовитися від вимоги оптимального рішення, на щастя, для більшості практичних завдань достатньо рішення, яке є «досить хорошим». Потім для прискорення можна використовувати голод і випадковість.

Голодний пошук вибирає значення для кожної змінної, яке здається найкращим на даний момент, і не повертається до цих рішень. Під час вирішення проблеми з рюкзаком ми могли брати предмети з найвищим співвідношенням ціна/вага один за одним, поки вони не помістяться в рюкзак. Голодний пошук дуже швидкий, але знайдене рішення може бути дуже поганим. Між крайнощами голодного пошуку (випробування одного шляху) і систематичного пошуку дерева (випробування всіх шляхів) існує променевий пошук (випробування фіксованої кількості шляхів). Променевий пошук залишає лише фіксовану кількість найкращих станів на кожному рівні дерева та відкидає інші.

Випадковий пошук перевіряє випадково вибрані рішення (замість усіх можливих). Існують більш складні техніки, які поступово збільшують ймовірність вибору рішень у перспективних областях – вони намагаються збалансувати дослідження недосліджених областей (випадковість) і використання інформації про більш досліджені (голод). Цей компроміс між дослідженням і використанням є загальним принципом, який можна зустріти у багатьох алгоритмах оптимізації.

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

Локальний пошук

Альтернативою поступовому створенню рішення є початок з довільного рішення та поступове покращення його невеликими змінами. Цей підхід називається локальним пошуком. Ми називаємо набір найближчих рішень, які відрізняються від поточного однією зміною, оточенням. (Під час розв’язання задачі про рюкзак до оточення можуть входити, наприклад, ті комбінації, які відрізняються щонайбільше одним доданим і одним вилученим предметом.) Існують різні евристики для вибору наступного рішення з оточення. Алгоритм підйому вибирає деякі поліпшувальні рішення або найкраще рішення з оточення (цей варіант алгоритму підйому називається методом максимального підйому).

Використовуючи ці голодні евристики, ми швидко приходимо до локального оптимуму, тобто рішення, яке є найкращим у своєму оточенні, але не обов’язково має бути глобальним оптимумом. Шанси знайти глобальний оптимум можна збільшити за допомогою випадковості. Імітація відпалу випадково вибирає з оточення: якщо нове рішення є поліпшенням, то ми його приймаємо, якщо це не поліпшення, то приймаємо його з певною імовірністю, яка поступово зменшується.

Еквівалентом локального пошуку в безперервному просторі є градієнтний спуск. У безперервному просторі часто можна обчислити напрямок, у якому цільова функція спадає або зростає найшвидше (так званий градієнт), тоді немає потреби тестувати різні рішення поблизу. Градієнтний спуск зазвичай використовується у машинному навчанні, наприклад, для оптимізації ваг нейронної мережі.

Пошук сукупностей

Під час пошуку сукупностей ми вдосконалюємо багато рішень одночасно. Це дає змогу вибрати найкраще рішення з поточної сукупності та, можливо, комбінувати різні рішення. Прикладом є генетичні алгоритми, створені за принципом еволюції. Розв’язки, що продовжують наступне покоління, вибираються відповідно до їх якості (значення цільової функції), комбінуються («схрещування») і, при необхідності, злегка випадково змінюються («мутація»).

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