淺析遺傳算法在智能組卷系統(tǒng)中的應用

龔利　史楊

摘要：該文介紹了遺傳算法的基本原理和構(gòu)成要素，分析了遺傳算法的特點，在遺傳算法的研究基礎(chǔ)上，找到了一個很好的策略過程應用于智能試卷，提高運行的速度，避免了標準算法容易早熟現(xiàn)象，具有更好的健壯性，是一種很有發(fā)展?jié)摿Φ膬?yōu)化方法。

關(guān)鍵詞：遺傳算法；智能組卷

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）16-3879-02

Abstract： This paper introduces the basic principle and constituent elements of genetic algorithm， while analysing the characteristics of genetic algorithm. I find a better strategy in the process of the intelligent test paper generation through the study of genetic algorithm .This algorithm improve the speed of the operation and avoid prone to premature phenomenon of the standard algorithm， It has a better robustness， it is a optimization method with development potential.

Key words： genetic algorithm； intelligent test paper generation

在大部分的試卷系統(tǒng)的開發(fā)中，智能組卷應該是整個系統(tǒng)的關(guān)鍵因素。在完成試卷系統(tǒng)開發(fā)后，如果用戶使用智能組卷操作，首先要輸入的相應參數(shù)值進行設(shè)置約束條件，然后系統(tǒng)根據(jù)參數(shù)值被最符合需求的試卷，最后生成試卷滿足用戶的需求。定義轉(zhuǎn)換的參數(shù)，這些參數(shù)和算法，稱為組策略。該文試圖用遺傳算法研究智能組卷，找到最好的組策略。

1 什么是遺傳算法

遺傳算法基于自然群體遺傳進化機制，是模擬生物的遺傳、進化過程的自然環(huán)境，最后形成的一種自適應、全局優(yōu)化概率的搜索算法，這是一種比較高效的探索算法。它將可能的解決方案的問題域，作為一個個體或染色體組，并且對每個編碼的字符串形式模擬達爾文的遺傳選擇和生物進化的自然選擇過程[1]。

基于遺傳組重復的操作，根據(jù)適應度函數(shù)來評價每個預定的目標，根據(jù)適者生存，優(yōu)勝劣汰的進化規(guī)則，不斷得到更好的優(yōu)化，同時并行全局搜索方法搜索最好的個人組織優(yōu)化，最終達到滿足要求的最優(yōu)解。

2 遺傳算法的5個基本要素

遺傳算法的5個基本要素為：初始種群、染色體編碼、適應度函數(shù)、控制參數(shù)和遺傳算子。具體如下：

1） 初始種群：從初始種群開始，首先對種群初始化， 一個問題的最優(yōu)解可能是解決空間的初始種群。在解決的過程中進行遺傳操作，初始化的種群是第一代，然后第二、第三代……第N代，直到你找到最優(yōu)的解決方案。它是模擬自然進化的選擇機制和消除算法，是解決這一問題的解決方案。

2） 染色體編碼：先對染色體編碼，一般有二進制編碼、浮點編碼、自然數(shù)編碼、編碼、交叉編碼方法等染色體編碼。

3） 適應度函數(shù)：在搜索的過程中，首先計算每個適應值，然后對比終止條件時，如果條件滿足，就找到最優(yōu)的解決方案，然后退出搜索；否則，將繼續(xù)搜索，直到找到最優(yōu)的解決方案。通常個體適應值較高，表明個體越好，被選的概率就越高。

4） 控制參數(shù)：一般來說根據(jù)初始種群的大小和算法實現(xiàn)迭代等方式，對于特定的問題，對應的控制參數(shù)也不同。

5） 遺傳算子：在具體的搜索的進程中，先算出適應值，按照算法選擇相應的機制，選擇變異操作和個體交叉，最后生成新的個體將保持個體的多樣性。遺傳算法的流程圖如圖1所示。

3 遺傳算法的特點

1）遺傳算法不需要求導、或者其他輔助知識。只需要確定目標函數(shù)和適應度函數(shù)值的計算，可以指導搜索過程朝著一個更好的解決方案的搜索空間區(qū)域，加大了遺傳算法的應用。

