一種新的元胞網(wǎng)絡(luò)模型

李學(xué)偉，孫有發(fā)，吳今培

一種新的元胞網(wǎng)絡(luò)模型

李學(xué)偉1，孫有發(fā)2，吳今培3

（1. 大連交通大學(xué)，遼寧 大連 116028；2. 廣東工業(yè)大學(xué) 管理學(xué)院，廣東 廣州 510520；3. 五邑大學(xué) 智能技術(shù)與系統(tǒng)研究所，廣東 江門 529020）

用元胞替換傳統(tǒng)人工神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元，以局部連接取代相鄰層級元胞之間的全連接，用規(guī)則演化算法替代BP算法，建立元胞網(wǎng)絡(luò)模型. 設(shè)計(jì)了元胞網(wǎng)絡(luò)的訓(xùn)練過程：內(nèi)嵌的遺傳算法用于尋優(yōu)各元胞狀態(tài)離散化邊界值以及元胞網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu). 以一個紅酒分類基準(zhǔn)數(shù)據(jù)為例，檢驗(yàn)了元胞網(wǎng)絡(luò)的學(xué)習(xí)性能和分類性能，獲得了較為滿意的結(jié)果.

元胞自動機(jī)；神經(jīng)網(wǎng)絡(luò)；遺傳算法；規(guī)則演化；元胞網(wǎng)絡(luò)

元胞自動機(jī)（Cellular Automata，CA）是定義在一個由具有離散、有限狀態(tài)的元胞組成的元胞空間上，并按照一定局部規(guī)則，在離散的時間維上演化的動力學(xué)系統(tǒng). 元胞自動機(jī)不是由嚴(yán)格定義的物理方程或函數(shù)確定，而是用一系列模型構(gòu)造的規(guī)則構(gòu)成[1-3].

神經(jīng)網(wǎng)絡(luò)（Neural Network，NN）是一類知識表達(dá)體系，通過對訓(xùn)練樣本的學(xué)習(xí)，將專家知識以權(quán)值和閾值的形式存儲在網(wǎng)絡(luò)中，并利用網(wǎng)絡(luò)中的信息完成不精確診斷推理，能較好地模擬專家憑經(jīng)驗(yàn)、直覺的推理過程[4-6].

本文將元胞自動機(jī)與神經(jīng)網(wǎng)絡(luò)融合在一起，用元胞替換傳統(tǒng)人工神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元，以局部連接取代相鄰層級元胞之間的全連接，用規(guī)則演化算法替代BP算法，首次提出并建立元胞網(wǎng)絡(luò)（Cellular Network，NN）模型. 由于元胞網(wǎng)絡(luò)是基于規(guī)則的計(jì)算，與其他一些基于解析計(jì)算的智能技術(shù)相比，元胞網(wǎng)絡(luò)將更擅長于解決現(xiàn)實(shí)世界中具有不穩(wěn)定、非線性、不確定性、非結(jié)構(gòu)化以及病態(tài)結(jié)構(gòu)的復(fù)雜決策問題，為人們認(rèn)識和模擬自然界的復(fù)雜現(xiàn)象提供了一種新的方法和工具.

本文提出的元胞網(wǎng)絡(luò)概念，不同于著名文獻(xiàn)[7-8]中的Cellular Neural Network（CNN，元胞或細(xì)胞神經(jīng)網(wǎng)絡(luò)），后者是一種局部互聯(lián)的神經(jīng)元電路設(shè)計(jì)，每個神經(jīng)元有輸入、輸出以及有限種狀態(tài). 也不同于文獻(xiàn)[9-11]中提到的Cellular Automata Neural Network（CA-ANN，元胞自動機(jī)－神經(jīng)網(wǎng)絡(luò)）或者基于神經(jīng)網(wǎng)絡(luò)的元胞自動機(jī)等概念，在該類文獻(xiàn)中，神經(jīng)網(wǎng)絡(luò)是用來為元胞自動機(jī)獲取規(guī)則的.

