Turinys

Uzduotis	Uzduoties analize	Teorine dalis	Algoritmas
Instrukcija vartotojui	Rezultatai	Programos tekstas	Isvados

Uzduotis

Sudaryti programa, kuri leistu generuoti vidurines mokyklos viduriniu ir aukstesniuju (penktu - dvyliktu) klasiu vienos savaites pamoku tvarkarasti ir optimizuotu ji taip, kad butu kuo maziau mokytoju langu.

Turinys

Uzduoties analize

Pagrindinis uzdavinio tikslas - praktikoje pritaikyti diskretinio optimizavimo uzdavini. Musu uzdavinys patenka i optimalaus planavimo uzdaviniu grupe, kuriai priklauso tokie uzdaviniai, kaip vagies, siuvyklos, mokyklos tvarkarascio ir kt. Sudarant mokyklos tvarkarasti, reikia nustatyta kiekvienai klasei atitinkamu dalyku skaiciu isdestyti visoje savaiteje taip, kad nebutu virsyti turimi mokyklos resursai: kabinetai, mokytojai ir t.t.

Mokyklos tvarkarascio uzdavinys issiskiria tokiais ypatumais:

• Mokiniai negali tureti langu
• Akademine tvarka nefiksuota (yra tik pageidavimai)

Mokykloje yra sie riboti resursai:

• mokytoju skaicius
• mokytoju darbo laikas
• kabinetu skaicius
• vienos dienos maksimalus pamoku skaicius

Be to, dar yra apribojimu, kurie isryskeja tvarkarascio formavimo metu:

• vienas mokytojas vienu metu gali vesti pamoka tik vienai klasei
• vienu metu viename kabinete gali vesti pamoka tik vienas mokytojas
• kai kurios pamokos yra dvigubos, t.y. turi buti vedamos dvi to dalyko pamokos is eiles
• tuo paciu kabinetu naudojasi du mokytojai

Pradiniai duomenys siai uzduociai yra:

• kiekvienos klases pamoku planas
• mokytoju uzimtumo grafikas
• "dvigubu" pamoku sarasas
• mokyklos kabinetu skaicius

Ivertinus visus siuos aspektus, galime apibrezti busimos programos matmenis:

• Kadangi pradiniams duomenims atvaizduoti pakanka dvimaciu lenteliu, tai juos patogu saugoti ir koreguoti standartiniuose CSV failuose, kur kiekviena eilute atitinka lenteles eilute, o stulpeliai skiriami kabliataskiais. Siuos failus galima redaguoti tekstiniu redaktoriumi, o taip pat Microsoft Excel programa.
• Ivedus pradinius duomenis, reikia patikrinti, ar pagal juos aplamai galima sudaryti tvarkarasti, t.y. ar jie yra leistini
• Kadangi realiu atveju skaiciavimu apimtis yra labai didele, tai yra netinkamas pilnas visu variantu perrinkimas
• Galima tiketis geru rezultatu derinant globalia paieska su lokalia, t.y. globalioje dalyje suformuojame pradini leistina sprendini, o lokalioje - ji geriname. Toks poziuris geras ir tuo atveju, jei jau turime pradini tvarkarascio varianta ir norime ji pagerinti
• Neleistinas yra toks tvarkarascio variantas, kai mokiniai turi nors viena langa.

Sio uzdavinio realizacija remsis ne tik auksciau paminetais praktiniais pastebejimais, taciau ir tam tikra teorine medziaga, kuri bus pateikta tolesniame skyriuje.

Turinys

Teorine dalis

Matematiskai tvarkarascio uzdavinys yra formuluojamas taip:
X(j), j=1..N - mokiniu klases
Y(I), I=1..M - dalykai
t(i,j), pozymis, ar i-tasis dalykas destomas j-tajai klasei.
Akademine pamoku tvarka - nefiksuota.
Yra riboti resursai (laikas, kabinetai): r(i,j)=(r(i,j)^1, � , r(i,j)^k).
Resursai pasizymi tuo, kad Sr(i,j)<=r(i).
Optimalumo kriterijai - laiko nuostoliai.
Reikia sudaryti optimalu tvarkarasti, t.y. toki, kuriame butu minimalus laiko nuostoliai.

