模拟退火算法求助

1493916656

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

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Circle
import tensorflow as tf
from tqdm import tqdm
# Example usage of simulated_annealing() function
# Set initial temperature and cooling rate
initial_temperature = 1000
cooling_rate = 0.99

# 障碍圆的位置和半径
obstacle_center = np.array([0, 0])
obstacle_radius = 500
min_turning_radius = 30 
#无人机的速度 speed_A=10 speed_B=10
# 两架无人机的初始位置和目标位置
A_start = np.array([-1000, 0])
A_goal = np.array([3500,0 ])
B_start = np.array([3500, 0])
B_goal = np.array([-1000, 0])

def create_model(input_shape):
    model = tf.keras.Sequential([
        tf.keras.layers.Dense(512, activation='relu', input_shape=input_shape),
        tf.keras.layers.Dense(512, activation='relu'),
        tf.keras.layers.Dense(2)  # 输出轨迹的点坐标
    ])
    return model
# 生成随机飞行轨迹
def generate_random_trajectory(start, goal, steps):
    x = np.linspace(start[0], goal[0], steps)
    y = np.linspace(start[1], goal[1], steps)
    trajectory = np.column_stack((x, y))
    return trajectory
# 检查是否避开障碍圆
def check_obstacle_avoidance(trajectory):
    distances = np.linalg.norm(trajectory - obstacle_center, axis=1)
    return np.all(distances > obstacle_radius)

def check_minimum_turning_radius(trajectory, min_turning_radius):
    for i in range(len(trajectory) - 2):
        point1, point2, point3 = trajectory[i], trajectory[i+1], trajectory[i+2]

        # 计算转弯半径
        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)))))

        if radius < min_turning_radius:
            return False

    return True


# 计算直线到点的距离
def line_point_distance(line_start, line_end, point):
    line_vec = line_end - line_start
    point_vec = point - line_start
    line_length = np.linalg.norm(line_vec)
    line_unit_vec = line_vec / line_length
    projection_length = np.dot(point_vec, line_unit_vec)
    if projection_length < 0:
        return np.linalg.norm(point_vec)
    elif projection_length > line_length:
        return np.linalg.norm(point - line_end)
    else:
        projection_point = line_start + projection_length * line_unit_vec
        return np.linalg.norm(point - projection_point)

# 检查是否避免碰面
def check_no_collisions(trajectory_A, trajectory_B):
    for i in range(len(trajectory_A) - 1):
        point_A1, point_A2 = trajectory_A[i], trajectory_A[i + 1]
        point_B1, point_B2 = trajectory_B[i], trajectory_B[i + 1]

        # 判断连线与障碍圆是否相交
        distance_A1 = line_point_distance(point_A1, point_A2, obstacle_center)
        distance_B1 = line_point_distance(point_B1, point_B2, obstacle_center)

        if distance_A1 <= obstacle_radius or distance_B1 <= obstacle_radius:
            return True

    return False
#计算飞行时间
def time_to_reach_goal(trajectory, speed):
    total_distance = 0.0
    for i in range(len(trajectory) - 1):
        total_distance += np.linalg.norm(trajectory[i + 1] - trajectory[i])

    time_to_reach_goal = total_distance / speed
    return time_to_reach_goal


#模拟退火算法
def simulated_annealing(iterations, speed_A, speed_B, initial_temperature, cooling_rate):
    current_trajectory_A = generate_random_trajectory(A_start, A_goal, steps=10000)
    current_trajectory_B = generate_random_trajectory(B_start, B_goal, steps=10000)
    best_trajectory_A = current_trajectory_A.copy()
    best_trajectory_B = current_trajectory_B.copy()

    shortest_time_A = time_to_reach_goal(current_trajectory_A, speed_A)

    for i in tqdm(range(iterations)):
        # 生成邻域内的随机新解
        new_trajectory_A = generate_random_trajectory(A_start, A_goal, steps=10000)
        new_trajectory_B = generate_random_trajectory(B_start, B_goal, steps=10000)

        # 检查约束条件
        if check_obstacle_avoidance(new_trajectory_A) and \
           check_no_collisions(new_trajectory_A, new_trajectory_B) and \
           check_minimum_turning_radius(new_trajectory_A, min_turning_radius):

            # 计算用时
            time_A = time_to_reach_goal(new_trajectory_A, speed_A)

            # 计算能量差
            energy_difference = shortest_time_A - time_A

            # 判断是否接受新解
            if energy_difference > 0 or np.random.rand() < np.exp(energy_difference / initial_temperature):
                current_trajectory_A = new_trajectory_A.copy()

                # 更新最优解
                if time_A < shortest_time_A:
                    best_trajectory_A = new_trajectory_A.copy()
                    shortest_time_A = time_A

        # 降低温度
        initial_temperature *= cooling_rate

    # 返回最优轨迹和B对应的轨迹
    return best_trajectory_A, current_trajectory_B



