計(jì)算機(jī)有關(guān)自動(dòng)機(jī)的論文

計(jì)算機(jī)有關(guān)自動(dòng)機(jī)的論文

　　自動(dòng)機(jī)原來(lái)是模仿人和動(dòng)物的行動(dòng)而做成的機(jī)器人的意思。但是現(xiàn)在已被抽象化為如下的機(jī)器。時(shí)間是離散的(t=0，1，2……)，在每一個(gè)時(shí)刻它處于所存在的有限個(gè)內(nèi)部狀態(tài)中的一個(gè)。對(duì)每一個(gè)時(shí)刻給予有限個(gè)輸入中的一個(gè)。那么下一個(gè)時(shí)刻的內(nèi)部狀態(tài)就由現(xiàn)在的輸入和現(xiàn)在的內(nèi)部狀態(tài)所決定。下面是學(xué)習(xí)啦小編給大家推薦的計(jì)算機(jī)有關(guān)自動(dòng)機(jī)的論文，希望大家喜歡!

　　計(jì)算機(jī)有關(guān)自動(dòng)機(jī)的論文篇一

　　《基于遺傳算法的自動(dòng)組卷系統(tǒng)設(shè)計(jì)》

　　摘要：自動(dòng)組卷系統(tǒng)是計(jì)算機(jī)輔助教學(xué)的重要組成部分，而遺傳算法以其全局尋優(yōu)和智能搜索的特性，得到了廣泛的運(yùn)用。根據(jù)自動(dòng)組卷系統(tǒng)的特點(diǎn)，將遺傳算法合理應(yīng)用于自動(dòng)組卷中，在遺傳算法中，設(shè)計(jì)了雙種群機(jī)制，并以試卷難度、試卷區(qū)分度、試卷的估計(jì)用時(shí)、知識(shí)點(diǎn)分布為基礎(chǔ)構(gòu)造適應(yīng)度函數(shù)，通過(guò)輪盤(pán)賭選擇方法、多點(diǎn)交叉和變異，較好地解決了自動(dòng)組卷的多重目標(biāo)尋優(yōu)問(wèn)題。

　　關(guān)鍵詞：自動(dòng)組卷;遺傳算法;適應(yīng)度函數(shù)

　　0引言

　　考試是教學(xué)過(guò)程中的一個(gè)重要環(huán)節(jié)，我們用它來(lái)檢測(cè)教學(xué)效果，以期提高教學(xué)質(zhì)量。傳統(tǒng)的手工方式，都是以教師的經(jīng)驗(yàn)與知識(shí)的積累為依據(jù)出題，帶有一定的主觀性，考試命題質(zhì)量和科學(xué)性不能保證。另外，對(duì)于有些課程，我們希望平時(shí)能夠在計(jì)算機(jī)機(jī)房通過(guò)上機(jī)完成測(cè)驗(yàn)。所以，伴隨人工智能的廣泛應(yīng)用，自動(dòng)組卷技術(shù)成為我們必須深入探討的一個(gè)課題。現(xiàn)有不少自動(dòng)組卷系統(tǒng)，但其算法存在時(shí)間復(fù)雜度和空間復(fù)雜度偏大、程序結(jié)構(gòu)復(fù)雜、試題缺乏隨機(jī)性等缺陷\[1\]。將遺傳算法應(yīng)用于自動(dòng)組卷系統(tǒng)中，并將試卷難度、試卷區(qū)分度、試卷的估計(jì)用時(shí)、知識(shí)點(diǎn)分布作為綜合優(yōu)化目標(biāo)，對(duì)上述缺陷作出了改進(jìn)。

　　1基于遺傳算法的自動(dòng)組卷算法設(shè)計(jì)

　　遺傳算法的操作步驟為編碼、隨機(jī)產(chǎn)生初始種群、構(gòu)建適應(yīng)度函數(shù)、對(duì)初始種群迭代執(zhí)行選擇、交叉、變異等遺傳操作產(chǎn)生下一代種群，獲取最優(yōu)解、解碼\[2\]。本自動(dòng)組卷算法設(shè)計(jì)如下。

　　1.1編碼設(shè)計(jì)

　　整數(shù)編碼直接采用解空間的形式進(jìn)行編碼，意義明確，易于引入特定領(lǐng)域的信息，而且能大大縮短串長(zhǎng)，遺傳操作無(wú)須頻繁地編碼、解碼，改善了遺傳算法的計(jì)算復(fù)雜性，提高了算法效率\[3\]。本算法采用整數(shù)編碼將現(xiàn)實(shí)問(wèn)題映射到染色體即個(gè)體形式。

