高 勇，李存華

（淮海工學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 連云港 222005）

0 引言

一個(gè)圖，如果可以將它畫(huà)在平面上，使它的邊僅在端點(diǎn)上才能相交，則稱(chēng)此圖為可平面圖。如果一個(gè)可平面圖的每一個(gè)面都是三角形，則它是最大可平面圖。地圖的四著色問(wèn)題最終可歸結(jié)到最大可平面圖的頂點(diǎn)四著色問(wèn)題，這一點(diǎn)，圖論的眾多文獻(xiàn)中都有介紹［1］，本文不再論述。最大可平面圖的頂點(diǎn)四著色，當(dāng)頂點(diǎn)數(shù)較多時(shí)，計(jì)算量太大，人工著色的辦法根本不可能，而利用神經(jīng)網(wǎng)絡(luò)方法進(jìn)行編程是可行的。

1 神經(jīng)網(wǎng)絡(luò)方法

人工神經(jīng)網(wǎng)絡(luò)方法是一種模仿動(dòng)物腦神經(jīng)網(wǎng)絡(luò)某些功能的數(shù)值計(jì)算方法。人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)由神經(jīng)元和神經(jīng)元間的連接權(quán)組成，多數(shù)類(lèi)型的神經(jīng)網(wǎng)絡(luò)將神經(jīng)元以層的形式組織在一起，常見(jiàn)的神經(jīng)元間的連接權(quán)以層間神經(jīng)元的連接權(quán)為主。目前應(yīng)用最廣泛的反向傳播神經(jīng)網(wǎng)絡(luò)，其結(jié)構(gòu)由輸入層、輸出層和至少一個(gè)隱含層，以及層間連接權(quán)組成［2］。反饋網(wǎng)絡(luò)有多種，霍普菲爾德網(wǎng)絡(luò)是單層對(duì)稱(chēng)全反饋網(wǎng)絡(luò)，根據(jù)其激活函數(shù)的選取不同，可分為離散型的霍普菲爾德網(wǎng)絡(luò)（DHNN）和連續(xù)型的霍普菲爾德網(wǎng)絡(luò)（CHNN）。DHNN的激活函數(shù)為二值型的，其輸入、輸出為｛－1，1｝的反饋網(wǎng)絡(luò)，主要用于聯(lián)想記憶；CHNN的激活函數(shù)為連續(xù)可微的單調(diào)上升函數(shù)，主要用于優(yōu)化計(jì)算（如圖1所示）。

圖1 霍普菲爾德網(wǎng)絡(luò)結(jié)構(gòu)示意圖Fig.1 Schematic diagram of Hopfield neural network

霍普菲爾德網(wǎng)絡(luò)是和電子模擬線(xiàn)路對(duì)應(yīng)的，其中每一個(gè)神經(jīng)元都有一樣的電路模型。它的工作原理有一定的動(dòng)態(tài)數(shù)學(xué)方程，其能量函數(shù)可正可負(fù)，但負(fù)向有界，是廣義的李雅普諾夫函數(shù)，如圖1和圖2所示。

圖2 神經(jīng)元電路模型示意圖（第i個(gè)）Fig.2 Schematic diagram of neuron circuit model（i）

Rij為第j個(gè)輸入與第i個(gè)輸入之間的連接導(dǎo)納，Wij＝1／Rij；ri與ci分別為第i個(gè)運(yùn)算放大器的電阻和輸入電容；Ii為外加恒定電流。調(diào)節(jié)其他系數(shù)，可忽略余項(xiàng)。V是輸入矢量，U是狀態(tài)矢量，O是輸出矢量。

輸出：

f（ui）＝ （1＋tanh（λ×ui））／2；

動(dòng)態(tài)方程：

dui／dt＝ （－ui／qi＋ ∑Wijvj＋I(xiàn)i）／ci，1／qi＝1／ri＋ ∑Wij；

能量函數(shù)：

E＝－（∑Wijvivj）／2－∑viIi＋余項(xiàng)。

2 四著色問(wèn)題的CHNN的網(wǎng)絡(luò)設(shè)計(jì)

2.1 反饋網(wǎng)絡(luò)的穩(wěn)定狀態(tài)

