嚴太山，王 欣

（湖南理工學院信息科學與工程學院，岳陽 414000）

0 引言

知識規(guī)則挖掘是從規(guī)則數(shù)據(jù)集中發(fā)現(xiàn)有用新知識規(guī)則的過程，知識規(guī)則挖掘算法的好壞直接影響到所發(fā)現(xiàn)的新知識規(guī)則的好壞，目前人們用到的知識規(guī)則挖掘算法有多種［1-6］，如統(tǒng)計方法、神經(jīng)網(wǎng)絡、機器學習、粗糙集方法、遺傳算法，等等。在這些算法中，遺傳算法是基于“優(yōu)勝劣汰、適者生存”的生物進化機理而建立的一種智能優(yōu)化算法，憑借其強大的魯棒性和全局搜索能力而倍受人們的青睞。但是，傳統(tǒng)遺傳算法是在一個種群中以固定的交叉率和變異率來工作的，對于一個給定的優(yōu)化對象，為了找到合適的交叉率和變異率，往往需要經(jīng)過反復試驗，耗費大量時間，影響了算法的效率，而且在這種情況下，算法也難以滿足種群多樣性要求。諸多學者提出了各種自適應遺傳算法［7-12］，但大多是從適應性參數(shù)設置方面進行研究的，其通常做法是使交叉率Pc、變異率Pm等遺傳參數(shù)在進化過程中根據(jù)種群的實際情況動態(tài)調(diào)整大小，在不同程度上提高全局收斂率和尋優(yōu)效率。但由于進化種群的單一性及遺傳個體無性別區(qū)分，無法從根本上保證算法有效地調(diào)出局部最優(yōu)。為此，本文提出一種具有雌、雄個體的雙種群自適應遺傳算法，并將該算法應用于實踐教學質(zhì)量評價知識規(guī)則挖掘，利用算法的全局尋優(yōu)能力，在已有的實踐教學質(zhì)量評價知識規(guī)則庫中進行尋優(yōu)，得到隱含在其中的更為優(yōu)秀的新知識規(guī)則，為提高實踐教學質(zhì)量評價的科學性提供保障。

1 雙種群自適應遺傳算法

1.1 算法思想

為了克服傳統(tǒng)遺傳算法因進化種群單一而無法確保跳出局部最優(yōu)的問題，我們在遺傳算法中引入“主導種群+輔助種群”雙種群機制，并在主導種群、輔助種群中以不同的策略實現(xiàn)遺傳個體的進化。為了減少選擇操作的盲目性，引入生物界有性繁殖的特征，將遺傳個體分為雄性個體和雌性個體兩種性別類型，讓異性個體進行交叉操作。由此建立一種雙種群自適應遺傳算法（dual population adaptive genetic algorithm，DPAGA）。該算法的基本思想是：以選擇操作選中的個體作為新的進化種群——主導種群，未被選擇操作選中的個體組成另一種群——輔助種群；主導種群在進化過程中執(zhí)行自適應大概率交叉和小概率變異操作，輔助種群進化過程中執(zhí)行自適應小概率交叉和大概率變異操作，在輔助種群的作用下，算法出現(xiàn)早熟時能有效跳出局部最優(yōu)。

1.2 遺傳操作

1.2.1 選擇操作

在DPAGA算法中，采用兩代競爭排序的選擇方法來選擇優(yōu)秀遺傳個體作為交叉操作的備選對象。為確保異性個體進行有效交叉，被選中的個體中雄性個體和雌性個體應在數(shù)量上保持相等，并分別按優(yōu)劣順序進行排序。這樣更好地保持了進化過程中的遺傳多樣性，使優(yōu)秀基因和模式不被破壞，有利于進化過程朝著全局最優(yōu)解方向發(fā)展。

1.2.2 交叉操作

DPAGA算法中，進行交叉操作的兩個個體是按優(yōu)劣順序配對的兩個異性個體。交叉方式為單點自適應交叉，其主導種群交叉率Pdc和輔助種群交叉Pac分別按以下方式進行自適應調(diào)整：

1.2.3 變異操作

DPAGA算法的變異操作為自適應變異，其主導種群變異率Pdm和輔助種群變異率Pam分別按以下方式進行自適應調(diào)整：

公式（1）～（4）中，fdmax及famax分別表示主導種群、輔助種群的適應度最大值，fdavg及faavg分別表示主導種群、輔助種群的適應度平均值，f'表示兩交叉?zhèn)€體適應度的最大值，f表示變異個體的適應度值，Pdc1及Pdc2分別表示主導種群交叉率的最大值和最小值，Pac1及Pac2分別表示輔助種群交叉率的最大值和最小值，Pdm1及Pdm2分別表示主導種群變異率的最大值和最小值，Pam1及Pam2分別表示輔助種群變異率的最大值和最小值。