　　實(shí)現(xiàn)時(shí)，按試卷的題型對(duì)個(gè)體進(jìn)行分段編碼。比如試卷由L種題型的試題組成，則染色體編碼劃分成L個(gè)子段，每個(gè)子段對(duì)應(yīng)一種題型。每個(gè)子段中基因個(gè)數(shù)為該題型要求的題目個(gè)數(shù)。

　　試題庫(kù)中每道題目，都有一個(gè)編號(hào)與其對(duì)應(yīng)。比如現(xiàn)在生成了兩張?jiān)嚲韨€(gè)體ExaPaper1、ExaPaper2。分別由選擇、填空、判斷、問(wèn)答、綜合5道題組成。

　　1.2產(chǎn)生兩個(gè)初始種群

　　在初始種群產(chǎn)生時(shí)，應(yīng)采用某種算法，使優(yōu)秀、中等的、劣質(zhì)的個(gè)體基本同概率存在。以保證初始種群產(chǎn)生的多樣性和分布均勻性。并且采用產(chǎn)生2個(gè)初始種群的方法，同時(shí)對(duì)解空間內(nèi)多個(gè)區(qū)域進(jìn)行搜索，并互相交流信息。這種設(shè)置方法，雖然每次需執(zhí)行與種群規(guī)模n成2倍的計(jì)算量，但實(shí)質(zhì)上可進(jìn)行大約O (n\+3)個(gè)解的有效搜索。因此，這種2種群的設(shè)置方法，成本雖提高一倍，效率則以指數(shù)形式上升。

　　實(shí)現(xiàn)時(shí)，本算法采用隨機(jī)的方法產(chǎn)生320個(gè)個(gè)體，將他們分為40個(gè)子空間，則每個(gè)子空間中有8個(gè)個(gè)體。然后從每個(gè)子空間中隨機(jī)獲取5個(gè)個(gè)體，這樣就形成了200個(gè)個(gè)體，對(duì)這200個(gè)個(gè)體再隨機(jī)劃分到兩個(gè)初始種群中。

　　1.3構(gòu)造適應(yīng)度函數(shù)

　　一份卷子設(shè)計(jì)是否合理，通常從3個(gè)方面考察：第一，題型比例配置是否適當(dāng);第二，題目難、中、易比例是否合理;第三，干擾項(xiàng)是否有效，能不能反映考生的典型錯(cuò)誤。本算法將試卷難度、試卷區(qū)分度、試卷的估計(jì)用時(shí)、知識(shí)點(diǎn)分布4個(gè)目標(biāo)作為綜合優(yōu)化目標(biāo)，因此也將其作為構(gòu)造適應(yīng)度函數(shù)的主要依據(jù)。適應(yīng)度函數(shù)的構(gòu)造過(guò)程為，首先以各目標(biāo)為基礎(chǔ)分別構(gòu)造各自的目標(biāo)函數(shù)，然后使用加權(quán)的方法對(duì)各目標(biāo)函數(shù)進(jìn)行組合獲得適應(yīng)度函數(shù)。

　　1.3.1各目標(biāo)函數(shù)構(gòu)造

　　(1)試卷難度目標(biāo)函數(shù)。

　　針對(duì)不同的考生，試卷難度要求也不同，因此將試卷難度作為構(gòu)造適應(yīng)度函數(shù)的一個(gè)依據(jù)。

　　Fc(X)=1-1[]total_score∑N[]i=1fc(i)*p(i)-Exp_Difficulty(1)

　　其中，X為種群中個(gè)體，N為X的長(zhǎng)度，i表示X中第i個(gè)位置。對(duì)應(yīng)到自動(dòng)組卷中，N為題目的個(gè)數(shù)，total_score為試卷的總分，i表示X這份試卷中第幾道題目。f\-c(i)為i這道題目對(duì)應(yīng)的難易度，p(i)為這道題目對(duì)應(yīng)的分值。Exp_Difficulty為對(duì)試卷的難度期望值。由此可知，F(xiàn)\-c(X)值越大，說(shuō)明試卷難度符合要求的可能性越大。

　　(2)試卷區(qū)分度目標(biāo)函數(shù)、試卷估計(jì)用時(shí)目標(biāo)函數(shù)。