Tvarkarascio uzdavinys yra priskiriamas NP-complete uzdaviniu klasei, kuriu skaiciavimo apimtis yra isreiskiama formule: T=C*2^m, kur m-kintamuju skaicius. Eksponentinis laikas T yra mokestis uz garantija.
Jei uzdavinys priklauso NP-complete klasei ir nepasizymi jokiomis ypatingomis savybemis (kurios susiaurina leistinu sprendiniu aibe) bei norime tikrai (!) optimalaus sprendinio, tuomet reikia pasirinkti PP - pilna perrinkima. Realiai tai reiskia labai dideles skaiciavimo apimtis.
Galima taikyti algoritmus, kurie stengiasi is anksto nustatyti sritis, kuriose nera leistinu sprendiniu ir tokiu budu greiciau gauna optimalu.Vienas is tokiu yra B&B - saku ir ribu algoritma. Darbo eigoje jis atsiriboja nuo neperspektyviu sprendiniu, taciau galima situacija, kai ir jis tures perrinkti visus variantus.
Jei mes atsisakome garantijos, kad gausime optimalu sprendini, tai galime pasinaudoti heuristiniais algoritmais, kurie perziuri tik tam tikra dali leistinu sprendiniu ir is ju parenka geriausia ir ji pateikia kaip optimaliausia gauta sprendini.

Yra du heuristikos budai:

1. "Gobsi" heuristika. Ji surusiuoja visus einamo zingsnio variantus pagal tam tikra "geruma" ir pasirenka varianta, kuris yra "geriausias. Vagies uzdaviniui sio algoritmo "kaina" nuo eksponentinio sumazeja iki T=Cm^2. Jis gerai veikia, kai yra didelis variantu "gerumu" issibarstymas.
2. Randomizuota heuristika. Ji paremta tuo principu, kad tolesni varianta pasirenkame nebutinai geriausia, o pagal tam tikra tikimybe. T.y. visiems variantams paskaiciuojame ju heuristikas ir tolesni varianta pasirenkame pagal sugeneruota atsitiktini skaiciu is intervalo [0..1].

Galima imti ne tiesine, o kitokia priklausomybe:
r0 = 1/N - Monte Carlo;
r1 = h(n)/ sum_j h(j) - tiesine;
r2 = h(n)^2/ sum_j h(j)^ - kvadratine;
r3 = 1, jei h(n)= max_j h(j) - "Gobsi".
Siuo atveju mes turime dvi loterijas: bilietine, kuri parodo, pagal kuria taisykle rinksimes tolesni varianta ir kainine, kuri randa tolesnio varianto numeri pagal bilietineje loterijoje nustatyta taisykle. Visais atvejais iskyla klausimas - kas yra varianto "gerumas"? Jis priklauso nuo konkrecios situacijos. Vagies uzdavinyje - tai maiso kaina, mokyklos tvarkarascio - mokytoju langu skaicius ir pan.

Turinys

Algoritmas

Atsizvelgus i pastabas, isdestytas uzduoties analizeje ir teorineje dalyje, buvo sudarytas toks apibendrintas uzduoties sprendimo algoritmas:

1. DuomenuIvedimas();
2. PradiniuDuomenuStrukturuInicializacija();
3. GeriausiasSprendinys=MAX;
4. do k=1, � MaxIter
1. GlobaliPaieska();
2. if LeistinasSprendinys=TRUE
3. begin
1. LokaliPaieska()
2. FiksuotiGeriausiaSprendini();
4. end
5. enddo

Pradiniame etape skaitome duomenis is failu ir paruosiame leistinu pamoku masyvus KLL ir KL0, kurie parodo kokias pamokas gali tureti konkreciu metu konkreti klase.

Globalioje paieskoje:

