GA-遗传算法

1. 方法概述

遗传算法（Genetic Algorithm, GA）是一类模拟自然选择与遗传机制的群体优化方法。本项目的核心实现位于 GA-遗传算法/core/ga_calculator.py，面向连续变量单目标优化，支持锦标赛/轮盘赌选择、算术交叉、非均匀变异、精英保留、多次独立运行统计以及上传数据代理优化。

设第 \(i\) 个个体在第 \(t\) 代的染色体向量为

$$ \boldsymbol{x}_i^{(t)}=(x_{i1}^{(t)},x_{i2}^{(t)},\ldots,x_{id}^{(t)})^\top\in\Omega \tag{1} $$

其中 \(d\) 为维度，\(\Omega=[\boldsymbol{l},\boldsymbol{u}]\subset\mathbb{R}^d\) 为连续搜索空间。

2. 问题定义与代理优化

对内置基准函数或上传代理问题，GA 求解的基本形式为

$$ \operatorname*{best}_{\boldsymbol{x}\in\Omega} f(\boldsymbol{x}) \tag{2} $$

其中 best 在最小化模式下表示 \(\min\)，在最大化模式下表示 \(\max\)。

当 problem_mode=upload_surrogate 时，项目使用随机森林回归器建立代理模型。设训练样本为

$$ \mathcal{D}=\{(\boldsymbol{x}^{(n)},y^{(n)})\}_{n=1}^{N_s} \tag{3} $$

对应代理目标函数为

$$ \hat{f}(\boldsymbol{x})=\frac{1}{B}\sum_{b=1}^{B}T_b(\boldsymbol{x}),\qquad B=300 \tag{4} $$

变量边界由训练样本特征极值给定：

$$ l_j=\min_{1\le n\le N_s}x_j^{(n)},\qquad u_j=\max_{1\le n\le N_s}x_j^{(n)} \tag{5} $$

3. 核心数学模型

3.1 初始化

设种群规模为 \(N\)。项目使用均匀随机采样生成初始种群：

$$ \boldsymbol{x}_i^{(0)}=\boldsymbol{l}+\boldsymbol{r}_i\odot(\boldsymbol{u}-\boldsymbol{l}),\qquad \boldsymbol{r}_i\sim U(0,1)^d \tag{6} $$

并计算个体适应度

$$ F_i^{(t)}=f(\boldsymbol{x}_i^{(t)}) \tag{7} $$

3.2 选择算子

项目支持两种选择方式。

3.2.1 轮盘赌选择

对最小化问题，代码先做平移处理

$$ \tilde{F}_i=F_i-\min_j F_j+\varepsilon \tag{8} $$

然后定义权重

$$ w_i=\frac{1}{\tilde{F}_i} \tag{9} $$

选择概率为

$$ P_i=\frac{w_i}{\sum_{j=1}^{N}w_j} \tag{10} $$

对最大化问题，则直接采用平移后的 \(\tilde{F}_i\) 作为轮盘赌权重。

3.2.2 锦标赛选择

若采用 tournament，则对每个父代位置随机抽取 \(k\) 个候选体，选择其中最优个体进入父代集合：

$$ \boldsymbol{x}_{parent}=\operatorname*{best}_{\boldsymbol{x}\in \mathcal{T}_k}\boldsymbol{x} \tag{11} $$

其中 \(\mathcal{T}_k\) 表示由 \(k\) 个随机样本组成的锦标赛集合。

3.3 精英保留

每一代开始时，项目先复制前 \(E\) 个精英个体：

$$ \mathcal{E}^{(t)}=\{\boldsymbol{x}_{(1)}^{(t)},\boldsymbol{x}_{(2)}^{(t)},\ldots,\boldsymbol{x}_{(E)}^{(t)}\} \tag{12} $$

其中 \((1),(2),\ldots,(E)\) 表示按适应度排序后的前 \(E\) 名个体。后续新一代生成完成后，这些精英会重新插入并替换最差个体。

3.4 算术交叉

项目对相邻两个父代个体按概率 \(p_c\) 进行交叉。若在维度 \(q\) 上触发交叉，并采样混合系数 \(\beta\sim U(0,1)\)，则两个子代在该维度上的更新为

$$ c_{1q}=\beta p_{2q}+(1-\beta)p_{1q} \tag{13} $$

$$ c_{2q}=\beta p_{1q}+(1-\beta)p_{2q} \tag{14} $$

其余维度保持不变。交叉后对子代执行边界截断。

3.5 非均匀变异

项目采用非均匀变异。对第 \(t\) 代的个体，若在某维 \(q\) 触发变异，记当前值为 \(v\)，则先定义到上下界的距离

$$ \Delta_1=v-l_q,\qquad \Delta_2=u_q-v \tag{15} $$

并构造代数相关的幂指数

$$ \psi^{(t)}=\left(1-\frac{t}{T}\right)^2 \tag{16} $$

其中 \(T\) 为最大代数。若随机决定向上变异，则

$$ v' = v + \Delta_2\left(1-r^{\psi^{(t)}}\right) \tag{17} $$

若向下变异，则

$$ v' = v - \Delta_1\left(1-r^{\psi^{(t)}}\right) \tag{18} $$

其中 \(r\sim U(0,1)\)。该机制使得前期变异幅度较大、后期逐渐收缩。

3.6 精英回插与最优记录

子代评估完成后，项目将最差的 \(E\) 个个体替换为精英集合：

$$ \mathcal{P}^{(t+1)} \leftarrow \left(\mathcal{P}^{(t+1)}\backslash \mathcal{W}^{(t+1)}\right)\cup \mathcal{E}^{(t)} \tag{19} $$

其中 \(\mathcal{W}^{(t+1)}\) 表示当前代最差的 \(E\) 个个体集合。随后更新本代最优值

$$ g^{(t)}=\operatorname*{best}_{1\le i\le N}F_i^{(t)} \tag{20} $$

以及种群平均适应度

$$ \bar{F}^{(t)}=\frac{1}{N}\sum_{i=1}^{N}F_i^{(t)} \tag{21} $$

4. 算法流程

根据 GACalculator._run_single，本项目的 GA 流程为：

1. 初始化种群并计算适应度。
2. 保留当前代的精英个体。
3. 按锦标赛或轮盘赌方式选择父代。
4. 对父代两两执行算术交叉。
5. 对子代执行非均匀变异。
6. 重新评估新种群适应度。
7. 将精英重新插入新种群，替换最差个体。
8. 更新代际最优值、全局最优值、均值曲线和最优轨迹。
9. 若设置 n_runs>1，则对多次独立运行的曲线和最终最优值进行汇总。

5. 关键参数说明

• pop_size：种群规模 \(N\)。
• max_gen：最大代数 \(T\)。
• crossover_rate：交叉概率 \(p_c\)。
• mutation_rate：变异概率 \(p_m\)。
• selection_method：选择方式，可选 tournament 或 roulette。
• tournament_k：锦标赛规模 \(k\)。
• elitism：精英保留数量 \(E\)。
• seed：随机种子。
• n_runs：独立重复运行次数。

6. 评价指标与输出结果解释

设共有 \(R\) 次独立运行，第 \(r\) 次运行的最终最优值记为 \(b_r\)，则项目统计：

$$ b_{\mathrm{best}}= \begin{cases} \min_{1\le r\le R}b_r, & \text{最小化}\\ \max_{1\le r\le R}b_r, & \text{最大化} \end{cases} \tag{22} $$

$$ \bar{b}=\frac{1}{R}\sum_{r=1}^{R}b_r \tag{23} $$

同时，对所有运行的最佳曲线与均值曲线分别做逐代聚合。实际导出的主要工作表包括：

• 参数、边界设置：问题配置与逐维边界；
• 运行汇总：每次运行的 best_fitness、耗时等统计；
• 稳定性统计：跨运行的均值、标准差、最小值和最大值；
• 收敛曲线：逐代聚合后的最佳曲线和均值曲线；
• 最优轨迹：最佳运行的最优位置轨迹；
• 最佳解、最佳适应度：最终最优解向量与对应最优值；
• 结果解读、图表清单：结果说明和图表路径。

上传代理模式下还会追加 UploadedBounds、UploadedData、SurrogateMetrics，用于记录样本边界明细、数据预览与代理模型误差。

论文结果部分建议先以 运行汇总 与 稳定性统计 作为主表汇报多次独立运行表现，再结合 收敛曲线 和 最优轨迹 解释代表性搜索过程。最佳解 与 最佳适应度 在正文中应分开引用，分别承担“最优决策变量表”和“最优目标值表”的作用；上传代理模式下还应附上 SurrogateMetrics。

7. 论文写作模板

可在论文方法部分表述为：

“本文采用遗传算法对连续变量优化问题进行求解。算法首先在给定边界内随机初始化种群，并通过锦标赛或轮盘赌方式选择父代个体；随后在单个维度上执行算术交叉生成子代，并采用与迭代代数相关的非均匀变异机制调节搜索步长。为避免优良个体在进化过程中丢失，本文在每代中保留精英个体，并在新种群生成后回插替换最差个体。对于数据驱动问题，则先构造随机森林代理目标函数，再使用 GA 在样本边界内进行优化。”

7.1 结果部分补充模板

若需把实验结果直接写入论文结果部分，可进一步表述为：

“表X给出了算法在当前问题上的最优目标值、平均最优值和标准差（如有多次独立运行），图X展示了收敛曲线变化。结果表明，该算法在迭代前期能够快速逼近优势区域，并在后期逐步趋于稳定，最终获得最优解 \(\boldsymbol{x}^*\) 及其对应目标值 \(f(\boldsymbol{x}^*)\)。对于上传代理优化场景，结合代理模型误差指标可认为该最优结果具有一定的数据驱动解释性。”

7.2 写作替换提示

为便于直接落稿，正文撰写时可将结果文件中的字段替换为以下论文措辞：

