概要
我的上一篇写遗传算法解决排序问题，当中思想借鉴了遗传算法解决TSP问题，本质上可以认为这是一类问题，就是这样认为：寻找到一个序列X，使F（X）最大。
详解介绍
排序问题：寻找一个序列，使得这个序列的逆序对的倒数最大。
TSP问题：寻找一个序列，使得这个序列的总路径长的倒数最大。
这两个问题有一个共同的特点是，所有的节点都要用上，而使用遗传算法解决排序问题（每一个格子可以认为是一个节点），是需要从众多的节点之中寻找到某些节点构成一个序列X。
序列X必须满足的条件是：
- 相邻节点直接邻接
- 无重复节点（有重复的相当于走回头路）
- 序列的起点和终点必须是已知的点
第一个需要解决的问题是初代如何选择：
- 随机选择然后判断是否符合上面的三个条件（垃圾）
- 从起点开始随机生成到终点的序列
第二种做法的另一个问题就是随机性太大，可能会走比较长的路（其实也是可以采用的），为了解决这个问题，我才用了A*算法的启发式思维，将当前点和目标点的蔓哈顿距离作为适应度加入到优先队列中。
算法步骤
- 将起点加入到优先队列中
- 从优先队列中取出顶部顶点p0，将p0加入到Path(路径结果),如果p0是终点结束；
- 随机获取其周围的8个点中的一个p1
- 比较p0到目标点的曼哈顿距离|p0-target| 和p1到目标点的距离|p1-target|
- 如果|p1-target|<|p0-target|并且p1 not in Path, 将p1加入优先队列，p0<-p1；转到2
使用这种策略不仅引入了随机性，而且路径也比较合适，收敛比较快。
选择
这一步比较简单，就是普通的轮盘法就ok
交叉和变异
目前还没有想到策略（后面补充）
代码实现
1 import random 2 import math 3 import copy 4 from tkinter import * 5 import tkinter.font as tkFont 6 import time, threading 7 8 WIDTH = 100 9 HEIGHT = 100 10 MIN = 0 11 MAX = WIDTH * HEIGHT - 1 12 13 PATH_COUNT = 100 14 # 交叉概率 15 cross_p = 0.6 16 # 变异概率 17 variation_p = 0.4 18 # 变异次数 19 variation_times = 4 20 21 DIS_1 = 1.4 22 DIS_2 = 1 23 24 S = 0 25 D = 0 26 27 best_path = [] 28 best_path_index = 0 29 30 res_fit = [] 31 32 # 路径 33 paths = [] 34 # 最优路径 35 # 迭代次数 36 ITERATION_COUNT = 100 37 # 38 direction_arr = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)] 39 40 41 def is_valid(point): 42 if point[0] < 0 or point[1] < 0 or point[0] >= WIDTH or point[1] >= HEIGHT: 43 return False 44 return True 45 46 47 # 计算欧式距离 48 def distance(p1, p2): 49 return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) 50 51 52 # 标号转坐标 53 def mark2position(mark): 54 return (mark % WIDTH, int(mark / WIDTH)) 55 56 57 def position2mark(position): 58 return position[1] * WIDTH + position[0] 59 60 61 # 5 6 7 62 # 3 4 63 # 0 1 2 64 def generate_one_path(start, end): 65 res = [] 66 res.append(start) 67 68 s = start 69 target_point = mark2position(end) 70 dis = distance(mark2position(start), target_point) 71 72 while (s != end): 73 pos = mark2position(s) 74 r = random.randint(0, 7) 75 pos = (pos[0] + direction_arr[r][0], pos[1] + direction_arr[r][1]) 76 temp_dis = distance(pos, target_point) 77 if is_valid(pos) and temp_dis <= dis: 78 s = position2mark(pos) 79 dis = temp_dis 80 res.append(s) 81 return res 82 83 84 # 初代 85 def init(count): 86 res = [] 87 for i in range(0, count): 88 res.append(generate_one_path(S, D)) 89 return res 90 91 92 # 计算一条路径的适应度值 93 def one_path_fit_val(path): 94 sm = 0 95 for i in range(1, len(path)): 96 w = int(math.fabs(path[i - 1] - path[i])) 97 if w == 1 or w == WIDTH: 98 sm += DIS_2 99 else: 100 sm += DIS_1 101 return MAX / sm 102 103 104 # 计算适应度值 105 def fitness(): 106 res = [] 107 max_fit = -1 108 global best_path 109 global best_path_index 110 111 temp_best_path = [] 112 113 for i in range(len(paths)): 114 f = one_path_fit_val(paths[i]) 115 res.append(f) 116 if f > max_fit: 117 max_fit = f 118 temp_best_path = paths[i] 119 best_path_index = i 120 best_path = copy.deepcopy(temp_best_path) 121 res_fit.append(max_fit) 122 return res 123 124 125 # 累计概率 126 def cumulative_probability(fits): 127 res = [] 128 sm = sum(fits) 129 temp = fits[0] / sm 130 res.append(temp) 131 for i in range(1, len(fits)): 132 res.append(res[i - 1] + fits[i] / sm) 133 return res 134 135 136 # 选择 产生下一代 137 def choose(pArr, count): 138 res = [] 139 for i in range(count): 140 p = random.random() 141 for j in range(len(pArr)): 142 if p <= pArr[j]: 143 res.append(paths[j]) 144 break 145 return res 146 147 148 def cross_one_times(path1, path2): 149 # 求交集 150 temp = list(set(path1[1:-1]).intersection(set(path2[1:-1]))) 151 sz = len(temp) 152 if sz == 0: 153 return (path1, path2) 154 r = random.random() 155 if r > cross_p: 156 index = random.randint(0, sz - 1) 157 e = temp[index] 158 t1 = path1.index(e) 159 t2 = path2.index(e) 160 p1 = path1[:t1] 161 p2 = path2[t2:] 162 p3 = path2[:t2] 163 p4 = path1[t1:] 164 p1.extend(p2) 165 p3.extend(p4) 166 return (p1, p3) 167 else: 168 return (path1, path2) 169 170 171 def cross(): 172 n = len(paths) 173 res = [] 174 for i in range(1, n, 2): 175 p = cross_one_times(paths[i], paths[i - 1]) 176 res.extend(p) 177 178 # 奇数情况 179 if len(res) < n: 180 res.append(paths[n - 1]) 181 return res 182 183 184 # 判断三点之间是否联通 185 def is_valid_3_mark(m1, m2, m3): 186 # 重复 187 if m1 == m2 or m1 == m3 or m2 == m3: 188 return False 189 if m2 < MIN or m2 > MAX: 190 return False 191 # 不联通 192 if not (m1 + 1 == m2 or m1 - 1 == m2 or m1 + WIDTH == m2 or m1 - WIDTH == m2 193 or m1 + WIDTH + 1 == m2 or m1 + WIDTH - 1 == m2 194 or m1 - WIDTH + 1 == m2 or m1 - WIDTH - 1 == m2): 195 return False 196 # 不联通 197 if not (m3 + 1 == m2 or m3 - 1 == m2 or m3 + WIDTH == m2 or m3 - WIDTH == m2 198 or m3 + WIDTH + 1 == m2 or m3 + WIDTH - 1 == m2 199 or m3 - WIDTH + 1 == m2 or m3 - WIDTH - 1 == m2): 200 return False 201 return True 202 203 204 def variation_one_times(path): 205 r = random.random() 206 if r < variation_p: 207 return path 208 else: 209 sz = len(path) 210 if sz <= 2: 211 return path 212 # 变异点 213 prob_mark = [] 214 var_index = random.randint(1, sz - 2) 215 pre_mark = path[var_index - 1] 216 cnt_mark = path[var_index] 217 next_mark = path[var_index + 1] 218 # 8中情况 219 temp_mark = [cnt_mark + 1, cnt_mark - 1, cnt_mark + WIDTH, cnt_mark - WIDTH, cnt_mark + WIDTH + 1, 220 cnt_mark + WIDTH - 1, cnt_mark - WIDTH - 1, cnt_mark - WIDTH + 1] 221 for e in temp_mark: 222 if is_valid_3_mark(pre_mark, e, next_mark): 223 prob_mark.append(e) 224 225 if len(prob_mark) == 0: 226 return path 227 changed_mark = prob_mark[random.randint(0, len(prob_mark) - 1)] 228 path[var_index] = changed_mark 229 return path 230 231 232 def variation(): 233 res = paths 234 for i in range(variation_times): 235 temp = [] 236 for e in res: 237 temp.append(variation_one_times(e)) 238 res = temp 239 return res 240 241 242 def output(g, f): 243 print("第" + str(g) + "代：最优路径：", end="", file=f) 244 print(best_path, end="", file=f) 245 print("适应度: ", end="", file=f) 246 print(fits[best_path_index], file=f) 247 for i, path in enumerate(paths): 248 print(str(i + 1) + ". ", end="", file=f) 249 print(path, end="", file=f) 250 print("适应度值：" + str(fits[i]), file=f) 251 252 253 def mark_screen_position(mark, x_min, y_max): 254 temp_p = mark2position(mark) 255 x = temp_p[0] - x_min 256 y = y_max - temp_p[1] 257 return (x, y) 258 259 260 def show(path, title): 261 canvas_width = 1000 262 point_r = 2 263 show_mark_min_width = 10 264 temp = [] 265 for p in path: 266 temp.append(p % 100) 267 x_min = min(temp) 268 x_max = max(temp) 269 temp.clear() 270 for p in path: 271 temp.append(int(p / 100)) 272 y_min = min(temp) 273 y_max = max(temp) 274 d = max(x_max - x_min + 1, y_max - y_min + 1) 275 grid_width = int(canvas_width / d) 276 canvas_width = grid_width * d 277 win = Tk() 278 win.title(title) 279 win.geometry(str(canvas_width) + "x" + str(canvas_width) + "+100+100") 280 can = Canvas(win, width=canvas_width, height=canvas_width, bg="white") 281 for i in range(0, canvas_width, grid_width): 282 can.create_line((0, i), (canvas_width, i)) 283 284 for i in range(0, canvas_width, grid_width): 285 can.create_line((i, 0), (i, canvas_width)) 286 ft = tkFont.Font(root=win, family='Fixdsys', size=int(20 / 4), weight=tkFont.BOLD) 287 if grid_width >= show_mark_min_ 288 for x in range(0, d): 289 for y in range(0, d): 290 s = position2mark((x + x_min, y_max - y)) 291 can.create_text(x * grid_width + grid_width / 2, y * grid_width + grid_width / 2, text=s, 292 font=ft) 293 sz = len(path) 294 for i in range(0, sz - 1): 295 p1 = mark_screen_position(path[i], x_min, y_max) 296 p2 = mark_screen_position(path[i + 1], x_min, y_max) 297 can.create_line((p1[0] * grid_width + grid_width / 2, p1[1] * grid_width + grid_width / 2), 298 (p2[0] * grid_width + grid_width / 2, p2[1] * grid_width + grid_width / 2), fill="red", width=3) 299 if i == 0: { 300 can.create_oval( 301 (p1[0] * grid_width + grid_width / 2 - point_r, p1[1] * grid_width + grid_width / 2 - point_r, 302 p1[0] * grid_width + grid_width / 2 + point_r, p1[1] * grid_width + grid_width / 2 + point_r), 303 fill="blue") 304 } 305 can.create_oval((p2[0] * grid_width + grid_width / 2 - point_r, p2[1] * grid_width + grid_width / 2 - point_r, 306 p2[0] * grid_width + grid_width / 2 + point_r, p2[1] * grid_width + grid_width / 2 + point_r), 307 fill="blue") 308 can.pack() 309 win.mainloop() 310 311 312 # run point 313 random.seed() 314 S = random.randint(MIN, MAX) 315 D = random.randint(MIN, MAX) 316 while (S == D): 317 D = random.randint(MIN, MAX) 318 g = 1 319 fp = open("1.txt", "w", encoding="utf-8") 320 321 # 初代 322 paths = init(PATH_COUNT) 323 fits = fitness() # 适应度计算 324 output(g, fp) 325 g = g + 1 326 327 origin_best_path = [] 328 329 for i in range(ITERATION_COUNT): 330 pArr = cumulative_probability(fits) # 累计概率 331 paths = choose(pArr, PATH_COUNT - 1) # 选择 332 paths = cross() # 交叉 333 paths = variation() # 变异 334 paths.append(best_path) 335 if i == 0: 336 origin_best_path = copy.deepcopy(best_path) 337 fits = fitness() # 适应度计算 338 output(g, fp) 339 g = g + 1 340 fp.flush() 341 fp.close() 342 343 fp = open("2.txt", "w", encoding="utf-8") 344 fp.write("最大适应度值列表： ") 345 for e in res_fit: 346 fp.write(format(e, ".2f")) 347 fp.write(" ") 348 fp.flush() 349 fp.close() 350 351 t1 = threading.Thread(target=show, args=(origin_best_path, "初代最好的路径")) 352 t2 = threading.Thread(target=show, args=(best_path, "最好的路径")) 353 t1.start() 354 t2.start() 355 t1.join() 356 t2.join()
效果图
图形显示
