Жергілікті іздеу - Guided Local Search

Жергілікті іздеу Бұл метауризм іздеу әдісі. Мета-эвристикалық әдіс - бұл жоғарыда орналасқан әдіс жергілікті іздеу алгоритмі оның мінез-құлқын өзгерту.

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

Шолу

Шешімнің ерекшеліктері

GLS қолдану үшін берілген проблема үшін шешім мүмкіндіктері анықталуы керек. Шешім ерекшеліктері әртүрлі сипаттамалары бар шешімдерді ажырату үшін анықталған, сондықтан жергілікті оптима айналасындағы ұқсастық аймақтары танылып, оларды болдырмауға болады. Шешім мүмкіндіктерін таңдау проблеманың түріне, сонымен қатар белгілі бір дәрежеде жергілікті іздеу алгоритміне байланысты. Әр функция үшін ${ displaystyle f_ {i}}$ шығындар функциясы ${ displaystyle c_ {i}}$ анықталды.

Әрбір ерекшелік пенальтиямен де байланысты ${ displaystyle p_ {i}}$ (бастапқыда 0-ге орнатылған), функцияның жергілікті минимумда пайда болу санын жазу.

Ерекшеліктер мен шығындар көбінесе тікелей мақсаттық функциядан туындайды. Мысалы, саяхатшылардың саяхаты кезінде «тур X қаласынан Y қаласына тікелей барады ма» ерекшелігі ретінде анықталуы мүмкін. X пен Y арасындағы қашықтықты шығындар деп анықтауға болады. SAT және салмақты MAX-SAT проблемаларында «С пункті ағымдағы тапсырмаларға сәйкес келе ме» ерекшеліктері болуы мүмкін.

Іске асыру деңгейінде біз әр функция үшін анықтаймыз ${ displaystyle i}$ индикатор функциясы ${ displaystyle I_ {i}}$ функцияның қазіргі шешімде бар-жоғын көрсететін. ${ displaystyle I_ {i}}$ ерітінді 1 болғанда ${ displaystyle x}$ мүлікті көрсетеді ${ displaystyle i}$ , Әйтпесе 0.

Айыппұлды таңдау

GLS әр мүмкіндікті жазалаудың утилитасын есептейді. Жергілікті іздеу алгоритмі а қайтарған кезде жергілікті минимум x, GLS осы шешімде бар барлық мүмкіндіктерге (функциялардың өсімпұлына дейін) максималды утилитасы бар жазалайды, ${ displaystyle operatorname {util} (x, i)}$ , төменде анықталғандай.

{ displaystyle operatorname {util} (x, i) = I_ {i} (x) { frac {c_ {i} (x)} {1 + p_ {i}}}.}

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

Толықтырылған шығын функциясы арқылы іздеу

Жергілікті іздеу алгоритмін жергілікті минимумнан шығаруға мүмкіндік беру үшін GLS (төменде анықталған) шығындар функциясын қолданады. Мұндағы мақсат жергілікті минималды мүмкіндіктер жоқ іздеу кеңістігіне қарағанда қымбатырақ ету болып табылады.

{ displaystyle g (x) = f (x) + lambda a sum _ {1 leq i leq m} I_ {i} (x) p_ {i}}

Шешімдерді іздеудің қарқындылығын өзгерту үшін λ параметрін қолдануға болады. Λ үшін үлкен мән іздеуді әр түрлі етеді, мұнда үстірттер мен бассейндер өрескел ізделеді; төмен мән шешім іздеуді күшейтеді, мұнда іздеу ландшафтыындағы үстірттер мен бассейндер егжей-тегжейлі ізделінеді. Коэффициент ${ displaystyle a}$ мақсат функциясының жазалау бөлігін мақсат функциясының өзгеруіне қатысты тепе-теңдікке келтіру үшін қолданылады және проблемалық сипатқа ие. Орнатуға арналған қарапайым эвристикалық ${ displaystyle a}$ Мақсатты функцияның орташа өзгеруін бірінші жергілікті минимумға дейін жазып, содан кейін орнату ғана ${ displaystyle a}$ осы мәнге проблема данасындағы GLS мүмкіндіктерінің санына бөлінеді.

Жергілікті іздеудің кеңейтімдері

Миллз (2002) кездейсоқ қозғалыстар мен айыппұлға негізделген схемалар үшін арнайы жасалған ұмтылыс критерийін қолданатын кеңейтілген басқарылатын жергілікті іздеуді (EGLS) сипаттады. Нәтижесінде алынған алгоритм GLS тұрақтылығын бірқатар параметрлер параметрлері бойынша жақсартты, әсіресе жағдайда квадраттық тағайындау есебі. GLS алгоритмінің минималды қақтығыстарға негізделген альпинизмді қолдайтын жалпы нұсқасы (Минтон және басқалар 1992 ж.) Және шектеулерді қанағаттандыру және оңтайландыру үшін ішінара GENET-ке негізделген. Компьютерлік шектеулерді бағдарламалау жобасы.

Альшедди (2011) кеңейтілген жергілікті іздеу көп мақсатты оңтайландыру, және оны жоспарлау кезінде персоналдың мүмкіндіктерін кеңейтуде қолдануды көрсетті^{[дәйексөз қажет ]}.

Осыған байланысты жұмыс

