計算機有關自動機的論文

　　自動機原來是模仿人和動物的行動而做成的機器人的意思。但是現在已被抽象化為如下的機器。時間是離散的***t=0，1，2……***，在每一個時刻它處於所存在的有限個內部狀態中的一個。對每一個時刻給予有限個輸入中的一個。那麼下一個時刻的內部狀態就由現在的輸入和現在的內部狀態所決定。下面是小編給大家推薦的，希望大家喜歡!

　　篇一

　　《基於遺傳演算法的自動組卷系統設計》

　　摘要：自動組卷系統是計算機輔助教學的重要組成部分，而遺傳演算法以其全域性尋優和智慧搜尋的特性，得到了廣泛的運用。根據自動組卷系統的特點，將遺傳演算法合理應用於自動組卷中，在遺傳演算法中，設計了雙種群機制，並以試卷難度、試卷區分度、試卷的估計用時、知識點分佈為基礎構造適應度函式，通過輪盤賭選擇方法、多點交叉和變異，較好地解決了自動組卷的多重目標尋優問題。

　　關鍵詞：自動組卷;遺傳演算法;適應度函式

　　0引言

　　考試是教學過程中的一個重要環節，我們用它來檢測教學效果，以期提高教學質量。傳統的手工方式，都是以教師的經驗與知識的積累為依據出題，帶有一定的主觀性，考試命題質量和科學性不能保證。另外，對於有些課程，我們希望平時能夠在計算機機房通過上機完成測驗。所以，伴隨人工智慧的廣泛應用，自動組卷技術成為我們必須深入探討的一個課題。現有不少自動組卷系統，但其演算法存在時間複雜度和空間複雜度偏大、程式結構複雜、試題缺乏隨機性等缺陷\[1\]。將遺傳演算法應用於自動組卷系統中，並將試卷難度、試卷區分度、試卷的估計用時、知識點分佈作為綜合優化目標，對上述缺陷作出了改進。

　　1基於遺傳演算法的自動組卷演算法設計

　　遺傳演算法的操作步驟為編碼、隨機產生初始種群、構建適應度函式、對初始種群迭代執行選擇、交叉、變異等遺傳操作產生下一代種群，獲取最優解、解碼\[2\]。本自動組卷演算法設計如下。

　　1.1編碼設計

　　整數編碼直接採用解空間的形式進行編碼，意義明確，易於引入特定領域的資訊，而且能大大縮短串長，遺傳操作無須頻繁地編碼、解碼，改善了遺傳演算法的計算複雜性，提高了演算法效率\[3\]。本演算法採用整數編碼將現實問題對映到染色體即個體形式。

　　實現時，按試卷的題型對個體進行分段編碼。比如試卷由L種題型的試題組成，則染色體編碼劃分成L個子段，每個子段對應一種題型。每個子段中基因個數為該題型要求的題目個數。

　　試題庫中每道題目，都有一個編號與其對應。比如現在生成了兩張試卷個體ExaPaper1、ExaPaper2。分別由選擇、填空、判斷、問答、綜合5道題組成。

　　1.2產生兩個初始種群

　　在初始種群產生時，應採用某種演算法，使優秀、中等的、劣質的個體基本同概率存在。以保證初始種群產生的多樣性和分佈均勻性。並且採用產生2個初始種群的方法，同時對解空間內多個區域進行搜尋，並互相交流資訊。這種設定方法，雖然每次需執行與種群規模n成2倍的計算量，但實質上可進行大約O ***n\+3***個解的有效搜尋。因此，這種2種群的設定方法，成本雖提高一倍，效率則以指數形式上升。

　　實現時，本演算法採用隨機的方法產生320個個體，將他們分為40個子空間，則每個子空間中有8個個體。然後從每個子空間中隨機獲取5個個體，這樣就形成了200個個體，對這200個個體再隨機劃分到兩個初始種群中。

　　1.3構造適應度函式

　　一份卷子設計是否合理，通常從3個方面考察：第一，題型比例配置是否適當;第二，題目難、中、易比例是否合理;第三，干擾項是否有效，能不能反映考生的典型錯誤。本演算法將試卷難度、試卷區分度、試卷的估計用時、知識點分佈4個目標作為綜合優化目標，因此也將其作為構造適應度函式的主要依據。適應度函式的構造過程為，首先以各目標為基礎分別構造各自的目標函式，然後使用加權的方法對各目標函式進行組合獲得適應度函式。

　　1.3.1各目標函式構造

