706 lines
37 KiB
Python
706 lines
37 KiB
Python
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 |