除此之外，在計(jì)算模式上，元胞網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)也有較大差異. 神經(jīng)網(wǎng)絡(luò)對知識的表示和利用，是把一切問題的特征都變?yōu)閿?shù)字，然后通過設(shè)定的神經(jīng)元函數(shù)，把一切推理都變?yōu)閿?shù)值計(jì)算，即神經(jīng)網(wǎng)絡(luò)實(shí)質(zhì)是一個解析函數(shù)[4-6]；而元胞網(wǎng)絡(luò)以規(guī)則形式來表達(dá)隱含于訓(xùn)練樣本中的分類知識，并直接利用規(guī)則推理出新任務(wù)的分類情況，是規(guī)則運(yùn)算[1-3].

最后，元胞網(wǎng)絡(luò)避免了神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)識別產(chǎn)生的問題. 眾所周知，神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)設(shè)計(jì)，迄今尚無系統(tǒng)的理論或原則可循，大多靠主觀經(jīng)驗(yàn)判斷，或采用實(shí)驗(yàn)方法[4-6]；因而神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)識別問題，也是影響其泛化能力的主要因素和重要原因. 本文構(gòu)建的元胞網(wǎng)絡(luò)，應(yīng)用遺傳算法[14-15]尋優(yōu)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，對復(fù)雜現(xiàn)象的結(jié)構(gòu)識別問題進(jìn)行了有益的探索.

1 元胞網(wǎng)絡(luò)

1.1 輸入層

圖1 元胞網(wǎng)絡(luò)結(jié)構(gòu)

1.2 隱含層

首先計(jì)算映射值

分段離散化方法中的邊界值由遺傳算法逐步尋優(yōu)得到.

1.3 輸出層

2 元胞網(wǎng)絡(luò)的訓(xùn)練和預(yù)測過程

2.1 訓(xùn)練過程

圖2 元胞狀態(tài)數(shù)與邊界值的關(guān)系

元胞網(wǎng)絡(luò)的訓(xùn)練過程包括如下5個步驟.

Step1 初始化元胞網(wǎng)絡(luò)連接. 根據(jù)預(yù)先設(shè)定的各元胞狀態(tài)數(shù)、樣本各指標(biāo)的輸入?yún)^(qū)間以及各元胞的投影算法等，初始化全體元胞狀態(tài)離散規(guī)則中的邊界值.

Step2 將全體訓(xùn)練樣本輸入元胞網(wǎng)絡(luò)，各元胞執(zhí)行預(yù)先設(shè)定的投影算法和分段離散化規(guī)則，輸出相應(yīng)離散狀態(tài)值，并最終確定元胞網(wǎng)絡(luò)的輸出，見圖3. 具體過程分解如下：

圖3 元胞狀態(tài)離散化

1）輸入層各元胞執(zhí)行狀態(tài)離散化規(guī)則，從而原始樣本的指標(biāo)數(shù)據(jù)被離散化；

2）離散化后的樣本指標(biāo)輸入到隱含層，隱含層各元胞執(zhí)行投影算法和分段離散化規(guī)則，得到隱含層的離散化輸出；

3）隱含層的輸出輸入到元胞網(wǎng)絡(luò)的最后一層，輸出層元胞執(zhí)行投影算法和分段離散化規(guī)則，得到元胞網(wǎng)絡(luò)的最終輸出（即某種分類狀態(tài)）.

Step3 計(jì)算該次分類狀態(tài)的準(zhǔn)確度.

Step5 達(dá)到設(shè)定的最大演化代數(shù)或者其他演化停止條件，元胞網(wǎng)絡(luò)訓(xùn)練結(jié)束，輸出“優(yōu)化規(guī)則”網(wǎng)絡(luò).

2.2 預(yù)測過程

元胞網(wǎng)絡(luò)經(jīng)過訓(xùn)練后，確定了網(wǎng)絡(luò)優(yōu)化連接狀態(tài)以及分段離散化規(guī)則所需要的各個邊界值，此時，訓(xùn)練后的元胞網(wǎng)絡(luò)實(shí)質(zhì)上已成“規(guī)則網(wǎng)絡(luò)”，具備了模式識別功能，可以用來預(yù)測新樣本的分類情況等.

預(yù)測操作很簡單，只需將新樣本的指標(biāo)值輸入到元胞網(wǎng)絡(luò)，輸出的狀態(tài)值即是元胞網(wǎng)絡(luò)建議該樣本的分類類別.

