数学建模竞赛优化实战：遗传算法与模拟退火求解多波束测线规划

1. 项目概述：从一道赛题到一套完整的优化方案

去年国赛B题“多波束测线问题”出来的时候，我身边不少参赛队伍都卡在了第一问的建模思路上。这道题表面上看是一个海洋测绘的工程问题，内核却是一个典型的、带有复杂约束的组合优化难题。它要求我们在一个矩形海域内，规划一系列平行的测线，用多波束声呐进行全覆盖测量，目标是在满足全覆盖和一定重叠率的前提下，让总测线长度最短。这听起来像是一个“铺瓷砖”问题，但“瓷砖”（即波束脚印）的形状会随着水深和开角变化，测线间距不是固定的，重叠率约束更是让问题变得非线性。对于初次接触这类优化问题的同学来说，很容易陷入局部细节，或者试图用一个过于简化的模型去套，结果就是要么模型建不出来，要么求解效率极低，甚至得不到可行解。

我花了相当一段时间来复盘这道题，不仅仅是为了做出答案，更是想梳理出一套面对此类“覆盖+优化”问题的通用思考框架和实战解法。今天，我就把自己沉淀下来的思路、踩过的坑，以及经过验证的参考代码实现，毫无保留地分享出来。无论你是正在备战数学建模竞赛的学生，还是对路径规划、优化算法感兴趣的开发者，这篇文章都将带你深入问题的核心，从问题本质理解、数学模型构建，到算法选型、代码实现与调参技巧，形成一个完整的闭环。我们会重点探讨如何将连续的覆盖问题离散化建模，以及如何运用遗传算法和模拟退火这两种元启发式算法来高效求解，并提供可直接运行、修改的Python代码。

2. 问题本质与数学模型构建

2.1 核心需求解析：什么是“多波束测线问题”？

我们先把问题从具体的海洋测绘场景中抽象出来。你有一块长方形的任务区域（海域），需要用一个传感器（多波束声呐）去扫描它。这个传感器的探测范围不是一个点，而是一条垂直于前进方向的“带状”区域（称为波束脚印）。传感器沿着一条直线（测线）移动时，这条“带子”就会扫过一片区域。为了让扫描没有遗漏，相邻两条“带子”之间需要有部分重叠。

问题的核心约束和目标就出来了：

1. 全覆盖约束：任务区域内的每一个点，都必须至少被一条测线的波束脚印覆盖到。
2. 重叠率约束：相邻两条测线扫过的区域，其重叠部分的宽度占单条测线覆盖宽度的比例，需要在一个指定范围内（例如10%-20%）。这保证了测量数据的连续性和可靠性，避免因边缘数据质量差而出现漏洞。
3. 优化目标：在满足上述两个约束的前提下，使得所有测线的总长度之和最小。这直接对应着节约测量时间与成本。

难点在于，波束脚印的宽度（即覆盖幅宽）不是常数。它取决于海水的深度和声呐的开角。题目通常会给出水深与位置的关系（如z(x, y)），以及声呐的固定开角theta。那么，在位置(x, y)处，单条测线的覆盖幅宽W可以通过几何关系计算：W(x, y) = 2 * z(x, y) * tan(theta / 2)。这意味着，在深水区，幅宽大，一条测线能扫更宽的区域；在浅水区，幅宽小，需要更密集的测线才能覆盖。

2.2 数学模型建立：从连续空间到离散决策

直接处理连续的测线位置和连续的区域覆盖是非常困难的。我们必须将其离散化，转化为一个计算机可以处理的优化模型。

2.2.1 决策变量定义最直观的决策变量是每条测线的位置。由于测线是平行于矩形区域一条边（假设为y轴方向）的，我们可以用测线在x轴上的坐标x_i(i=1, 2, ..., N) 来表示第i条测线。测线数量N本身也是一个变量，但我们可以先设定一个足够大的上限，然后通过优化来确定实际使用的数量。

2.2.2 约束条件的数学表达

