雙種群自適應遺傳算法及其在知識挖掘中應用

嚴太山，王 欣

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

0 引言

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

1 雙種群自適應遺傳算法

1.1 算法思想

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

1.2 遺傳操作

1.2.1 選擇操作

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

1.2.2 交叉操作

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

1.2.3 變異操作

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

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

1.3 算法流程

DPAGA算法流程如圖1所示。

圖1 DPAGA算法流程

2 基于DPAGA的實踐教學質量評價知識規則挖掘方法

2.1 實踐教學質量評價指標體系構建

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

圖2 實踐教學質量評價指標體系

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

2.2 知識規則表示與編碼

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

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

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

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

圖3 知識規則個體編碼結構

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

2.3 知識規則評價與檢驗

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

（1）正確度

（2）覆蓋度

（3）可信度

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

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

3 算例

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

表2 實踐教學質量評價知識規則庫

表3 知識規則編碼及其適應度評價

我們應用改進遺傳算法DPAGA分別進行知識規則挖掘，DPAGA參數設置為：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產生的新知識規則有效性，選取DPAGA第5次迭代運算后得到的結果，此時挖掘出的新知識規則個體編碼如表4所示，相應的知識規則個體如表5所示。在DPAGA算法挖掘出的八條新知識規則中，經過有效性檢驗，發現其中兩條被知識規則庫中的現有規則包含了，它們分別是新規則N2被知識規則庫中的現有規則3包含，新規則N6被知識規則庫中的現有規則16包含；另有兩條與知識規則庫中的現有規則相矛盾，它們分別是新規則N5與知識規則庫中的現有規則14相矛盾，新規則N7與知識規則庫中的現有規則6相矛盾，這四條規則是無效的知識規則，應被刪除。只有規則N1、N3、N4和N8是有效的新知識規則，按照上述適應度評價方法計算得到N1、N4的適應度值均為0.961450，N3的適應度值為0.914062，N8的適應度值為0.726775。

表4 新知識規則編碼

表5 新知識規則

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

4 結語

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