3 應(yīng)用

3.1 基準(zhǔn)數(shù)據(jù)描述

本文采用的意大利紅酒基準(zhǔn)分類實(shí)驗(yàn)數(shù)據(jù)①來自加利福尼亞大學(xué)爾灣分校（University of California，Irvine，UC Irvine）國際機(jī)器學(xué)習(xí)論壇，該數(shù)據(jù)是對出產(chǎn)于意大利同一地區(qū)的3個不同品種葡萄酒的化學(xué)成分分析，包含13個成分?jǐn)?shù)據(jù)，它們分別是：1）Alcohol；2）Malic acid；3）Ash；4）Alcalinity of ash；5）Magnesium；6）Total phenols；7）Flavanoids；8）Nonflavanoid phenols；9）Proanthocyanins；10）Color intensity；11）Hue；12）OD280/OD315 of diluted wines；13）Proline. 該基準(zhǔn)分類數(shù)據(jù)共有178例樣本，分3類.

根據(jù)國際機(jī)器學(xué)習(xí)統(tǒng)計(jì)，意大利紅酒分類基準(zhǔn)數(shù)據(jù)被點(diǎn)擊過93 348次，引用此基準(zhǔn)分類數(shù)據(jù)的國際知名文獻(xiàn)有40多篇，其中文獻(xiàn)[16-17]獲得了較為理想的分類結(jié)果：通過規(guī)則化識別分析（RDA）獲得了100%的分類精度，采用二次識別分析（QDA）方法取得99.4%的分類精度，采用線性識別分析（LDA）方法獲得98.9%的分類精度，采用人工神經(jīng)網(wǎng)絡(luò)技術(shù)獲得的分類精度為96.1%. 這些分類方法均采用的是留一法（leave-one-out）.

本文應(yīng)用元胞網(wǎng)絡(luò)于上述紅酒分類基準(zhǔn)實(shí)例，目的是檢驗(yàn)元胞網(wǎng)絡(luò)的學(xué)習(xí)能力和預(yù)測性能等. 與上述“留一法”不同的是，本文采取對半分基準(zhǔn)數(shù)據(jù)方法：一半用于訓(xùn)練，另一半用于預(yù)測. 從理論上講，本文采用的“對半分”方法的分類程度要大于留一法.

3.2 元胞網(wǎng)絡(luò)的初始拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)

3.3 訓(xùn)練

設(shè)定遺傳算法總?cè)阂?guī)模為50，演化代數(shù)為100次，交叉概率為0.8，變異概率為0.10，圖4是執(zhí)行遺傳算法1次的演化過程圖. 本次元胞網(wǎng)絡(luò)訓(xùn)練后輸出的邊界值見表3，網(wǎng)絡(luò)連接狀態(tài)的優(yōu)化過程見圖4a）.

表3 元胞網(wǎng)絡(luò)訓(xùn)練結(jié)束后輸出的優(yōu)化邊界值

圖4a）顯示，隨著演化的進(jìn)展，整個元胞網(wǎng)絡(luò)的連接狀態(tài)在不斷調(diào)整；群體的平均適應(yīng)值以及群體中最佳個體的適應(yīng)值也逐步得到提升，見圖4b）. 這充分展示了演化算法的優(yōu)良性能，也反應(yīng)了本文元胞網(wǎng)絡(luò)的學(xué)習(xí)性能.

3.4 預(yù)測

用圖4所示的訓(xùn)練后的元胞網(wǎng)絡(luò)對余下的一半樣本進(jìn)行分類測試，經(jīng)檢驗(yàn)，元胞網(wǎng)絡(luò)的分類準(zhǔn)確度為94.4%.

4 結(jié)論

本文首次提出元胞網(wǎng)絡(luò)概念，并建立元胞網(wǎng)絡(luò)模型，設(shè)計(jì)了訓(xùn)練過程，用遺傳算法尋優(yōu)元胞網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及元胞狀態(tài)離散化邊界值. 應(yīng)用于紅酒分類國際基準(zhǔn)實(shí)例，元胞網(wǎng)絡(luò)取得了較滿意的分類精確度.