　　區(qū)分度是指試題對(duì)被試者情況的分辨能力的大小。區(qū)分度適當(dāng)?shù)脑嚲砟馨褍?yōu)秀、一般、差三個(gè)層次的學(xué)生真正區(qū)分開(kāi)。試卷區(qū)分度目標(biāo)函數(shù)、試卷估計(jì)用時(shí)目標(biāo)函數(shù)構(gòu)造方法與試卷難度目標(biāo)函數(shù)構(gòu)造方法類似。試卷區(qū)分度目標(biāo)函數(shù)構(gòu)造如式(2)所示。

　　Fd(X)=1-1[]total_score∑N[]i=1fd(i)*p(i)-Exp_Difficulty(2)

　　其中，X為種群中個(gè)體，N為X的長(zhǎng)度，i表示X中第i個(gè)位置。對(duì)應(yīng)到自動(dòng)組卷中，N為題目的個(gè)數(shù)，f\-d(i)為i這道題目對(duì)應(yīng)的區(qū)分度，p(i)為這道題目對(duì)應(yīng)的分值。total_score為試卷總分值。Exp_Different為對(duì)試卷的區(qū)分度的望值。由此可知，F(xiàn)\-d(X)值越大，說(shuō)明試卷難度符合要求的可能性越大。

　　試卷估計(jì)用時(shí)目標(biāo)函數(shù)構(gòu)造如式(3)、式(4)所示。

　　Ft(X)=T(X)T(X)<11[]T(X)T(X)>1(3)

　　T(X)=∑N[]i=1ft(i)[]Exp_Time(4)

　　其中，X為種群中個(gè)體，N為X的長(zhǎng)度i表示X中第i個(gè)位置。對(duì)應(yīng)到自動(dòng)組卷中，N為題目的個(gè)數(shù)，f\-t(i)為完成i這道題目的期望時(shí)間。Exp_Time為完成本試卷估計(jì)用時(shí)的期望值。由此可知，F(xiàn)\-t(X)值越大，說(shuō)明試卷難度符合要求的可能性越大。

　　(3)知識(shí)點(diǎn)分布目標(biāo)函數(shù)。

　　教學(xué)大綱中，對(duì)不同章節(jié)知識(shí)點(diǎn)的掌握程度要求也不同。因此，設(shè)計(jì)知識(shí)點(diǎn)分布目標(biāo)函數(shù)，用來(lái)把握考察的知識(shí)點(diǎn)是否全面合理。

　　知識(shí)點(diǎn)分布目標(biāo)函數(shù)構(gòu)造如式(5)、式(6)所示。

　　Fn(X)=(∑M[]j=1fw(j)*∑N[]i=1Fs(i))/total_score(5)

　　Fs(i)=fs(i)第i題目屬于第j章內(nèi)容0第i題目不屬于第j章內(nèi)容(6)

　　其中，X為種群中個(gè)體，N為X的長(zhǎng)度，i表示X中第i個(gè)位置。對(duì)應(yīng)到自動(dòng)組卷中，M為本試卷要考察到的章節(jié)總數(shù)。fw(j)為課本第j章在試卷中占用的權(quán)重。N為題目的個(gè)數(shù)，fs(j)為第i題目的分值。若第i題目是第j章節(jié)的內(nèi)容，F(xiàn)\-s(i)才存儲(chǔ)f\-s(i)的值，以便參與實(shí)際試卷中第j章節(jié)權(quán)重的計(jì)算。total_score為試卷總分值。由此可知，F(xiàn)\-n(X)值越大，說(shuō)明試卷難度符合要求的可能性越大。

　　1.3.2適應(yīng)度函數(shù)構(gòu)造

　　使用加權(quán)的方法對(duì)各目標(biāo)函數(shù)進(jìn)行組合，形成適應(yīng)度函數(shù)。適應(yīng)度函數(shù)如式(7)所示：

　　F(X)=1Fc(X)+2Fd(X)+3Ft(X)+4Fn(X)(7)

　　其中，F(xiàn)\-c(X)、F\-d(X)、F\-t(X)、F\-n(X)分別為試卷難度、試卷區(qū)分度、試卷的估計(jì)用時(shí)、知識(shí)點(diǎn)分布的目標(biāo)函數(shù)。1、2、3、4分別為試卷難度、試卷區(qū)分度、試卷的估計(jì)用時(shí)、知識(shí)點(diǎn)分布目標(biāo)函數(shù)的權(quán)值。并且1+2+3+4=1。權(quán)值1、2、3、4的取值應(yīng)依據(jù)具體試卷考核目標(biāo)而定。

