CoDE 与 L-SHADE：公式、代码与原理详解

阅读说明

当前目录包含论文 PDF 和比较 PPT，没有 CoDE、L-SHADE 的原作者源码。因此，本文依据论文整理公式，并给出与公式对应的 Python/NumPy 核心代码。

代码性质：教学用核心片段及结构伪代码，不是从目录中提取的原作者源码，也不是已测试的完整可运行实现。 片段中的 X、fitness、objective、lower、upper 等变量由上下文提供。

主要参考文件：

• CoDE 论文中文译文：PDF 第 3～5 页，策略池、参数池和候选解生成。
• L-SHADE 论文：PDF 第 2～3 页，公式（1）～（10）及算法 1、2；PDF 第 5 页，参数设置。

本文中的公式采用 LaTeX 数学语法，需要支持数学公式的 Markdown 阅读器渲染。

一、共同基础：差分进化 DE

两种算法都用于求解有界连续优化问题。以下统一讨论最小化：

$ \min_{\mathbf{x}} f(\mathbf{x}),\qquad l_j\le x_j\le h_j,\quad j=1,\ldots,D. $

目标是在变量允许的范围内，找到让目标函数尽可能小的一组参数。算法维护一群候选解，反复生成新解、评价优劣并选择下一代，不需要计算目标函数的梯度。

1. 符号与代码变量

代码约定：

import numpy as np

rng = np.random.default_rng(42)

# X.shape == (N, D)
# X[i] 表示第 i 个候选解
# lower、upper 为长度为 D 的上下界数组
# fitness[i] == objective(X[i])

2. 种群初始化

公式：

$ x_{i,j,0}=l_j+r_{i,j}(h_j-l_j),\qquad r_{i,j}\sim U(0,1). $

对应代码：

X = lower + rng.random((N, D)) * (upper - lower)
fitness = np.array([objective(x) for x in X])
nfe = N

含义：每个变量在对应上下界之间均匀随机取值。

例如 $l_j=-10$、$h_j=10$、$r_{i,j}=0.7$，则：

$ x_{i,j,0}=-10+0.7\times20=4. $

初始化评价也要计入 NFE。

3. 差分向量

公式：

$ \mathbf{d}=\mathbf{x}{r_2,G}-\mathbf{x}{r_3,G}. $

对应代码：

difference = X[r2] - X[r3]

例如 $(5,3)-(2,1)=(3,2)$。这个差值提供一个搜索方向，乘以 $F$ 后成为差分扰动。

4. 二项式交叉

公式：

$ u_{i,j,G}=\begin{cases} v_{i,j,G}, & r_j\le CR_i\ \text{或}\ j=j_{\mathrm{rand}},\ x_{i,j,G}, & \text{其他情况}, \end{cases} \qquad r_j\sim U(0,1). $

对应代码：

def binomial_crossover(x, v, CR, rng):
    D = len(x)
    mask = rng.random(D) <= CR
    mask[rng.integers(D)] = True
    return np.where(mask, v, x)

解释：

• mask 为真：取变异向量对应分量。
• mask 为假：保留父代对应分量。
• 强制随机一维为真，确保至少一维取自变异向量。

注意：取自变异向量不保证数值一定发生变化，因为该分量可能恰好与父代相同。

取自变异向量的维数期望为：

$ 1+(D-1)CR. $

因此，$CR=0$ 也不是完全不交叉，而是强制一维取自变异向量。

5. 贪婪选择

公式：

$ \mathbf{x}{i,G+1}=\begin{cases} \mathbf{u}{i,G}, & f(\mathbf{u}{i,G})\le f(\mathbf{x}{i,G}),\ \mathbf{x}_{i,G}, & \text{其他情况}. \end{cases} $

对应代码：

if trial_fitness <= fitness[i]:
    next_X[i] = u
    next_fitness[i] = trial_fitness

含义：新解不差于父代，就允许替换。

在 L-SHADE 中还要区分：

• 小于等于：允许替换。
• 严格小于：才作为成功样本更新参数记忆，并把被替换父代加入存档。

二、CoDE：三种策略与参数池的复合

CoDE 的正式名称是 Composite Differential Evolution，复合差分进化。