1. 区域边界约束：所有测线x_i必须位于区域x方向的范围内，即x_min <= x_i <= x_max。
2. 全覆盖约束：这是最棘手的部分。我们需要确保区域内在x方向上的任何一点，都被至少一条测线的波束所覆盖。考虑到幅宽随水深变化，这是一个函数约束。一个实用的离散化方法是：将任务区域在x方向上均匀离散成M个细小的条带（或直接离散成网格点）。对于每个离散点x_k，计算其所在位置的平均水深或最不利水深，进而得到该点处所需的“有效覆盖半径”。然后检查是否存在一条测线x_i，使得|x_k - x_i|小于等于该点处幅宽的一半。如果所有离散点x_k都满足这个条件，则认为全覆盖约束近似满足。M越大，近似精度越高，但计算量也越大。
3. 重叠率约束：对于相邻的两条测线x_i和x_{i+1}，它们之间的重叠情况与它们之间的水深变化有关。重叠率eta定义为重叠区域宽度与两条测线平均幅宽之比。我们需要约束eta_min <= eta <= eta_max。计算重叠区域宽度需要知道两条测线中间区域的水深情况，这通常需要通过插值或取平均来估算。

2.2.3 目标函数目标函数很直接：总测线长度。由于测线平行且长度固定（等于区域在y方向的长度L_y），总长度就是N * L_y。但因为N由测线位置{x_i}决定（太密的测线会被优化掉），所以目标函数本质上是关于{x_i}的。

注意：这里有一个关键的建模技巧。很多同学试图同时优化测线数量N和位置{x_i}，这会让问题变得非常复杂。更聪明的做法是固定一个较大的N，但允许测线位置x_i取一个特殊的“无效值”或让两条测线无限接近。在优化过程中，算法自然会倾向于将多余的测线“挤”到一起或标记为无效，从而实现减少有效测线数量的目的。在计算目标函数时，只统计有效测线的长度。

2.3 模型特点与求解策略分析

建立好模型后，我们发现它有几个显著特点：

• 非线性：约束和目标中都有关于决策变量x_i的非线性项（如绝对值、三角函数通过水深计算幅宽）。
• 约束复杂：全覆盖约束是全局性的，涉及所有决策变量和所有离散点。
• 组合性：测线的数量（即有多少条活跃的测线）是组合问题。

传统的基于梯度的优化算法（如拉格朗日乘子法、序列二次规划）处理这类问题非常吃力，因为约束不光滑，且容易陷入局部最优。这正是元启发式算法大显身手的地方，比如遗传算法和模拟退火。它们不依赖于问题的梯度信息，通过模拟自然过程（进化、退火）来在解空间中进行全局搜索，特别适合处理这类黑箱式、多峰值的复杂优化问题。

3. 核心算法选型与原理剖析

既然确定了用元启发式算法，接下来就要在遗传算法和模拟退火之间做出选择，或者思考如何结合。两者没有绝对优劣，但风格迥异。

3.1 遗传算法：群体进化的力量

遗传算法的核心思想是“优胜劣汰，适者生存”。它维护一个包含多个潜在解（称为染色体或个体）的种群，通过选择、交叉、变异等操作模拟生物进化过程，一代代地改进解的质量。

3.1.1 在本题中的具体设计

1. 编码：如何用一个染色体表示一个解？一个很自然的方式是使用实数编码。染色体就是一个长度为N_max（最大允许测线数）的实数数组，数组中的每个基因代表一条测线的x坐标。如果某条测线是无效的，可以将其坐标设为一个超出区域范围的特定值（如-1），或者在计算适应度时忽略距离过近的测线。
2. 适应度函数：这是驱动进化的关键。我们需要设计一个函数，为每个染色体（解）打分。目标是最小化总长度，所以我们可以让适应度与总长度负相关。同时，必须惩罚违反约束的解。一个常用的方法是构造罚函数。例如：Fitness = - (总长度 + α * 覆盖率违例度 + β * 重叠率违例度)其中，α和β是很大的正数惩罚系数。这样，违反约束的解适应度会非常低，在“选择”阶段被淘汰的概率就极大。覆盖率和重叠率的违例度可以量化为未被覆盖的离散点数量，以及超出范围的重叠率误差总和。
3. 遗传操作：
   • 选择：轮盘赌选择或锦标赛选择。适应度高的个体有更大几率被选中进入交配池。
   • 交叉：由于是实数编码，可以采用模拟二进制交叉、算术交叉等。例如，对于两个父代染色体p1和p2，产生一个子代c = λ * p1 + (1-λ) * p2，其中λ是随机数。这能探索父代解之间的区域。
   • 变异：以较小概率随机改变某个基因的值（测线位置）。可以加入高斯扰动，让变异在当前位置附近进行微调。这对于跳出局部最优至关重要。

