From 2eacd762b1605f4b6d449b8725d980c96de4d826 Mon Sep 17 00:00:00 2001 From: JonZhao <1044264932@qq.com> Date: Thu, 30 May 2019 12:57:27 +0800 Subject: add local_search_procedure_for_global_path --- ant.py | 18 +++++++---- multiple_ant_colony_system.py | 74 ++++++++++++++++++++++++++++++++++++++++++- vprtw_aco_figure.py | 2 +- vrptw_base.py | 11 +++++-- 4 files changed, 94 insertions(+), 11 deletions(-) diff --git a/ant.py b/ant.py index 3ee888e..1c950ea 100644 --- a/ant.py +++ b/ant.py @@ -230,7 +230,6 @@ class Ant: # 将self.travel_path分成多段，每段以depot开始，以depot结束，称为route for i in range(1, len(depot_ind)): for j in range(i+1, len(depot_ind)): - if stop_event.is_set(): # print('[local_search_procedure]: receive stop event') return @@ -264,17 +263,24 @@ class Ant: else: break # 如果新生成的path是可行的 - if check_ant.index_to_visit_empty(): + if check_ant.index_to_visit_empty() and check_ant.total_travel_distance < self.total_travel_distance: # print('success to search') new_path_travel_distance.append(check_ant.total_travel_distance) new_path.append(path) + else: + path.clear() # 找出新生成的path中，路程最小的 if len(new_path_travel_distance) > 0: new_path_travel_distance = np.array(new_path_travel_distance) min_distance_ind = np.argmin(new_path_travel_distance) - min_distance = new_path_travel_distance[min_distance_ind] - if min_distance < self.total_travel_distance: - self.travel_path = new_path[int(min_distance_ind)] - self.index_to_visit.clear() + self.travel_path = copy.deepcopy(new_path[int(min_distance_ind)]) + self.index_to_visit.clear() + + for i in range(len(new_path)): + new_path[i].clear() + new_path.clear() + del new_path_travel_distance + + # print('[new_active_ant]: local search finished') \ No newline at end of file diff --git a/multiple_ant_colony_system.py b/multiple_ant_colony_system.py index 888c84b..5bd5e74 100644 --- a/multiple_ant_colony_system.py +++ b/multiple_ant_colony_system.py @@ -52,6 +52,66 @@ class MultipleAntColonySystem: if random.random() <= norm_transition_prob[ind]: return index_to_visit[ind] + @staticmethod + def local_search_procedure_for_global_path(graph: VrptwGraph, global_best_path: list, global_best_distance: float, stop_event: Event): + """ + 对global_path使用cross进行局部搜索 + :return: + """ + result_path = None + result_distance = None + + new_path_travel_distance = [] + new_path = [] + for i in range(1, len(global_best_path)): + + if graph.nodes[global_best_path[i]].is_depot: + continue + + for j in range(i+1, len(global_best_path)): + + if graph.nodes[global_best_path[j]].is_depot: + continue + + if stop_event.is_set(): + # print('[local_search_procedure_for_global_path]: receive stop event') + return result_path, result_distance + + path = copy.deepcopy(global_best_path) + path[i], path[j] = path[j], path[i] + + # 判断新生成的path是否是可行的 + check_ant = Ant(graph, path[0]) + for ind in path[1:]: + if check_ant.check_condition(ind): + check_ant.move_to_next_index(ind) + else: + break + + # 如果新生成的path是可行的 + if check_ant.index_to_visit_empty() and check_ant.total_travel_distance < global_best_distance: + # print('success to search') + new_path_travel_distance.append(check_ant.total_travel_distance) + new_path.append(path) + else: + path.clear() + + # 找出新生成的path中，路程最小的 + if len(new_path_travel_distance) > 0: + new_path_travel_distance = np.array(new_path_travel_distance) + min_distance_ind = np.argmin(new_path_travel_distance) + + result_path = copy.deepcopy(new_path[int(min_distance_ind)]) + result_distance = new_path_travel_distance[int(min_distance_ind)] + + for i in range(len(new_path)): + new_path[i].clear() + new_path.clear() + del new_path_travel_distance + + # print('[]: local search for global path finished') + return result_path, result_distance + @staticmethod def new_active_ant(ant: Ant, vehicle_num: int, local_search: bool, IN: np.numarray, q0: float, beta: int, stop_event: Event): """ @@ -158,6 +218,7 @@ class MultipleAntColonySystem: ants_thread = [] ants = [] while True: + print('[acs_time]: new iteration') if stop_event.is_set(): print('[acs_time]: receive stop event') @@ -192,9 +253,17 @@ class MultipleAntColonySystem: # 如果比全局的路径要好，则要将该路径发送到macs中 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') + print('[acs_time]: ant found a improved feasible path, send path info to macs') path_found_queue.put(PathMessage(ant.travel_path, ant.total_travel_distance)) + # 为global path进行局部搜索 + result_path, result_distance = MultipleAntColonySystem.local_search_procedure_for_global_path(new_graph, global_best_path, global_best_distance, stop_event) + + if result_distance is not None: + print('[acs_time]: local_search_procedure_for_global_path found a improved feasible path,' + ' send path info to macs') + path_found_queue.put(PathMessage(result_path, result_distance)) + # 在这里执行信息素的全局更新 new_graph.global_update_pheromone(global_best_path, global_best_distance) @@ -231,6 +300,7 @@ class MultipleAntColonySystem: ants = [] IN = np.zeros(new_graph.node_num) while True: + print('[acs_vehicle]: new iteration') if stop_event.is_set(): print('[acs_vehicle]: receive stop event') @@ -318,6 +388,7 @@ class MultipleAntColonySystem: self.best_path, self.best_path_distance, self.best_vehicle_num = self.graph.nearest_neighbor_heuristic() while True: + print('[multiple_ant_colony_system]: new iteration') start_time = time.time() # 当前best path的信息，放在queue中以通知acs_time和acs_vehicle当前的best_path是什么 @@ -403,4 +474,5 @@ class MultipleAntColonySystem: # 停止acs_time 和 acs_vehicle 两个线程 print('[macs]: send stop info to acs_time and acs_vehicle') + # 通知acs_vehicle和acs_time两个线程，当前找到的best_path和best_path_distance stop_event.set() diff --git a/vprtw_aco_figure.py b/vprtw_aco_figure.py index 6fa8765..9860f8e 100644 --- a/vprtw_aco_figure.py +++ b/vprtw_aco_figure.py @@ -72,4 +72,4 @@ class VrptwAcoFigure: 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, color=self._line_color, linewidth=1.5, label='line') - plt.pause(0.05) + plt.pause(0.02) diff --git a/vrptw_base.py b/vrptw_base.py index 988713e..52cdafa 100644 --- a/vrptw_base.py +++ b/vrptw_base.py @@ -166,9 +166,14 @@ class VrptwGraph: class PathMessage: def __init__(self, path, distance): - self.path = copy.deepcopy(path) - self.distance = copy.deepcopy(distance) - self.used_vehicle_num = self.path.count(0) - 1 + if path is not None: + self.path = copy.deepcopy(path) + self.distance = copy.deepcopy(distance) + self.used_vehicle_num = self.path.count(0) - 1 + else: + self.path = None + self.distance = None + self.used_vehicle_num = None def get_path_info(self): return self.path, self.distance, self.used_vehicle_num -- cgit v1.2.3