Метаеври́стика — досить невдала назва для опису великого підрозділу, в дійсності основного, в стохастичній оптимізації (stochastic optimization). Стохастична оптимізація є великим класом алгоритмів і методів, які так чи інакше використовують випадковість для пошуку оптимального (або досяжного оптимального) рішення складних завдань. Метаевристики — найзагальніші алгоритми з цього класу і застосовуються для вирішення широкого спектра завдань.
Тип задач метаевристики
Які завдання розглядаються? У справі Якобелліс проти штату Огайо (Jacobellis v. Ohio) (1964 р., справа про фільм нецензурного змісту) суддя Верховного суду США Поттер Стюарт написав свій знаменитий вислів: «Сьогодні я не буду більше намагатися дати визначення тих матеріалів, які я розумію, і які потрібно втиснути в коротке визначення. Цілком можливо, що в мене ніколи не вийде зробити це виразно. Але я впізнаю їх, коли побачу, і фільм, що розглядається в справі, до них не відноситься.»
Метаевристики застосовуються до завдань типу «я впізнаю їх, коли побачу». Це алгоритми, які використовуються для пошуку рішення на завдання, в яких доступно дуже мало допоміжної інформації: ви не знаєте, на що схоже оптимальне рішення, невідомо, яким способом необхідно шукати це рішення, наявної евристичної інформації явно недостатньо, а послідовний перебір не підходить, тому що простір пошуку дуже великий. Але якщо є потенційне рішення, то його можна перевірити і встановити, наскільки воно добре. Тобто можна дізнатися якість рішення, коли воно доступно.
Припустимо, наприклад, що необхідно знайти оптимальний набір дій для робота, який грає у футбол. Є симулятор дій робота і можна протестувати будь-який набір дій і присвоїти цьому набору оцінку (хороший набір дій можна побачити). Також є загальне визначення для набору дій, тобто можна уявити, що він із себе представляє. Однак немає жодної ідеї про те, яким повинен бути оптимальний набір, і про те, як до нього прийти.
Найпростіший варіант розв'язання задачі в подібній ситуації — випадковий пошук (Random Search): будемо просто генерувати випадкові набори поводжень, поки не закінчиться відведений на пошук час, і повернемо найкращий знайдений набір. Але перш ніж впасти у відчай і взятися за випадковий пошук, розглянемо альтернативу, таку як локальний пошук (Hill-Climbing). Почнемо працювати з випадковим набором дій. Потім застосуємо до нього невелику випадкову зміну і протестуємо отриману нову версію. Якщо вона виявиться краще, то попередню версію відкинемо. В іншому випадку, відкидається нова версія. Після зробимо ще одне невелику випадкову зміну поточної версії набору (тобто тієї, яка не була відкинута). Якщо нова версія краща, то відкидаємо поточну, інакше не приймаємо нову. Повторюємо процес наскільки це можливо.
Локальний пошук — це простий метаевристичний алгоритм. Він використовує евристичне припущення про властивість простору пошуку, яке зазвичай актуально для багатьох завдань: схожі рішення часто поводять себе подібним чином (і часто мають близьку якість), тому невеликі модифікації рішень зазвичай тягнуть невеликі і зрозумілі зміни в їхній якості, що дозволяє підніматися на «вершину гори якості» для отримання хороших рішень. Таке евристичне припущення є однією з ключових особливостей метаевристичних методів. І дійсно, практично всі метаевристики об'єднують локальний пошук з випадковим.
Алгоритми
Локальний пошук
Випадковий пошук
Best ← деяке початкове значення 'repeat S ← випадковий потенційний розв'язок if (якість)S >(якість)Best then Best ← S end if until в Best записано ідеальний розв'язок, або скінчився час пошуку return Best
Алгоритм імітації відпалу
Пошук із забороною
Алгоритм пошуку з забороною (Табу пошук), розроблений Фредом Гловером (Fred Glover), використовує оригінальний підхід до дослідження простору пошуку: у ньому зберігається інформація про недавні згенеровані потенційні рішення (так званий «список заборон», табу список), повернення до яких на подальших етапах неможливий поки не скінчиться тимчасове обмеження. Таким чином, якщо алгоритм «підіймається» по пагорбу, то у нього немає іншого вибору, як перейти на іншу сторону, оскільки залишитися на вершині не можна.
Найпростішим способом реалізації пошуку з забороною є підтримка списку заборон L з максимальною довжиною I, включає вже знайдені потенційні рішення. Кожен раз, коли створюється нове рішення, воно записується в список заборон. Якщо список стає занадто великим, то з нього виключається саме «старе» рішення, яке перестає бути забороненим. Пошук із забороною зазвичай нагадує варіант найшвидшого підйому з заміщенням.
Ітеративний локальний пошук
Ітеративний локальний пошук (ІЛП) (Iterated Local Search (ILS)) намагається працювати більш інтелектуально: він виконує стохастичний локальний пошук в просторі локальних оптимумів. Тобто ІЛП знаходить локальний оптимум, а потім здійснює пошук іншого локального оптимуму в околиці і можливо робить його поточним, потім шукає новий локальний оптимум в околиці нового і т. д. Тут використовується евристика, що завжди можна знайти більш «хороший» локальний оптимум поруч з поточним, і подібні переміщення мають бути ефективнішими, ніж абсолютно випадкові перезапуски.
Джерела інформації
- Sean Luke, 2009, Essentials of Metaheuristics, First Edition
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Metaevri stika dosit nevdala nazva dlya opisu velikogo pidrozdilu v dijsnosti osnovnogo v stohastichnij optimizaciyi stochastic optimization Stohastichna optimizaciya ye velikim klasom algoritmiv i metodiv yaki tak chi inakshe vikoristovuyut vipadkovist dlya poshuku optimalnogo abo dosyazhnogo optimalnogo rishennya skladnih zavdan Metaevristiki najzagalnishi algoritmi z cogo klasu i zastosovuyutsya dlya virishennya shirokogo spektra zavdan Tip zadach metaevristikiYaki zavdannya rozglyadayutsya U spravi Yakobellis proti shtatu Ogajo Jacobellis v Ohio 1964 r sprava pro film necenzurnogo zmistu suddya Verhovnogo sudu SShA Potter Styuart napisav svij znamenitij visliv Sogodni ya ne budu bilshe namagatisya dati viznachennya tih materialiv yaki ya rozumiyu i yaki potribno vtisnuti v korotke viznachennya Cilkom mozhlivo sho v mene nikoli ne vijde zrobiti ce virazno Ale ya vpiznayu yih koli pobachu i film sho rozglyadayetsya v spravi do nih ne vidnositsya Metaevristiki zastosovuyutsya do zavdan tipu ya vpiznayu yih koli pobachu Ce algoritmi yaki vikoristovuyutsya dlya poshuku rishennya na zavdannya v yakih dostupno duzhe malo dopomizhnoyi informaciyi vi ne znayete na sho shozhe optimalne rishennya nevidomo yakim sposobom neobhidno shukati ce rishennya nayavnoyi evristichnoyi informaciyi yavno nedostatno a poslidovnij perebir ne pidhodit tomu sho prostir poshuku duzhe velikij Ale yaksho ye potencijne rishennya to jogo mozhna pereviriti i vstanoviti naskilki vono dobre Tobto mozhna diznatisya yakist rishennya koli vono dostupno Pripustimo napriklad sho neobhidno znajti optimalnij nabir dij dlya robota yakij graye u futbol Ye simulyator dij robota i mozhna protestuvati bud yakij nabir dij i prisvoyiti comu naboru ocinku horoshij nabir dij mozhna pobachiti Takozh ye zagalne viznachennya dlya naboru dij tobto mozhna uyaviti sho vin iz sebe predstavlyaye Odnak nemaye zhodnoyi ideyi pro te yakim povinen buti optimalnij nabir i pro te yak do nogo prijti Najprostishij variant rozv yazannya zadachi v podibnij situaciyi vipadkovij poshuk Random Search budemo prosto generuvati vipadkovi nabori povodzhen poki ne zakinchitsya vidvedenij na poshuk chas i povernemo najkrashij znajdenij nabir Ale persh nizh vpasti u vidchaj i vzyatisya za vipadkovij poshuk rozglyanemo alternativu taku yak lokalnij poshuk Hill Climbing Pochnemo pracyuvati z vipadkovim naborom dij Potim zastosuyemo do nogo neveliku vipadkovu zminu i protestuyemo otrimanu novu versiyu Yaksho vona viyavitsya krashe to poperednyu versiyu vidkinemo V inshomu vipadku vidkidayetsya nova versiya Pislya zrobimo she odne neveliku vipadkovu zminu potochnoyi versiyi naboru tobto tiyeyi yaka ne bula vidkinuta Yaksho nova versiya krasha to vidkidayemo potochnu inakshe ne prijmayemo novu Povtoryuyemo proces naskilki ce mozhlivo Lokalnij poshuk ce prostij metaevristichnij algoritm Vin vikoristovuye evristichne pripushennya pro vlastivist prostoru poshuku yake zazvichaj aktualno dlya bagatoh zavdan shozhi rishennya chasto povodyat sebe podibnim chinom i chasto mayut blizku yakist tomu neveliki modifikaciyi rishen zazvichaj tyagnut neveliki i zrozumili zmini v yihnij yakosti sho dozvolyaye pidnimatisya na vershinu gori yakosti dlya otrimannya horoshih rishen Take evristichne pripushennya ye odniyeyu z klyuchovih osoblivostej metaevristichnih metodiv I dijsno praktichno vsi metaevristiki ob yednuyut lokalnij poshuk z vipadkovim AlgoritmiLokalnij poshuk Dokladnishe Lokalnij poshuk optimizaciya Vipadkovij poshuk Best deyake pochatkove znachennya repeat S vipadkovij potencijnij rozv yazok if yakist S gt yakist Best then Best S end if until v Best zapisano idealnij rozv yazok abo skinchivsya chas poshuku return Best Algoritm imitaciyi vidpalu Dokladnishe Algoritm imitaciyi vidpalu Poshuk iz zaboronoyu Algoritm poshuku z zaboronoyu Tabu poshuk rozroblenij Fredom Gloverom Fred Glover vikoristovuye originalnij pidhid do doslidzhennya prostoru poshuku u nomu zberigayetsya informaciya pro nedavni zgenerovani potencijni rishennya tak zvanij spisok zaboron tabu spisok povernennya do yakih na podalshih etapah nemozhlivij poki ne skinchitsya timchasove obmezhennya Takim chinom yaksho algoritm pidijmayetsya po pagorbu to u nogo nemaye inshogo viboru yak perejti na inshu storonu oskilki zalishitisya na vershini ne mozhna Najprostishim sposobom realizaciyi poshuku z zaboronoyu ye pidtrimka spisku zaboron L z maksimalnoyu dovzhinoyu I vklyuchaye vzhe znajdeni potencijni rishennya Kozhen raz koli stvoryuyetsya nove rishennya vono zapisuyetsya v spisok zaboron Yaksho spisok staye zanadto velikim to z nogo viklyuchayetsya same stare rishennya yake perestaye buti zaboronenim Poshuk iz zaboronoyu zazvichaj nagaduye variant najshvidshogo pidjomu z zamishennyam Iterativnij lokalnij poshuk Iterativnij lokalnij poshuk ILP Iterated Local Search ILS namagayetsya pracyuvati bilsh intelektualno vin vikonuye stohastichnij lokalnij poshuk v prostori lokalnih optimumiv Tobto ILP znahodit lokalnij optimum a potim zdijsnyuye poshuk inshogo lokalnogo optimumu v okolici i mozhlivo robit jogo potochnim potim shukaye novij lokalnij optimum v okolici novogo i t d Tut vikoristovuyetsya evristika sho zavzhdi mozhna znajti bilsh horoshij lokalnij optimum poruch z potochnim i podibni peremishennya mayut buti efektivnishimi nizh absolyutno vipadkovi perezapuski Dzherela informaciyiSean Luke 2009 Essentials of Metaheuristics First Edition