　　***1***試卷難度目標函式。

　　針對不同的考生，試卷難度要求也不同，因此將試卷難度作為構造適應度函式的一個依據。

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

　　其中，X為種群中個體，N為X的長度，i表示X中第i個位置。對應到自動組卷中，N為題目的個數，total_score為試卷的總分，i表示X這份試卷中第幾道題目。f\-c***i***為i這道題目對應的難易度，p***i***為這道題目對應的分值。Exp_Difficulty為對試卷的難度期望值。由此可知，F\-c***X***值越大，說明試卷難度符合要求的可能性越大。

　　***2***試卷區分度目標函式、試卷估計用時目標函式。

　　區分度是指試題對被試者情況的分辨能力的大小。區分度適當的試卷能把優秀、一般、差三個層次的學生真正區分開。試卷區分度目標函式、試卷估計用時目標函式構造方法與試卷難度目標函式構造方法類似。試卷區分度目標函式構造如式***2***所示。

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

　　其中，X為種群中個體，N為X的長度，i表示X中第i個位置。對應到自動組卷中，N為題目的個數，f\-d***i***為i這道題目對應的區分度，p***i***為這道題目對應的分值。total_score為試卷總分值。Exp_Different為對試卷的區分度的望值。由此可知，F\-d***X***值越大，說明試卷難度符合要求的可能性越大。

　　試卷估計用時目標函式構造如式***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為種群中個體，N為X的長度i表示X中第i個位置。對應到自動組卷中，N為題目的個數，f\-t***i***為完成i這道題目的期望時間。Exp_Time為完成本試卷估計用時的期望值。由此可知，F\-t***X***值越大，說明試卷難度符合要求的可能性越大。

　　***3***知識點分佈目標函式。

　　教學大綱中，對不同章節知識點的掌握程度要求也不同。因此，設計知識點分佈目標函式，用來把握考察的知識點是否全面合理。

　　知識點分佈目標函式構造如式***5***、式***6***所示。

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

　　Fs***i***=fs***i***第i題目屬於第j章內容0第i題目不屬於第j章內容***6***

　　其中，X為種群中個體，N為X的長度，i表示X中第i個位置。對應到自動組卷中，M為本試卷要考察到的章節總數。fw***j***為課本第j章在試卷中佔用的權重。N為題目的個數，fs***j***為第i題目的分值。若第i題目是第j章節的內容，F\-s***i***才儲存f\-s***i***的值，以便參與實際試卷中第j章節權重的計算。total_score為試卷總分值。由此可知，F\-n***X***值越大，說明試卷難度符合要求的可能性越大。

　　1.3.2適應度函式構造

　　使用加權的方法對各目標函式進行組合，形成適應度函式。適應度函式如式***7***所示：

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

　　其中，F\-c***X***、F\-d***X***、F\-t***X***、F\-n***X***分別為試卷難度、試卷區分度、試卷的估計用時、知識點分佈的目標函式。1、2、3、4分別為試卷難度、試卷區分度、試卷的估計用時、知識點分佈目標函式的權值。並且1+2+3+4=1。權值1、2、3、4的取值應依據具體試卷考核目標而定。

　　1.4遺傳操作

　　1.4.1選擇操作設計

　　在本演算法中，應用輪盤賭選擇方法進行選擇操作，決定將哪些個體複製到新種群中\[4\]。並進一步根據適應度值對t+1代和t代種群最優個體進行比較及選取，確保在t+1種群中，最優個體的適應度並不低於t種群的最優個體適應度。

　　1.4.2交叉操作設計

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

　　1.4.3變異操作設計

　　變異操作為對群體中某些個體的基因進行小概率擾動。本變異的操作如下：以題型為基礎，將個體分段，每段隨機選擇一個變異位置，並從同題型題庫中隨機選擇一個題目替換該變異位置題目，條件是新選的題目不能與當前試卷中同題型其它題目重複。

　　1.4.4種群競爭設計

　　本演算法採用產生2個初始種群的方法，同時對解空間內多個區域進行搜尋，並互相交流資訊。種群競爭的具體設計思想為：對兩個初始種群K11、K21分別進行遺傳操作產生新的種群，各經過T代***不同問題T的設定不同***後，獲取到新種群K1T、K2T。將K1T、K2T兩個種群中個體合併，按適應度排序。前一半個體形成新的K1T種群，後一半個體形成新的K2T種群。將新K1T、K2T再反覆執行上述過程，直到滿足終止條件時進化結束。本演算法的終止條件是當達到規定的最大迭代次數HMAX或者最好個體的適應度函式值HMAX/5次達到了要求。

