from base_optimizer.optimizer_common import * def dynamic_programming_cycle_path(pcb_data, cycle_placement, assigned_feeder): head_sequence = [] num_pos = sum([placement != -1 for placement in cycle_placement]) + 1 pos, head_set = [], [] feeder_set = set() for head, feeder in enumerate(assigned_feeder): if feeder == -1: continue head_set.append(head) placement = cycle_placement[head] if feeder != -1 and placement == -1: print(assigned_feeder) print(cycle_placement) pos.append([pcb_data.iloc[placement]['x'] - head * head_interval + stopper_pos[0], pcb_data.iloc[placement]['y'] + stopper_pos[1], pcb_data.iloc[placement]['r'], head]) feeder_set.add(feeder - head * interval_ratio) pos.insert(0, [slotf1_pos[0] + ((min(list(feeder_set)) + max(list(feeder_set))) / 2 - 1) * slot_interval, slotf1_pos[1], None, 0]) def get_distance(pos_1, pos_2): # 拾取起始与终止位置 或 非同轴 if pos_1[2] is None or pos_2[2] is None or pos_1[3] + (1 if pos_1[3] % 2 == 0 else -1) != pos_2[3]: return max(axis_moving_time(pos_1[0] - pos_2[0], 0), axis_moving_time(pos_1[1] - pos_2[1], 1)) else: return max(axis_moving_time(pos_1[0] - pos_2[0], 0), axis_moving_time(pos_1[1] - pos_2[1], 1), head_rotary_time(pos_1[2] - pos_2[2])) # 各节点之间的距离 dist = [[get_distance(pos_1, pos_2) for pos_2 in pos] for pos_1 in pos] min_dist = [[np.inf for _ in range(num_pos)] for s in range(1 << num_pos)] min_path = [[[] for _ in range(num_pos)] for s in range(1 << num_pos)] # 状压dp搜索 for s in range(1, 1 << num_pos, 2): # 考虑节点集合s必须包括节点0 if not (s & 1): continue for j in range(1, num_pos): # 终点j需在当前考虑节点集合s内 if not (s & (1 << j)): continue if s == int((1 << j) | 1): # 若考虑节点集合s仅含节点0和节点j，dp边界，赋予初值 # print('j:', j) min_path[s][j] = [j] min_dist[s][j] = dist[0][j] # 枚举下一个节点i，更新 for i in range(1, num_pos): # 下一个节点i需在考虑节点集合s外 if s & (1 << i): continue if min_dist[s][j] + dist[j][i] < min_dist[s | (1 << i)][i]: min_path[s | (1 << i)][i] = min_path[s][j] + [i] min_dist[s | (1 << i)][i] = min_dist[s][j] + dist[j][i] ans_dist = float('inf') ans_path = [] # 求最终最短哈密顿回路 for i in range(1, num_pos): if min_dist[(1 << num_pos) - 1][i] + dist[i][0] < ans_dist: # 更新，回路化 ans_path = min_path[s][i] ans_dist = min_dist[(1 << num_pos) - 1][i] + dist[i][0] for parent in ans_path: head_sequence.append(head_set[parent - 1]) start_head, end_head = head_sequence[0], head_sequence[-1] if pcb_data.iloc[cycle_placement[start_head]]['x'] - start_head * head_interval > \ pcb_data.iloc[cycle_placement[end_head]]['x'] - end_head * head_interval: head_sequence = list(reversed(head_sequence)) return ans_dist, head_sequence @timer_wrapper def greedy_placement_route_generation(component_data, pcb_data, component_result, cycle_result, feeder_slot_result, hinter=True): placement_result, head_sequence_result = [], [] if len(pcb_data) == 0: return placement_result, head_sequence_result mount_point_index = [[] for _ in range(len(component_data))] mount_point_pos = [[] for _ in range(len(component_data))] for i in range(len(pcb_data)): part = pcb_data.iloc[i]['part'] component_index = component_data[component_data['part'] == part].index.tolist()[0] # 记录贴装点序号索引和对应的位置坐标 mount_point_index[component_index].append(i) mount_point_pos[component_index].append([pcb_data.iloc[i]['x'], pcb_data.iloc[i]['y']]) search_dir = 1 # 0：自左向右搜索 1：自右向左搜索 for cycle_set in range(len(component_result)): floor_cycle, ceil_cycle = sum(cycle_result[:cycle_set]), sum(cycle_result[:(cycle_set + 1)]) for cycle in range(floor_cycle, ceil_cycle): # search_dir = 1 - search_dir assigned_placement = [-1] * max_head_index max_pos = [max(mount_point_pos[component_index], key=lambda x: x[0]) for component_index in range(len(mount_point_pos)) if len(mount_point_pos[component_index]) > 0][0][0] min_pos = [min(mount_point_pos[component_index], key=lambda x: x[0]) for component_index in range(len(mount_point_pos)) if len(mount_point_pos[component_index]) > 0][0][0] point2head_range = min(math.floor((max_pos - min_pos) / head_interval) + 1, max_head_index) # 最近邻确定 way_point = None head_range = range(max_head_index - 1, -1, -1) if search_dir else range(max_head_index) for head_counter, head in enumerate(head_range): if component_result[cycle_set][head] == -1: continue component_index = component_result[cycle_set][head] if way_point is None or head_counter % point2head_range == 0: index = 0 if way_point is None: if search_dir: index = np.argmax(mount_point_pos[component_index], axis=0)[0] else: index = np.argmin(mount_point_pos[component_index], axis=0)[0] else: for next_head in head_range: component_index = component_result[cycle_set][next_head] if assigned_placement[next_head] == -1 and component_index != -1: num_points = len(mount_point_pos[component_index]) index = np.argmin( [abs(mount_point_pos[component_index][i][0] - way_point[0]) * .1 + abs( mount_point_pos[component_index][i][1] - way_point[1]) for i in range(num_points)]) head = next_head break # index = np.argmax(mount_point_pos[component_index], axis=0)[0] assigned_placement[head] = mount_point_index[component_index][index] # 记录路标点 way_point = mount_point_pos[component_index][index] way_point[0] += (max_head_index - head - 1) * head_interval if search_dir else -head * head_interval mount_point_index[component_index].pop(index) mount_point_pos[component_index].pop(index) else: head_index, point_index = -1, -1 min_cheby_distance, min_euler_distance = float('inf'), float('inf') for next_head in range(max_head_index): if assigned_placement[next_head] != -1 or component_result[cycle_set][next_head] == -1: continue next_comp_index = component_result[cycle_set][next_head] for counter in range(len(mount_point_pos[next_comp_index])): if search_dir: delta_x = abs(mount_point_pos[next_comp_index][counter][0] - way_point[0] + (max_head_index - next_head - 1) * head_interval) else: delta_x = abs(mount_point_pos[next_comp_index][counter][0] - way_point[0] - next_head * head_interval) delta_y = abs(mount_point_pos[next_comp_index][counter][1] - way_point[1]) euler_distance = pow(axis_moving_time(delta_x, 0), 2) + pow(axis_moving_time(delta_y, 1), 2) cheby_distance = max(axis_moving_time(delta_x, 0), axis_moving_time(delta_y, 1)) + 5e-2 * euler_distance if cheby_distance < min_cheby_distance or (abs(cheby_distance - min_cheby_distance) < 1e-9 and euler_distance < min_euler_distance): # if euler_distance < min_euler_distance: min_cheby_distance, min_euler_distance = cheby_distance, euler_distance head_index, point_index = next_head, counter component_index = component_result[cycle_set][head_index] assert 0 <= head_index < max_head_index assigned_placement[head_index] = mount_point_index[component_index][point_index] way_point = mount_point_pos[component_index][point_index] way_point[0] += (max_head_index - head_index - 1) * head_interval if search_dir \ else -head_index * head_interval mount_point_index[component_index].pop(point_index) mount_point_pos[component_index].pop(point_index) placement_result.append(assigned_placement) # 各个头上贴装的元件类型 head_sequence_result.append( dynamic_programming_cycle_path(pcb_data, assigned_placement, feeder_slot_result[cycle_set])[1]) return placement_result, head_sequence_result @timer_wrapper def beam_search_route_generation(component_data, pcb_data, component_result, cycle_result, feeder_slot_result): beam_width = 10 # 集束宽度 base_points = [float('inf'), float('inf')] mount_point_index = [[] for _ in range(len(component_data))] mount_point_pos = [[] for _ in range(len(component_data))] for idx, data in pcb_data.iterrows(): component_index = component_data[component_data['part'] == data.part].index.tolist()[0] # 记录贴装点序号索引和对应的位置坐标 mount_point_index[component_index].append(idx) mount_point_pos[component_index].append([data.x, data.y]) # 记录最左下角坐标 if mount_point_pos[component_index][-1][0] < base_points[0]: base_points[0] = mount_point_pos[component_index][-1][0] if mount_point_pos[component_index][-1][1] < base_points[1]: base_points[1] = mount_point_pos[component_index][-1][1] beam_placement_sequence, beam_head_sequence = [], [] beam_mount_point_index, beam_mount_point_pos = [], [] for beam_counter in range(beam_width): beam_mount_point_index.append(copy.deepcopy(mount_point_index)) beam_mount_point_pos.append(copy.deepcopy(mount_point_pos)) beam_placement_sequence.append([]) beam_head_sequence.append([]) beam_distance = [0 for _ in range(beam_width)] # 记录当前集束搜索点的点数 def argpartition(list, kth): if kth < len(list): return np.argpartition(list, kth) else: index, indexes = 0, [] while len(indexes) < kth: indexes.append(index) index += 1 if index >= len(list): index = 0 return np.array(indexes) with tqdm(total=100) as pbar: search_dir = 0 pbar.set_description('beam search route schedule') for cycle_set in range(len(component_result)): floor_cycle, ceil_cycle = sum(cycle_result[:cycle_set]), sum(cycle_result[:(cycle_set + 1)]) for cycle in range(floor_cycle, ceil_cycle): search_dir = 1 - search_dir beam_way_point = None for beam_counter in range(beam_width): beam_placement_sequence[beam_counter].append([-1 for _ in range(max_head_index)]) head_range = range(max_head_index - 1, -1, -1) if search_dir else range(max_head_index) for head in head_range: component_index = component_result[cycle_set][head] if component_index == -1: continue if beam_way_point is None: # 首个贴装点的选取，距离基准点最近的beam_width个点 beam_way_point = [[0, 0]] * beam_width for beam_counter in range(beam_width): if search_dir: index = np.argmax(beam_mount_point_pos[beam_counter][component_index], axis=0)[0] else: index = np.argmin(beam_mount_point_pos[beam_counter][component_index], axis=0)[0] beam_placement_sequence[beam_counter][-1][head] = \ beam_mount_point_index[beam_counter][component_index][index] beam_way_point[beam_counter] = beam_mount_point_pos[beam_counter][component_index][index] beam_way_point[beam_counter][0] += (max_head_index - head - 1) * head_interval if \ search_dir else -head * head_interval beam_mount_point_index[beam_counter][component_index].pop(index) beam_mount_point_pos[beam_counter][component_index].pop(index) else: # 后续贴装点 search_beam_distance = [] search_beam_component_index = [0] * (beam_width ** 2) for beam_counter in range(beam_width ** 2): search_beam_distance.append(beam_distance[beam_counter // beam_width]) for beam_counter in range(beam_width): # 对于集束beam_counter + 1最近的beam_width个点 num_points = len(beam_mount_point_pos[beam_counter][component_index]) dist = [] for i in range(num_points): if search_dir: delta_x = axis_moving_time( beam_mount_point_pos[beam_counter][component_index][i][0] - beam_way_point[beam_counter][0] + (max_head_index - head - 1) * head_interval, 0) else: delta_x = axis_moving_time( beam_mount_point_pos[beam_counter][component_index][i][0] - beam_way_point[beam_counter][0] - head * head_interval, 0) delta_y = axis_moving_time(beam_mount_point_pos[beam_counter][component_index][i][1] - beam_way_point[beam_counter][1], 1) dist.append(max(delta_x, delta_y)) indexes = argpartition(dist, kth=beam_width)[:beam_width] # 记录中间信息 for i, index in enumerate(indexes): search_beam_distance[i + beam_counter * beam_width] += dist[index] search_beam_component_index[i + beam_counter * beam_width] = index indexes = np.argsort(search_beam_distance) beam_mount_point_pos_cpy = copy.deepcopy(beam_mount_point_pos) beam_mount_point_index_cpy = copy.deepcopy(beam_mount_point_index) beam_placement_sequence_cpy = copy.deepcopy(beam_placement_sequence) beam_head_sequence_cpy = copy.deepcopy(beam_head_sequence) beam_counter = 0 assigned_placement = [] for i, index in enumerate(indexes): # 拷贝原始集束数据 beam_mount_point_pos[beam_counter] = copy.deepcopy(beam_mount_point_pos_cpy[index // beam_width]) beam_mount_point_index[beam_counter] = copy.deepcopy(beam_mount_point_index_cpy[index // beam_width]) beam_placement_sequence[beam_counter] = copy.deepcopy(beam_placement_sequence_cpy[index // beam_width]) beam_head_sequence[beam_counter] = copy.deepcopy(beam_head_sequence_cpy[index // beam_width]) # 更新各集束最新扫描的的贴装点 component_index = component_result[cycle_set][head] beam_placement_sequence[beam_counter][-1][head] = \ beam_mount_point_index[beam_counter][component_index][search_beam_component_index[index]] if beam_placement_sequence[beam_counter][-1] in assigned_placement \ and beam_width - beam_counter < len(indexes) - i: continue assigned_placement.append(beam_placement_sequence[beam_counter][-1]) # 更新参考基准点 beam_way_point[beam_counter] = beam_mount_point_pos[beam_counter][component_index][ search_beam_component_index[index]] beam_way_point[beam_counter][0] += (max_head_index - head - 1) * head_interval if \ search_dir else -head * head_interval # 更新各集束贴装路径长度，移除各集束已分配的贴装点 beam_distance[beam_counter] = search_beam_distance[index] beam_mount_point_pos[beam_counter][component_index].pop(search_beam_component_index[index]) beam_mount_point_index[beam_counter][component_index].pop(search_beam_component_index[index]) beam_counter += 1 if beam_counter >= beam_width: break assert beam_counter >= beam_width # 更新头贴装顺序 for beam_counter in range(beam_width): beam_head_sequence[beam_counter].append( dynamic_programming_cycle_path(pcb_data, beam_placement_sequence[beam_counter][-1], feeder_slot_result[cycle_set])[1]) pbar.update(1 / sum(cycle_result) * 100) index = np.argmin(beam_distance) print('beam distance : ', beam_distance[index]) return beam_placement_sequence[index], beam_head_sequence[index] def scan_based_placement_route_generation(component_data, pcb_data, component_assign, cycle_assign, feeder_slot_result): placement_result, head_sequence_result = [], [] mount_point_pos, mount_point_index, mount_point_angle, mount_point_part = [], [], [], [] for i, data in pcb_data.iterrows(): component_index = component_data[component_data.part == data.part].index.tolist()[0] # 记录贴装点序号索引和对应的位置坐标 mount_point_index.append(i) mount_point_pos.append([data.x + stopper_pos[0], data.y + stopper_pos[1]]) mount_point_angle.append(data.r) mount_point_part.append(component_index) lBoundary, rBoundary = min(mount_point_pos, key=lambda x: x[0])[0], max(mount_point_pos, key=lambda x: x[0])[0] search_step = max((rBoundary - lBoundary) / max_head_index / 2, 0) ref_pos_y = min(mount_point_pos, key=lambda x: x[1])[1] for cycle_index, component_cycle in enumerate(component_assign): for _ in range(cycle_assign[cycle_index]): min_dist = None tmp_assigned_placement, tmp_assigned_head_seq = [], [] tmp_mount_point_pos, tmp_mount_point_index = [], [] for search_dir in range(3): # 不同的搜索方向，贴装头和起始点的选取方法各不相同 if search_dir == 0: # 从左向右搜索 searchPoints = np.arange(lBoundary, (lBoundary + rBoundary) / 2, search_step) head_range = list(range(max_head_index)) elif search_dir == 1: # 从右向左搜索 searchPoints = np.arange(rBoundary + 1e-3, (lBoundary + rBoundary) / 2, -search_step) head_range = list(range(max_head_index - 1, -1, -1)) else: # 从中间向两边搜索 searchPoints = np.arange(lBoundary, rBoundary, search_step / 2) head_range, head_index = [], (max_head_index - 1) // 2 while head_index >= 0: if 2 * head_index != max_head_index - 1: head_range.append(max_head_index - 1 - head_index) head_range.append(head_index) head_index -= 1 for startPoint in searchPoints: mount_point_pos_cpy, mount_point_index_cpy = copy.deepcopy(mount_point_pos), copy.deepcopy( mount_point_index) mount_point_angle_cpy = copy.deepcopy(mount_point_angle) assigned_placement = [-1] * max_head_index assigned_mount_point = [[0, 0]] * max_head_index assigned_mount_angle = [0] * max_head_index head_counter, point_index = 0, -1 for head_index in head_range: if head_counter == 0: component_index = component_assign[cycle_index][head_index] if component_index == -1: continue min_horizontal_distance = None for index, mount_index in enumerate(mount_point_index_cpy): if mount_point_part[mount_index] != component_index: continue horizontal_distance = abs(mount_point_pos_cpy[index][0] - startPoint) + 1e-3 * abs( mount_point_pos_cpy[index][1] - ref_pos_y) if min_horizontal_distance is None or horizontal_distance < min_horizontal_distance: min_horizontal_distance = horizontal_distance point_index = index else: point_index = -1 min_cheby_distance = None next_comp_index = component_assign[cycle_index][head_index] if assigned_placement[head_index] != -1 or next_comp_index == -1: continue for index, mount_index in enumerate(mount_point_index_cpy): if mount_point_part[mount_index] != next_comp_index: continue point_pos = [[mount_point_pos_cpy[index][0] - head_index * head_interval, mount_point_pos_cpy[index][1]]] cheby_distance, euler_distance = 0, 0 for next_head in range(max_head_index): if assigned_placement[next_head] == -1: continue point_pos.append(assigned_mount_point[next_head].copy()) point_pos[-1][0] -= next_head * head_interval point_pos = sorted(point_pos, key=lambda x: x[0]) for mount_seq in range(len(point_pos) - 1): cheby_distance += max(abs(point_pos[mount_seq][0] - point_pos[mount_seq + 1][0]), abs(point_pos[mount_seq][1] - point_pos[mount_seq + 1][1])) euler_distance += math.sqrt( (point_pos[mount_seq][0] - point_pos[mount_seq + 1][0]) ** 2 + ( point_pos[mount_seq][1] - point_pos[mount_seq + 1][1]) ** 2) cheby_distance += 0.01 * euler_distance if min_cheby_distance is None or cheby_distance < min_cheby_distance: min_cheby_distance, min_euler_distance = cheby_distance, euler_distance point_index = index if point_index == -1: continue head_counter += 1 assigned_placement[head_index] = mount_point_index_cpy[point_index] assigned_mount_point[head_index] = mount_point_pos_cpy[point_index].copy() assigned_mount_angle[head_index] = mount_point_angle_cpy[point_index] mount_point_index_cpy.pop(point_index) mount_point_pos_cpy.pop(point_index) mount_point_angle_cpy.pop(point_index) dist, head_seq = dynamic_programming_cycle_path(pcb_data, assigned_placement, feeder_slot_result[cycle_index]) if min_dist is None or dist < min_dist: tmp_mount_point_pos, tmp_mount_point_index = mount_point_pos_cpy, mount_point_index_cpy tmp_assigned_placement, tmp_assigned_head_seq = assigned_placement, head_seq min_dist = dist mount_point_pos, mount_point_index = tmp_mount_point_pos, tmp_mount_point_index placement_result.append(tmp_assigned_placement) head_sequence_result.append(tmp_assigned_head_seq) return placement_result, head_sequence_result # return placement_route_relink_heuristic(component_data, pcb_data, placement_result, head_sequence_result, # feeder_slot_result, cycle_assign) def placement_route_relink_heuristic(component_data, pcb_data, placement_result, head_sequence_result, feeder_slot_result, cycle_result, hinter=True): cycle_group_index = defaultdict(int) cycle_index = 0 for cycle_group, group in enumerate(cycle_result): for _ in range(group): cycle_group_index[cycle_index] = cycle_group cycle_index += 1 mount_point_pos, mount_point_angle, mount_point_index, mount_point_part = [], [], [], [] for i, data in pcb_data.iterrows(): component_index = component_data[component_data.part == data.part].index.tolist()[0] # 记录贴装点序号索引和对应的位置坐标 mount_point_index.append(i) mount_point_pos.append([data.x + stopper_pos[0], data.y + stopper_pos[1]]) mount_point_angle.append(data.r) mount_point_part.append(component_index) cycle_length, cycle_average_pos = [], [] for cycle, placement in enumerate(placement_result): # prev_pos, prev_angle = None, None cycle_pos_list = [] for idx, head in enumerate(head_sequence_result[cycle]): if point_index := placement[head] == -1: continue cycle_pos_list.append( [mount_point_pos[point_index][0] - head * head_interval, mount_point_pos[point_index][1]]) cycle_average_pos.append([sum(map(lambda pos: pos[0], cycle_pos_list)) / len(cycle_pos_list), sum(map(lambda pos: pos[1], cycle_pos_list)) / len(cycle_pos_list)]) cycle_length.append( dynamic_programming_cycle_path(pcb_data, placement, feeder_slot_result[cycle_group_index[cycle]])[0]) best_placement_result, best_head_sequence_result = copy.deepcopy(placement_result), copy.deepcopy( head_sequence_result) best_cycle_length, best_cycle_average_pos = copy.deepcopy(cycle_length), copy.deepcopy(cycle_average_pos) n_runningtime, n_iteration = 30, 0 start_time = time.time() with tqdm(total=n_runningtime) as pbar: pbar.set_description('swap heuristic process') prev_time = start_time while True: n_iteration += 1 placement_result, head_sequence_result = copy.deepcopy(best_placement_result), copy.deepcopy( best_head_sequence_result) cycle_length = best_cycle_length.copy() cycle_average_pos = copy.deepcopy(best_cycle_average_pos) cycle_index = roulette_wheel_selection(cycle_length) # 根据周期加权移动距离随机选择周期 point_dist = [] # 周期内各贴装点距离中心位置的切氏距离 for head in head_sequence_result[cycle_index]: point_index = placement_result[cycle_index][head] _delta_x = abs(mount_point_pos[point_index][0] - head * head_interval - cycle_average_pos[cycle_index][0]) _delta_y = abs(mount_point_pos[point_index][1] - cycle_average_pos[cycle_index][1]) point_dist.append(max(_delta_x, _delta_y)) # 随机选择一个异常点 head_index = head_sequence_result[cycle_index][roulette_wheel_selection(point_dist)] point_index = placement_result[cycle_index][head_index] # 找距离该异常点最近的周期 min_dist = None chg_cycle_index = -1 for idx in range(len(cycle_average_pos)): if idx == cycle_index: continue dist_ = 0 component_type_check = False for head in head_sequence_result[idx]: dist_ += max(abs(mount_point_pos[placement_result[idx][head]][0] - mount_point_pos[point_index][0]), abs(mount_point_pos[placement_result[idx][head]][1] - mount_point_pos[point_index][1])) if mount_point_part[placement_result[idx][head]] == mount_point_part[point_index]: component_type_check = True if (min_dist is None or dist_ < min_dist) and component_type_check: min_dist = dist_ chg_cycle_index = idx if chg_cycle_index == -1: continue chg_head, min_chg_dist = None, None chg_cycle_point = [] for head in head_sequence_result[chg_cycle_index]: index = placement_result[chg_cycle_index][head] chg_cycle_point.append([mount_point_pos[index][0] - head * head_interval, mount_point_pos[index][1]]) for idx, head in enumerate(head_sequence_result[chg_cycle_index]): chg_cycle_point_cpy = copy.deepcopy(chg_cycle_point) index = placement_result[chg_cycle_index][head] if mount_point_part[index] != mount_point_part[point_index]: continue chg_cycle_point_cpy[idx][0] = (mount_point_pos[index][0]) - head * head_interval chg_dist = 0 aver_chg_pos = [sum(map(lambda x: x[0], chg_cycle_point_cpy)) / len(chg_cycle_point_cpy), sum(map(lambda x: x[1], chg_cycle_point_cpy)) / len(chg_cycle_point_cpy)] for pos in chg_cycle_point_cpy: chg_dist += max(abs(aver_chg_pos[0] - pos[0]), abs(aver_chg_pos[1] - pos[1])) # 更换后各点距离中心更近 if min_chg_dist is None or chg_dist < min_chg_dist: chg_head = head min_chg_dist = chg_dist if chg_head is None: continue # === 第一轮，变更周期chg_cycle_index的贴装点重排 === chg_placement_res = placement_result[chg_cycle_index].copy() chg_placement_res[chg_head] = point_index cycle_point_list = defaultdict(list) for head, point in enumerate(chg_placement_res): if point == -1: continue cycle_point_list[mount_point_part[point]].append(point) for key, point_list in cycle_point_list.items(): cycle_point_list[key] = sorted(point_list, key=lambda p: mount_point_pos[p][0]) chg_placement_res = [] for head, point_index in enumerate(placement_result[chg_cycle_index]): if point_index == -1: chg_placement_res.append(-1) else: part = mount_point_part[point_index] chg_placement_res.append(cycle_point_list[part][0]) cycle_point_list[part].pop(0) chg_place_moving, chg_head_res = dynamic_programming_cycle_path(pcb_data, chg_placement_res, feeder_slot_result[ cycle_group_index[chg_cycle_index]]) # === 第二轮，原始周期cycle_index的贴装点重排 === placement_res = placement_result[cycle_index].copy() placement_res[head_index] = placement_result[chg_cycle_index][chg_head] for point in placement_res: if point == -1: continue cycle_point_list[mount_point_part[point]].append(point) for key, point_list in cycle_point_list.items(): cycle_point_list[key] = sorted(point_list, key=lambda p: mount_point_pos[p][0]) placement_res = [] for head, point_index in enumerate(placement_result[cycle_index]): if point_index == -1: placement_res.append(-1) else: part = mount_point_part[point_index] placement_res.append(cycle_point_list[part][0]) cycle_point_list[part].pop(0) place_moving, place_head_res = dynamic_programming_cycle_path(pcb_data, placement_res, feeder_slot_result[ cycle_group_index[cycle_index]]) # 更新贴装顺序分配结果 placement_result[cycle_index], head_sequence_result[cycle_index] = placement_res, place_head_res placement_result[chg_cycle_index], head_sequence_result[chg_cycle_index] = chg_placement_res, chg_head_res # 更新移动路径 cycle_length[cycle_index], cycle_length[chg_cycle_index] = place_moving, chg_place_moving # 更新平均坐标和最大偏离点索引 point_list, point_index_list = [], [] for head in head_sequence_result[cycle_index]: point_index_list.append(placement_result[cycle_index][head]) point_pos = mount_point_pos[point_index_list[-1]].copy() point_pos[0] -= head * head_interval point_list.append(point_pos) cycle_average_pos[cycle_index] = [sum(map(lambda x: x[0], point_list)) / len(point_list), sum(map(lambda x: x[1], point_list)) / len(point_list)] point_list, point_index_list = [], [] for head in head_sequence_result[chg_cycle_index]: point_index_list.append(placement_result[chg_cycle_index][head]) point_pos = mount_point_pos[point_index_list[-1]].copy() point_pos[0] -= head * head_interval point_list.append(point_pos) cycle_average_pos[chg_cycle_index] = [sum(map(lambda x: x[0], point_list)) / len(point_list), sum(map(lambda x: x[1], point_list)) / len(point_list)] test1 = sum(cycle_length) test2 = sum(best_cycle_length) if sum(cycle_length) < sum(best_cycle_length): best_cycle_length = cycle_length.copy() best_cycle_average_pos = copy.deepcopy(cycle_average_pos) best_placement_result, best_head_sequence_result = copy.deepcopy(placement_result), copy.deepcopy( head_sequence_result) cur_time = time.time() if cur_time - start_time > n_runningtime: break pbar.update(cur_time - prev_time) prev_time = cur_time # print("number of iteration: ", n_iteration) return best_placement_result, best_head_sequence_result