核心流程：对每个父代，使用三种策略分别生成三个候选解；每种策略随机搭配参数；从三个候选解中选最好的，再与父代比较。

1. 参数池

公式：

$ \mathcal{P}={(1.0,0.1),(1.0,0.9),(0.8,0.2)}, $

其中每一对表示 $(F,CR)$。

对应代码：

parameter_pool = np.array([
    [1.0, 0.1],
    [1.0, 0.9],
    [0.8, 0.2],
])

F, CR = parameter_pool[rng.integers(len(parameter_pool))]

每种策略分别随机选一组参数，允许重复选择。不是三种策略与三组参数固定一一对应，也不是每个父代随机选一种策略。

基本 CoDE 不根据历史成功率改变参数组的抽取概率。

2. 策略一：rand/1/bin

变异公式：

$ \mathbf{v}{i,G}^{(1)}=\mathbf{x}{r_1,G}+F(\mathbf{x}{r_2,G}-\mathbf{x}{r_3,G}). $

随后执行二项式交叉：

$ \mathbf{u}{i,G}^{(1)}=\operatorname{BinCross}(\mathbf{x}{i,G},\mathbf{v}_{i,G}^{(1)},CR). $

对应代码：

r1, r2, r3 = rng.choice(
    [k for k in range(N) if k != i],
    size=3,
    replace=False,
)

F, CR = parameter_pool[rng.integers(3)]
v1 = X[r1] + F * (X[r2] - X[r3])
u1 = binomial_crossover(X[i], v1, CR, rng)

名称含义：

• rand：随机选择基向量。
• 1：使用一个差分向量。
• bin：二项式交叉。

作用：提供不直接依赖最优个体引导的随机探索。

3. 策略二：rand/2/bin

CoDE 使用的版本，其第一项差分系数为随机数，不是两项都乘同一个 F。

公式：

$ \mathbf{v}{i,G}^{(2)}=\mathbf{x}{r_1,G}+\alpha(\mathbf{x}{r_2,G}-\mathbf{x}{r_3,G})+F(\mathbf{x}{r_4,G}-\mathbf{x}{r_5,G}), \qquad \alpha\sim U(0,1). $

随后执行二项式交叉：

$ \mathbf{u}{i,G}^{(2)}=\operatorname{BinCross}(\mathbf{x}{i,G},\mathbf{v}_{i,G}^{(2)},CR). $

对应代码：

r1, r2, r3, r4, r5 = rng.choice(
    [k for k in range(N) if k != i],
    size=5,
    replace=False,
)

F, CR = parameter_pool[rng.integers(3)]
alpha = rng.random()

v2 = (
    X[r1]
    + alpha * (X[r2] - X[r3])
    + F * (X[r4] - X[r5])
)
u2 = binomial_crossover(X[i], v2, CR, rng)

含义：随机起点加两组差分扰动，产生更丰富的候选方向。

这里 alpha 是该候选向量使用的随机标量，不是每一维分别采样一个系数。上述排除父代、无放回选取五个索引的实现需要种群至少有六个个体。

4. 策略三：current-to-rand/1

公式：

$ \mathbf{u}{i,G}^{(3)}=\mathbf{x}{i,G}+K(\mathbf{x}{r_1,G}-\mathbf{x}{i,G})+F(\mathbf{x}{r_2,G}-\mathbf{x}{r_3,G}), \qquad K\sim U(0,1). $

对应代码：

r1, r2, r3 = rng.choice(
    [k for k in range(N) if k != i],
    size=3,
    replace=False,
)

F, _ = parameter_pool[rng.integers(3)]
K = rng.random()

u3 = (
    X[i]
    + K * (X[r1] - X[i])
    + F * (X[r2] - X[r3])
)

三部分含义：

1. $\mathbf{x}_{i,G}$：从当前父代出发。
2. $K(\mathbf{x}{r_1,G}-\mathbf{x}{i,G})$：向随机个体靠近。
3. $F(\mathbf{x}{r_2,G}-\mathbf{x}{r_3,G})$：增加差分扰动。

这一公式直接产生试验向量，不再额外执行二项式交叉。因此，抽取参数组中的 CR 在该策略中不起作用。