　　1.5選擇最優解及解碼

　　通過遺傳演算法最終可獲得一組個體，對這組個體分別計算適應度值，獲取適應度最優的個體，作為最終解。因為是整數編碼，個體中基因值即為題庫中被選中題的題號。因此，從最優個體可直接得到最終生成的試卷。

　　2結語

　　本文圍繞自動組卷存在的問題，重點研究了遺傳演算法的改進及其在自動組卷演算法中的應用。通過執行基於該遺傳演算法的組卷程式，證明了該設計的可行性、有效性。

　　參考文獻：

　　[1]黎軍.基於遺傳演算法的自動組卷設計[J].電腦學習，2009***3***.

　　[2]陳國良，王煦法，莊鎮.遺傳演算法及其應用[M].北京：人民郵電出版社，1996.

　　[3]張超群，鄭建國，錢潔.遺傳演算法編碼方式比較[J].計算機應用，2011***3***.

　　[4]丁承層，強傳生，張輝.遺傳演算法縱橫談[J].資訊與控制，1997***1***.

　　篇二

　　《基於改進遺傳演算法的自動組卷研究》

　　摘要：通過詳細分析試卷的各項約束條件，建立了一個以知識點、難度係數、區分度等為核心屬性的自動組卷數學模型，並利用改進的遺傳演算法實現了自動組卷。

　　關鍵字：自動組卷;數學模型;遺傳演算法

　　自動組卷就是根據使用者的要求，採用一定的演算法自動地從試題庫中抽取一定數量的試題組成試卷。自動組卷演算法的好壞直接影響到試卷的質量，如何從試題庫中選出試題組成符合使用者要求的試卷，並使組卷具有較高的效率和成功率是當前研究的熱門課題。現有的自動組卷演算法一般有三種：隨機選取法、回溯試探法和遺傳演算法。遺傳演算法是一種新發展起來的並行優化演算法，它很適合解決自動組卷問題。

　　1 試題核心屬性的確定

　　在自動組卷系統中，一些試題庫設定了試題的各類屬性，如章節、層次、要求、題型、難度係數、難度級別、各章節分值等屬性，其實過多的屬性會增加實際組卷的難度，降低效率。以教育學理論為指導，選擇以下屬性作為試題的核心屬性。

　　***1*** 題號。試題的編號，用來唯一標識試題。

　　***2*** 題型。試題的型別。

　　***3*** 知識點。某道題屬於某門課程的哪個知識點，知識點的設定不以章節為依據，從而可以避免教材的不同對組卷造成影響。

　　***4*** 難度係數。難度係數[1]是表示某一試題的難易程度，通常用未通過率來表示，即一次考試中未答對某道試題的考生數在其總體中所佔的比例。一般來說，難度係數值為0.5時，是中等難度，如果小於0.3試題太簡單，如果大於0.7試題太難，對考生都會做或都不會做***難度係數為0或為1***的試題，屬於無意義的試題，必須淘汰。

　　***5*** 區分度。區分度[2]是指某道題對不同水平考生加以區分的能力。區分度高的試題，對學生水平有較好的鑑別力。區分度的計算公式為：

　　其中，B表示試題的區分度，H表示樣本中高分組在某題上所得的平均分，L表示樣本中低分組在某題上所得的平均分，K表示某題滿分。高分組和低分組一般各佔樣本的25%～30%，最好取27%。一般來說，試題的區分度在0.4以上就被認為是很好的。在0.3～0.39之間，認為良好;在0.2～0.29之間，認為可以;在0.19以下，認為差，必須淘汰或加以修改。對在校學生的達標考試，試卷的區分度不宜太高，因為它不是選拔性質的考試。但也不能過低，否則對學生的鑑別效果差，不能很好的達到考試的目的。一般區分度控制在0.2～0.3之間為宜。

　　***6*** 分值。某小題的分數。

　　***7*** 答題時間。完成某題估計所需的時間。

　　2 自動組卷數學模型的建立

　　自動組卷中決定一道試題，其實就是決定一個包含題號、題型、知識點、難度係數、區分度、分值、答題時間的七維向量***a 1，a 2，a 3， a4，a 5，a 6，a 7***。假設一套試卷中包含n道試題，一套試卷就決定了一個n×7的矩陣S：

