From 1b2e26d831e075770baa8c2c27ef965b1c7743b2 Mon Sep 17 00:00:00 2001 From: JonZhao <1044264932@qq.com> Date: Mon, 27 May 2019 22:45:10 +0800 Subject: =?UTF-8?q?=E7=A7=BB=E9=99=A4=E5=A4=8D=E5=88=B6=E5=A4=9A=E4=B8=AAd?= =?UTF-8?q?epot=E7=9A=84graph=E5=88=9B=E5=BB=BA=E6=96=B9=E6=B3=95=EF=BC=8C?= =?UTF-8?q?=E4=BD=BF=E7=94=A8=E6=9B=B4=E5=8A=A0=E5=8E=9F=E5=A7=8B=E7=9A=84?= =?UTF-8?q?=EF=BC=8C=E5=A6=82=E6=9E=9C=E6=B2=A1=E6=9C=89=E5=8F=AF=E4=BB=A5?= =?UTF-8?q?=E8=BE=BE=E5=88=B0=E7=9A=84=E4=B8=8B=E4=B8=80=E4=B8=AA=E5=AE=A2?= =?UTF-8?q?=E6=88=B7=E7=BB=93=E7=82=B9=EF=BC=8C=E5=88=99=E5=9B=9E=E5=88=B0?= =?UTF-8?q?depot=EF=BC=8C=E5=8F=96=E5=BE=97=E4=BA=86=E4=B8=8D=E9=94=99?= =?UTF-8?q?=E7=9A=84=E6=95=88=E6=9E=9C=EF=BC=8C=E5=B8=A6=E6=8E=A5=E4=B8=8B?= =?UTF-8?q?=E6=9D=A5=E7=BB=A7=E7=BB=AD=E6=B5=8B=E8=AF=95?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- ant.py | 34 ++++++++++++++-------------------- 1 file changed, 14 insertions(+), 20 deletions(-) (limited to 'ant.py') diff --git a/ant.py b/ant.py index 54b096c..3ee888e 100644 --- a/ant.py +++ b/ant.py @@ -128,7 +128,7 @@ class Ant: for insert_index in range(len(self.travel_path)): if stop_event.is_set(): - print('[try_insert_on_path]: receive stop event') + # print('[try_insert_on_path]: receive stop event') return if self.graph.nodes[self.travel_path[insert_index]].is_depot: @@ -155,7 +155,7 @@ class Ant: for next_ind in self.travel_path[insert_index:]: if stop_event.is_set(): - print('[try_insert_on_path]: receive stop event') + # print('[try_insert_on_path]: receive stop event') return if check_ant.check_condition(next_ind): @@ -183,13 +183,6 @@ class Ant: best_ind = feasible_insert_index[int(min_insert_ind)] return best_ind - 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, stop_even: Event): """ 为每个未访问的结点尝试性地找到一个合适的位置，插入到当前的travel_path @@ -211,7 +204,7 @@ class Ant: for node_id in ind_to_visit: if stop_even.is_set(): - print('[insertion_procedure]: receive stop event') + # print('[insertion_procedure]: receive stop event') return best_insert_index = self.try_insert_on_path(node_id, stop_even) @@ -239,7 +232,7 @@ class Ant: for j in range(i+1, len(depot_ind)): if stop_event.is_set(): - print('[local_search_procedure]: receive stop event') + # print('[local_search_procedure]: receive stop event') return # 随机在两段route，各随机选择一段customer id，交换这两段customer id @@ -257,10 +250,10 @@ class Ant: 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+1]) + path.extend(self.travel_path[start_a:end_a]) path.extend(self.travel_path[end_b+1:]) - if len(path) != self.travel_path: + if len(path) != len(self.travel_path): raise RuntimeError('error') # 判断新生成的path是否是可行的 @@ -277,10 +270,11 @@ class Ant: new_path.append(path) # 找出新生成的path中，路程最小的 - new_path_travel_distance = np.array(new_path_travel_distance) - min_distance_ind = np.argmin(new_path_travel_distance) - min_distance = new_path_travel_distance[min_distance_ind] - - if min_distance < self.total_travel_distance: - self.travel_path = new_path[int(min_distance_ind)] - self.index_to_visit.clear() + if len(new_path_travel_distance) > 0: + new_path_travel_distance = np.array(new_path_travel_distance) + min_distance_ind = np.argmin(new_path_travel_distance) + min_distance = new_path_travel_distance[min_distance_ind] + + if min_distance < self.total_travel_distance: + self.travel_path = new_path[int(min_distance_ind)] + self.index_to_visit.clear() -- cgit v1.2.3