5. 三候选竞争与父代选择

先选最好的候选解：

$ s^=\arg\min_{s\in{1,2,3}}f(\mathbf{u}{i,G}^{(s)}), \qquad \mathbf{u}{i,G}^{}=\mathbf{u}_{i,G}^{(s^*)}. $

再与父代比较：

$ \mathbf{x}{i,G+1}=\begin{cases} \mathbf{u}{i,G}^{}, & f(\mathbf{u}_{i,G}^{})\le f(\mathbf{x}{i,G}),\ \mathbf{x}{i,G}, & \text{其他情况}. \end{cases} $

对应代码：

trials = [u1, u2, u3]

# 假定三个候选解已完成边界修复
trial_values = np.array([objective(u) for u in trials])
best_id = np.argmin(trial_values)

if trial_values[best_id] <= fitness[i]:
    next_X[i] = trials[best_id]
    next_fitness[i] = trial_values[best_id]

nfe += 3

例如父代目标值为 10，三个候选值为 8、12、6，则先取 6，再因其优于 10 而替换父代。

边界修复是完整实现中必须明确的环节；本文没有将某个自行选择的修复方法冒充为已核实的 CoDE 原作者实现。不同修复方式可能影响复现实验结果。

6. CoDE 主流程伪代码

初始化种群 X 和目标值 fitness
nfe = N

当评价预算足够时：
    next_X = X 的副本
    next_fitness = fitness 的副本

    对每个父代 i：
        三种策略分别随机抽取参数
        用 rand/1/bin 生成 u1
        用 rand/2/bin 生成 u2
        用 current-to-rand/1 生成 u3

        对三个候选解进行边界修复
        评价三个候选解
        从中选出目标值最小的候选解
        若其不差于父代，将其写入 next_X
        nfe += 3

    X = next_X
    fitness = next_fitness

使用下一代缓冲区，可避免在同一代生成候选解时无意混用已经更新的个体。

完整一代通常消耗 $3N$ 次目标函数评价。末代应明确预算处理，不能无意超出最大评价次数。

三、L-SHADE：成功历史自适应与线性缩群

核心关系：

$ \text{L-SHADE}=\text{SHADE 1.1}+\text{线性种群规模缩减（LPSR）}. $

主要机制：

1. 从历史记忆生成 F、CR。
2. 用 current-to-pbest/1/bin 产生候选解。
3. 用外部存档维持多样性。
4. 用严格改善的成功参数更新历史记忆。
5. 随评价预算消耗逐渐减小种群。

1. 历史记忆初始化

公式：

$ M_{F,k}=0.5,\qquad M_{CR,k}=0.5,\qquad k=1,\ldots,H. $

对应代码：

M_F = np.full(H, 0.5)
M_CR = np.full(H, 0.5)
memory_index = 0
archive = np.empty((0, D))

记忆保存的是成功参数汇总形成的取值中心，不是历史最优解，也不是每个个体永久绑定的参数。

2. 生成 CR：论文式（1）

每个个体随机选一个记忆槽：

$ r_i\sim U{1,\ldots,H}. $

交叉率：

$ CR_i=\begin{cases} 0, & M_{CR,r_i}=\bot,\ \mathcal{N}(M_{CR,r_i},0.1^2), & \text{其他情况}. \end{cases} $

采样后截断到 $[0,1]$。其中 0.1 是正态分布的标准差，$\bot$ 是特殊终止标记。

对应代码，用 np.nan 表示终止标记：

r = rng.integers(H)

if np.isnan(M_CR[r]):
    CR = 0.0
else:
    CR = np.clip(rng.normal(M_CR[r], 0.1), 0.0, 1.0)

例如记忆值为 0.7，后续就倾向尝试 0.7 附近的 CR，而不是固定使用 0.7。

3. 生成 F：论文式（2）

公式：

$ F_i\sim\operatorname{Cauchy}(M_{F,r_i},0.1). $

处理规则：

• 若 $F_i\le0$，重新采样。
• 若 $F_i>1$，截断为 1。

对应代码：