2）遺傳算法具有自學習、自組織和自適應的特點。遺傳算法自動根據(jù)算法來計算的實現(xiàn)個體選擇和繁殖，產(chǎn)生新的種群，并最終找到最優(yōu)和次優(yōu)的解決方案，具有自學習、自組織和自適應能力【2】。

3）遺傳算法若給予一個特定的問題，就會產(chǎn)生很多的解決方案，最后可以由用戶決定。

由于遺傳算法可以通過整體搜索策略和優(yōu)化搜索方法，只要確定目標函數(shù)，并確定適應度函數(shù)和一系列的約束，就可以基于系統(tǒng)解決一般約束優(yōu)化問題。不需要求導、不需要其他輔助知識，并且可以更好的減少算法的盲目性和隨機性，所以可以滿足網(wǎng)絡(luò)考試系統(tǒng)多樣的組卷要求。

2 遺傳算法在智能組卷中的研究

1）什么是智能組卷

智能組卷是根據(jù)老師的要求生成滿足要求的，對于每一個學生都是公平公正的試卷。大多數(shù)考試系統(tǒng)采用的是手動組卷，這種方式效率低，并且消耗老師們大量精力來組建的試卷也不能完全滿足考試的需求。因此，許多高校正在努力開發(fā)的網(wǎng)絡(luò)考試系統(tǒng)，大多要求實現(xiàn)能夠進行智能組卷，從而將將教師擺脫沉重的組卷任務(wù)，提高教學質(zhì)量和考試效率?，F(xiàn)在很多基于智能組卷算法，主要基于是否優(yōu)先策略、隨機策略、回溯試探策略是本文將關(guān)注的遺傳算法，智能組卷的步驟是相似的。

2）遺傳算法在智能組卷系統(tǒng)的應用

在大多數(shù)智能組卷系統(tǒng)中，遺傳算法解決問題基本思想是：對于某個問題，首先隨機獲得N×n（N>=2，n>=2）個樣本，然后把這些樣本拆分成N個子種群，這樣一來每個子種群就包含n個樣本，我們對每個子種群進行單獨運行各自的遺傳算法，并且達到一定次數(shù)。

將這樣的每個種群記為GAi（i=1，2， 3，4…，N）。根據(jù)算法當每個子種群的遺傳算法開始循環(huán)運行到一定的代數(shù)以后，通過二維數(shù)組G[1..N，1..n]記錄N個遺傳算法的計算的結(jié)果，則[G[i，j]（i=1...M，j=1...m）]表示GAi的結(jié)果種群的第j個個體。同時采用數(shù)組K[1..N]記錄這N個結(jié)果種群的平均適應度值，K[i]表示GAi的結(jié)果種群平均適應度值。其應用于智能組卷系統(tǒng)的遺傳算法流程圖如圖2。

通過算法流程圖我們可以看到，這種遺傳算法在和上一層的個體交換上，它不需要人工控制交換一個相應的個體，也不需要設(shè)置某個特定的處理器來交換出某個體。這不僅改善了遺傳算法與遺傳算法在每個處理器上運行，同時每個處理器不斷產(chǎn)生新種群的更高一層的運算和控制。

3 小結(jié)

本文主要研究了智能試卷算法在組卷系統(tǒng)中的應用。首先介紹了什么是遺傳算法，并介紹了遺傳算法5個基本要素和特點；然后介紹了什么是智能組卷，重點介紹了遺傳算法如何應用于智能組卷系統(tǒng)，給出了算法的流程圖。通過對遺傳算法解決問題的算法分析，我們發(fā)現(xiàn)遺傳算法在智能試卷過程中，能夠提高系統(tǒng)的運算速度，避免了標準算法容易早熟現(xiàn)象，具有更好的健壯性，是一種很有發(fā)展?jié)摿Φ膬?yōu)化方法。

參考文獻：

[1] 史楊.基于改進遺傳算法的智能組卷系統(tǒng)研究[D].武漢：武漢理工大學，2011：100-135.

[2] 劉洋.算法在數(shù)字濾波器設(shè)計中的應用研究[D].成都：電子科技大學，2004：60-89.

[3] 宋照紅.通用智能實時反垃圾郵件機的設(shè)計與實現(xiàn)[D].成都：電子科技大學，2004：75-96.endprint

