use main thread to draw figure

3 files changed, 104 insertions, 48 deletions

diff --git a/main.py b/main.py
index 34c19aa..afa3d95 100644
--- a/main.py
+++ b/main.py
@@ -10,7 +10,7 @@ import copy
 
 
 class VrptwAco:
-    def __init__(self, graph: VrptwGraph, ants_num=10, max_iter=200, alpha=1, beta=1):
+    def __init__(self, graph: VrptwGraph, ants_num=10, max_iter=200, alpha=1, beta=2):
         super()
         # graph 结点的位置、服务时间信息
         self.graph = graph
@@ -33,13 +33,25 @@ class VrptwAco:
         self.best_path = None
         self.best_vehicle_num = None
 
-        self.whether_or_not_to_show_figure = False
+        self.whether_or_not_to_show_figure = True
 
+    def run_basic_aco(self):
+        # 开启一个线程来跑_basic_aco，使用主线程来绘图
+        path_queue_for_figure = Queue()
+        basic_aco_thread = Thread(target=self._basic_aco, args=(path_queue_for_figure,))
+        basic_aco_thread.start()
+
+        # 是否要展示figure
+        if self.whether_or_not_to_show_figure:
+            figure = VrptwAcoFigure(self.graph, path_queue_for_figure)
+            figure.run()
+        basic_aco_thread.join()
+
+        # 传入None作为结束标志
         if self.whether_or_not_to_show_figure:
-            # figure
-            self.figure = VrptwAcoFigure(self.graph)
+            path_queue_for_figure.put(PathMessage(None, None))
 