F = M_F[r] + 0.1 * rng.standard_cauchy()
while F <= 0:
    F = M_F[r] + 0.1 * rng.standard_cauchy()
F = min(F, 1.0)

柯西分布重尾，保留产生偏离历史中心的采样值的机会。最终 F 仍按规则限制在有效范围内。

不能把非正的 F 直接截断为 0 来替代重新采样。

4. current-to-pbest/1 变异：论文式（3）

公式：

$ \mathbf{v}{i,G}=\mathbf{x}{i,G}+F_i(\mathbf{x}{pbest,G}-\mathbf{x}{i,G})+F_i(\mathbf{x}{r_1,G}-\widetilde{\mathbf{x}}{r_2,G}). $

其中：

• p-best 从当前种群前 p 比例的较优个体中随机选。
• r1 从当前种群选，且不等于 i。
• 带波浪号的 r2 个体从种群与存档并集 $P_G\cup A_G$ 中选。
• r2 若对应当前种群个体，不能与 i、r1 冲突。

对应代码：

r1 = rng.choice([j for j in range(N) if j != i])

# 并集前 N 行是当前种群，后面是存档
union = np.vstack([X, archive])
allowed_r2 = [
    j for j in range(len(union))
    if j != i and j != r1
]
r2 = rng.choice(allowed_r2)

v = (
    X[i]
    + F * (pbest - X[i])
    + F * (X[r1] - union[r2])
)

含义：从当前解出发，向较优解靠近，再叠加差分扰动。

5. p-best 的选择

将当前种群按目标值从小到大排序，从前约 $pN_G$ 个个体中随机选择一个。

下面使用“最近整数且至少取两个”的实现约定：

rank = np.argsort(fitness)
p_num = max(2, int(np.floor(p * N + 0.5)))
p_num = min(p_num, N)
pbest_id = rng.choice(rank[:p_num])
pbest = X[pbest_id]

例如 N=100、p=0.1，从排名前约 10 个个体中随机选一个。

• p 小：选择范围集中，更贪婪。
• p 大：选择范围更宽。

p-best 不是每次都取全种群唯一最优个体。 复现时还应明确 pN 的整数化规则。

6. 边界修复：论文式（4）

公式：

$ v_{i,j,G}=\begin{cases} (l_j+x_{i,j,G})/2, & v_{i,j,G}<l_j,\ (h_j+x_{i,j,G})/2, & v_{i,j,G}>h_j,\ v_{i,j,G}, & \text{其他情况}. \end{cases} $

对应代码：

v = np.where(v < lower, (lower + X[i]) / 2.0, v)
v = np.where(v > upper, (upper + X[i]) / 2.0, v)

例如父代某维为 6、范围为 [0,10]、变异结果为 13，则修复为 $(10+6)/2=8$，不是简单截断到 10。

修复变异向量后，再进行二项式交叉。

7. 交叉与选择：论文式（5）、（6）

对应共同基础中的公式：

u = binomial_crossover(X[i], v, CR, rng)
trial_fitness = objective(u)

if trial_fitness <= fitness[i]:
    next_X[i] = u
    next_fitness[i] = trial_fitness

再次强调：允许等值替换，但只有严格改善才更新成功统计和存档。

8. 外部存档

严格改善时：

$ f(\mathbf{u}{i,G})<f(\mathbf{x}{i,G}) \quad\Longrightarrow\quad A\leftarrow A\cup{\mathbf{x}_{i,G}}. $

对应代码：

if trial_fitness < fitness[i]:
    archive = np.vstack([archive, X[i].copy()])

超容量时随机删除：

if len(archive) > archive_capacity:
    keep = rng.choice(
        len(archive), size=archive_capacity, replace=False
    )
    archive = archive[keep]

存档保存被更优子代替换的旧父代。虽然它们的目标值相对较差，但仍能提供有价值的差分方向。

存档不是历史最优解集合。

9. 成功参数与改善量

成功集合：

$ S_F={F_k\mid f(\mathbf{u}_k)<f(\mathbf{x}_k)}, $

$ S_{CR}={CR_k\mid f(\mathbf{u}_k)<f(\mathbf{x}_k)}. $

改善量，对成功样本有：