[1] WOLFRAM S. Cellular automata as models of complexity[J]. Nature, 1984, 311(4): 419-424.

[2] WOLFRAM S. Theory and application of cellular automata[M]. Singapore: World Scientific, 1986.

[3] WOLFRAM S. A new kind of science[M]. Champaign Illinois: Wolfram Media, 2002.

[4] BISHOP C M. Neural networks for pattern recognition[M]. Oxford: Oxford University Press, 1996.

[5] MITCHELL T M. Machine learning[M]. New York: McGraw-Hill, 1997.

[6] RUMELHART D, WIDROW B, LEHR M. The basic ideas in neural networks[J]. Communications of the ACM, 1994, 37(3): 87-92.

[7] CHUA L O, YANG L. Cellular neural networks: theory[J]. IEEE Trans Circuits Syst, 1988a, 35(10): 1257-1272.

[8] CHUA L O, YANG L. Cellular neural networks: applications. IEEE Trans Circuits Syst, 1988b, 35(10): 1273-1290.

[9] LI Xia. YEH A G O. Neural-network-based cellular automata for simulating multiple land use changes using GIS[J]. International Journal of Geographical Information Science, 2002, 16(4): 323-343.

[10] YEH A G O, LI Xia. Integration of neural networks and cellular automata for urban planning[J]. Geo-Spatial Information Science, 2004, 7(1): 6-13.

[11] 徐昔保，楊桂山，張建明. 基于神經(jīng)網(wǎng)絡(luò)CA的蘭州城市土地利用變化情景模擬[J]. 地理與地理信息科學(xué)，2008, 24(6): 80-84.

[12] HUANG S H, XING Hao. Extract intelligible and concise fuzzy rules from neural networks[J]. Fuzzy Sets and Systems, 2002, 132(2): 233-243.

[13] ZADEH L A. Fuzzy logic, neural networks, and soft computing[J]. Communications of the ACM, 1994, 37(3): 77-84.

[14] 孫有發(fā)，張成科，高京廣，等. 帶反饋的混沌并行GA及其在非線性約束優(yōu)化中的應(yīng)用[J]. 計(jì)算機(jī)學(xué)報，2007, 30(3): 424-430.

[15] 孫有發(fā)，陳世權(quán)，吳今培. 一種非一致性的自適應(yīng)遺傳算法與應(yīng)用[J]. 系統(tǒng)工程，2002, 20(62): 82-86.

[16] AEBERHARD S, COOMANS D, VEL O de. Comparison of classifiers in high dimensional settings, Tech Rep no 92-02, 1992, Dept of Computer Science and Dept of Mathematics and Statistics, James Cook University of North Queensland.

[17] AEBERHARD S, COOMANS D, VEL O de. The classification performance of RDA. Tech Rep no 92-01, 1992, Dept of Computer Science and Dept of Mathematics and Statistics, James Cook University of North Queensland.

① http://archive.ics.uci.edu/ml/datasets/Wine.

A New Kind of Cellular Network

LIXue-wei1, SUNYou-fa2, WUJin-pei3

(1. Dalian Jiaotong University, Dalian 116028, China; 2. School of Management, Guangdong University of Technology, Guangzhou 510520, China; 3. Institute of Intelligence Technology and Systems, Wuyi University, Jiangmen 529020, China)

A novel concept of cellular network is proposed. The cellular network is constructed based on the traditional artificial neural network by replacing the neurons with cells, replacing the full connections among cells with partial connections, and replacing the back-propagation algorithm with rule-evolution algorithm. The training process of cellular network is also designed. The embedded genetic algorithm is to search for the optimal parameters and structures of the network. Finally, the cellular network is applied to a benchmark data set (classification of Italy’s red wine), and is validated to be of good performances of learning and predicting.

cellular automata; neural network; genetic algorithm; rule evolution; cellular network

1006-7302（2011）04-0014-08

TP393.01

A

2011-07-20

國家自然科學(xué)基金資助項(xiàng)目（No.70571006；No.70801019）

李學(xué)偉（1962—），男，河南宜陽人，教授，博士，博士生導(dǎo)師，研究方向?yàn)楣芾砜茖W(xué)與復(fù)雜系統(tǒng)決策理論方法等.