自组织神经网络求解TSP问题

自组织特征映射网络（SOFM）求解TSP问题

组长：袁滨

组员：杨涛，徐丽丽，张冰，殳晶莹，许才华，郑彩萍

一、 旅行商问题

旅行商问题(Traveling Salesman Problem，简称TSP). 商品的推销员打算从驻地出发遍访他要去的每个城市，并且每个城市只能访问一次，最后必须返回出发城市。问如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？

旅行商问题TSP是一个典型的组合优化问题，并且是一个NP完全问题，其可能Hamilton圈的数目是顶点的数目n的指数函数，所以一般很难精确地求出其最优解。所谓组合优化问题，是指在离散的，有限的数学结构上，寻找一个满足给定条件，并使其目标函数值达到最小或最大的解。一般来说，组合优化问题通常带有大量的局部极值点，通常是非线性的NP完全问题。其最先起源于一个旅行商要访问他所有的客户，要发现一条最短的路线。用用图论的术语来说，旅行商问题就是在赋权完全图上找一个权最小的Hamilton圈。但是，首先从应用上来说，很多实际应用问题，如印制电路板的、连锁店的货物配送路线等，经简化的处理后，均可转化为旅行商问题TSP。由于旅行商问题的重要应用价值，因而对旅行商问题的算法研究自然是一个无法回避的问题;其次，从理论上来说，它的计算复杂性研究在形成NP完全理论中起到奠基作用。今天，由于电子计算机科学技术的进展，这个古老问题的算法研究又重新注入了新的活力，旅行商问题研究的新思路、新方法、新成果必将丰富NP完全理论的内涵，促进NP完全理论的发展。

二、神经网络算法与优化计算

神经网络的应用已经渗透到多个领域，如智能控制、模式识别、信号处理、计算机视觉、优化计算、知识处理、生物医学工程等。利用神经网络进行优化计算，采用的模型一般包括Hopfield神经网络、混沌神经网络和波尔兹曼机（类似模拟退火）等。TSP是典型的NP-难解问题，它对应的判定问题属于NPC类。由于这个问题具有许多实际应用背景，所以寻求解决它的高效近似算法就成为学术界的研究热点。可以利用自组织特征映射网络（SOFM）解决TSP问题。

八十年代中后期，美国、日本等国家出现了一股神经网络热潮，许多从事脑、科学、心理学、计算机科学以及电子学等方面的专家都在积极合作，开展这一领域的研究。Hopfield于1984年又提出一种连续时间神经网络(HNN)模型，并由容易实现的电子线路所构成。对于HNN,给出适当的初始条件，在状态空间里反复使其更新状态，网络的能量随时间推移单调地减小，状态向着平衡状态的方向更新。最后，网络的能量减至全局最小或局部最小，其状态稳定在某个平衡状态。利用HNN模

型在状态空间里的这种能量最小(极小)化特性，可将它应用于TSP问题的求解。

该方法的基本思想是通过对神经网络引入适当的能量函数，使之与TSP的目标函数相一致来确定神经元之间的联结权，随着网络状态的变化，其能量不断减少，最后达到平衡时，即收敛到一个局部最优解。要解 n城 市的TSP问题，要把问题映射到一个神经网络上。可以使用n*n神经元矩阵。矩阵中的每个元的状态只能为0或1，神经元的状态用Vsi表示，Vsi=l表示城市X在路径中第i个位臵出现。一次有效路径使每行每列有且仅有一个元素为1，其余为0。为了最终解决TSP问题，必须构成这样的神经网络:在网络运行时，计算能量降低，网络稳定后其输出状态表示城市被访问的次序。网络能量的极小点，对应于最佳(或较佳)路径的形成。其解决问题最关键的一步，是构造能量函数。

三、自组织特征映射网络（SOFM）

自组织特征映射（SOFM）是由芬兰学者T. Kohonen提出的。它属于竞争神经网络，本质上是一种无监督的学习机，可以根据输入空间中样本的分布情况，把样本输入空间变换到输出空间。这个输出空间一般比原来的输入空间来的简单（例如前者是离散的而后者是连续的；或者前者的维数比后者低），但是通过将输入样本以自组织的方式映射到输出空间上，输入样本所包含的重要统计信息得以保留，从而达到特征提取、特征选择以及样本聚类等多种目的。

