Optimization of the Item Selection Problem Using Multi-Division Dynamic Programming

利用多區間動態規劃技術於選題策略之研究

10.7108/PT.201009.0325

林靖玲(Ching-Ling Lin)；孫光天(Koun-Tem Sun)

多區間動態規劃 ； 動態規劃 ； 選題問題 ； Dynamic Programming ； item selection problem ； Multi-Division Dynamic Programming

測驗學刊

57卷3期（2010 / 09 / 01）

325 - 343

英文

對於解組合最佳化問題上，動態規劃(Dynamic Programming, DP)是一種功能強大的尋求最佳解之有效技術。但是，在多變數（維度）的二次方程式中，DP無法找到0~1整數規劃的最佳解。在本文中，研究者提出一新的技術「多區間動態規劃」(Multi-Division Dynamic Programming, MDDP)做為選題策略。在建構測驗時，MDDP除了可以改善DP的效率和正確性外，亦可有效解決誤差函數為二次函數時，所導致誤差值遞減後再遞增的問題。實驗結果顯示，研究者所提出的方法能產生誤差非常小的平行測驗，優於其他新近所提的方法，而且MDDP的執行時間與誤差的改善率比傳統DP好，改進比例分別達到88.3%和94.9%，肯定了本研究所提之多區間動態規劃技術，對於測驗之選題策略，具有高效益與高精確度，對測驗之研究也提供一有用的技術。

Dynamic Programming (DP) is a powerful method for solving combinatorial optimization problems. However, it is incapable of finding the optimal solutions of 0-1 integer programming in the multi-dimensional quadratic equation. In this study, we proposed a new approach called ”Multi-Division Dynamic Programming (MDDP)” that improves the efficiency and the accuracy of dynamic programming in constructing parallel tests for minimizing the deviations of quadratic equations. Experimental results show that our proposed approach can construct the parallel tests with the lowest error than the other methods (e.g., Genetic Algorithm, Greedy Approach, Neural Network, Swanson & Stocking, and Wang & Ackerman). The execution-times and the deviation improvement ratios of MDDP are more than 88.3% and 94.9% better than DP. The proposed MDDP would be useful for its effectiveness and accuracy to the item selection problem.