def visualize_trajectory(trajectory_A, trajectory_B):
    plt.figure(figsize=(8, 6))
    plt.plot(trajectory_A[:, 0], trajectory_A[:, 1], label='无人机A')
    plt.plot(trajectory_B[:, 0], trajectory_B[:, 1], label='无人机B')
    plt.scatter(A_start[0], A_start[1], color='green', marker='o', label='无人机A起点')
    plt.scatter(A_goal[0], A_goal[1], color='green', marker='x', label='无人机A目标点')
    plt.scatter(B_start[0], B_start[1], color='blue', marker='o', label='无人机B起点')
    plt.scatter(B_goal[0], B_goal[1], color='blue', marker='x', label='无人机B目标点')
    
    # 绘制障碍圆
    obstacle_circle = Circle(obstacle_center, obstacle_radius, edgecolor='red', facecolor='none')
    plt.gca().add_patch(obstacle_circle)
    
    plt.xlabel('X坐标')
    plt.ylabel('Y坐标')
    plt.title('无人机飞行轨迹')
    plt.legend()
    plt.grid(True)
    plt.axis('equal')  # 设置坐标轴刻度相等，确保圆形显示不被压缩
    plt.show()
# 运行模拟退火算法并获取最优轨迹和B对应的轨迹
best_trajectory_A, current_trajectory_B = simulated_annealing(iterations=500000, speed_A=10, speed_B=10, initial_temperature=1000, cooling_rate=0.99)

# 可视化最优轨迹（增加判断）
if best_trajectory_A is not None and current_trajectory_B is not None:
    visualize_trajectory(best_trajectory_A, current_trajectory_B)
else:
    print("未找到满足约束条件的飞行轨迹，无法进行可视化。")

陶远航

根据提供的代码，以下是可能导致问题的几个方面：

1. iterations 的值可能需要增加。当前设置为 500,000，这可能不足以获得最佳解决方案。尝试增加该值，例如设置为 1,000,000，看看是否能够找到更好的解决方案。

2. 随机生成的新轨迹的步数 (steps) 设置为 10,000。这个值可能过高，导致搜索空间过大，使得模拟退火算法难以找到满足约束条件的解决方案。可以尝试减少 steps 的值，例如设置为 1,000。

3. 温度衰减率 (cooling_rate) 设置为 0.99。这个值可能过小，导致退火速度太慢，无法在合理时间内找到较优的解决方案。可以尝试增大 cooling_rate 的值，例如设置为 0.999。

4. 可能需要对神经网络模型进行调整和训练，以获得更准确的飞行轨迹预测。可以尝试更深层次的模型、不同的激活函数和优化器，以及更多的训练数据，来改进模型的性能。

请注意，以上只是一些可能导致问题的方面，并不能保证一定解决问题。调试复杂算法往往需要不断尝试和调整参数，以找到最佳的解决方案。
如果问题已经解决，请设置最佳答案

Mike_python小

代码中存在几个问题导致无法找到满足约束条件的飞行轨迹：

1. 生成随机飞行轨迹的步长过大：在generate_random_trajectory函数中，步长steps设置为10000，这会导致生成的轨迹点之间距离较大，不满足最小转弯半径的限制。你可以尝试将步长调小一些，例如设置为100或更小的值。