摘要：該文介紹了遺傳算法的基本原理和構(gòu)成要素，分析了遺傳算法的特點，在遺傳算法的研究基礎(chǔ)上，找到了一個很好的策略過程應用于智能試卷，提高運行的速度，避免了標準算法容易早熟現(xiàn)象，具有更好的健壯性，是一種很有發(fā)展?jié)摿Φ膬?yōu)化方法。

關(guān)鍵詞：遺傳算法；智能組卷

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）16-3879-02

Abstract： This paper introduces the basic principle and constituent elements of genetic algorithm， while analysing the characteristics of genetic algorithm. I find a better strategy in the process of the intelligent test paper generation through the study of genetic algorithm .This algorithm improve the speed of the operation and avoid prone to premature phenomenon of the standard algorithm， It has a better robustness， it is a optimization method with development potential.

Key words： genetic algorithm； intelligent test paper generation

在大部分的試卷系統(tǒng)的開發(fā)中，智能組卷應該是整個系統(tǒng)的關(guān)鍵因素。在完成試卷系統(tǒng)開發(fā)后，如果用戶使用智能組卷操作，首先要輸入的相應參數(shù)值進行設(shè)置約束條件，然后系統(tǒng)根據(jù)參數(shù)值被最符合需求的試卷，最后生成試卷滿足用戶的需求。定義轉(zhuǎn)換的參數(shù)，這些參數(shù)和算法，稱為組策略。該文試圖用遺傳算法研究智能組卷，找到最好的組策略。

1 什么是遺傳算法

遺傳算法基于自然群體遺傳進化機制，是模擬生物的遺傳、進化過程的自然環(huán)境，最后形成的一種自適應、全局優(yōu)化概率的搜索算法，這是一種比較高效的探索算法。它將可能的解決方案的問題域，作為一個個體或染色體組，并且對每個編碼的字符串形式模擬達爾文的遺傳選擇和生物進化的自然選擇過程[1]。

基于遺傳組重復的操作，根據(jù)適應度函數(shù)來評價每個預定的目標，根據(jù)適者生存，優(yōu)勝劣汰的進化規(guī)則，不斷得到更好的優(yōu)化，同時并行全局搜索方法搜索最好的個人組織優(yōu)化，最終達到滿足要求的最優(yōu)解。

2 遺傳算法的5個基本要素

遺傳算法的5個基本要素為：初始種群、染色體編碼、適應度函數(shù)、控制參數(shù)和遺傳算子。具體如下：

1） 初始種群：從初始種群開始，首先對種群初始化， 一個問題的最優(yōu)解可能是解決空間的初始種群。在解決的過程中進行遺傳操作，初始化的種群是第一代，然后第二、第三代……第N代，直到你找到最優(yōu)的解決方案。它是模擬自然進化的選擇機制和消除算法，是解決這一問題的解決方案。

2） 染色體編碼：先對染色體編碼，一般有二進制編碼、浮點編碼、自然數(shù)編碼、編碼、交叉編碼方法等染色體編碼。

3） 適應度函數(shù)：在搜索的過程中，首先計算每個適應值，然后對比終止條件時，如果條件滿足，就找到最優(yōu)的解決方案，然后退出搜索；否則，將繼續(xù)搜索，直到找到最優(yōu)的解決方案。通常個體適應值較高，表明個體越好，被選的概率就越高。

4） 控制參數(shù)：一般來說根據(jù)初始種群的大小和算法實現(xiàn)迭代等方式，對于特定的問題，對應的控制參數(shù)也不同。

5） 遺傳算子：在具體的搜索的進程中，先算出適應值，按照算法選擇相應的機制，選擇變異操作和個體交叉，最后生成新的個體將保持個體的多樣性。遺傳算法的流程圖如圖1所示。

3 遺傳算法的特點

1）遺傳算法不需要求導、或者其他輔助知識。只需要確定目標函數(shù)和適應度函數(shù)值的計算，可以指導搜索過程朝著一個更好的解決方案的搜索空間區(qū)域，加大了遺傳算法的應用。