　　1.4遺傳操作

　　1.4.1選擇操作設(shè)計(jì)

　　在本算法中，應(yīng)用輪盤(pán)賭選擇方法進(jìn)行選擇操作，決定將哪些個(gè)體復(fù)制到新種群中\(zhòng)[4\]。并進(jìn)一步根據(jù)適應(yīng)度值對(duì)t+1代和t代種群最優(yōu)個(gè)體進(jìn)行比較及選取，確保在t+1種群中，最優(yōu)個(gè)體的適應(yīng)度并不低于t種群的最優(yōu)個(gè)體適應(yīng)度。

　　1.4.2交叉操作設(shè)計(jì)

　　本文使用多點(diǎn)交叉操作。針對(duì)兩個(gè)個(gè)體即兩份試卷中的選擇、填空、判斷、問(wèn)答、綜合5類題型，分別進(jìn)行20%的基因點(diǎn)交叉。比如假設(shè)生成了表3、表4所示兩份試題。黑邊框處為交叉點(diǎn)。交叉操作后，試卷1、卷2轉(zhuǎn)換為表5、表6所示內(nèi)容。

　　1.4.3變異操作設(shè)計(jì)

　　變異操作為對(duì)群體中某些個(gè)體的基因進(jìn)行小概率擾動(dòng)。本變異的操作如下：以題型為基礎(chǔ)，將個(gè)體分段，每段隨機(jī)選擇一個(gè)變異位置，并從同題型題庫(kù)中隨機(jī)選擇一個(gè)題目替換該變異位置題目，條件是新選的題目不能與當(dāng)前試卷中同題型其它題目重復(fù)。

　　1.4.4種群競(jìng)爭(zhēng)設(shè)計(jì)

　　本算法采用產(chǎn)生2個(gè)初始種群的方法，同時(shí)對(duì)解空間內(nèi)多個(gè)區(qū)域進(jìn)行搜索，并互相交流信息。種群競(jìng)爭(zhēng)的具體設(shè)計(jì)思想為：對(duì)兩個(gè)初始種群K11、K21分別進(jìn)行遺傳操作產(chǎn)生新的種群，各經(jīng)過(guò)T代(不同問(wèn)題T的設(shè)定不同)后，獲取到新種群K1T、K2T。將K1T、K2T兩個(gè)種群中個(gè)體合并，按適應(yīng)度排序。前一半個(gè)體形成新的K1T種群，后一半個(gè)體形成新的K2T種群。將新K1T、K2T再反復(fù)執(zhí)行上述過(guò)程，直到滿足終止條件時(shí)進(jìn)化結(jié)束。本算法的終止條件是當(dāng)達(dá)到規(guī)定的最大迭代次數(shù)HMAX或者最好個(gè)體的適應(yīng)度函數(shù)值HMAX/5次達(dá)到了要求。

　　1.5選擇最優(yōu)解及解碼

　　通過(guò)遺傳算法最終可獲得一組個(gè)體，對(duì)這組個(gè)體分別計(jì)算適應(yīng)度值，獲取適應(yīng)度最優(yōu)的個(gè)體，作為最終解。因?yàn)槭钦麛?shù)編碼，個(gè)體中基因值即為題庫(kù)中被選中題的題號(hào)。因此，從最優(yōu)個(gè)體可直接得到最終生成的試卷。

　　2結(jié)語(yǔ)

　　本文圍繞自動(dòng)組卷存在的問(wèn)題，重點(diǎn)研究了遺傳算法的改進(jìn)及其在自動(dòng)組卷算法中的應(yīng)用。通過(guò)運(yùn)行基于該遺傳算法的組卷程序，證明了該設(shè)計(jì)的可行性、有效性。

　　參考文獻(xiàn)：

　　[1]黎軍.基于遺傳算法的自動(dòng)組卷設(shè)計(jì)[J].電腦學(xué)習(xí)，2009(3).

　　[2]陳國(guó)良，王煦法，莊鎮(zhèn).遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996.

　　[3]張超群，鄭建國(guó)，錢(qián)潔.遺傳算法編碼方式比較[J].計(jì)算機(jī)應(yīng)用，2011(3).

　　[4]丁承層，強(qiáng)傳生，張輝.遺傳算法縱橫談[J].信息與控制，1997(1).

　　計(jì)算機(jī)有關(guān)自動(dòng)機(jī)的論文篇二

