diff options
| -rw-r--r-- | basic_aco.py | 16 | ||||
| -rw-r--r-- | example1.py | 10 | ||||
| -rw-r--r-- | example2.py | 11 | ||||
| -rw-r--r-- | multiple_ant_colony_system.py | 65 | ||||
| -rw-r--r-- | vprtw_aco_figure.py | 40 |
5 files changed, 105 insertions, 37 deletions
diff --git a/basic_aco.py b/basic_aco.py index bbadb52..b6e2d50 100644 --- a/basic_aco.py +++ b/basic_aco.py @@ -8,7 +8,8 @@ from queue import Queue class BasicACO: - def __init__(self, graph: VrptwGraph, ants_num=10, max_iter=200, beta=2): + def __init__(self, graph: VrptwGraph, ants_num=10, max_iter=200, beta=2, q0=0.1, + whether_or_not_to_show_figure=True): super() # graph 结点的位置、服务时间信息 self.graph = graph @@ -18,18 +19,16 @@ class BasicACO: self.max_iter = max_iter # vehicle_capacity 表示每辆车的最大载重 self.max_load = graph.vehicle_capacity - # 信息素强度 - self.Q = 1 # beta 启发性信息重要性 self.beta = beta # q0 表示直接选择概率最大的下一点的概率 - self.q0 = 0.1 + self.q0 = q0 # best path self.best_path_distance = None self.best_path = None self.best_vehicle_num = None - self.whether_or_not_to_show_figure = True + self.whether_or_not_to_show_figure = whether_or_not_to_show_figure def run_basic_aco(self): # 开启一个线程来跑_basic_aco，使用主线程来绘图 @@ -85,6 +84,7 @@ class BasicACO: if self.best_path is None: self.best_path = ants[int(best_index)].travel_path self.best_path_distance = paths_distance[best_index] + start_iteration = iter # 图形化展示 if self.whether_or_not_to_show_figure: @@ -93,7 +93,7 @@ class BasicACO: elif paths_distance[best_index] < self.best_path_distance: self.best_path = ants[int(best_index)].travel_path self.best_path_distance = paths_distance[best_index] - + start_iteration = iter # 图形化展示 if self.whether_or_not_to_show_figure: path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance)) @@ -102,9 +102,11 @@ class BasicACO: # 更新信息素表 self.graph.global_update_pheromone(self.best_path, self.best_path_distance) - given_iteration = 50 + given_iteration = 100 if iter - start_iteration > given_iteration: print('iteration is up: can not find better solution in %d iteration' % given_iteration) + print('exit.') + break def select_next_index(self, ant): """ diff --git a/example1.py b/example1.py index c7629e8..370a5d7 100644 --- a/example1.py +++ b/example1.py @@ -3,8 +3,12 @@ from multiple_ant_colony_system import MultipleAntColonySystem if __name__ == '__main__': - file_path = './solomon-100/c101.txt' - graph = VrptwGraph(file_path) + file_path = './solomon-100/rc101.txt' + ants_num = 10 + beta = 2 + q0 = 0.1 + show_figure = True - macs = MultipleAntColonySystem(graph) + graph = VrptwGraph(file_path) + macs = MultipleAntColonySystem(graph, ants_num=ants_num, beta=beta, q0=q0, whether_or_not_to_show_figure=show_figure) macs.run_multiple_ant_colony_system() diff --git a/example2.py b/example2.py index 16e12b2..8afb652 100644 --- a/example2.py +++ b/example2.py @@ -4,7 +4,14 @@ from basic_aco import BasicACO if __name__ == '__main__': file_path = './solomon-100/c101.txt' + ants_num = 10 + max_iter = 200 + beta = 2 + q0 = 0.1 + show_figure = True + graph = VrptwGraph(file_path) + basic_aco = BasicACO(graph, ants_num=ants_num, max_iter=max_iter, beta=beta, q0=q0, + whether_or_not_to_show_figure=show_figure) - vrptw = BasicACO(graph) - vrptw.run_basic_aco()
\ No newline at end of file + basic_aco.run_basic_aco() diff --git a/multiple_ant_colony_system.py b/multiple_ant_colony_system.py index 9a9dcb1..888c84b 100644 --- a/multiple_ant_colony_system.py +++ b/multiple_ant_colony_system.py @@ -11,30 +11,24 @@ import time class MultipleAntColonySystem: - def __init__(self, graph: VrptwGraph, ants_num=10, max_iter=200, alpha=1, beta=2): + def __init__(self, graph: VrptwGraph, ants_num=10, beta=2, q0=0.1, whether_or_not_to_show_figure=True): super() # graph 结点的位置、服务时间信息 self.graph = graph # ants_num 蚂蚁数量 self.ants_num = ants_num - # max_iter 最大迭代次数 - self.max_iter = max_iter # vehicle_capacity 表示每辆车的最大载重 self.max_load = graph.vehicle_capacity - # 信息素强度 - self.Q = 1 - # alpha 信息素信息重要新 - self.alpha = alpha # beta 启发性信息重要性 self.beta = beta # q0 表示直接选择概率最大的下一点的概率 - self.q0 = 0.1 + self.q0 = q0 # best path self.best_path_distance = None self.best_path = None self.best_vehicle_num = None - self.whether_or_not_to_show_figure = True + self.whether_or_not_to_show_figure = whether_or_not_to_show_figure @staticmethod def stochastic_accept(index_to_visit, transition_prob): @@ -60,6 +54,19 @@ class MultipleAntColonySystem: @staticmethod def new_active_ant(ant: Ant, vehicle_num: int, local_search: bool, IN: np.numarray, q0: float, beta: int, stop_event: Event): + """ + 按照指定的vehicle_num在地图上进行探索，所使用的vehicle num不能多于指定的数量，acs_time和acs_vehicle都会使用到这个方法 + 对于acs_time来说，需要访问完所有的结点（路径是可行的），尽量找到travel distance更短的路径 + 对于acs_vehicle来说，所使用的vehicle num会比当前所找到的best path所使用的车辆数少一辆，要使用更少的车辆，尽量去访问结点，如果访问完了所有的结点（路径是可行的），就将通知macs + :param ant: + :param vehicle_num: + :param local_search: + :param IN: + :param q0: + :param beta: + :param stop_event: + :return: + """ # print('[new_active_ant]: start, start_index %d' % ant.travel_path[0]) # 在new_active_ant中，最多可以使用vehicle_num个车，即最多可以包含vehicle_num+1个depot结点，由于出发结点用掉了一个，所以只剩下vehicle个depot @@ -128,6 +135,18 @@ class MultipleAntColonySystem: @staticmethod def acs_time(new_graph: VrptwGraph, vehicle_num: int, ants_num: int, q0: float, beta: int, global_path_queue: Queue, path_found_queue: Queue, stop_event: Event): + """ + 对于acs_time来说，需要访问完所有的结点（路径是可行的），尽量找到travel distance更短的路径 + :param new_graph: + :param vehicle_num: + :param ants_num: + :param q0: + :param beta: + :param global_path_queue: + :param path_found_queue: + :param stop_event: + :return: + """ # 最多可以使用vehicle_num辆车，即在path中最多包含vehicle_num+1个depot中，找到路程最短的路径， # vehicle_num设置为与当前的best_path一致 @@ -182,8 +201,18 @@ class MultipleAntColonySystem: @staticmethod def acs_vehicle(new_graph: VrptwGraph, vehicle_num: int, ants_num: int, q0: float, beta: int, global_path_queue: Queue, path_found_queue: Queue, stop_event: Event): - - # 最多可以使用vehicle_num辆车，即在path中最多包含vehicle_num+1个depot中，找到路程最短的路径， + """ + 对于acs_vehicle来说，所使用的vehicle num会比当前所找到的best path所使用的车辆数少一辆，要使用更少的车辆，尽量去访问结点，如果访问完了所有的结点（路径是可行的），就将通知macs + :param new_graph: + :param vehicle_num: + :param ants_num: + :param q0: + :param beta: + :param global_path_queue: + :param path_found_queue: + :param stop_event: + :return: + """ # vehicle_num设置为比当前的best_path少一个 print('[acs_vehicle]: start, vehicle_num %d' % vehicle_num) global_best_path = None @@ -254,7 +283,10 @@ class MultipleAntColonySystem: new_graph.global_update_pheromone(global_best_path, global_best_distance) def run_multiple_ant_colony_system(self): - # _multiple_ant_colony_system，使用主线程来绘图 + """ + 开启另外的线程来跑multiple_ant_colony_system， 使用主线程来绘图 + :return: + """ path_queue_for_figure = Queue() multiple_ant_colony_system_thread = Thread(target=self._multiple_ant_colony_system, args=(path_queue_for_figure,)) multiple_ant_colony_system_thread.start() @@ -270,6 +302,11 @@ class MultipleAntColonySystem: path_queue_for_figure.put(PathMessage(None, None)) def _multiple_ant_colony_system(self, path_queue_for_figure: Queue): + """ + 调用acs_time 和 acs_vehicle进行路径的探索 + :param path_queue_for_figure: + :return: + """ # 在这里需要两个队列，time_what_to_do、vehicle_what_to_do， 用来告诉acs_time、acs_vehicle这两个线程，当前的best path是什么，或者让他们停止计算 global_path_to_acs_time = Queue() global_path_to_acs_vehicle = Queue() @@ -353,7 +390,9 @@ class MultipleAntColonySystem: start_time = time.time() print('-' * 50) - print('[macs]: vehicle num of found path (%d) better than best path\'s (%d)' % (found_path_used_vehicle_num, best_vehicle_num)) + print('[macs]: vehicle num of found path (%d) better than best path\'s (%d), found path distance is %f' + % (found_path_used_vehicle_num, best_vehicle_num, found_path_distance)) + print('-' * 50) self.best_path = found_path self.best_vehicle_num = found_path_used_vehicle_num diff --git a/vprtw_aco_figure.py b/vprtw_aco_figure.py index 01dbc80..6fa8765 100644 --- a/vprtw_aco_figure.py +++ b/vprtw_aco_figure.py @@ -18,42 +18,58 @@ class VrptwAcoFigure: self.figure = plt.figure(figsize=(10, 10)) self.figure_ax = self.figure.add_subplot(1, 1, 1) self.path_queue = path_queue - self._dot_color = 'k' - self._line_color_list = ['r', 'y', 'g', 'c', 'b', 'm'] + self._depot_color = 'k' + self._customer_color = 'steelblue' + self._line_color = 'darksalmon' def _draw_point(self): - # 先画出图中的点 - self.figure_ax.plot(list(node.x for node in self.nodes), - list(node.y for node in self.nodes), '%s.' % self._dot_color) - self.figure.show() + # 画出depot + self.figure_ax.scatter([self.nodes[0].x], [self.nodes[0].y], c=self._depot_color, label='depot', s=40) + + # 画出customer + self.figure_ax.scatter(list(node.x for node in self.nodes[1:]), + list(node.y for node in self.nodes[1:]), c=self._customer_color, label='customer', s=20) plt.pause(0.5) def run(self): + # 先绘制出各个结点 self._draw_point() + self.figure.show() # 从队列中读取新的path，进行绘制 while True: if not self.path_queue.empty(): + # 取队列中最新的一个path，其他的path丢弃 info = self.path_queue.get() while not self.path_queue.empty(): info = self.path_queue.get() - path, distance, used_vehicle_num = info.get_path_info() + path, distance, used_vehicle_num = info.get_path_info() if path is None: + print('[draw figure]: exit') break - self.figure_ax.clear() - self._draw_point() - self.figure.canvas.draw() + # 需要先记录要移除的line，不能直接在第一个循环中进行remove， + # 不然self.figure_ax.lines会在循环的过程中改变，导致部分line无法成功remove + remove_obj = [] + for line in self.figure_ax.lines: + if line._label == 'line': + remove_obj.append(line) + + for line in remove_obj: + self.figure_ax.lines.remove(line) + remove_obj.clear() plt.pause(1) + # 重新绘制line + self.figure_ax.set_title('current path travel distance: %f' % distance) self._draw_line(path) plt.pause(1) def _draw_line(self, path): - # 根据path中index进行路劲的绘制 + # 根据path中index进行路径的绘制 for i in range(1, len(path)): x_list = [self.nodes[path[i - 1]].x, self.nodes[path[i]].x] y_list = [self.nodes[path[i - 1]].y, self.nodes[path[i]].y] - self.figure_ax.plot(x_list, y_list, '%s-' % self._line_color_list[0]) + self.figure_ax.plot(x_list, y_list, color=self._line_color, linewidth=1.5, label='line') plt.pause(0.05) |