1.3 算法流程

DPAGA算法流程如圖1所示。

圖1 DPAGA算法流程

2 基于DPAGA的實踐教學質(zhì)量評價知識規(guī)則挖掘方法

2.1 實踐教學質(zhì)量評價指標體系構(gòu)建

在高等教育人才培養(yǎng)體系中，實踐教學一直是一個重要環(huán)節(jié)。高校在加強實踐教學日常管理的同時，還需要定期對實踐教學質(zhì)量進行客觀的評價。進行實踐教學質(zhì)量評價，首先需要構(gòu)建合理的評價指標體系。實踐教學質(zhì)量評價指標體系要符合教學實際，體現(xiàn)實踐教學的特點、目標和要求，同時要遵循教學評價指標體系的導向性原則、科學性原則、全面性原則、穩(wěn)定性與動態(tài)性兼顧的原則［13-15］。當然，評價指標體系中的指標數(shù)量要合適，而不是越多越好，因為隨著指標數(shù)的增加，計算量會呈指數(shù)急劇上升。我們通過對大量的實踐教學評價數(shù)據(jù)進行分析，并結(jié)合本校的實踐教學實際，構(gòu)建了一套較完善的實踐教學質(zhì)量評價指標體系。該指標體系的一級指標有4個，它們分別是實踐教學過程、實踐教學效果、實踐教學環(huán)境和實踐教學保障，這些一級指標下面一共有20個二級指標，如圖2所示。

圖2 實踐教學質(zhì)量評價指標體系

其中，x1～x4分別表示實驗室建設是否完善、人均實踐面積的大小是否合適、實踐場地和設備的實用性、實踐場地與設備的利用率；x5～x8分別表示生師比例是否合理、實踐學分占比是否恰當、實踐教學安全保障是否到位、常規(guī)管理制度是否有效執(zhí)行；x9～x14分別表示教學過程安排是否合理、教師教學態(tài)度是否認真、教師教學方法是否得當、實踐教學內(nèi)容與理論銜接程度、教學內(nèi)容的實用性和前沿性；x15～x20分別表示是否提高了學生學習積極性、是否培養(yǎng)了學生創(chuàng)新意識、是否培養(yǎng)了學生操作能力、是否促進了學生對理論知識的掌握、學生實踐報告完成情況、學生考核結(jié)果是否滿意。

2.2 知識規(guī)則表示與編碼

與其他知識規(guī)則表示方法相比，產(chǎn)生式規(guī)則表示方法具有符合人類認知特征、格式簡單、直觀自然等突出的優(yōu)越性，使得它成為應用最廣泛的一種知識規(guī)則表示方法，非常適合于實踐教學質(zhì)量評價。產(chǎn)生式知識規(guī)則在結(jié)構(gòu)上是由前提和結(jié)論兩部分組成的，其形式描述如下：

IF E1（A1,A2,…,Am）and E2（A1,A2,…,Am）and…and En（A1,A2,…,Am）THEN H（結(jié)論）。其中，Ei（A1,A2,…,Am）（1≤i≤n）是以Ai（1≤i≤m）為屬性的前提條件，H表示結(jié)論。

我們采用0-1編碼方式對知識規(guī)則進行編碼，每個評價指標及評價結(jié)論均有優(yōu)、良、中、差四個評價等級，四個評價等級的標記及編碼如表1所示，知識規(guī)則編碼結(jié)構(gòu)如圖3所示。

表1 評價等級的標記及編碼

圖3 知識規(guī)則個體編碼結(jié)構(gòu)

圖3中，S為知識規(guī)則個體的性別編碼，對于雄性個體，S=1；對于雌性個體，S=0；Ui為知識規(guī)則個體的第i個前提屬性值（即第i個評價指標等級）的編碼；由于全部條件不一定均被包含到規(guī)則中去，所以對每個前提屬性需設置一個標志位Flagi，如果條件i被規(guī)則包含，則Flagi=1；否則，F(xiàn)lagi=0；C為知識個體結(jié)論屬性值（評價等級）的編碼。

2.3 知識規(guī)則評價與檢驗

我們選取的實踐教學質(zhì)量評價知識規(guī)則的評價目標包括正確度、覆蓋度和可信度，利用這些評價目標的線性組合來進行知識規(guī)則適應度評價。正確度、覆蓋度和可信度的定義分別為

（1）正確度

（2）覆蓋度

（3）可信度