• best_fitness 或结果汇总表中的最优值，可写为“最优目标函数值”或“最优适应度值”；
• BestSolution、BestPosition、Best_Solution、最优解 等工作表，可统一写为“最优决策变量组合 \(\boldsymbol{x}^*\)”；
• Convergence、收敛曲线 等图表，可统一写为“算法收敛曲线图”；
• SurrogateMetrics 可写为“代理模型训练误差与拟合优度指标”，如 RMSE、MAE、\(R^2\)。

7.3 可直接替换的论文结果段落

若需进一步直接落稿，可按以下模板替换其中的表号、图号和数值：

“由表X可知，该算法在[问题名称]上的最优目标值为 [best_fitness]。若进行了多次独立运行，则其平均最优值与标准差分别为 [mean_best_fitness] 和 [std_best_fitness]。由图X所示收敛曲线可见，算法在迭代前期快速逼近优势区域，后期逐渐趋于平稳，表现出较好的收敛性。最终得到的最优决策变量组合为 \(\boldsymbol{x}^*=[x_1^*,x_2^*,\ldots,x_d^*]\)。若采用上传代理优化模式，则结合 RMSE、MAE 和 \(R^2\) 等代理误差指标，可认为该优化结果具有一定的数据驱动可信度。”

8. 实现说明与注意事项

• 本实现适用于连续变量单目标优化，不是二进制编码 GA。
• 交叉算子是“单维算术交叉”，不是多点交叉或模拟二进制交叉（SBX）。
• 变异算子是随代数递减的非均匀变异，因此后期搜索会更偏向局部精修。
• 精英回插会改变当代原始子代分布，这对保持最优个体稳定性很重要。
• 上传代理优化的最优解依赖随机森林代理精度，应结合训练误差一起解读。

9. 单篇终审补充

9.1 图题与表题对齐建议

• 运行汇总 表可写为：表X GA 各次运行结果汇总。
• 稳定性统计 表可写为：表X GA 多次运行稳定性统计。
• 收敛曲线 表可写为：表X GA 聚合收敛曲线。
• 最优轨迹 表可写为：表X GA 最佳运行的最优位置轨迹。
• 最佳解 表可写为：表X GA 求得的最优解向量。
• 最佳适应度 表可写为：表X GA 最终最优目标值。

9.2 终审说明

• 这篇文档已经适合落稿，终稿时应把 最佳解 与 最佳适应度 分开引用，避免把向量表和标量结果表混成一张表。
• 若引用代理优化结果，SurrogateMetrics 应与 运行汇总 同时出现，不能只报最优值。

9.3 全量强化补充

本次全量强化绑定的真实上传验证目录为 具体的算法3/优化与多目标/GA-遗传算法/results/manual_upload_verify_20260328/GA-遗传算法分析结果_20260329_153544。主结果文件为 GA-遗传算法分析结果_20260329_153544.xlsx，实际工作表为 参数、边界设置、运行汇总、稳定性统计、收敛曲线、最优轨迹、最佳解、最佳适应度、结果解读、图表清单、UploadedBounds、UploadedData、SurrogateMetrics。

当前真实图文件为 charts/convergence.png 与 charts/best_box.png。因此正文若讨论多次运行稳定性，可直接引用 稳定性统计 和 best_box.png，不必再虚写不存在的额外分布图。

复现脚本为 repro_ga.py，输入口径为 problem_file = 'repro_inputs/ga_sample.xlsx'，运行参数中显式包含 problem_mode = 'upload_surrogate'、target_column = 'f_sphere'、objective_direction = 'min' 和 n_runs = 2。因此这篇文档应按“上传代理模式下、含两次独立运行统计的 GA 复现”来描述。

10. 软件实现核查补充（2026-07）

本篇对应的软件源码目录是 具体的算法3/优化与多目标/GA-遗传算法。软件实现支持内置基准函数和上传数据代理优化；上传模式会把输入文件复制到 repro_inputs，并通过随机森林代理模型将用户数据转成 GA 可搜索目标。文档中的选择、交叉、变异、种群迭代和适应度函数公式可以保留，但需要说明当前软件是连续变量单目标优化实现。

当前较新的代表性目录包括 results/GA-遗传算法分析结果_20260517_104312-优化模式、results/GA-遗传算法分析结果_20260517_104325-上传数据代理优化 和 results/GA-遗传算法分析结果_20260517_104347-上传数据代理优化。主工作簿包含 结果说明、字段说明、Summary、Problem、GA_Params、Bounds、Run_Summary、History_Mean、History_All、Best_Solution、Charts；上传模式额外包含 UploadedProblem、UploadedData、SurrogateMetrics。这与旧文中中文表名较多的历史目录不同，当前交付文档应按新版统一表结构解释。

当前稳定图表为 charts/GA_convergence_时间戳.png，部分历史 smoke 目录中存在 GA_best_box_时间戳.png，但较新主目录不应写成必有箱线图。复现代码位于 复现代码/优化模式/ 或 复现代码/上传数据代理优化/，上传模式输入副本为 repro_inputs/ga_sample.xlsx，复现结果进入 repro_outputs/。若正文讨论多次运行稳定性，应先确认当前结果目录实际是否有箱线图；若没有，应只引用 Run_Summary、History_Mean 和 History_All。