$ \Delta f_k=f(\mathbf{x}_k)-f(\mathbf{u}_k)>0. $

它等价于论文式（9）在成功样本上的绝对差值。

对应代码：

successful_F = []
successful_CR = []
improvements = []

# 在选择过程中
if trial_fitness < fitness[i]:
    successful_F.append(F)
    successful_CR.append(CR)
    improvements.append(fitness[i] - trial_fitness)

改善量用于区分不同成功参数的贡献大小。

10. 成功权重：论文式（8）

公式：

$ w_k=\frac{\Delta f_k}{\sum_{\ell=1}^{|S|}\Delta f_\ell}. $

对应代码：

delta = np.asarray(improvements)
weights = delta / delta.sum()

例如改善量为 2、8，则权重为 0.2、0.8。

11. 加权 Lehmer 均值：论文式（7）

公式：

$ \operatorname{mean}{WL}(S)= \frac{\sum{k=1}^{|S|}w_kS_k^2}{\sum_{k=1}^{|S|}w_kS_k}. $

对应代码：

def weighted_lehmer(values, weights):
    values = np.asarray(values)
    return (
        np.sum(weights * values**2)
        / np.sum(weights * values)
    )

对于非负样本且分母为正，Lehmer 均值相比相同权重的算术平均更偏向较大样本。

例如成功 F 为 0.4、0.8，权重为 0.2、0.8：

$ \operatorname{mean}_{WL}(S_F)= \frac{0.2(0.4)^2+0.8(0.8)^2}{0.2(0.4)+0.8(0.8)} =\frac{0.544}{0.72}\approx0.756. $

12. 历史记忆更新与 CR 终止标记

当本代存在成功样本时：

$ M_{F,k}\leftarrow\operatorname{mean}_{WL}(S_F). $

对于 CR：

$ M_{CR,k}\leftarrow\begin{cases} \bot, & M_{CR,k}=\bot\ \text{或}\ \max(S_{CR})=0,\ \operatorname{mean}{WL}(S{CR}), & \text{其他情况}. \end{cases} $

对应代码：

if successful_F:
    weights = np.asarray(improvements)
    weights = weights / weights.sum()

    M_F[memory_index] = weighted_lehmer(
        successful_F, weights
    )

    if (
        np.isnan(M_CR[memory_index])
        or max(successful_CR) == 0.0
    ):
        M_CR[memory_index] = np.nan
    else:
        M_CR[memory_index] = weighted_lehmer(
            successful_CR, weights
        )

    memory_index = (memory_index + 1) % H

若本代没有严格改善，则不改记忆，也不移动写入指针。

重要细节：

• 你这篇论文基于 SHADE 1.1，F 和非终止状态的 CR 都用加权 Lehmer 均值。
• 若所有成功 CR 都为 0，不能直接计算 0/0，应写入终止标记。
• 某个 CR 记忆槽一旦成为终止状态，后续保持该状态。
• 只有抽中该槽的个体才令 CR=0，不是整个种群都被锁定为 0。

13. 线性种群规模缩减：论文式（10）

公式：

$ N_{G+1}=\operatorname{round}\left[ N_{\mathrm{init}}+ (N_{\min}-N_{\mathrm{init}})\frac{NFE}{MAX_NFE} \right]. $

通常最小规模为：

$ N_{\min}=4. $

对应代码：

progress = nfe / max_nfe
target_size = int(np.floor(
    N_init + (N_min - N_init) * progress + 0.5
))
target_size = max(N_min, min(len(X), target_size))

if len(X) > target_size:
    keep = np.argsort(fitness)[:target_size]
    X = X[keep]
    fitness = fitness[keep]

这里用 floor(value + 0.5) 明确正数的最近整数处理，避免不同语言的 round 半整数规则产生歧义。

例：初始 100 个、最少 4 个。

含义：前期用较大种群探索，后期用较小种群集中搜索。

线性是相对于评价次数，不是代数。 每代消耗的评价次数随种群变化，因此不能直接按代数等步长缩群。

论文伪代码注意事项：当前 PDF 的算法 2 第 22 行显示为 $N_G<N_{G+1}$，与删除 $N_G-N_{G+1}$ 个个体的操作和正文相矛盾。实现应在 $N_{G+1}<N_G$ 时执行缩群。