1. Paeiliui nuo pirmuju pamoku pereinamos visos savaites pamokos (masyvas PM uzduoda pamoku perrinkimo tvarka)
2. Visos klases surusiuojamos leistinu dalyku aktyviai pamokai skaiciaus didejimo tvarka
3. 2-tame punkte nustatyta tvarka perrenkamos visos klases ir aktyviai pamokai atsitiktiniu budu parenkamas dalykas is leistinu dalyku saraso (KLL).
4. Parinkus viena dalyka kuriai nors klasei, vel is naujo perziurima likusiu klasiu perrinkimo tvarka
5. Kartojami 3-5 punktai visoms klasems
6. Kartojami 2-6 punktai visoms savaites pamokoms

Jei globalioje paieskoje buvo gautas leistinas sprendinys, tai tolesniame zingsnyje atliekama lokali paieska:

1. Zingsnis k=0
1. ivertinam tvarkarascio L_0 geruma H_0
2. atliekam N tvarkarascio L_0 perstatymu L_0(n), n=1,...,N
3. ivertinam siu perstatymu "gerumus" atitinkamai H_0(n), n=1,...,N
4. paskaiciuojam "heuristikas" h_0(n)= H_0(n)-H_0^min
5. nustatom tris randomizacijos taisykles:
   r^0(n)=1/N
   r^1(n)=h_0(n)/ sum_j h_0(j)
   r^2(n)=1, jei h_0(n)= max_j h_0(j)
   kur r^i(n) nurodo tikimybe isrinkti perstatyma n naudojant taisykle i
6. fiksuojam kievienos is siu taisykliu panaudojimo tikimybes
7. atsitiktiniu budu pasirenkame taisykle, pagal kuria pasirinksime tolesni sprendini
8. atsitiktiniu budu pagal anksciau pasirinkta taisykle parenkame perstatyma, kuri laikysime pradiniu kitam lokalios paieskos zingsniui. Rezultate gaunam modifikuota tvarkarasti L(1)
2. Zingsnis k=1
1. Darom ta pati su modifikuotu tvarkarasciu,
2. Isrenkam geriausia modifikacija lygindami "gerumus" H_0 ir H_1,
3. Pazymim jos geruma H*_1 = max (H_0,H_1)
3. Po K zingsniu gaunam geruma H*_K

Fiksuojant geriausia sprendini palyginame jau turima geriausia sprendini su sprendiniu, kuris buvo gautas po lokalios paieskos ir atsimename geresni.

Turinys

Instrukcija vartotojui

Vartotojui yra pateikiamas programinis paketas, skirtas ne tik stebeti sudarytos programos darba, bet ir analizuoti jos veikima ir rezultatus esant ivairiems pradiniams parametrams. Programa paleidziama komandineje eiluteje surinkus "test".
Vartotojui pateikiamas programos langas, kuris turi tokius meniu punktus: "Global", "Local", "Operations", "Quit", "Parameters", "Output".
Meniu punktais "Global" ir "Local" vartotojas gali pasirinkti darbo algoritmus.
Meniu punktas "Output" suteikia galimybe perziureti skaiciavimu rezultatus programos darbo metu.
Pasirinkus algoritma, reikia meniu punkte "Parameters" parinkti darbinius parametrus: IT - iteraciju skaiciu, LT - pradiniu iteraciu skaicius. Ai ir Bi - tai intervalai, kuriuose programa pagal pasirinkta algoritma parinks skaicius.
Jei visi nustatymai baigti, reikia pasirinkti meniu punkta "Operations.Run".
Programos pabaiga - punktas "Quit".

Turinys

Rezultatai

Programos kurimo metu buvo sudarytos dvi programos versijos: DOS ir UNIX opracinems sistemoms.

Programos versija UNIX operacinei sistemai buvo priderinta prie jau egzistuojancio ivairius optimizavimo metodus palaikancio paketo. DOS operacinei sistemai buvo galima naudotis tuo paciu paketu TurboC kalbai, arba paleisti vykdyti sia programa visiskai atskirai. Paskutiniuoju atveju reikia ranka nustatyti vidiniu taisykliu parinkimo tikimybes (masyvas X). Abiem kitais atvejais sias tikimybes pagal pasirinktus metodus parinkdavo programiniai paketai. Pateikti programiniai paketai leidzia stebeti gauto optimalaus sprendinio kitimo dinamika. Autonominis DOS variantas rezultatus pateikia tekstiniame pavidale, taciau jis leidzia analizuoti ir ankstesnius duomenis, ko neleidzia mineti programiniai paketai.

