Մետրոպոլիս-Հաստինգսի ալգորիթմ

Վիքիպեդիայից՝ ազատ հանրագիտարանից
The Proposal distribution Q proposes the next point that the random walk might move to.

Մետրոպոլիս-Հաստինգսի ալգորիթմը, սեմպլիրացման ալգորիթմ է, որն հիմնականում օգտագործվում է բաշխման բարդ ֆունկցիաների համար։ Այն մասամբ նման է շեղումներով ընտրության ալգորիթմին, սակայն այստեղ բաշխման օժանդակ ֆունկցիան փոխվում է ժամանակի ընթացքում է։ Առաջին անգամ ալգորիթմը լույս է տեսել Նիկոլաս Մետրոպոլիսի կողմից 1953 թվին, և հետո ընդհանրացվել Հաստինգսի կողմից 1970 թվին. սեմպլիրացում ըստ Գիբբսի հանդիսանում է Մետրոպոլիս-Հաստինգսի ալգորիթմի մասնավոր դեպք, և ավելի հայտնի է իր պարզությամբ և արագությամբ, չնայած առավել հազվադեպ է կիրառվում։

Մետրոպոլիս-Գաստինգի ալգորիթմը թույլ է տալիս սեմպլիրացնել ցանկացած բաշխման ֆունկցիա։ Այն հիմնված է Մարկովի շղթայի ստեղծման վրա, այսինքն ալգորիթմի յուրաքանչյուր քայլին նոր ընտրված -ի իմաստը կախված է նախորդ -ից.Ալգորիթմն օգտագործում է բաշխման օժանդակ ֆունկցիան, որը կախված է -ից, և որի համար գեներացիան выборку հեշտ է (օրինակ, նորմալ բաշխումը). Այս ֆունկցիայի համար ամեն քայլին գեներացվում է -ի պատահական իմաստ։ Հետո հավանականությամբ՝

( կամ 1 հավանականությամբ եթե ), ընտրված իմաստը ընդունվում է որպես նոր՝ , հակառակ դեպքում մնում է նույնը՝ .

Օրինակ, եթե ընդունենք բաշխման նորմալ ֆունկցիան որպես օժանդակ, ապա

.

Այսպիսի ֆունկցիան տալիս է նոր նշանակություն՝կախված նախկին քայլում ստացված նշանակությունից։ Ի սկզբանե Մետրոպոլիսի ալգորիթմը պահանջում էր, որ օժանդակ ֆունկցիան լիներ սիմետրիկ՝ , սակայն Գաստինգսի ընդհանրացումը այս սահմանափակումը վերացնում է։

Ալգորիթմ[խմբագրել | խմբագրել կոդը]

Ենթադրենք մենք արդեն ընտրել ենք նշանակությունը։ Մյուս նշանակության ընտրության համար սկզբում ֆունկցիայի համար պետք է ստանանք պատահական նշանակությունը։ Հետո գտնենք ածանցյալը, որտեղ

հանդիսանում է միջանկյալ և նախկին նշանակությունների միջև հավանականությունների հարաբերակցություն, իսկ

սա հարաբերություն է հավանականությունների միջև ` անցնելով -ից կամ հակառակը. Եթե սիմետրիկ է, ապա երկրորդ բազմապատկիչը հավասար է 1. Պատահական նշանակությունը նոր քայլում ընտրվում է կանոններին համապտասխան`

Ալգորիթմը ծագում է –ի պատահական նշանակությունից, և սկզբում մի քանի քայլ գործում է միայնակ, որպեսզի մոռացվի սկզբնական նշանակությունը։

Ամենալավը ալգորիթմը գործում է այն ժամանակ, երբ օժանդակ ֆունկցիայի ձևը մոտ է նպատակայինին ֆունկցիայի ձևին. ։ Սակայն այս չճշտվածությանը հասնելը մասամբ անհնար է։ Խնդրի լուծման համար օժանդակ ֆունկցիան հարմարեցնում են ալգորիթմի աշխատանքի նախապատրաստական փուլի ընթացքում։ Օրինակ, նորմալ բաշխման համար պարամետրը ընտրում են այնպես, որ ընդունած պատահական նշանակությունների բաժինը (այսինքն նրանց, որոնց համար )-ը մոտ լինի 60%. Եթե -ը չափազանց փոքր է, ապա նշանակությունները կստացվեն շատ մոտ և ընդունվածների բաժինը կլինի բարձր։ Եթե չափազանց մեծ է, ապա մեծ հավանականությամբ նոր նշանակությունները փոքր հավանականության զոնայից դուրս կմնան, որից ընդունված նշանակությունների բաժինը փոքր կլինի։