3.1.2 优势与挑战

• 优势：并行搜索多个解，全局探索能力强。通过交叉操作，能融合不同解的优秀片段。
• 挑战：参数多（种群大小、交叉率、变异率、惩罚系数），调参需要经验。可能收敛速度慢，且后期种群多样性下降，容易“早熟”。

3.2 模拟退火：单个粒子的渐进寻优

模拟退火算法灵感来源于固体退火过程。它从一个初始解开始，通过随机扰动产生新解，并根据Metropolis准则以一定概率接受劣质解，从而有机会跳出局部最优，随着“温度”的降低，接受劣解的概率逐渐减小，算法最终收敛。

3.2.1 在本题中的具体设计

1. 状态与邻域：状态即一个解，同样可以用实数数组表示。邻域操作（产生新解）可以定义为：随机选择一条测线，对其x坐标加上一个小的随机扰动（如高斯噪声）；或者以一定概率增加/删除一条测线。
2. 能量函数：相当于遗传算法中的适应度函数，但这里我们要最小化“能量”。能量函数E可以直接定义为：E = 总长度 + α * 覆盖率违例度 + β * 重叠率违例度目标就是找到使E最小的解。
3. 退火计划表：这是模拟退火的核心参数，包括初始温度T0、温度衰减系数α_T（例如0.95）、每个温度下的迭代次数L、终止温度T_end。初始温度要足够高，使得几乎任何劣解都能被接受；衰减要足够慢，让系统有充分时间平衡。

3.2.2 优势与挑战

• 优势：原理简单，实现方便。通过接受劣解，具有很强的逃离局部最优的能力。参数相对遗传算法更直观。
• 挑战：退火计划表的设计非常关键，且对不同问题敏感。是一种串行搜索，不如遗传算法并行。在超大规模问题上可能收敛慢。

3.3 算法选型与融合建议

对于本题，两种算法都能有效求解。我个人更倾向于以下策略：

• 快速原型与初步探索：使用模拟退火。因为它实现快，参数调整直观，能快速得到一个不错的可行解，帮助你验证模型和约束的正确性。
• 追求更优解与稳定性：使用遗传算法。通过设置合理的种群大小，GA能更系统地搜索解空间，多次运行的结果稳定性通常比单次模拟退火更好。
• 高级策略：混合算法。例如，用遗传算法进行全局探索，找到有潜力的区域；然后将遗传算法得到的最优解作为模拟退火的初始解，进行局部精细搜索。或者，在遗传算法中，对种群中的精英个体偶尔进行模拟退火式的变异（以一定概率接受劣变），以增强局部搜索能力。

4. 代码实现与关键步骤详解

这里我将提供一个基于Python的、以遗传算法为核心的参考代码框架，并融入模拟退火的思想进行局部优化。代码会包含详细的注释，并重点讲解几个关键函数。

4.1 环境准备与问题参数设置

我们首先定义问题的基本参数和工具函数。

import numpy as np import random from typing import List, Tuple # ========== 问题参数 ========== # 区域参数 x_min, x_max = 0.0, 2000.0 # 海域x方向范围 (米) y_min, y_max = 0.0, 1000.0 # 海域y方向范围 (米)，测线长度Ly = y_max - y_min Ly = y_max - y_min # 声呐参数 theta = np.radians(120) # 多波束开角，转换为弧度 (假设120度) tan_half_theta = np.tan(theta / 2) # 重叠率约束 eta_min, eta_max = 0.10, 0.20 # 重叠率范围 10% - 20% # 水深函数 z(x, y) - 这里用一个简单函数示例，实际比赛可能由数据文件给出 def depth(x: float, y: float) -> float: """计算位置(x, y)处的水深。示例：一个平滑变化的斜坡地形。""" return 50.0 + 0.01 * x + 0.005 * y # 基础深度50米，随x,y增加而变深 # 计算单点覆盖幅宽 def beam_width(z: float) -> float: """根据水深z计算波束脚印幅宽。""" return 2 * z * tan_half_theta # 离散化参数 M = 200 # 将x方向离散为M个点，用于检查全覆盖约束 x_check_points = np.linspace(x_min, x_max, M) # 遗传算法参数 POP_SIZE = 50 # 种群大小 MAX_GEN = 200 # 最大进化代数 PC = 0.8 # 交叉概率 PM = 0.1 # 变异概率 N_MAX = 20 # 最大允许测线数（染色体长度） PENALTY_COVER = 1e6 # 覆盖率违例惩罚系数 PENALTY_OVERLAP = 1e5 # 重叠率违例惩罚系数 # 模拟退火参数（用于局部搜索） T0 = 100.0 # 初始温度 T_COOL = 0.95 # 冷却系数 ITER_PER_TEMP = 100 # 每个温度下的迭代次数

4.2 解的表达与适应度计算

这是最核心的部分，决定了算法如何理解一个“解”的好坏。

def decode_individual(chromosome: np.ndarray) -> List[float]: """解码染色体，获取有效的测线位置列表。 处理策略：将染色体中位置排序，并合并距离过近的测线（视为同一条）。 """ # 过滤掉无效值（如果编码时用了-1）并排序 valid_positions = sorted([x for x in chromosome if x_min <= x <= x_max]) if not valid_positions: return [] # 合并距离过近的测线，阈值设为最小可能幅宽的1/10（这是一个经验值） min_depth = depth(x_min, (y_min+y_max)/2) min_width = beam_width(min_depth) merge_threshold = min_width * 0.1 merged_positions = [] current = valid_positions[0] for pos in valid_positions[1:]: if pos - current < merge_threshold: # 合并，取平均 current = (current + pos) / 2 else: merged_positions.append(current) current = pos merged_positions.append(current) return merged_positions def calculate_fitness(chromosome: np.ndarray) -> float: """计算个体的适应度。适应度越高越好。""" positions = decode_individual(chromosome) if len(positions) < 1: return -1e9 # 没有有效测线，适应度极低 # 1. 计算总长度 total_length = len(positions) * Ly # 2. 检查全覆盖约束，计算违例度 coverage_violation = 0.0 for xp in x_check_points: covered = False # 计算该点处的水深和最大允许距离（半幅宽） zp = depth(xp, (y_min+y_max)/2) # 取y方向中点水深作为代表，或可沿y积分，此处简化 max_dist = beam_width(zp) / 2.0 for x_survey in positions: if abs(xp - x_survey) <= max_dist: covered = True break if not covered: coverage_violation += 1.0 # 该点未被覆盖，违例度+1 # 3. 检查重叠率约束，计算违例度 overlap_violation = 0.0 positions_sorted = sorted(positions) for i in range(len(positions_sorted) - 1): x1, x2 = positions_sorted[i], positions_sorted[i+1] # 估算两条测线中点处的水深，用于计算平均幅宽和重叠宽度 x_mid = (x1 + x2) / 2.0 z_mid = depth(x_mid, (y_min+y_max)/2) W = beam_width(z_mid) # 重叠区域宽度 (假设为简单几何模型) D = x2 - x1 overlap_width = max(0, W - D) # 当间距D小于幅宽W时，才有重叠 if W == 0: eta = 0 else: eta = overlap_width / W # 计算违例度 if eta < eta_min: overlap_violation += (eta_min - eta) * W # 按宽度加权惩罚 elif eta > eta_max: overlap_violation += (eta - eta_max) * W # 4. 构造适应度函数：负的总成本（长度+惩罚） # 注意：适应度应越大越好，所以取负号 cost = total_length + PENALTY_COVER * coverage_violation + PENALTY_OVERLAP * overlap_violation fitness = -cost # 因为我们要最小化成本，所以适应度是成本的负数 return fitness

4.3 遗传算法核心操作实现

def initialize_population() -> List[np.ndarray]: """初始化种群。随机生成测线位置，数量在1到N_MAX之间随机。""" population = [] for _ in range(POP_SIZE): # 随机决定这个个体有几条测线（1到N_MAX） n_lines = random.randint(1, N_MAX) # 在[x_min, x_max]范围内随机生成n_lines个位置 lines = np.random.uniform(x_min, x_max, n_lines) # 如果染色体长度固定为N_MAX，则用-1填充剩余位置 if len(lines) < N_MAX: lines = np.pad(lines, (0, N_MAX - n_lines), constant_values=-1) # 打乱顺序，避免位置有序对交叉操作产生偏见 np.random.shuffle(lines) population.append(lines) return population def selection(population: List[np.ndarray], fitnesses: List[float]) -> List[np.ndarray]: """锦标赛选择。""" selected = [] for _ in range(POP_SIZE): # 随机选择k个个体进行竞争，取适应度最高的 k = 3 contestants_idx = np.random.choice(len(population), k, replace=False) best_idx = max(contestants_idx, key=lambda idx: fitnesses[idx]) selected.append(population[best_idx].copy()) return selected def crossover(parent1: np.ndarray, parent2: np.ndarray) -> Tuple[np.ndarray, np.ndarray]: """模拟二进制交叉。""" child1, child2 = parent1.copy(), parent2.copy() for i in range(len(parent1)): if random.random() < 0.5: # 交叉概率控制 # SBX交叉 u = random.random() if u <= 0.5: beta = (2 * u) ** (1.0 / (1.0 + 1.0)) # 分布指数设为1 else: beta = (1.0 / (2.0 * (1.0 - u))) ** (1.0 / (1.0 + 1.0)) child1[i] = 0.5 * ((1 + beta) * parent1[i] + (1 - beta) * parent2[i]) child2[i] = 0.5 * ((1 - beta) * parent1[i] + (1 + beta) * parent2[i]) # 确保交叉后基因值在合理范围内（对于无效基因-1，特殊处理） if parent1[i] == -1 or parent2[i] == -1: # 如果父代有一个是无效基因，子代有一定概率继承无效 if random.random() < 0.5: child1[i] = -1 if random.random() < 0.5: child2[i] = -1 return child1, child2 def mutation(chromosome: np.ndarray) -> np.ndarray: """高斯变异。对有效基因（非-1）进行小范围扰动。""" mutated = chromosome.copy() for i in range(len(mutated)): if random.random() < PM and mutated[i] != -1: # 高斯变异，标准差设为区域宽度的1/20 sigma = (x_max - x_min) / 20.0 mutated[i] += np.random.normal(0, sigma) # 边界处理 mutated[i] = np.clip(mutated[i], x_min, x_max) # 有小概率将该测线变为无效 if random.random() < 0.05: mutated[i] = -1 return mutated def local_search_by_sa(individual: np.ndarray, current_fitness: float) -> np.ndarray: """用模拟退火对单个优秀个体进行局部精细搜索。""" best_solution = individual.copy() best_fitness = current_fitness current_solution = individual.copy() current_fitness_local = current_fitness T = T0 / 10 # 局部搜索可以用一个较低的初始温度 for _ in range(ITER_PER_TEMP // 5): # 局部搜索迭代次数少一些 # 产生邻域解：随机扰动一条有效测线 new_solution = current_solution.copy() valid_indices = [i for i, val in enumerate(new_solution) if val != -1] if valid_indices: idx = random.choice(valid_indices) sigma = (x_max - x_min) / 100.0 # 更小的扰动 new_solution[idx] += np.random.normal(0, sigma) new_solution[idx] = np.clip(new_solution[idx], x_min, x_max) new_fitness = calculate_fitness(new_solution) # Metropolis准则 delta_f = new_fitness - current_fitness_local if delta_f > 0 or random.random() < np.exp(delta_f / T): current_solution = new_solution current_fitness_local = new_fitness if current_fitness_local > best_fitness: best_solution = current_solution.copy() best_fitness = current_fitness_local T *= T_COOL return best_solution

4.4 主循环与结果输出

def main(): # 初始化 population = initialize_population() best_individual = None best_fitness = -float('inf') history_best_fitness = [] for gen in range(MAX_GEN): # 计算适应度 fitnesses = [calculate_fitness(ind) for ind in population] # 更新当代最优 gen_best_idx = np.argmax(fitnesses) if fitnesses[gen_best_idx] > best_fitness: best_fitness = fitnesses[gen_best_idx] best_individual = population[gen_best_idx].copy() history_best_fitness.append(best_fitness) # 选择 selected = selection(population, fitnesses) # 交叉与变异生成新一代 new_population = [] for i in range(0, POP_SIZE, 2): parent1, parent2 = selected[i], selected[i+1] if random.random() < PC: child1, child2 = crossover(parent1, parent2) else: child1, child2 = parent1.copy(), parent2.copy() child1 = mutation(child1) child2 = mutation(child2) new_population.extend([child1, child2]) # 精英保留：用上一代的最优个体替换新一代的最差个体 worst_idx = np.argmin([calculate_fitness(ind) for ind in new_population]) new_population[worst_idx] = best_individual.copy() population = new_population # 每隔若干代，对精英个体进行局部搜索 if gen % 20 == 0 and best_individual is not None: population[0] = local_search_by_sa(best_individual, best_fitness) # 重新计算并更新全局最优 new_fitness = calculate_fitness(population[0]) if new_fitness > best_fitness: best_fitness = new_fitness best_individual = population[0].copy() # 打印进度 if gen % 10 == 0: positions = decode_individual(best_individual) print(f"Generation {gen:3d} | Best Fitness: {-best_fitness:.2f} | " f"Lines: {len(positions)} | Positions: {np.round(positions, 1)}") # 最终结果 print("\n=== Optimization Finished ===") final_positions = decode_individual(best_individual) final_positions_sorted = sorted(final_positions) print(f"Optimal number of survey lines: {len(final_positions_sorted)}") print(f"Optimal line positions (x-coordinates): {np.round(final_positions_sorted, 2)}") print(f"Total survey length: {len(final_positions_sorted) * Ly:.2f} meters") # 详细验证约束 print("\n=== Constraint Verification ===") # ... (这里可以添加详细的覆盖率和重叠率验证代码) # 验证覆盖率 coverage_violation = 0 for xp in x_check_points: zp = depth(xp, (y_min+y_max)/2) max_dist = beam_width(zp) / 2.0 if not any(abs(xp - xs) <= max_dist for xs in final_positions_sorted): coverage_violation += 1 print(f"Uncovered points: {coverage_violation}/{M}") # 验证重叠率 for i in range(len(final_positions_sorted)-1): x1, x2 = final_positions_sorted[i], final_positions_sorted[i+1] x_mid = (x1 + x2)/2 z_mid = depth(x_mid, (y_min+y_max)/2) W = beam_width(z_mid) D = x2 - x1 overlap = max(0, W - D) eta = overlap / W if W>0 else 0 print(f"Line {i+1} & {i+2}: Distance={D:.1f}m, Width={W:.1f}m, Overlap={overlap:.1f}m, Eta={eta:.3f} ({'OK' if eta_min<=eta<=eta_max else 'VIOLATION'})") if __name__ == "__main__": main()

5. 参数调优与实战心得

代码跑起来只是第一步，要让算法真正发挥效力，关键在调参和细节处理。下面分享我踩过坑后总结的经验。

5.1 遗传算法参数调优指南

参数没有银弹，但有以下调优方向：

• 种群大小POP_SIZE：太小容易早熟，太大计算慢。对于本题这种中等规模问题，50-100是个不错的起点。如果解空间非常复杂（如水深变化剧烈），可以适当增大。
• 交叉概率PC与变异概率PM：经典设置是PC=0.8~0.9,PM=0.01~0.1。交叉主导全局探索，变异提供局部扰动和跳出局部最优的能力。如果发现种群过早收敛（所有个体都一样），就提高PM或降低PC。
• 惩罚系数PENALTY_COVER,PENALTY_OVERLAP：这是最关键也最棘手的参数。原则是：惩罚必须足够大，使得任何违反约束的解的适应度都远低于可行解。通常可以从一个大数开始（如1e6），观察进化过程中违例度是否能够较快降到0。如果一直降不到0，说明惩罚不够大，或者算法探索能力不足。另一个技巧是使用动态惩罚，早期惩罚小一些鼓励探索，后期惩罚增大迫使收敛到可行域。
• 最大测线数N_MAX：设置一个明显大于预估值的数即可。算法会通过合并或惩罚来减少有效数量。

5.2 模拟退火关键参数设置

如果采用模拟退火或局部搜索：

