Kompyuterinjiniringi” fakulteti 961-18 guruh 5-bosqich talabasi Boltayev Boltaboyning
Yüklə 39,01 Kb.
|
- Bu səhifədəki naviqasiya:
- Mavzu: Qidiruv. “Hill climbing” texnikasi REJA: Raqamli tahlilda Hill climbing Hill climbing algoritmi
|
Muhammad al-Xorazmiynomidagi Toshkent Axborot texnologiyalari Universiteti Urganch filiali “Kompyuterinjiniringi” fakulteti 961-18 guruh 5-bosqich talabasi Boltayev Boltaboyning ‘’Suniy intellekt’’ fanidan MUSTAQIL ISHI Mavzu: Qidiruv. “Hill climbing” texnikasi REJA: Raqamli tahlilda Hill climbing Hill climbing algoritmi Hill Climbing algoritmi turlari Hill climbing algoritmidagi muammolar Raqamli tahlilda Hill climbing - bu mahalliy qidiruv oilasiga tegishli bo'lgan matematik optimallashtirish usuli. Bu muammoni o'zboshimchalik bilan hal qilishdan boshlanuvchi, so'ngra yechimga bosqichma-bosqich o'zgartirish kiritish orqali yaxshiroq yechim topishga harakat qiladigan iterativ algoritm. Agar o'zgartirish yaxshiroq yechimni keltirsa, yangi yechimga yana bir bosqichma-bosqich o'zgartirish kiritiladi va boshqa yaxshilanishlar topilmaguncha davom etadi. Masalan, Hill climbing sayohatchi sotuvchi muammosiga qo'llash mumkin. Barcha shaharlarga tashrif buyuradigan boshlang'ich echimni topish oson, lekin optimal echim bilan solishtirganda juda yomon bo'lishi mumkin. Algoritm shunday yechim bilan boshlanadi va unga kichik yaxshilanishlar kiritadi, masalan, ikkita shaharga tashrif buyurish tartibini almashtirish. Oxir-oqibat, ancha qisqaroq marshrutga erishish mumkin. Hill climbing konveks muammolari uchun maqbul echimlarni topadi - boshqa muammolar uchun u faqat mahalliy optimalarni (qo'shni konfiguratsiyalar tomonidan takomillashtirilmaydigan echimlar) topadi, bu barcha mumkin bo'lgan echimlar ichidan eng yaxshi yechim (global optimal) bo'lishi shart emas. qidiruv maydoni). Qavariq masalalarni toqqa chiqish yoʻli bilan hal qiluvchi algoritmlarga misollar qatoriga chiziqli dasturlash va ikkilik qidiruv uchun simpleks algoritmi kiradi: 253 Lokal optimaga yopishib qolmaslik uchun qayta ishga tushirish (masalan, takroriy mahalliy qidiruv) yoki yana koʻp usullardan foydalanish mumkin. iteratsiyaga asoslangan murakkab sxemalar (masalan, takrorlangan mahalliy qidiruv) yoki xotiraga (masalan, reaktiv qidiruvni optimallashtirish va tabu qidiruvi) yoki xotirasiz stokastik modifikatsiyalarga (masalan, simulyatsiya qilingan yumshatish). Algoritmning nisbatan soddaligi uni optimallashtirish algoritmlari orasida mashhur birinchi tanlovga aylantiradi. U sun'iy intellektda, boshlang'ich tugundan maqsad holatiga erishish uchun keng qo'llaniladi. Tegishli algoritmlarda keyingi tugunlar va boshlang'ich tugunlar uchun turli xil tanlovlar qo'llaniladi. Simulyatsiya qilingan tavlanish yoki tabu qidiruvi kabi ilg'or algoritmlar yaxshi natijalar berishi mumkin bo'lsa-da, ba'zi hollarda toqqa chiqish ham ishlaydi. Qidiruvni amalga oshirish uchun vaqt miqdori cheklangan bo'lsa, masalan, real vaqt tizimlarida, toqqa chiqish ko'pincha boshqa algoritmlarga qaraganda yaxshiroq natija berishi mumkin, chunki oz sonli o'sishlar odatda yaxshi yechimga (optimal yechim) yaqinlashsa. yoki yaqin taxmin). Boshqa tomondan, qabariqni saralash Hill climbing algoritmi sifatida ko'rib chiqilishi mumkin (har bir qo'shni element almashinuvi tartibsiz elementlar juftlari sonini kamaytiradi), ammo bu yondashuv hatto oddiy N uchun ham samarali emas, chunki zarur almashinuvlar soni kvadratik ravishda oshadi. Hill climbing har doimgi algoritmdir: u tugashidan oldin istalgan vaqtda to'xtatilgan bo'lsa ham, to'g'ri yechimni qaytarishi mumkin. Hill climbing algoritmi - bu tog'ning cho'qqisini yoki muammoning eng yaxshi echimini topish uchun balandlik/qiymatni oshirish yo'nalishida doimiy ravishda harakatlanadigan mahalliy qidiruv algoritmi. Hech bir qo'shni yuqori qiymatga ega bo'lmagan cho'qqi qiymatiga etganida u tugaydi. Hill climbing algoritmi - bu matematik muammolarni optimallashtirish uchun ishlatiladigan usul. Hill climbing algoritmining keng muhokama qilingan misollaridan biri bu Sayohatchi-sotuvchi muammosi bo'lib, unda biz sotuvchi bosib o'tgan masofani minimallashtirishimiz kerak. Bu, shuningdek, ochko'z mahalliy qidiruv deb ataladi, chunki u faqat yaqin qo'shni davlatga qaraydi va undan tashqarida emas. Hill climbing algoritmining tugunida holat va qiymat bo'lgan ikkita komponent mavjud. Hill climbing, asosan, yaxshi evristik mavjud bo'lganda qo'llaniladi. Ushbu algoritmda biz qidiruv daraxti yoki grafigini saqlash va boshqarishimiz shart emas, chunki u faqat bitta joriy holatni saqlaydi. Hill climbing uchun davlat-kosmik diagrammasi: Shtat-kosmik landshaft - bu Hill climbing algoritmining grafik tasviri bo'lib, u algoritmning turli holatlari va Maqsad funktsiyasi/narx o'rtasidagi grafikni ko'rsatadi. Y o'qida biz maqsad funksiyasi yoki xarajat funktsiyasi bo'lishi mumkin bo'lgan funktsiyani va x o'qida holat-fazoni oldik. Agar Y o'qidagi funktsiya xarajat bo'lsa, qidiruv maqsadi global minimal va mahalliy minimumni topishdir. Agar Y o'qining funktsiyasi Ob'ektiv funktsiya bo'lsa, qidiruvning maqsadi global maksimal va mahalliy maksimalni topishdir. Hill Climbing algoritmi turlari: Simple hill Climbing: Steepest-Ascent hill-climbing: Stochastic hill Climbing: Simple Hill Climbing - bu Hill Climbingalgoritmini amalga oshirishning eng oddiy usuli. U bir vaqtning o'zida faqat qo'shni tugun holatini baholaydi va joriy xarajatlarni optimallashtiradigan birinchisini tanlaydi va uni joriy holat sifatida o'rnatadi. U faqat bitta voris holatini tekshiradi va agar u hozirgi holatdan yaxshiroq deb topsa, boshqa holatda o'ting. Ushbu algoritm quyidagi xususiyatlarga ega: Kamroq vaqt talab qiladi Kamroq optimal yechim va yechim kafolatlanmaydi Simple Hill Climbing algoritmi: 1-qadam: Dastlabki holatni baholang, agar u maqsad holati bo'lsa, muvaffaqiyatni qaytaring va to'xtating. 2-qadam: Yechim topilmaguncha yoki qo'llash uchun yangi operator qolmaguncha tsikl. 3-qadam: Operatorni joriy holatga tanlang va qo'llang. 4-qadam: Yangi holatni tekshiring: Agar bu maqsad holati bo'lsa, muvaffaqiyatga qayting va chiqing. Aks holda, agar u joriy holatdan yaxshiroq bo'lsa, yangi holatni joriy holat sifatida belgilang. Aks holda, joriy holatdan yaxshiroq bo'lmasa, 2-bosqichga qayting. 5-qadam: Chiqish. Steepest-Ascent hill climbing: Steepest-Ascent hill climbing algoritmi Simple hill Climbing algoritmining o'zgarishidir. Ushbu algoritm joriy holatning barcha qo'shni tugunlarini tekshiradi va maqsad holatiga eng yaqin bo'lgan bitta qo'shni tugunni tanlaydi. Ushbu algoritm bir nechta qo'shnilarni qidirganda ko'proq vaqt sarflaydi Steepest-Ascent hill climbing algoritmi: 1-qadam: Dastlabki holatni baholang, agar u maqsad holati bo'lsa, muvaffaqiyatni qaytaring va to'xtating, aks holda joriy holatni boshlang'ich holat sifatida belgilang. 2-qadam: Yechim topilmaguncha yoki joriy holat o'zgarmaguncha aylantiring. SUCC shunday davlat bo'lsinki, hozirgi davlatning har qanday vorisi undan yaxshiroq bo'ladi. Joriy holatga tegishli har bir operator uchun: Yangi operatorni qo'llang va yangi holat yarating. Yangi holatni baholang. Agar bu maqsad holati bo'lsa, uni qaytaring va chiqing, aks holda uni SUCC bilan solishtiring. Agar u SUCC dan yaxshiroq bo'lsa, yangi holatni SUCC sifatida o'rnating. Agar SUCC joriy holatdan yaxshiroq bo'lsa, joriy holatni SUCC ga o'rnating. 5-qadam: Chiqish. 3. Stochastic hill climbing: Stochastic hill climbing, harakat qilishdan oldin barcha qo'shnilarini tekshirmaydi. Aksincha, ushbu qidiruv algoritmi tasodifiy bir qo'shni tugunni tanlaydi va uni joriy holat sifatida tanlash yoki boshqa holatni tekshirish haqida qaror qabul qiladi. Hill climbing algoritmidagi muammolar: Mahalliy maksimal: Mahalliy maksimal - bu landshaftdagi cho'qqi holati bo'lib, u qo'shni shtatlarning har biridan yaxshiroq, lekin mahalliy maksimaldan yuqori bo'lgan boshqa holat ham mavjud. Simulyatsiya qilingan tavlanish: Hech qachon pastroq qiymat tomon harakat qilmaydigan hill-climbing algoritmi to'liq bo'lmasligi kafolatlanadi, chunki u mahalliy maksimalga yopishib qolishi mumkin. Va agar algoritm vorisni ko'chirish orqali tasodifiy yurishni qo'llasa, u tugallanishi mumkin, ammo samarali emas. Simulyatsiyalangan tavlanish - bu ham samaradorlik, ham to'liqlikni ta'minlaydigan algoritm. Mexanik atamada tavlanish - bu metall yoki shishani yuqori haroratgacha qotib, so'ngra asta-sekin sovutish jarayoni, shuning uchun bu metallning past energiyali kristal holatiga erishishiga imkon beradi. Xuddi shu jarayon simulyatsiya qilingan yumshatishda qo'llaniladi, bunda algoritm eng yaxshi harakatni tanlash o'rniga tasodifiy harakatni tanlaydi. Agar tasodifiy harakat holatni yaxshilasa, u xuddi shu yo'ldan boradi. Aks holda, algoritm ehtimolligi 1 dan kichik bo'lgan yo'ldan boradi yoki u pastga siljiydi va boshqa yo'lni tanlaydi. Sun'iy intellektda Hill climbing Birinchidan, sun'iy intellektda Hill climbing haqida gapiraylik. Bu muammolarni matematik jihatdan optimallashtirish uchun evristik. Haqiqiy funktsiyani maksimallashtirish yoki minimallashtirish uchun kirishdan qiymatlarni tanlashimiz kerak. Agar yechim global optimal maksimal bo'lmasa, yaxshi. Evristik qidiruv usullari - Hill climbing Keling, Python nutqini aniqlashni muhokama qilaylik Hill climbingning bunday misollaridan biri keng muhokama qilinadigan Sayohatchi sotuvchi muammosi bo'ladi - bu erda biz u sayohat qilgan masofani minimallashtirishimiz kerak. a. AIda Hill climbingning xususiyatlari
Bu yaratish va sinab ko'rish algoritmining bir variantidir Bu ochko'zlik yondashuvidan foydalanadi Bu shuni anglatadiki, u kutilgan yechimni topmaguncha mumkin bo'lgan echimlarni ishlab chiqarishni davom ettiradi va faqat xarajatlar funktsiyasini optimallashtiradigan yo'nalishda harakat qiladi. b. AIda Hill climbing turlari Evristik qidiruv - sun'iy intellektda Hill climbing turlari
Keling, SimpleHill climbing algoritmini ko'rib chiqaylik. Dastlabki holatni baholang - agar maqsad holati bo'lsa, to'xtating va muvaffaqiyatga qayting. Aks holda, dastlabki holatni joriy qiling.
b. Yangi holatni baholang: Agar maqsad aniq bo'lsa, to'xtating va muvaffaqiyatga qayting.
Mahalliy maksimal - Barcha qo'shni shtatlarda hozirgidan yomonroq qiymatlar mavjud. Ochko'z yondashuv biz bundan ham yomonroq holatga o'tmasligimizni anglatadi. Bu, garchi yaxshiroq yechim bo'lgan bo'lsa ham, jarayonni tugatadi. Vaqtinchalik yechim sifatida biz orqaga qaytishdan foydalanamiz. Plato- Unga barcha qo'shnilar bir xil qiymatga ega. Bu yo'nalishni tanlashni imkonsiz qiladi. Bunga yo'l qo'ymaslik uchun biz tasodifiy katta sakrash qilamiz. Ridge - tizmada barcha mumkin bo'lgan yo'nalishlarda harakat pastga qarab amalga oshiriladi. Bu uni cho'qqiga o'xshatadi va jarayonni tugatadi. Bunga yo'l qo'ymaslik uchun sinovdan oldin ikki yoki undan ortiq qoidalardan foydalanishimiz mumkin. Python Assert bayonotlari haqida bilasizmi? Cheklovlarni qondirish muammolari (CSP) Cheklov cheklash yoki cheklashdan boshqa narsa emas. AI bilan ishlash , muammolarni hal qilish uchun biz ba'zi cheklovlarni qondirishimiz kerak bo'lishi mumkin. Keling, muammoni shu tarzda hal qilishga harakat qilaylik, shunday emasmi? Keling, sehrli kvadrat haqida gapiraylik. Bu kvadrat to'rda joylashgan raqamlar ketma-ketligi - odatda butun sonlar. Har bir satrdagi, har bir ustundagi va har bir diagonaldagi raqamlar qo'shilib, biz Sehrli doimiy deb ataymiz. Keling, buni Python bilan amalga oshiraylik. def magic_square (matritsa):
>>>sehrli kvadrat ([[1,2,3],[4,5,6],[7,8,9]]) Noto'g'ri Bu sehrli kvadrat emas. Qatorlar/ustunlar/diagonallardagi raqamlar bir xil qiymatga qo'shilmaydi. Keling, boshqa ro'yxatlar ro'yxatini ko'rib chiqaylik. AI neyron tarmoqlarini ko'rib chiqing >>>sehrli kvadrat ([[2,7,6],[9,5,1],[4,3,8]])
Evristik qidiruv - sehr Qiymatlar barcha yo'nalishlarda doimiy 15 ga teng bo'lganligi sababli, bu sehrli kvadratdir! Simulyatsiya qilingan tavlanish evristik qidiruvi Metallurgiyada biz metallarni sekin sovutganda, ularni past energiya holatiga tushirish uchun ularga namunaviy kuch beradi. Biz buni yumshatish deb ataymiz. Yuqori haroratlar ko'p tasodifiy harakatni kuzatsa-da, past haroratlar kam tasodifiylikni sezadi. Sun'iy intellektda biz simulyatsiya qilingan tavlanish deb ataladigan narsani ishlab chiqarish uchun bundan ibrat olamiz. Bu optimallashtirish usuli bo'lib, biz yuqori haroratda tasodifiy qidiruvni boshlaymiz va haroratni sekin pasaytiramiz. Oxir-oqibat, harorat nolga yaqinlashganda, qidiruv sof ochko'zlikka aylanadi. Har bir bosqichda bu jarayonlar tasodifiy o'zgaruvchi va qiymatni tanlaydi. U topshiriqni faqat yaxshilangan yoki ko'proq ziddiyatga olib kelmasa, qabul qiladi. Agar yo'q bo'lsa, u biron bir ehtimollik bilan topshiriqni qabul qilish uchun harorat joriy topshiriqdan ancha yomonroq ekanligini tekshiradi. Python uchlik operatorlari haqida bilasizmi? Yuvish jadvali qidiruv jarayonida harorat qanday tushishini belgilaydi. Juda keng tarqalgan jadval geometrik sovutishdir. Agar biz haroratni 10 dan boshlasak va har bir qadamdan keyin 0,97 ga ko'paytirsak, 100 qadamdan keyin bizda 0,48 harorat qoladi. Eng yaxshi birinchi qidiruv (BFS) evristik qidiruv Ko'pincha BFS deb ataladi, Best First Search - bu tadqiqotni davom ettirishdan oldin qaysi qo'shni eng istiqbolli ekanligini aniqlash uchun baholash funktsiyasidan foydalanadigan ma'lumotli qidiruv. Kenglik va chuqurlik - Birinchi qidiruvlar xarajat funktsiyasini yodda tutmasdan yo'llarni ko'r-ko'rona o'rganadi. Biroq, BFS bilan hammasi bir xil emas. Bu erda biz tugun xarajatlarini saqlash uchun ustuvor navbatdan foydalanamiz. Pseudocode orqali BFS evristik qidiruvini tushunaylik. OPEN ro'yxatini bitta tugunli s - boshlang'ich tugun bilan belgilang. Agar ro'yxat bo'sh bo'lsa, qaytarilmaydi. Ro'yxatdan n tugunini (eng yaxshi ballga ega bo'lgan tugun) olib tashlang, uni YOPIQ ro'yxatiga o'tkazing. n tugunini kengaytirish. Agar n ning har qanday vorisi maqsad tugun bo'lsa, muvaffaqiyatni qaytaring va yechimni qaytarish uchun maqsad tugunidan s gacha bo'lgan yo'lni kuzating. Har bir voris tugun uchun: Baholash funktsiyasini qo'llash f. AGAR tugun ikkala ro'yxatda bo'lmasa, uni OPEN ro'yxatiga qo'shing. Yüklə 39,01 Kb. Dostları ilə paylaş:
|