From 1b2e26d831e075770baa8c2c27ef965b1c7743b2 Mon Sep 17 00:00:00 2001 From: JonZhao <1044264932@qq.com> Date: Mon, 27 May 2019 22:45:10 +0800 Subject: =?UTF-8?q?=E7=A7=BB=E9=99=A4=E5=A4=8D=E5=88=B6=E5=A4=9A=E4=B8=AAd?= =?UTF-8?q?epot=E7=9A=84graph=E5=88=9B=E5=BB=BA=E6=96=B9=E6=B3=95=EF=BC=8C?= =?UTF-8?q?=E4=BD=BF=E7=94=A8=E6=9B=B4=E5=8A=A0=E5=8E=9F=E5=A7=8B=E7=9A=84?= =?UTF-8?q?=EF=BC=8C=E5=A6=82=E6=9E=9C=E6=B2=A1=E6=9C=89=E5=8F=AF=E4=BB=A5?= =?UTF-8?q?=E8=BE=BE=E5=88=B0=E7=9A=84=E4=B8=8B=E4=B8=80=E4=B8=AA=E5=AE=A2?= =?UTF-8?q?=E6=88=B7=E7=BB=93=E7=82=B9=EF=BC=8C=E5=88=99=E5=9B=9E=E5=88=B0?= =?UTF-8?q?depot=EF=BC=8C=E5=8F=96=E5=BE=97=E4=BA=86=E4=B8=8D=E9=94=99?= =?UTF-8?q?=E7=9A=84=E6=95=88=E6=9E=9C=EF=BC=8C=E5=B8=A6=E6=8E=A5=E4=B8=8B?= =?UTF-8?q?=E6=9D=A5=E7=BB=A7=E7=BB=AD=E6=B5=8B=E8=AF=95?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- main.py | 47 ++++++++++++++++++++++++++--------------------- 1 file changed, 26 insertions(+), 21 deletions(-) (limited to 'main.py') diff --git a/main.py b/main.py index 7f641e1..34c19aa 100644 --- a/main.py +++ b/main.py @@ -6,6 +6,7 @@ from ant import Ant from threading import Thread, Event from queue import Queue from concurrent.futures import ThreadPoolExecutor +import copy class VrptwAco: @@ -131,17 +132,23 @@ class VrptwAco: return index_to_visit[ind] @staticmethod - def new_active_ant(ant: Ant, local_search: bool, IN: np.numarray, q0: float, stop_event: Event): + 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]) # 计算从当前位置可以达到的下一个位置 - next_index_meet_constrains = ant.cal_next_index_meet_constrains() - - while len(next_index_meet_constrains) > 0: + unused_depot_count = vehicle_num - 1 + while not ant.index_to_visit_empty() and unused_depot_count > 0: if stop_event.is_set(): - print('[new_active_ant]: receive stop event') + # print('[new_active_ant]: receive stop event') return + next_index_meet_constrains = ant.cal_next_index_meet_constrains() + + 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) @@ -168,10 +175,7 @@ class VrptwAco: # 更新信息素矩阵 ant.graph.local_update_pheromone(ant.current_index, next_index) - ant.move_to_next_index(next_index) - # 重新计算可选的下一个点 - next_index_meet_constrains = ant.cal_next_index_meet_constrains() # 如果走完所有的点了，需要回到depot if ant.index_to_visit_empty(): @@ -200,8 +204,8 @@ class VrptwAco: return for k in range(ants_num): - ant = Ant(new_graph, random.randint(0, vehicle_num - 1)) - thread = ants_pool.submit(VrptwAco.new_active_ant, ant, True, np.zeros(new_graph.node_num), q0, stop_event) + ant = Ant(new_graph, 0) + thread = ants_pool.submit(VrptwAco.new_active_ant, ant, vehicle_num, True, np.zeros(new_graph.node_num), q0, stop_event) ants_thread.append(thread) ants.append(ant) @@ -225,7 +229,7 @@ class VrptwAco: if ant.index_to_visit_empty() and ant.total_travel_distance < global_best_distance: print('[acs_time]: found a improved feasible path, send path info to macs') - path_found_queue.put(PathMessage(ant.get_path_without_duplicated_depot(), ant.total_travel_distance)) + path_found_queue.put(PathMessage(ant.travel_path, ant.total_travel_distance)) # 在这里执行信息素的全局更新 new_graph.global_update_pheromone(global_best_path, global_best_distance) @@ -255,8 +259,8 @@ class VrptwAco: return for k in range(ants_num): - ant = Ant(new_graph, random.randint(0, vehicle_num-1)) - thread = ants_pool.submit(VrptwAco.new_active_ant, ant, True, IN, q0, stop_event) + ant = Ant(new_graph, 0) + thread = ants_pool.submit(VrptwAco.new_active_ant, ant, vehicle_num, True, IN, q0, stop_event) ants_thread.append(thread) ants.append(ant) @@ -271,13 +275,12 @@ class VrptwAco: print('[acs_vehicle]: receive stop event') return - index_to_visit = ant.index_to_visit + index_to_visit = copy.deepcopy(ant.index_to_visit) IN[index_to_visit] = IN[index_to_visit]+1 - path = ant.get_path_without_duplicated_depot() # 判断蚂蚁找出来的路径是否比current_path，能使用vehicle_num辆车访问到更多的结点 if len(index_to_visit) < len(current_index_to_visit): - current_path = path + current_path = copy.deepcopy(ant.travel_path) current_index_to_visit = index_to_visit current_path_distance = ant.total_travel_distance # 并且将IN设置为0 @@ -286,7 +289,7 @@ class VrptwAco: # 如果这一条路径是feasible的话，就要发到macs_vrptw中 if ant.index_to_visit_empty(): print('[acs_vehicle]: found a feasible path, send path info to macs') - path_found_queue.put(PathMessage(ant.get_path_without_duplicated_depot(), ant.total_travel_distance)) + path_found_queue.put(PathMessage(ant.travel_path, ant.total_travel_distance)) # 更新new_graph中的信息素，global new_graph.global_update_pheromone(current_path, current_path_distance) @@ -316,15 +319,13 @@ class VrptwAco: 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.construct_graph_with_duplicated_depot(self.best_vehicle_num-1, - self.graph.init_pheromone_val) + graph_for_acs_vehicle = self.graph.copy(self.graph.init_pheromone_val) acs_vehicle_thread = Thread(target=VrptwAco.acs_vehicle, args=(graph_for_acs_vehicle, self.best_vehicle_num-1, self.ants_num, self.q0, global_path_to_acs_vehicle, path_found_queue, stop_event)) # acs_time - graph_for_acs_time = self.graph.construct_graph_with_duplicated_depot(self.best_vehicle_num, - self.graph.init_pheromone_val) + graph_for_acs_time = self.graph.copy(self.graph.init_pheromone_val) acs_time_thread = Thread(target=VrptwAco.acs_time, args=(graph_for_acs_time, self.best_vehicle_num, self.ants_num, self.q0, global_path_to_acs_time, path_found_queue, stop_event)) @@ -347,7 +348,9 @@ 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('-' * 50) self.best_path = found_path self.best_vehicle_num = found_path.count(0) - 1 self.best_path_distance = found_path_distance @@ -355,7 +358,9 @@ class VrptwAco: # 如果，这两个线程找到的路径用的车辆更少了，就停止这两个线程，开始下一轮迭代 # 向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('-' * 50) self.best_path = found_path self.best_vehicle_num = found_path.count(0)-1 self.best_path_distance = found_path_distance -- cgit v1.2.3