基于Hopfield的TSP问题求解软件程序设计与实现

目 录
1 引言 1
2 Hopfield 网络模型 1
2.1 连续型Hopfield神经网络模型结构 2
2.2 旅行商问题（TSP）的HNN 求解 4
2.2.1 TSP 描述 4
2.2.2 TSP 问题的网络匹配与求解 7
3 TSP 问题求解的软件模拟程序实现 8
4 TSP问题求解结果分析 11
5 总结 12
参考文献 12
3 TSP 问题求解的软件模拟程序实现
程序的基本思想是：当确定了 N个城市的位置分布后，用随机函数产生20 组神经元的初始状态。对每组初始状态用式（4.22）进行迭代，计算神经元的状态变化，一直到达某稳定状态，则获得了该TSP 的一个解，若迭代超过3000 次仍未达到稳定状态，则求解失败，再对下一组初始状态进行迭代。
程序主要包含以下四个子过程：
(1)网络参数的选择
式（4.25）中的网络参数A, B, C, D, u0 等对网络的变化相当敏感，原则上不能随意改变，Hopfield 和Tank 给出的参数值为：A=B=D=500, C=200, u0=0.02。这种选择是考虑了以下两点后的折衷：① D 值较小时，容易获得合法路径；D 值较大时，可增加路径长度的权重，从而使合法路径趋于最优；② u0 是放大器的增益，太小时，阈值函数接近于符号函数，不能获得较好的解；太大时，S 型阈值函数过于平坦，神经元状态不易于收敛到0 和1，从而使获得合法路径的概率下降。
除了以上两点外，程序中还考虑了网络参数对收敛速度的影响。实际中为了取得一个较好的能量函数数量级差异，程序中初始设置A=B=C=0.05 D=0.1，然后用步长0.5依次增大它们的值，并在每次ABCD的值下求解路径，以求获得最佳路径。
(2) 网络初始状态的设置
double u00=0-u0log(CityNum-1)/2;
for(i=0;i<CityNumCityNum;i++){
double t=((rand())%32767)/(float)32767;
InSig[i]=u00+0.001*(t*2-1)*InitBias[i];
OutSig[i]=G(InSig[i]);
对于网络初始状态 uxi 的选择问题，常采用随机扰动的方法。即给初始值u00, 增加一个小的扰动δ：
uxi=u00+δ
−0.1u00≤δ≤0.1u00
采用随机扰动的方法设置初始状态可以获得正确解，但随机扰动缺乏网络的整体特性,因而不易获得较好的解，本文转载自http://www.biyezuopin.vip/onews.asp?id=12879并且收敛效率也不高。一种改进的办法是采用给初始状态增加一个偏置，偏置公式由Wilson-Pawley 给出：

#include "CityInfo.h"
//设置城市名字
void CityInfo::SetName(string na){
    Name=na;
}
//设置城市索引
void CityInfo::SetCityIndex(int index){
    CityIndex=index;
}
//设置Coordx
void CityInfo::SetCoordx(double x){
    Coordx=x;
}
//设置Coordy
void CityInfo::SetCoordy(double y){
    Coordy=y;
}
//得到城市名字
string CityInfo::GetName( ){
    return Name;
}
//得到城市下标索引
int CityInfo::GetCityIndex( ){
    return CityIndex;
}
//得到X坐标
double CityInfo::GetCoordx( ){
    return Coordx;
}
//得到Y坐标
double CityInfo::GetCoordy(){
    return Coordy;
}
//得到两个城市距离
double CityInfo::GetCityDis(CityInfo c1){
	return sqrt((c1.GetCoordx()-Coordx)*(c1.GetCoordx()-Coordx)+(c1.GetCoordy()-Coordy)*(c1.GetCoordy()-Coordy));
}