1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
import numpy as np
from vrptw_base import VPRTW_Graph, Ant
import random
class VRPTW_ACO:
def __init__(self, graph: VPRTW_Graph, ants_num=10, max_iter=100, alpha=1, beta=3, rho=0.1):
super()
# 结点的位置、服务时间信息
self.graph = graph
# 蚂蚁数量
self.ants_num = ants_num
# 最大迭代次数
self.max_iter = max_iter
self.alpha = alpha
self.beta = beta
# 信息素挥发速度
self.pheromone_rho = rho
# q0 表示直接选择概率最大的下一点的概率
self.q0 = 0.1
# Q 表示每辆车的最大载重
self.max_load = graph.vehicle_capacity
# L 表示每辆车的最远行驶距离
self.max_travel_distance = 2000
# 出车的单位成本
self.car_cost = 50
# 行驶的单位成本
self.travel_cost = 1
# 早到时间成本
self.before_ready_time_cost = 1
# 晚到时间成本
self.after_due_time_cost = 2
# 信息素强度
self.Q = 1
# 车辆行驶速度
self.vehicle_speed = 60
# 创建信息素矩阵
self.pheromone_mat = self.init_pheromone_mat()
self.eta_mat = 1 / graph.node_dist_mat
# best path
self.best_path_distance = None
self.best_path = None
def run(self):
"""
运行蚁群优化算法
:return:
"""
# 最大迭代次数
for iter in range(self.max_iter):
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])
# 判断加入该位置后，是否还满足约束条件, 如果不满足，则再选择一次，然后再进行判断
if not self.check_condition(ants[k], next_index):
next_index = self.select_next_index(ants[k])
if not self.check_condition(ants[k], next_index):
next_index = 0
# 更新蚂蚁路径
ants[k].move_to_next_index(self.graph, self.vehicle_speed, next_index)
# 最终回到0位置
ants[k].move_to_next_index(self.graph, self.vehicle_speed, 0)
# 计算所有蚂蚁的路径长度
paths_distance = np.array([ant.calculate_path_distance(self.graph) for ant in ants])
# 记录当前的最佳路径
best_index = np.argmin(paths_distance)
if self.best_path is None or paths_distance[best_index] < self.best_path_distance:
self.best_path = ants[best_index].travel_path
self.best_path_distance = paths_distance[best_index]
print('[iteration %d]: best_cost %f' % (iter, self.best_path_distance))
# 更新信息素表
self.update_pheromone_mat(ants, paths_distance)
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:
:return:
"""
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.eta_mat[current_index][index_to_visit], self.beta)
if np.random.rand() < self.q0:
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)
return next_index
def check_condition(self, ant: Ant, next_index) -> bool:
"""
检查移动到下一个点是否满足约束条件
:param ant:
:param next_index:
:return:
"""
current_index = ant.current_index
if ant.vehicle_load + self.graph.nodes[next_index].demand > self.max_load:
return False
if ant.vehicle_travel_distance + self.graph.node_dist_mat[current_index][next_index] + self.graph.node_dist_mat[next_index][0] > self.max_travel_distance:
return False
return True
def update_pheromone_mat(self, ants, paths_distance):
"""
更新信息素矩阵
:return:
"""
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]
for index in path[1:]:
self.pheromone_mat[current_index][index] += self.Q / paths_distance[k]
def calculate_all_path_cost(self, ants):
"""
计算所有蚂蚁行走路径的cost
:param paths:
:return:
"""
# 注意路径是否是从0开始、以0结束的
costs = 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:]:
if index == 0:
costs[k] += self.car_cost + self.travel_cost * self.graph.node_dist_mat[current_index][index]
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 stochastic_accept(self, index_to_visit, transition_prob):
"""
轮盘赌
:param index_to_visit: a list of N index (list or tuple)
:param transition_prob:
:return: selected index
"""
# calculate N and max fitness value
N = len(index_to_visit)
# normalize
max_tran_prob = np.max(transition_prob)
transition_prob = transition_prob/max_tran_prob
# select: O(1)
while True:
# randomly select an individual with uniform probability
ind = int(N * random.random())
if random.random() <= transition_prob[ind]:
return index_to_visit[ind]
if __name__ == '__main__':
file_path = './solomon-100/c101.txt'
graph = VPRTW_Graph(file_path)
vrptw = VRPTW_ACO(graph)
vrptw.run()
|
