|
Ta’lim tizimida dars jadvalini shakllantirishni tadqiqoti va uni yaratish algoritmi Mundarija
|
| bet | 16/25 | | Sana | 28.07.2024 | | Hajmi | 1,86 Mb. | | #268854 |
Bog'liq DissertatsiyaCheklangan mantiqiy dasturlash usuli
Jadvalni ko'plab algoritmlar ishlab chiqilgan cheklovlarni qondirish muammosi sifatida qarash mumkin. Dasturlashda butun yo'nalish mavjud edi - cheklovlarda dasturlash (constraint programming).
Cheklovli dasturlash an'anaviy mantiqiy dasturlash bilan chambarchas bog'liq bo'lib, uning doirasida shakllangan.
Ko'pgina cheklovlarni dasturlash tizimlari cheklovlarni qondirish muammolarining ma'lum bir sinfini hal qilish uchun o'rnatilgan mexanizmga ega oddiy Prolog tarjimonidir. Bunday tizimlarda dasturlash cheklovlarda mantiqiy dasturlash (Constraint Logic Programming yoki CLP) deb ataladi.
Muammolarni hal qilishning asosiy g'oyasi quyidagicha: dasturchi x1, . . ., xn o'zgaruvchilarning ma'lum bir to'plamini va ularning X1, . . ., Xn, qiymatlari diapazonini belgilaydi, o'zgaruvchilar qondirishi kerak bo'lgan qo'shimcha cheklovlarni tavsiflaydi va tizim tegishli qiymatlarni topadi. berilgan barcha cheklovlarni bir vaqtning o'zida qondiradigan o'zgaruvchilardan.
Buni tushuntirish uchun o'rganilayotgan mavzuga oid kichik bir misol keltiramiz. M o'qituvchi ishlaydigan, o'quv rejasida N ta fan belgilangan va sinflar fondi L sinf xonalaridan iborat bo'lgan oliy o'quv yurtini ko'rib chiqaylik. Keling, P = 1, 2, . . ., D to'plamini aniqlaymiz, uning elementlari hafta davomida universitetda o'qishning barcha davrlari (o'quv juftlari), D esa hafta davomidagi barcha o'qish davrlari soni.
Belgilang yij - o'qish davri - i chi o'qituvchi j fanidan dars beradi, . Keyin "har bir o'qituvchi bir vaqtning o'zida bittadan ortiq dars o'tkaza olmaydi" cheklovi quyidagi shaklni oladi:
zi auditoriyada i -chi o'qituvchi dars olib boradigan bo'lsin, bunda . Keyin "har bir sinfda istalgan vaqtda bittadan ortiq dars o'tkazilishi mumkin emas" cheklovi quyidagi shaklni oladi:
Boshqa cheklovlar ham xuddi shunday tarzda amalga oshiriladi.
Algoritm natijasida har bir o'zgaruvchi uchun berilgan cheklovlarni qondiradigan qiymatlar to'plami olinadi. Bunday holda, qat'iy cheklovlarda ishtirok etuvchi o'zgaruvchilarni aniqlash sohasi sezilarli darajada qisqartirilishi yoki hatto bitta qiymatni o'z ichiga olishi mumkin.
CLP-dan foydalanishda qo'lga kiritilgan asosiy afzallik - bu qidiruv maydonining qisqarishi, bu jadvalning har bir variantini baholash orqali emas, balki tizimning o'zi "o'lik nuqtaga olib keladigan yo'llarni" hisobga olishdan chiqarib tashlashi tufayli erishiladi.
Genetik algoritmlar.
Yuqoridagi usullar natijalarni yaxshilash uchun asosan iterativ texnikadan foydalanadi. Bitta iteratsiyani amalga oshirayotganda, ular oldingi iteratsiyada olingan joriy yechim yaqinida eng yaxshi echimni izlaydilar. Agar shunday yechim topilsa, u joriy bo'ladi va yangi iteratsiya boshlanadi. Bu to'xtash qoidasi bajarilgunga qadar davom etadi: maqsad funktsiyasining daromadi deyarli nolga tushadi yoki belgilangan takrorlashlar soni bajariladi. Tabiiyki, bunday usullar faqat mahalliy optimallarni qidiradi va topilgan optimalning pozitsiyasi boshlang'ich nuqtaga bog'liq va global optimalni faqat tasodifan topish mumkin. Global optimalni topish ehtimolini oshirish uchun qidiruv turli boshlang'ich nuqtalari bilan bir necha marta takrorlanadi. Shunday qilib, qidiruv vaqti sezilarli darajada oshadi.
Shuning uchun tavsiflangan usullarning afzalliklarini saqlaydigan va bu kamchilikdan xoli bo'lgan algoritmlarni ishlab chiqish qiziqish uyg'otadi. Bu algoritmlarga genetik algoritmlar kiradi.
Genetik algoritmlar stoxastik evristik optimallashtirish usullari bo'lib, ularning asosiy g'oyasi turlarning evolyutsion rivojlanishi nazariyasidan olingan [26]. Evolyutsiyaning asosiy mexanizmi tabiiy tanlanishdir: ko'proq moslashgan shaxslar omon qolish va ko'payish ehtimoli ko'proq. Ular kamroq moslashgan shaxslarga qaraganda ko'proq nasl beradi. Genetik ma'lumotni uzatish orqali nasl ota-onasidan asosiy fazilatlarni meros qilib oladi. Shaxsning genetik ma'lumotlarining tashuvchisi DNK molekulalaridir. Ikki ota-ona jinsiy hujayralari birlashganda, ularning DNKlari o'zaro ta'sirlashib, naslning DNKsini hosil qiladi. O'zaro ta'sirning asosiy usuli - bu ajdodlar DNKsi ikki qismga bo'lingan, so'ngra ularning yarmi almashinadigan krossingover. Atrof-muhitga ta'sir qilish, masalan, radioaktivlik, ota-onalardan birining jinsiy hujayralarida genlarda mutatsiyaga (o'zgarishlar) olib kelishi mumkin. Mutatsiyaga uchragan genlar naslga o'tishi mumkin va u yangi xususiyatlarga ega bo'ladi. Yangi xususiyatlar ma'lum bir tur uchun foydali bo'lishi mumkin, uning yaroqliligini oshiradi va keyin bu xususiyatlar ushbu turda saqlanib qoladi.
Genetik algoritmga asoslangan matematik modelni yaratishda birinchi qadam eritmani saqlaydigan xromosoma tuzilishini ishlab chiqishdir. Bizning holatlarimizda bunday "xromosoma" jadvaldir. Tanlangan tuzilma kerakli yechimga qo'yilgan barcha xususiyatlar va cheklovlarni, shuningdek, krossover va mutatsiya algoritmlarini amalga oshirish bevosita uning tanloviga bog'liqligini hisobga olishi kerak. Oxir oqibat, "xromosoma" ni tanlash nafaqat tezlikka, balki umuman algoritmning yaqinlashishiga ham ta'sir qiladi.
Ko'rib chiqilayotgan masalani yechishning eng qulay ko'rinishlaridan biri bu uch o'lchovli matritsa bo'lib, i, j, k o'qlari bo'ylab mos ravishda guruhlar, mashg'ulotlar soatlari va auditoriyalar chiziladi. Matritsaning elementi bu o'qituvchi tomonidan ushbu fan bo'yicha i - bu guruh bilan j - soatda k - o'sha auditoriya bilan dars o'tkazish so'rovidir. Asosan, darsni o'tkazish so'rovi quyidagicha: dastlabki ma'lumotlarni o'rnatish bosqichida foydalanuvchi har bir guruh (kichik guruh, oqim) uchun belgilangan o'quv rejasi doirasida ularni o'rgatadigan fanlar va o'qituvchilarni ko'rsatadi. Shundan so'ng, har bir bo'g'in fan-guruh-o'qituvchi yagona shaxs sifatida ko'rib chiqiladi, agar algoritmga ma'lumot kiritilsa: qaysi fanlar, qaysi guruhda, qaysi o'qituvchi va qaysi auditoriya turi bunga mos keladi [26].
Xromosomaning bunday tuzilishi qulay, chunki dastlabki ma'lumotlarni o'rnatish bosqichida, mos keladigan hujayralarni blokirovka qilish orqali aniq muvaffaqiyatsiz echimlarni chiqarib tashlash mumkin.
Algoritmning keyingi bosqichida boshlang'ich populyatsiya yaratiladi, uning hajmi muammoning o'lchamiga bog'liq va odatda bir necha yuz echimni tashkil qiladi.
Optimallashtirish jarayonini tashkil etish uchun aholi rivojlanishi uchun yetakchi kuch yaratish zarur. Bunday kuch maqsad funktsiyasini (genetik algoritmlar nuqtai nazaridan, fitnes funktsiyasi) minimallashtirish talabidir. Fitnes funktsiyasi sifatida siz jadvaldagi ba'zi noqulay daqiqalar uchun har bir yechim uchun belgilangan jazolarga asoslangan qo'shimcha optimallik ko'rsatkichidan foydalanishingiz mumkin. Ushbu tanlovning muhim xususiyati - muayyan muammoni hal qilish uchun algoritmni sozlash qobiliyati. Bunga koeffitsientlarni o'zgartirish orqali erishiladi, bu esa optimal jadvalni qidirishda ustuvorliklarning o'zgarishiga olib keladi.
Genetik algoritmning sxemasi 4-rasmda ko'rsatilgan.
|
| |
