自動(dòng)組卷是網(wǎng)絡(luò)考試系統(tǒng)的核心功能，組卷成功與否決定了考試的質(zhì)量，遺傳加密算法以其自適應(yīng)全局尋優(yōu)、智能搜索和收斂速度快的特點(diǎn)，適宜于解決大范圍和復(fù)雜度高的問(wèn)題求解。

一、遺傳加密算法特點(diǎn)

遺傳算法借用了生物遺傳學(xué)的觀點(diǎn)，每個(gè)物種的特征均來(lái)自于該物種的基因排列，通過(guò)模擬自然進(jìn)化的遺傳、變異等機(jī)制，實(shí)現(xiàn)各個(gè)個(gè)體的適應(yīng)性的提高，這一點(diǎn)體現(xiàn)了自然界中“物競(jìng)天擇、適者生存”的進(jìn)化過(guò)程。

二、遺傳加密算法基本構(gòu)成要素

1、染色體編碼

在使用遺傳加密算法對(duì)一個(gè)問(wèn)題進(jìn)行求解之前，必須先對(duì)問(wèn)題的解空間進(jìn)行編碼，以實(shí)現(xiàn)解空間到遺傳加密算法搜索空問(wèn)的映射，編碼方法有二進(jìn)制編碼（SGA）、浮點(diǎn)數(shù)編碼、符號(hào)編碼等，選擇何種編碼方式有時(shí)對(duì)算法的性能和效率會(huì)產(chǎn)生很大的影響。

2、 群體數(shù)

群體數(shù)就是染色體個(gè)體的數(shù)目，群體數(shù)的多少對(duì)于搜索的效果有很大影響，群體數(shù)越多則參與搜索的染色體越多，從而有更大的機(jī)會(huì)得到最優(yōu)解，但是需要更多的搜索時(shí)間使得收斂速度降低，一般情況下，專(zhuān)家建議群體數(shù)為20—100。

3、適應(yīng)度函數(shù)　

遺傳加密算法是在適應(yīng)度函數(shù)的指導(dǎo)下進(jìn)行搜索，而不是窮舉式的全面搜索，適應(yīng)度函數(shù)評(píng)估是選擇操作的依據(jù)，各個(gè)個(gè)體適應(yīng)度的大小決定了它們繼續(xù)繁衍還是消亡，相當(dāng)于是自然界中各生物對(duì)環(huán)境適應(yīng)能力的大小。因此，適應(yīng)度函數(shù)的選取直接影響到遺傳算法的收斂性及收斂速度，對(duì)于提高遺傳加密算法的智能程度顯得尤為重要。

4、遺傳操作

（1）選擇　

選擇操作決定如何從當(dāng)前種群中選擇個(gè)體作為產(chǎn)生下一代種群的父代個(gè)體，選擇過(guò)程體現(xiàn)了生物進(jìn)化過(guò)程中“適者生存。優(yōu)勝劣汰”的思想。并且保證優(yōu)良基因遺傳給下一代個(gè)體。

（2）交叉

交叉算子是模仿自然界有性生殖的基因重組過(guò)程，其作用在于將原來(lái)的優(yōu)良基因遺傳給下一代個(gè)體，并生成包含更復(fù)雜基因結(jié)構(gòu)的新個(gè)體。

（3）變異　

變異操作模擬自然界生物體進(jìn)化過(guò)程中染色體上某位基因發(fā)生的突變現(xiàn)象，從而改變?nèi)旧w的結(jié)構(gòu)和物理形狀，變異可以引進(jìn)新的基因碼，增加新的參數(shù)搜索區(qū)域，避免陷入局部最優(yōu)解，因而可以搜索到整體最優(yōu)解。

5、最優(yōu)保存策略

選擇、交叉、變異操作后，再比較上下兩代最好個(gè)體的適應(yīng)度，如下降，則以上一代最好個(gè)體替換下一代的最差個(gè)體，反之則相反。

6、遺傳加密算法的步驟

步驟如下：

（1）初始化，產(chǎn)生足夠數(shù)量的個(gè)體，組成種群。

（2）迭代的執(zhí)行下述步驟：

a、計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值；

b、產(chǎn)生新的種群。

按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體；

按概率 進(jìn)行交叉操作；

按概率 進(jìn)行變異操作；

c、沒(méi)有滿(mǎn)足停止條件，則轉(zhuǎn)第a步；

（3）輸出種群中適應(yīng)度值最優(yōu)的染色體作為問(wèn)題的滿(mǎn)意解或最優(yōu)解。

三、遺傳加密算法的設(shè)計(jì)與實(shí)現(xiàn)

1、染色體編碼

本文采用了分段的浮點(diǎn)數(shù)編碼，染色體形如（a1,a2…an），其中a1表示試題庫(kù)中試題的題號(hào)，n為試卷要求的試題數(shù)，基因按照題型有序排序，并且將同類(lèi)型的試題放在同一個(gè)區(qū)間內(nèi)，如圖所示：

采用這種編碼，克服了標(biāo)準(zhǔn)二進(jìn)制編法方式占據(jù)存儲(chǔ)空間大和計(jì)算量大的特點(diǎn)，減少了解碼的過(guò)程，加快了進(jìn)化速度。