公式（5）～（7）中，U為測試數(shù)據(jù)集，ri為待評價的知識規(guī)則，為U的一個子集，其所有元素均與ri相匹配，為Ω的基數(shù)；W為U的另一子集，其所有元素的前提條件與ri相匹配，為Ω的基數(shù)，為U中與已有知識規(guī)則前提條件相匹配的元素個數(shù)最大值，Tri為知識規(guī)則庫中滿足ri條件完備的應有規(guī)則條數(shù)，TC為知識規(guī)則庫中結(jié)論的種數(shù)。

DPAGA算法運行之后，進行反復迭代運算，產(chǎn)生新的個體。對于算法挖掘出的新知識規(guī)則個體，需要進行有效性檢驗，如果規(guī)則rj被知識規(guī)則庫中已有的規(guī)則包含，或者與已有的規(guī)則相矛盾，則rj無效，予以刪除。有效性檢驗完成之后，再根據(jù)適應度值的大小，挑選那些優(yōu)秀的新知識規(guī)則個體加入到實踐教學質(zhì)量評價知識規(guī)則庫中。

3 算例

實踐教學質(zhì)量評價知識規(guī)則庫即測試數(shù)據(jù)集，其部分知識規(guī)則個體如表2所示。按照0-1編碼方式對知識規(guī)則個體進行編碼，利用評價目標的線性組合對知識規(guī)則個體進行適應度計算，編碼和適應度計算結(jié)果如表3所示。

表2 實踐教學質(zhì)量評價知識規(guī)則庫

表3 知識規(guī)則編碼及其適應度評價

我們應用改進遺傳算法DPAGA分別進行知識規(guī)則挖掘，DPAGA參數(shù)設置為：T=200，M=100，Pdc1=0.9，Pdc2=0.6，Pac1=0.1，Pac2=0.001，Pdm1=0.1，Pdm2=0.001，Pam1=0.5，Pam2=0.1。為分析DPAGA產(chǎn)生的新知識規(guī)則有效性，選取DPAGA第5次迭代運算后得到的結(jié)果，此時挖掘出的新知識規(guī)則個體編碼如表4所示，相應的知識規(guī)則個體如表5所示。在DPAGA算法挖掘出的八條新知識規(guī)則中，經(jīng)過有效性檢驗，發(fā)現(xiàn)其中兩條被知識規(guī)則庫中的現(xiàn)有規(guī)則包含了，它們分別是新規(guī)則N2被知識規(guī)則庫中的現(xiàn)有規(guī)則3包含，新規(guī)則N6被知識規(guī)則庫中的現(xiàn)有規(guī)則16包含；另有兩條與知識規(guī)則庫中的現(xiàn)有規(guī)則相矛盾，它們分別是新規(guī)則N5與知識規(guī)則庫中的現(xiàn)有規(guī)則14相矛盾，新規(guī)則N7與知識規(guī)則庫中的現(xiàn)有規(guī)則6相矛盾，這四條規(guī)則是無效的知識規(guī)則，應被刪除。只有規(guī)則N1、N3、N4和N8是有效的新知識規(guī)則，按照上述適應度評價方法計算得到N1、N4的適應度值均為0.961450，N3的適應度值為0.914062，N8的適應度值為0.726775。

表4 新知識規(guī)則編碼

表5 新知識規(guī)則

通過把新知識規(guī)則N1、N3、N4和N8的適應度值與知識規(guī)則庫的現(xiàn)有規(guī)則相比較，可以看出N1、N3、N4的適應度值較大，它們是較優(yōu)秀的新知識規(guī)則，因此這三條新知識規(guī)則將被加入到實踐教學質(zhì)量評價知識規(guī)則庫中，使知識規(guī)則庫得以更新。

4 結(jié)語

本文以主導種群和輔助種群為基礎，結(jié)合有性繁殖思想，提出了一種雙種群自適應進化遺傳算法，避免了傳統(tǒng)遺傳算法的種群單一性和遺傳個體無性別區(qū)分的缺陷，解決了傳統(tǒng)遺傳算法交叉率、變異率難以找到最佳值的問題，增強了遺傳算法的全局尋優(yōu)能力，提高了遺傳算法的尋優(yōu)效率。為得到隱含在實踐教學質(zhì)量評價知識規(guī)則庫中的優(yōu)秀知識規(guī)則，提高實踐教學評價的科學性，將雙種群自適應進化遺傳算法應用于知識規(guī)則挖掘。實例結(jié)果表明，利用改進遺傳算法進行知識規(guī)則挖掘是有效的，能夠快速挖掘出優(yōu)秀的新知識規(guī)則，為實踐教學質(zhì)量評價的公平、公正提供保障。