改進和聲搜索算法的英語考試智能組卷策略①

霍小靜

(西安培華學院 人文與國際教育學院,西安 710125)

目前英語考試智能組卷多以計算機自動組卷技術(shù)為主,計算機自動組卷技術(shù)能夠按照用戶的組卷需求,在計算機題庫里選取英語試題構(gòu)建一套滿足用戶需求的英語試卷.計算機自動組卷技術(shù)能夠降低人力物力的投入,優(yōu)化英語考試組卷質(zhì)量與效率.

組卷問題屬于一類多目標優(yōu)化問題,研究一種滿足組卷需求的智能組卷方法,是完成計算機智能組卷的核心,存在一定研究價值.

諸多學者為了提高組卷的水平對此進行了研究,并取得了一定成果.例如,李瑞森等人[1]針對試題庫建設需求,提出了一種自底向上的試題庫建設方案,研究了試卷圖形化交互布局;杜明等人[2]針對信息化發(fā)展中在線試卷的組卷工作中存在的問題,設計了基于知識水平的改進智能遺傳組卷算法;此外,潘婷婷等人[3]研究了基于知識點權(quán)重與錯誤率關(guān)聯(lián)的個性化訓練模型,提高組卷水平.

和聲搜索算法能夠?qū)Χ嗄繕藘?yōu)化問題存在較好的求解功能,但是傳統(tǒng)的和聲搜索算法易進入局部最優(yōu),求解精度有待考證.為此,本文提出基于改進和聲搜索算法的英語考試智能組卷策略,該方法中采用的和聲搜索算法為離散和聲搜索算法,并對離散和聲搜索算法進行改進,使算法不易陷入局部最優(yōu).而且本文策略在求取英語考試智能組卷最優(yōu)解時,題庫試題質(zhì)量較好;并且在計算機自動組卷后,種群多樣性在組卷前期都較高,伴隨迭代次數(shù)增多,組卷后期本文策略種群多樣性快速降低,能夠快速獲取全局最優(yōu)解.

1 基于改進和聲搜索算法的英語考試智能組卷策略

1.1 英語考試智能組卷多目標優(yōu)化模型

將英語考試知識點屬性φ1(y)設成:

其中,組卷任務的英語試題總量是m,第j個英語試題涵蓋的知識點比例是是第j個英語試題涵蓋的知識點數(shù)目,Stotal是知識點的總數(shù)量.

難度屬性可以描述英語試題難度φ2(y):

其中,Q1、Q2分別是主觀類、客觀類英語試題的難度;高分組、低分組的得分均值依次是、;此英語試題的總分值與本試題答對的人數(shù)依次是U、G;參與英語考試的所有人數(shù)是P;組卷人設置的難度值是φ,φ值較大,英語試題難度較高;yj表示第j個試題的難度水平.

區(qū)分度屬性能夠判斷英語試題得分程度[4–6].區(qū)分度屬性設成φ3(y):

其中,是γ 組卷人設定的區(qū)分度值,其值越大,代表英語試題得分高低差距越顯著.

時間期望屬性能描述一套英語考試時間多少,英語考試完成時間與組卷設定的時間較為靠近,則英語考試智能組卷的時間質(zhì)量較優(yōu)[7].試卷時間期望屬性φ4(y)具體設定是:

其中,第j個英語試題耗費的期望時間是Hj,Hj值由組卷人設置;Htotal是整體測試時間.

為了優(yōu)化組卷質(zhì)量,構(gòu)建的模型需要以上述屬性為核心,構(gòu)建英語考試智能組多目標優(yōu)化函數(shù)是:

1.2 基于改進和聲搜索算法的組卷最優(yōu)解求解方法

英語考試智能組卷屬于離散問題,必須采用離散和聲搜索算法求解式(8),獲取組卷最優(yōu)方案[8,9].離散和聲搜索算法先初始化和聲記憶庫,各個組卷難度決策變量的值域設成組卷難度決策變量可能取值的數(shù)量設成L.在離散和聲搜索算法各次迭代時,對φ (y)進行求解,獲取智能組卷策略的可行解集合表示M個可行解.新的智能組卷策略可行解獲取方法是:

其中,rand表示[0 1]間的隨機數(shù),通過rand產(chǎn)生一個[0 1]間的隨機數(shù),然后將HMCR與該隨機數(shù)進行比較,根據(jù)比較結(jié)果產(chǎn)生新的新和聲.HMCR表示和聲記憶庫取值(題庫使用)概率.

調(diào)整和聲記憶庫(Harmony Memory,HM)中的新和聲:

