|
Ta’lim tizimida dars jadvalini shakllantirishni tadqiqoti va uni yaratish algoritmi Mundarija
|
| bet | 14/25 | | Sana | 28.07.2024 | | Hajmi | 1,86 Mb. | | #268854 |
Bog'liq DissertatsiyaTavlanish simulyatsiyasi usulining algoritmi.
Simulyatsiya qilingan tavlanish algoritmi g'oyasi uni tavlash jarayonida metall atomlarining xatti-harakatlarini o'rganishdan olingan. Erish nuqtasidan yuqori haroratgacha qizdirilgan metallda atomlar tartibsiz harakatda bo'ladi. Bundan tashqari, barcha fizik tizimlarda bo'lgani kabi, ular minimal energiya holatiga (bitta kristall) intilishadi, ammo yuqori haroratlarda atom harakatlarining energiyasi bunga to'sqinlik qiladi. Metallni asta-sekin sovutish jarayonida, mumkin bo'lgan eng past holatga, global minimumga erishilgunga qadar, tobora kam energiyali holatlar yuzaga keladi [49].
Jadval tuzish masalasining matematik modelida holat jadvalning qandaydir joriy versiyasi sifatida tushuniladi. Energiya rolini undagi har bir noqulay moment uchun joriy jadvalga qo'shilgan jarimalar asosidagi ob'ektiv funktsiya o'ynashi mumkin va past energiya holati sifatida to'g'ri (noma'lum bo'lsa ham) jadvaldan foydalanish mumkin.
Keling, yumshatish usuli uchun kengaytirilgan algoritm sxemasini taqdim qilaylik. Masalaning joriy yechimini X bilan belgilaymiz.
Rejalashtirish muammosi uchun tavlanish simulyatsiyasi algoritmi quyidagi bosqichlar ketma-ketligi bilan ifodalanishi mumkin:
1-bosqich. Birinchi iteratsiyada qandaydir to'g'ri boshlang'ich jadval X0 hosil bo'ladi, X = X0, X0 masalaning joriy yechimi hisoblanadi.
2-bosqich. T0 haroratining boshlang'ich, yuqori qiymati va jadvalning mutatsiya (o'zgarishi) operatsiyalari o'rnatiladi. Jadval mutatsiyasi quyidagi harakatlar bilan ta'minlanishi mumkin:
• dars vaqtini o'zgartirish;
• dars auditoriyasining o'zgarishi;
• ikkita dars jadvalidagi o'rin almashish.
3-bosqich. Kiritilgan mutatsiya operatsiyalari va joriy X yechimi asosida avvalgisidan biroz farq qiladigan yangi to'g'ri X' jadvali hosil bo'ladi.
4-bosqich. Maqsad funksiyasining ∆f = f(X') − f(X) o‘zgarishi hisoblanadi:
agar ∆f < 0 (qaror yomonlashmagan), u holda X = X', ya'ni. yangi jadval varianti joriy bo'ladi;
agar ∆f > 0 bo'lsa (yechim yomonlashgan), u holda yangi jadval faqat ehtimolligi bilan joriy bo'ladi.
Va ehtimollik bilan (1 - p) oldingi jadval joriy sifatida saqlanadi.
Bu bosqichda maqsad funksiyasining ortishiga ruxsat beriladi, lekin buning ehtimoli ∆f ortishi bilan kamayadi. Bu mahalliy ekstremallarni engish imkonini beradi.
5-bosqich. Joriy haroratni o'zgartirish funktsiyasi hisoblanadi. Harorat va shunga mos ravishda, maqsad funktsiyasining katta qiymatiga ega bo'lgan jadvalni qabul qilish ehtimoli X joriy jadval har bir iteratsiya bilan kamayadi. Haroratning pasayishi qiymatini bajarilgan takrorlashlar soni bilan ham, maqsad funktsiyasining o'zgarishi qiymati bilan ham bog'lash mumkin va to'xtash mezonini shakllantirish mumkin. Yuqori haroratlarda maqsad funktsiyasining keskin o'zgarishi kuzatiladi. Asta-sekin, harorat pasayganda, uning qiymati minimal bo'lishi kerak.
6- bosqich. Agar to‘xtash mezoni bajarilmasa, 3-bosqichga o‘ting. To‘xtash mezoni sifatida quyidagi qoidalar qabul qilinishi mumkin:
• iteratsiyalarning berilgan sonining bajarilishi;
• maqsad funksiyasining qiymatini berilgan qiymatga yaxshilamasdan, berilgan sonli takrorlashlarni bajarish.
Eng yaxshi m yechimni, shuningdek, oxirgi n ta yaratilgan jadvalni saqlash algoritm samaradorligini oshiradi va rejalashtirish jarayonining aylanishini oldini oladi.
Algoritm bo'yicha olingan eritmaning aniqligi sekinroq harorat o'zgarishi bilan oshirilishi mumkin. Bunday holda, algoritm qidiruv maydonini yanada chuqurroq o'rganadi, lekin uning ishlash muddati sezilarli darajada oshadi. Shuning uchun harorat funktsiyasi har bir aniq vazifa uchun alohida tanlanishi kerak.
Ko'rinib turgan soddaligiga qaramay, bu yondashuv kichik jadvallar uchun juda samarali bo'lishi mumkin. Imtihonlarni rejalashtirish uchun [60] da simulyatsiya qilingan tavlanish usuli ishlatilgan.
|
| |