　　《基于改進(jìn)遺傳算法的自動(dòng)組卷研究》

　　摘要：通過(guò)詳細(xì)分析試卷的各項(xiàng)約束條件，建立了一個(gè)以知識(shí)點(diǎn)、難度系數(shù)、區(qū)分度等為核心屬性的自動(dòng)組卷數(shù)學(xué)模型，并利用改進(jìn)的遺傳算法實(shí)現(xiàn)了自動(dòng)組卷。

　　關(guān)鍵字：自動(dòng)組卷;數(shù)學(xué)模型;遺傳算法

　　自動(dòng)組卷就是根據(jù)用戶的要求，采用一定的算法自動(dòng)地從試題庫(kù)中抽取一定數(shù)量的試題組成試卷。自動(dòng)組卷算法的好壞直接影響到試卷的質(zhì)量，如何從試題庫(kù)中選出試題組成符合用戶要求的試卷，并使組卷具有較高的效率和成功率是當(dāng)前研究的熱門(mén)課題。現(xiàn)有的自動(dòng)組卷算法一般有三種：隨機(jī)選取法、回溯試探法和遺傳算法。遺傳算法是一種新發(fā)展起來(lái)的并行優(yōu)化算法，它很適合解決自動(dòng)組卷問(wèn)題。

　　1 試題核心屬性的確定

　　在自動(dòng)組卷系統(tǒng)中，一些試題庫(kù)設(shè)置了試題的各類屬性，如章節(jié)、層次、要求、題型、難度系數(shù)、難度級(jí)別、各章節(jié)分值等屬性，其實(shí)過(guò)多的屬性會(huì)增加實(shí)際組卷的難度，降低效率。以教育學(xué)理論為指導(dǎo)，選擇以下屬性作為試題的核心屬性。

　　(1) 題號(hào)。試題的編號(hào)，用來(lái)唯一標(biāo)識(shí)試題。

　　(2) 題型。試題的類型。

　　(3) 知識(shí)點(diǎn)。某道題屬于某門(mén)課程的哪個(gè)知識(shí)點(diǎn)，知識(shí)點(diǎn)的設(shè)置不以章節(jié)為依據(jù)，從而可以避免教材的不同對(duì)組卷造成影響。

　　(4) 難度系數(shù)。難度系數(shù)[1]是表示某一試題的難易程度，通常用未通過(guò)率來(lái)表示，即一次考試中未答對(duì)某道試題的考生數(shù)在其總體中所占的比例。一般來(lái)說(shuō)，難度系數(shù)值為0.5時(shí)，是中等難度，如果小于0.3試題太簡(jiǎn)單，如果大于0.7試題太難，對(duì)考生都會(huì)做或都不會(huì)做(難度系數(shù)為0或?yàn)?)的試題，屬于無(wú)意義的試題，必須淘汰。

　　(5) 區(qū)分度。區(qū)分度[2]是指某道題對(duì)不同水平考生加以區(qū)分的能力。區(qū)分度高的試題，對(duì)學(xué)生水平有較好的鑒別力。區(qū)分度的計(jì)算公式為：

　　其中，B表示試題的區(qū)分度，H表示樣本中高分組在某題上所得的平均分，L表示樣本中低分組在某題上所得的平均分，K表示某題滿分。高分組和低分組一般各占樣本的25%～30%，最好取27%。一般來(lái)說(shuō)，試題的區(qū)分度在0.4以上就被認(rèn)為是很好的。在0.3～0.39之間，認(rèn)為良好;在0.2～0.29之間，認(rèn)為可以;在0.19以下，認(rèn)為差，必須淘汰或加以修改。對(duì)在校學(xué)生的達(dá)標(biāo)考試，試卷的區(qū)分度不宜太高，因?yàn)樗皇沁x拔性質(zhì)的考試。但也不能過(guò)低，否則對(duì)學(xué)生的鑒別效果差，不能很好的達(dá)到考試的目的。一般區(qū)分度控制在0.2～0.3之間為宜。

　　(6) 分值。某小題的分?jǐn)?shù)。

　　(7) 答題時(shí)間。完成某題估計(jì)所需的時(shí)間。

　　2 自動(dòng)組卷數(shù)學(xué)模型的建立

