Hopfield网络求解TSP两种改进算法的仿真研究

2011-05-27 19:33:51来源: 互联网
1 引言
    用Hopfield神经网络求解旅行商问题(TSP),给组合优化完备性问题的求解提供新的方法。但该算法会经常生成无效解,因此需进一步改进。有学者通过TSP网络的动态分析修正TSP的能量函数,从而获得有效解,但其能量函数的表达式过于复杂。有人简化该能量函数,进一步提出改进算法。这里拟对典型的两种改进算法进行仿真分析。

2 HopfieId网络的能量函数
    为将TSP问题映射成神经网络的动态过程,Hopfield采取置换矩阵的表示方法,用N×N个神经元组成Hopfield人工神经网络表示商人访问N个城市。
    网络达到稳定状态时各神经元的状态对应置换矩阵各元素的值(“1”或“0”)。用uxi表示神经元(x,i)的输出,相应的输入用Vxi表示。
    若城市x在i位置上被访问,则Vxi=1,否则Vxi=0。Hop-field定义如下形式的能量函数:
   

   
式中,A、B、C、D是实系数。dxy为城市x与y之间的距离。
    式中前3项是问题的约束项。最后1项是优化目标项。利用动态方程:
   
式中,VT表示V的转置。
    求得A、B、C、D和d描述的连接矩阵和及偏置,的表达式:

    Hopfield把能量函数的概念引入神经网络,从而开创求解优化问题的新方法。但该算法会以大百分比生成无效解,因此需进一步改进。

3 改进算法与仿真
3.1 改进算法1
   
Aiyer等人从理论上证明Hopfield网络不能生成有效解的原因,并提出一个新的连接矩阵:

外部输入
    可从理论上证明该算法的有效性,试验也验证它几乎100%可获得有效解。利用上述改进算法对Hopfield的10城市问题进行模拟试验,已知其最短路径为2.690 6。模拟试验采用两种神经元状态更新函数,一种采用S型函数,即
   
    另一种采用如下定义的软限幅函数:
   

它是线性化近似的一种合理选择。图1给出软限幅函数及双曲正切函Uo取0.02时的曲线图。对于每种情况,从起始条件出发模拟运行200次,每次模拟在达到下列两条件之一时终止运行:(1)网络中的每个神经元均在[0.9,1]或[0,0.1]之间取值,分别对应神经元的“激活”(取值落在[0.9,1]中)或“抑制”状态(取值落在[0,0.1]中),并且矩阵的每行每列恰有一个非零元素;(2)运行迭代次数大于10 000次。注意,没有以dE/dt=0判别迭代结束。因为满足dE/dt=0的点不一定是E的极小点或最小点,也可能是拐点。其次,即使是E的极小点,继续迭代有可能跳出这个极小点。取A=B=8,A1=7.75,D=2,步长δt=0.02,测试结果如表1和图1所示。由测试结果可知,软限幅的效果明显优于硬限幅,因为软限幅与线性化近似极为相似,但所需的收敛次数较多。
    研究表明,在S型函数UO=2情况下,网络给不出任何有效的解答。因为网络中的神经元无法收敛于其稳态(“激活”或“抑制”)。

3.2 改进算法2
    Aiyer通过TSP网络的动态分析修正TSP的连接矩阵,从而获得有效解,但其表达式过于复杂,影响优化效果。简化该能量函数:

首先检查式(1)的前3项,其中,第3项仅在网络输出全为0时起约束作用,否则前2项已保证第3项成立。对前2项作如下修改:
   
    则第3项完全可省去。将优化目标项写成:

    或
    也可满足优化要求。则TSP的能量函数简化为:
   
    下面以式(13)作为研究对象,其对应的网络连接矩阵和外部输入分别是:
   
    该算法可从理论上证明其有效性,仿真研究如下:取A=B=3,D=1,步长δt=0.05,对Uo=0.02和软限幅两种情况进行仿真,仿真终止条件与改进算法2相同。测试的统计结果如表2和图2所示。

    从测试结果可以看出,该方法获得的最优解的个数明显的多于改进算法1。软限幅的效果明显优于sigmold函数的效果。但所需的收敛次数较多。这一点与改进算法1是一致的。在使用软限幅时获得最优解的概率大于95%,只是所需迭代次数稍多。

4 结束语
   
对两种求解TSP的改进算法进行仿真研究,结果表明他们具有非常好的优化效果,在10城市问题上可近似100%的获得最优解。
    另外,该算法还具有对参数敏感度低的优点。改进算法的缺点是所需迭代次数较多。当采用大步长迭代时,可降低收敛所需的迭代次数,但会影响优化效果。
    这种影响对Uo=0.02的情况不明显,例如,在δt=0.5时,其优化效果与δt=0.05时几乎相同,所需迭代次数可降到450次左右。而对于软限幅的情况,步长的影响就明显了,δt= 0.5时,优化效果与图中Uo=0.02的情况差不多。下一步的工作拟采用变步长的方法,估计可大大降低所需的迭代次数。

关键字:网络  求解  两种  改进

编辑:eeleader 引用地址:http://www.eeworld.com.cn/gykz/2011/0527/article_6212.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部
网络
求解
两种
改进

小广播

独家专题更多

TTI携TE传感器样片与你相见,一起传感未来
TTI携TE传感器样片与你相见,一起传感未来
TTI携TE传感器样片与你相见,一起传感未来
富士通铁电随机存储器FRAM主题展馆
富士通铁电随机存储器FRAM主题展馆
馆内包含了 纵览FRAM、独立FRAM存储器专区、FRAM内置LSI专区三大部分内容。 
走,跟Molex一起去看《中国电子消费品趋势》!
走,跟Molex一起去看《中国电子消费品趋势》!
 
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved