学习周报第十周

算法优化

代码详细解释

def func(x):
    if x.ndim == 1:
        x = x.reshape(1, -1)
    
    A = 10
    n = x.shape[0]
   
    # Rastrigin函数的公式
    return A * n + np.sum(x**2 - A * np.cos(2 * np.pi * x), axis=0)

注释：确定数据为2维，以Rastrigin函数为测试函数。

def fast_flood_fill_optimizer_V3(
   func, # 目标函数
    bounds, # 搜索范围：一个列表，定义了每个维度的搜索区间
    n_droplets_initial=200, # 初始水滴数量
    max_iterations=500, # 最大迭代次数
    water_level_rise_factor=0.005, # 水位上涨因子
    droplet_injection_scale=0.0, # 水滴注入规模
    grid_res=50, # 网格分辨率：用于划分搜索空间的网格大小，分辨率越高，计算成本越高
    verbose=True, # 详细输出模式：设置为 True 时，在运行时打印详细信息
    splash_rate=0.05, # 飞溅率：在每次迭代中随机注入全局探索水滴的比例
    splash_count_min=1, # 最小飞溅水滴数
   
):
    dim = len(bounds)
    
    min_b = np.array([b[0] for b in bounds]) # 将数组的下限组合成数组
    max_b = np.array([b[1] for b in bounds])
    search_space_range = np.linalg.norm(max_b - min_b) # 计算数组之差的范数，根据范数动态调整步长
    
    # 1. 初始化水滴
    droplets = np.zeros((dim, n_droplets_initial)) # 创建数组，形状为维度，水滴个数
    for d_idx in range(dim): # 遍历，为每一个水滴随机生成位置
        low = bounds[d_idx][0]
        high = bounds[d_idx][1]
        droplets[d_idx, :] = np.random.uniform(low, high, n_droplets_initial)
    
    droplet_values = func(droplets)
    
    # 2. 网格初始化 
    grid_min_values = np.full((grid_res, grid_res), np.inf) # 创建一个数组，形状为grid_res，数值为无穷大
    
    # 3. 初始化最佳解
    best_solution = droplets[:, np.argmin(droplet_values)] # 找到最小值的索引
    best_value = np.min(droplet_values) # 最小值为多少
    
    # 4. 定义获取网格索引的辅助函数
    def get_grid_idx(pos):
        scaled_pos = (pos - min_b) / (max_b - min_b) # 将坐标值转换成一个[0，1]的值
        idx = np.floor(scaled_pos * grid_res).astype(int) # 将值转换到对应的网格 
        idx = np.clip(idx, 0, grid_res - 1) # 防止变为整数后，超出网格的有效范围
        return idx[0], idx[1]
    
    # 5. 初始化水位和收敛条件
    water_level = best_value 
    water_level_rise_step = water_level_rise_factor * search_space_range # 设置水位上升步长
    history = [best_value]
    best_value_stagnant_count = 0

for iteration in range(max_iterations):
    # 1. 更新网格的最低点
    for i in range(droplets.shape[1]): 
        x, y = get_grid_idx(droplets[:, i])
        grid_min_values[x, y] = min(grid_min_values[x, y], droplet_values[i])
        
    # 2. 水位上涨
    water_level += water_level_rise_step
    
    # 3. 洪水填充聚类
    flooded_grid = grid_min_values <= water_level # 一个单元格的值小于或等于 water_level，那么在 flooded_grid 中对应位置的值就为 True，表示该区域被水淹没。否则为 False。
    visited = np.zeros_like(flooded_grid, dtype=bool) # 标记是否访问过
    clusters = [] # 存储淹没的索引
    for i in range(grid_res):
        for j in range(grid_res):
            if flooded_grid[i, j] and not visited[i, j]: # 检查当前单元格 (i, j) 是否被水淹没，是否从未被访问过
                cluster_grid_indices = [] #列表
                queue = [(i, j)] # 队列	
                visited[i, j] = True
                while queue:
                    x_g, y_g = queue.pop(0) # 队列的前端取出一个单元格的坐标
                    cluster_grid_indices.append((x_g, y_g)) # 单元格坐标添加到当前聚类的列表中。
                    # 检查相邻的网格点
                    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        nx, ny = x_g + dx, y_g + dy
                         if 0 <= nx < grid_res and 0 <= ny < grid_res and flooded_grid[nx, ny] and not visited[nx, ny]: # 找到满足条件的点（是否淹没，是否被记录
                            visited[nx, ny] = True # 记录
                            queue.append((nx, ny))
                clusters.append(cluster_grid_indices)
    
    # 4. 注入新水滴
    newly_injected_droplets = []
    for cluster_grid in clusters:
        # 在每个聚类中找到最佳点
        best_in_cluster_value = np.inf # 值
        best_in_cluster_pos = None # 位置	
        for i in range(droplets.shape[1]):
            x, y = get_grid_idx(droplets[:, i])
            if (x, y) in cluster_grid and droplet_values[i] < best_in_cluster_value: # 找到最小值，赋值
                best_in_cluster_value = droplet_values[i]
                best_in_cluster_pos = droplets[:, i]
        
        # 在最佳点附近注入新的水滴
        if best_in_cluster_pos is not None: # 在每个找到的局部最优解周围，生成一个或多个新的点进行更精细的探索。
            injection_sigma = droplet_injection_scale * search_space_range # 计算注入时的标准差 droplet_injection_scale: 一个预设的参数，用于控制注入的“紧密”程度。 search_space_range: 搜索空间的对角线长度。
            injected_droplet = np.random.normal(best_in_cluster_pos.reshape(-1, 1), scale=injection_sigma, size=(dim, 1)) #高斯采样
            injected_droplet = np.clip(injected_droplet, min_b.reshape(-1, 1), max_b.reshape(-1, 1)) # 防止溢出
            newly_injected_droplets.append(injected_droplet)

    # 5. 注入飞溅水滴（全局探索）
    splash_count = max(splash_count_min, int(n_droplets_initial * splash_rate))  # 计算水滴数量
    splashed_droplets = np.zeros((dim, splash_count)) # 创建容器
    for d_idx in range(dim):
        splashed_droplets[d_idx, :] = np.random.uniform(bounds[d_idx][0], bounds[d_idx][1], splash_count) 
    
    # 6. 合并水滴并更新最佳解
    new_droplets_array = np.hstack(newly_injected_droplets + [splashed_droplets]) # 将所有新生成的水滴（包括局部注入的和全局随机的）合并成一个单一的 NumPy 数组，方便后续处理。
    droplets = np.hstack((droplets, new_droplets_array))# 将旧水滴与新生成的水滴连接起来
    droplet_values = func(droplets) # 值
    
    old_best_value = best_value
    current_best_value = np.min(droplet_values)
    if current_best_value < best_value:
        best_value = current_best_value
        best_solution = droplets[:, np.argmin(droplet_values)]
    history.append(best_value) #更新
    
    # 7. 检查收敛条件
    if abs(best_value - old_best_value) < min_delta:
        best_value_stagnant_count += 1
    else:
        best_value_stagnant_count = 0
    
    if best_value_stagnant_count >= patience:
        print(f"Best value has not improved for {patience} iterations, terminating...")
        break

数据测试

对上周提出的算法进行多维度的数据测试并且和QDA进行对比

（1）洒水

二维测试：稳定在0.6到1之间，1秒左右收敛。

多维测试：因为实在转换为二维网格，不适用于高纬度。

在修改收敛判断条件，例如将收俩条件改为，判断是否多次迭代后，“湖泊”数量不变，效果仍不显著，并且有概率会陷入局部最小值长时间不收敛的情况。

（2）QDA

2，5，10维度都接近10的负12次，收敛速度，0-10秒不等。

差分进化

1. 种群初始化

• 目的：为算法提供一个初始的、多样化的解集。
• 方法：在问题的 n 维解空间中，随机且均匀地生成 M 个个体。
• 个体表示：每个个体 Xi(0) 是一个 n 维向量，其每个属性 xi,j(0) 在给定的上下限 [min(Lj), max(Lj)] 之间随机取值。
• 建议：种群规模 M 通常建议取维数 n 的 5 到 10 倍。

2. 变异操作

• 目的：通过“差分”生成新的候选解。
• 方法：对于第 g 代种群中的每个个体，随机选择三个不同的个体 X₁(g), X₂(g), X₃(g)。
• 公式：通过以下向量等式生成一个变异个体 H(g)： H(g)=X₁(g)+F⋅(X₂(g)−X₃(g))
• 参数：F 是一个缩放因子，通常取 0.5 左右。过小容易导致早熟收敛，过大则容易陷入局部最优。

3. 交叉操作

• 目的：将变异个体与原始个体进行基因互补，生成试验个体。

• 方法：将第 g 代原始种群中的个体 xi,j(g) 和变异个体 hi,j(g) 的每个属性进行比较。

• 公式：通过以下概率公式生成新的试验个体 vi,j(g) 的每个属性：

  $v_{i,j}(g) = \begin{cases} h_{i,j}(g), & \text{if } rand(0,1) \le cr \\ x_{i,j}(g), & \text{else} \end{cases}$

• 参数：cr 是一个交叉概率，通常取 0.1 左右。

4. 选择操作

• 目的：通过“适者生存”的原则，决定哪些个体进入下一代种群。

• 方法：比较试验个体 Vi(g) 和原始个体 Xi(g) 的适应度（函数值）。

• 机制：执行完全确定的竞争机制。如果试验个体的适应度 f(Vi(g)) 优于原始个体的适应度 f(Xi(g))，则用试验个体替换原始个体。

• 公式：

  $X_i(g+1) = \begin{cases} V_i(g), & \text{if } f(V_i(g)) < f(X_i(g)) \\ X_i(g), & \text{else} \end{cases}$

  （这里假设适应度值越小越好）

测试：速度上根据参数调整，种群数量严格控制到维度的5到10倍

算法在5维以下，算法收敛局部最小值精度很高，速度快。
算法到5维以上，算法收敛局部最小值精度较低，速度快。

计算速度在5维左右与qda拉开差距

测试函数为：Rastrigin

QDA优化

scale在原本的代码中简单的折半，优化为动态。

# 计算当前种群在每个维度上的范围
dim_ranges = np.max(a, axis=1) - np.min(a, axis=1)

scale = np.linalg.norm(dim_ranges)

ite_flag=True

测试：因为其本身优越的性能，在高维度状态下，收敛极其缓慢。不是很实用。究其原因在于：QDA 算法用种群中最远的两个点来计算 scale。只要有一个“行走者”因为随机采样或偶然情况偏离了种群，这个离群点就会导致 scale 值被大幅拉大。

我认为这可能是qda算法性能优越的关键所在。着眼于全局，找到局部，而不是定向的从局部优开始寻找，简而言之：理解寻找最优解的能力，正比于全局关联性。我会在下周的时候验证，如果可行的话，将会运用于我最终的优化算法构建。

定义：参数的定义。

第一性原理：遇事不决量子力学。（物理）

关于为什么DE快于QDA没有什么想法，在之后时间里验证。

调参：为什么这么调整，可解释性