　　自動(dòng)組卷中決定一道試題，其實(shí)就是決定一個(gè)包含題號(hào)、題型、知識(shí)點(diǎn)、難度系數(shù)、區(qū)分度、分值、答題時(shí)間的七維向量(a 1，a 2，a 3， a4，a 5，a 6，a 7)。假設(shè)一套試卷中包含n道試題，一套試卷就決定了一個(gè)n×7的矩陣S：

　　這就是問(wèn)題求解中的目標(biāo)矩陣，其中a i1 、a i2 、 a i3 、a i4、a i5、 a i6 、a i7分別表示試卷中第i道題的題號(hào)、題型、知識(shí)點(diǎn)、難度系數(shù)、區(qū)分度、分值、答題時(shí)間。從矩陣S可以看出組卷問(wèn)題是一個(gè)多重約束目標(biāo)的問(wèn)題求解，且目標(biāo)狀態(tài)不是唯一的。

　　在實(shí)際組卷時(shí)，用戶會(huì)對(duì)試卷提出多方面的要求，用戶的每一個(gè)要求對(duì)應(yīng)試卷的一個(gè)約束條件。要組成一份符合要求的、高質(zhì)量的試卷，目標(biāo)矩陣的分布要滿足以下試卷約束條件。

　　(1) 試卷中包含的題型以及每種題型的題量要與用戶的設(shè)置相符。

　　k種題型的題量=

　　(2) 試卷中包含知識(shí)點(diǎn)即考核知識(shí)點(diǎn)以及各考核知識(shí)點(diǎn)所占分?jǐn)?shù)的比例要與用戶設(shè)置相符。

　　K種考核知識(shí)點(diǎn)所占分?jǐn)?shù)=

　　(3) 試卷的難度系數(shù)要滿足用戶的要求，試卷的難度系數(shù)一般用試卷中每道試題的難度系數(shù)的加權(quán)平均來(lái)計(jì)算。

　　即：試卷的難度系數(shù)=

　　(4) 試卷的區(qū)分度要滿足用戶的要求，試卷的區(qū)分度一般用試卷中每道試題的區(qū)分度的加權(quán)平均來(lái)計(jì)算。

　　即：試卷的區(qū)分度=

　　(5) 試卷的總分要與設(shè)置相符。

　　即：試卷的總分=

　　(6) 試卷的總答題時(shí)間要與用戶設(shè)置相符。

　　即：試卷的總答題時(shí)間=

　　在實(shí)際組卷時(shí)，試卷的總分、考核知識(shí)點(diǎn)、各題型每小題分值、試卷中包含的題型、各題型的題量都應(yīng)該是精確達(dá)到的。試卷中各考核知識(shí)點(diǎn)所占的分?jǐn)?shù)、試卷的難度系數(shù)、區(qū)分度和試卷的總答題時(shí)間這四個(gè)約束條件可以存在一定的誤差。誤差的大小由用戶的期望值和各約束條件的重要性決定。在實(shí)際應(yīng)用中，各約束條件的重要性是不同的，因此，目標(biāo)函數(shù)就取各項(xiàng)誤差的加權(quán)和。目標(biāo)函數(shù)f可以表示為：

　　為了不至于各項(xiàng)誤差相互抵消，實(shí)際值與用戶要求值的誤差都取絕對(duì)值。其中，試卷中各考核知識(shí)點(diǎn)所占的分?jǐn)?shù)和試卷的總答題時(shí)間這兩項(xiàng)的誤差為實(shí)際值與用戶要求值的誤差絕對(duì)值與用戶要求值的比，試卷的難度系數(shù)和區(qū)分度這兩項(xiàng)的誤差為實(shí)際值與用戶要求值的誤差的絕對(duì)值。w i表示第i個(gè)約束條件的權(quán)值，w i通常由專家經(jīng)驗(yàn)或試驗(yàn)給出，0≤w i ≤1。由上式可知，目標(biāo)函數(shù)f的值越小，即誤差越小，問(wèn)題的解越優(yōu)，即生成的試卷越接近用戶的需求。

　　3 遺傳算法

　　遺傳算法[3，4，5]是以適應(yīng)度函數(shù)(或目標(biāo)函數(shù))為依據(jù)，通過(guò)對(duì)群體中的個(gè)體進(jìn)行遺傳操作實(shí)現(xiàn)群體內(nèi)個(gè)體結(jié)構(gòu)重組的迭代處理過(guò)程。在這一過(guò)程中，群體中的個(gè)體一代一代地得以優(yōu)化，并逐漸地逼近最優(yōu)解，最終獲得最優(yōu)解。傳統(tǒng)遺傳算法的主要步驟包括初始染色體群體生成、適應(yīng)度評(píng)估和檢測(cè)、選擇操作、交叉操作和變異操作。傳統(tǒng)遺傳算法流程圖如圖1所示(其中t為進(jìn)化代數(shù)，t0為最大進(jìn)化代數(shù))。

