遗传算法与深度学习实战（15）——差分进化详解与实现

0. 前言

深度学习 (Deep learning, DL) 系统通常可以被简单的视为凸函数逼近器，函数逼近并不仅局限于 DL。进化计算 (Evolutionary Computation, EC) 包含了多种方法，不仅限于连续解，还可以解决不连续解。差分进化 (Differential Evolution, DE) 是一种专注于连续和不连续解的函数逼近方法，但该方法并不是基于微积分，而是依赖于减少优化解的差异。在本节中，我们将使用 DE 来逼近已知的连续多项式解，以及不连续和复杂函数。当我们需要将 DL 与 EC 结合解决问题时，DE 是一个行之有效的方法。

1. 差分进化

1.1 基本原理

相比遗传算法 (Genetic Algorithms, GA) 与遗传编程，差分进化 (Differential Evolution, DE) 与粒子群优化 (Particle Swarm Optimization, PSO) 更相似。在差分进化中，我们维护一个个体种群，每个个体具有相等的向量大小。与 PSO 类似，个体是长期存在的，不会产生后代，但它们的组件向量会通过与其他随机个体的差异比较来进行修改，以生成新的更好的个体。

1.2 差分进化基本流程

下图显示了差分进化的基本工作流程。在该图的起始处，从一组较大的个体种群中随机选择三个个体。然后，使用这三个个体来修改每个索引值上的目标 Y，方法是将第一个个体 a 的值加到个体 b 和 c 之间的比例差异上。评估生成的个体 Y 的适应度，如果该值更好，则用新的个体 Y 替换该个体。

这种方法在不连续函数上如此有效的原因是计算个体维度差异。与通常需要混合结果(如在 DL 中)或概括结果(如在遗传进化中)的正常优化函数不同，差分进化进行了分量级的差异化。
在 DL 中，我们使用梯度优化方法在训练期间反向传播误差，这是一个全局优化问题。差分进化将优化提取为数值的分量级差异，因此不受全局方法的限制。这意味着差分进化可以用于逼近不连续或复杂的函数。

2. 使用差分进化逼近复杂和不连续函数

在本节中，我们继续使用在进化策略一节中使用的三个问题：多项式、绝对值和阶跃函数。

(1) 为了比较，我们首先使用差分进化解决多项式函数逼近问题。由于绝对值和分段函数更复杂，需要更多时间来运行，因此我们还需要修改最长运行时间超参数(将 MAX_TIME 的值从 5 秒更改为 100)：

import random
import array
import timeimport numpy as npfrom deap import base
from deap import benchmarks
from deap import creator
from deap import toolsimport matplotlib.pyplot as plt
from IPython.display import clear_outputNDIM = 6
CR = 0.25
F = 1  
MU = 300
NGEN = 1000  
GEN_OUTPUT = 25
MAX_TIME = 5

通过设置不同函数，重新运行代码，能够解决不同函数逼近问题。例如，为了更好的进行比较，将 MAX_TIME 更改为 100 秒，将目标函数设置为 step (分段函数)。下图显示了使用差分进化 (Differential Evolution, DE) 和进化策略 (Evolutionary Strategies, ES) 方法逼近 step 函数的差异，可以看到，DE 方法的性能比 ES 方法要好 10 倍以上，这与差分方法有关；另一方面，ES 的直方图服从正态分布，而 DE 的分布类似于狭窄的柯西分布。

(2) 接下来，编写 creator 和 toolbox 设置代码。对于 toolbox，注册一个类型为 float 的属性，初始值为 -3 到 +3，类似于遗传进化中的基因。然后，定义类型为 float 且大小为 NDIM (维度数)的个体。注册一个使用 random 方法选择三个元素的 select 函数，用于选择三个个体 (a、b、c) 来应用差分算法。

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", array.array, typecode='d', fitness=creator.FitnessMin)toolbox = base.Toolbox()
toolbox.register("attr_float", random.uniform, -3, 3)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, NDIM)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("select", tools.selRandom, k=3)equation_form = "polynomial" #@param ["polynomial", "abs", "step"]X_START = -5
X_END = 5
X_STEP = 0.5def equation(x):if equation_form == "polynomial":return (2*x + 3*x**2 + 4*x**3 + 5*x**4 + 6*x**5 + 10) elif equation_form == "abs":    return abs(x)else:    return np.where(x>1, 1, 0)     X = np.array([x for x in np.arange(X_START, X_END, X_STEP)])
Y = equation(X)
data = list(zip(X, Y))plt.scatter(X,Y)import csv
with open('data.csv', 'w') as f:      # using csv.writer method from CSV packagewrite = csv.writer(f)      
write.writerows(data)def pred(ind, x):    y_ = 0.0    for i in range(1,NDIM):y_ += ind[i-1]*x**i    y_ += ind[NDIM-1]       return y_def fitness(ind, data):    mse = 0.0    for x, y in data:        y_ = pred(ind, x)mse += (y - y_)**2        return mse/len(data),# fitness eval
toolbox.register("evaluate", fitness, data=data)def plot_fitness(g, best, pop, logbook):Y_ = np.array([pred(best, x) for x in X])clear_output()print(f"Generation {g}, Best {best}") print(logbook.stream)fits = [f.fitness.values[0] for f in pop]  plt.hist(fits)plt.show()plt.scatter(X,Y)plt.plot(X,Y_, 'r')plt.show()

