From a8a336151cedebec9629d10283be6b6ac29fc9fd Mon Sep 17 00:00:00 2001 From: JonZhao <1044264932@qq.com> Date: Sun, 2 Jun 2019 13:55:05 +0800 Subject: 1. update: update local_search_procedure 2. remove: remove local_search_procedure_for_global_path --- ant.py | 106 ++++++++++++++++++++++++++---------------- multiple_ant_colony_system.py | 99 +++++++++------------------------------ 2 files changed, 87 insertions(+), 118 deletions(-) diff --git a/ant.py b/ant.py index ab0cc35..fe224f4 100644 --- a/ant.py +++ b/ant.py @@ -1,6 +1,5 @@ import numpy as np import copy -import random from vrptw_base import VrptwGraph from threading import Event @@ -20,6 +19,10 @@ class Ant: self.total_travel_distance = 0 + def clear(self): + self.travel_path.clear() + self.index_to_visit.clear() + def move_to_next_index(self, next_index): # 更新蚂蚁路径 self.travel_path.append(next_index) @@ -225,27 +228,25 @@ class Ant: if self.graph.nodes[self.travel_path[ind]].is_depot: depot_ind.append(ind) - new_path_travel_distance = [] - new_path = [] + new_path_travel_distance = self.total_travel_distance + new_path = self.travel_path + # 将self.travel_path分成多段，每段以depot开始，以depot结束，称为route for i in range(1, len(depot_ind)): for j in range(i+1, len(depot_ind)): - for k in range(10): - if stop_event.is_set(): - # print('[local_search_procedure]: receive stop event') - return - - # 随机在两段route，各随机选择一段customer id，交换这两段customer id - start_a = random.randint(depot_ind[i-1]+1, depot_ind[i]-1) - end_a = random.randint(depot_ind[i-1]+1, depot_ind[i]-1) - if end_a < start_a: - start_a, end_a = end_a, start_a - - start_b = random.randint(depot_ind[j-1]+1, depot_ind[j]-1) - end_b = random.randint(depot_ind[j - 1] + 1, depot_ind[j] - 1) - if end_b < start_b: - start_b, end_b = end_b, start_b + if stop_event.is_set(): + return + + position = [] + for start_a in range(depot_ind[i-1]+1, depot_ind[i]): + for end_a in range(start_a, min(depot_ind[i], start_a+7)): + for start_b in range(depot_ind[j-1]+1, depot_ind[j]): + for end_b in range(start_b, min(depot_ind[j], start_b+7)): + position.append([start_a, end_a, start_b, end_b]) + + for posi in position: + start_a, end_a, start_b, end_b = posi path = [] path.extend(self.travel_path[:start_a]) path.extend(self.travel_path[start_b:end_b+1]) @@ -253,35 +254,58 @@ class Ant: path.extend(self.travel_path[start_a:end_a]) path.extend(self.travel_path[end_b+1:]) - if len(path) != len(self.travel_path): - raise RuntimeError('error') + for k in range(1, len(path)): + if path[i-1] == 0 and path[i] == 0: + path.remove(i) + break + + depot_before_start_a = start_a + while not self.graph.nodes[path[depot_before_start_a]].is_depot: + depot_before_start_a -= 1 + + depot_before_start_b = start_b + while not self.graph.nodes[path[depot_before_start_b]].is_depot: + depot_before_start_b -= 1 - # 判断新生成的path是否是可行的 - check_ant = Ant(self.graph, path[0]) - for ind in path[1:]: + # 判断发生改变的route a是否是feasible的 + success_route_a = False + check_ant = Ant(self.graph, path[depot_before_start_a]) + for ind in path[depot_before_start_a+1:]: if check_ant.check_condition(ind): check_ant.move_to_next_index(ind) + if self.graph.nodes[ind].is_depot: + success_route_a = True + break else: break - # 如果新生成的path是可行的 - 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) + check_ant.clear() + del check_ant + + # 判断发生改变的route b是否是feasible的 + success_route_b = False + check_ant = Ant(self.graph, path[depot_before_start_b]) + for ind in path[depot_before_start_b + 1:]: + if check_ant.check_condition(ind): + check_ant.move_to_next_index(ind) + if self.graph.nodes[ind].is_depot: + success_route_b = True + break + else: + break + check_ant.clear() + del check_ant + + if success_route_a and success_route_b: + total_travel_distance = self.cal_total_travel_distance(path) + if total_travel_distance < new_path_travel_distance: + # print('success to search') + new_path_travel_distance = total_travel_distance + new_path = path + print('[local_search_procedure]: found a path in local search, its distance is %f' % new_path_travel_distance) 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) - - 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 + self.travel_path = new_path + self.total_travel_distance = new_path_travel_distance + print('[local_search_procedure]: local search finished') \ No newline at end of file diff --git a/multiple_ant_colony_system.py b/multiple_ant_colony_system.py index 21e2fae..ea500b5 100644 --- a/multiple_ant_colony_system.py +++ b/multiple_ant_colony_system.py @@ -52,66 +52,6 @@ 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): """ @@ -236,6 +176,14 @@ class MultipleAntColonySystem: for thread in ants_thread: thread.result() + # 获取当前的best path + 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, global_used_vehicle_num = info.get_path_info() + # 判断蚂蚁找出来的路径是否是feasible的，并且比全局的路径要好 for ant in ants: @@ -243,30 +191,20 @@ class MultipleAntColonySystem: print('[acs_time]: receive stop event') return - # 获取当前的best path - 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, global_used_vehicle_num = info.get_path_info() - # 如果比全局的路径要好，则要将该路径发送到macs中 if ant.index_to_visit_empty() and ant.total_travel_distance < global_best_distance: 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) + ants_thread.clear() + for ant in ants: + ant.clear() + del ant + ants.clear() + @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): @@ -308,7 +246,7 @@ class MultipleAntColonySystem: for k in range(ants_num): ant = Ant(new_graph, 0) - thread = ants_pool.submit(MultipleAntColonySystem.new_active_ant, ant, vehicle_num, True, IN, q0, + thread = ants_pool.submit(MultipleAntColonySystem.new_active_ant, ant, vehicle_num, False, IN, q0, beta, stop_event) ants_thread.append(thread) @@ -352,6 +290,12 @@ class MultipleAntColonySystem: new_graph.global_update_pheromone(global_best_path, global_best_distance) + ants_thread.clear() + for ant in ants: + ant.clear() + del ant + ants.clear() + def run_multiple_ant_colony_system(self): """ 开启另外的线程来跑multiple_ant_colony_system， 使用主线程来绘图 @@ -388,6 +332,7 @@ class MultipleAntColonySystem: # 使用近邻点算法初始化 self.best_path, self.best_path_distance, self.best_vehicle_num = self.graph.nearest_neighbor_heuristic() + path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance)) while True: print('[multiple_ant_colony_system]: new iteration') -- cgit v1.2.3