　　4 基于改進(jìn)遺傳算法的自動(dòng)組卷

　　傳統(tǒng)的遺傳算法采用二進(jìn)制編碼，用1表示某題被選中，0表示某題沒(méi)有被選中，這種編碼非常簡(jiǎn)單，但在進(jìn)行交叉和變異操作時(shí)，各題型的題量很難控制，而且當(dāng)試題庫(kù)題量很大時(shí)編碼很長(zhǎng)。傳統(tǒng)的遺傳算法以進(jìn)化代數(shù)等于最大進(jìn)化代數(shù)作為終止條件，但是在實(shí)際組卷過(guò)程中并不知道種群進(jìn)化到第幾代就能得到試卷的最優(yōu)組合。因此用遺傳算法實(shí)現(xiàn)自動(dòng)組卷時(shí)，要對(duì)傳統(tǒng)遺傳算法進(jìn)行一些改進(jìn)。

　　4.1 改進(jìn)的遺傳算法

　　4.1.1 染色體編碼

　　通過(guò)對(duì)編碼的大量分析，提出了一種分段實(shí)數(shù)編碼機(jī)制，首先將染色體分成若干段，每一段對(duì)應(yīng)一種題型，組成試卷的各道試題題號(hào)直接映射為基因，編碼時(shí)將同一題型的試題放在同一段，同一段內(nèi)題號(hào)各不相同。以題號(hào)編碼的方法所表達(dá)的意義清楚、明確、不需解碼，從而可以提高算法性能，提高運(yùn)算效率。而且交叉和變異操作都在各段內(nèi)部進(jìn)行，因此可以保證組卷過(guò)程中各題型題量的正確匹配。

　　4.1.2 適應(yīng)度函數(shù)設(shè)計(jì)遺傳算法在進(jìn)化搜索中僅以適應(yīng)度函數(shù)為依據(jù)，利用種群中每個(gè)個(gè)體的適應(yīng)度值來(lái)進(jìn)行搜索。因此，適應(yīng)度函數(shù)的選擇至關(guān)重要，一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的。上面提出的自動(dòng)組卷模型是最小化問(wèn)題，采用如下方法可將目標(biāo)函數(shù)f轉(zhuǎn)換成適應(yīng)度函數(shù)F。

　　由上式可知，F(xiàn)的取值范圍為0～1，適應(yīng)度函數(shù)F的值越大，說(shuō)明個(gè)體越好，個(gè)體越接近問(wèn)題的最優(yōu)解。

　　4.1.3 初始化染色體群體

　　隨機(jī)生成初始染色體群體，在初始染色體群體中，染色體的長(zhǎng)度為n，群體的大小為m，m太小時(shí)，難以求出最優(yōu)解，太大時(shí)則增長(zhǎng)收斂時(shí)間。群體的大小一般根據(jù)需要，按經(jīng)驗(yàn)或試驗(yàn)給出，一般m=30～160。

　　4.1.4 遺傳算子

　　(1) 選擇算子

　　在遺傳操作中，為了保留較優(yōu)的個(gè)體，以概率1完全地復(fù)制每一代群體中按適應(yīng)度值從大到小依次排列的前面2個(gè)個(gè)體。為了保持群體大小不變，同時(shí)刪除適應(yīng)度排列的后面的2個(gè)個(gè)體。然后從排列在前面的m-2個(gè)個(gè)體中隨機(jī)抽取p(p≤m-2)個(gè)個(gè)體進(jìn)行交叉和變異操作。這種選擇策略使得適應(yīng)度小的個(gè)體也有可能被選中，這樣有助于增加下一代群體的多樣性。

　　(2) 交叉算子

　　在遺傳操作中，采用了分段的思想，交叉的時(shí)候按題型段進(jìn)行交叉，因此交叉后不存在段內(nèi)試題重復(fù)的問(wèn)題，也不會(huì)改變每種題型的題量。交叉概率p c太小時(shí)難以向前搜索，太大時(shí)則容易破壞高適應(yīng)度的結(jié)構(gòu)。一般p c=0.4～0.6。 (3)變異算子在遺傳操作中，變異在染色體的題型段內(nèi)進(jìn)行。變異概率p m太小時(shí)難以產(chǎn)生新的基因結(jié)構(gòu)，太大時(shí)使遺傳算法成了單純的隨機(jī)搜索。一般p m=0.01～0.2。