2）遺傳算法具有自學習、自組織和自適應的特點。遺傳算法自動根據(jù)算法來計算的實現(xiàn)個體選擇和繁殖，產(chǎn)生新的種群，并最終找到最優(yōu)和次優(yōu)的解決方案，具有自學習、自組織和自適應能力【2】。

3）遺傳算法若給予一個特定的問題，就會產(chǎn)生很多的解決方案，最后可以由用戶決定。

由于遺傳算法可以通過整體搜索策略和優(yōu)化搜索方法，只要確定目標函數(shù)，并確定適應度函數(shù)和一系列的約束，就可以基于系統(tǒng)解決一般約束優(yōu)化問題。不需要求導、不需要其他輔助知識，并且可以更好的減少算法的盲目性和隨機性，所以可以滿足網(wǎng)絡(luò)考試系統(tǒng)多樣的組卷要求。

2 遺傳算法在智能組卷中的研究

1）什么是智能組卷

智能組卷是根據(jù)老師的要求生成滿足要求的，對于每一個學生都是公平公正的試卷。大多數(shù)考試系統(tǒng)采用的是手動組卷，這種方式效率低，并且消耗老師們大量精力來組建的試卷也不能完全滿足考試的需求。因此，許多高校正在努力開發(fā)的網(wǎng)絡(luò)考試系統(tǒng)，大多要求實現(xiàn)能夠進行智能組卷，從而將將教師擺脫沉重的組卷任務(wù)，提高教學質(zhì)量和考試效率?，F(xiàn)在很多基于智能組卷算法，主要基于是否優(yōu)先策略、隨機策略、回溯試探策略是本文將關(guān)注的遺傳算法，智能組卷的步驟是相似的。

2）遺傳算法在智能組卷系統(tǒng)的應用

在大多數(shù)智能組卷系統(tǒng)中，遺傳算法解決問題基本思想是：對于某個問題，首先隨機獲得N×n（N>=2，n>=2）個樣本，然后把這些樣本拆分成N個子種群，這樣一來每個子種群就包含n個樣本，我們對每個子種群進行單獨運行各自的遺傳算法，并且達到一定次數(shù)。

將這樣的每個種群記為GAi（i=1，2， 3，4…，N）。根據(jù)算法當每個子種群的遺傳算法開始循環(huán)運行到一定的代數(shù)以后，通過二維數(shù)組G[1..N，1..n]記錄N個遺傳算法的計算的結(jié)果，則[G[i，j]（i=1...M，j=1...m）]表示GAi的結(jié)果種群的第j個個體。同時采用數(shù)組K[1..N]記錄這N個結(jié)果種群的平均適應度值，K[i]表示GAi的結(jié)果種群平均適應度值。其應用于智能組卷系統(tǒng)的遺傳算法流程圖如圖2。

通過算法流程圖我們可以看到，這種遺傳算法在和上一層的個體交換上，它不需要人工控制交換一個相應的個體，也不需要設(shè)置某個特定的處理器來交換出某個體。這不僅改善了遺傳算法與遺傳算法在每個處理器上運行，同時每個處理器不斷產(chǎn)生新種群的更高一層的運算和控制。

3 小結(jié)

本文主要研究了智能試卷算法在組卷系統(tǒng)中的應用。首先介紹了什么是遺傳算法，并介紹了遺傳算法5個基本要素和特點；然后介紹了什么是智能組卷，重點介紹了遺傳算法如何應用于智能組卷系統(tǒng)，給出了算法的流程圖。通過對遺傳算法解決問題的算法分析，我們發(fā)現(xiàn)遺傳算法在智能試卷過程中，能夠提高系統(tǒng)的運算速度，避免了標準算法容易早熟現(xiàn)象，具有更好的健壯性，是一種很有發(fā)展?jié)摿Φ膬?yōu)化方法。

參考文獻：

[1] 史楊.基于改進遺傳算法的智能組卷系統(tǒng)研究[D].武漢：武漢理工大學，2011：100-135.

[2] 劉洋.算法在數(shù)字濾波器設(shè)計中的應用研究[D].成都：電子科技大學，2004：60-89.

[3] 宋照紅.通用智能實時反垃圾郵件機的設(shè)計與實現(xiàn)[D].成都：電子科技大學，2004：75-96.endprint

摘要：該文介紹了遺傳算法的基本原理和構(gòu)成要素，分析了遺傳算法的特點，在遺傳算法的研究基礎(chǔ)上，找到了一個很好的策略過程應用于智能試卷，提高運行的速度，避免了標準算法容易早熟現(xiàn)象，具有更好的健壯性，是一種很有發(fā)展?jié)摿Φ膬?yōu)化方法。

關(guān)鍵詞：遺傳算法；智能組卷

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）16-3879-02

Abstract： This paper introduces the basic principle and constituent elements of genetic algorithm， while analysing the characteristics of genetic algorithm. I find a better strategy in the process of the intelligent test paper generation through the study of genetic algorithm .This algorithm improve the speed of the operation and avoid prone to premature phenomenon of the standard algorithm， It has a better robustness， it is a optimization method with development potential.

Key words： genetic algorithm； intelligent test paper generation

在大部分的試卷系統(tǒng)的開發(fā)中，智能組卷應該是整個系統(tǒng)的關(guān)鍵因素。在完成試卷系統(tǒng)開發(fā)后，如果用戶使用智能組卷操作，首先要輸入的相應參數(shù)值進行設(shè)置約束條件，然后系統(tǒng)根據(jù)參數(shù)值被最符合需求的試卷，最后生成試卷滿足用戶的需求。定義轉(zhuǎn)換的參數(shù)，這些參數(shù)和算法，稱為組策略。該文試圖用遺傳算法研究智能組卷，找到最好的組策略。

1 什么是遺傳算法

遺傳算法基于自然群體遺傳進化機制，是模擬生物的遺傳、進化過程的自然環(huán)境，最后形成的一種自適應、全局優(yōu)化概率的搜索算法，這是一種比較高效的探索算法。它將可能的解決方案的問題域，作為一個個體或染色體組，并且對每個編碼的字符串形式模擬達爾文的遺傳選擇和生物進化的自然選擇過程[1]。

基于遺傳組重復的操作，根據(jù)適應度函數(shù)來評價每個預定的目標，根據(jù)適者生存，優(yōu)勝劣汰的進化規(guī)則，不斷得到更好的優(yōu)化，同時并行全局搜索方法搜索最好的個人組織優(yōu)化，最終達到滿足要求的最優(yōu)解。

2 遺傳算法的5個基本要素

遺傳算法的5個基本要素為：初始種群、染色體編碼、適應度函數(shù)、控制參數(shù)和遺傳算子。具體如下：

1） 初始種群：從初始種群開始，首先對種群初始化， 一個問題的最優(yōu)解可能是解決空間的初始種群。在解決的過程中進行遺傳操作，初始化的種群是第一代，然后第二、第三代……第N代，直到你找到最優(yōu)的解決方案。它是模擬自然進化的選擇機制和消除算法，是解決這一問題的解決方案。

2） 染色體編碼：先對染色體編碼，一般有二進制編碼、浮點編碼、自然數(shù)編碼、編碼、交叉編碼方法等染色體編碼。

3） 適應度函數(shù)：在搜索的過程中，首先計算每個適應值，然后對比終止條件時，如果條件滿足，就找到最優(yōu)的解決方案，然后退出搜索；否則，將繼續(xù)搜索，直到找到最優(yōu)的解決方案。通常個體適應值較高，表明個體越好，被選的概率就越高。

4） 控制參數(shù)：一般來說根據(jù)初始種群的大小和算法實現(xiàn)迭代等方式，對于特定的問題，對應的控制參數(shù)也不同。

5） 遺傳算子：在具體的搜索的進程中，先算出適應值，按照算法選擇相應的機制，選擇變異操作和個體交叉，最后生成新的個體將保持個體的多樣性。遺傳算法的流程圖如圖1所示。

3 遺傳算法的特點

1）遺傳算法不需要求導、或者其他輔助知識。只需要確定目標函數(shù)和適應度函數(shù)值的計算，可以指導搜索過程朝著一個更好的解決方案的搜索空間區(qū)域，加大了遺傳算法的應用。