14. 存档容量同步缩减

关系：

$ A_{\max,G}\approx\operatorname{round}(r_{\mathrm{arc}}N_G). $

对应代码：

archive_capacity = int(np.floor(
    archive_ratio * len(X) + 0.5
))

if len(archive) > archive_capacity:
    keep = rng.choice(
        len(archive), size=archive_capacity, replace=False
    )
    archive = archive[keep]

种群缩减删除最差个体；存档超容量随机删除。不能混为同一种删除规则。

15. 论文中的参数设置

PDF 第 5 页表 II：

因此按这份论文的调优设置：

$ N_{\mathrm{init}}=\operatorname{round}(18D),\qquad A_{\max,G}\approx\operatorname{round}(2.6N_G), $

$ p=0.11,\qquad H=6,\qquad N_{\min}=4. $

这些是论文实验配置，不是所有问题都必须采用的算法定义常量。

16. L-SHADE 主流程伪代码

初始化种群 X、目标值 fitness
初始化 M_F 和 M_CR，各槽设为 0.5
初始化空存档 archive 和记忆写入位置
nfe = N_init

当 nfe < max_nfe 时：
    清空本代成功参数与改善量集合

    基于本代种群及存档，对每个父代：
        随机抽取记忆槽 r
        生成 CR 和 F
        随机选 p-best、r1、r2
        执行 current-to-pbest/1 变异
        修复变异向量边界
        执行二项式交叉
        保存候选解及其 F、CR

    评价本代预算允许的候选解：
        nfe += 1
        若严格优于父代：
            将旧父代加入存档
            记录 F、CR 和改善量
        若不差于父代：
            接受候选解

    随机裁剪超容量存档
    用本代成功样本更新一个记忆槽
    按 nfe / max_nfe 计算新种群规模
    删除种群中最差的多余个体
    按新种群规模同步缩减存档容量

完整程序必须处理末代预算不足、输入合法性、目标函数异常等工程细节。

四、两种算法的关键对照

最容易混淆的两个公式

CoDE 的 current-to-rand/1：

$ \mathbf{u}i=\mathbf{x}i+K(\mathbf{x}{r_1}-\mathbf{x}i)+F(\mathbf{x}{r_2}-\mathbf{x}{r_3}). $

• 向随机个体靠近。
• 引导项系数为随机 K。
• 直接产生试验向量，不再做二项式交叉。

L-SHADE 的 current-to-pbest/1：

$ \mathbf{v}i=\mathbf{x}i+F_i(\mathbf{x}{pbest}-\mathbf{x}i)+F_i(\mathbf{x}{r_1}-\widetilde{\mathbf{x}}{r_2}). $

• 向随机选择的较优个体靠近。
• 两项使用同一个个体参数 F。
• 第二差分来源可以包含存档。
• 产生变异向量后还需要修复边界并做二项式交叉。

五、实现和答辩时最应记住的要点

1. CoDE 每个父代产生三个候选，不是随机选一种策略只产生一个。
2. CoDE 的 rand/2/bin 第一差分系数是随机数，第二项才是参数 F。
3. CoDE 的 current-to-rand/1 不额外执行二项式交叉，CR 不参与该策略计算。
4. L-SHADE 的历史记忆保存成功参数的汇总值，不是历史最优解。
5. 按当前论文的 SHADE 1.1 版本，F 和非终止状态的 CR 都用加权 Lehmer 均值。
6. L-SHADE 允许等值替换，但只有严格改善才记录成功参数和加入存档。
7. L-SHADE 的存档保存被更优子代替换的父代，不是最优解排行榜。
8. L-SHADE 按目标函数评价次数线性缩群，不是按代数线性缩群。
9. 种群缩减删最差个体，存档缩减随机删个体。
10. 公平比较两种算法要控制总评价次数、问题维数、边界、目标函数和多次独立运行配置，不能只比较相同代数。

一句话总结：CoDE 是“同时用三种办法试，选最好的”；L-SHADE 是“记住有效参数，向较优解搜索，并逐步集中种群”。