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

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

ID:53258592

大小:66.50 KB

页数:10页

时间:2020-04-02

自组织神经网络求解TSP问题.doc_第1页
自组织神经网络求解TSP问题.doc_第2页
自组织神经网络求解TSP问题.doc_第3页
自组织神经网络求解TSP问题.doc_第4页
自组织神经网络求解TSP问题.doc_第5页
资源描述:

《自组织神经网络求解TSP问题.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、自组织特征映射网络(SOFM)求解TSP问题组长:袁滨组员:杨涛,徐丽丽,张冰,殳晶莹,许才华,郑彩萍一、旅行商问题旅行商问题(TravelingSalesmanProblem,简称TSP).商品的推销员打算从驻地出发遍访他要去的每个城市,并且每个城市只能访问一次,最后必须返回出发城市。问如何安排他对这些城市的访问次序,可使其旅行路线的总长度最短?旅行商问题TSP是一个典型的组合优化问题,并且是一个NP完全问题,其可能Hamilton圈的数目是顶点的数目n的指数函数,所以一般很难精确地求出其最优解。所谓组合优化问题,是指在离散的,有限的数学结构上,寻找一个满足给定条件,并使其目标

2、函数值达到最小或最大的解。一般来说,组合优化问题通常带有大量的局部极值点,通常是非线性的NP完全问题。其最先起源于一个旅行商要访问他所有的客户,要发现一条最短的路线。用用图论的术语来说,旅行商问题就是在赋权完全图上找一个权最小的Hamilton圈。但是,首先从应用上来说,很多实际应用问题,如印制电路板的、连锁店的货物配送路线等,经简化的处理后,均可转化为旅行商问题TSP。由于旅行商问题的重要应用价值,因而对旅行商问题的算法研究自然是一个无法回避的问题;其次,从理论上来说,它的计算复杂性研究在形成NP完全理论中起到奠基作用。今天,由于电子计算机科学技术的进展,这个古老问题的算法研究

3、又重新注入了新的活力,旅行商问题研究的新思路、新方法、新成果必将丰富NP完全理论的内涵,促进NP完全理论的发展。二、神经网络算法与优化计算神经网络的应用已经渗透到多个领域,如智能控制、模式识别、信号处理、计算机视觉、优化计算、知识处理、生物医学工程等。利用神经网络进行优化计算,采用的模型一般包括Hopfield神经网络、混沌神经网络和波尔兹曼机(类似模拟退火)等。TSP是典型的NP-难解问题,它对应的判定问题属于NPC类。由于这个问题具有许多实际应用背景,所以寻求解决它的高效近似算法就成为学术界的研究热点。可以利用自组织特征映射网络(SOFM)解决TSP问题。八十年代中后期,美国

4、、日本等国家出现了一股神经网络热潮,许多从事脑、科学、心理学、计算机科学以及电子学等方面的专家都在积极合作,开展这一领域的研究。Hopfield于1984年又提出一种连续时间神经网络(HNN)模型,并由容易实现的电子线路所构成。对于HNN,给出适当的初始条件,在状态空间里反复使其更新状态,网络的能量随时间推移单调地减小,状态向着平衡状态的方向更新。最后,网络的能量减至全局最小或局部最小,其状态稳定在某个平衡状态。利用HNN模型在状态空间里的这种能量最小(极小)化特性,可将它应用于TSP问题的求解。该方法的基本思想是通过对神经网络引入适当的能量函数,使之与TSP的目标函数相一致来确

5、定神经元之间的联结权,随着网络状态的变化,其能量不断减少,最后达到平衡时,即收敛到一个局部最优解。要解n城市的TSP问题,要把问题映射到一个神经网络上。可以使用n*n神经元矩阵。矩阵中的每个元的状态只能为0或1,神经元的状态用Vsi表示,Vsi=l表示城市X在路径中第i个位置出现。一次有效路径使每行每列有且仅有一个元素为1,其余为0。为了最终解决TSP问题,必须构成这样的神经网络:在网络运行时,计算能量降低,网络稳定后其输出状态表示城市被访问的次序。网络能量的极小点,对应于最佳(或较佳)路径的形成。其解决问题最关键的一步,是构造能量函数。三、自组织特征映射网络(SOFM)自组织特

6、征映射(SOFM)是由芬兰学者T.Kohonen提出的。它属于竞争神经网络,本质上是一种无监督的学习机,可以根据输入空间中样本的分布情况,把样本输入空间变换到输出空间。这个输出空间一般比原来的输入空间来的简单(例如前者是离散的而后者是连续的;或者前者的维数比后者低),但是通过将输入样本以自组织的方式映射到输出空间上,输入样本所包含的重要统计信息得以保留,从而达到特征提取、特征选择以及样本聚类等多种目的。在SOFM中,输出层的神经元分布在一维或二维的网格上(更高维数的网格也是可能的,但比较少见)。与其他类型的神经网络很不相同的是,神经元分布中的相互位置和近邻关系对于整个网络而言非常

7、重要,这是因为特征映射的过程,就是把在输入空间中样本之间的拓扑关系,尽量完整地反映到输出空间中由神经元组成的网格中,即在网格中的邻近的神经元对应类似的输入样本。这种充分利用神经元位置关系的神经网络,更接近于生物神经系统的特性,具有很好的自组织学习能力。SOFM的学习过程:(1)初始化网络的权值,确定学习步长α以及邻域宽度参数σ(2)随机选取一个输入样本x,根据最小欧氏距离确定获胜神经元,设其标号为i(x),i(x)=argminj

8、x(n)–wj

9、然后更改网络的权值:wj(n+1

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。