等質テスト構成における整数計画法を用いた最大クリーク探索の並列化

渕本 壱真  植野 真臣  

誌名
電子情報通信学会論文誌 D   Vol.J103-D   No.12   pp.881-893
発行日: 2020/12/01
早期公開日: 2020/08/05
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2020JDP7004
論文種別: 論文
専門分野: 教育工学
キーワード: 
eテスティング,  項目反応理論,  等質テスト自動構成,  最大クリーク問題,  整数計画法,  

本文: PDF(2.8MB)>>
論文を購入




あらまし: 
本論文では,等質テスト構成のための整数計画法を用いた最大クリークの並列化探索手法を提案する.等質テストとは各テストで出題される項目が異なるが,受験者得点の予測誤差が等質なテスト群である.等質テストでは同一能力の受験者が異なるテストを受験しても同一の得点となる保証があり,アイテムバンクから可能な限り多く生成することが望ましい.石井ら(2017)は等質テスト構成を最大クリーク問題と整数計画法により,従来手法より多くのテストを構成できる手法を提案した.本論文では,石井ら(2017)の手法で最も時間を要する整数計画法による逐次的頂点追加処理を並列化することを考える.具体的には,探索中のクリークの全頂点と隣接する頂点集合を候補頂点集合として,逐次的に整数計画法の解を追加し,要素数が一定となるまで並列化して繰り返し,この要素の最大クリークを追加することで探索を高速化できる.この提案手法の有効性は最大で従来手法で生成されるテスト数が194575個であったのに対し,438950個にテスト生成数を更新した.