1. Armstrong, R. D.,Jones, D. H.,Kunce, C. S.(1998).IRT test assembly using networkflow programming.Applied Psychological Measurement,22(3),237-247.
2. Baker, F. B.,Cohen, A. S.,Barmish, B. R.(1998).Item characteristics of tests constructed by linear programming.Applied Psychological Measurement,12(2),189-199.
3. Camus, M.,Cardon, A.(2006).Dynamic programming for robot control in real-time: Towards a morphology programming.Proceedings of the 2006 International Conference on Artificial Intelligence,Las Vegas, Nevada, USA:
4. Dreyfus, S.(2002).Richard Bellman on the birth of dynamic programming.Operations Research,50(1),48-51.
5. Hambelton, R. K.,Swaminathan, H.(1985).Item response theory: Principles and applications.Hingham, MA:Kluwer, Nijhoff.
6. Hambleton, R. K.,Swaminathan, H.,Rogers, H. J.(1991).Fundamentals of item response theory.Newbury Park, CA:Sage.
7. Hau, K. T.,Chang, H. H.(2001).Item selection in computerized adaptive testing: Should more discriminating items be used first?.Journal of Educational Measurement,38(3),249-266.
8. Hedlund, S.,Rantzer, A.(2002).Convex dynamic programming for hybrid systems.IEEE Transactions on Automatic Control,47(9),1536-1540.
9. Hulin, C. L.,Drasgow, F.,Parsons, C. K.(1983).Item response theory: Application to psychological measurement.Homewood, IL:Dow Jones-Irwin.
10. Jeng, H. L.,Shih, S. G.(1997).A comparison of pairwise and group selections of items using simulated annealing in automated construction of parallel tests.Psychological Testing,44(2),195-212.
11. Kim, Y. H.,Yoo, C. Y.,Lee, I. B.(2008).Optimization of biological nutrient removal in a SBR using simulation-based iterative dynamic programming.Chemical Engineering Journal,139,11-19.
12. Kleinberg, J.,Tardos, E.(2006).Algorithm design.London:Pearson/Addison-Wesley.
13. Kumar, N. D.,Baliarsingh, F.(2003).Folded dynamic programming for optimal operation of multireservoir system.Water Resources Management,17(5),337-353.
14. Kung, J. J.(2008).Multi-period asset allocation by stochastic dynamic programming.Applied Mathematics and Computation,199(1),341-348.
15. Leung, C. K.,Chang, H. H.,Hau, K. T.(2002).Item selection in computerized adaptive testing: Improving the a-stratified design with the sympson-hetter algorithm.Applied Psychological Measurement,26(4),376-392.
16. Lew, A.,Mauch, H.(2007).Applications of dynamic programming.Studies in Computational Intelligence,38,45-100.
17. Lord, F.(1952).A theory of test scores.Richmond, VA:Psychometric Corporation.
18. Lord, F. M.(1953).An application of confidence intervals and of maximum likelihood to the estimation of an examinee's ability.Psychometrika,18,57-76.
19. Lord, F. M.(1980).Applications of item response theory to practical testing problems.Hillsdale, NJ:Lawrence Erlbaum Associates.
20. Lord, F. M.,Novick, M. R.(1968).Statistical theories of mental test scores.Reading, MA:Addison-Wesley.
21. Luecht, R. M.(1998).Computer-assisted test assembly using optimization heuristics.Applied Psychological Measurement,22(3),224-236.
22. Novoa, C.,Storer, R.(2009).An approximate dynamic programming approach for the vehicle routing problem with stochastic demands.European Journal of Operational Research,196(2),509-515.
23. Papadimitrion, C. H.,Steiglitz, K.(1982).Combinatorial optimization: algorithms and complexity.Englewood Cliffs, NJ:Prentice-Hall.
24. Qiu, A.,Rosenau, B. J.,Greenberg, A. S.,Barta, P.,Yantis, S.,Miller, M. I.(2006).Estimating linear cortical magnification in human primary visual cortex via dynamic programming.NeuroImage,31(1),125-138.
25. Rantzer, A.(2006).On relaxed dynamic programming in switching systems.IEE Proceedings on Control Theory and Applications,153(5),567-574.
26. Robinett III, R. D.,Wilson, D. G.,Eisler, G. R.,Hurtado, J. E.(2005).Applied dynamic programming for optimization of dynamical systems.Philadelphia, PA:Society for Industrial and Applied Mathematics.
27. Sanders, P. F.,Verschoor, A. J.(1998).Parallel test construction using classical item parameters.Applied Psychological Measurement,22(3),212-223.
28. Stocking, M. L.,Swanson, L.,Pearlman, M.(1993).Application of an automated item selection method to real data.Applied Psychological Measurement,17(2),167-176.
29. Sun, K. T.(2001).A greedy approach to test construction problems.Proceedings of the National Science Council (Part D): Mathematics, Science, and Technology Education,11(2),78-87.
30. Sun, K. T.,Chen, S. F.(1999).A study of applying the artificial intelligent technique to select test items.Psychological Testing,46(1),75-88.
31. Sun, K. T.,Chen, Y. J.,Tsai, S. Y.,Cheng, C. F.(2008).Creating IRT-based parallel test forms using the genetic algorithm method.Applied Measurement in Education,21(2),141-161.
32. Swanson, L.,Stocking, M. L.(1993).A model and heuristic for solving very large item selection problems.Applied Psychological Measurement,17(2),151-166.
33. Swanson, L.,Stocking, M. L.(1993).A method for severely constrained item selection in adaptive testing.Applied Psychological Measurement,17(3),277-292.
34. Tang, L.,Xuan, H.,Liu, J.(2007).Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling.Computers & Operations Research,34(9),2625-2636.
35. Theunissen, T. J. J. M.(1985).Binary programming and test design.Psychometrika,50,411-420.
36. van der Linden, W. J.(2005).A comparison of item-selection methods for adaptive tests with content constraints.Journal of Educational Measurement,42(3),283-302.
37. van der Linden, W. J.(1998).Optimal assembly of psychological and educational tests.Applied Psychological Measurement,22(3),195-211.
38. van der Linden, W. J.,Boekkooi-Timminga, E.(1989).A maximum model for test design with practical constraints.Psychometrika,54,237-247.
39. van der Linden, W. J.,Boekkooi-Timminga, E.(1988).A zero-one programming approach to Gulliksen's matched random subtests method.Applied Psychological Measurement,12(2),201-209.
40. van der Linden, W. J.,Breithaupt, K.,Chuah, S. C.,Zhang, Y.(2007).Detecting differential speededness in multistage testing.Journal of Educational Measurement,44(2),117-130.
41. van der Linden, W. J.,Reese, L. M.(1998).A model for optimal constrained adaptive testing.Applied Psychological Measurement,22(3),259-270.
42. Wang, C. S.,Ackerman, T.(1997).Two item selection algorithms for creating weakly parallel test forms using the IRT information functions.Psychological Testing,44(2),123-140.
43. Weiss, D. J.(1982).Improving measurement quality and efficiency with adaptive testing.Applied Psychological Measurement,6(4),379-396.