　　這就是問題求解中的目標矩陣，其中a i1 、a i2 、 a i3 、a i4、a i5、 a i6 、a i7分別表示試卷中第i道題的題號、題型、知識點、難度係數、區分度、分值、答題時間。從矩陣S可以看出組卷問題是一個多重約束目標的問題求解，且目標狀態不是唯一的。

　　在實際組卷時，使用者會對試卷提出多方面的要求，使用者的每一個要求對應試卷的一個約束條件。要組成一份符合要求的、高質量的試卷，目標矩陣的分佈要滿足以下試卷約束條件。

　　***1*** 試卷中包含的題型以及每種題型的題量要與使用者的設定相符。

　　k種題型的題量=

　　***2*** 試卷中包含知識點即考核知識點以及各考核知識點所佔分數的比例要與使用者設定相符。

　　K種考核知識點所佔分數=

　　***3*** 試卷的難度係數要滿足使用者的要求，試卷的難度係數一般用試卷中每道試題的難度係數的加權平均來計算。

　　即：試卷的難度係數=

　　***4*** 試卷的區分度要滿足使用者的要求，試卷的區分度一般用試卷中每道試題的區分度的加權平均來計算。

　　即：試卷的區分度=

　　***5*** 試卷的總分要與設定相符。

　　即：試卷的總分=

　　***6*** 試卷的總答題時間要與使用者設定相符。

　　即：試卷的總答題時間=

　　在實際組卷時，試卷的總分、考核知識點、各題型每小題分值、試卷中包含的題型、各題型的題量都應該是精確達到的。試卷中各考核知識點所佔的分數、試卷的難度係數、區分度和試卷的總答題時間這四個約束條件可以存在一定的誤差。誤差的大小由使用者的期望值和各約束條件的重要性決定。在實際應用中，各約束條件的重要性是不同的，因此，目標函式就取各項誤差的加權和。目標函式f可以表示為：

　　為了不至於各項誤差相互抵消，實際值與使用者要求值的誤差都取絕對值。其中，試卷中各考核知識點所佔的分數和試卷的總答題時間這兩項的誤差為實際值與使用者要求值的誤差絕對值與使用者要求值的比，試卷的難度係數和區分度這兩項的誤差為實際值與使用者要求值的誤差的絕對值。w i表示第i個約束條件的權值，w i通常由專家經驗或試驗給出，0≤w i ≤1。由上式可知，目標函式f的值越小，即誤差越小，問題的解越優，即生成的試卷越接近使用者的需求。

　　3 遺傳演算法

　　遺傳演算法[3，4，5]是以適應度函式***或目標函式***為依據，通過對群體中的個體進行遺傳操作實現群體內個體結構重組的迭代處理過程。在這一過程中，群體中的個體一代一代地得以優化，並逐漸地逼近最優解，最終獲得最優解。傳統遺傳演算法的主要步驟包括初始染色體群體生成、適應度評估和檢測、選擇操作、交叉操作和變異操作。傳統遺傳演算法流程圖如圖1所示***其中t為進化代數，t0為最大進化代數***。

　　4 基於改進遺傳演算法的自動組卷

　　傳統的遺傳演算法採用二進位制編碼，用1表示某題被選中，0表示某題沒有被選中，這種編碼非常簡單，但在進行交叉和變異操作時，各題型的題量很難控制，而且當試題庫題量很大時編碼很長。傳統的遺傳演算法以進化代數等於最大進化代數作為終止條件，但是在實際組捲過程中並不知道種群進化到第幾代就能得到試卷的最優組合。因此用遺傳演算法實現自動組卷時，要對傳統遺傳演算法進行一些改進。

　　4.1 改進的遺傳演算法

　　4.1.1 染色體編碼

　　通過對編碼的大量分析，提出了一種分段實數編碼機制，首先將染色體分成若干段，每一段對應一種題型，組成試卷的各道試題題號直接對映為基因，編碼時將同一題型的試題放在同一段，同一段內題號各不相同。以題號編碼的方法所表達的意義清楚、明確、不需解碼，從而可以提高演算法效能，提高運算效率。而且交叉和變異操作都在各段內部進行，因此可以保證組捲過程中各題型題量的正確匹配。

　　4.1.2 適應度函式設計遺傳演算法在進化搜尋中僅以適應度函式為依據，利用種群中每個個體的適應度值來進行搜尋。因此，適應度函式的選擇至關重要，一般而言，適應度函式是由目標函式變換而成的。上面提出的自動組卷模型是最小化問題，採用如下方法可將目標函式f轉換成適應度函式F。

