1
人工神经网络实验
用 CHNN 算法求解 TSP 问题
一. 问题描述
利用连续型 Hopfield 反馈网络求解 10 城市的旅行商(TSP)问题。
其中 10 个城市的坐标给定如下:
1 (0.4000,0.4439), 2 (0.2439,0.1463),
3 (0.1707, 0.2293), 4 (0.2293,0.7610),
5 (0.5171,0.9414), 6 (0.8732,0.6536),
7 (0.6878, 0.5219), 8 (0.8488, 0.3609),
9 (0.6683,0.2536),
city city
city city
city city
city city
city ci
= =
= =
= =
= =
= 10 (0.6195, 0.2634)ty =
基本网络参数为:
0
500, 200, 0.02A B D C
m
= = = = =
二. 算法实现
1.CHNN 算法
应用 CHNN 网络解决优化问题一般需要以下步骤:
(1.)对于特定的问题,要选择一种合适的表示方法,使得神经网络
的输出与问题的解相对应。
(2.)构造网络的能量函数,使其最小值对应于问题的最佳解。
(3.)将能量函数与 CHNN 算法标准形式相比较,推出神经网络权值与
偏流表达式。
(4.)推出网络状态更新公式,并利用更新公式迭代求问题的最优解。
2.TSP 问题
为使用 CHNN 网络进行 TSP 问题的求解,根据上述步骤,可将问
题转化为:
(1.)对 N 个城市的 TSP 问题,用一个
N N´
的换位阵描述旅行路线,
换位阵中每行每列有且只有一个元素为 1,其余全为 0。为 1 的元