Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
| Цю статтю треба для відповідності Вікіпедії. (березень 2012) |
Реактивний пошук — це методологія для вирішення важких оптимізаційних проблем як для ізольованої так і для неперервної області, що базується на інтеграції машинного самонавчання та оптимізації у неавтономному режимі.
Машинне самовдосконалення засноване на методах пошукової евристики (від грец. «знаходити» — знання, надбане по мірі накопичення людиною досвіду у певній діяльності, тобто при вирішенні практичних завдань певного класу. Більш строго — це стратегія вибіркового пошуку у просторі станів. Тобто теоретично не обґрунтоване правило, що дозволяє скоротити кількість переборів у просторі рішень. Евристичні методи на відміну від алгоритмічних не потребують вичерпної вихідної інформації, але не завжди гарантують успіху. Евристики використовуються у експертних системах та в евристичному програмуванні) для того аби дозволити алгоритму самостійно налаштувати усі операційні параметри під час пошуку. Таким чином, підбір параметрів, який зазвичай демонструє машина в автономному режимі, стає невід'ємною частиною пошукового алгоритму і гарантує гнучкість методу без втручання людини. «Навчальний» елемент реалізується як схема певних реакцій заснована на історії попередніх пошуків завдяки чому підвищується результативність та ефективність методу.
Проблеми оптимізації
Реактивний пошук як і всі методи локального пошуку, застосовується для вирішення проблеми знаходження оптимальної конфігурації системи. Ця конфігурація зазвичай складається з окремих або неперервних параметрів, і число цих параметрів буде змінюється в залежності від кожної окремої конфігурації. В більшості випадків, оптимізаційна задача перетворюється на знаходження глобального мінімуму функції, аргументами якої є параметри оптимізації, представлені як вільні змінні в просторі цієї функції. Розглянемо наприклад функцію, графік якої представлений вище. Знаходження глобального мінімуму функції на цьому графіку не здається складною задачею, оскільки мі можемо бачити і аналізувати «загальний» вид графічного представлення цієї функції. Але комп'ютерна програма може обчислювати та аналізувати лише одну точку простору в один момент часу. «Глобальне» бачення, від самого початку, не доступне нікому, але воно розвивається і вдосконалюється під час виконання достатньої кількості обчислень. (наприклад, маленька дитина, що тільки вчиться рахувати, не в змозі одразу назвати кількість намальованих по кутках аркушу паперу крапочок. Дитина має порахувати кожну окремо: один, два, три, чотири. Тоді як дорослій людині буде досить лише на мить поглянути на аркуш і вона одразу скаже правильну відповідь. Згадайте лише колоду гральних карт.)
Методи локального пошуку
Для того аби знайти мінімум, машина використовує метод «швидкого спуску», при цьому методі генерується довільна конфігурація яка рухається в напрямку до менших значень функції (див. зображення справа, на якому зображена та сама функція, що й раніше, але вже не вид згори, а вид збоку), пошук зупиняється коли не залишається шляхів до вдосконалення. Конфігурації що розглядаються представлені червоною крапкою що рухається вздовж ліній. Цей метод дослідження гарантовано зупиниться в локальному мінімумі функції (де не залишиться жодних варіантів для подальших досліджень). На жаль не можна заздалегідь сказати коли саме пошук завершиться. Цей метод схожий на наступну реальну дію: ви кладете м'ячика на похилу площину і чекаєте доки він скотиться вниз. Але функції які реально потребують досліджень в наш час, на жаль набагато складніші, аніж та, що ми розглядали раніше. Вони можуть мати кілька локальних мінімумів, а послідовне «закидання м'ячика» може зайняти багато часу перш ніж рішення буде знайдене. Витонченіший приклад: пошук заснований на забороні. Більш «реальні» проблеми, тим не менш мають певні «структури», такі, що локальні мінімуми зібрані у певній області довкола глобального мінімуму, таким чином, метод який продовжує пошук після того як знайдено локальний мінімум, може дати кращі результати. Для вирішення таких задач можливе використання сукупності методів, що базуються на забороні («табу»-пошук). Це означає, не зупиняти пошук, навіть коли не спостерігається ніяких покращень (тобто дозволити нашому м'ячику рухатись вгору), це потрібно для того аби здолати бар'єри (гірки) між мінімумами, аби попередити скочування системою по вже пройденому шляху. Це означає, що коли перший крок зроблено наступний крок не може залишитися незакінченим. Таким чином, основною метою «табу»-пошуку є уникання повторного проходження однієї і тієї ж самої ділянки пошуку.
Реактивний пошук Але кількість ітерацій застосованих у пошуку не може нескінченною, інакше система вичерпає всі свої ресурси а рішення так і не буде знайдене. Необхідно правильно встановити критерій зупинки процесу пошуку. І обрати цей параметр правильно це і є одним із найкритичніших параметрів даного методу. Через різні, невірно вибрані умови продовження, можуть виникнути різні непередбачувані помилки. Звичайний спосіб знаходження вірного параметра — «запуск-до-помилки» в кілька повторюваних етапів: дослідник повторно запускає пошук на машині, встановлюючи різні параметри зупинки роботи, таким чином відкидаючи невірні, і обираючи самий багатообіцяючий.
Техніка Реактивного пошуку автоматизує усі параметри пошуку спираючись на впорядкування історії минулих пошуків (тобто свого роду використання попереднього досвіду, навчання). Наприклад, якщо дослідження певної конфігурації повторюється занадто часто, це, можливо, означає необхідність прискорити момент припинення операції на цьому проміжку пошуку. Схема відгуку яка змінює параметри пошуку в залежності від результатів називається реакцією і є ядром техніки реактивного пошуку. Іншою перевагою системи заснованої на запам'ятовуванні історії є можливість розпізнавання «безнадійних» ситуацій, в яких система не знаходить покращення протягом тривалого часу; може бути застосований механізм втечі, який перезавантажить систему з довільної точки за певних обставин.
«Табу-пошук» — це тільки один із прикладів технік що мають перевагу над звичайними механізмами реагування. Всі алгоритми що критично залежать від певних параметрів, таких як алгоритм модельного «загартування» (покращення моделі), генетичні алгоритми, та інші можуть мати переваги над цією евристикою.
Використання історії (попереднього досвіду)
Реактивний пошук використовує широкий спектр евристичних алгоритмів задля дискретної оптимізації, в якій локальний пошук доповнюється і підтримується схемами відгуку (реакції), саме вони використовують історію минулих пошуків, аби підвищити якість та дієвість методу. У реактивному пошуку історія минулих пошуків використовується задля:
- Налаштування параметрів, заснованих на схемі відгуку. Цей алгоритм підтримує максимальну гнучкість для вирішення багатьох можливих проблем, але налаштування цілком автоматизоване і виконується доти доки виконується алгоритм, також налаштування враховує попередню історію.
- Автоматизований баланс розширення меж та посилення на проміжку. Дилема «Дослідження проти дослідження» зустрічається в багатьох евристиках: Чи краще посилити пошук у перспективних регіонах, чи розсунути межі пошуку на незадіяні території. Можна здобути автоматизований евристичний баланс за допомогою механізмів відгуку, наприклад, почати із зосередження ресурсів на проміжку, а потім, коли це виправдано, поступово розширювати окіл пошуку.
Головні стадії реактивного пошуку
Перейдемо до визначення трьох головних стадій реактивного пошуку, заснованого на схемах заборонах (табу пошук):
- Період самоналаштовуючої заборони. У реактивному пошуку заборона «Т» визначається через схеми відгуку (реакції) під час пошуку. На початку операції «Т» прирівнюється до одиниці (), значення «Т» зростає лише тоді коли є підстава для того щоб розширити поле пошуку, та зменшується коли такі підстави зникають. Зрозуміти що настав час розширювати поле пошуку дуже просто, — машина починає занадто часто сигналізувати про повторне проходження тієї самої ділянки пошуку.
На прикладі графіка, зображеного вище ми можемо бачити поведінку параметра «Т» під час певного пошуку. Тут параметр «Т» збільшується експоненціально коли зустрічаються повторні проходження ділянок, і поступово зменшується коли повторні проходження зникають
- Механізм виходу (втечі)
Основного «табу»-механізму заснованого на заборонах, недостатньо для того щоб уникнути довгих повторюваних циклів. До того ж, навіть коли вдалося уникнути «лімітних циклів» (нескінченні циклічні повторення на одному і тому ж проміжку), реагуючий механізм необов'язково гарантує що траєкторія пошуку не замкнеться на певній ділянці пошукового простору. Хаотичне «замикання» траєкторії пошуку на обмеженій ділянці пошукового простору можливе завжди (задля аналогії можна привести динамічні системи із хаотичним притяганням, де траєкторія обмежена у певному проміжку області пошуку, хоча лімітний цикл відсутній). Тому механізм виходу (втечі із циклу) необхідний з двох причин: перша — підвищити працездатність алгоритму, друга — розширити коло пошуку. Фаза виходу запускається багатьма факторами та повторюється занадто часто. Проста схема «втечі» складається з набору довільних кроків що виконуються на поточному проміжку (інколи ці кроки обираються із врахуванням того аби швидше покинути поточну область пошуку).
- Швидкі алгоритми із використанням історії пошуку.
Зберігання та доступ до попередніх подій забезпечується за допомогою добре відомої техніки хешування, або техніки базисного дерева, що зберігається під час роботи центрального процесору. Таким чином можна не хвилюватися за вичерпування ресурсів під час виконання задач, що потребують складно-обчислюваних кількостей операцій для того аби швидко оцінити вартість функціонування.
Використані матеріали
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cyu stattyu treba vikifikuvati dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit dodavannyam dorechnih vnutrishnih posilan abo vdoskonalennyam rozmitki statti berezen 2012 Reaktivnij poshuk ce metodologiya dlya virishennya vazhkih optimizacijnih problem yak dlya izolovanoyi tak i dlya neperervnoyi oblasti sho bazuyetsya na integraciyi mashinnogo samonavchannya ta optimizaciyi u neavtonomnomu rezhimi Mashinne samovdoskonalennya zasnovane na metodah poshukovoyi evristiki vid grec znahoditi znannya nadbane po miri nakopichennya lyudinoyu dosvidu u pevnij diyalnosti tobto pri virishenni praktichnih zavdan pevnogo klasu Bilsh strogo ce strategiya vibirkovogo poshuku u prostori staniv Tobto teoretichno ne obgruntovane pravilo sho dozvolyaye skorotiti kilkist pereboriv u prostori rishen Evristichni metodi na vidminu vid algoritmichnih ne potrebuyut vicherpnoyi vihidnoyi informaciyi ale ne zavzhdi garantuyut uspihu Evristiki vikoristovuyutsya u ekspertnih sistemah ta v evristichnomu programuvanni dlya togo abi dozvoliti algoritmu samostijno nalashtuvati usi operacijni parametri pid chas poshuku Takim chinom pidbir parametriv yakij zazvichaj demonstruye mashina v avtonomnomu rezhimi staye nevid yemnoyu chastinoyu poshukovogo algoritmu i garantuye gnuchkist metodu bez vtruchannya lyudini Navchalnij element realizuyetsya yak shema pevnih reakcij zasnovana na istoriyi poperednih poshukiv zavdyaki chomu pidvishuyetsya rezultativnist ta efektivnist metodu Problemi optimizaciyiReaktivnij poshuk yak i vsi metodi lokalnogo poshuku zastosovuyetsya dlya virishennya problemi znahodzhennya optimalnoyi konfiguraciyi sistemi Cya konfiguraciya zazvichaj skladayetsya z okremih abo neperervnih parametriv i chislo cih parametriv bude zminyuyetsya v zalezhnosti vid kozhnoyi okremoyi konfiguraciyi V bilshosti vipadkiv optimizacijna zadacha peretvoryuyetsya na znahodzhennya globalnogo minimumu funkciyi argumentami yakoyi ye parametri optimizaciyi predstavleni yak vilni zminni v prostori ciyeyi funkciyi Rozglyanemo napriklad funkciyu grafik yakoyi predstavlenij vishe Znahodzhennya globalnogo minimumu funkciyi na comu grafiku ne zdayetsya skladnoyu zadacheyu oskilki mi mozhemo bachiti i analizuvati zagalnij vid grafichnogo predstavlennya ciyeyi funkciyi Ale komp yuterna programa mozhe obchislyuvati ta analizuvati lishe odnu tochku prostoru v odin moment chasu Globalne bachennya vid samogo pochatku ne dostupne nikomu ale vono rozvivayetsya i vdoskonalyuyetsya pid chas vikonannya dostatnoyi kilkosti obchislen napriklad malenka ditina sho tilki vchitsya rahuvati ne v zmozi odrazu nazvati kilkist namalovanih po kutkah arkushu paperu krapochok Ditina maye porahuvati kozhnu okremo odin dva tri chotiri Todi yak doroslij lyudini bude dosit lishe na mit poglyanuti na arkush i vona odrazu skazhe pravilnu vidpovid Zgadajte lishe kolodu gralnih kart Metodi lokalnogo poshukuDlya togo abi znajti minimum mashina vikoristovuye metod shvidkogo spusku pri comu metodi generuyetsya dovilna konfiguraciya yaka ruhayetsya v napryamku do menshih znachen funkciyi div zobrazhennya sprava na yakomu zobrazhena ta sama funkciya sho j ranishe ale vzhe ne vid zgori a vid zboku poshuk zupinyayetsya koli ne zalishayetsya shlyahiv do vdoskonalennya Konfiguraciyi sho rozglyadayutsya predstavleni chervonoyu krapkoyu sho ruhayetsya vzdovzh linij Cej metod doslidzhennya garantovano zupinitsya v lokalnomu minimumi funkciyi de ne zalishitsya zhodnih variantiv dlya podalshih doslidzhen Na zhal ne mozhna zazdalegid skazati koli same poshuk zavershitsya Cej metod shozhij na nastupnu realnu diyu vi kladete m yachika na pohilu ploshinu i chekayete doki vin skotitsya vniz Ale funkciyi yaki realno potrebuyut doslidzhen v nash chas na zhal nabagato skladnishi anizh ta sho mi rozglyadali ranishe Voni mozhut mati kilka lokalnih minimumiv a poslidovne zakidannya m yachika mozhe zajnyati bagato chasu persh nizh rishennya bude znajdene Vitonchenishij priklad poshuk zasnovanij na zaboroni Bilsh realni problemi tim ne mensh mayut pevni strukturi taki sho lokalni minimumi zibrani u pevnij oblasti dovkola globalnogo minimumu takim chinom metod yakij prodovzhuye poshuk pislya togo yak znajdeno lokalnij minimum mozhe dati krashi rezultati Dlya virishennya takih zadach mozhlive vikoristannya sukupnosti metodiv sho bazuyutsya na zaboroni tabu poshuk Ce oznachaye ne zupinyati poshuk navit koli ne sposterigayetsya niyakih pokrashen tobto dozvoliti nashomu m yachiku ruhatis vgoru ce potribno dlya togo abi zdolati bar yeri girki mizh minimumami abi poperediti skochuvannya sistemoyu po vzhe projdenomu shlyahu Ce oznachaye sho koli pershij krok zrobleno nastupnij krok ne mozhe zalishitisya nezakinchenim Takim chinom osnovnoyu metoyu tabu poshuku ye unikannya povtornogo prohodzhennya odniyeyi i tiyeyi zh samoyi dilyanki poshuku Reaktivnij poshuk Ale kilkist iteracij zastosovanih u poshuku ne mozhe neskinchennoyu inakshe sistema vicherpaye vsi svoyi resursi a rishennya tak i ne bude znajdene Neobhidno pravilno vstanoviti kriterij zupinki procesu poshuku I obrati cej parametr pravilno ce i ye odnim iz najkritichnishih parametriv danogo metodu Cherez rizni nevirno vibrani umovi prodovzhennya mozhut viniknuti rizni neperedbachuvani pomilki Zvichajnij sposib znahodzhennya virnogo parametra zapusk do pomilki v kilka povtoryuvanih etapiv doslidnik povtorno zapuskaye poshuk na mashini vstanovlyuyuchi rizni parametri zupinki roboti takim chinom vidkidayuchi nevirni i obirayuchi samij bagatoobicyayuchij Tehnika Reaktivnogo poshuku avtomatizuye usi parametri poshuku spirayuchis na vporyadkuvannya istoriyi minulih poshukiv tobto svogo rodu vikoristannya poperednogo dosvidu navchannya Napriklad yaksho doslidzhennya pevnoyi konfiguraciyi povtoryuyetsya zanadto chasto ce mozhlivo oznachaye neobhidnist priskoriti moment pripinennya operaciyi na comu promizhku poshuku Shema vidguku yaka zminyuye parametri poshuku v zalezhnosti vid rezultativ nazivayetsya reakciyeyu i ye yadrom tehniki reaktivnogo poshuku Inshoyu perevagoyu sistemi zasnovanoyi na zapam yatovuvanni istoriyi ye mozhlivist rozpiznavannya beznadijnih situacij v yakih sistema ne znahodit pokrashennya protyagom trivalogo chasu mozhe buti zastosovanij mehanizm vtechi yakij perezavantazhit sistemu z dovilnoyi tochki za pevnih obstavin Tabu poshuk ce tilki odin iz prikladiv tehnik sho mayut perevagu nad zvichajnimi mehanizmami reaguvannya Vsi algoritmi sho kritichno zalezhat vid pevnih parametriv takih yak algoritm modelnogo zagartuvannya pokrashennya modeli genetichni algoritmi ta inshi mozhut mati perevagi nad ciyeyu evristikoyu Vikoristannya istoriyi poperednogo dosvidu Reaktivnij poshuk vikoristovuye shirokij spektr evristichnih algoritmiv zadlya diskretnoyi optimizaciyi v yakij lokalnij poshuk dopovnyuyetsya i pidtrimuyetsya shemami vidguku reakciyi same voni vikoristovuyut istoriyu minulih poshukiv abi pidvishiti yakist ta diyevist metodu U reaktivnomu poshuku istoriya minulih poshukiv vikoristovuyetsya zadlya Nalashtuvannya parametriv zasnovanih na shemi vidguku Cej algoritm pidtrimuye maksimalnu gnuchkist dlya virishennya bagatoh mozhlivih problem ale nalashtuvannya cilkom avtomatizovane i vikonuyetsya doti doki vikonuyetsya algoritm takozh nalashtuvannya vrahovuye poperednyu istoriyu Avtomatizovanij balans rozshirennya mezh ta posilennya na promizhku Dilema Doslidzhennya proti doslidzhennya zustrichayetsya v bagatoh evristikah Chi krashe posiliti poshuk u perspektivnih regionah chi rozsunuti mezhi poshuku na nezadiyani teritoriyi Mozhna zdobuti avtomatizovanij evristichnij balans za dopomogoyu mehanizmiv vidguku napriklad pochati iz zoseredzhennya resursiv na promizhku a potim koli ce vipravdano postupovo rozshiryuvati okil poshuku Golovni stadiyi reaktivnogo poshukuPerejdemo do viznachennya troh golovnih stadij reaktivnogo poshuku zasnovanogo na shemah zaboronah tabu poshuk Period samonalashtovuyuchoyi zaboroni U reaktivnomu poshuku zaborona T viznachayetsya cherez shemi vidguku reakciyi pid chas poshuku Na pochatku operaciyi T pririvnyuyetsya do odinici znachennya T zrostaye lishe todi koli ye pidstava dlya togo shob rozshiriti pole poshuku ta zmenshuyetsya koli taki pidstavi znikayut Zrozumiti sho nastav chas rozshiryuvati pole poshuku duzhe prosto mashina pochinaye zanadto chasto signalizuvati pro povtorne prohodzhennya tiyeyi samoyi dilyanki poshuku Na prikladi grafika zobrazhenogo vishe mi mozhemo bachiti povedinku parametra T pid chas pevnogo poshuku Tut parametr T zbilshuyetsya eksponencialno koli zustrichayutsya povtorni prohodzhennya dilyanok i postupovo zmenshuyetsya koli povtorni prohodzhennya znikayut Mehanizm vihodu vtechi Osnovnogo tabu mehanizmu zasnovanogo na zaboronah nedostatno dlya togo shob uniknuti dovgih povtoryuvanih cikliv Do togo zh navit koli vdalosya uniknuti limitnih cikliv neskinchenni ciklichni povtorennya na odnomu i tomu zh promizhku reaguyuchij mehanizm neobov yazkovo garantuye sho trayektoriya poshuku ne zamknetsya na pevnij dilyanci poshukovogo prostoru Haotichne zamikannya trayektoriyi poshuku na obmezhenij dilyanci poshukovogo prostoru mozhlive zavzhdi zadlya analogiyi mozhna privesti dinamichni sistemi iz haotichnim prityagannyam de trayektoriya obmezhena u pevnomu promizhku oblasti poshuku hocha limitnij cikl vidsutnij Tomu mehanizm vihodu vtechi iz ciklu neobhidnij z dvoh prichin persha pidvishiti pracezdatnist algoritmu druga rozshiriti kolo poshuku Faza vihodu zapuskayetsya bagatma faktorami ta povtoryuyetsya zanadto chasto Prosta shema vtechi skladayetsya z naboru dovilnih krokiv sho vikonuyutsya na potochnomu promizhku inkoli ci kroki obirayutsya iz vrahuvannyam togo abi shvidshe pokinuti potochnu oblast poshuku Shvidki algoritmi iz vikoristannyam istoriyi poshuku Zberigannya ta dostup do poperednih podij zabezpechuyetsya za dopomogoyu dobre vidomoyi tehniki heshuvannya abo tehniki bazisnogo dereva sho zberigayetsya pid chas roboti centralnogo procesoru Takim chinom mozhna ne hvilyuvatisya za vicherpuvannya resursiv pid chas vikonannya zadach sho potrebuyut skladno obchislyuvanih kilkostej operacij dlya togo abi shvidko ociniti vartist funkcionuvannya Vikoristani materiali