Жергілікті іздеу (шектеулі қанағаттану) - Local search (constraint satisfaction)

Жылы шектеулі қанағаттану, жергілікті іздеу а шешімін табудың толық емес әдісі болып табылады проблема. Ол барлық шектеулер орындалғанға дейін айнымалылардың тағайындауын итеративті түрде жақсартуға негізделген. Атап айтқанда, жергілікті іздеу алгоритмдері әр қадамда тағайындаудағы айнымалының мәнін өзгертеді. Жаңа тапсырма тағайындау кеңістігіндегі алдыңғысына жақын, демек, оның атауы жергілікті іздеу.

Барлық жергілікті іздеу алгоритмдері тағайындау сапасын бағалайтын функцияны қолданады, мысалы, тапсырма бұзған шектеулер саны. Бұл сома деп аталады құны тапсырманың Жергілікті іздеудің мақсаты минималды шығындарды тағайындау болып табылады, бұл бар болған жағдайда шешім болып табылады.

А нүктесі шешім емес, бірақ жергілікті қозғалу құнын төмендетпейді. Алайда шешім В нүктесінде бар.

Жергілікті іздеу алгоритмдерінің екі класы бар. Біріншісі ашкөз немесе кездейсоқ емес алгоритмдер. Бұл алгоритмдер әрдайым оның құнын төмендетуге (немесе, кем дегенде, көбейтпеуге) тырысып, ағымдағы тапсырманы өзгерту арқылы жүреді. Бұл алгоритмдердің негізгі мәселесі - мүмкін болуы үстіртs, бұл жергілікті қозғалу құнын төмендетпейтін тағайындаулар кеңістігінің аймақтары. Бұл мәселені шешу үшін жергілікті іздеу алгоритмінің екінші класы ойлап табылды. Олар кездейсоқ қозғалыстар жасау арқылы осы үстірттерден қашып, рандомизацияланған жергілікті іздеу алгоритмдері деп аталады.

Ашкөз алгоритмдер

Төбеге шығу

Жергілікті іздеудің ең негізгі формасы шешімнің құнын барынша төмендететін өзгерісті таңдауға негізделген. Бұл әдіс деп аталады төбеге шығу, келесідей жүреді: біріншіден, кездейсоқ тағайындау таңдалады; содан кейін алынған тапсырманың сапасын барынша жақсарту үшін мән өзгертіледі. Егер берілген өзгерістер санынан кейін шешім табылмаса, жаңа кездейсоқ тағайындау таңдалады. Төбеге көтерілу алгоритмдері тек тапсырманың сапасын өзгертпейтін өзгертулер енгізу арқылы үстірттен құтыла алады. Нәтижесінде, олар тағайындау сапасы жергілікті максимумға ие болатын үстіртте тұрып қалуы мүмкін.

GSAT (ашкөздік сат) қанықтылықты іздеудің алғашқы жергілікті алгоритмі болды және бұл тауға шығу түрі.

Шектеуді өлшеу немесе сындыру әдісі

Жергілікті минимумнан құтылу әдісі - бұл шығындардың өлшемі ретінде бұзылған шектеулердің өлшенген сомасын қолдану және жақсарту мүмкіндігі болмаған кезде кейбір салмақтарды өзгерту. Дәлірек айтсақ, егер ешқандай өзгеріс тапсырманың құнын төмендетпесе, алгоритм ағымдағы тағайындаумен бұзылған шектеулердің салмағын арттырады.

Осылайша, шешім құнын өзгертпейтін кез-келген қадам оны төмендетеді. Сонымен қатар, көптеген қозғалыстар үшін шектеулердің салмағы өсіп келеді. Сондықтан, шектеулерді қанағаттандырмайтын бірқатар қозғалыстар кезінде, осы шектеулерді қанағаттандыратын тапсырмаларға көшу құны өсе береді.

Табу іздеу

Төбеге шығудың өзіндік құнын төмендетпейтін қадамдармен жетіспеушілігі, ол бірдей шығындар бойынша тапсырмаларды айналып өтуі мүмкін. Табу іздеу[1][2][3] деп аталатын «тыйым салынған» тапсырмалар тізімін жүргізу арқылы бұл мәселені шешеді кестелер тізімі. Атап айтқанда, табу тізімінде тек ең соңғы өзгерістер бар. Дәлірек айтқанда, ол айнымалы жақында мәнге тағайындалатындай етіп соңғы айнымалы-мәндік жұпты қамтиды.

Бұл тізім тапсырма өзгерген сайын жаңарып отырады. Егер айнымалы мәнге тағайындалса, онда айнымалы-мән жұбы тізімге қосылады, ал ең көне жұп одан шығарылады. Осылайша, тізім тек айнымалының соңғы тағайындауларынан тұрады. Егер айнымалы мәндер жұбы табу тізімінде болса, онда айнымалыны мәнге қою арқылы ағымдағы тағайындауға тыйым салынады. Алгоритм тыйым салынған әрекеттердің ішінен ең жақсы қадамды таңдай алады. Осылайша, егер бұл циклдегі қозғалыс саны табу тізімінің ұзындығынан көп болмаса, ол бір шешімнің үстінен айналып өте алмайды.

Кездейсоқ жүру