-    def basic_aco(self):
+    def _basic_aco(self, path_queue_for_figure: Queue):
         """
         最基本的蚁群算法
         :return:
@@ -77,13 +89,13 @@ class VrptwAco:
                 self.best_path = ants[int(best_index)].travel_path
                 self.best_path_distance = paths_distance[best_index]
                 if self.whether_or_not_to_show_figure:
-                    self.figure.init_figure(self.best_path)
+                    path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance))
 
             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]
                 if self.whether_or_not_to_show_figure:
-                    self.figure.update_figure(self.best_path)
+                    path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance))
 
             print('[iteration %d]: best distance %f' % (iter, self.best_path_distance))
             # 更新信息素表
@@ -134,21 +146,26 @@ class VrptwAco:
     @staticmethod
     def new_active_ant(ant: Ant, vehicle_num: int, local_search: bool, IN: np.numarray, q0: float, stop_event: Event):
         # print('[new_active_ant]: start, start_index %d' % ant.travel_path[0])
-        # 计算从当前位置可以达到的下一个位置
-        unused_depot_count = vehicle_num - 1
 
+        # 在new_active_ant中，最多可以使用vehicle_num个车，即最多可以包含vehicle_num+1个depot结点，由于出发结点用掉了一个，所以只剩下vehicle个depot
+        unused_depot_count = vehicle_num
+
+        # 如果还有未访问的结点，并且还可以回到depot中
         while not ant.index_to_visit_empty() and unused_depot_count > 0:
             if stop_event.is_set():
                 # print('[new_active_ant]: receive stop event')
                 return
 
+            # 计算所有满足载重等限制的下一个结点
             next_index_meet_constrains = ant.cal_next_index_meet_constrains()
 
+            # 如果没有满足限制的下一个结点，则回到depot中
             if len(next_index_meet_constrains) == 0:
                 ant.move_to_next_index(0)
                 unused_depot_count -= 1
                 continue
 
+            # 开始计算满足限制的下一个结点，选择各个结点的概率
             index_num = len(next_index_meet_constrains)
             ready_time = np.zeros(index_num)
             due_time = np.zeros(index_num)
@@ -165,7 +182,7 @@ class VrptwAco:
             distance = np.array([max(1.0, j) for j in distance-IN[next_index_meet_constrains]])
             closeness = 1/distance
 
-            # 按照概率选择下一个点next_index
+            # 按照概率直接选择closeness最大的结点
             if np.random.rand() < q0:
                 max_prob_index = np.argmax(closeness)
                 next_index = next_index_meet_constrains[max_prob_index]
@@ -190,6 +207,8 @@ class VrptwAco:
 
     @staticmethod
     def acs_time(new_graph: VrptwGraph, vehicle_num, ants_num, q0, global_path_queue: Queue, path_found_queue: Queue, stop_event: Event):
+        # 最多可以使用vehicle_num辆车，即在path中最多包含vehicle_num+1个depot中，找到路程最短的路径，
+        # vehicle_num设置为与当前的best_path一致
         print('[acs_time]: start, vehicle_num %d' % vehicle_num)
         # 初始化信息素矩阵
         global_best_path = None
@@ -222,8 +241,10 @@ class VrptwAco:
                     return
 
                 # 如果比全局的路径要好，则要将该路径发送到macs中
-                while not global_path_queue.empty():
+                if not global_path_queue.empty():
                     info = global_path_queue.get()
+                    while not global_path_queue.empty():
+                        info = global_path_queue.get()
                     print('[acs_time]: receive global path info')
                     global_best_path, global_best_distance = info.get_path_info()
 
@@ -236,6 +257,8 @@ class VrptwAco:
 
     @staticmethod
     def acs_vehicle(new_graph: VrptwGraph, vehicle_num: int, ants_num: int, q0: float, global_path_queue: Queue, path_found_queue: Queue, stop_event: Event):
+        # 最多可以使用vehicle_num辆车，即在path中最多包含vehicle_num+1个depot中，找到路程最短的路径，
+        # vehicle_num设置为比当前的best_path少一个
         print('[acs_vehicle]: start, vehicle_num %d' % vehicle_num)
         global_best_path = None
         global_best_distance = None
@@ -294,14 +317,32 @@ class VrptwAco:
             # 更新new_graph中的信息素，global
             new_graph.global_update_pheromone(current_path, current_path_distance)
 
-            while not global_path_queue.empty():
+            if not global_path_queue.empty():
                 info = global_path_queue.get()
+                while not global_path_queue.empty():
+                    info = global_path_queue.get()
                 print('[acs_vehicle]: receive global path info')
                 global_best_path, global_best_distance = info.get_path_info()
 
             new_graph.global_update_pheromone(global_best_path, global_best_distance)
 
-    def multiple_ant_colony_system(self):
+    def run_multiple_ant_colony_system(self):
+        # _multiple_ant_colony_system，使用主线程来绘图
+        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()
+
+        # 是否要展示figure
+        if self.whether_or_not_to_show_figure:
+            figure = VrptwAcoFigure(self.graph, path_queue_for_figure)
+            figure.run()
+        multiple_ant_colony_system_thread.join()
+
+        # 传入None作为结束标志
+        if self.whether_or_not_to_show_figure:
+            path_queue_for_figure.put(PathMessage(None, None))
+
+    def _multiple_ant_colony_system(self, path_queue_for_figure: Queue):
         # 在这里需要两个队列，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()
@@ -317,6 +358,7 @@ class VrptwAco:
             # 当前best path的信息
             global_path_to_acs_vehicle.put(PathMessage(self.best_path, self.best_path_distance))
             global_path_to_acs_time.put(PathMessage(self.best_path, self.best_path_distance))
+
             # acs_vehicle
             stop_event = Event()
             graph_for_acs_vehicle = self.graph.copy(self.graph.init_pheromone_val)
@@ -349,22 +391,33 @@ class VrptwAco:
                 # 如果找到的路径（feasible）的距离更短，则更新当前的最佳path的信息
                 if found_path_distance < self.best_path_distance:
                     print('-' * 50)
-                    print('[macs]: distance of found path better than best path\'s')
+                    print('[macs]: distance of found path (%f) better than best path\'s (%f)' % (found_path_distance, self.best_path_distance))
                     print('-' * 50)
                     self.best_path = found_path
                     self.best_vehicle_num = found_path.count(0) - 1
                     self.best_path_distance = found_path_distance
 
+                    # 如果需要绘制图形，则要找到的best path发送给绘图程序
+                    if self.whether_or_not_to_show_figure:
+                        path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance))
+
+                    # 通知acs_vehicle和acs_time两个线程，当前找到的best_path和best_path_distance
+                    global_path_to_acs_vehicle.put(PathMessage(self.best_path, self.best_path_distance))
+                    global_path_to_acs_time.put(PathMessage(self.best_path, self.best_path_distance))
+
                 # 如果，这两个线程找到的路径用的车辆更少了，就停止这两个线程，开始下一轮迭代
                 # 向acs_time和acs_vehicle中发送停止信息
                 if found_path.count(0)-1 < best_vehicle_num:
                     print('-' * 50)
-                    print('[macs]: vehicle num of found path better than best path\'s')
+                    print('[macs]: vehicle num of found path (%d) better than best path\'s (%d)' % (found_path.count(0)-1, best_vehicle_num))
                     print('-' * 50)
                     self.best_path = found_path
                     self.best_vehicle_num = found_path.count(0)-1
                     self.best_path_distance = found_path_distance
 
+                    if self.whether_or_not_to_show_figure:
+                        path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance))
+
                     # 停止acs_time 和 acs_vehicle 两个线程
                     print('[macs]: send stop info to acs_time and acs_vehicle')
                     stop_event.set()
@@ -375,4 +428,4 @@ if __name__ == '__main__':
     graph = VrptwGraph(file_path)
 
     vrptw = VrptwAco(graph)
-    vrptw.multiple_ant_colony_system()
+    vrptw.run_multiple_ant_colony_system()
diff --git a/vprtw_aco_figure.py b/vprtw_aco_figure.py
index 3d1a269..99e71f4 100644
--- a/vprtw_aco_figure.py
+++ b/vprtw_aco_figure.py
@@ -1,47 +1,50 @@
 import matplotlib.pyplot as plt
 from vrptw_base import VrptwGraph
-import time
+from queue import Queue
 
 
 class VrptwAcoFigure:
-    def __init__(self, graph: VrptwGraph):
+    def __init__(self, graph: VrptwGraph, path_queue: Queue):
         self.graph = graph
         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']
 
-    def init_figure(self, path):
-        self.figure_ax.plot(list(self.graph.nodes[index].x for index in path),
-                            list(self.graph.nodes[index].y for index in path), '%s.' % self._dot_color)
-        self._draw_line(path)
+    def _draw_point(self):
+        # 先画出图中的点
+        self.figure_ax.plot(list(node.x for node in self.graph.nodes),
+                            list(node.y for node in self.graph.nodes), '%s.' % self._dot_color)
         self.figure.show()
-        time.sleep(0.2)
+        plt.pause(0.5)
+
+    def run(self):
+        self._draw_point()
+
+        # 从队列中读取新的path，进行绘制
+        while True:
+            if not self.path_queue.empty():
+                info = self.path_queue.get()
+                while not self.path_queue.empty():
+                    info = self.path_queue.get()
+                path, distance = info.get_path_info()
 
-    def update_figure(self, path):
-        for line in self.figure_ax.lines:
-            if line._color != self._dot_color:
-                self.figure_ax.lines.remove(line)
+                if path is None:
+                    break
 
-        self._draw_line(path)
+                self.figure_ax.clear()
+                self._draw_point()
+                self.figure.canvas.draw()
+                plt.pause(1)
 
-        self.figure.canvas.draw()
-        time.sleep(0.2)
+                self._draw_line(path)
+            plt.pause(1)
 
     def _draw_line(self, path):
-        color_ind = 0
-        x_list = []
-        y_list = []
-        i = 0
-        while i < len(path):
-            x_list.append(self.graph.nodes[path[i]].x)
-            y_list.append(self.graph.nodes[path[i]].y)
-
-            if path[i] == 0 and len(x_list) > 1:
-                self.figure_ax.plot(x_list, y_list, '%s-' % self._line_color_list[color_ind])
-                color_ind = (color_ind + 1) % len(self._line_color_list)
-                x_list.clear()
-                y_list.clear()
-                i -= 1
-            i += 1
+        # 根据path中index进行路劲的绘制
+        for i in range(1, len(path)):
+            x_list = [self.graph.nodes[path[i - 1]].x, self.graph.nodes[path[i]].x]
+            y_list = [self.graph.nodes[path[i - 1]].y, self.graph.nodes[path[i]].y]
+            self.figure_ax.plot(x_list, y_list, '%s-' % self._line_color_list[0])
+            plt.pause(0.05)
diff --git a/vrptw_base.py b/vrptw_base.py
index ba86128..645b114 100644
--- a/vrptw_base.py
+++ b/vrptw_base.py
@@ -164,8 +164,8 @@ class VrptwGraph:
 
 class PathMessage:
     def __init__(self, path, distance):
-        self.path = path
-        self.distance = distance
+        self.path = copy.deepcopy(path)
+        self.distance = copy.deepcopy(distance)
 
     def get_path_info(self):
         return self.path, self.distance