在SOFM中，输出层的神经元分布在一维或二维的网格上（更高维数的网格也是可能的，但比较少见）。与其他类型的神经网络很不相同的是，神经元分布中的相互位臵和近邻关系对于整个网络而言非常重要，这是因为特征映射的过程，就是把在输入空间中样本之间的拓扑关系，尽量完整地反映到输出空间中由神经元组成的网格中，即在网格中的邻近的神经元对应类似的输入样本。这种充分利用神经元位臵关系的神经网络，更接近于生物神经系统的特性，具有很好的自组织学习能力。 SOFM的学习过程：

(1) 初始化网络的权值，确定学习步长α以及邻域宽度参数σ

(2) 随机选取一个输入样本ｘ，根据最小欧氏距离确定获胜神经元，设其标号为i(x)，i(x) = arg min|x(n) – w|

j

j

然后更改网络的权值： w(n+1) = w(n) + α(n)*h

j

j

i(x),j

(n)*(x – w(n))

j

其中，邻域函数, n = 0, 1, 2, 3…

(3) 按如下公式减小学习步长α以及宽度参数σ：

，

α0= 0.1, τ2= 1000 τ1= 1000 / logσ0

(4) 重复第(2)步直至网络权值不再发生变化。

四、利用SOFM解决TSP的基本思路

根据SOFM在自组织映射过程中保持输入样本的拓扑关系这一特点，如果我们把所有城市的二维坐标作为输入样本，把它们映射到一维的环形输出空间上，就得到了一个环游所有城市的回路。由于邻近的城市映射到相邻的神经元上，根据这个回路进行环游，从直观上看，其路径总长度应该是最短的。这就是利用SOFM解决TSP的基本想法。

网络的结构是输入神经元，每个神经元对应二维城市坐标的一个维度；ｎ个输出神经元（ｎ为城市数目）；２ｎ个连接权。这ｎ个神经元排列成环状结构（保证最后得到一个合法环游），在这个环状神经元结构中，两个神经元ｉ，ｊ之间的距离di,j可以定义为： di,j = 在环路中从ｉ到ｊ需要经过的最少神经元数目（顺时针和逆时针） 利用所有城市的坐标作为输入样本进行训练，直到网络权值不再发生变化。这时，理想的情况应该是神经元的位臵与城市位臵一一重合（重合

的次序决定环游路径）。但是，由于网络初始权值的影响，这样理想的结果一般不容易达到。解决这个问题的办法是，将所有城市的坐标逐一输入，找出具有与每个城市的坐标的欧氏距离最近的权值的神经元，该神经元的编号就是这个城市在环游路径中的位臵。

五．实验结果

城市数目：30 神经元数目：90 学习步长参数：1 邻域宽度参数：10 实验结果： 旅行路径：

10,5,9,14,15,8,11,13,3,22,19,28,23,25,30,27,29,20,24,26,21,18,16,17,12,1,2,4,6,7, distance = 18783.000000

附：MATLAB程序

function varargout = tsp(varargin) % TSP M-file for tsp.fig % Begin initialization code gui_Singleton = 1;

gui_State = struct('gui_Name', mfilename, ...

'gui_Singleton', gui_Singleton, ...

'gui_OpeningFcn', @tsp_OpeningFcn, ... 'gui_OutputFcn', @tsp_OutputFcn, ... 'gui_LayoutFcn', [] , ... 'gui_Callback', []); if nargin & isstr(varargin{1})

gui_State.gui_Callback = str2func(varargin{1}); end

if nargout

[varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});

else

gui_mainfcn(gui_State, varargin{:}); end

% End initialization code

% --- Executes just before tsp is made visible.

function tsp_OpeningFcn(hObject, eventdata, handles, varargin) % This function has no output args, see OutputFcn. % hObject handle to figure

% eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) % varargin command line arguments to tsp (see VARARGIN)

% Choose default command line output for tsp handles.output = hObject;

% Update handles structure guidata(hObject, handles);

% UIWAIT makes tsp wait for user response (see UIRESUME) % uiwait(handles.figure1);

% --- Outputs from this function are returned to the command line. function varargout = tsp_OutputFcn(hObject, eventdata, handles)

% varargout cell array for returning output args (see VARARGOUT); % hObject handle to figure

% eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA)

% Get default command line output from handles structure varargout{1} = handles.output;

% --- Executes on button press in pushbutton1.

function pushbutton1_Callback(hObject, eventdata, handles) % hObject handle to pushbutton1 (see GCBO)

% eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) file1 = uigetfile('*.txt'); if ~isequal(file1, 0) read1(file1); end

% --- Executes on button press in pushbutton2.

function pushbutton2_Callback(hObject, eventdata, handles)

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库自组织神经网络求解TSP问题在线全文阅读。