1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
import math
import random
import time,os
from matplotlib.pyplot import *
import numpy as np
class Metal():
def __init__(self, data, temperature, descending):
self.temperature = temperature
self.descending = descending
self.change = range(0, len(data))
self.data = data
self.best = [[1,2], float("inf")]
self.x = self.best[0][:]
self.y = self.best[1]
self.HistoryY = []
self.Cm = cm.get_cmap('Greys')
def Smelt(self):
"""
开始冶炼
"""
NewY = self.Fx(self.change)
dE = self.y - NewY
if dE > 0 or math.e ** (dE / self.temperature) > random.uniform(0, 1):
self.y = NewY
self.x = self.change[:]
if self.y < self.best[1]:
self.best[0] = self.x
self.best[1] = self.y
os.system('cls')
print '当金属温度为', self.temperature, '℃时达到历史最佳路径, 长度为', self.best[1], '\n 路线为\n', self.best[0], '\n', '-'*100
self.HistoryY += [NewY]
self.temperature -= self.descending
self.RandX()
def Fx(self, xi):
"""
计算冶炼的程度
"""
start = 0
distance = 0.0
Xi=xi+[xi[0]]
for end in range(1, len(Xi)):
distance += ((self.data[Xi[start]][1][0] * 1.0 - self.data[Xi[end]][1][0]) ** 2 + (self.data[Xi[start]][1][1] * 1.0 - self.data[Xi[end]][1][1]) ** 2) ** 0.5
start = end
return distance
def RandX(self):
"""
随机产生 2 个点,
一个为起点,一个为终点,
将这 2 点之间的路径倒置
"""
self.change = self.x[:]
start = random.randint(0, len(self.change))
end = random.randint(start, len(self.change))
self.change[start:end] = self.change[start:end][::-1]
def PlotAndSave(self):
"""
冶炼结束时画出每温度下的 x 与 y
"""
plot(range(1, len(self.HistoryY) + 1), self.HistoryY)
title(str(self.x) + '\n\n' + str(self.y), fontsize = 7)
savefig('Max.jpg')
close('all')
xr = []
yr = []
for i in self.x:
xr += [self.data[i][1][0]]
yr += [self.data[i][1][1]]
xr = np.array(xr + [xr[0]])
yr = np.array(yr + [yr[0]])
x0 = xr[:2]
y0 = yr[:2]
xr = xr[1:]
yr = yr[1:]
quiver(x0[:-1], y0[:-1], x0[1:] - x0[:-1], y0[1:] - y0[:-1], scale_units = 'xy', angles = 'xy', scale = 1, color='r')
quiver(xr[:-1], yr[:-1], xr[1:] - xr[:-1], yr[1:] - yr[:-1], scale_units = 'xy', angles = 'xy', scale = 1)
savefig('Max_Road.jpg')
close('all')
time.clock()
data = [["*", [37, 52]],..., ["*", [30,40]]]
temperature = 100
descending = 0.001
metal = Metal(data, temperature, descending)
while metal.temperature > 1:
t = time.clock()
minute, second = divmod(t, 60)
hour, minute = divmod(minute, 60)
metal.Smelt()
print '当前金属温度为', metal.temperature, '℃', '此温度下最优路径长度为', metal.y, ' 花费时间 %02d:%02d:%02d' %(hour, minute, second), ' '*5,'\r',
print '\n路线为\n', metal.x
metal.PlotAndSave()
print
os.system('pause')
|