　　4.1.5 終止條件

　　在改進(jìn)的遺傳算法中，設(shè)置了期望適應(yīng)度值，把每一代計(jì)算出來(lái)的最高適應(yīng)度個(gè)體的適應(yīng)度值與期望適應(yīng)度值相比較，當(dāng)適應(yīng)度最高的個(gè)體的適應(yīng)度值大于或等于期望適應(yīng)度值時(shí)則停止進(jìn)化，否則繼續(xù)進(jìn)行遺傳操作、計(jì)算適應(yīng)度值、反復(fù)迭代直到組卷成功。

　　4.2 主要算法描述

　　基于改進(jìn)遺傳算法的自動(dòng)組卷的主要算法描述如算法1所示。

　　算法1：

　　int GJGA(p c，p m，m，f0)

　　{

　　t=0;

　　initialize(p(t));//隨機(jī)產(chǎn)生初始染色體群體

　　計(jì)算初始染色體群體的適應(yīng)度值;

　　while (maxf

　　{

　　selection(p(t));//選擇操作

　　crossover(p(t));//交叉操作

　　mutation(p(t));//變異操作

　　得到下一代染色體群體q(t+1)，計(jì)算下一代染色體群體的適應(yīng)度值;

　　t++;

　　}

　　輸出當(dāng)前染色體群體中適應(yīng)度最高的染色體;

　　}

　　4.3 遺傳算法復(fù)雜度分析

　　在遺傳算法中，絕大部分處理都集中在適應(yīng)度的計(jì)算上，因此可以用計(jì)算個(gè)體適應(yīng)度操作的時(shí)間復(fù)雜度作為算法的時(shí)間量度。遺傳算法的時(shí)間復(fù)雜度為O(t*m*n)。因?yàn)樵囶}庫(kù)中的題量一般都很大，所以改進(jìn)后的遺傳算法的時(shí)間復(fù)雜度一般要比傳統(tǒng)遺傳算法的時(shí)間復(fù)雜度小。遺傳算法的空間復(fù)雜度可以用初始染色體群體所占的空間來(lái)衡量，遺傳算法的空間復(fù)雜度為O(m*n)。因?yàn)楦倪M(jìn)后的遺傳算法的染色體的長(zhǎng)度遠(yuǎn)比傳統(tǒng)遺傳算法的染色體的長(zhǎng)度小，所以改進(jìn)后的遺傳算法的空間復(fù)雜度遠(yuǎn)比傳統(tǒng)遺傳算法空間復(fù)雜度小。

　　5 結(jié)論

　　算法的改進(jìn)往往不能顧及問(wèn)題每一個(gè)方面，如果算法設(shè)計(jì)的核心是提高解的精度，則算法可能在搜索范圍和搜索精度上花去更多的時(shí)間，如果算法的設(shè)計(jì)主要在于盡快收斂，得到結(jié)果，則在解的精度上考慮很少，算法往往側(cè)重于減少進(jìn)化代數(shù)。改進(jìn)后的遺傳算法使生成試卷的質(zhì)量得到了保證，但要使組卷的收斂速度得到進(jìn)一步改進(jìn)，還需進(jìn)一步研究。

　　參考文獻(xiàn)

　　[1] 文海英. 智能型試卷自動(dòng)生成系統(tǒng)中試卷難度控制技術(shù)的研究(J).湖南科技學(xué)院學(xué)報(bào)，2005，26(5)：153-156

　　[2] 常振江. 學(xué)生成績(jī)分布與一種簡(jiǎn)便的評(píng)估試卷命題質(zhì)量的方法(J). 遼寧師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2003，26(1)：109-112

　　[3] 丁衛(wèi)平. 基于遺傳算法的智能組卷應(yīng)用研究.電氣電子教學(xué)學(xué)報(bào)(J)，2005，27(2)：93-95

　　[4] 朱黎明. 基于單親遺傳算法的試題生成及其應(yīng)用研究(D). 長(zhǎng)沙：湖南大學(xué)，2005

　　[5] T.Lynda，C.Chrisment，Boughanem Mohand. Multiple Query Evaluation Based on Enhanced Genetic Algorithm. Information Processing and Management，2003，39(2)：215-231