Naslov (srp)

Heuristika za automatsko sastavljanje paralelnih testova znanja : doktorska disertacija

Autor

Ignjatović, Miroslava, 1974-

Doprinosi

Protić, Jelica, 1962-
Bojić, Dragan, 1967-
Tartalja, Igor, 1959-
Tomašević, Milo, 1957-
Simić, Dejan, 1964-
Lutovac, Tatjana, 1966-

Opis (eng)

Parallel knowledge tests are tests which contain different sets of items (sets of questionsor assignments of different types) with approximately equal measurement properties, that makethem interchangeable. They are applicable when more examinees are solving the test, regardless ofwhether they do it at the same time or at different times. The results of the testing must becomparable.Automation of the parallel test assembly process is practically necessary in order to achieveobjectivity of the testing by well balancing the measurement properties of different test forms and toreduce the possibility of subjective errors by the examiner. Also, the more massive the testing, themore significant is saving up the invested examiner’s time for preparation of parallel tests, byautomation of assembly process.Since the automated parallel test assembly problem (APTA) belongs to NP-hard combinatorialoptimization problems, the use of heuristics is expected and necessary. The APTA problem isisomorphic with some existing combinatorial optimization problems, therefore heuristics forsolving those problems can also be used for solving the APTA problem. In the dissertation anextensive review of the existing formulations of this problem is presented, its mathematical models,then an overview of the heuristics used for solving different problem formulations. Firstly,formulations of the problem and heuristic solutions are independently classified, then their crossclassification pointed to an open space for exploration through new combinations of formulations ofthe problem and heuristics for their solving.The heuristics used to solve ASPT problems are mainly improvement heuristics, where theexecution is interrupted either when a predetermined execution time occurs or when the desiredquality of the solution is reached. Constructive heuristics are mainly used to create an initialsolution for improvement heuristics. The focus of this dissertation is on the proposal of a newefficient method of polynomial complexity for the complete solving the APTA problem. Theproposed method solves one formulation of the bin packing problem by adapting the constructiveheuristic proposed by Nawaz, Enschore and Ham, which has not been used for solving the APTAproblem so far. Among the characteristics of the new method, predictable execution time, efficiencyand simplicity of implementation stand out. Predictable time and efficient tests assembly is ofspecial importance in educational institutions where frequent testing of a relatively small number ofexaminees is performed, and where the available computer resources for ASPT are limited.The proposed APTA method has been implemented and compared to the efficient comparablemethods based on improvement heuristics, such as simulated annealing (SA) and variableneighbourhood search (VNS). In open literature, the VNS method gives the results of the bestquality for the APTA problem formulated as the bin packing problem. The execution time of theproposed algorithm is significantly shorter compared to the SA algorithm, while the quality isnegligibly worse. Compared to the VNS algorithm, the average execution time is significallyshorter, while for the same execution time (achieved by interrupting the execution of the VNSalgorithm), the proposed new algorithm achieves a better quality of result for the case of a relativelysmall number of parallel tests (20, 30 and 60) and relatively small item banks (300 items), whichare often found in knowledge tests in education institutions.

Opis (srp)