2、 初始化種群　

依據(jù)組卷要求從每一類(lèi)題型中隨機(jī)產(chǎn)生相應(yīng)數(shù)目的題號(hào)，按題型有序的存人個(gè)體的染色體中，保證同種題型的各題號(hào)必須相異，以免在同一份試卷中出現(xiàn)重復(fù)的試題，而且每個(gè)題號(hào)均在相應(yīng)題型的題號(hào)定義域中產(chǎn)生。

3、 適應(yīng)度函數(shù)的確定

在遺傳加密算法中，常以適應(yīng)度大小來(lái)區(qū)分群體中個(gè)體的優(yōu)劣，組卷時(shí)，個(gè)體的適應(yīng)度由章節(jié)比例、試　題難度、區(qū)分度來(lái)決定。

（1）章節(jié)比例的約束　

對(duì)相應(yīng)章節(jié)所占的分?jǐn)?shù)與用戶(hù)輸人值相減所得的絕對(duì)值求和再除總分，就得到章節(jié)比例不滿(mǎn)足命題要求的程度f(wàn)1。

其中s-num為章節(jié)的數(shù)目，apj為第j題的分值，si為第i章要求的章節(jié)比例，當(dāng)試題章節(jié)為i時(shí)，seci為1，否則為0，f1∈[0,1]越小說(shuō)明章節(jié)比例的約束滿(mǎn)足的越好，當(dāng)f1=0時(shí),完全滿(mǎn)足章節(jié)比例。

（2）難度級(jí)比例的約束　

對(duì)相應(yīng)難度級(jí)所占的分?jǐn)?shù)與用戶(hù)輸入值相減所得的絕對(duì)值求和再除總分，就得到難度級(jí)不滿(mǎn)足命題要求的程度f(wàn)2。

其中d-num為難度級(jí)的數(shù)目，f2∈[0,1]，f2越小說(shuō)明難度級(jí)比例的約束滿(mǎn)足的越好。

（3）區(qū)分度的約束

對(duì)試卷中所有試題求區(qū)分度和與用戶(hù)輸入值相減所得的絕對(duì)值再除總分，就得到區(qū)分度不滿(mǎn)足命題要求的程度f(wàn)3。

DIV為試卷要求的區(qū)分度,為第i題的區(qū)分度，f3∈[0,1]，f3越小說(shuō)明區(qū)分度的約束滿(mǎn)足的越好，當(dāng)f3=0時(shí),完全滿(mǎn)足該約束。

4、遺傳操作

（1）選擇

本文采用適應(yīng)度比例選擇方法，也叫輪盤(pán)賭方法，該方法根據(jù)每個(gè)個(gè)體的適應(yīng)度值計(jì)算其選擇概率。

首先計(jì)算種群個(gè)體適應(yīng)度的平均值，進(jìn)而可以計(jì)算群體中各個(gè)個(gè)體期望被選中的次數(shù)。

可以看出，個(gè)體適應(yīng)值越高，被選中的次數(shù)越多，這使得新種群的性能大大提高，通過(guò)選擇操作，保持了染色體的編碼規(guī)則，選中的個(gè)體被復(fù)制到下一代種群中，用來(lái)進(jìn)行后面的交叉。

（2）交叉　

采用單點(diǎn)交叉方式，具體操作是，從群體中隨機(jī)選擇2個(gè)染色體，對(duì)兩個(gè)配對(duì)個(gè)體的每一個(gè)基因，生成一個(gè)隨機(jī)數(shù)，如果小于交叉概率Pc。則交換該對(duì)基因同時(shí)如果交叉之后得到的染色體中存在同一題型中包含相同試題的情況，則不進(jìn)行交換。

（3）變異　

由于采用了實(shí)數(shù)編碼方式，普通的變異操作可能破壞試卷的題型順序，由此采用了均勻變異方法。其過(guò)程是，從群體中隨機(jī)選擇 1個(gè)染色體，對(duì)個(gè)體中的每一個(gè)基因，生成一個(gè)隨機(jī)數(shù)，如果小于變異概率Pm則從該基因所屬題型的定義域中隨機(jī)產(chǎn)生相異的題號(hào)替換原有基因。

5、最優(yōu)保存策略　

進(jìn)行選擇、交叉和變異操作后，比較新一代的最好個(gè)體與上一代的最好個(gè)體的適應(yīng)度值，如下降，則以上一代最好個(gè)體替換新一代的最差個(gè)體。

此策略可以保證迄今為止的最優(yōu)個(gè)體不會(huì)被交叉和變異等遺傳運(yùn)算破壞，它是遺傳加密算法收斂的一個(gè)重要保證條件。

本文利用遺傳加密算法的搜索空間大和收斂速度快的特點(diǎn)，設(shè)計(jì)了一種用于自動(dòng)組卷的智能加密算法，提高了組卷的效率和成功率，為智能組卷的實(shí)現(xiàn)提供了一種新途徑，要使自動(dòng)出題的誤差精度和收斂速度進(jìn)一步得到改進(jìn)，還需要進(jìn)行更深入的研究。

admin

收藏 海報(bào)分享