Amaliyot ishi №1 Mavzu

Nazorat savollari:

1. 
   Hill-climbing qidiruv algoritmini tushuntirib bering?
   
2. 
   The simulated annealing search algorithm tuzilishini ko’rsating?.
   

Amaliyot ishi № 10

Mavzu: Qidiruv “Beam search” algoritmi.

Ishdan maqsad: Qidiruv “Beam search” algoritmi, maxalliy qidiruv, gaenetika algoritmlarini o`rganish.

Nazariy qism:

Mahalliy qidiruv

Xotirada faqat bir tugunni tutilishi xotira cheklanishi muammosiga haddan tashqari reaktsiya bo'lishi mumkin. Mahalliy nur qidiruv algorithm10 к davlatlar emas, balki faqat bir-izlar. Bu к tasodifiy davlatlar bilan boshlanadi. Har bir qadamda, barcha к davlatlarning barcha xalifa hosil qilinadi. Har qanday bir maqsad bo'lsa, algoritm to'xtadi. Aks holda, u to'liq ro'yxati va qayta dan к eng yaxshi o'rinbosarlar tanlaydi.

Birinchi qarashda, к davlatlar bilan mahalliy nur qidiruv parallel o'rniga ketma-ketlikda к tasodifiy qayta ishlaydigan boshqa narsa bo'lishi mumkin. Aslida, ikki algoritmlarni juda farq qiladi. tasodifiy-qayta ishga tushirishni izlab, har bir qidiruv jarayoni mustaqil ishlaydi.

Lavlama benzetimi qidiruv algoritmi, stokastik tepalik climb- bir versiyasini tushunishga; Ba'zi pastga harakat ruxsat etiladi qaerda Pastga harakat bo`lsa kamroq vaqt o'tib tez erta yumshatish jadvaliga va keyin qabul qilinadi. Jadvali kiritish vaqt Junction sifatida T qiymatini beradi.

Boshqalar mahalliy nur izlab, foydali ma'lumotlar к parallel qidiruv iplar orasida uzatiladi. Misol uchun, bir davlat bir necha yaxshi xalifa va boshqa K hosil bo'lsa - barcha yomon xalifa ishlab 1 davlatlar, keyin ta'sir ilk davlat boshqalarga deydi, "o't yashil bo'lib Bu yoqqa kel!" algoritm tez samarasiz qidiruvlarni tark va eng o'sish amalga oshirilmoqda.

Uning eng oddiy shaklida, mahalliy nur qidiruv к orasida xilma-xilligi yetishmasligi aziyat chekishi mumkin. Davlatlar-ular tez tepalikka toqqa chiqishga qimmat versiyasi oz ko'proq qidiruv qilish, davlat kosmik kichik viloyati joyga jamlanganda bo'lishi mumkin. stokastik Hill, toqqa o'xshash bir variant deb nomlangan stokastik nur qidiruv, bu muammoni bartaraf qilish uchun yordam beradi. Buning o'rniga nomzod merosxo'rlari pulidan eng yaxshi K tanlash, stokastik nur qidiruv qiymati ortib borayotgan vorisini tanlashda ehtimoli bilan, tasodifiy da к o'rinbosarlar tanlaydi. Stochastic nur qidiruv "xalifa" a "davlat" (organizm) ning (avlodlari) uning "qiymati" (fitness)ga ko'ra, keyingi avlod to'ldirish tufayli tabiiy tanlanish jarayoniga o'xshab ketadi.

Genetika algoritmlarni

A genetik algoritm (yoki GA) vorisi arduvaz ikki ota-davlatlar, birlashtirib o'rniga bitta davlat o'zgartirib hosil bo'lgan stokastik nur qidiruv varianti hisoblanadi. Tabiiy tanlanish uchun o'xshashlik endi biz jinsiy o'rniga jinssiz ko'payish bilan muomala qilinadi, stokastik nur izlab bir xil bo'ladi.

GAZ VA к tasodifiy davlatlar majmui bilan boshlanadi. Har bir davlat, yoki shaxsiy, chekli alphabetmost ustidan bilan mag'lubiyatga sifatida taqdim etiladi

Rasm 4.15 genetik algoritm. (A) boshlang'ich aholi (b), (v) da kuyikish uchun juft-juft, natijada fitness funktsiyasi tomonidan tartiblashtiriladi. Ular (e) mutatsion tortiladi (d) zurriyotlarini ham ishlab chiqarish.

Rasm 4.16 8-malika, shakl 4.15 (c) va ko'rsatkich 4.15 (d) birinchi bola birinchi ikki ota-ona mos Shtatlari. soyabon columas krossover qadam yo'qoladi va himoyalanadi.

Tez-tez bir os torli va Masalan, 1 S., 8-malika Davlat 8 kvadratlar bir ustun 8 qirolichalar, har bir mavqeini belgilash kerak va shuning uchun 8 x log2 8 = 24 bit talab qiladi. 1 8. (Biz keyinchalik ikki kodlanmalarga boshqacha muomala ko'ramiz.) bir qatorda, davlat 8 kod dekabrdagi har bir vakili sifatida bo'lishi mumkin-rasm 4.15 (a) 8- ifodalovchi to'rt 8-raqamli satrlari aholiga ko'rsatilgan malika davlatlar.

Davlatlar keyingi avlod ishlab chiqarish, shakl 4.15 da ko'rsatilgan (b) - (e). (B), har bir davlat baholash funktsiyasi tomonidan yoki fitness funktsiyasi (GA terminologiya) tomonidan baholanmoqda. A fitness vazifasi biz bir yechim uchun 28 a ahamiyatga ega Queens nonattacking juft sonini, foydalanish 8-malika muammo uchun, yaxshiroq davlatlar uchun yuqori qadriyatlar qaytib, shuning uchun kerak. to'rt davlatlar qiymatlari 24, 23, 20, va genetik algoritm, manba uchun tanlangan olinish ehtimoli fitness hisobida to'g'ri proportsional bo'ladi va foiz xom ballar yonida ko'rsatilgan.