|
- import numpy as np
- from matplotlib import pyplot as plt
- import copy
-
- def route_to_coordinates(routes):#解码路径点坐标集
- coordinates=[]
- for route in routes:
- temp1=[]
- temp2=[]
- for i in route:
- temp1.append(i//9)
- temp2.append(i%9)
- coordinates.append([temp1,temp2])
- return coordinates
-
- def routes_to_control_command(routes):
- control_command_set=[]
- uav_move_distance=0.5
-
- for route in routes:
- if type(route)==list:
- route=route*8
- control_command=[]
- for i in range(len(route)-1):
- dx=int((route[i+1]//9-route[i]//9)/uav_move_distance)
- dy=int((route[i+1]%9-route[i]%9)/uav_move_distance)
- if dx>0:#需要向上移动0
- control_command = control_command + [[0]] * abs(dx)
- elif dx<0:#需要向下移动1
- control_command = control_command + [[1]] * abs(dx)
- if dy>0:#需要向右移动3
- control_command = control_command + [[3]] * abs(dy)
- elif dy<0:#需要向左移动2
- control_command = control_command + [[2]] * abs(dy)
- control_command_set.append(control_command)
- command_length_lst=[len(command) for command in control_command_set]
- max_command_length=max(command_length_lst)
- for i in range(4):
- if command_length_lst[i]<max_command_length:
- control_command_set[i]=control_command_set[i]+[[4]]*(max_command_length-command_length_lst[i])
- control_command_set=np.array(control_command_set)
- control_command_set=control_command_set.transpose([1,0,2])
- return control_command_set
-
-
- def visualization(routes):#讲路径点坐标集可视化
- #routes:
- fig=plt.figure('routes')
- coordinates=route_to_coordinates(routes)
- for i in range(4):
- plt.plot(coordinates[i][0],coordinates[i][1])
- plt.show()
-
-
- def compute_routes(entity,break_points,start_position):
- break_points.insert(0, 0)
- break_points.append(len(entity))
- routes = []
- for i in range(len(break_points) - 1):
- routes.append(entity[break_points[i]:break_points[i + 1]])
- # 上面代码的作用是将路径拆成m段。break_points的长度设置为k时,则将路径拆分成了k+1段。
- for i, route in enumerate(routes):
- for item in start_position:
- if item in route:
- route.remove(item)
- route.insert(0, start_position[i]) # 此处给每段路径添上起点
- return routes
-
-
- def init_population(length, num):#初始化
- population=np.random.permutation(range(length))
- for i in range(num-1):
- population=np.vstack((population,np.random.permutation(range(length))))
- return population.tolist()
-
-
- def aimFunction(entity, DMAT, break_points, start_position):
- """
- 目标函数
- :param entity: 个体
- :param DMAT: 距离矩阵
- :param break_points: 切断点 eg:break_points=[1,18,65,74] len(break_points)=4则表示切成5段
- :return:适应度函数值
- """
- distance = 0
- routes=compute_routes(entity,break_points,start_position)
- for route in routes:
- for i in range(len(route) - 1):
- distance += DMAT[route[i], route[i + 1]]
-
- return 1.0 / distance
-
- # 返回种群所有个体的适应度列表
- def fitness(population, DMAT, break_points, start_position):
- """
- 适应度
- :param population: 种群
- :param DMAT: 距离矩阵
- :param break_points:切断点
- :param aimFunction: 目标函数
- :return:
- """
-
- value = []
- for i in range(len(population)):
- value.append(aimFunction(population[i], DMAT, copy.deepcopy(break_points),start_position))
- # weed out negative value
- if value[i] < 0:
- value[i] = 0
- return value
-
- # 这里传入的是种群和每个个体的适应度
- # 这里的轮盘赌与蚁群算法的有一定区别。这里对适应度归一化得到概率之后,每个个体被选中的概率就是这个概率
- # 对每次被选中的个体的数目没有限制,完全随机,限制的是选择次数n与种群数目相同,使得新的种群数量与旧的种群一致
-
- def selection(population, value):
- # 轮盘赌选择
- fitness_sum = []
- for i in range(len(value)):
- if i == 0:
- fitness_sum.append(value[i])
- else:
- fitness_sum.append(fitness_sum[i - 1] + value[i])
-
- for i in range(len(fitness_sum)):
- fitness_sum[i] /= sum(value)
-
- # select new population
- population_new = []
- for i in range(len(value)):
- rand = np.random.uniform(0, 1)
- for j in range(len(value)):
- if j == 0:
- if 0 < rand and rand <= fitness_sum[j]:
- population_new.append(population[j])
-
- else:
- if fitness_sum[j - 1] < rand and rand <= fitness_sum[j]:
- population_new.append(population[j])
- return population_new
-
- # 对于被选中的双亲,随机两两组合。并以pc的概率交配
- # 若没有被选择交配,则直接双亲进入下一代。如果被选择,则交换中间片段。
- def amend(entity, low, high):
- """
- 修正个体
- :param entity: 个体
- :param low: 交叉点最低处
- :param high: 交叉点最高处
- :return:
- """
- length = len(entity)
- cross_gene = entity[low:high] # 交叉基因
- not_in_cross = [] # 应交叉基因
- raw = entity[0:low] + entity[high:] # 非交叉基因
-
- for i in range(length):
- if not i in cross_gene:
- not_in_cross.append(i)
-
- error_index = []
- for i in range(len(raw)):
- if raw[i] in not_in_cross:
- not_in_cross.remove(raw[i])
- else:
- error_index.append(i)
- for i in range(len(error_index)):
- raw[error_index[i]] = not_in_cross[i]
-
- entity = raw[0:low] + cross_gene + raw[low:]
-
- return entity
-
- def crossover(population_new, pc):
- """
- 交叉
- :param population_new: 种群
- :param pc: 交叉概率
- :return:
- """
- half = int(len(population_new) / 2)
- father = population_new[:half]
- mother = population_new[half:]
- np.random.shuffle(father)
- np.random.shuffle(mother)
- offspring = []
- for i in range(half):
- if np.random.uniform(0, 1) <= pc:
- cut1 = np.random.randint(0, len(population_new[0]))
- cut2 = np.random.randint(0, len(population_new[0]))
- if cut1 > cut2:
- cut1, cut2 = cut2, cut1
- if cut1 == cut2:
- son = father[i]
- daughter = mother[i]
- else:
- son = father[i][0:cut1] + mother[i][cut1:cut2] + father[i][cut2:]
- son = amend(son, cut1, cut2)
- daughter = mother[i][0:cut1] + father[i][cut1:cut2] + mother[i][cut2:]
- daughter = amend(daughter, cut1, cut2)
-
- else:
- son = father[i]
- daughter = mother[i]
- offspring.append(son)
- offspring.append(daughter)
-
- return offspring
-
- # 这里的变异是最简单的变异法则,直接随机选取两个位置上的数进行交换
- def mutation(offspring, pm):
- for i in range(len(offspring)):
- if np.random.uniform(0, 1) <= pm:
- position1 = np.random.randint(0, len(offspring[i]))
- position2 = np.random.randint(0, len(offspring[i]))
- # print(offspring[i])
- offspring[i][position1], offspring[i][position2] = offspring[i][position2], offspring[i][position1]
- # print(offspring[i])
- return offspring
-
- def compute_distance_graph(points_matrix):#根据目标点位置坐标计算距离矩阵
- #point_matrix:list (point_num,2)
- points_num=len(points_matrix)
- distance_graph=np.zeros([points_num,points_num])
- for i in range(points_num):
- for j in range(points_num):
- # distance_graph[i,j]=math.sqrt((points_matrix[i][0]-points_matrix[j][0])**2+(points_matrix[i][1]-points_matrix[j][1])**2)#欧氏距离
- distance_graph[i, j] = abs(points_matrix[i][0]-points_matrix[j][0])+abs(points_matrix[i][1]-points_matrix[j][1])#chessboard——distance
- return distance_graph
-
- def mTSP_main(start_position):
- EVERY_GENERATION_NUM=90
- TOTAL_GENERATION_NUM=40000
- CROSSOVER_PROBILITY=0.65
- MUTATION_PROBILITY=0.02
- points_matrix = [[i, j] for i in range(9) for j in range(9)]#目标点矩阵 list:(points_num,2)
- points_num = len(points_matrix)
- DMAT = compute_distance_graph(points_matrix)#计算距离矩阵 DMAT:(points_num,points_num)
- break_points = [i * (points_num // 4) for i in range(1, 4)] # 将所有点从中间断开成4段,每段代表一个旅行商,可以在任意位置切断。
- population = init_population(points_num, EVERY_GENERATION_NUM) # 生成90个初始个体 population:list (90,points_num)
- t = [] # 记录每一步的最小路径的距离
- all_routes = [] # 记录每一步的最小路径
- for i in range(TOTAL_GENERATION_NUM):
- # selection
- value = fitness(population, DMAT, break_points, start_position)
- population_new = selection(population, value)
- # crossover
- offspring = crossover(population_new, CROSSOVER_PROBILITY)
- # mutation
- population = mutation(offspring, MUTATION_PROBILITY)
- result = []
- for j in range(len(population)):
- result.append(1.0 / aimFunction(population[j], DMAT, copy.deepcopy(break_points),start_position))
- t.append(min(result))
- min_entity = population[result.index(min(result))]
- routes = compute_routes(min_entity,copy.deepcopy(break_points),start_position)
- all_routes.append(routes)
- best_routes=all_routes[t.index(min(t))]
- print(min(t)) # 每次迭代的最优路径
- print('最短路径距离之和为', min(t), '米')
- print('最优的路径为:',all_routes[t.index(min(t))])
- # plt.plot(t) # 画出每次迭代的最优个体对应的环路程
- # visualization(best_routes)
- # plt.show()
- return routes_to_control_command(best_routes)
-
- if __name__ == '__main__':
- start_position=[0,20,40,60]
- mTSP_main(start_position)
|