其中,音調(diào)(英語試題)調(diào)整概率是PAR;h、n分別代表一維變量與組卷的干擾變量.若獲取的新和聲比HM中最劣和聲好,把最劣和聲換成新和聲.當?shù)螖?shù)達到最大值后,算法停止[10].

離散和聲搜索算法流程是:

(1)設定離散和聲搜索算法參數(shù):和聲記憶庫(題庫)的大小HMS、音調(diào)(英語試題)調(diào)整概率PAR、和聲記憶庫取值(題庫使用)概率HMCR與迭代次數(shù)最大值N.

(2)在組卷難度決策變量可能取值的整數(shù)區(qū)間中任意建立多個和聲,運算相應的和聲適應度值Ω (y1,y2),適應度值能夠體現(xiàn)題庫試題的優(yōu)劣,將和聲記憶庫實施初始化處理[11,12].

其中,y1、y2依次表示英語試卷第1 道題與第2 道題的優(yōu)劣變量.

(3)使用式(9)獲取一個新和聲.使用式(11)調(diào)整HM中新和聲.如果新和聲比HM中最劣和聲優(yōu),把最劣和聲換成新和聲,運算相應和聲適應度值,刷新HM.

(4)如果迭代次數(shù)為最大值,算法停止;反之回到第(2)步.

因為離散和聲搜索算法運行時,各次迭代僅可以使用和聲記憶庫的一個新和聲,新和聲與HM 里最劣的和聲相比之下,若新和聲比HM中最劣和聲優(yōu),把最劣和聲換成新和聲,實現(xiàn)HM 更新.此類方法屬于單個體更新處理,HM中的信息不能被充分使用,且算法具有非固定搜索屬性,獲取的智能組卷新解伴隨迭代次數(shù)的增多,難以存儲于和聲記憶庫中,和聲搜索算法的局部搜索性能將變差[13].為此,本文對此問題進行優(yōu)化,優(yōu)化模式如下:有和聲集合yj中建立一個相應的新和聲,通過優(yōu)勝劣汰的模式將和HM中最劣和聲實施更新.在HM 外隨機設定一個收斂因子vj,防止算法進入局部最佳,獲取的新解是:

(1)個性記憶考慮過程.在個體記憶考慮過程中可以全面使用HM中的全部積累信息.因為傳統(tǒng)和聲搜索算法是一種維記憶考慮模式,記憶僅對和聲的部分維而言具備有效性.本文中,個體記憶考慮過程需要將各個個體實施全局記憶考慮.部分維記憶的模式將有損于和聲信息的完整度,但個體記憶考慮過程對和聲信息的完整度不存在損壞[14].算法在各次迭代時,在已

其中,v1∈vj.若v1

(2)擾動搜索過程.擾動搜索過程為局部搜索,存在較顯著的局部搜索性能.能夠調(diào)整音調(diào),在小范圍中獲取和聲最優(yōu)解,不會進入局部最優(yōu)[15].

若新解屬于HM,使用音調(diào)調(diào)整概率PAR將ynew的各維變量實施調(diào)整搜索:

其中,v2∈vj,v3∈vj.

(3)競爭淘汰機制.因為更新HS是在新解與最劣解之間實現(xiàn)競爭更新,HM中信息更新效率低.為此改進和聲搜索算法使用競爭淘汰機制,將和聲記憶庫實施更新.在競爭淘汰機制里,各個新解與HM中相應的最劣解實施競爭.競爭淘汰機制可以提升HM中優(yōu)勝劣汰的速度,優(yōu)化單個個體與和聲庫的整體質(zhì)量,將新和聲實施優(yōu)劣評價,以此實現(xiàn)和聲記憶庫的更新.更新方法是:

使用此類競爭淘汰機制提高HM 全局往最優(yōu)解靠近的效率.

2 仿真實驗

為了測試本文基于改進和聲搜索算法的英語考試智能組卷策略對英語考試試卷的智能組卷有效性,以2019年遼寧省英語四級考試的試卷為例,該省相關(guān)組卷機構(gòu)使用計算機自動組卷系統(tǒng)進行智能組卷,在該系統(tǒng)中引入本文策略進行組卷.使用Java 語言編程進行程序編寫,實驗環(huán)境是Windows XP 系統(tǒng),處理器為851 MHz,內(nèi)存為64 MB.2019年某省英語四級考試的題庫里全部試題的知識點均值、難度均值、區(qū)分度均值依次設成0.65、0.52、0.63.

2.1 不同試卷期望時間下組卷效果分析