(3) 运行训练过程，代码中有两个 for 循环——第一个循环迭代代数次，第二个循环遍历每个个体。在内部循环中，我们首先对个体进行采样 (a、b、c)，然后克隆个体作为目标 Y。然后，我们对个体的向量进行随机索引采样，并使用交叉概率值 (CR) 确定是否计算可能的差异。最后，检查新个体是否具有更好的适应度，如果是，则用新个体替换旧个体：

pop = toolbox.population(n=MU);
hof = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", np.mean)
stats.register("std", np.std)
stats.register("min", np.min)
stats.register("max", np.max)logbook = tools.Logbook()
logbook.header = "gen", "evals", "std", "min", "avg", "max"# Evaluate the individuals
fitnesses = toolbox.map(toolbox.evaluate, pop)
for ind, fit in zip(pop, fitnesses):ind.fitness.values = fitrecord = stats.compile(pop)
logbook.record(gen=0, evals=len(pop), **record)
print(logbook.stream)
start = time.time()
for g in range(1, NGEN):for k, agent in enumerate(pop):a,b,c = toolbox.select(pop)y = toolbox.clone(agent)index = random.randrange(NDIM)for i, value in enumerate(agent):if i == index or random.random() < CR:y[i] = a[i] + F*(b[i]-c[i])y.fitness.values = toolbox.evaluate(y)if y.fitness > agent.fitness:pop[k] = y       hof.update(pop)    record = stats.compile(pop)logbook.record(gen=g, evals=len(pop), **record)if (g+1) % GEN_OUTPUT == 0:plot_fitness(g, hof[0], pop, logbook) end = time.time()if end-start > MAX_TIME:breakprint("Best individual is ", hof[0], hof[0].fitness.values[0])

输出结果如下所示：

Generation 224, Best Individual('d', [30.623428393852492, 9.95572994067285, -0.111135397356243, 4.814033796899285, 6.145782841353448, -15.520563507441928])
200	300  	12101.9    	1204.96	14070.8    	105171     
201	300  	12097.2    	1204.96	14038.9    	105171     
202	300  	12075      	1204.96	13995.6    	105171     
203	300  	11617      	1204.96	13748.1    	105171     
204	300  	11572.5    	1204.96	13707.8    	105171     
205	300  	10211.7    	1204.96	13305.5    	80207      
206	300  	10213.3    	1204.96	13298.9    	80207      
207	300  	10210.2    	1204.96	13190.8    	80207      
208	300  	10193.8    	1204.96	13046.2    	80207      
209	300  	10153.5    	1204.96	12928.7    	80207      
210	300  	9831.04    	1204.96	12818.5    	65199.8    
211	300  	9731.12    	1204.96	12725      	65199.8    
212	300  	9386.74    	1204.96	12482.3    	65199.8    
213	300  	9351.17    	1099.93	12338      	65199.8    
214	300  	9269.36    	1099.93	12217.7    	65199.8    
215	300  	9304.61    	1099.93	12113.3    	64891      
216	300  	9300.13    	1099.93	12020.8    	64891      
217	300  	9263.16    	1099.93	11888.1    	64891      
218	300  	9276.17    	1099.93	11794.4    	64891      
219	300  	9291.6     	1099.93	11732.7    	64891      
220	300  	9310.43    	1099.93	11694.6    	64891      
221	300  	9299.04    	1099.93	11622      	64891      
222	300  	9281.38    	1099.93	11508.5    	64891      
223	300  	9274.25    	1099.93	11461.3    	64891      
224	300  	9178.1     	1099.93	11391.1    	64891      Best individual is  Individual('d', [30.623428393852492, 9.95572994067285, -0.111135397356243, 4.814033796899285, 6.145782841353448, -15.520563507441928]) 1099.9285908060874

通过更改数据准备中的函数类型，我们可以在绝对值或分段函数上使用差分进化，还可以尝试调整超参数，查看它们对使用 ES 和 DE 逼近函数的影响。通过完成以下问题进一步理解差分进化的基本概念：

• 修改超参数，然后重新运行，观察能否改善不连续函数逼近的性能
• 比较 ES 和 DE 对于各种函数的函数逼近结果。

小结

差分进化 (Differential Evolution, DE) 和进化策略 (Evolutionary Strategies, ES) 都为连续问题提供了优秀的函数逼近器，对于不连续问题，通常最好应用 DE，因为它不受全局空间中逐渐逼近的限制。在本节中，我们对 EC 进行了扩展，并介绍了差分进化方法，用于解决新颖或复杂的问题。

系列链接

遗传算法与深度学习实战（1）——进化深度学习
遗传算法与深度学习实战（2）——生命模拟及其应用
遗传算法与深度学习实战（3）——生命模拟与进化论
遗传算法与深度学习实战（4）——遗传算法（Genetic Algorithm）详解与实现
遗传算法与深度学习实战（5）——遗传算法中常用遗传算子
遗传算法与深度学习实战（6）——遗传算法框架DEAP
遗传算法与深度学习实战（7）——DEAP框架初体验
遗传算法与深度学习实战（8）——使用遗传算法解决N皇后问题
遗传算法与深度学习实战（9）——使用遗传算法解决旅行商问题
遗传算法与深度学习实战（10）——使用遗传算法重建图像
遗传算法与深度学习实战（11）——遗传编程详解与实现
遗传算法与深度学习实战（12）——粒子群优化详解与实现
遗传算法与深度学习实战（13）——协同进化详解与实现
遗传算法与深度学习实战（14）——进化策略详解与实现