论文研究-基于SOM神经网络的TSP问题研究 .pdf

所需积分/C币:33 2019-08-16 17:33:30 253KB .PDF
121
收藏 收藏
举报

基于SOM神经网络的TSP问题研究,韩洪宁,,TSP问题是组合优化领域的一个重要问题,具有很强的实际应用价值。TSP也是一个NP-hard困难的问题,解决大规模的TSP问题目前还没有完美��
山国武技论文在线 始化学习率1=7 对每个输入模式向量执行如下操作 将输入模式冋量同竞争层所有神经元节点对应的权冋量进行比较,寻找欧氏 距离最小的获胜神经元。 对所有的神经元∈ 根据神经元与神经元的欧氏距离,计算各个神经元的修正强度 根据下式,调整神经元的杈值 +n 其中n是关于训练次数的函数,且满足↑→n↓;是关于和的函 数,且满足个→y,个→√。 当满足某个条件时,结束。否则继续执行步骤。该条件一般为η小于某个值或训练 次数达到某个值。 问题介绍 )问题,即旅行商问题是数学领域中著名问题之 其问题描述为:已知个城市和所有这个城市之间的距离,一个旅行商人要拜访这个城 市,每个城市必须且只能拜访次,最后要回到原来岀发的城市。要求求山·条巡回路径, 使此路径是所有循回路径中最短的 问题的数学描述为:给定有限个城市的集合 及每两个城市之间 的距离矩阵 ,求出满足∑ 的城市序列,其 丌 中丌x…丌是 的一个全排列。 问题是一个组合优化问题,该问题被证明具有计算复杂性。对于个城市 全部的路径组合总数,由 公式,其值为 √兀 。可见,随着城市规模 的增加,路径组合总数将以指数方式急剧増加。当问题规模较大时,穷举出所有的 组合将需要很长的吋间。旦然此类方法可以得到确切的最优解,但其吋间复杂度限制了其应 用沱围。在这些确定性算法中有动态规划法、分枝界限法等。另类是智能算法,即近似算 法,这类算法能够在所冇路径组合中找岀相对较优的解,此类算法包括遗传算法、模拟退火 算法、蚁群算法、人工神经网络算法等。 在大多数的实际应用中,并不需要必须找到最优解,一些次优解既能淸足要求。因 此利用这些智能算法,以适当牺牲解的质量为代价,就能满足时间复杂度方面的要求。运用 智能算法中的神经网络算法,即应用自组织人工神纾网终网,可以以较小的时间复杂 度找到满意解。 解决问题的方法 解决问题的基本思路是:训练集是城市的集合,每个二维输入向量代表一个 山国武技论文在线 城市在二维平面上的位置坐标,因此网络的输入层有两个节点。将输出层节点分布在 图所示的一个封闭圆环上,圆环中的每个节点代表一个城市,因此该圆环模拟了一个巡 回路径,在训练过程中,该巡回路径的城巾组合在不断地变动,训练结束后得到的一个路径 就是要求的优化解 实际上,一般取几倍于城市个数的神经元节点数目,这样更謇易得到所求的解。初始化 妽经元的权值时,理想情况时按照样本集中的输入冋量的分布来确定,为了简化起见,也可 以随杋初始化权值,但这样做的缺点是有可能造成严重的不平衡,即一部分远离样本的神经 元总是无法得到匹配,造成了浪费,另一部分神经元代表的类含有过多的输入向量,无法达 到预期的期望分类。因此要根据实际情况灵活选择初始化权值的方法 实例: 解决 问题 问题就是遍历中国所有笮会城市(包括直辖市、特别行政区)的问题特例。 下面以解决问题为例,详细说明解决过程,并比较 算法在输入顺序不同的时 候,计算出的 路径的差异。 中国个省会城市(包括直辖市、特别行政区)的经纬度如下表所小 表各省会城市绎纬度 编号城市名东经北纬编号城市名东经北纬 北京 南京 天津 合肥 上海 杭州 重庆 福州 南昌 乌鲁木产 长沙 银川 武汉 呼和浩特 广州 南宁 台北 哈尔滨 海口 长春 沈阳 西安 石家庄 成祁 太原 贵阳 西宁 昆明 济南 香港 郑州 澳门 求解时分别以经度、纬度为横坐标和纵坐标表示城市的位置来计算嵱径。具体的 步骤入卜面所示。 输出层设计与权值初始化 本例中,取输出层的神绎元数目为城市数目的倍,即个神经元。这些神经元分布 在一个封闭的矩形的边上,模拟了一个巡回路径,如下图所示。注意此时的神经元为初始 化时的值,偏离实际城市较远,并不能看出某个神经兀代表的城市,在训练过程中神经儿将 逐渐靠近实际的城市。初始时如下图所小,其中蓝色的圆圈代表城市,红色的点代表初始化 山国武技论文在线 吋候各个神经元的位置,相邻两点之间的连线组成了个封闭的图形,代表了个巡回路径 佟初始巡回路径 学习率的设计 学习率η的设计原则是在开始训练时取较大的值,之后以较快的速度下降,这样有利于 很快捕捉到输入样本(即各个城市)的大致分布情况。然后η又在较小的值上缓慢降全, 这样可以精细地调整权值使之符合输入空间的样本分布结构。 满足刀变化规律的函数有很多,例如下图所示的指数函数,在区间+∞上,刚开 始函数值由迅速减少,后来缓慢的趋向。 图指数函数 具体到 问题时,取学习率为关于训练次数的指数函数,即 7=7 其中为一常数。 权值修正强度的设计 神经元的权值修正强度是关于训练次数和神经元距获胜神经元的距离的 函数,满足↑>↓,↑>↓。具体来说,权值修正强度在刚开始时,修正的范围和 强度都比较大,随着训练次数的增加,宄是较快的减小修正范围和强度,后米再缓慢的减小 修正范围和强度。这样可以使输出平面上相邻神经元对应的杈向量既有区别又有一定的相似 性,从而保证当获胜节点对某一类模式产生最大响应时,其邻近的节点也能产生较大响应。 具体到 问题,修正强度的公式定义如下 其中G=G 为一常数。 山国武技论文在线 求解路径 在确定了输出层的设计和学习率、修正强度的睬数后,就可以开始求解了。通过试验, 取n 。按照 算法,计算的路径。 训练次数与路径的关系如下图 n=100 7-=300 图巡回路径变化过程 经过了约次迭代,求出了最终的巡回路径如下图所小,其路径长度为 佟最终巡回路径 在上面的进行输入模式向量的输入时,是按照城市编号依次输入的。一和可行的做 法是在输入城市时进行随即输入,通过次的实验,得到的路径长度妇下表所示。其中 每次实验,在训练至次左右时,就能得到清昕的巡回路径。对比传统方法求解问 题时,要先找出个城市直间的所有路径组合,其总数为 与求解 的迭代次数比较,说明了解决问题时,在时间方面,有较小的时间复杂度 表以不同顺序输入城市的实验结果 次数 烙径长度 次数 路径长度 由上表,通过与顺序输入城市得到的结果 相比,可以看出,有次得到了更优的解 并且有次得到了值为 的解,路径都如下图所示: 山国武技论文在线 - 求得的铰优路径 为了验证应用 网络求解 问题解的质量,可以通过一个专门解决问题的 应用程序 来验证 求的路径如下图所示,其长度为 与用 求解的路径基本一致,且误差仅有 图 求出的巡冋路径 结论 本文阐述了网络的基本概念,并介绍了解决问题的原理。然后给出了 网络求解问题的具体过程,对比了与传统方法求解在时间复杂度方 面的差异,表明了的快速性。又对比了输入模式向量的不同对结果的影响以及应用 求解的结果和最优结果的误差,表明了求解问题的有效性。 参考文献 韩丿群人工神经网终理论、设计及应用北京:化学工业出版社, 蒋宗礼人工神经网终导论北京:高等教育出版社, 中国城市经纬度查询

...展开详情
试读 7P 论文研究-基于SOM神经网络的TSP问题研究 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-基于SOM神经网络的TSP问题研究 .pdf 33积分/C币 立即下载
1/7
论文研究-基于SOM神经网络的TSP问题研究 .pdf第1页
论文研究-基于SOM神经网络的TSP问题研究 .pdf第2页

试读结束, 可继续读1页

33积分/C币 立即下载