2）遺傳算法具有自學習、自組織和自適應的特點。遺傳算法自動根據(jù)算法來計算的實現(xiàn)個體選擇和繁殖，產(chǎn)生新的種群，并最終找到最優(yōu)和次優(yōu)的解決方案，具有自學習、自組織和自適應能力【2】。

3）遺傳算法若給予一個特定的問題，就會產(chǎn)生很多的解決方案，最后可以由用戶決定。

由于遺傳算法可以通過整體搜索策略和優(yōu)化搜索方法，只要確定目標函數(shù)，并確定適應度函數(shù)和一系列的約束，就可以基于系統(tǒng)解決一般約束優(yōu)化問題。不需要求導、不需要其他輔助知識，并且可以更好的減少算法的盲目性和隨機性，所以可以滿足網(wǎng)絡(luò)考試系統(tǒng)多樣的組卷要求。

2 遺傳算法在智能組卷中的研究

1）什么是智能組卷

智能組卷是根據(jù)老師的要求生成滿足要求的，對于每一個學生都是公平公正的試卷。大多數(shù)考試系統(tǒng)采用的是手動組卷，這種方式效率低，并且消耗老師們大量精力來組建的試卷也不能完全滿足考試的需求。因此，許多高校正在努力開發(fā)的網(wǎng)絡(luò)考試系統(tǒng)，大多要求實現(xiàn)能夠進行智能組卷，從而將將教師擺脫沉重的組卷任務(wù)，提高教學質(zhì)量和考試效率。現(xiàn)在很多基于智能組卷算法，主要基于是否優(yōu)先策略、隨機策略、回溯試探策略是本文將關(guān)注的遺傳算法，智能組卷的步驟是相似的。

2）遺傳算法在智能組卷系統(tǒng)的應用

在大多數(shù)智能組卷系統(tǒng)中，遺傳算法解決問題基本思想是：對于某個問題，首先隨機獲得N×n（N>=2，n>=2）個樣本，然后把這些樣本拆分成N個子種群，這樣一來每個子種群就包含n個樣本，我們對每個子種群進行單獨運行各自的遺傳算法，并且達到一定次數(shù)。

將這樣的每個種群記為GAi（i=1，2， 3，4…，N）。根據(jù)算法當每個子種群的遺傳算法開始循環(huán)運行到一定的代數(shù)以后，通過二維數(shù)組G[1..N，1..n]記錄N個遺傳算法的計算的結(jié)果，則[G[i，j]（i=1...M，j=1...m）]表示GAi的結(jié)果種群的第j個個體。同時采用數(shù)組K[1..N]記錄這N個結(jié)果種群的平均適應度值，K[i]表示GAi的結(jié)果種群平均適應度值。其應用于智能組卷系統(tǒng)的遺傳算法流程圖如圖2。

通過算法流程圖我們可以看到，這種遺傳算法在和上一層的個體交換上，它不需要人工控制交換一個相應的個體，也不需要設(shè)置某個特定的處理器來交換出某個體。這不僅改善了遺傳算法與遺傳算法在每個處理器上運行，同時每個處理器不斷產(chǎn)生新種群的更高一層的運算和控制。

3 小結(jié)

本文主要研究了智能試卷算法在組卷系統(tǒng)中的應用。首先介紹了什么是遺傳算法，并介紹了遺傳算法5個基本要素和特點；然后介紹了什么是智能組卷，重點介紹了遺傳算法如何應用于智能組卷系統(tǒng)，給出了算法的流程圖。通過對遺傳算法解決問題的算法分析，我們發(fā)現(xiàn)遺傳算法在智能試卷過程中，能夠提高系統(tǒng)的運算速度，避免了標準算法容易早熟現(xiàn)象，具有更好的健壯性，是一種很有發(fā)展?jié)摿Φ膬?yōu)化方法。

參考文獻：

[1] 史楊.基于改進遺傳算法的智能組卷系統(tǒng)研究[D].武漢：武漢理工大學，2011：100-135.

[2] 劉洋.算法在數(shù)字濾波器設(shè)計中的應用研究[D].成都：電子科技大學，2004：60-89.

[3] 宋照紅.通用智能實時反垃圾郵件機的設(shè)計與實現(xiàn)[D].成都：電子科技大學，2004：75-96.endprint