Kaip pavyzdi pateiksime vieno skaiciavimo eiga. Buvo atlikta 30 globaliu iteraciju. Kiekvienos globalios iteracijos metu buvo vykdoma 10 lokaliu iteraciju. Lokalioje paieskoje buvo generuojama 100 galimu tolesniu perstatymu. Programa ekrane pateike toki vaizda:

 2. Mokytojai: Global = 184 Local = 164 Min = 164
 3. Mokytojai: Global = 187 Local = 165 Min = 164
 5. Mokytojai: Global = 175 Local = 155 Min = 155
 6. Mokytojai: Global = 191 Local = 169 Min = 155
 7. Mokytojai: Global = 173 Local = 171 Min = 155
 8. Mokytojai: Global = 197 Local = 170 Min = 155
10. Mokytojai: Global = 181 Local = 157 Min = 155
11. Mokytojai: Global = 174 Local = 166 Min = 155
13. Mokytojai: Global = 190 Local = 158 Min = 155
14. Mokytojai: Global = 180 Local = 162 Min = 155
15. Mokytojai: Global = 167 Local = 140 Min = 140
16. Mokytojai: Global = 195 Local = 160 Min = 140
18. Mokytojai: Global = 167 Local = 161 Min = 140
19. Mokytojai: Global = 181 Local = 156 Min = 140
20. Mokytojai: Global = 188 Local = 169 Min = 140
21. Mokytojai: Global = 174 Local = 163 Min = 140
22. Mokytojai: Global = 197 Local = 158 Min = 140
23. Mokytojai: Global = 189 Local = 163 Min = 140
24. Mokytojai: Global = 190 Local = 170 Min = 140
25. Mokytojai: Global = 188 Local = 154 Min = 140
26. Mokytojai: Global = 200 Local = 169 Min = 140
27. Mokytojai: Global = 196 Local = 181 Min = 140
30. Mokytojai: Global = 181 Local = 165 Min = 140

Stulpeliuose atitinkamai pavaizduoti mokytoju langai: po globalios paieskos, po lokalios paieskos ir rastas geriausias sprendinys. Kai kuriu iteraciju rezultatai i ekrana isvesti nebuvo, nes po globalios paieskos buvo gautas neleistinas sprendinys ir lokali paieska su tuo variantu nebuvo atliekama..

Turinys

Programos tekstas

Failas FI.C

Duomenu failas VALANDOS.CSV

Duomenu failas UZIMTUM.CSV

Duomenu failas DVIGUBA.CSV

Turinys

Isvados

1. Sudaryta programa, kuri suformuoja vidurines mokyklos pamoku tvarkarasti
2. Optimalaus varianto ieskota naudojantis randomizuota heuristika
3. Programa ivertina tokias realias situacijas:
1. Ivertina mokytoju darbo grafika (mokytojai gali vesti pamokas ne visomis valandomis)
2. Ivertina "dvigubas" pamokas, kai tai paciai klasei vienas dalykas turi buti destomas dvi pamokas paeiliui
3. Neleidzia, kad vienas mokytojas vienu metu vestu dvi pamokas
4. Neleidzia langu mokiniams
5. Pajegus dirbti su realios mokyklos duomenu apimtimis, t.y. kai turime realius mokytoju, dalyku bei klasiu skaicius
4. Stengtasi, kad programa butu kuo arciau realios situacijos, taciau ji neivertina:
1. Riboto kabinetu skaiciaus
2. Situacijos, kai viename kabinete skirtingu metu dirba skirtingi mokytojai
3. Uzsienio kalbu pasiskirstymo
4. Situacijos, kai vienas dalykas turi buti destomas kelioms klasems vienu metu
5. Pageidavimu, kad tikslieji dalykai butu anksciau uz kitus, t.y. visi dalykai turi vienodus pirmumo prioritetus
5. Programos testavimo metu naudota randomizuota heuristika padeda pagerinti globalios paieskos metu gauta sprendini iki 50% kartu, t.y. sumazina mokytoju langu skaiciu iki dvieju kartu.

Turinys