反饋網(wǎng)絡(luò)能夠表現(xiàn)出非線(xiàn)性動(dòng)力學(xué)系統(tǒng)的動(dòng)態(tài)特性，它具有如下的主要特性。

（1）網(wǎng)絡(luò)系統(tǒng)具有若干個(gè)穩(wěn)定的平衡狀態(tài)。當(dāng)網(wǎng)絡(luò)從某一個(gè)初始狀態(tài)開(kāi)始運(yùn)動(dòng)后，網(wǎng)絡(luò)系統(tǒng)總可以收斂到某一個(gè)穩(wěn)定的平衡狀態(tài)。

（2）系統(tǒng)穩(wěn)定的平衡狀態(tài)可以通過(guò)設(shè)計(jì)網(wǎng)絡(luò)的權(quán)值而被存儲(chǔ)到網(wǎng)絡(luò)中［3］。

假設(shè)一個(gè)最大可平面圖已被四著色成功，那么它的每一個(gè)頂點(diǎn)顏色與其相鄰的頂點(diǎn)顏色都不相同，這是一種穩(wěn)定狀態(tài)，其他情況可視為不穩(wěn)定狀態(tài)。因此，頂點(diǎn)顏色狀態(tài)矩陣需要滿(mǎn)足3個(gè)條件：

（1）每列只能有一個(gè)是1。

（2）1的總數(shù)必須與頂點(diǎn)數(shù)相符。

（3）若某點(diǎn)的一個(gè)顏色模式為1，則與其連接的所有頂點(diǎn)的這個(gè)模式都不能為1。示例見(jiàn)表1。

表1 頂點(diǎn)顏色狀態(tài)表Table 1 Model table of vertex color

2.2 神經(jīng)元設(shè)計(jì)

對(duì)于m個(gè)頂點(diǎn)，需要4m個(gè)神經(jīng)元，設(shè)n＝4m，則描述CHNN的動(dòng)態(tài)方程如下。

其中，T為CHNN網(wǎng)絡(luò)連接矩陣，λ為增益參數(shù)，τ是各神經(jīng)元的時(shí)間常數(shù)。

2.3 網(wǎng)絡(luò)設(shè)計(jì)

設(shè)G為最大平面圖的連接矩陣；g（a，b）＝0表示第a個(gè)頂點(diǎn)與第b個(gè)頂點(diǎn)不連接；g（a，b）＝1表示第a個(gè)頂點(diǎn)與第b個(gè)頂點(diǎn)連接。則T設(shè)計(jì)為

其中，Col為列限制系數(shù)常量，A為全局限制系數(shù)常量，D為平面圖結(jié)構(gòu)限制系數(shù)常量。a，b取1到m的值；a＝b意味同一頂點(diǎn)，δab＝1；a≠b，δab＝0。x，y取1到4的值；x＝y(tǒng)意味同一顏色，δxy＝1；x≠y，δxy＝0。

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)程序

程序主要由以下5個(gè)部分組成。

（1）隨機(jī)生成最大可平面圖。

（2）網(wǎng)絡(luò)中有關(guān)矩陣的生成。

（3）迭代計(jì)算。

（4）根據(jù)計(jì)算結(jié)果對(duì)頂點(diǎn)進(jìn)行染色。

（5）參數(shù)設(shè)定模塊。參數(shù)設(shè)定模塊主要迭代計(jì)算的偽代碼如下。

初始化：① 按公式（5）設(shè)置連接矩陣；② 以零設(shè)置輸入和狀態(tài)值。

cok：＝false；／／cok表示著色是否成功

dt：＝0.01；

while（idx＜nMax）do begin

／／nMax為迭代次數(shù)限制

／／狀態(tài)的計(jì)算；tt，II，dt分別對(duì)應(yīng)參數(shù)τ，I，Δt

for k：＝1to 4＊DDN do begin

／／DDN為實(shí)際頂點(diǎn)數(shù)

tmp：＝0；

for j：＝1to 4＊DDN do

tmp：＝tmp＋T［k，j］＊V［j］；

U［k］：＝U［k］＋

（tmp－U［k］／tt＋I(xiàn)I）＊dt；／／參照公式（4）end；

／／利用激活函數(shù)計(jì)算反饋；lmd為參數(shù)λ

for k：＝1to 4＊DDN do begin

