diff options
| -rw-r--r-- | ant.py | 77 | ||||
| -rw-r--r-- | basic_aco.py | 25 | ||||
| -rw-r--r-- | multiple_ant_colony_system.py | 25 | ||||
| -rw-r--r-- | vprtw_aco_figure.py | 3 |
4 files changed, 69 insertions, 61 deletions
@@ -230,45 +230,46 @@ class Ant: # 将self.travel_path分成多段，每段以depot开始，以depot结束，称为route for i in range(1, len(depot_ind)): for j in range(i+1, len(depot_ind)): - if stop_event.is_set(): - # print('[local_search_procedure]: receive stop event') - 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) - if end_a < start_a: - start_a, end_a = end_a, start_a - - start_b = random.randint(depot_ind[j-1]+1, depot_ind[j]-1) - end_b = random.randint(depot_ind[j - 1] + 1, depot_ind[j] - 1) - if end_b < start_b: - start_b, end_b = end_b, start_b - - path = [] - path.extend(self.travel_path[:start_a]) - path.extend(self.travel_path[start_b:end_b+1]) - path.extend(self.travel_path[end_a:start_b]) - path.extend(self.travel_path[start_a:end_a]) - path.extend(self.travel_path[end_b+1:]) - - if len(path) != len(self.travel_path): - raise RuntimeError('error') - - # 判断新生成的path是否是可行的 - check_ant = Ant(self.graph, path[0]) - for ind in path[1:]: - if check_ant.check_condition(ind): - check_ant.move_to_next_index(ind) + for k in range(10): + if stop_event.is_set(): + # print('[local_search_procedure]: receive stop event') + 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) + if end_a < start_a: + start_a, end_a = end_a, start_a + + start_b = random.randint(depot_ind[j-1]+1, depot_ind[j]-1) + end_b = random.randint(depot_ind[j - 1] + 1, depot_ind[j] - 1) + if end_b < start_b: + start_b, end_b = end_b, start_b + + path = [] + path.extend(self.travel_path[:start_a]) + path.extend(self.travel_path[start_b:end_b+1]) + path.extend(self.travel_path[end_a:start_b]) + path.extend(self.travel_path[start_a:end_a]) + path.extend(self.travel_path[end_b+1:]) + + if len(path) != len(self.travel_path): + raise RuntimeError('error') + + # 判断新生成的path是否是可行的 + check_ant = Ant(self.graph, path[0]) + for ind in path[1:]: + if check_ant.check_condition(ind): + check_ant.move_to_next_index(ind) + else: + break + # 如果新生成的path是可行的 + if check_ant.index_to_visit_empty() and check_ant.total_travel_distance < self.total_travel_distance: + # print('success to search') + new_path_travel_distance.append(check_ant.total_travel_distance) + new_path.append(path) else: - break - # 如果新生成的path是可行的 - if check_ant.index_to_visit_empty() and check_ant.total_travel_distance < self.total_travel_distance: - # print('success to search') - new_path_travel_distance.append(check_ant.total_travel_distance) - new_path.append(path) - else: - path.clear() + path.clear() # 找出新生成的path中，路程最小的 if len(new_path_travel_distance) > 0: diff --git a/basic_aco.py b/basic_aco.py index b6e2d50..c841ab3 100644 --- a/basic_aco.py +++ b/basic_aco.py @@ -5,6 +5,7 @@ from vrptw_base import VrptwGraph, PathMessage from ant import Ant from threading import Thread from queue import Queue +import time class BasicACO: @@ -51,6 +52,8 @@ class BasicACO: 最基本的蚁群算法 :return: """ + start_time_total = time.time() + # 最大迭代次数 start_iteration = 0 for iter in range(self.max_iter): @@ -81,33 +84,33 @@ class BasicACO: # 记录当前的最佳路径 best_index = np.argmin(paths_distance) - if self.best_path is None: + if self.best_path is None or paths_distance[best_index] < self.best_path_distance: self.best_path = ants[int(best_index)].travel_path self.best_path_distance = paths_distance[best_index] + self.best_vehicle_num = self.best_path.count(0) - 1 start_iteration = iter # 图形化展示 if self.whether_or_not_to_show_figure: path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance)) - elif paths_distance[best_index] < self.best_path_distance: - self.best_path = ants[int(best_index)].travel_path - self.best_path_distance = paths_distance[best_index] - start_iteration = iter - # 图形化展示 - if self.whether_or_not_to_show_figure: - path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance)) + print('\n') + print('[iteration %d]: find a improved path, its distance is %f' % (iter, self.best_path_distance)) + print('it takes %0.3f second multiple_ant_colony_system running' % (time.time() - start_time_total)) - print('[iteration %d]: best distance %f' % (iter, self.best_path_distance)) # 更新信息素表 self.graph.global_update_pheromone(self.best_path, self.best_path_distance) given_iteration = 100 if iter - start_iteration > given_iteration: - print('iteration is up: can not find better solution in %d iteration' % given_iteration) - print('exit.') + print('\n') + print('iteration exit: can not find better solution in %d iteration' % given_iteration) break + print('\n') + print('final best path distance is %f, number of vehicle is %d' % (self.best_path_distance, self.best_vehicle_num)) + print('it takes %0.3f second multiple_ant_colony_system running' % (time.time() - start_time_total)) + def select_next_index(self, ant): """ 选择下一个结点 diff --git a/multiple_ant_colony_system.py b/multiple_ant_colony_system.py index 5bd5e74..9f20559 100644 --- a/multiple_ant_colony_system.py +++ b/multiple_ant_colony_system.py @@ -377,6 +377,8 @@ class MultipleAntColonySystem: :param path_queue_for_figure: :return: """ + start_time_total = time.time() + # 在这里需要两个队列，time_what_to_do、vehicle_what_to_do， 用来告诉acs_time、acs_vehicle这两个线程，当前的best path是什么，或者让他们停止计算 global_path_to_acs_time = Queue() global_path_to_acs_vehicle = Queue() @@ -389,7 +391,7 @@ class MultipleAntColonySystem: while True: print('[multiple_ant_colony_system]: new iteration') - start_time = time.time() + start_time_found_improved_solution = time.time() # 当前best path的信息，放在queue中以通知acs_time和acs_vehicle当前的best_path是什么 global_path_to_acs_vehicle.put(PathMessage(self.best_path, self.best_path_distance)) @@ -419,10 +421,12 @@ class MultipleAntColonySystem: while acs_vehicle_thread.is_alive() and acs_time_thread.is_alive(): # 如果在指定时间内没有搜索到更好的结果，则退出程序 - end_time = time.time() - if end_time - start_time > 60 * 5: + if time.time() - start_time_found_improved_solution > 60 * 5: stop_event.set() + print(' * ' * 50) print('time is up: cannot find a better solution in given time') + print('it takes %0.3f second from multiple_ant_colony_system running' % (time.time()-start_time_total)) + print(' * ' * 50) return if path_found_queue.empty(): @@ -436,11 +440,12 @@ class MultipleAntColonySystem: if found_path_distance < self.best_path_distance: # 搜索到更好的结果，更新start_time - start_time = time.time() + start_time_found_improved_solution = time.time() - print('-' * 50) + print(' * ' * 50) print('[macs]: distance of found path (%f) better than best path\'s (%f)' % (found_path_distance, self.best_path_distance)) - print('-' * 50) + print('it takes %0.3f second from multiple_ant_colony_system running' % (time.time()-start_time_total)) + print(' * ' * 50) self.best_path = found_path self.best_vehicle_num = found_path_used_vehicle_num self.best_path_distance = found_path_distance @@ -458,13 +463,13 @@ class MultipleAntColonySystem: if found_path_used_vehicle_num < best_vehicle_num: # 搜索到更好的结果，更新start_time - start_time = time.time() + start_time_found_improved_solution = time.time() - print('-' * 50) + 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)) - - print('-' * 50) + print('it takes %0.3f second multiple_ant_colony_system running' % (time.time() - start_time_total)) + print(' * ' * 50) self.best_path = found_path self.best_vehicle_num = found_path_used_vehicle_num self.best_path_distance = found_path_distance diff --git a/vprtw_aco_figure.py b/vprtw_aco_figure.py index 9860f8e..79fab72 100644 --- a/vprtw_aco_figure.py +++ b/vprtw_aco_figure.py @@ -59,10 +59,9 @@ class VrptwAcoFigure: for line in remove_obj: self.figure_ax.lines.remove(line) remove_obj.clear() - plt.pause(1) # 重新绘制line - self.figure_ax.set_title('current path travel distance: %f' % distance) + self.figure_ax.set_title('travel distance: %0.2f, number of vehicles: %d ' % (distance, used_vehicle_num)) self._draw_line(path) plt.pause(1) |