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

[關(guān)鍵詞]網(wǎng)絡(luò)考試系統(tǒng) 遺傳算法 交叉概率 自適應(yīng)變異概率

本文主要針對如何提高網(wǎng)絡(luò)考試系統(tǒng)中組卷速度及質(zhì)量問題進(jìn)行分析。該問題的核心是組卷算法。目前在各種自動組卷算法中，組卷質(zhì)量較好的是遺傳算法。

一、遺傳算法的基本思想

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

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

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

1.與進(jìn)化代數(shù)相關(guān)的交叉概率

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

要設(shè)計如上所述的交叉概率而又要兼顧計算速度，無疑是比較困難的。本文為此設(shè)計與進(jìn)化代數(shù)相關(guān)而與個體適應(yīng)度無關(guān)的交叉概率計算公式：

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

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

此外，變異概率的總趨勢也應(yīng)該是能逐漸減小而使群體能夠迅速集中。為此設(shè)計了如下的與遺傳進(jìn)化代數(shù)和個體適應(yīng)度相關(guān)的自適應(yīng)變異概率：

三、結(jié)束語

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

參考文獻(xiàn)：

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

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

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

（作者單位：內(nèi)蒙古包鋼高級技術(shù)學(xué)校）