Топ питань
Часова шкала
Чат
Перспективи
Глобальна оптимізація
З Вікіпедії, вільної енциклопедії
Remove ads
Глобальна оптимізація — це розділ прикладної математики та числового аналізу, який намагається знайти глобальні мінімуми або максимуми функції або множини функцій на заданій множині. Зазвичай це описується як проблема мінімізації, оскільки максимізація дійсної функції еквівалентна мінімізації функції .

Дано нелінійну та невипуклу неперервну функцію з глобальними мінімумами і множина усіх глобальних мінімізаторів в , стандартну задачу мінімізації можна подати як
тобто знаходження і глобальний мінімізатор в ; де є (не обов'язково опуклою) компактною множиною, визначеною нерівностями .
Глобальна оптимізація відрізняється від локальної оптимізації тим, що вона зосереджена на пошуку мінімуму або максимуму над заданою множиною, на відміну від пошуку локальних мінімумів або максимумів. Знайти довільний локальний мінімум відносно просто за допомогою класичних методів локальної оптимізації. Знайти глобальний мінімум функції набагато складніше: аналітичні методи не завжди можна застосовати, а використання підходів чисельного розв'язання часто призводить до дуже складних обчислювальних завдань.
Remove ads
Загальна теорія
Узагальнити
Перспектива
Сучасний підхід до проблеми глобальної оптимізації полягає в розподілі мінімумів.[1] Далі продемонструємо зв'язок між будь-якою безперервною функцією на компактній множині і її глобальними мінімумами . Як типовий випадок, з цього випливає, що
тим часом,
де — це -вимірна міра Лебега множини мінімізаторів . І якщо не є постійною на , монотонні нерівності
виконуються для всіх і , що передбачає низку монотонних включень, і одним із них є, наприклад,
Далі визначаємо розподіл мінімумів як слабку межу таку, що тотожність
виконується для кожної гладкої функції з компактним носієм в . Ось дві безпосередні властивості :
- задовольняє тотожності .
- Якщо є неперервною на , то .
Для порівняння, добре відомо, що зв'язок між будь-якою диференційованою опуклою функцією та її мінімумами строго встановлюється за допомогою градієнта. Якщо диференційована на опуклій множині , то є опуклою тоді і тільки тоді, коли
таким чином, означає, що виконується для всіх , тобто є глобальним мінімізатором на .
Remove ads
Застосування
Типові приклади застосування глобальної оптимізації включають:
- Передбачення структури білка (мінімізація функції енергії/вільної енергії)
- Обчислювальна філогенетика[en] (наприклад, мінімізація кількості перетворень символів у дереві)
- Задача комівояжера та побудова електричної схеми (мінімізація довжини шляху)
- Хімічна інженерія (наприклад, аналіз енергії Гіббса)
- Перевірка безпеки, техніка безпеки (наприклад, механічних конструкцій, будівель)
- Аналіз найгіршого випадку для алгоритмів
- Математичні задачі (наприклад, гіпотеза Кеплера)
- Задача пакування (розробки конфігурації) об'єктів
- Початковою точкою кількох симуляцій молекулярної динаміки є початкова оптимізація енергії системи, що моделюється
- Спінове скло
- Калібрування моделей розповсюдження радіохвиль і багатьох інших моделей у науці та техніці
- Допасовування кривої[en], як аналіз методу нелінійних найменших квадратів[en] та інші узагальнення, які використовуються для допасовування параметрів моделі до експериментальних даних у хімії, фізиці, біології, економіці, фінансах, медицині, астрономії, інженерії
- Планування променевої терапії.
Remove ads
Детерміновані методи
Узагальнити
Перспектива
Найуспішніші загальні точні стратегії:
Внутрішня і зовнішня апроксимація
В обох цих стратегіях множина, над якою функція повинна бути оптимізована, апроксимується многогранниками. У внутрішньому наближенні багатогранники містяться в множині, тоді як у зовнішньому наближенні багатогранники містять множину.
Методи січних площин
Метод січних площин — це загальний термін для методів оптимізації, які ітеративно уточнюють можливу множина або цільову функцію за допомогою лінійних нерівностей, які називаються перерізами. Такі процедури широко використовуються для пошуку цілочисельних розв'язків задач змішаного цілочисельного лінійного програмування, а також для вирішення загальних, не обов'язково диференційованих задач опуклої оптимізації. Використання січних площин для вирішення задач змішаного цілочисельного лінійного програмування було введено Ральфом Е. Гоморі[en] та Вацлавом Хваталом.
Методи гілок і меж
Метод гілок і меж — це парадигма розробки алгоритму для задач дискретної та комбінаторної оптимізації. Алгоритм складається з систематичного перебору варіантів рішень за допомогою пошуку у просторі станів[en]: множина можливих рішень утворює дерево, яке містить всі можливі розв'язки у корені. Алгоритм досліджує гілки цього дерева, які представляють підмножини множини рішень. Перед тим як розглядати можливі варіанти розв'язків гілки, виконують перевірку гілки на верхню та нижню оцінку оптимального розв'язку. Якщо перевірка показує, що гілка не може дати кращого розв'язку, ніж найкращий розв'язок, вже знайдений на поточний момент алгоритмом, то гілка пропускається.
Інтервальні методи
Інтервальна арифметика, інтервальна математика, інтервальний аналіз або інтервальне числення — це метод, розроблений математиками в 1960-х роках як підхід до встановлення обмежень на похибки округлення та вимірювання в математичних обчисленнях і, таким чином, для розробки чисельних методів, які дають надійні результати. Інтервальна арифметика допомагає знаходити надійні та гарантовані рішення рівнянь і задач оптимізації.
Методи, засновані на дійсній алгебричній геометрії
Дійсна алгебра — це частина алгебри, яка має відношення до дійсної алгебричної (і напівалгебричної) геометрії. В цілому вона стосується вивчення впорядкованих полів і впорядкованих кілець (зокрема алгебрично замкнутих полів) та їх застосування до вивчення додатних поліномів[en] і сум квадратів поліномів[en]. Його можна використовувати для опуклої оптимізації.
Remove ads
Стохастичні методи
Узагальнити
Перспектива
Існує кілька точних або неточних алгоритмів на основі Монте-Карло:
Прямий вибірковий метод Монте-Карло
У цьому методі для пошуку наближеного розв'язку використовується випадкове моделювання.
Приклад: задача комівояжера називається класичною задачею оптимізації. Тобто всі факти (відстані між кожною точкою призначення), необхідні для визначення оптимального шляху, відомі, і мета полягає в тому, щоб переглянути можливі варіанти подорожей, щоб знайти той, який має найменшу загальну відстань. Однак припустімо, що замість того, щоб мінімізувати загальну відстань, пройдену для відвідування кожного бажаного пункту призначення, ми хотіли мінімізувати загальний час, необхідний для досягнення кожного пункту призначення. Це виходить за рамки традиційної оптимізації, оскільки час у дорозі за своєю суттю є невизначеним (пробки, час доби, тощо). Як наслідок, щоб визначити наш оптимальний шлях, ми хотіли б використати симуляцію — оптимізацію, щоб спочатку зрозуміти діапазон потенційного часу, який може знадобитися для переходу від однієї точки до іншої (у цьому випадку представлений розподілом ймовірностей, а не конкретною відстанню), а потім оптимізувати наші рішення про подорожі, щоб визначити найкращий шлях, яким слід слідувати, враховуючи цю невизначеність.
Стохастичне тунелювання
Стохастичне тунелювання — це підхід до глобальної оптимізації, заснований на методі Монте-Карло — вибірка функції, яка об'єктивно мінімізується, у якій функція нелінійно перетворюється, щоб полегшити тунелювання між областями, що містять мінімуми функції. Просте тунелювання дозволяє швидше досліджувати простір зразків і забезпечує більш швидку збіжність до оптимального рішення.
Паралельний відпуск
![]() | Цей розділ потребує уваги й турботи фахівця в галузі фізика. Причина — аматорський переклад та можливі помилки в термінології. |
Паралельний відпуск — це метод моделювання, спрямований на покращення динамічних властивостей моделювання фізичних систем методом Монте-Карло та методів Монте-Карло марковських ланцюгів (МКМЛ) загалом. Метод обміну копіями спочатку був розроблений Свендсеном[en][2], потім розширений Гейєром[3] і пізніше розроблений Джорджіо Парізі.[4][5] Сугіта та Окамото сформулювали молекулярно-динамічну версію паралельного відпуска[6] — це зазвичай відомо як молекулярна динаміка обміну репліками.
По суті, запускається N копій системи, випадково ініціалізованих, при різних температурах. Потім на основі критерію Метрополіса відбувається обмін конфігураціями при різних температурах. Ідея цього методу полягає в тому, щоб зробити конфігурації при високих температурах доступними для моделювання при низьких температурах і навпаки. Це призводить до дуже надійного ансамблю, який здатний відбирати як низькоенергетичні, так і високоенергетичні конфігурації. Таким чином, такі термодинамічні властивості, як питома теплоємність, яка, як правило, погано обчислюється в канонічному ансамблі, можуть бути обчислені з високою точністю.
Remove ads
Евристика та метаевристика
Інші підходи включають евристичні стратегії пошуку в просторі пошуку більш-менш інтелектуальним способом, включаючи:
- Мурашиний алгоритм
- Імітація відпалу, загальна імовірнісна метаевристика
- Табу-пошук — розширення локального пошуку, здатне виходити з локальних мінімумів
- Еволюційні алгоритми (наприклад, генетичні алгоритми та еволюційні стратегії)
- Диференціальна еволюція — метод, який оптимізує проблему шляхом повторних спроб покращити простір пошуку з огляду на задану міру якості
- Алгоритми колективного інтелекту (наприклад, оптимізація роїв часток, бджолиний алгоритм, соціальна когнітивна оптимізація і оптимізація мурашиних колоній)
- Меметичні алгоритми[en], що поєднують глобальні та локальні стратегії пошуку
- Реактивний пошук (тобто інтеграція підсимвольних методів машинного навчання в евристику пошуку)
- Поступова оптимізація[en] — метод, який для розв'язання складної задачі оптимізації спочатку розв'язує значно спрощену задачу та поступово перетворює цю задачу (під час оптимізації), поки вона не стане еквівалентною складній задачі оптимізації.[7][8][9]
Remove ads
Підходи, засновані на методології поверхні відгуку
- Непряма оптимізація на основі самоорганізації[en]
- Баєсова оптимізація, стратегія послідовного проектування для глобальної оптимізації функцій чорної скриньки з використанням байєсової статистики[10]
Див. також
- Детермінована глобальна оптимізація[en]
- Міжгалузеве оптимальне проєктування[en]
- Багатокритеріальна оптимізація
- Оптимізація (математика)
Виноски
Список літератури
Посилання
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads