摘要

如何选取一组最佳的参数，使得代价函数值最优？这是优化算法做的事，一个直觉的方法是使用网格搜索，遍历参数值在值域上的所有组合，选取代价函数值最优的一组参数值，该方法搜索时无方向驱使，需遍历整个参数空间，复杂度太高。梯度下降算法通过代价函数对参数的导数有方向的更新参数值，无需搜索整个向量空间，速度很快，但无法解决不可导问题。而差分进化算法是一种基于“适者生存”思想的最优参数搜索算法。通过变异、交叉、选择循环维护$NP$个最优秀个体的种群实现“适者生存”，达到最优参数搜索的目的，无需代价函数对参数可导。注意种群中的每个个体表示参数空间的一组向量值，个体的一个基因表示一个参数。本文参考97年原始论文，根据差分进化算法原理复现代码。

1、算法原理

差分进化算法核心是种群的演化，第$G$代种群中的第$i$个个体可用数学符号表示为$x_{i,G}，i=1,2,\dots ,NP$。流程如下图，初始化时在值域空间随机选取$NP个个体$作为初始种群，通过变异交叉得到种群中每个个体对应的实验个体， 比较种群的现有个体与实验个体的代价值，选择更优的作为下一代种群中的个体，循环往复，直至满足结束条件。

1.1、种群初始化

根据参数的取值范围，随机生成$NP$个个体，作为初始种群。

1.2、变异

对于种群中的每一个个体，随机抽取的2个个体加权差与之加和，得到变异个体$v_{i,G+1}$，数学表示为：
$$v_{i,G+1}=x_{r_1,G}+F\cdot \left(x_{r_2,G}-x_{r_3,G}\right)\text{\hspace{1em}(1)}$$
$r_1,r_2,r_3\in [1,NP]$，是种群中的个体索引，$F\in [0,2]$，是常数因子，用与控制差分的缩放。

1.3、交叉