Paralelni testovi znanja su testovi koji sadrže različite skupove stavki (skupove pitanja ilizadataka različitih vrsta) sa približno jednakim mernim osobinama, što ih čini međusobnozamenljivim. Oni imaju primenu kada više ispitanika rešava test, bez obzira da li to čine u isto ili urazličito vreme. Rezultati dobijeni testiranjem moraju da budu poredivi.Automatizam u procesu sastavljanja paralelnih testova znanja je praktično neophodan da bi sepostigla objektivnost ispitivanja dobrim balansiranjem mernih osobina različitih primeraka testa ismanjila mogućnost grešaka ispitivača u merenju znanja. Što je testiranje masovnije, uštedauloženog vremena ispitivača za pripremu paralelnih testova, primenom automatizacije sastavljanja,postaje značajnija.Pošto problem automatskog sastavljanja paralelnih testova (ASPT) spada u NP-teške problemekombinatorne optimizacije, korišćenje heuristika je očekivano i neophodno. Problem ASPT jeizomorfan sa nekim postojećim problemima kombinatorne optimizacije, pa se heuristike zarešavanje tih problema mogu koristiti i za rešavanje problema ASPT. U disertaciji je dat opsežanpregled postojećih formulacija ovog problema, odnosno njihovih matematičkih modela, a zatimpregled heuristika koje se koriste za rešavanje različitih formulacija problema. Najpre suformulacije problema i heuristička rešenja nezavisno klasifikovani, a zatim se njihovom unakrsnomklasifikacijom ukazalo na otvoren prostor za istraživanje kroz nove kombinacije formulacijaproblema i heuristika za njihovo rešavanje.Heuristike koje se koriste za rešavanje problema ASPT su uglavnom heuristike poboljšanja, čije seizvršenje prekida ili kada dođe do unapred zadatog vremena izvršavanja ili kada je dostignut željenikvalitet rešenja. Konstruktivne heuristike se uglavnom koriste za kreiranje početnog rešenja zaheuristike poboljšanja. Fokus ove disertacije je na predlogu novog efikasnog metoda polinomijalnekompleksnosti za kompletno rešavanje problema ASPT. Predloženi metod rešava jednu formulacijuProblema pakovanja u korpe prilagođavanjem konstruktivne heuristike koju su predložili Nawaz,Enscore i Ham, a koja do sada nije primenjivana za rešavanje problema ASPT. Međukarakteristikama novog metoda ističu se predvidivo vreme njegovog izvršenja, efikasnost ijednostavnost implementacije. Predvidivo vreme i efikasno sastavljanje testova je od posebnogznačaja u obrazovnim ustanovama u kojima se vrše česta testiranja relativno malog broja ispitanika,a gde su raspoloživi računarski resursi za ASPT ograničeni.Predloženi metod ASPT je implementiran i upoređen sa efikasnim poredivim metodima koji suzasnovani na heuristikama poboljšanja, kakve su simulirano kaljenje (eng. Simulated Annealing,SA) i pretraga promenljivih okolina (eng. Variable Neighborhood Search, VNS). U otvorenojliteraturi, VNS metod daje rezultate najboljeg kvaliteta za problem ASPT formulisan kao Problempakovanja u korpe. Vreme izvršenja predloženog algoritma je značajno kraće u poređenju sa SAalgoritmom, dok je kvalitet zanemarljivo lošiji. U poređenju sa VNS algoritmom, prosečno vremeizvršavanja je značajno kraće, dok za isto vreme izvršavanja (postignuto prekidanjem izvršavanjaVNS algoritma), predloženi novi algoritam postiže bolji kvalitet rešenja za slučaj relativno malogbroja paralelnih testova (20, 30 i 60) i banke stavki relativno male veličine (300 stavki), kakvi sečesto sreću kod testova znanja u obrazovnim institucijama.

Opis (srp)

Elektrotehnika i računarstvo - Softversko inženjerstvo / Electrical engineering and computer science - Software engineering Datum odbrane: 05.09.2022.

Jezik

srpski

Datum

2022

Licenca

Ovo delo je licencirano pod uslovima licence
Creative Commons CC BY-NC-ND 3.0 AT - Creative Commons Autorstvo - Nekomercijalno - Bez prerada 3.0 Austria License.

http://creativecommons.org/licenses/by-nc-nd/3.0/at/legalcode

Predmet

OSNO - Opšta sistematizacija naučnih oblasti, Kombinatorna analiza. Teorija grafova

OSNO - Opšta sistematizacija naučnih oblasti, Softversko inženjerstvo

automated test assembly, parallel tests, combinatorial optimization, bin packing, heuristic, constructive heuristic

OSNO - Opšta sistematizacija naučnih oblasti, Kombinatorna analiza. Teorija grafova

OSNO - Opšta sistematizacija naučnih oblasti, Softversko inženjerstvo

automatsko sastavljanje testova, paralelni testovi, kombinatorna optimizacija, pakovanje u korpe, heuristika, konstruktivna heuristika