Heuristika za automatsko sastavljanje paralelnih testova znanja

Abstract

Paralelni testovi znanja su testovi koji sadrže različite skupove stavki (skupove pitanja ili zadataka različitih vrsta) sa približno jednakim mernim osobinama, što ih čini međusobno zamenljivim. Oni imaju primenu kada više ispitanika rešava test, bez obzira da li to čine u isto ili u različito vreme. Rezultati dobijeni testiranjem moraju da budu poredivi. Automatizam u procesu sastavljanja paralelnih testova znanja je praktično neophodan da bi se postigla objektivnost ispitivanja dobrim balansiranjem mernih osobina različitih primeraka testa i smanjila mogućnost grešaka ispitivača u merenju znanja. Što je testiranje masovnije, ušteda ulož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 probleme kombinatorne optimizacije, korišćenje heuristika je očekivano i neophodno. Problem ASPT je izomorfan sa nekim postojećim problemima kombinatorne optimizacije, pa se heuristike za rešavanje tih problema mogu koristiti i za rešavanje problema ASPT. U disertaciji je dat opsežan pregled postojećih formulacija ovog problema, odnosno njihovih matematičkih modela, a zatim pregled heuristika koje se koriste za rešavanje različitih formulacija problema. Najpre su formulacije problema i heuristička rešenja nezavisno klasifikovani, a zatim se njihovom unakrsnom klasifikacijom ukazalo na otvoren prostor za istraživanje kroz nove kombinacije formulacija problema i heuristika za njihovo rešavanje. Heuristike koje se koriste za rešavanje problema ASPT su uglavnom heuristike poboljšanja, čije se izvršenje prekida ili kada dođe do unapred zadatog vremena izvršavanja ili kada je dostignut željeni kvalitet rešenja. Konstruktivne heuristike se uglavnom koriste za kreiranje početnog rešenja za heuristike poboljšanja. Fokus ove disertacije je na predlogu novog efikasnog metoda polinomijalne kompleksnosti za kompletno rešavanje problema ASPT. Predloženi metod rešava jednu formulaciju Problema 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đu karakteristikama novog metoda ističu se predvidivo vreme njegovog izvršenja, efikasnost i jednostavnost implementacije. Predvidivo vreme i efikasno sastavljanje testova je od posebnog znač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 su zasnovani na heuristikama poboljšanja, kakve su simulirano kaljenje (eng. Simulated Annealing, SA) i pretraga promenljivih okolina (eng. Variable Neighborhood Search, VNS). U otvorenoj literaturi, VNS metod daje rezultate najboljeg kvaliteta za problem ASPT formulisan kao Problem pakovanja u korpe. Vreme izvršenja predloženog algoritma je značajno kraće u poređenju sa SA algoritmom, dok je kvalitet zanemarljivo lošiji. U poređenju sa VNS algoritmom, prosečno vreme izvršavanja je značajno kraće, dok za isto vreme izvršavanja (postignuto prekidanjem izvršavanja VNS algoritma), predloženi novi algoritam postiže bolji kvalitet rešenja za slučaj relativno malog broja 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.

Parallel knowledge tests are tests which contain different sets of items (sets of questions or assignments of different types) with approximately equal measurement properties, that make them interchangeable. They are applicable when more examinees are solving the test, regardless of whether they do it at the same time or at different times. The results of the testing must be comparable. Automation of the parallel test assembly process is practically necessary in order to achieve objectivity of the testing by well balancing the measurement properties of different test forms and to reduce the possibility of subjective errors by the examiner. Also, the more massive the testing, the more significant is saving up the invested examiner’s time for preparation of parallel tests, by automation of assembly process. Since the automated parallel test assembly problem (APTA) belongs to NP-hard combinatorial optimization problems, the use of heuristics is expected and necessary. The APTA problem is isomorphic with some existing combinatorial optimization problems, therefore heuristics for solving those problems can also be used for solving the APTA problem. In the dissertation an extensive 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 of the problem and heuristics for their solving. The heuristics used to solve ASPT problems are mainly improvement heuristics, where the execution is interrupted either when a predetermined execution time occurs or when the desired quality of the solution is reached. Constructive heuristics are mainly used to create an initial solution for improvement heuristics. The focus of this dissertation is on the proposal of a new efficient method of polynomial complexity for the complete solving the APTA problem. The proposed method solves one formulation of the bin packing problem by adapting the constructive heuristic proposed by Nawaz, Enschore and Ham, which has not been used for solving the APTA problem so far. Among the characteristics of the new method, predictable execution time, efficiency and simplicity of implementation stand out. Predictable time and efficient tests assembly is of special importance in educational institutions where frequent testing of a relatively small number of examinees is performed, and where the available computer resources for ASPT are limited. The proposed APTA method has been implemented and compared to the efficient comparable methods based on improvement heuristics, such as simulated annealing (SA) and variable neighbourhood search (VNS). In open literature, the VNS method gives the results of the best quality for the APTA problem formulated as the bin packing problem. The execution time of the proposed algorithm is significantly shorter compared to the SA algorithm, while the quality is negligibly worse. Compared to the VNS algorithm, the average execution time is significally shorter, while for the same execution time (achieved by interrupting the execution of the VNS algorithm), the proposed new algorithm achieves a better quality of result for the case of a relatively small number of parallel tests (20, 30 and 60) and relatively small item banks (300 items), which are often found in knowledge tests in education institutions.