模拟退火算法问题

1493916656

在这段代码中，我试图建立一个数学模型：平面上A、B两个无人机站分别位于半径为500 m的障碍圆两边直径的延长线上，A站距离圆心1 km，B站距离圆心3.5 km。两架无人机分别从A、B两站同时出发，以恒定速率10 m/s飞向B站和A站执行任务。飞行过程中两架无人机必须避开障碍圆、并且不得碰面 (即两架无人机的连线必须保持与障碍圆处于相交状态)要求两架无人机中第一个到达目的站点的用时最少，给出两架无人机的飞行航迹方案。 使用了模拟退火算法来进行优化 但是经过调参 输出结果要么是通过圆心的一条直线 要么是输出无法找到飞行轨迹 求助代码什么地方出了问题？

1. import numpy as np
   
2. import matplotlib.pyplot as plt
   
3. from matplotlib.patches import Circle
   
4. import tensorflow as tf
   
5. from tqdm import tqdm
   
6. # Example usage of simulated_annealing() function
   
7. # Set initial temperature and cooling rate
   
8. initial_temperature = 1000
   
9. cooling_rate = 0.99
   
10. 
    
11. # 障碍圆的位置和半径
    
12. obstacle_center = np.array([0, 0])
    
13. obstacle_radius = 500
    
14. min_turning_radius = 30
    
15. #无人机的速度 speed_A=10 speed_B=10
    
16. # 两架无人机的初始位置和目标位置
    
17. A_start = np.array([-1000, 0])
    
18. A_goal = np.array([3500,0 ])
    
19. B_start = np.array([3500, 0])
    
20. B_goal = np.array([-1000, 0])
    
21. 
    
22. def create_model(input_shape):
    
23.     model = tf.keras.Sequential([
    
24.         tf.keras.layers.Dense(512, activation='relu', input_shape=input_shape),
    
25.         tf.keras.layers.Dense(512, activation='relu'),
    
26.         tf.keras.layers.Dense(2)  # 输出轨迹的点坐标
    
27.     ])
    
28.     return model
    
29. # 生成随机飞行轨迹
    
30. def generate_random_trajectory(start, goal, steps):
    
31.     x = np.linspace(start[0], goal[0], steps)
    
32.     y = np.linspace(start[1], goal[1], steps)
    
33.     trajectory = np.column_stack((x, y))
    
34.     return trajectory
    
35. # 检查是否避开障碍圆
    
36. def check_obstacle_avoidance(trajectory):
    
37.     distances = np.linalg.norm(trajectory - obstacle_center, axis=1)
    
38.     return np.all(distances > obstacle_radius)
    
39. 
    
40. def check_minimum_turning_radius(trajectory, min_turning_radius):
    
41.     for i in range(len(trajectory) - 2):
    
42.         point1, point2, point3 = trajectory[i], trajectory[i+1], trajectory[i+2]
    
43. 
    
44.         # 计算转弯半径
    
45.         radius = np.linalg.norm(point2 - point1) / (2 * np.sin(np.arccos(np.dot((point2 - point1) / np.linalg.norm(point2 - point1), (point3 - point1) / np.linalg.norm(point3 - point1)))))
    
46. 
    
47.         if radius < min_turning_radius:
    
48.             return False
    
49. 
    
50.     return True
    
51. 
    
52. 
    
53. # 计算直线到点的距离
    
54. def line_point_distance(line_start, line_end, point):
    
55.     line_vec = line_end - line_start
    
56.     point_vec = point - line_start
    
57.     line_length = np.linalg.norm(line_vec)
    
58.     line_unit_vec = line_vec / line_length
    
59.     projection_length = np.dot(point_vec, line_unit_vec)
    
60.     if projection_length < 0:
    
61.         return np.linalg.norm(point_vec)
    
62.     elif projection_length > line_length:
    
63.         return np.linalg.norm(point - line_end)
    
64.     else:
    
65.         projection_point = line_start + projection_length * line_unit_vec
    
66.         return np.linalg.norm(point - projection_point)
    
67. 
    
68. # 检查是否避免碰面
    
69. def check_no_collisions(trajectory_A, trajectory_B):
    
70.     for i in range(len(trajectory_A) - 1):
    
71.         point_A1, point_A2 = trajectory_A[i], trajectory_A[i + 1]
    
72.         point_B1, point_B2 = trajectory_B[i], trajectory_B[i + 1]
    
73. 
    
74.         # 判断连线与障碍圆是否相交
    
75.         distance_A1 = line_point_distance(point_A1, point_A2, obstacle_center)
    
76.         distance_B1 = line_point_distance(point_B1, point_B2, obstacle_center)
    
77. 
    
78.         if distance_A1 <= obstacle_radius or distance_B1 <= obstacle_radius:
    
79.             return True
    
80. 
    
81.     return False
    
82. #计算飞行时间
    