V［k］：＝（1＋tanh（lmd＊U［k］））／2；

／／參照公式（2）

end；

／／頂點(diǎn)顏色的計(jì)算；CoT為頂點(diǎn)顏色狀態(tài)表

for i：＝1to DDN do

for j：＝1to 4do

CoT［j，i］：＝V［（j－1）＊DDN＋i］；

for k：＝1to DDN do begin

max：＝－1；maxi：＝0；

for i：＝1to 4do

if CoT［i，k］＞max then begin

max：＝F［i，k］；maxi：＝i；

end；

Se［k］：＝maxi；／／頂點(diǎn)所著顏色（次號(hào)）

end；

／／判斷是否著色成功

i：＝1；

while i＜＝DDN do begin

j：＝1；

while j＜＝DDN do begin

if（G［i］［j］＝1）and（Se［i］＝Se［j］）then

break；

j：＝j(luò)＋1；

end；

if j＜＝DDN then break；

i：＝i＋1；

end；

if i＞DDN then break；

idx：＝idx＋1；

end；

cok：＝（idx＜nMax）；／／cok為 True表示著色成功。

3.2 實(shí)驗(yàn)參數(shù)和著色示例

在實(shí)驗(yàn)中，隨機(jī)產(chǎn)生了100個(gè)頂點(diǎn)的最大可平面圖，使用表2的最后一行數(shù)據(jù)為運(yùn)行參數(shù)，經(jīng)過(guò)大約20 599次迭代以后，成功染色，運(yùn)行時(shí)間大約為180s。圖3中的空?qǐng)A圈、實(shí)心圓圈、空方塊、實(shí)心方塊分別代表4種不同的顏色。在參數(shù)表中，參數(shù)Col，A和D用于網(wǎng)絡(luò)矩陣T的初始化計(jì)算；參數(shù)λ，τ，和I用于迭代計(jì)算［4］。U和V的初始值可以為零。本程序使用Delphi2010實(shí)現(xiàn)，如圖3所示為實(shí)驗(yàn)著色的結(jié)果。

表2 運(yùn)行參數(shù)表Table 2 Running parameter table

圖3 100個(gè)頂點(diǎn)的著色結(jié)果Fig.3 Coloring result of one hundred vertexes

4 結(jié)論

霍普菲爾德神經(jīng)網(wǎng)絡(luò)已成功地應(yīng)用于多種場(chǎng)合，主要集中于圖像處理、語(yǔ)音處理、信號(hào)處理、數(shù)據(jù)查詢(xún)、容錯(cuò)計(jì)算、模式分類(lèi)、模式識(shí)別等［5］。霍普菲爾德認(rèn)為，在系統(tǒng)的運(yùn)動(dòng)過(guò)程中，其內(nèi)部?jī)?chǔ)存的能量隨著時(shí)間的增加而逐漸減少，當(dāng)運(yùn)動(dòng)到平衡狀態(tài)時(shí)系統(tǒng)的能量耗盡或變得最少，那么系統(tǒng)自然在此平衡狀態(tài)穩(wěn)定下來(lái)。利用能量函數(shù)概念，可以設(shè)計(jì)CHNN進(jìn)行優(yōu)化計(jì)算，利用其并行性可解決計(jì)算中的“指數(shù)爆炸”問(wèn)題。典型例子是TSP問(wèn)題、旅行商問(wèn)題。本文探討更復(fù)雜的四著色問(wèn)題，希望能給圖論研究帶來(lái)一點(diǎn)啟示。

［1］ 楊炳儒.圖論概要［M］.天津：天津科學(xué)技術(shù)大學(xué)出版社，1990.

［2］ HAYKIN S.神經(jīng)網(wǎng)絡(luò)原理［M］.北京：機(jī)械工業(yè)出版社，2004.

［3］ 魏海坤.神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)的理論與方法［M］.北京：國(guó)防工業(yè)出版社，2005.

［4］ TALAVAN P M，JAVIER.Parameter setting of the Hopfield network applied to TSP［J］.Neural Networks，2002，15（1）：363－373.

［5］ KURITA N，F(xiàn)UNAHASHI K－I.On the Hopfield neural networks and mean field theory［J］.Neural Networks，1996，9（9）：1531－1540.