本文基于TSP问题是合理规划无线传感器网络中移动充电器的充电路线。建模解决了单个移动充电器和多个移动充电器的路径规划和最小电池容量问题。 具体问题可以去官网查看 第一个问题很经典TSP有很多问题和解决方案。本文采用0-1规划思路 通过的路线与未通过的路线对应赋值 以下是Python代码 不要做太多的解释
1. # -*- encoding: utf-8 -*- 2. 3. import math 4. from GA import GA 5. import threading 6. import copy 7. import time 8. import tkinter 9. 10. class TSP_WIN(object): 11. #初始化 12. def __init__(self, aRoot, times,num,aLifeCount=100, aWidth=660, aHeight=650): 13. self.plan_numbers = num 14. self.n=times 15. self.evolution_times = times 16. self.root = aRoot 17. self.lifeCount = aLifeCount 18. self.width = aWidth 19. self.height = aHeight 20. self.plan = [] 21. self.out = [] 22. self.canvas = tkinter.Canvas( 23. self.root, 24. width=self.width, 25. height=self.height 26. #background = "grey" 27. ) 28. self.canvas.pack(expand=tkinter.YES, fill=tkinter.BOTH) 29. self.canvas.create_text(330, 30, text='TSP-GA VIEW',font=(黑体，20)， fill = 'red') 30. self.initCitys() 31. self.bindEventsButton() 32. #self.initCitys() 33. self.prechoose() 34. self.linenodes() 35. #T=threading.Thread(self.prechoose()) 36. #T.start() 37. #self.new() 38. self.title("TSP") 39. 40. #从文件中读取节点信息，并初始化结点信息 41. def initCitys(self): 42. self.citys = [] 43. # 本文件是30个节点的经纬度 44. f = open("data.txt", "r") 45. while True: 46. # 一行一行读取 47. loci = str(f.readline()) 48. if loci: 49. pass # do something here 50. else: 51. break 52. # 用readline读完总会有回车，用replace函数删除此回车 53. loci = loci.replace("\n", "") 54. # 按照tab键分割 55. loci = loci.split(",") 56. # 经纬度读入citys 57. self.citys.append([float(loci[1]), float(loci[2]), loci[0],0]) #city=(经度，纬度，名) 58. self.original_citys = copy.deepcopy(self.citys) #深拷贝 59. self.drawnodes() 60. 61. #在地图上画结点 62. def drawnodes(self): 63. # 坐标变换 64. minX, minY = self.citys[0][0], self.citys[0][1] # 第一节点的坐标 65. maxX, maxY = minX, minY 66. # 在34个节点中寻找经度和纬度最高和最低的节点maxX，maxY，minX,minY 67. for city in self.citys[1:]: 68. if minX > city[0]: 69. minX = city[0] 70. if minY > city[1]: 71. minY = city[1] 72. if maxX < city[0]: 73. maxX = city[0] 74. if maxY < city[1]: 75. maxY = city[1] 76. w = maxX - minX # width 77. h = maxY - minY # height 78. xoffset = 120 79. yoffset = 120 80. ww = self.width - 2 * xoffset # 上下左右各留出30个像素的空白 81. hh = self.height - 300 - 2 * yoffset 82. xx = ww / float(w) # 画布大小与地图大小的关系 83. yy = hh / float(h) 84. r = 3 # 节点结点半径 85. self.nodes1 = [] 86. self.nodes2 = [] 87. for city in self.citys: 88. x = (city[0] - minX) * xx xoffset # 将经纬度坐标转换为画布上的坐标 89. y = hh - (city[1] - minY) * yy yoffset # y坐标自上而下增长 90. self.nodes1.append((x, y)) # 节点在画布上表示的坐标位置按照初始化读取的节点信息顺序保存 91. # 画出画布上的结点 92. if city[3]==0: 93. node = self.canvas.create_oval(x - r, y - r, x r, y r, 94. fill="#0000FF", # 蓝色 95. outline="#000000", # 黑色 96. tags="node", ) # 画圆形节点两点确定一个圆的位置 97. else: 98. node = self.canvas.create_oval(x - r, y - r, x r, y r, 99. fill="red", # 蓝色 100. outline="#000000", # 黑色 101. tags="node", ) # 确定圆形节点的位置 102. #self.nodes3=self.nodes1[:] 103. # 为结点添加文本信息，即相应的节点名称 104. self.canvas.create_text(x, y - 10, text=city[2]) 105. # 将画布上的结点信息保存到另一个结点列表中 106. self.nodes2.append(node) 107. self.linenodes() 108. 109. #根据传入order计算列表的顺序，也就是说，30个距离之和 110. def distance(self, order):
111. distance = 0.0
112. for i in range(-1, len(self.all_citys) - 1): #先计算最后一个和第一个节点的距离
113. index1, index2 = order[i], order[i + 1]
114. city1, city2 = self.all_citys[index1], self.all_citys[index2]
115. distance += math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)
116. return distance
117.
118. #适应度函数，返回某个基因型个体的适应度
119. def fitnessFun(self):
120. return lambda life: 1.0 / self.distance(life.gene+self.pre_gene)
121.
122. #将传入的text设置为程序标题文字
123. def title(self, text):
124. self.root.title(text)
125. #self.canvas.create_text(100, 30, text=txt, font=('黑体', 20), fill='red')
126.
127. #输出方案
128. def plan_out(self):
129. colors = [ "red", "green", "purple", "blue","pink","yellow"]*5
130. for i in range(len(self.plan)-1,-1,-1):
131. if self.plan[i]!=self.plan[i-1]:
132. self.out.append(self.plan[i])
133. if len(self.out)>=self.plan_numbers:
134. break
135. for i in range(0,len(self.out)):
136. print("PLAN {} :".format(i+1),end=" ")
137. for j in range(0,len(self.all_citys)):
138. print("-{}-".format(self.all_citys[self.out[i][j]][2]),end="")
139. print("\n总距离为：{}".format(self.distance(self.out[i])))
140. for k in range(-1, len(self.out[i]) - 1): #一共要连30条线
141. p1 = self.nodes1[self.out[i][k]]
142. p2 = self.nodes1[self.out[i][k + 1]]
143. self.canvas.create_line(p1, p2, fill=colors[i], tags="line")
144. #time.sleep(0.5)
145.
146. #将结点之间用实线连接起来
147. def line(self, order):
148. self.canvas.delete("line") #删掉连线，然后按新的顺序连线
149. for i in range(-1, len(order) - 1): #一共要连30条线
150. p1 = self.nodes1[order[i]]
151. p2 = self.nodes1[order[i + 1]]
152. self.canvas.create_line(p1, p2, fill="#000000", tags="line")
153.
154. #选择初始规定的路线
155. def choose_line(self):
156. self.n = self.evolution_times
157. self.initCitys()
158. self.prechoose()
159.
160. #绑定按钮功能
161. def bindEventsButton(self):
162. '''''
163. self.root.bind("n", self.new)
164. self.root.bind("g", self.start)
165. self.root.bind("s", self.stop)
166. '''
167. restart = tkinter.Button(self.root, text="预选路径", width=10, padx=9, bg="#32CD32", fg="#000000",command=self.choose_line)
168. restart.place(x=30, y=350)
169. restart = tkinter.Button(self.root, text="预选完成", width=10, padx=9, bg="#32CD32", fg="#000000",command=self.pre_order)
170. restart.place(x=160, y=350)
171. #重新迭代
172. restart=tkinter.Button(self.root, text ="产生初代",width=10,padx = 9,bg="#32CD32",fg="#000000",command = self.new)
173. restart.place(x=290, y=350)
174. #开始迭代
175. start=tkinter.Button(self.root, text ="开始进化",width=10,padx = 9,bg="#32CD32",fg="#000000",command = self.start)
176. start.place(x=420,y=350)
177. #start.pack()
178. #停止迭代
179. stop=tkinter.Button(self.root, text ="停止衍变",width=10,padx = 9,bg="#32CD32",fg="#000000",command = self.stop)
180. stop.place(x=550, y=350)
181.
182.
183. #next.pack()
184. #stop.pack()
185.
186. '''''
187. i = 0
188. x = 50
189. y = 400
190. v=[]
191. for city in self.citys:
192. name = city[2]
193. v.append(tkinter.IntVar())
194. #v = tkinter.IntVar()
195. if i > 5:
196. x = 50
197. y += 40
198. i = 0
199. # button = tkinter.Checkbutton(self.root, text=name, command=lambda: self.nodeselect(self.citys.index(city)))
200. # ,variable=v,command=self.nodeselect(self.citys.index(city))
201. self.posi = self.citys.index(city)
202. print(self.posi)
203. tkinter.Button(self.root, text=name,command=lambda: self.nodeselect(self.posi)).place(x=x, y=y)
204. #button.place(x=x, y=y)
205. # check.place(x=x, y=y)
206. # check.select()
207. # print(check.value)
208. # l = tkinter.Label(self.root, textvariable=v) # 为了更直观的看出选中和未选中v的表现状态，可以将其显示在Label标签里
209. # l.pack()
210. x += 100
211. i += 1
212. # print(self.citys)
213. '''
214.
215. #将结点连起来
216. def linenodes(self):
217. order = range(len(self.nodes1))
218. self.line(order)
219.
220. #初始化新的迭代
221. def new(self, evt=None):
222. self.isRunning = False
223. self.linenodes()
224. #self.prechoose()
225. self.ga = GA(aCrossRate=0.65, #交叉率
226. aMutationRage=0.035, #突变率
227. aLifeCount=self.lifeCount, #种群中的个体数
228. aGeneLenght=len(self.citys), #基因长度
229. afitnessFun=self.fitnessFun()) #适应度函数
230. self.canvas.delete("dis")
231. self.title("TSP") #标题设置为TSP
232.
233. #标记预先选择的路径
234. def nodeselect(self,index):
235. self.citys[index][3]=1 #每个节点的下标为3的地方标记为1则表示这个地方已经被预先标记
236. self.drawnodes()
237. print("当前被选中的节点有：")
238. for city in self.citys:
239. if city[3]==1:
240. print(city[2])
241.
242. #预先规定好预先选择路径的基因片段
243. def pre_order(self):
244. self.pre_citys=[]
245. self.nodes3=[]
246. temp = self.citys[:]
247. for city in temp:
248. if city[3]==1:
249. self.pre_citys.append(self.citys[self.citys.index(city)])
250. self.nodes3.append(self.nodes1[self.citys.index(city)])
251. self.nodes1.pop(self.citys.index(city))
252. self.citys.remove(city)
253. self.nodes1+=self.nodes3
254. self.pre_gene = [x for x in range(len(self.citys), len(self.citys) + len(self.pre_citys))]
255. self.all_citys=self.citys+self.pre_citys
256. self.linenodes()
257. #print("len",len(self.citys),len(self.nodes1),len(self.nodes3))
258.
259. #预先选择路径
260. def prechoose(self):
261. self.bt=[]
262. self.bt.append(tkinter.Button(self.root, text=self.original_citys[0][2],width=8,activebackground="red",command=lambda:self.nodeselect(0)).place(x=50,y=400))
263. self.bt.append(tkinter.Button(self.root, text=self.original_citys[1][2], width=8,activebackground="red",command=lambda: self.nodeselect(1)).place(x=150, y=400))
264. self.bt.append(tkinter.Button(self.root, text=self.original_citys[2][2], width=8,activebackground="red",command=lambda: self.nodeselect(2)).place(x=250, y=400))
265. self.bt.append(tkinter.Button(self.root, text="传感器3", width=8,activebackground="red",command=lambda: self.nodeselect(3)).place(x=350, y=400))
266. self.bt.append(tkinter.Button(self.root, text="传感器4", width=8,activebackground="red",command=lambda: self.nodeselect(4)).place(x=450, y=400))
267. self.bt.append(tkinter.Button(self.root, text="传感器5", width=8,activebackground="red",command=lambda: self.nodeselect(5)).place(x=550, y=400))
268. self.bt.append(tkinter.Button(self.root, text="传感器6",width=8,activebackground="red",command=lambda: self.nodeselect(6)).place(x=50, y=440))
269. self.bt.append(tkinter.Button(self.root, text="传感器7",width=8,activebackground="red",command=lambda: self.nodeselect(7)).place(x=150, y=440))
270. self.bt.append(tkinter.Button(self.root, text="传感器8", width=8,activebackground="red",command=lambda: self.nodeselect(8)).place(x=250, y=440))
271. self.bt.append(tkinter.Button(self.root, text="传感器9", width=8,activebackground="red",command=lambda: self.nodeselect(9)).place(x=350, y=440))
272. self.bt.append(tkinter.Button(self.root, text="传感器10",width=8,activebackground="red",command=lambda: self.nodeselect(10)).place(x=450, y=440))
273. self.bt.append(tkinter.Button(self.root, text="传感器11", width=8,activebackground="red",command=lambda: self.nodeselect(11)).place(x=550, y=440))
274. self.bt.append(tkinter.Button(self.root, text="传感器12", width=8,activebackground="red",command=lambda: self.nodeselect(12)).place(x=50, y=480))
275. self.bt.append(tkinter.Button(self.root, text="传感器13",width=8,activebackground="red",command=lambda: self.nodeselect(13)).place(x=150, y=480))
276. self.bt.append(tkinter.Button(self.root, text="传感器14", width=8,activebackground="red",command=lambda: self.nodeselect(14)).place(x=250, y=480))
277. self.bt.append(tkinter.Button(self.root, text="传感器15",width=8,activebackground="red",command=lambda: self.nodeselect(15)).place(x=350, y=480))
278. self.bt.append(tkinter.Button(self.root, text="传感器16",width=8,activebackground="red",command=lambda: self.nodeselect(16)).place(x=450, y=480))
279. self.bt.append(tkinter.Button(self.root, text="传感器17",width=8,activebackground="red",command=lambda: self.nodeselect(17)).place(x=550, y=480))
280. self.bt.append(tkinter.Button(self.root, text="传感器18",width=8,activebackground="red",command=lambda: self.nodeselect(18)).place(x=50, y=520))
281. self.bt.append(tkinter.Button(self.root, text="传感器19",width=8,activebackground="red",command=lambda: self.nodeselect(19)).place(x=150, y=520))
282. self.bt.append(tkinter.Button(self.root, text="传感器20",width=8,activebackground="red",command=lambda: self.nodeselect(20)).place(x=250, y=520))
283. self.bt.append(tkinter.Button(self.root, text="传感器21",width=8,activebackground="red",command=lambda: self.nodeselect(21)).place(x=350, y=520))
284. self.bt.append(tkinter.Button(self.root, text="传感器22",width=8,activebackground="red",command=lambda: self.nodeselect(22)).place(x=450, y=520))
285. self.bt.append(tkinter.Button(self.root, text="传感器23",width=8,activebackground="red",command=lambda: self.nodeselect(23)).place(x=550, y=520))
286. self.bt.append(tkinter.Button(self.root, text="传感器24",width=8,activebackground="red",command=lambda: self.nodeselect(24)).place(x=50, y=560))
287. self.bt.append(tkinter.Button(self.root, text="传感器25",width=8,activebackground="red",command=lambda: self.nodeselect(25)).place(x=150, y=560))
288. self.bt.append(tkinter.Button(self.root, text="传感器26",width=8,activebackground="red",command=lambda: self.nodeselect(26)).place(x=250, y=560))
289. self.bt.append(tkinter.Button(self.root, text="传感器27",width=8,activebackground="red",command=lambda: self.nodeselect(27)).place(x=350, y=560))
290. self.bt.append(tkinter.Button(self.root, text="传感器28",width=8,activebackground="red",command=lambda: self.nodeselect(28)).place(x=450, y=560))
291. self.bt.append(tkinter.Button(self.root, text="传感器29",width=8,activebackground="red",command=lambda: self.nodeselect(29)).place(x=550,y=560))
292.
293. #print(self.citys)
294. # tkinter.Radiobutton(self.root, variable=v, text=name,value=1, bd=0, relief='sunken', ).place(x=x - 15, y=y - 15)
295.
296. #开始迭代
297. def start(self,evt=None):
298. self.isRunning = True
299. #print(self.all_citys)
300. while self.n>0 and self.isRunning:
301. self.ga.next()
302. #self.ga.best.gene+=self.pre_gene #加上预先规定好的路径
303. best_gene = self.ga.best.gene+self.pre_gene
304. print("第{}代种群最好的基因为：{}".format(self.evolution_times-self.n+1,best_gene))
305. distance_sum = self.distance(best_gene)
306. self.plan.append(best_gene)
307. self.line(best_gene)
308. self.title("%d generations" % self.ga.generation)
309. self.canvas.delete("dis")
310. self.canvas.create_text(100, 300, text="Distance=%3f" % distance_sum,tag="dis",fill="#3CB371",font="黑体")
311. self.canvas.update()
312. self.n-=1
313. self.plan_out()
314.
315. #停止迭代
316. def stop(self, evt=None):
317. self.isRunning = False
318.
319. #进入到事件(消息)循环
320. def mainloop(self):
321. self.root.mainloop()
322. '''''
323. def drawline():
324. n = 5
325. while n!=0:
326. if n < 5:
327. colors = ["red", "green", "yellow", "purple", "blue"]
328. root = tkinter.Tk()
329. plan_window = tkinter.Canvas(root, width=660, height=400, bg='white')
330. line(self.ga.best.gene + pre_gene)
331. initCitys()
332. drawnodes()
333. for i in range(-1, len(order) - 1): # 一共要连34条线
334. p1 = nodes1[order[i]]
335. p2 = nodes1[order[i + 1]]
336. plan_window.create_line(p1, p2, fill=colors[n], tags="line")
337. n-=1
338. root.mainloop()
339. '''
340. def main():
341. #global line_solotion
342. #line_solotion = []
343. evolution_times = int(input("迭代次数："))
344. plan_numbers = int(input("输出方案个数："))
345. tsp = TSP_WIN(tkinter.Tk(),evolution_times,plan_numbers)
346. tsp.mainloop()
347.
348. if __name__ == '__main__':
349. main()