83. def time_to_reach_goal(trajectory, speed):
    
84.     total_distance = 0.0
    
85.     for i in range(len(trajectory) - 1):
    
86.         total_distance += np.linalg.norm(trajectory[i + 1] - trajectory[i])
    
87. 
    
88.     time_to_reach_goal = total_distance / speed
    
89.     return time_to_reach_goal
    
90. 
    
91. 
    
92. #模拟退火算法
    
93. def simulated_annealing(iterations, speed_A, speed_B, initial_temperature, cooling_rate):
    
94.     current_trajectory_A = generate_random_trajectory(A_start, A_goal, steps=10000)
    
95.     current_trajectory_B = generate_random_trajectory(B_start, B_goal, steps=10000)
    
96.     best_trajectory_A = current_trajectory_A.copy()
    
97.     best_trajectory_B = current_trajectory_B.copy()
    
98. 
    
99.     shortest_time_A = time_to_reach_goal(current_trajectory_A, speed_A)
    
100. 
     
101.     for i in tqdm(range(iterations)):
     
102.         # 生成邻域内的随机新解
     
103.         new_trajectory_A = generate_random_trajectory(A_start, A_goal, steps=10000)
     
104.         new_trajectory_B = generate_random_trajectory(B_start, B_goal, steps=10000)
     
105. 
     
106.         # 检查约束条件
     
107.         if check_obstacle_avoidance(new_trajectory_A) and \
     
108.            check_no_collisions(new_trajectory_A, new_trajectory_B) and \
     
109.            check_minimum_turning_radius(new_trajectory_A, min_turning_radius):
     
110. 
     
111.             # 计算用时
     
112.             time_A = time_to_reach_goal(new_trajectory_A, speed_A)
     
113. 
     
114.             # 计算能量差
     
115.             energy_difference = shortest_time_A - time_A
     
116. 
     
117.             # 判断是否接受新解
     
118.             if energy_difference > 0 or np.random.rand() < np.exp(energy_difference / initial_temperature):
     
119.                 current_trajectory_A = new_trajectory_A.copy()
     
120. 
     
121.                 # 更新最优解
     
122.                 if time_A < shortest_time_A:
     
123.                     best_trajectory_A = new_trajectory_A.copy()
     
124.                     shortest_time_A = time_A
     
125. 
     
126.         # 降低温度
     
127.         initial_temperature *= cooling_rate
     
128. 
     
129.     # 返回最优轨迹和B对应的轨迹
     
130.     return best_trajectory_A, current_trajectory_B
     
131. 
     
132. 
     
133. 
     
134. def visualize_trajectory(trajectory_A, trajectory_B):
     
135.     plt.figure(figsize=(8, 6))
     
136.     plt.plot(trajectory_A[:, 0], trajectory_A[:, 1], label='无人机A')
     
137.     plt.plot(trajectory_B[:, 0], trajectory_B[:, 1], label='无人机B')
     
138.     plt.scatter(A_start[0], A_start[1], color='green', marker='o', label='无人机A起点')
     
139.     plt.scatter(A_goal[0], A_goal[1], color='green', marker='x', label='无人机A目标点')
     
140.     plt.scatter(B_start[0], B_start[1], color='blue', marker='o', label='无人机B起点')
     
141.     plt.scatter(B_goal[0], B_goal[1], color='blue', marker='x', label='无人机B目标点')
     
142.    
     
143.     # 绘制障碍圆
     
144.     obstacle_circle = Circle(obstacle_center, obstacle_radius, edgecolor='red', facecolor='none')
     
145.     plt.gca().add_patch(obstacle_circle)
     
146.    
     
147.     plt.xlabel('X坐标')
     
148.     plt.ylabel('Y坐标')
     
149.     plt.title('无人机飞行轨迹')
     
150.     plt.legend()
     
151.     plt.grid(True)
     
152.     plt.axis('equal')  # 设置坐标轴刻度相等，确保圆形显示不被压缩
     
153.     plt.show()
     
154. # 运行模拟退火算法并获取最优轨迹和B对应的轨迹
     
155. best_trajectory_A, current_trajectory_B = simulated_annealing(iterations=500000, speed_A=10, speed_B=10, initial_temperature=1000, cooling_rate=0.99)
     
156. 
     
157. # 可视化最优轨迹（增加判断）
     
158. if best_trajectory_A is not None and current_trajectory_B is not None:
     
159.     visualize_trajectory(best_trajectory_A, current_trajectory_B)
     
160. else:
     
161.     print("未找到满足约束条件的飞行轨迹，无法进行可视化。")

复制代码

陶远航

在代码中，有几个可能导致问题的地方：

1. 参数设置：需要适当调整模拟退火算法的迭代次数（iterations）、初始温度（initial_temperature）和冷却速率（cooling_rate）。这些参数的选择可能会影响算法收敛到最优解的效果。

