劉開健，何碧貴，毛安定，孫幸福

(1.長江大學 電子信息學院，湖北 荊州434023；2.重慶電子工程職業(yè)學院，重慶401331；3.中國人民解放軍77538部隊政治處，西藏拉薩850000)

噪聲混沌神經(jīng)網(wǎng)絡在TSP中的應用研究

劉開健1，何碧貴2，毛安定3，孫幸福3

(1.長江大學 電子信息學院，湖北 荊州434023；2.重慶電子工程職業(yè)學院，重慶401331；3.中國人民解放軍77538部隊政治處，西藏拉薩850000)

分析了NCNN(噪聲混沌神經(jīng)網(wǎng)絡)模型的幾個重要參數(shù)對系統(tǒng)性能的影響，并對其進行了優(yōu)化。仿真結(jié)果表明，優(yōu)化的算法能成功解決旅行商問題，比傳統(tǒng)的依靠經(jīng)驗選擇參數(shù)的方法更有效，在收斂速度同解的質(zhì)量之間取得了很好的折中。

NCNN；TSP；收斂速度；解的質(zhì)量

1 引言

TSP是一個典型的NP-hard（非確定性多項式）完全問題，自從1985年 Hopfield和Tank用 Hopfield人工神經(jīng)網(wǎng)絡(HNN)對其進行有效求解以來[1]，人工神經(jīng)網(wǎng)絡被認為是解決復雜組合優(yōu)化問題的有效方法之一[1-4]。但HNN在穩(wěn)健性、優(yōu)化率以及收斂速度等方面仍然存在許多問題，因此，人們提出了許多改進方法。Wang等綜合了隨機模擬退火（SSA）和混沌模擬退火（CSA）算法的優(yōu)點，提出了一種新的隨機混沌模擬退火（SCSA）算法，即噪聲混沌神經(jīng)網(wǎng)絡[2]。該算法具有十分復雜的混沌動力學特點，利用其遍歷性和隨機性進行搜索，同時引入隨機噪聲，再由退火策略控制混沌動態(tài)和噪聲逐漸消失，保證網(wǎng)絡能有效收斂和跳出局部最優(yōu)，從而找到最優(yōu)解。該算法的參數(shù)設置非常靈活，不同的優(yōu)化問題具有不同的權(quán)重因子，因此，本文就NCNN的參數(shù)設置問題進行探討和優(yōu)化。

1.1 TSP問題描述

旅行商問題 （TSP）是指已知多個城市之間的相互距離，如：現(xiàn)有一位推銷員必須遍訪每個城市，并且每個城市只訪問一次，最后必須返回出發(fā)城市。如何安排訪問次序，才能使其旅行路線的總長度最短。這是一個典型的組合優(yōu)化問題，該問題描述如下：

其中，x和y表示城市，i和j表示訪問次序，dx,y表示x城市和y城市之間的距離。vx,i表示訪問交換矩陣，即vx,i=1表示第i次訪問x城市，否則vx,i=0。（1）式表示TSP問題的目標函數(shù)，即總閉合路徑最短；（2）式表示行約束，即每個城市最多而且只能被訪問一次；（3）式表示列約束，即每次只訪問一個城市；（4）式表示N個城市一共只能被訪問N次。

2 NCNN的TSP實現(xiàn)

2.1 能量函數(shù)

由HNN演變而來的NCNN的能量函數(shù)表示如下：

其中正常數(shù)Ae、Be、Ce和De為權(quán)重因子，E中前三項分別為（2）-（4）式對應的約束項，當系統(tǒng)收斂至平衡點后，這三項為0。表示每行每列恰有一個1，且矩陣V的各元素之和為N，表示N個城市恰被訪問N次。最后一項表示目標函數(shù)（1）式，當系統(tǒng)收斂至穩(wěn)定狀態(tài)后，該項為正的最小值，即使NCNN繼續(xù)運算，該項也不再減小。

2.2 動能方程

由系統(tǒng)穩(wěn)定條件推出應用于 TSP問題的噪聲混沌神經(jīng)網(wǎng)絡系統(tǒng)的動力學演化方程如下：

其中，Ux,i(t)和Vx,i(t)分別為t時刻神經(jīng)元xi的內(nèi)部狀態(tài)輸入和輸出。其關系由S函數(shù)表示如下：

u0為神經(jīng)元激活函數(shù)的增益因子。

為了在計算機上運行該系統(tǒng)以求得最優(yōu)解，我們首先用歐拉方法建立(6)式的離散時間模型，然后加入負反饋產(chǎn)生暫態(tài)混沌動力，最后加入白噪聲獲得NCNN的離散時間模型如下：

