diff options
| -rw-r--r-- | main.py | 94 | ||||
| -rw-r--r-- | vrptw_base.py | 15 |
2 files changed, 74 insertions, 35 deletions
@@ -4,7 +4,7 @@ import random class VRPTW_ACO: - def __init__(self, graph: VPRTW_Graph, ants_num=50, max_iter=300, alpha=1, beta=1, rho=0.1): + def __init__(self, graph: VPRTW_Graph, ants_num=10, max_iter=100, alpha=1, beta=3, rho=0.1): super() # 结点的位置、服务时间信息 self.graph = graph @@ -15,7 +15,7 @@ class VRPTW_ACO: self.alpha = alpha self.beta = beta # 信息素挥发速度 - self.rho = rho + self.pheromone_rho = rho # q0 表示直接选择概率最大的下一点的概率 self.q0 = 0.1 # Q 表示每辆车的最大载重 @@ -35,7 +35,7 @@ class VRPTW_ACO: # 车辆行驶速度 self.vehicle_speed = 60 # 创建信息素矩阵 - self.pheromone_mat = np.ones((graph.node_num, graph.node_num)) + self.pheromone_mat = self.init_pheromone_mat() self.eta_mat = 1 / graph.node_dist_mat # best path @@ -49,17 +49,19 @@ class VRPTW_ACO: """ # 最大迭代次数 for iter in range(self.max_iter): - transition_prob = np.zeros((self.graph.node_num, self.graph.node_num)) + self.pheromone_rho = self.calculate_pheromone_rho(iter) + self.q0 = self.calculate_prob_q0(iter) + # 为每只蚂蚁设置当前车辆负载，当前旅行距离，当前时间 ants = list(Ant(self.graph.node_num) for _ in range(self.ants_num)) for k in range(self.ants_num): # 蚂蚁需要访问完所有的客户 while not ants[k].index_to_visit_empty(): - next_index = self.select_next_index(ants[k], transition_prob) + next_index = self.select_next_index(ants[k]) # 判断加入该位置后，是否还满足约束条件, 如果不满足，则再选择一次，然后再进行判断 if not self.check_condition(ants[k], next_index): - next_index = self.select_next_index(ants[k], transition_prob) + next_index = self.select_next_index(ants[k]) if not self.check_condition(ants[k], next_index): next_index = 0 @@ -70,7 +72,7 @@ class VRPTW_ACO: ants[k].move_to_next_index(self.graph, self.vehicle_speed, 0) # 计算所有蚂蚁的路径长度 - paths_distance = self.calculate_all_path_distance(ants) + paths_distance = np.array([ant.calculate_path_distance(self.graph) for ant in ants]) # 记录当前的最佳路径 best_index = np.argmin(paths_distance) @@ -81,24 +83,64 @@ class VRPTW_ACO: # 更新信息素表 self.update_pheromone_mat(ants, paths_distance) - def select_next_index(self, ant: Ant, transition_prob): + def init_pheromone_mat(self): + """ + 初始化信息素矩阵 + 随机地选择蚂蚁走的下一个位置，并且下一个需要满足载重、行驶距离等要求，直到走完所有的点，然后计算行走的路程L，则信息素初始化为1/(N*L)，这里的N为结点个数 + :return: + """ + ant = Ant(self.graph.node_num) + while not ant.index_to_visit_empty(): + next_index = random.choice(ant.index_to_visit) + if not self.check_condition(ant, next_index): + next_index = random.choice(ant.index_to_visit) + if not self.check_condition(ant, next_index): + next_index = 0 + + ant.move_to_next_index(self.graph, self.vehicle_speed, next_index) + ant.move_to_next_index(self.graph, self.vehicle_speed, 0) + travel_distance = ant.calculate_path_distance(self.graph) + val = (1 / (self.graph.node_num * travel_distance)) + return np.ones((self.graph.node_num, self.graph.node_num)) * val + + def calculate_pheromone_rho(self, iter): + """ + 信息素挥发系数随着迭代次数进行改变 + :param iter: + :return: + """ + if iter <= 1/3 * self.max_iter: + return 0.2 + elif 1/3 * self.max_iter < iter < 2/3 * self.max_iter: + return 0.5 + else: + return 0.8 + + def calculate_prob_q0(self, iter): + """ + q0着迭代次数进行改变 + :param iter: + :return: + """ + return 0.1+0.8 * iter/self.max_iter + + def select_next_index(self, ant: Ant): """ 选择下一个结点 :param ant: - :param transition_prob: :return: """ current_index = ant.current_index index_to_visit = ant.index_to_visit - transition_prob[ant.current_index][ant.index_to_visit] = np.power(self.pheromone_mat[current_index][index_to_visit], self.alpha) * \ + transition_prob = np.power(self.pheromone_mat[current_index][index_to_visit], self.alpha) * \ np.power(self.eta_mat[current_index][index_to_visit], self.beta) if np.random.rand() < self.q0: - max_prob_index = np.argmax(transition_prob[current_index][index_to_visit]) + max_prob_index = np.argmax(transition_prob) next_index = index_to_visit[max_prob_index] else: # 使用轮盘度 - next_index = self.stochastic_accept(index_to_visit, transition_prob[current_index][index_to_visit]) + next_index = self.stochastic_accept(index_to_visit, transition_prob) return next_index def check_condition(self, ant: Ant, next_index) -> bool: @@ -120,7 +162,7 @@ class VRPTW_ACO: 更新信息素矩阵 :return: """ - self.pheromone_mat = (1 - self.rho) * self.pheromone_mat + self.pheromone_mat = (1 - self.pheromone_rho) * self.pheromone_mat for k in range(self.ants_num): path = ants[k].travel_path current_index = path[0] @@ -133,7 +175,7 @@ class VRPTW_ACO: :param paths: :return: """ - # 注意路径是否是从0开始到0结束的 + # 注意路径是否是从0开始、以0结束的 costs = np.zeros(self.ants_num) for k in range(self.ants_num): path = ants[k].travel_path @@ -141,29 +183,13 @@ class VRPTW_ACO: for index in path[1:]: if index == 0: costs[k] += self.car_cost + self.travel_cost * self.graph.node_dist_mat[current_index][index] - else: - costs[k] += self.travel_cost * self.graph.node_dist_mat[current_index][index] - # 这里如何计算是否是早到了，还是迟到了，我还没有记录时间 - costs[k] += 0 + costs[k] += self.travel_cost * self.graph.node_dist_mat[current_index][index] + costs[k] += self.before_ready_time_cost * max(self.graph.nodes[index].ready_time-ants[k].arrival_time, 0) + \ + self.after_due_time_cost * max(ants[k].arrival_time-self.graph.nodes[index].due_time, 0) current_index = index return costs - def calculate_all_path_distance(self, ants: list): - """ - 计算所有蚂蚁的行走路径的长度 - :param paths: - :return: - """ - distances = np.zeros(self.ants_num) - for k in range(self.ants_num): - path = ants[k].travel_path - current_index = path[0] - for index in path[1:]: - distances[k] += self.graph.node_dist_mat[current_index][index] - current_index = index - return distances - def stochastic_accept(self, index_to_visit, transition_prob): """ 轮盘赌 @@ -190,5 +216,5 @@ if __name__ == '__main__': file_path = './solomon-100/c101.txt' graph = VPRTW_Graph(file_path) - vrptw = VRPTW_ACO(graph, ants_num=50, max_iter=300, alpha=1, beta=1, rho=0.1) + vrptw = VRPTW_ACO(graph) vrptw.run() diff --git a/vrptw_base.py b/vrptw_base.py index 798ffc7..2541842 100644 --- a/vrptw_base.py +++ b/vrptw_base.py @@ -87,4 +87,17 @@ class Ant: self.current_index = next_index def index_to_visit_empty(self): - return len(self.index_to_visit) == 0
\ No newline at end of file + return len(self.index_to_visit) == 0 + + def calculate_path_distance(self, graph: VPRTW_Graph): + """ + 计算所有蚂蚁的行走路径的长度 + :param paths: + :return: + """ + distance = 0 + current_index = self.travel_path[0] + for index in self.travel_path[1:]: + distance += graph.node_dist_mat[current_index][index] + current_index = index + return distance |