2. 随机飞行轨迹生成：可以尝试增加或减少生成随机飞行轨迹的步数（steps），以获取更多的轨迹选择。

3. 约束条件检查：确保在检查避开障碍圆、避免碰面以及满足最小转弯半径约束条件时的逻辑正确。可以逐个检查这些条件的实现是否正确。

4. 能量差计算和接受新解条件：在计算能量差（energy_difference）和判断是否接受新解时，确保逻辑正确，并使用正确的能量差计算方式。

建议逐个检查这些部分的实现并进行调试，确保每一步的逻辑正确执行。如果问题仍然存在，可以通过打印中间结果或调试器来进一步排查问题。
如果问题已经解决，请设置最佳答案

isdkz

在这段代码中，您尝试使用模拟退火算法来优化两架无人机的飞行航迹，使得它们分别从A、B两站出发，以恒定速率飞向对方执行任务，并在飞行过程中避开障碍圆，且不得碰面。但是，您发现经过调参后输出的结果要么是通过圆心的一条直线，要么是输出无法找到飞行轨迹。接下来，我将分析代码，并找出可能出现问题的地方。

代码中包含了模拟退火算法的实现，并在其中使用了一些辅助函数来检查约束条件、计算飞行时间以及可视化飞行轨迹。主要问题可能出现在模拟退火算法的实现或约束条件的检查上。让我们逐一来检查可能的问题：

1. 随机生成飞行轨迹：在模拟退火算法中，通过generate_random_trajectory()函数随机生成无人机的飞行轨迹。请确保生成的轨迹在可行的区域内，即在障碍圆的外部，且避免直线穿过障碍圆。请检查generate_random_trajectory()函数是否正确生成符合约束条件的轨迹。

2. 约束条件的检查：在模拟退火算法的实现中，通过check_obstacle_avoidance()、check_no_collisions()和check_minimum_turning_radius()函数来检查障碍物避开、不碰面以及满足最小转弯半径的约束条件。请确保这些函数的实现正确，可以正确判断是否满足约束条件。

3. 能量差的计算：在模拟退火算法中，能量差（即目标函数）用于判断是否接受新解。请确保在计算能量差时没有出现错误，并且在更新最优解时，能够正确记录最优轨迹和最短时间。

4. 模拟退火参数：模拟退火算法的性能很大程度上依赖于初始温度、冷却率和迭代次数等参数的选择。请确保这些参数的设置合理，以便算法能够在合理的时间内找到较优解。

综上所述，您需要逐一检查上述几个方面的代码，确认各个函数的实现是否正确，并确保约束条件的检查能够正确判断是否满足要求。如果在实现中遇到具体问题，您可以将出现问题的部分代码分享给我，我将尽力帮助您找出问题所在，并提供解决方案。祝您成功解决问题！

Mike_python小

代码中存在几个问题可能导致模拟退火算法无法找到满足约束条件的飞行轨迹：

1. 生成随机飞行轨迹时，将步长设置为10000，这可能导致生成的轨迹过于稀疏，无法有效避开障碍圆。建议将步长适当减小，比如设置为100或更小的值。

2. current_trajectory_A = generate_random_trajectory(A_start, A_goal, steps=100)
3. current_trajectory_B = generate_random_trajectory(B_start, B_goal, steps=100)

复制代码

2. 在模拟退火算法的邻域搜索中，使用相同的步长生成新的随机飞行轨迹。这可能导致算法陷入局部最优解而无法找到全局最优解。建议在生成新的随机飞行轨迹时，采用逐步逼近的方式，逐渐减小步长。

3. 检查最小转弯半径时，计算半径的方法存在问题。当前代码中计算的是两条线段的夹角余弦值，而没有考虑到无人机的飞行方向和转向半径。建议重新计算转弯半径，可以参考以下代码：

2. def check_minimum_turning_radius(trajectory, min_turning_radius):
3.     for i in range(len(trajectory) - 2):
4.         point1, point2, point3 = trajectory[i], trajectory[i+1], trajectory[i+2]
5.         
6.         v1 = point2 - point1
7.         v2 = point3 - point2
8.         
9.         angle = np.arccos(np.dot(v1, v2) / (np.linalg.norm(v1) * np.linalg.norm(v2)))
10.         radius = np.linalg.norm(v1) / (2 * np.sin(angle / 2))
11.         
12.         if radius < min_turning_radius:
13.             return False
14.     return True

复制代码

通过以上修改，重新运行模拟退火算法，可能会获得满足约束条件的飞行轨迹。另外，建议增加一些输出语句来调试代码，可以输出每次迭代中的最优解和对应的能量差，以便进一步定位问题所在。

球一个最佳答案谢谢啦！这对我非常重要！

tantan1

请问楼主解决了吗，能分享一下吗

tantan1

tantan1 发表于 2023-8-16 14:49
请问楼主解决了吗，能分享一下吗

这代码是不是要执行特别久啊