From 64ea2265e21e678a2c36fa32da6390456ae3a235 Mon Sep 17 00:00:00 2001 From: JonZhao <1044264932@qq.com> Date: Sun, 2 Jun 2019 16:45:32 +0800 Subject: =?UTF-8?q?=E4=BC=98=E5=8C=96local=5Fsearch=E7=9A=84=E8=AE=A1?= =?UTF-8?q?=E7=AE=97?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- ant.py | 32 ++++++++++++++--------------- multiple_ant_colony_system.py | 47 +++++++++++++++++++++++-------------------- 2 files changed, 40 insertions(+), 39 deletions(-) diff --git a/ant.py b/ant.py index fe224f4..829c068 100644 --- a/ant.py +++ b/ant.py @@ -36,9 +36,6 @@ class Ant: self.vehicle_load = 0 self.vehicle_travel_time = 0 - # remove duplicated_depot - if next_index in self.index_to_visit: - self.index_to_visit.remove(next_index) else: # 更新车辆负载、行驶距离、时间 self.vehicle_load += self.graph.nodes[next_index].demand @@ -240,9 +237,11 @@ class Ant: 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 end_a in range(start_a, min(depot_ind[i], start_a+6)): 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)): + for end_b in range(start_b, min(depot_ind[j], start_b+6)): + if start_a == end_a and start_b == end_b: + continue position.append([start_a, end_a, start_b, end_b]) for posi in position: @@ -254,18 +253,11 @@ class Ant: path.extend(self.travel_path[start_a:end_a]) path.extend(self.travel_path[end_b+1:]) - 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_a = depot_ind[i-1] - depot_before_start_b = start_b - while not self.graph.nodes[path[depot_before_start_b]].is_depot: - depot_before_start_b -= 1 + depot_before_start_b = depot_ind[j-1] + (end_b-start_b) - (end_a-start_a) + 1 + if not self.graph.nodes[path[depot_before_start_b]].is_depot: + raise RuntimeError('error') # 判断发生改变的route a是否是feasible的 success_route_a = False @@ -278,6 +270,7 @@ class Ant: break else: break + check_ant.clear() del check_ant @@ -305,7 +298,12 @@ class Ant: else: path.clear() - # 找出新生成的path中，路程最小的 + # 判断new_path中是否存在连个连续的depot + for i in range(1, len(new_path)): + if self.graph.nodes[new_path[i]].is_depot and self.graph.nodes[new_path[i-1]].is_depot: + new_path.pop(i) + break + 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 ea500b5..3e9b0f3 100644 --- a/multiple_ant_colony_system.py +++ b/multiple_ant_colony_system.py @@ -88,25 +88,23 @@ class MultipleAntColonySystem: continue # 开始计算满足限制的下一个结点，选择各个结点的概率 - index_num = len(next_index_meet_constrains) - ready_time = np.zeros(index_num) - due_time = np.zeros(index_num) + length = len(next_index_meet_constrains) + ready_time = np.zeros(length) + due_time = np.zeros(length) - for i in range(index_num): + for i in range(length): ready_time[i] = ant.graph.nodes[next_index_meet_constrains[i]].ready_time due_time[i] = ant.graph.nodes[next_index_meet_constrains[i]].due_time - delivery_time = np.array([max(i, j) for i, j in zip(ant.vehicle_travel_time + ant.graph.node_dist_mat[ant.current_index][next_index_meet_constrains], ready_time)]) - + delivery_time = np.maximum(ant.vehicle_travel_time + ant.graph.node_dist_mat[ant.current_index][next_index_meet_constrains], ready_time) delta_time = delivery_time - ant.vehicle_travel_time distance = delta_time * (due_time - ant.vehicle_travel_time) - distance = np.array([max(1.0, j) for j in distance-IN[next_index_meet_constrains]]) + distance = np.maximum(1.0, distance-IN[next_index_meet_constrains]) closeness = 1/distance transition_prob = ant.graph.pheromone_mat[ant.current_index][next_index_meet_constrains] * \ np.power(closeness, beta) - transition_prob = transition_prob / np.sum(transition_prob) # 按照概率直接选择closeness最大的结点 @@ -168,7 +166,6 @@ class MultipleAntColonySystem: ant = Ant(new_graph, 0) thread = ants_pool.submit(MultipleAntColonySystem.new_active_ant, ant, vehicle_num, True, np.zeros(new_graph.node_num), q0, beta, stop_event) - ants_thread.append(thread) ants.append(ant) @@ -176,14 +173,6 @@ 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: @@ -191,6 +180,14 @@ 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') @@ -262,13 +259,12 @@ class MultipleAntColonySystem: print('[acs_vehicle]: receive stop event') return - index_to_visit = copy.deepcopy(ant.index_to_visit) - IN[index_to_visit] = IN[index_to_visit]+1 + IN[ant.index_to_visit] = IN[ant.index_to_visit]+1 # 蚂蚁找出来的路径与current_path进行比较，是否能使用vehicle_num辆车访问到更多的结点 - if len(index_to_visit) < len(current_index_to_visit): + if len(ant.index_to_visit) < len(current_index_to_visit): current_path = copy.deepcopy(ant.travel_path) - current_index_to_visit = index_to_visit + current_index_to_visit = copy.deepcopy(ant.index_to_visit) current_path_distance = ant.total_travel_distance # 并且将IN设置为0 IN = np.zeros(new_graph.node_num) @@ -380,6 +376,14 @@ class MultipleAntColonySystem: path_info = path_found_queue.get() print('[macs]: receive found path info') found_path, found_path_distance, found_path_used_vehicle_num = path_info.get_path_info() + while not path_found_queue.empty(): + path, distance, vehicle_num = path_found_queue.get().get_path_info() + + if distance < found_path_distance: + found_path, found_path_distance, found_path_used_vehicle_num = path, distance, vehicle_num + + if vehicle_num < found_path_used_vehicle_num: + found_path, found_path_distance, found_path_used_vehicle_num = path, distance, vehicle_num # 如果找到的路径（which is feasible）的距离更短，则更新当前的最佳path的信息 if found_path_distance < self.best_path_distance: @@ -409,7 +413,6 @@ class MultipleAntColonySystem: # 搜索到更好的结果，更新start_time start_time_found_improved_solution = time.time() - print('*' * 50) 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)) -- cgit v1.2.3