其中，λ為抑制因子，α為縮放因子且＞0，I0是一個正常數(shù)，zx,i(t)為負反饋聯(lián)接權(quán)值，nx,i(t)是隨機噪聲，取值范圍是[-Am,Am]，β1和 β2是退火參數(shù)。

為了加速系統(tǒng)收斂，本文采用神經(jīng)元輸出矩陣的平均值作為閾值去激活神經(jīng)元函數(shù)，使本來連續(xù)的輸出離散化，盡快靠近0和1。

3 仿真結(jié)果分析

為了便于比較，本文同樣采用Hopfield-tank模型[1]，用MTTLAB7.6進行仿真。為神經(jīng)元激活函數(shù)的增益因子，是將每個神經(jīng)元的內(nèi)部輸入映射為輸出，直接影響到整個系統(tǒng)的各方面性能，所以該參數(shù)的選擇至關重要。在很多文獻中依靠經(jīng)驗選擇，若太大，神經(jīng)元輸出快速收斂至0或1，近似離散函數(shù)，不利于混沌遍歷搜索，易陷入局部最小值；若太小，搜索空間增大，但收斂速度變慢，如圖1所示。所以本文基于系統(tǒng)收斂效率和解的質(zhì)量的折中考慮，采用u0=10，這與前期文獻有很大差別。

圖1 不同激活函數(shù)的仿真效果

圖2 Hopfield-tank模型的最優(yōu)解

為了使負反饋對下次的神經(jīng)元輸入有足夠的影響，同時為了能跳出局部最優(yōu)，使系統(tǒng)能收斂到全局最優(yōu)值，隨機噪聲也應該被加大，這樣也有利于快速收斂。所以本文改變其常用值，將其設置為z0=0.85，Am=2。相應地，兩個退火因子也同時被增加，但不能設置過大，否則優(yōu)化率將大大降低，這里將其設置為β1=0.02,β2=0.02。本文NCNN模型的其他參數(shù)選擇如下：α=0.05,I0=0.65,λ=0.95。四個權(quán)重因子分別設置為：Ae=3.5,Be=3.5,Ce=2.4,De=4.3。

將本文優(yōu)化的參數(shù)用于Hopfield-tank模型，仿真1000次，每次最大迭代500次，仿真結(jié)果如圖2所示。該系統(tǒng)平均迭代67次就能收斂到最優(yōu)值，明顯高于文獻[2]中的124次。優(yōu)化率為96.2%，略低于文獻[2]中的99.4%。而且可以看到改進算法在混沌和噪聲消失之前，系統(tǒng)已經(jīng)收斂到穩(wěn)定狀態(tài)，大大提高了收斂速度；在系統(tǒng)收斂速度和解的質(zhì)量之間取得了很好的折中。另外，我們隨機選擇了No(3,5)神經(jīng)元，畫出了它的內(nèi)部狀態(tài)（輸入）U(3,5)和神經(jīng)元輸出V(3,5)，可以看出V經(jīng)過離散處理后，與文獻[2]中的V值已大大的不同。同時我們也畫出了能量函數(shù)E的變化曲線，由于離散化的處理，它已經(jīng)不再是很規(guī)則的梯度下降，但總的趨勢還是呈下降趨勢，直至系統(tǒng)收斂。

4 結(jié) 論

本文分析了NCNN的幾個重要參數(shù)對求解最優(yōu)值的影響，通過對其常用數(shù)值的調(diào)整，將其成功應用于TSP問題。仿真結(jié)果表明，優(yōu)化的算法大大地提高了系統(tǒng)收斂速度，而且也獲得了較高的優(yōu)化率，在收斂效率和解的質(zhì)量之間取得了較好的折中。

[1]J.J.Hopfield and D.W.Tank, “Neural computation of decisions in optimization problems”,Biol.Cybern.,1985，52（3）：141-152.

[2]L.Wang,S.Li,F.Tian,and X.Fu,“A noisy chaotic neural network forsolvingcombinatorialoptimizationproblems:Stochastic chaotic simulated annealing”,IEEE Trans.Syst.,Man,Cybern.,Part B:Cybern.,2004，34（5）：2119-2125.

[3]閻平凡.神經(jīng)網(wǎng)絡與模擬進化計算[M]．北京：清化大學出版社，2000.

[4]李敏，吳浪，張開碧．求解旅行商問題的幾種算法的比較研究[J]．重慶郵電大學學報，2008，20(5)：525-528．

TP183

A

1674－5787（2011）04－0160－02

2011-06-15

劉開健(1981—)，女，重慶人，長江大學，講師，主要研究方向：人工神經(jīng)網(wǎng)絡技術；何碧貴（1980—），女，重慶電子工程職業(yè)學院，講師。

責任編輯 王榮輝