2. 模拟退火算法参数设定不合适：在simulated_annealing函数中，迭代次数iterations设置为500000，温度初始值initial_temperature设置为1000，冷却率cooling_rate设置为0.99。这些参数可能需要根据具体情况进行调整。你可以尝试增加迭代次数，增加初始温度，或者减小冷却率，以增加算法搜索空间和收敛速度。

3. 判断连线与障碍圆相交的方法不正确：在check_no_collisions函数中，使用了line_point_distance函数来判断连线与障碍圆是否相交。然而，该方法只能判断线段与圆的距离，不能判断线段是否和圆相交。你可以参考其他方法来判断线段和圆是否相交，例如计算线段和圆心的距离，并比较距离和圆的半径的关系。

除了以上问题，你还可以尝试以下改进来提高算法的效果：

1. 调整无人机的初始位置和目标位置：在当前代码中，无人机A的起点为[-1000, 0]，目标点为[3500, 0]；无人机B的起点为[3500, 0]，目标点为[-1000, 0]。你可以尝试调整这些位置，以探索更多可能的飞行轨迹。

2. 调整模型的结构和超参数：你可以尝试使用不同的神经网络结构、层数和激活函数，或者调整训练的超参数，以改进模型的性能。

3. 使用其他优化算法：除了模拟退火算法，还有其他优化算法可以尝试，例如遗传算法、粒子群优化等。你可以尝试使用这些算法来求解该问题。

希望以上建议对你有所帮助，祝你成功优化无人机飞行轨迹的模拟退火算法！如果还有其他问题，请随时提问。

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

isdkz

在这段代码中，您试图通过模拟退火算法来寻找两架无人机的飞行航迹方案，使得它们分别从A、B两个站点出发，避开障碍圆，并且不碰面，到达各自的目标站点的用时最短。然而，您发现输出结果要么是通过圆心的一条直线，要么是输出无法找到飞行轨迹。

在分析代码时，我们可以注意到一些问题：

1. 生成随机飞行轨迹的步长太长：在 generate_random_trajectory 函数中，您将步长设置为 steps=10000 ，这可能导致生成的轨迹过于直线化，难以满足避开障碍圆和不碰面的条件。较小的步长可以增加轨迹的曲折性，使其更有可能符合约束条件。

2. 模拟退火算法的迭代次数较少：您设置了 iterations=500000 ，但对于这样的复杂问题，可能需要更多的迭代次数来搜索到较优解。较少的迭代次数可能导致算法未能充分探索搜索空间。

3. 温度下降速率过快：您将冷却率设置为 cooling_rate=0.99 ，这会导致温度很快下降，可能使算法陷入局部最优解。较小的冷却率可以使算法更有机会跳出局部最优解，寻找到全局最优解。

4. 可视化代码判断问题：在可视化代码部分，判断最优轨迹和当前轨迹是否为空的逻辑存在问题。即使找不到满足约束条件的飞行轨迹，也应该尝试可视化当前轨迹。

针对以上问题，我们可以尝试进行以下调整：

1.  generate_random_trajectory 函数中减小步长，比如将 steps 设置为100或更小的值。

2. 增加模拟退火算法的迭代次数，将 iterations 设置为一个更大的值，比如100万次。

3. 调整冷却率，将 cooling_rate 设置为0.95或更小的值。

4. 可视化代码部分修改为如下逻辑，尝试可视化当前轨迹：

# 可视化当前轨迹
visualize_trajectory(current_trajectory_A, current_trajectory_B)

# 判断最优轨迹是否存在，如果存在则进行可视化
if best_trajectory_A is not None:
    visualize_trajectory(best_trajectory_A, current_trajectory_B)
else:
    print("未找到满足约束条件的飞行轨迹，无法进行最优轨迹的可视化。")

以上是针对代码中可能存在的问题的一些建议调整。但请注意，模拟退火算法的性能和结果也受到初始温度等参数的影响，可能需要进一步的参数调优和算法优化。另外，这样的优化问题通常较为复杂，也可能需要使用其他更适合的优化算法来解决。如果问题仍然存在，您可以尝试使用其他优化算法或对模拟退火算法进行更深入的调优和分析。

1493916656

调整参数似乎不起作用，可能是定义的约束条件有错误？