用的是随机点的测试数据。
1// ******************************************************************************************
2// 物体降温退火过程中,其能量转移服从Boltzmann distribution规律 P(E) ∝ exp(-E/kT);
3// P(E)是系统处于低能E的概率(probability),k为Boltzmann常数,T为系统温度。
4// 模拟退火算法原理
5// (1)初始温度T(0) = T0。迭代次数t=0,任意初始状态做当前解V(0)∈V
6// (2)按某一规则有当前状态产生当前状态的下一次侯选状态。
7// 计算目标代价变化△C,若△C<0则接受解,(△ delta)
8// 否则考虑当前温度下状态活动概率 P(△C) = exp(-△C/T);P(△C)≥λ则接受解,否则不接受
9// λ(lambda)为预先指定或随机产生的正数。 (0<λ<1)
10// (3)按某种策略对T更新(降温)。
11// (4)按某种标准检查退火过程是否应该结束,若不满足则转(2)
12// (5)输出状态V(t)做问题解
13// ******************************************************************************************
14
15using System;
16using System.Drawing;
17
18namespace Algorithm.SimulatedAnnealing
19{
20 public class TravellingSalesmanProblem
21 {
22 private Point[] _points;
23 private double[,] _distanceMatrix;
24 private double _initialTemperature = 0d;
25 private double _currentTemperature = 0d;
26
27 private int _routerCount;
28
29 private int[] _currentRouter;
30 private int[] _resultRouter;
31
32 private Random _rdm;
33 private bool _IsCalculated = false;
34 private DateTime calculate_begin;
35 private DateTime calculate_end;
36
37 public TravellingSalesmanProblem(Point[] pts)
38 {
39 _points = (Point[])pts.Clone();
40
41 _routerCount = _points.Length;
42 _currentRouter = new int[_routerCount];
43 _resultRouter = new int[_routerCount];
44 _distanceMatrix = new double[_routerCount, _routerCount];
45
46 _rdm = new Random((int)DateTime.Now.Ticks);
47
48 double minDistance = 10000d;
49 double maxDistance = 0d;
50
51 for(int i = 0; i < _points.Length; i++)
52 {
53 _currentRouter[i] = i; // init point router 1 > 2 > 3 > n
54 _resultRouter[i] = i;
55 for(int j = i + 1; j < _points.Length; j++)
56 {
57 double offsetX = (double)(_points[i].X - _points[j].X);
58 double offsetY = (double)(_points[i].Y - _points[j].Y);
59 double distance = Math.Sqrt(offsetX * offsetX + offsetY * offsetY); //计算两点间的距离
60 _distanceMatrix[i, j] = distance;
61 _distanceMatrix[j, i] = distance;
62 if(distance > maxDistance) maxDistance = distance;
63 if(distance < minDistance) minDistance = distance;
64 }
65 }
66 _initialTemperature = 20 * (_routerCount * maxDistance - _routerCount * minDistance);// 计算起始温度
67 _currentTemperature = _initialTemperature;
68 }
69
70 // 得出最优距离
71 public double GetTotalDistancOptimization()
72 {
73 if(!_IsCalculated)
74 Calculation();
75 return CalculateTotalDistance(_resultRouter);
76 }
77
78 // 得到最优路由
79 public int[] GetRouterOptimization()
80 {
81 if(!_IsCalculated)
82 Calculation();
83 return _resultRouter;
84 }
85
86 public double GetCalculationalTime()
87 {
88 if(_IsCalculated)
89 {
90 TimeSpan span = calculate_end - calculate_begin;
91 return span.TotalMilliseconds;
92 }
93 else
94 return 0d;
95 }
96
97 // 求出最优解
98 private void Calculation()
99 {
100 //Random rdm = new Random((int)DateTime.Now.Ticks);
101 calculate_begin = DateTime.Now;
102 while(true)
103 {
104 int IterCount = 0;
105 while(true)
106 {
107 double totalDistance1 = CalculateTotalDistance(_resultRouter);
108 BuildRandomRouter(); // change router
109 double totalDistance2 = CalculateTotalDistance(_currentRouter);
110
111 double deltaTotalDistance = totalDistance2 - totalDistance1;//delta
112 //原理见顶部注释
113 if(deltaTotalDistance <= 0d)
114 {
115 for(int i = 0; i < _resultRouter.Length; i++)
116 _resultRouter[i] = _currentRouter[i];//赋值到结果路由
117 }
118 else
119 {
120 //原理见顶部注释
121 double probability = Math.Exp( -(deltaTotalDistance/_currentTemperature));
122 double lambda = ((double)(_rdm.Next() % 10000)) / 10000d;//随机指定的正数lambda
123 if(probability > lambda)
124 {
125 for(int i = 0; i < _resultRouter.Length; i++)
126 _resultRouter[i] = _currentRouter[i];
127 }
128 }
129 if(IterCount >= _routerCount * _routerCount * _routerCount) //某一温度下的循环次数是点个数的三次方
130 {
131 break;
132 }
133 else
134 {
135 IterCount++;
136 }
137
2// 物体降温退火过程中,其能量转移服从Boltzmann distribution规律 P(E) ∝ exp(-E/kT);
3// P(E)是系统处于低能E的概率(probability),k为Boltzmann常数,T为系统温度。
4// 模拟退火算法原理
5// (1)初始温度T(0) = T0。迭代次数t=0,任意初始状态做当前解V(0)∈V
6// (2)按某一规则有当前状态产生当前状态的下一次侯选状态。
7// 计算目标代价变化△C,若△C<0则接受解,(△ delta)
8// 否则考虑当前温度下状态活动概率 P(△C) = exp(-△C/T);P(△C)≥λ则接受解,否则不接受
9// λ(lambda)为预先指定或随机产生的正数。 (0<λ<1)
10// (3)按某种策略对T更新(降温)。
11// (4)按某种标准检查退火过程是否应该结束,若不满足则转(2)
12// (5)输出状态V(t)做问题解
13// ******************************************************************************************
14
15using System;
16using System.Drawing;
17
18namespace Algorithm.SimulatedAnnealing
19{
20 public class TravellingSalesmanProblem
21 {
22 private Point[] _points;
23 private double[,] _distanceMatrix;
24 private double _initialTemperature = 0d;
25 private double _currentTemperature = 0d;
26
27 private int _routerCount;
28
29 private int[] _currentRouter;
30 private int[] _resultRouter;
31
32 private Random _rdm;
33 private bool _IsCalculated = false;
34 private DateTime calculate_begin;
35 private DateTime calculate_end;
36
37 public TravellingSalesmanProblem(Point[] pts)
38 {
39 _points = (Point[])pts.Clone();
40
41 _routerCount = _points.Length;
42 _currentRouter = new int[_routerCount];
43 _resultRouter = new int[_routerCount];
44 _distanceMatrix = new double[_routerCount, _routerCount];
45
46 _rdm = new Random((int)DateTime.Now.Ticks);
47
48 double minDistance = 10000d;
49 double maxDistance = 0d;
50
51 for(int i = 0; i < _points.Length; i++)
52 {
53 _currentRouter[i] = i; // init point router 1 > 2 > 3 > n
54 _resultRouter[i] = i;
55 for(int j = i + 1; j < _points.Length; j++)
56 {
57 double offsetX = (double)(_points[i].X - _points[j].X);
58 double offsetY = (double)(_points[i].Y - _points[j].Y);
59 double distance = Math.Sqrt(offsetX * offsetX + offsetY * offsetY); //计算两点间的距离
60 _distanceMatrix[i, j] = distance;
61 _distanceMatrix[j, i] = distance;
62 if(distance > maxDistance) maxDistance = distance;
63 if(distance < minDistance) minDistance = distance;
64 }
65 }
66 _initialTemperature = 20 * (_routerCount * maxDistance - _routerCount * minDistance);// 计算起始温度
67 _currentTemperature = _initialTemperature;
68 }
69
70 // 得出最优距离
71 public double GetTotalDistancOptimization()
72 {
73 if(!_IsCalculated)
74 Calculation();
75 return CalculateTotalDistance(_resultRouter);
76 }
77
78 // 得到最优路由
79 public int[] GetRouterOptimization()
80 {
81 if(!_IsCalculated)
82 Calculation();
83 return _resultRouter;
84 }
85
86 public double GetCalculationalTime()
87 {
88 if(_IsCalculated)
89 {
90 TimeSpan span = calculate_end - calculate_begin;
91 return span.TotalMilliseconds;
92 }
93 else
94 return 0d;
95 }
96
97 // 求出最优解
98 private void Calculation()
99 {
100 //Random rdm = new Random((int)DateTime.Now.Ticks);
101 calculate_begin = DateTime.Now;
102 while(true)
103 {
104 int IterCount = 0;
105 while(true)
106 {
107 double totalDistance1 = CalculateTotalDistance(_resultRouter);
108 BuildRandomRouter(); // change router
109 double totalDistance2 = CalculateTotalDistance(_currentRouter);
110
111 double deltaTotalDistance = totalDistance2 - totalDistance1;//delta
112 //原理见顶部注释
113 if(deltaTotalDistance <= 0d)
114 {
115 for(int i = 0; i < _resultRouter.Length; i++)
116 _resultRouter[i] = _currentRouter[i];//赋值到结果路由
117 }
118 else
119 {
120 //原理见顶部注释
121 double probability = Math.Exp( -(deltaTotalDistance/_currentTemperature));
122 double lambda = ((double)(_rdm.Next() % 10000)) / 10000d;//随机指定的正数lambda
123 if(probability > lambda)
124 {
125 for(int i = 0; i < _resultRouter.Length; i++)
126 _resultRouter[i] = _currentRouter[i];
127 }
128 }
129 if(IterCount >= _routerCount * _routerCount * _routerCount) //某一温度下的循环次数是点个数的三次方
130 {
131 break;
132 }
133 else
134 {
135 IterCount++;
136 }
137