　　由上式可知，F的取值範圍為0～1，適應度函式F的值越大，說明個體越好，個體越接近問題的最優解。

　　4.1.3 初始化染色體群體

　　隨機生成初始染色體群體，在初始染色體群體中，染色體的長度為n，群體的大小為m，m太小時，難以求出最優解，太大時則增長收斂時間。群體的大小一般根據需要，按經驗或試驗給出，一般m=30～160。

　　4.1.4 遺傳運算元

　　***1*** 選擇運算元

　　在遺傳操作中，為了保留較優的個體，以概率1完全地複製每一代群體中按適應度值從大到小依次排列的前面2個個體。為了保持群體大小不變，同時刪除適應度排列的後面的2個個體。然後從排列在前面的m-2個個體中隨機抽取p***p≤m-2***個個體進行交叉和變異操作。這種選擇策略使得適應度小的個體也有可能被選中，這樣有助於增加下一代群體的多樣性。

　　***2*** 交叉運算元

　　在遺傳操作中，採用了分段的思想，交叉的時候按題型段進行交叉，因此交叉後不存在段內試題重複的問題，也不會改變每種題型的題量。交叉概率p c太小時難以向前搜尋，太大時則容易破壞高適應度的結構。一般p c=0.4～0.6。 ***3***變異運算元在遺傳操作中，變異在染色體的題型段內進行。變異概率p m太小時難以產生新的基因結構，太大時使遺傳演算法成了單純的隨機搜尋。一般p m=0.01～0.2。

　　4.1.5 終止條件

　　在改進的遺傳演算法中，設定了期望適應度值，把每一代計算出來的最高適應度個體的適應度值與期望適應度值相比較，當適應度最高的個體的適應度值大於或等於期望適應度值時則停止進化，否則繼續進行遺傳操作、計算適應度值、反覆迭代直到組捲成功。

　　4.2 主要演算法描述

　　基於改進遺傳演算法的自動組卷的主要演算法描述如演算法1所示。

　　演算法1：

　　int GJGA***p c，p m，m，f0***

　　{

　　t=0;

　　initialize***p***t******;//隨機產生初始染色體群體

　　計算初始染色體群體的適應度值;

　　while ***maxf

　　{

　　selection***p***t******;//選擇操作

　　crossover***p***t******;//交叉操作

　　mutation***p***t******;//變異操作

　　得到下一代染色體群體q***t+1***，計算下一代染色體群體的適應度值;

　　t++;

　　}

　　輸出當前染色體群體中適應度最高的染色體;

　　}

　　4.3 遺傳演算法複雜度分析

　　在遺傳演算法中，絕大部分處理都集中在適應度的計算上，因此可以用計算個體適應度操作的時間複雜度作為演算法的時間量度。遺傳演算法的時間複雜度為O***t*m*n***。因為試題庫中的題量一般都很大，所以改進後的遺傳演算法的時間複雜度一般要比傳統遺傳演算法的時間複雜度小。遺傳演算法的空間複雜度可以用初始染色體群體所佔的空間來衡量，遺傳演算法的空間複雜度為O***m*n***。因為改進後的遺傳演算法的染色體的長度遠比傳統遺傳演算法的染色體的長度小，所以改進後的遺傳演算法的空間複雜度遠比傳統遺傳演算法空間複雜度小。

　　5 結論

　　演算法的改進往往不能顧及問題每一個方面，如果演算法設計的核心是提高解的精度，則演算法可能在搜尋範圍和搜尋精度上花去更多的時間，如果演算法的設計主要在於儘快收斂，得到結果，則在解的精度上考慮很少，演算法往往側重於減少進化代數。改進後的遺傳演算法使生成試卷的質量得到了保證，但要使組卷的收斂速度得到進一步改進，還需進一步研究。

　　參考文獻

　　[1] 文海英. 智慧型試卷自動生成系統中試卷難度控制技術的研究***J***.湖南科技學院學報，2005，26***5***：153-156

　　[2] 常振江. 學生成績分佈與一種簡便的評估試卷命題質量的方法***J***. 遼寧師範大學學報：自然科學版，2003，26***1***：109-112

　　[3] 丁衛平. 基於遺傳演算法的智慧組卷應用研究.電氣電子教學學報***J***，2005，27***2***：93-95

　　[4] 朱黎明. 基於單親遺傳演算法的試題生成及其應用研究***D***. 長沙：湖南大學，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