diff options
Diffstat (limited to 'main.py')
| -rw-r--r-- | main.py | 85 |
1 files changed, 34 insertions, 51 deletions
@@ -1,11 +1,12 @@ import numpy as np -from vrptw_base import VrptwGraph, Ant, NearestNeighborHeuristic import random from vprtw_aco_figure import VrptwAcoFigure +from vrptw_base import VrptwGraph +from ant import Ant class VrptwAco: - def __init__(self, graph: VrptwGraph, ants_num=10, max_iter=200, alpha=1, beta=2, rho=0.1): + def __init__(self, graph: VrptwGraph, ants_num=10, max_iter=200, alpha=1, beta=2): super() # graph 结点的位置、服务时间信息 self.graph = graph @@ -13,24 +14,16 @@ class VrptwAco: self.ants_num = ants_num # max_iter 最大迭代次数 self.max_iter = max_iter + # vehicle_capacity 表示每辆车的最大载重 + self.max_load = graph.vehicle_capacity + # 信息素强度 + self.Q = 1 # alpha 信息素信息重要新 self.alpha = alpha # beta 启发性信息重要性 self.beta = beta - # rho 信息素挥发速度 - self.rho = rho # q0 表示直接选择概率最大的下一点的概率 self.q0 = 0.1 - # vehicle_capacity 表示每辆车的最大载重 - self.max_load = graph.vehicle_capacity - # 信息素强度 - self.Q = 1 - # 创建信息素矩阵 - nn_heuristic = NearestNeighborHeuristic(self.graph) - self.init_pheromone_val = nn_heuristic.cal_init_pheromone_val() - self.pheromone_mat = np.ones((self.graph.node_num, self.graph.node_num)) * self.init_pheromone_val - # 启发式信息矩阵 - self.heuristic_info_mat = 1 / graph.node_dist_mat # best path self.best_path_distance = None self.best_path = None @@ -64,11 +57,11 @@ class VrptwAco: # 更新蚂蚁路径 ants[k].move_to_next_index(next_index) - self.local_update_pheromone(ants[k].current_index, next_index) + self.graph.local_update_pheromone(ants[k].current_index, next_index) # 最终回到0位置 ants[k].move_to_next_index(0) - self.local_update_pheromone(ants[k].current_index, 0) + self.graph.local_update_pheromone(ants[k].current_index, 0) # 计算所有蚂蚁的路径长度 paths_distance = np.array([ant.total_travel_distance for ant in ants]) @@ -76,22 +69,22 @@ class VrptwAco: # 记录当前的最佳路径 best_index = np.argmin(paths_distance) if self.best_path is None: - self.best_path = ants[best_index].travel_path + self.best_path = ants[int(best_index)].travel_path self.best_path_distance = paths_distance[best_index] if self.whether_or_not_to_show_figure: self.figure.init_figure(self.best_path) elif paths_distance[best_index] < self.best_path_distance: - self.best_path = ants[best_index].travel_path + self.best_path = ants[int(best_index)].travel_path self.best_path_distance = paths_distance[best_index] if self.whether_or_not_to_show_figure: self.figure.update_figure(self.best_path) print('[iteration %d]: best distance %f' % (iter, self.best_path_distance)) # 更新信息素表 - self.global_update_pheromone() + self.graph.global_update_pheromone(self.best_path, self.best_path_distance) - def select_next_index(self, ant: Ant): + def select_next_index(self, ant): """ 选择下一个结点 :param ant: @@ -100,8 +93,8 @@ class VrptwAco: current_index = ant.current_index index_to_visit = ant.index_to_visit - transition_prob = np.power(self.pheromone_mat[current_index][index_to_visit], self.alpha) * \ - np.power(self.heuristic_info_mat[current_index][index_to_visit], self.beta) + transition_prob = np.power(self.graph.pheromone_mat[current_index][index_to_visit], self.alpha) * \ + np.power(self.graph.heuristic_info_mat[current_index][index_to_visit], self.beta) if np.random.rand() < self.q0: max_prob_index = np.argmax(transition_prob) @@ -111,22 +104,6 @@ class VrptwAco: next_index = self.stochastic_accept(index_to_visit, transition_prob) return next_index - def local_update_pheromone(self, start_ind, end_ind): - self.pheromone_mat[start_ind][end_ind] = (1-self.rho) * self.pheromone_mat[start_ind][end_ind] + \ - self.rho * self.init_pheromone_val - - def global_update_pheromone(self): - """ - 更新信息素矩阵 - :return: - """ - self.pheromone_mat = (1-self.rho) * self.pheromone_mat - - current_ind = self.best_path[0] - for next_ind in self.best_path[1:]: - self.pheromone_mat[current_ind][next_ind] += self.rho/self.best_path_distance - current_ind = next_ind - def stochastic_accept(self, index_to_visit, transition_prob): """ 轮盘赌 @@ -148,13 +125,7 @@ class VrptwAco: if random.random() <= norm_transition_prob[ind]: return index_to_visit[ind] - def new_active_ant(self, k: int, local_search: bool, IN): - # 对graph中的depot复制k-1，使得depot数量等于k - new_graph = self.graph.construct_graph_with_duplicated_depot(k) - - # 从任意一个depot开始 - start_index = random.randint(0, k-1) - ant = Ant(new_graph, start_index) + def new_active_ant(self, ant: Ant, local_search: bool, IN): # 计算从当前位置可以达到的下一个位置 next_index_meet_constrains = ant.cal_next_index_meet_constrains() @@ -163,10 +134,10 @@ class VrptwAco: ready_time = np.zeros(index_num) due_time = np.zeros(index_num) for i in range(index_num): - ready_time[i] = new_graph.nodes[next_index_meet_constrains[i]].ready_time - due_time[i] = new_graph.nodes[next_index_meet_constrains[i]].due_time + 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 + new_graph.node_dist_mat[ant.current_index][next_index_meet_constrains], ready_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) @@ -174,12 +145,12 @@ class VrptwAco: closeness = 1/distance # 按照概率选择下一个点next_index - if np.random.rand() < self.q0: + if np.random.rand() < ant.graph.q0: max_prob_index = np.argmax(closeness) next_index = next_index_meet_constrains[max_prob_index] else: # 使用轮盘赌算法 - next_index = self.stochastic_accept(next_index_meet_constrains, closeness) + next_index = ant.graph.stochastic_accept(next_index_meet_constrains, closeness) ant.move_to_next_index(next_index) # 更新信息素矩阵 @@ -194,7 +165,19 @@ class VrptwAco: new_path = ant.local_search_procedure() if new_path is not None: pass - print('fuck') + + def acs_time(self, vehicle_num): + # how to calculate init_pheromone_val + new_graph = self.graph.construct_graph_with_duplicated_depot(vehicle_num, 1) + + # 初始化信息素矩阵 + while True: + for k in range(self.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 if __name__ == '__main__': |