差分进化

差分进化（differential evolution，DE）通过种群个体之间的差向量生成连续优化候选，再经交叉和选择更新种群。它不使用目标导数。不同变异策略和更新次序构成不同版本；下面固定讨论一代结束后统一更新的 DE/rand/1/bin。

差向量产生怎样的候选

设n维目标 $f$ 在矩形边界内取有限值，当前种群为 $x_1,\dots ,x_N\in {ℝ}^n$，$N\ge 4$。对目标个体 $x_i$，从其他个体中取三个互异索引 $r_1,r_2,r_3$，变异为 $$v_i=x_{r_1}+F(x_{r_2}-x_{r_3}),F>0.$$ rand表示基点随机选，1表示使用一个差向量；F控制差向量倍数。该公式产生的点可能越界，需要明确修复规则。

例如二维种群为 $(-2,-2),(0,0),(1,1),(3,-1)$，目标为 $f(x,y)=(x-1/2{)}^2+(y+1/2{)}^2$。更新第一个个体，选择基点 $(0,0)$、差向量 $(3,-1)-(1,1)=(2,-2)$、$F=1/2$，得到 $v=(1,-1)$。其代价为二分之一，低于原个体的8.5。

虚线为父个体差向量，实线从零基点出发得到变异点。

二项交叉和选择

取交叉概率 $CR\in [0,1]$，每个坐标有独立均匀数 $U_j$，并随机指定一个强制坐标 $j_{\ast }\in \{1,\dots ,n\}$。定义 $$u_{i,j}=\{\begin{array}{cc}{v}_{i,j},& U_j<CR\text{ 或 }j=j_{\ast },\\ x_{i,j},& \text{其他情形}.\end{array}$$ 强制坐标保证至少一次从变异向量取分量，但如果相应数值恰好相同，仍可能得到与目标相同的候选。随后只在 $f(u_i)\le f(x_i)$ 时替换，否则保留原点。一代所有候选均由旧种群生成，再统一提交；立即使用新个体会改变轨迹。

两个候选都比旧点改善，但变化的坐标与目标值不同。

在主例中 $CR=1$ 时，试验向量就是 $(1,-1)$，被接受。变式取 $CR=0$ 且强制第二坐标，候选为 $(-2,-1)$，代价6.5，也被接受，但只更新了一个分量。如果没有强制坐标，CR为零时会完全复制目标，所有计算都无法改变种群。

最好值不增加及停滞反例

选择规则对每个个体都保证 $f(x_i^{\mathrm{n}\mathrm{e}\mathrm{w}})\le f(x_i^{\mathrm{o}\mathrm{l}\mathrm{d}})$，于是对i取最小值得 $\underset{i}{min}f(x_i^{\mathrm{n}\mathrm{e}\mathrm{w}})\le \underset{i}{min}f(x_i^{\mathrm{o}\mathrm{l}\mathrm{d}})$。这是精英保留不变量，保证已取得的最好值不会丢失，不保证严格改善，也不保证达到全局最小。

例如一维目标 $f(x)=(x-1{)}^2$，种群四个个体全部为零。所有差向量均为零，变异、交叉和选择始终返回零，永远达不到可行最优点一。即使F为正、CR为一，种群丢失多样性也可完全冻结。种群目标标准差变小、预算用尽或多代未改善，是停止证据，不是精确最优性差距。

可运行的一代与多代实现

下例只用标准库，复制输入种群并在每代使用旧副本；边界外分量按最近边界截断。该规则是本实现的选择，其他修复方式会影响分布。输入个体维数一致且至少四个，返回新种群、最好值历史，不改写输入。N个n维个体、K代需约 $O(KN(n+C_f))$ 时间，种群空间 $O(Nn)$，历史另占 $O(K)$；其中 $C_f$ 是单次目标评价成本。

Python 3

import random

def differential_evolution(population,objective,bounds,F=.5,CR=.8,generations=4,seed=820):
    pop = [list(map(float,row)) for row in population]
    N,d = len(pop),len(bounds)
    if N < 4 or d < 1 or any(len(row) != d for row in pop) or F <= 0 or not 0 <= CR <= 1 or generations < 0:
        raise ValueError("invalid population or DE parameters")
    if any(lo >= hi for lo,hi in bounds) or any(not lo <= row[j] <= hi for row in pop for j,(lo,hi) in enumerate(bounds)):
        raise ValueError("invalid bounds or infeasible initial population")
    rng = random.Random(seed)
    values = [objective(row) for row in pop]
    history = [min(values)]
    for _ in range(generations):
        next_pop,next_values = [],[]
        for i in range(N):
            q = rng.sample(range(N-1),3)
            a,b,c = (j+int(j >= i) for j in q)
            mutant = [pop[a][j]+F*(pop[b][j]-pop[c][j]) for j in range(d)]
            mutant = [min(hi,max(lo,v)) for v,(lo,hi) in zip(mutant,bounds)]
            forced = rng.randrange(d)
            trial = [mutant[j] if rng.random() < CR or j == forced else pop[i][j] for j in range(d)]
            value = objective(trial)
            accept = value <= values[i]
            next_pop.append(trial if accept else pop[i][:])
            next_values.append(value if accept else values[i])
        pop,values = next_pop,next_values
        history.append(min(values))
    return pop,history

objective = lambda z:(z[0]-.5)**2+(z[1]+.5)**2
population = [(-2,-2),(0,0),(1,1),(3,-1)]
print("manual trial",(1,-1),objective((1,-1)))
print("CR=0 variant",(-2,-1),objective((-2,-1)))
result,history = differential_evolution(population,objective,[(-3,3),(-3,3)])
print("best history",history)
assert all(b <= a for a,b in zip(history,history[1:]))
assert differential_evolution([[0]]*4,lambda z:(z[0]-1)**2,[(-2,2)])[1] == [1.0]*5