基于遺傳算法的城市公交服務質量評價知識規則挖掘方法

摘要：城市公共交通服務質量評價知識規則是城市公共交通企業進行服務質量評價的重要依據，優質、合理的評價知識規則將使服務質量評價更加公正、更加客觀。本文在分析城市公共交通服務質量評價指標體系的基礎上，將一種改進的遺傳算法用于城市公共交通服務質量評價價的知識規則挖掘，提出一種基于遺傳算法的城市公共交通服務質量評價知識規則挖掘方法，闡述算法的實現途徑。實例表明，該方法在進行知識規則挖掘時是完全可行的、有效的。

關鍵詞：知識規則挖掘；城市公共交通；服務質量評價；遺傳算法

中圖分類號：TP301.6 文獻標識碼：A

1引言

知識規則挖掘就是從大量的、不完全的、有噪聲的知識規則中，提取隱含在其中的、人們事先不知道的有用的知識規則的過程。知識規則挖掘方法[1，2，3]有多種，如機器學習、決策樹、神經網絡、粗糙集方法、遺傳算法等。在這些方法中，遺傳算法由于具有高度的魯棒性和極佳的全局搜索能力而倍受眾多學者的青睞。在城市公共交通服務質量評價知識規則體系中，由于評價指標較多，在進行知識規則挖掘時，使用遺傳算法尤為有效。利用遺傳算法進行城市公共交通服務質量評價知識規則挖掘，就是在已有的知識規則的基礎上進一步進行優化，得到隱含在知識規則庫中的、更為滿意的、新的知識規則。

2城市公共交通服務質量評價指標體系構建

城市公共交通服務質量可以從硬件和軟件兩個大的方面進行評價。硬件方面包括道路公共交通網絡和公交企業本身的設施投入；軟件方面則主要指道路交通通行的實際水平與公交企業的軟性服務。上述方面還可以進一步細分，直至一些基礎性的指標。結合綜合評價加指標體系建立的方法，建立城市公共交通服務質量評價指標體系[4-6]。評價指標體系包括四個方面：公共交通網絡、公交企業硬性投入、公共交通通行服務水平、公交企業軟性服務，具體評價指標有15個，如圖1所示。

遺傳算法是模擬生物界自然選擇和自然遺傳機制進化過程來求解復雜問題的全局隨機搜索算法[7，8]，它以編碼空間代替問題空間，以適應度函數為評價依據，以編碼群體為進化基礎，以對群體中個體位串的遺傳操作實現選擇和遺傳機制，建立起一個迭代過程。在這一過程中，通過隨機重組編碼位串中重要的基因，使新一代的位串集合優于老一代的位串集合，群體的個體不斷進化，逐漸接近最優解，最終達到求解問題的目的。

由于傳統遺傳算法存在收斂速度慢、容易出現早熟收斂等缺點[9]，本文采用文獻[10]中的改進遺傳算法（IGA），這種改進遺傳算法的工作流程如圖2所示。

4.3遺傳算子

在本文使用的改進遺傳算法中，遺傳算子包括選擇算子、助長算子、交叉算子和變異算子。選擇算子采用兩代競爭排序的選擇方法來對遺傳個體進行優選，遺傳個體被區分為雄性和雌性兩種不同的性別，把父代與子代的所有雄性個體與雌性個體分別進行重新排序，再按群體規模N分別從排序后的雄性個體集與雌性個體集中截取前N/2個優秀的個體進入匹配池，作為交叉操作的對象。助長算子用來對種群中的個體進行一定概率下的助長，助長操作在選擇操作之后及配對操作之前進行，本文是采用基于個體適應度的助長。在交叉操作中，同性別個體之間是不能進行配對的，雄性個體只能同雌性個體進行配對，配對是按個體優劣順序進行的，個體配對之后還要進行親緣關系的檢測，以保證個體之間的繁殖屬于嚴格的遠緣繁殖。在二進制編碼方式下，變異操作就是以很小的變異概率從群體中隨機選取若干個體，對于選中的個體又隨機選取表現型編碼中的某一位或多位進行數碼翻轉，即將1變為0或0變為1。

4.4新知識規則的檢驗

遺傳算法運行結束后，要對挖掘出的新知識規則的有效性進行檢驗。一方面要檢驗新知識規則是否被知識規則庫中已有的規則所包含，如果被已有的規則所包含，則新知識規則無效；另一方面是檢驗新知識規則是否與知識規則庫中已有的規則相矛盾，如果與已有的規則相矛盾，則新知識規則同樣無效。無效的新知識規則將被剔除，有效地新知識規則將被加入知識規則庫中。

5實例

一城市公共交通服務質量評價知識規則庫（部分知識規則）如表1所示，這個知識規則庫即為測試數據集。表1的知識規則編碼及適應度值如表2所示。

這二條新的有效的知識規則將被加入到城市公共交通服務質量評價知識規則庫中，使知識規則庫得以更新。

6結論

本文將一種改進的遺傳算法用于城市公共交通服務質量評價的知識規則挖掘，提出了一種基于遺傳算法的城市公共交通服務質量評價知識規則挖掘方法。實例表明，遺傳算法在進行知識規則挖掘時是完全有效的，能夠得到比知識規則庫中已有的一些知識規則更優的知識規則。這為知識規則挖掘提供了一種重要途徑。

參考文獻

[1]刁力力. 數據挖掘與組合學習[J].計算機科學，2001， 28（7）：73-78.

[2]Dasarathy， B.V Nearest Neighbor（NN）Norms. NN Pattern Classification Techniques[M]. Washington， D.C.： IEEE Computer Society， 1991.

[3]ZIARKO W. Rough sets， Fuzzy Sets and Knowledge Discovery[J]. New York： Springer-Verlag， 1994.

[4]邵祖峰. 基于神經網絡的城市公共交通服務質量評價[J]. 城市交通，2005，7（4）：178-180.

[5]張麗花， 張好智， 楊小寶. 基于乘客出行鏈的公共交通服務質量評價研究[J]. 公路與汽車，2011，7（4）：48-51.

[6]邵祖峰. 城市公共交通服務質量評價神經網絡模型[J]. 城市交通，2006，4（6）：38-41.

[7]雷英杰，張善文，李續武，等. MATLAB遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社，2005.

[8]王小平，曹立明. 遺傳算法——理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.

[9]Thomas Strassner， Markus Busold， Wolfgang A. Herrmann， MM 3 parametrization of four and fivecoordinated rhenium complexes by a genetic algorithm[J].Journal of Computational chemistry，Vol.23， 2002.

[10]嚴太山，陶永芹，崔杜武. 基于人類繁殖現象的遺傳算法研究[J]. 計算機工程與應用，2007，43（33）：78-81.