GLS GENET-те жасалған, оны Чан Ванг, Эдвард Цанг және Эндрю Дэвенпорт әзірлеген.

The үзіліс әдісі GENET-ке өте ұқсас. Ол арналған шектеулі қанағаттану.

Табу іздеу нақты әдістерге негізделген іздеу әдістерінің класы. GLS-ді ерекше жағдай ретінде қарастыруға болады Табу іздеу.

GLS үстінде отыру арқылы генетикалық алгоритм, Tung-leng Lau Генетикалық бағдарламалаудың (GGA) алгоритмін енгізді. Ол жалпы тағайындау мәселесіне (кесте құруда), процессорлардың конфигурациясына (электронды дизайнда) және радиобайланыс жиілігін тағайындау мәселелеріне (рефераттағы әскери қосымшада) сәтті қолданылды.

Чой және басқалар. Лагранждық іздеу ретінде GENET-ті шығарды.

Библиография

Альшедди, А., Куәландыруды жоспарлау: Жетекші жергілікті іздеуді қолдана отырып, көп мақсатты оңтайландыру тәсілі, PhD диссертациясы, Ессекс университеті, Информатика және электронды инженерия мектебі [1]
Choi, KMF, Lee, JHM. & Stuckey, PJ, GENET-тің лагранжды қайта құру, жасанды интеллект, 2000, 123 (1-2), 1-39
Davenport A., Tsang E.P.K., Kangmin Zhu & C J Wang, GENET: шектеулі қанағаттанушылық мәселелерін қайталанатын жақсарту арқылы шешуге арналған коннектистік сәулет, Proc., AAAI, 1994, 325-330 [2]
Лау, Т.Л. & Tsang, E.P.K., Процессорды конфигурациялау мәселесін мутацияға негізделген генетикалық алгоритммен шешу, Халықаралық жасанды интеллект құралдары журналы (IJAIT), World Scientific, Vol.6, №4, желтоқсан 1997, 567-585
Лау, Т.Л. & Tsang, E.P.K., басшылыққа алынған генетикалық алгоритм және оны радиобайланыс жиілігін тағайындау мәселелеріне қолдану, шектеулер, 6-том, №4, 2001, 373-398 [3]
Лау, Т.Л. & Tsang, E.P.K., Жетекші генетикалық алгоритм және оны жалпы тағайындау мәселелеріне қолдану, IEEE Жасанды Интеллект Құралдары бойынша 10 Халықаралық Конференциясы (ICTAI'98), Тайвань, 1998 ж. Қараша
Mills, P. & Tsang, E.P.K., SAT және салмақты MAX-SAT есептерін шешуге арналған жергілікті іздеу, Автоматтандырылған пікірлер журналы, Қанағаттанушылық проблемалары туралы арнайы шығарылым, Kluwer, 24-том, 2000, 205-223 [4]
Миллс, П. & Цанг, Э.П.К. & Форд, Дж., Квадраттық тағайындау мәселесі бойынша кеңейтілген жергілікті іздеуді қолдану, Амалдарды зерттеу анналы, Kluwer Academic Publishers, Vol.118, 2003, 121-135 [5]
Минтон, С., Джонстон, М., Филипс, А.Б. & Laird, P., Қақтығыстарды минимизациялау: шектеулерді қанағаттандыру және жоспарлау мәселелерін шешуге арналған эвристикалық жөндеу әдісі, Жасанды интеллект (Шектеулі негіздегі ақыл-ойдың арнайы томы), 58-том, 1992 ж. №1-3, 161-205
Цанг, Е.П.К. & Voudouris, C., Жылдам жергілікті іздеу және жергілікті іздеу және оларды British Telecom жұмыс күшін жоспарлау мәселесіне қолдану, Operations Research Letters, Elsevier Science Publishers, Амстердам, 20-том, №3, наурыз 1997, 119-127 [6]
Voudouris, C, Комбинаторлық оңтайландыру мәселелерін жергілікті іздеу, кандидаттық диссертация, Ессекс университетінің Информатика кафедрасы, Колчестер, Ұлыбритания, шілде, 1997 [7]
Voudouris, C., Жергілікті іздеу - функцияны оңтайландырудағы мысал, BT Technology журналы, 16 том, №3, 1998 ж. Шілде, 46-50 [8]
Voudouris, C. & Tsang, E.P.K., Жергілікті іздеу және оны саяхатшылар мәселесіне қолдану, Еуропалық жедел зерттеу журналы, Anbar Publishing, Vol.113, 2-шығарылым, 1999 ж., 469-499 [9]
Voudouris, C. & Tsang, E.P.K., басшылыққа алынған жергілікті іздеу элитаны дискреттік оңтайландыруда біріктіреді, дискретті математика және теориялық информатика саласындағы DIMACS сериясы 57 том, 2001, 29-39 [10]
Voudouris, C. & Tsang, E.P.K., жергілікті іздеу, F. Glover (ред.), Metaheuristics анықтамалығы, Kluwer, 2003, 185-218 [11]
Вудурис, С., Цанг, Э.П.К. & Alsheddy, A., Жергілікті іздеу, 11-тарау, M. Gendroau & J-Y Потвин (ред.), Metaheuristics анықтамалығы, Springer, 2010, 321-361

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

Жергілікті іздеудің басты беті