試卷分數(shù)總值是100 分,填空題分數(shù)是12 分,選擇題分數(shù)是32 分,名詞解釋分數(shù)是12 分,簡答題分數(shù)是22 分,綜合題分數(shù)是22 分.設定試卷預期完成3個時間段指標上下限值分別是30–60 min、61–90 min、91–120 min,3個時間段的組卷效果如圖1、圖2、圖3所示.組卷精度表示本文策略使用前后,計算機自動組卷40 次獲取組卷策略可行解的概率;最優(yōu)值、最劣值、均值依次是本文策略組卷40 次后,計算機自動組卷系統(tǒng)獲取可行解質(zhì)量的最優(yōu)值、最劣值、均值.圖1、圖2、圖3中,使用本文策略前,計算機自動組卷系統(tǒng)獲取3個時間段可行解的概率依次是0.86、0.99、0.91;本文策略使用后,計算機自動組卷獲取可行解的概率都是0.99.且本文策略使用后,計算機自動組卷40 次獲取可行解的最優(yōu)值、均值大于使用前.

圖1 30–60 min 試卷的組卷效果

圖2 61–90 min 試卷的組卷效果

2.2 試卷種群適應度分析

設定本文基于改進和聲搜索算法的英語考試智能組卷策略在求取英語考試智能組卷策略的最優(yōu)解時,和聲記憶庫中種群的個體數(shù)量都是100個,迭代次數(shù)為350 次.本文策略使用前后的適應度最大值如圖4所示.分析圖4可知,本文策略使用后的適應度最大值為0.70,使用前的適應度值是0.65,則使用本文策略求取英語考試智能組卷最優(yōu)解時,題庫的試題質(zhì)量較好.

圖3 91–120 min 試卷的組卷效果

圖4 種群適應度最大值

2.3 試卷種群多樣性分析

試卷種群的多樣性可表示題庫試題間的差異水平.試題差異較大,種群多樣性較高,否則,種群多樣性較低,試題差異較小.種群多樣性計算方法是:

其中,題庫中第j套智能組卷的最優(yōu)解種類均值為;h為維數(shù).

針對和聲搜索算法而言,種群的多樣性和算法的搜索性能存在直接影響,如果種群多樣性較大,算法的整體搜索性能較優(yōu),能夠探索未曾探索過的搜索范圍,用在本文研究內(nèi)容中,可理解成能夠獲取新題型.但是,若種群多樣性始終較大,獲取全局最優(yōu)解的難度便提升,因此在搜索開始階段,種群需要存在較好的種群多樣性,搜索后階段,為了得到準確的全局最優(yōu)解,種群需要往最優(yōu)解靠攏,種群的多樣性需要逐漸變小.

測試本文策略使用前后,計算機自動組卷系統(tǒng)智能組卷后的種群多樣性,設定需要組卷的試題時間分別是30–60 min、91–120 min,結(jié)果如圖5、圖6所示.分析圖5、圖6可知,英語考試時間存在約束時,本文策略使用下,計算機自動組卷后,種群多樣性在組卷前期都較高,伴隨迭代次數(shù)增多,組卷后期本文策略種群多樣性快速降低,能夠快速獲取全局最優(yōu)解.相比之下,使用本文策略后,計算機自動組卷性能較佳.

圖5 30–60 min 試卷的種群多樣性

圖6 91–120 min 試卷的種群多樣性

為了進一步證明本文策略的有效性,采用文獻[1]、文獻[2]策略與本文策略進行對比.對比方向為組卷精度以及組卷時間,比較結(jié)果分別如圖7、圖8所示.

根據(jù)圖7、圖8對比結(jié)果可以清晰看出,無論在50、100、150、200 還是250 次迭代次數(shù)中,本文策略的組卷精度明顯高于另外兩種策略,精度最高可達97%,而從組卷時間也可以看出,采用本文策略組卷的組卷時間明顯低于另外兩種方法,有效證明了本文策略的有效性.

圖7 不同策略組卷的精度對比

圖8 不同策略組卷的時間對比

3 結(jié)束語

以英語考試智能組卷這一問題為研究核心,提出基于改進和聲搜索算法的英語考試智能組卷策略.實驗結(jié)果表明,不同試卷期望時間下本文策略獲取英語考試智能組卷可行解的概率都是0.99,組卷精度較高;迭代次數(shù)是300 次時,本文策略適應度最大值為0.70,本文策略在求取英語考試智能組卷最優(yōu)解時,題庫試題質(zhì)量較好;本文策略使用下,計算機自動組卷后,種群多樣性在組卷前期都較高,伴隨迭代次數(shù)增多,組卷后期本文策略種群多樣性快速降低,能夠快速獲取全局最優(yōu)解.