網絡考試系統中算法的優化

[摘要]目前網絡在教育教學管理中的作用越來越重要，而在網絡教學中，網絡考試系統是重要的組成部分之一。如何提高網絡考試系統中組卷速度及質量，核心是組卷算法。目前在各種自動組卷算法中，組卷質量較好的是遺傳算法，但遺傳算法在理論和應用方法上仍有許多亟待完善之處，本文提出一種優化的改進的遺傳算法。

[關鍵詞]網絡考試系統 遺傳算法 交叉概率 自適應變異概率

本文主要針對如何提高網絡考試系統中組卷速度及質量問題進行分析。該問題的核心是組卷算法。目前在各種自動組卷算法中，組卷質量較好的是遺傳算法。

一、遺傳算法的基本思想

遺傳算法是一種模擬生物群體進化的優化算法，是由美國Michigan大學的JohnHolland教授于1975年首先提出來的。遺傳算法是一類隨機算法，它可以有效地利用已有的信息來搜尋那些有希望改善解的質量的串。遺傳算法通過作用于染色體上的基因，尋找好的染色體來求解問題。初始種群產生之后，按照適者生存和優勝劣汰的原理，逐代演化產生出越來越好的近似解。在每一代，根據問題域中個體的適應度大小挑選個體，并借助于自然遺傳學的遺傳算子進行組合交叉和變異，產生出代表新的解集的種群。這個過程將導致種群像自然界進化一樣。遺傳算法對求解問題的本身一無所知，它所需要的僅僅是對算法所產生的每個染色體進行評價，并基于適應值來選擇染色體，使適應值好的染色體比適應值差的染色體有更多的繁殖機會，后生代種群比前代更加適應于環境，末代種群中的最優個體經過解碼，可以作為問題近似最優解。

作為一種自適應啟發式的全局意義上的搜索算法，遺傳算法具有很強的魯棒性和通用優化能力。但遺傳算法在理論和應用方法上仍有許多亟待完善之處，比較突出的就是其全局搜索性能和收斂速度之間的矛盾。為此本文結合基本GA，提出一種優化的改進的遺傳算法。

二、遺傳算法的改進

1.與進化代數相關的交叉概率

交叉算子主要作用是產生新個體，實現了算法的全局搜索能力。所以，從種群的個體來看，交叉概率取值要與個體適應度值相關；從種群整體進化過程來看，交叉概率應該能隨進化過程逐漸變小，到最后趨于某一穩定值，以避免對算法后期的穩定性造成沖擊而導致算法不能收斂，或收斂過程加長；而從產生新個體的角度來看，種群中的所有個體在交叉操作上應該具有同等地位，即相同的概率，從而使 GA在搜索空間具有各個方向的均勻性。

要設計如上所述的交叉概率而又要兼顧計算速度，無疑是比較困難的。本文為此設計與進化代數相關而與個體適應度無關的交叉概率計算公式：

該公式的算法對劣質個體的處理顯得相對薄弱，但這個缺點可由此后的改進算子來擬補。2.改進的自適應變異概率

變異算子主要起維持種群多樣性的作用，即產生新個體和抑制早熟。所以，同一代種群中各個個體的變異概率應該隨個體的優劣而變化。即對于劣質個體，其變異概率應加大，而優秀個體應給予較小的變異概率。

此外，變異概率的總趨勢也應該是能逐漸減小而使群體能夠迅速集中。為此設計了如下的與遺傳進化代數和個體適應度相關的自適應變異概率：

三、結束語

標準遺傳算法生成的種群序列是有限的非周期不可約馬氏鏈，不能以概率1收斂到全局最優解，改進遺傳算法的執行過程和標準遺傳算法是相同的，因此也不能以概率1收斂到適應度為最大的個體。但改進遺傳算法的尋優能力和尋優速度都要優于標準遺傳算法，并且更利于搜索目標解，其原因在于編碼方式和適應度的定義不同，使得種群的演化更趨向于目標解區域。基因優劣編碼比其它的編碼方式含有更多的目標解信息，使得種群的演化更具有方向性，每一次迭代后有利于目標解的基因會增加，而不利于目標解的基因在減少，從而提高了尋優能力。由于適應度的定義決定了目標解的適應度并不是最大的，在搜索過程中，個體的演化方向并不嚴格趨向于目標解，而是趨向于目標解的K鄰域。當個體向適應度最大的個體X演化時，只要目標解處于演化路徑上，就會被找出來，當某演化路徑接近目標解時，這時所有個體距X尚有一定距離，即個體模式之間還有一定差距，不會因為個體差異性的減少而降低收斂速度。因此，目標解會很快被達到，這明顯優于把目標解作為適應度最大個體的情況，從而提高了尋優速度。如果目標解不在演化路徑上，但目標解處于X的某個鄰域內，算法依然可以找到近似最優解。

參考文獻：

［1］HollandJH.Adaptationin Nature and Artificial Systems[M].US:The University of Michigan Press，1975.

［2］邊潤強，陳增強，袁著祉.一種改進的遺傳算法及其在系統辨識中的應用[J].控制與決策，2000，15(5):623-625.

［3］王小平，曹立明．遺傳算法，西安交通大學出版社，2002.

（作者單位：內蒙古包鋼高級技術學校）