• 初始温度T0：要足够高，使得算法初期能接受大部分劣解。一个经验法则是，让初始状态下，目标函数值差ΔE的接受概率exp(-ΔE/T0)大于0.8。可以运行几次，观察初期接受劣解的比例来调整。
• 冷却系数T_COOL：通常在0.9到0.99之间。越接近1，冷却越慢，搜索越充分，但耗时越长。对于复杂问题，建议用慢速退火（如0.95-0.99）。
• 每个温度的迭代次数ITER_PER_TEMP：要保证在每个温度下，系统能达到“平衡状态”。通常与问题规模有关，可以设为几十到几百。

5.3 常见问题与排查技巧

1. 问题：算法始终找不到可行解（覆盖率或重叠率始终不满足）。

   • 排查：首先检查你的约束计算函数是否正确。用一个极端的解测试，比如测线密集布满整个区域，理论上应该满足全覆盖。如果不满足，说明覆盖检查逻辑有bug。
   • 检查惩罚系数：如果惩罚系数设置过大，可能导致适应度值跨度太大，选择压力过强，种群多样性迅速丧失。可以尝试先减小惩罚系数，让算法能探索包含不可行解的区域，再逐步增大。
   • 检查初始种群：确保初始种群中包含一些“较好”的解。可以手动构造一个简单的可行解（如等间距布设）放入初始种群，作为“种子”。

2. 问题：算法早熟，很快收敛到一个明显不好的解。

   • 提高变异概率PM：这是最直接的方法。
   • 采用自适应变异：变异概率随着种群收敛而增加。例如，当种群中最佳适应度连续多代没有改善时，提高PM。
   • 增加种群多样性：采用小生境技术，惩罚过于相似的个体。或者在选择操作中，不仅看适应度，也考虑个体之间的差异。
   • 使用更强大的交叉算子。

3. 问题：计算速度太慢。

   • 优化适应度计算：这是最大的性能瓶颈。decode_individual和全覆盖检查（遍历所有离散点）是热点。可以考虑：
     • 减少离散点数量M，在优化后期再提高精度。
     • 使用向量化操作代替循环。例如，用numpy的广播机制一次性计算所有离散点到所有测线的距离。
     • 对水深函数depth(x)进行预计算或插值，避免重复调用复杂函数。
   • 调整算法参数：减小种群大小POP_SIZE或进化代数MAX_GEN。

4. 问题：结果不稳定，每次运行得到的最优解差异很大。

   • 这是元启发式算法的固有特点。标准做法是独立运行算法多次（例如30次），然后取这些运行中得到的最好结果作为最终解。在论文中，也应该汇报多次运行的平均结果和标准差，以体现算法的鲁棒性。
   • 可以增加算法的搜索时间（更多代数、更大种群）来提高找到高质量解的稳定性。

5.4 模型与算法的扩展思考

本题的模型还可以进一步深化：

• 更精确的水深模型：题目可能提供离散的水深点数据。你需要进行二维插值（如双线性插值、样条插值）来得到任意点(x,y)的水深。这会显著增加计算量，需要更精细的离散化策略。
• 测线非平行：如果测线可以不平行，问题将升级为更复杂的二维路径规划问题，可能需要使用不同的编码方式（如表示测线起点、角度和长度）和更复杂的交叉变异操作。
• 多目标优化：除了总长度最短，可能还有别的目标，如测量时间最短、能耗最低等。这就变成了多目标优化问题，可以使用NSGA-II、MOEA/D等多目标进化算法，得到一组Pareto最优解供决策者选择。

最后，在数学建模论文中，除了呈现结果，一定要包含清晰的灵敏度分析。比如，分析重叠率要求（eta_min,eta_max）变化对总测线长度的影响；分析水深变化幅度对测线布局的影响。这能极大地提升论文的深度和得分。

这套从问题理解、模型构建、算法实现到调参分析的完整流程，不仅适用于这道赛题，也为你今后解决类似的工程优化问题提供了一个坚实的模板。记住，建模竞赛的核心不是追求绝对的最优解，而是在有限时间内，用清晰的逻辑、合理的模型和有效的求解方法，讲好一个解决问题的“故事”。希望这份超详细的拆解能成为你工具箱里的一件利器。