变异个体与目标个体随机交换基因，得到下一代的实验个体。数学表示为：
$$\begin{array}{rl}{u}_{ji,G+1}& =\{\begin{array}{ll}{v}_{ji,G+1}& \text{ if }(\mathrm{randb}(j)\le CR)\text{ or }j=\mathrm{rnbr}(i)\\ x_{ji,G}& \text{ if }(\mathrm{randb}(j)>CR)\text{ and }j\ne \mathrm{rnbr}(i)\end{array}\\ j& =1,2,\dots ,D.\end{array}\text{\hspace{1em}(2)}$$
其中$j$是个体基因的索引，$u_{ji,G+1}$表示第$G+1$代种群第$i$个个体的第$j$个基因，$randb(j)$是一个随机数生成器，生成值范围为$[0,1]$，CR是$[0,1]$的交叉常数，当$randb(j)>CR$时交换目标个体和变异个体第$j$个位置的基因，从而得到实验个体，$rnbr(i)$用于确保个体中至少一个基因发生交叉。

1.4、选择

通过比较种群中的个体与对应实验个体的代价函数，选择更优的作为下一轮种群中的个体，并判断是否达到搜索的终止条件，达到终止条件则从当前种群中选取代价函数值最优的个体作为结果。

2、算法实现

以搜索让代价函数$y=x_1^2+|x_2|+x_3^3$值最小的一组参数为例，其中$x_1,x_2,x_3\in [-30,30]$。全部如下代码：

import math
import numpy as npdef cost_func(x:np.array)->float:"""代价函数:param x: 参数列表:return: 参数值对应的代价值"""return math.pow(x[0], 2) + np.abs(x[1]) + math.pow(x[2], 3)def population_init(x_bounds:list, n=50)->np.array:"""种群初始化:param x_bounds: 各参数上下边界:param n: 初始种群大小:return: 初始种群"""population = []for _ in range(n):vector = []for low, high in x_bounds:vector.append(np.random.uniform(low, high))population.append(vector)return np.array(population)def mutation(population:np.array, x_bounds:list, F=1.0):"""变异操作:param population: 种群:param x_bounds: 参数边界范围:param F: 变异的常数因子:return: 变异种群"""n = len(population)mutation_vectors = []for r1 in range(n):r2 = np.random.randint(1, n)r3 = np.random.randint(1, n)v = population[r1] + F*(population[r2]-population[r3])v = edge_deal(v, x_bounds)mutation_vectors.append(v)return np.array(mutation_vectors)def edge_deal(x:np.array, x_bounds:list)->np.array:"""边界处理:param x: 种群中的一个个体:param x_bounds: 参数边界范围:return: 满足边界条件的个体"""D = len(x)for j in range(D):low, high = x_bounds[j][0], x_bounds[j][1]if x[j] < low:x[j] = lowif x[j] > high:x[j] = highreturn xdef crossover(population:np.array, mutation_vectors:np.array, CR=0.5):"""交叉操作:param population: 种群:param mutation_vectors: 变异种群:param CR: 交叉的常数因子:return: 实验种群（种群和变异种群基因交叉后得到的）"""D = len(population[0])for i in range(len(population)):rnbr = np.random.randint(1, D)for j in range(D):if np.random.rand() > CR or j == rnbr:mutation_vectors[i][j] = population[i][j]return mutation_vectorsdef selector(population:np.array, trial_population:np.array, cost_func):"""选择操作:param population: 种群:param trial_population: 实验种群:param cost_func: 代价函数:return: 更优秀的下一代种群"""next_population = []for i in range(len(population)):if cost_func(population[i]) < cost_func(trial_population[i]):next_population.append(population[i])else:next_population.append(trial_population[i])return next_populationdef min_cost_get(population:np.array):"""获取种群中代价最小的个体:param population: 种群:return: 最优秀的个体和其对应的代价值"""min_cost = cost_func(population[0])min_cost_index = 0for i in range(1, len(population)):if cost_func(population[i]) < min_cost:min_cost = cost_func(population[i])min_cost_index = ireturn population[min_cost_index], min_costif __name__ == '__main__':max_items = 200x_bounds = [(-30, 30)] * 3population = population_init(x_bounds, 50)for i in range(max_items):mutation_vectors = mutation(population, x_bounds)trial_population = crossover(population, mutation_vectors)population = selector(population, trial_population, cost_func)print(min_cost_get(population))

2.1、种群初始化

def population_init(x_bounds:list, n=50)->np.array:"""种群初始化:param x_bounds: 各参数上下边界:param n: 初始种群大小:return: 初始种群"""population = []for _ in range(n):vector = []for low, high in x_bounds:vector.append(np.random.uniform(low, high))population.append(vector)return np.array(population)if __name__ == '__main__':max_items = 200x_bounds = [(-30, 30)] * 3population = population_init(x_bounds, 50)

2.2、变异

def mutation(population:np.array, x_bounds:list, F=1.0):"""变异操作:param population: 种群:param x_bounds: 参数边界范围:param F: 变异的常数因子:return: 变异种群"""n = len(population)mutation_vectors = []for r1 in range(n):r2 = np.random.randint(1, n)r3 = np.random.randint(1, n)v = population[r1] + F*(population[r2]-population[r3])v = edge_deal(v, x_bounds)mutation_vectors.append(v)return np.array(mutation_vectors)def edge_deal(x:np.array, x_bounds:list)->np.array:"""边界处理:param x: 种群中的一个个体:param x_bounds: 参数边界范围:return: 满足边界条件的个体"""D = len(x)for j in range(D):low, high = x_bounds[j][0], x_bounds[j][1]if x[j] < low:x[j] = lowif x[j] > high:x[j] = highreturn x

2.3、交叉

def crossover(population:np.array, mutation_vectors:np.array, CR=0.5):"""交叉操作:param population: 种群:param mutation_vectors: 变异种群:param CR: 交叉的常数因子:return: 实验种群（种群和变异种群基因交叉后得到的）"""D = len(population[0])for i in range(len(population)):rnbr = np.random.randint(1, D)for j in range(D):if np.random.rand() > CR or j == rnbr:mutation_vectors[i][j] = population[i][j]return mutation_vectors

2.4、选择

def selector(population:np.array, trial_population:np.array, cost_func):"""选择操作:param population: 种群:param trial_population: 实验种群:param cost_func: 代价函数:return: 更优秀的下一代种群"""next_population = []for i in range(len(population)):if cost_func(population[i]) < cost_func(trial_population[i]):next_population.append(population[i])else:next_population.append(trial_population[i])return next_population

2.5、选取终代种群中最优秀个体

def min_cost_get(population:np.array):"""获取种群中代价最小的个体:param population: 种群:return: 代价最小的个体和其对应的代价值"""min_cost = cost_func(population[0])min_cost_index = 0for i in range(1, len(population)):if cost_func(population[i]) < min_cost:min_cost = cost_func(population[i])min_cost_index = ireturn population[min_cost_index], min_cost