A кездейсоқ серуендеу алгоритм кейде ашкөз алгоритм сияқты қозғалады, бірақ кейде кездейсоқ қозғалады. Бұл параметрге байланысты , бұл 0 мен 1 аралығындағы нақты сан, ықтималдықпен алгоритм тапсырманың құнын максималды төмендетуге тырысып, ашкөз алгоритм сияқты жүреді. Ықтималдықпен дегенмен, шешім басқа жолмен өзгертіледі, бұл кездейсоқтықтың белгілі бір дәрежесін қамтиды.

WalkSAT

WalkSAT-тің кездейсоқ қозғалысы кездейсоқ бұзылған шектеудің кездейсоқ шамасының мәнін өзгертеді. Үшін ұсыныстық қанағаттанушылық туралы конъюнктивті қалыпты форма формулалар, бұл осы алгоритмнің бастапқы параметрлері болып табылады, әрбір осындай қозғалыс айнымалының мәнін шыннан жалғанға немесе керісінше өзгертеді және бұзылған шектеудің қанағаттанушылығын тудырады. Кездейсоқ жүрудің барлық стратегияларына келетін болсақ, кездейсоқ жылжу тек берілген ықтималдылықпен жүзеге асырылады, ал шығындарды максималды төмендететін қозғалыс басқаша жағдайда жасалады.

Имитациялық күйдіру

Имитациялық күйдіру әдісі құнын максималды төмендететін кездейсоқ жылжу ықтималдығын өзгертуге негізделген. Атап айтқанда, атау алгоритмді орындау кезінде кездейсоқ жүрістер жасау ықтималдығын төмендету стратегиясынан туындайды, осылайша іздеу кеңістігін іс жүзінде «қатырады».

Атап айтқанда, егер құнын жақсарту Қозғалыс теріс (қозғалыс өзіндік құнды арттырады), бұл ықтималдықпен орындалады , қайда нақты сан. Бұл мүмкіндікті орындау ықтималдығы өседі , бұл параметр. деп аталады температура. Имитациялық күйдіру бұл температураны уақыт өте келе төмендетеді, осылайша басында көп кездейсоқ жылжулар болады, ал уақыт өткеннен кейін аз болады.

Цикл кесіндісіндегі жергілікті іздеу

Жергілікті іздеу, әдетте, барлық айнымалыларға жұмыс істейді, оларға толық тапсырма береді. Сонымен қатар, жергілікті іздеуді басқа айнымалылар үшін басқа механизмді қолдана отырып, айнымалылардың ішкі жиынтығында да жүргізуге болады. Ұсынылған алгоритм жұмыс істейді цикл жиынтығы, бұл айнымалы жиынтығы, егер проблемадан шығарылса, оны ациклді етеді.

Кетсеттің айнымалыларын кез-келген тағайындау үшін қалған есепте a болады орман бастапқы график ретінде. Нәтижесінде оны тиімді шешуге болады. Жергілікті іздеуге басшылық ету үшін проблеманың орман бөлігіндегі қанықтылық алгоритмінің орнына бұзылуы мүмкін шектеулердің минималды санын анықтайтын алгоритм қолданылады.

Бұл минималды сан әр айнымалы тағайындаудың құнын анықтау арқылы табылады. Бұл шығын - айнымалы берілген мәнді қабылдаған кезде, өзгермеліге негізделген ішкі ағаштағы айнымалылардың тағайындауымен бұзылған шектеулердің минималды саны. Бұл құнын келесідей есептеуге болады. Егер тапсырманың құнын білдіреді және балалары , келесі формула орындалады. Осы формулада, бұл тағайындауға байланысты 0 немесе 1 арасындағы шектеуді бұзады және .

Коттестегі айнымалылардың құны нөлге тең, ал бұл айнымалылар тек олардың берілген мәнін қабылдауға рұқсат етілген деп есептеледі. Осы жорамалдармен жоғарыда келтірілген формула барлық айнымалы бағалаудың құнын орманның жапырақтарынан бастап тамырларына дейін төменнен жоғарыға қарай итеративті түрде есептеуге мүмкіндік береді.

Айнымалы бағалау құнын шешім құнын есептеу үшін жергілікті іздеу арқылы пайдалануға болады. Орман тамырларының мәндерінің құны, шын мәнінде, берілген мәндер үшін ормандағы шектеулердің минималды саны болып табылады. Сондықтан бұл шығындар жиынтықтың ауыспалы мәндеріне тағайындау құнын бағалауға және кескінді айнымалыларға ұқсас тағайындаулардың құнын бағалауға пайдаланылуы мүмкін.

Сыртқы сілтемелер

Әдебиеттер тізімі

  1. ^ Гловер, Фред (1986 ж. Қаңтар). «Бүтін программалаудың болашақ жолдары және жасанды интеллектке сілтемелер». Компьютерлер және операцияларды зерттеу. 13 (5): 533–549. дои:10.1016/0305-0548(86)90048-1.
  2. ^ Glover, Fred (тамыз 1989). «Tabu іздеуі - I бөлім». ORSA Journal on Computing. 1 (3): 190–206. дои:10.1287 / ijoc.1.3.190. ISSN  0899-1499.
  3. ^ Glover, Fred (ақпан 1990). «Tabu Search - II бөлім». Есептеу бойынша ORSA журналы. 2 (1): 4–32. дои:10.1287 / ijoc.2.1.4. ISSN  0899-1499.