From 8ce2cb66ae5f5e5ba5afc10edbf8f1e85967f090 Mon Sep 17 00:00:00 2001 From: JonZhao <1044264932@qq.com> Date: Mon, 27 May 2019 18:50:52 +0800 Subject: add multiple_ant_colony_system --- ant.py | 45 +++++++++-- main.py | 250 ++++++++++++++++++++++++++++++++++++++++++++++++++++------ vrptw_base.py | 46 +++++++---- 3 files changed, 293 insertions(+), 48 deletions(-) diff --git a/ant.py b/ant.py index 3f2bdd2..2294377 100644 --- a/ant.py +++ b/ant.py @@ -8,7 +8,7 @@ class Ant: def __init__(self, graph: VrptwGraph, start_index=0): super() self.graph = graph - self.current_index = 0 + self.current_index = start_index self.vehicle_load = 0 self.vehicle_travel_time = 0 self.travel_path = [start_index] @@ -110,7 +110,7 @@ class Ant: current_ind = next_ind return distance - def try_insert_on_path(self, node_id): + def try_insert_on_path(self, node_id, what_to_do_list: list): """ 尝试性地将node_id插入当前的travel_path中 插入的位置不能违反载重，时间，行驶距离的限制 @@ -124,6 +124,12 @@ class Ant: path = copy.deepcopy(self.travel_path) for insert_index in range(len(path)): + + if len(what_to_do_list) > 0: + info = what_to_do_list[0] + if info.is_to_stop(): + return + if self.graph.nodes[path[insert_index]].is_depot: continue @@ -144,6 +150,12 @@ class Ant: # 如果可以到node_id，则要保证vehicle可以行驶回到depot for next_ind in path[insert_index:]: + + if len(what_to_do_list) > 0: + info = what_to_do_list[0] + if info.is_to_stop(): + return + if check_ant.check_condition(next_ind): check_ant.move_to_next_index(next_ind) if self.graph.nodes[next_ind].is_depot: @@ -162,7 +174,14 @@ class Ant: best_ind = feasible_insert_index[int(min_insert_ind)] return best_ind - def insertion_procedure(self): + def get_path_without_duplicated_depot(self): + path = copy.deepcopy(self.travel_path) + for i in range(len(path)): + if self.graph.nodes[i].is_depot: + path[i] = 0 + return path + + def insertion_procedure(self, what_to_do_list: list): """ 为每个未访问的结点尝试性地找到一个合适的位置，插入到当前的travel_path 插入的位置不能违反载重，时间，行驶距离的限制 @@ -181,14 +200,20 @@ class Ant: ind_to_visit = ind_to_visit[sorted_ind] for node_id in ind_to_visit: - best_insert_index = self.try_insert_on_path(node_id) + + if len(what_to_do_list) > 0: + info = what_to_do_list[0] + if info.is_to_stop(): + return + + best_insert_index = self.try_insert_on_path(node_id, what_to_do_list) if best_insert_index is not None: self.travel_path.insert(best_insert_index, node_id) self.index_to_visit.remove(node_id) self.total_travel_distance = self.cal_total_travel_distance(self.travel_path) - def local_search_procedure(self): + def local_search_procedure(self, what_to_do_list): """ 对当前的已经访问完graph中所有节点的travel_path使用cross进行局部搜索 :return: @@ -205,6 +230,11 @@ class Ant: for i in range(1, len(depot_ind)): for j in range(i+1, len(depot_ind)): + if len(what_to_do_list) > 0: + info = what_to_do_list[0] + if info.is_to_stop(): + 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) @@ -245,6 +275,5 @@ class Ant: min_distance = new_path_travel_distance[min_distance_ind] if min_distance < self.total_travel_distance: - return new_path[int(min_distance_ind)] - else: - return None \ No newline at end of file + self.travel_path = new_path[int(min_distance_ind)] + self.index_to_visit.clear() diff --git a/main.py b/main.py index 07cc98f..30d8a8d 100644 --- a/main.py +++ b/main.py @@ -1,8 +1,12 @@ import numpy as np import random from vprtw_aco_figure import VrptwAcoFigure -from vrptw_base import VrptwGraph +from vrptw_base import VrptwGraph, VrptwMessage from ant import Ant +from threading import Thread +from queue import Queue +from concurrent.futures import ThreadPoolExecutor +import copy class VrptwAco: @@ -27,6 +31,7 @@ class VrptwAco: # best path self.best_path_distance = None self.best_path = None + self.best_vehicle_num = self.graph.nnh_travel_path.count(0)-1 self.whether_or_not_to_show_figure = False @@ -34,9 +39,9 @@ class VrptwAco: # figure self.figure = VrptwAcoFigure(self.graph) - def run(self): + def basic_aco(self): """ - 运行蚁群优化算法 + 最基本的蚁群算法 :return: """ # 最大迭代次数 @@ -101,10 +106,11 @@ class VrptwAco: next_index = index_to_visit[max_prob_index] else: # 使用轮盘赌算法 - next_index = self.stochastic_accept(index_to_visit, transition_prob) + next_index = VrptwAco.stochastic_accept(index_to_visit, transition_prob) return next_index - def stochastic_accept(self, index_to_visit, transition_prob): + @staticmethod + def stochastic_accept(index_to_visit, transition_prob): """ 轮盘赌 :param index_to_visit: a list of N index (list or tuple) @@ -125,11 +131,19 @@ class VrptwAco: if random.random() <= norm_transition_prob[ind]: return index_to_visit[ind] - def new_active_ant(self, ant: Ant, local_search: bool, IN): - + @staticmethod + def new_active_ant(ant: Ant, local_search: bool, IN: np.numarray, q0: float, what_to_do_list: list): + 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: + + if len(what_to_do_list) > 0: + info = what_to_do_list[0] + if info.is_to_stop(): + return + index_num = len(next_index_meet_constrains) ready_time = np.zeros(index_num) due_time = np.zeros(index_num) @@ -137,20 +151,21 @@ class VrptwAco: 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.max(ant.vehicle_travel_time + ant.graph.node_dist_mat[ant.current_index][next_index_meet_constrains], ready_time) - delat_time = delivery_time - ant.vehicle_travel_time - distance = delat_time * (due_time - ant.vehicle_travel_time) - distance = np.max(1.0, distance-IN) + 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)]) + + 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]]) closeness = 1/distance # 按照概率选择下一个点next_index - if np.random.rand() < ant.graph.q0: + if np.random.rand() < q0: max_prob_index = np.argmax(closeness) next_index = next_index_meet_constrains[max_prob_index] else: # 使用轮盘赌算法 - next_index = ant.graph.stochastic_accept(next_index_meet_constrains, closeness) + next_index = VrptwAco.stochastic_accept(next_index_meet_constrains, closeness) ant.move_to_next_index(next_index) # 更新信息素矩阵 @@ -158,26 +173,209 @@ class VrptwAco: # 重新计算可选的下一个点 next_index_meet_constrains = ant.cal_next_index_meet_constrains() - ant.insertion_procedure() + ant.insertion_procedure(what_to_do_list) # ant.index_to_visit_empty()==True就是feasible的意思 if local_search is True and ant.index_to_visit_empty(): - new_path = ant.local_search_procedure() - if new_path is not None: - pass + ant.local_search_procedure(what_to_do_list) - def acs_time(self, vehicle_num): - # how to calculate init_pheromone_val - new_graph = self.graph.construct_graph_with_duplicated_depot(vehicle_num, 1) + return ant.get_path_without_duplicated_depot() + @staticmethod + def acs_time(new_graph: VrptwGraph, vehicle_num, ants_num, q0, what_to_do: Queue, what_is_found: Queue): + print('[acs_time]: start, vehicle_num %d' % vehicle_num) # 初始化信息素矩阵 + global_best_path = [] + global_best_distance = None + ants_pool = ThreadPoolExecutor(ants_num) + ants_thread = [] + ants = [] + ants_what_to_do_list = [] while True: - for k in range(self.ants_num): + for k in range(ants_num): + ant = Ant(new_graph, random.randint(0, vehicle_num - 1)) + what_to_do_list = [] + thread = ants_pool.submit(VrptwAco.new_active_ant, ant, True, np.zeros(new_graph.node_num), q0, what_to_do_list) + + ants_thread.append(thread) + ants.append(ant) + ants_what_to_do_list.append(what_to_do_list) + + # 这里可以使用result方法，等待线程跑完 + for thread in ants_thread: + + while not what_to_do.empty(): + info = what_to_do.get() + if info.is_to_stop(): + print('[acs_time]: receive stop info') + # 顺便要让蚂蚁线程都结束 + for what_to_do_list in ants_what_to_do_list: + what_to_do_list.append(VrptwMessage('stop', None, None)) + ants_pool.shutdown() + return + else: + print('[acs_time]: receive global path info') + global_best_path, global_best_distance = info.get_path_info() + + thread.result() + + # 判断蚂蚁找出来的路径是否是feasible的，并且比全局的路径要好 + for ant in ants: + # 如果比全局的路径要好，则要将该路径发送到macs中 + while not what_to_do.empty(): + info = what_to_do.get() + if info.is_to_stop(): + print('[acs_time]: receive stop info') + # 顺便要让蚂蚁线程都结束 + for what_to_do_list in ants_what_to_do_list: + what_to_do_list.append(VrptwMessage('stop', None, None)) + ants_pool.shutdown() + return + else: + print('[acs_time]: receive global path info') + global_best_path, global_best_distance = info.get_path_info() + + 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') + what_is_found.put(VrptwMessage('path_info', ant.travel_path, ant.total_travel_distance)) + + # 在这里执行信息素的全局更新 + new_graph.global_update_pheromone(global_best_path, global_best_distance) + + @staticmethod + def acs_vehicle(new_graph: VrptwGraph, vehicle_num, ants_num, q0, what_to_do: Queue, what_is_found: Queue): + print('[acs_vehicle]: start, vehicle_num %d' % vehicle_num) + global_best_path = [] + global_best_distance = None + + # 使用邻近点算法初始化path 和distance + current_path, current_path_distance = new_graph.nearest_neighbor_heuristic() + + # 找出当前path中未访问的结点 + current_index_to_visit = list(range(new_graph.node_num)) + for ind in set(current_path): + current_index_to_visit.remove(ind) + + ants_pool = ThreadPoolExecutor(ants_num) + ants_thread = [] + ants = [] + ants_what_to_do_list = [] + IN = np.zeros(new_graph.node_num) + while True: + for k in range(ants_num): ant = Ant(new_graph, random.randint(0, vehicle_num-1)) - self.new_active_ant(ant, True, 0) - # if ant.index_to_visit_empty() and ant.total_travel_distance < global_travel_distance: - # send ant.travel_path - # pass + what_to_do_list = [] + thread = ants_pool.submit(VrptwAco.new_active_ant, ant, True, IN, q0, what_to_do_list) + + ants_thread.append(thread) + ants.append(ant) + ants_what_to_do_list.append(what_to_do_list) + + # 这里可以使用result方法，等待线程跑完 + for thread in ants_thread: + + while not what_to_do.empty(): + info = what_to_do.get() + if info.is_to_stop(): + # 顺便要让蚂蚁线程都结束 + print('[acs_vehicle]: receive stop info') + for what_to_do_list in ants_what_to_do_list: + what_to_do_list.append(VrptwMessage('stop', None, None)) + ants_pool.shutdown() + return + else: + print('[acs_vehicle]: receive global path info') + global_best_path, global_best_distance = info.get_path_info() + + thread.result() + + for ant in ants: + index_to_visit = 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_index_to_visit = index_to_visit + current_path_distance = ant.total_travel_distance + # 并且将IN设置为0 + IN = np.zeros(new_graph.node_num) + + # 如果这一条路径是feasible的话，就要发到macs_vrptw中 + if ant.index_to_visit_empty(): + print('[acs_vehicle]: found a feasible path, send path info to macs') + what_is_found.put(VrptwMessage('path_info', ant.travel_path, ant.total_travel_distance)) + + # 更新new_graph中的信息素，global + new_graph.global_update_pheromone(current_path, current_path_distance) + + while not what_to_do.empty(): + info = what_to_do.get() + if info.is_to_stop(): + # 顺便要让蚂蚁线程都结束 + print('[acs_vehicle]: receive stop info') + for what_to_do_list in ants_what_to_do_list: + what_to_do_list.append(VrptwMessage('stop', None, None)) + ants_pool.shutdown() + return + else: + 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): + # 在这里需要两个队列，一个队列是macs告诉acs_time和acs_vehicle这两个线程，当前的best path是什么、告诉他们停止计算 + # 另外的一个线程就是用来，接收他们两个计算出来的比best path还要好的feasible path + time_what_to_do = Queue() + vehicle_what_to_do = Queue() + what_is_found = Queue() + + while True: + # acs_vehicle + graph_for_acs_vehicle = self.graph.construct_graph_with_duplicated_depot(self.best_vehicle_num-1, + self.graph.init_pheromone_val) + acs_vehicle_thread = Thread(target=self.acs_vehicle, args=(graph_for_acs_vehicle, self.best_vehicle_num-1, + self.ants_num, self.q0, vehicle_what_to_do, + what_is_found)) + + # acs_time + graph_for_acs_time = self.graph.construct_graph_with_duplicated_depot(self.best_vehicle_num, + self.graph.init_pheromone_val) + acs_time_thread = Thread(target=self.acs_time, args=(graph_for_acs_time, self.best_vehicle_num, + self.ants_num, self.q0, time_what_to_do, what_is_found)) + + # 启动acs_vehicle_thread和acs_time_thread，当他们找到feasible、且是比best path好的路径时，就会发送到macs中来 + print('[macs]: start acs_vehicle and acs_time') + acs_vehicle_thread.start() + acs_time_thread.start() + + best_vehicle_num = self.best_vehicle_num + + while acs_vehicle_thread.is_alive() and acs_time_thread.is_alive(): + path_info = what_is_found.get() + print('[macs]: receive found path info') + found_path, found_path_distance = path_info.get_path_info() + # 如果，这两个线程找到的路径用的车辆更少了，就停止这两个线程，开始下一轮迭代 + # 向acs_time和acs_vehicle中发送停止信息 + + if found_path_distance < self.best_path_distance: + print('[macs]: distance of found path better than best path\'s') + self.best_path = found_path + self.best_vehicle_num = found_path.count(0) - 1 + self.best_path_distance = 0 + + if found_path.count(0)-1 < best_vehicle_num: + print('[macs]: vehicle num of found path better than best path\'s') + self.best_path = found_path + self.best_vehicle_num = found_path.count(0)-1 + self.best_path_distance = 0 + + # 停止acs_time 和 acs_vehicle 两个线程 + print('[macs]: send stop info to acs_time and acs_vehicle') + time_what_to_do.put(VrptwMessage(info_type='stop', path=None, distance=None)) + vehicle_what_to_do.put(VrptwMessage(info_type='stop', path=None, distance=None)) if __name__ == '__main__': @@ -185,4 +383,4 @@ if __name__ == '__main__': graph = VrptwGraph(file_path) vrptw = VrptwAco(graph) - vrptw.run() + vrptw.multiple_ant_colony_system() diff --git a/vrptw_base.py b/vrptw_base.py index 9413731..5837e10 100644 --- a/vrptw_base.py +++ b/vrptw_base.py @@ -32,7 +32,7 @@ class VrptwGraph: self.rho = rho # 创建信息素矩阵 - self.init_pheromone_val = self._nearest_neighbor_heuristic() + self.nnh_travel_path, self.init_pheromone_val = self.nearest_neighbor_heuristic() self.init_pheromone_val = 1/(self.init_pheromone_val * self.node_num) self.pheromone_mat = np.ones((self.node_num, self.node_num)) * self.init_pheromone_val @@ -49,18 +49,14 @@ class VrptwGraph: # 从新计算距离 new_graph.node_dist_mat = np.zeros((new_graph.node_num, new_graph.node_num)) for i in range(new_graph.node_num): - if 0 <= i <= vehicle_num - 1: - original_i = 0 - else: - original_i = i - vehicle_num + 1 + original_i = max(0, i - vehicle_num + 1) + for j in range(i + 1, new_graph.node_num): - if 0 <= i <= vehicle_num - 1: - original_j = 0 - else: - original_j = j - vehicle_num + 1 + original_j = max(0, j - vehicle_num + 1) + new_graph.node_dist_mat[i][j] = self.node_dist_mat[original_i][original_j] + new_graph.node_dist_mat[j][i] = new_graph.node_dist_mat[i][j] - new_graph.node_dist_mat[j][i] = new_graph.node_dist_mat[i][j] = self.node_dist_mat[original_i][original_j] - # 启发式信息 + # 启发式信息 new_graph.heuristic_info_mat = 1 / new_graph.node_dist_mat # 信息素 new_graph.init_pheromone_val = init_pheromone_val @@ -88,6 +84,7 @@ class VrptwGraph: node_dist_mat = np.zeros((node_num, node_num)) for i in range(node_num): node_a = nodes[i] + node_dist_mat[i][i] = 1e-8 for j in range(i+1, node_num): node_b = nodes[j] node_dist_mat[i][j] = VrptwGraph.calculate_dist(node_a, node_b) @@ -115,12 +112,13 @@ class VrptwGraph: self.pheromone_mat[current_ind][next_ind] += self.rho/best_path_distance current_ind = next_ind - def _nearest_neighbor_heuristic(self): + def nearest_neighbor_heuristic(self): index_to_visit = list(range(1, self.node_num)) current_index = 0 current_load = 0 current_time = 0 travel_distance = 0 + travel_path = [0] while len(index_to_visit) > 0: nearest_next_index = self._cal_nearest_next_index(index_to_visit, current_index, current_load, current_time) @@ -129,6 +127,7 @@ class VrptwGraph: current_load = 0 current_time = 0 + travel_path.append(0) current_index = 0 else: current_load += self.nodes[nearest_next_index].demand @@ -141,9 +140,12 @@ class VrptwGraph: index_to_visit.remove(nearest_next_index) travel_distance += self.node_dist_mat[current_index][nearest_next_index] - + travel_path.append(nearest_next_index) current_index = nearest_next_index - return travel_distance + # 最后要回到depot + travel_distance += self.node_dist_mat[current_index][0] + travel_path.append(0) + return travel_path, travel_distance def _cal_nearest_next_index(self, index_to_visit, current_index, current_load, current_time): """ @@ -174,3 +176,19 @@ class VrptwGraph: nearest_ind = next_index return nearest_ind + + +class VrptwMessage: + def __init__(self, info_type, path, distance): + super() + if info_type != 'stop' and info_type != 'path_info': + raise RuntimeError('info_type should be: stop or path_info') + self.info_type = info_type + self.path = copy.deepcopy(path) + self.distance = distance + + def get_path_info(self): + return self.path, self.distance + + def is_to_stop(self): + return self.info_type == 'stop' -- cgit v1.2.3