用什么优化算法(遗传算法, 神经网络等)解决多个参数的优化 ...

RhinoFreak 发表于 2022-1-2 10:52

一、机器学习的优化

机器学习的优化（目标），简单来说是：搜索模型的一组参数 w，它能显著地降低代价函数 J(w)，该代价函数通常包括整个训练集上的性能评估（经验风险）和额外的正则化（结构风险）。与传统优化不同，它不是简单地根据数据的求解最优解，在大多数机器学习问题中，我们关注的是测试集（未知数据）上性能度量P的优化。

[*]对于模型测试集是未知，我们只能通过优化训练集的性能度量P_train，在独立同分布基础假设下，期望测试集也有较好的性能（泛化效果），这意味并不是一味追求训练集的最优解。
[*]另外，有些情况性能度量P（比如分类误差f1-score）并不能高效地优化，在这种情况下，我们通常会优化替代损失函数 (surrogate loss function)。例如，负对数似然通常用作 01 分类损失的替代。

当我们机器学习的学习目标是极大化降低（经验）损失函数，这点和传统的优化是比较相似的，那么如何实现这个目标呢？我们第一反应可能是直接求解损失函数最小值的公式/解析解（如最小二乘法），获得最优的模型参数。但是，通常机器学习模型的损失函数较复杂，很难直接求最优解。幸运的是，我们还可以通过优化算法（如遗传算法、梯度下降算法、牛顿法等）有限次迭代优化模型参数，以尽可能降低损失函数的值，得到较优的参数值（数值解）。上述去搜索一组最\较优参数解w所使用的算法，即是优化算法。下图优化算法的总结：（图与本文内容较相符，摘自@teekee）

二、优化算法盘点

最小二乘法

最小二乘法常用在机器学习回归模型求解析解（对于复杂的深度神经网络无法通过这方法求解），其几何意义是高维空间中的一个向量在低维子空间的投影。
如下以一元线性回归用最小二乘法求解为例。

其损失函数mse为：

对损失函数求极小值，也就是一阶导数为0。通过偏导可得关于参数a及偏置b的方程组：

代入数值求解上述线性方程组，可以求解出a，b的参数值。也就是求解出上图拟合的那条直线ax+b。
遗传算法

注：神经网络优化算法以梯度下降类算法较为高效，也是主流的算法。而遗传算法、贪心算法、模拟退火等优化算法用的比较少。
遗传算法（Genetic Algorithms，GA）是模拟自然界遗传和生物进化论而成的一种并行随机搜索最优化方法。与自然界中“优胜略汰，适者生存”的生物进化原理相似，遗传算法就是在引入优化参数形成的编码串联群体中，按照所选择的适应度函数并通过遗传中的选择、交叉和变异对个体进行筛选，使适应度好的个体被保留，适应度差的个体被淘汰，新的群体既继承了上一代的信息，又优于上一代。这样反复循环迭代，直至满足条件。
梯度下降（GD）

梯度下降算法可以直观理解成一个下山的方法，将损失函数J(w)比喻成一座山，我们的目标是到达这座山的山脚（即求解出最优模型参数w使得损失函数为最小值）。

下山要做的无非就是“往下坡的方向走，走一步算一步”，而在损失函数这座山上，每一位置的下坡的方向也就是它的负梯度方向（直白点，也就是山的斜向下的方向）。在每往下走到一个位置的时候，求解当前位置的梯度，向这一步所在位置沿着最陡峭最易下山的位置再走一步。这样一步步地走下去，一直走到觉得我们已经到了山脚。当然这样走下去，有可能我们不是走到山脚（全局最优，Global cost minimun），而是到了某一个的小山谷（局部最优，Local cost minimun），这也后面梯度下降算法的可进一步调优的地方。对应的算法步骤，直接截我之前的图：

梯度下降是一个大类，常见的梯度下降算法及优缺点，如下图：

随机梯度下降（SGD）

对于深度学习而言“随机梯度下降, SGD”，其实就是基于小批量（mini-batch）的随机梯度下降，当batchsize为1也就是在线学习优化。
随机梯度下降是在梯度下降算法效率上做了优化，不使用全量样本计算当前的梯度，而是使用小批量（mini-batch）样本来估计梯度，大大提高了效率。原因在于使用更多样本来估计梯度的方法的收益是低于线性的，对于大多数优化算法基于梯度下降，如果每一步中计算梯度的时间大大缩短，则它们会更快收敛。且训练集通常存在冗余，大量样本都对梯度做出了非常相似的贡献。此时基于小批量样本估计梯度的策略也能够计算正确的梯度，但是节省了大量时间。
对于mini-batch的batchsize的选择是为了在内存效率（时间）和内存容量（空间）之间寻找最佳平衡。

[*]batchsize 不能太大。较大的batch可能会使得训练更快，但可能导致泛化能力下降。更大的batch size 只需要更少的迭代步数就可以使得训练误差收敛，还可以利用大规模数据并行的优势。但是更大的batch size 计算的梯度估计更精确，它带来更小的梯度噪声。此时噪声的力量太小，不足以将参数带出一个尖锐极小值的吸引区域。这种情况需要提高学习率，减小batch size 提高梯度噪声的贡献。
[*]batchsize不能太小。小的batchsize可以提供类似正则化效果的梯度噪声，有更好的泛化能力。但对于多核架构来讲，太小的batch并不会相应地减少计算时间（考虑到多核之间的同步开销）。另外太小batchsize，梯度估计值的方差非常大，因此需要非常小的学习速率以维持稳定性。如果学习速率过大，则导致步长的变化剧烈。
还可以自适应调节batchsize，参见《Small Batch or Large Batch? Peifeng Yin》
Momentum动量算法

Momentum算法在梯度下降中加入了物理中的动量的概念，模拟物体运动时候的惯性，即在更新的时候在一定程度上保留之前更新的方向，同时利用当前batch的梯度对之前的梯度进行微调，这样一来，可以在一定程度上增加稳定性，从而学习的更快，并且有一定的摆脱局部最优的能力。
该算法引入了变量 v 作为参数在参数空间中持续移动的速度向量，速度一般可以设置为负梯度的指数衰减滑动平均值。对于一个给定需要最小化的代价函数，动量可以表达为：更新后的梯度 = 折损系数γ动量项+ 学习率当前的梯度。

其中为学习率，γ ∈ (0, 1] 为动量系数，v 是速度向量。一般来说，梯度下降算法下降的方向为局部最速的方向（数学上称为最速下降法），它的下降方向在每一个下降点一定与对应等高线的切线垂直，因此这也就导致了 GD 算法的锯齿现象。加入动量法的梯度下降是令梯度直接指向最优解的策略之一。

Nesterov

Nesterov动量是动量方法的变种，也称作Nesterov Accelerated Gradient（NAG）。在预测参数下一次的位置之前，我们已有当前的参数和动量项，先用(θγvt1)下一次出现位置的预测值作为参数，虽然不准确，但是大体方向是对的，之后用我们预测到的下一时刻的值来求偏导，让优化器高效的前进并收敛。

在平滑的凸函数的优化中，对比批量梯度下降，NAG 的收敛速度超出 1/k 到 1/(k^2)
Adagrad

Adagrad 亦称为自适应梯度（adaptive gradient），允许学习率基于参数进行调整，而不需要在学习过程中人为调整学习率。Adagrad 根据不常用的参数进行较大幅度的学习率更新，根据常用的参数进行较小幅度的学习率更新。然而 Adagrad 的最大问题在于，在某些情况，学习率变得太小，学习率单调下降使得网络停止学习过程。

其中是梯度平方的积累量s，在进行参数更新时，学习速率要除以这个积累量的平方根，其中加上一个很小值是ε为了防止除0的出现。由于s 是逐渐增加的，那么学习速率是相对较快地衰减的。
RMSProp

RMSProp 算是对Adagrad算法的改进，主要是解决学习速率过快衰减的问题，它不是像AdaGrad算法那样暴力直接的累加平方梯度，而是加了一个衰减系数γ 来控制历史信息的获取多少。

Adam

Adam 算法为两种随机梯度下降的优点集合：

[*]适应性梯度算法（AdaGrad）为每一个参数保留一个学习率以提升在稀疏梯度（即自然语言和计算机视觉问题）上的性能。
[*]均方根传播（RMSProp）基于权重梯度最近量级的均值为每一个参数适应性地保留学习率。这意味着算法在非稳态和在线问题上有很有优秀的性能。
Adam 算法同时获得了 AdaGrad 和 RMSProp 算法的优点，像RMSprop 一样存储了过去梯度的平方 v的指数衰减平均值，也像 momentum 一样保持了过去梯度 m 的指数衰减平均值：

如果 m 和 v被初始化为 0 向量，那它们就会向 0 偏置，所以做了偏差校正放大它们：

梯度更新能够从梯度均值及梯度平方两个角度进行自适应地调节，而不是直接由当前梯度决定。

牛顿法

牛顿法和梯度下降法相比，两者都是迭代求解，不过梯度下降法是梯度求解（一阶优化），而牛顿法是用二阶的海森矩阵的逆矩阵求解。相对而言，使用牛顿法收敛更快（迭代更少次数），但是每次迭代的时间比梯度下降法长（计算开销更大，实际常用拟牛顿法替代）。

通俗来讲，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，后面坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。但是，牛顿法对初始值有一定要求，在非凸优化问题中（如神经网络训练），牛顿法很容易陷入鞍点（牛顿法步长会越来越小），而梯度下降法则更容易逃离鞍点（因此在神经网络训练中一般使用梯度下降法，高维空间的神经网络中存在大量鞍点）。
综上，对于神经网络的优化，常用梯度下降等较为高效的方法。梯度下降算法类有SGD、Momentum、Adam等算法可选。对于大多数任务而言，通常可以直接先试下Adam，然后可以继续在具体任务上验证不同优化器效果。
当然，对于机器学习的优化而言，优化算法只是一方面，【数据/特征，模型，目标函数，优化算法】是一个整体，一个较优的结果，往往需要协调好这四个因素。

文章首发公众号“算法进阶”，更多原创文章敬请关注个人github：https://github.com/aialgorithm

DungDaj 发表于 2022-1-2 10:54

Ylisar 发表于 2022-1-2 10:59

首先，如果你的问题是每个参数的取值是整数的话，你直接用网格搜索全部遍历一遍就好了。你的搜索空间太小了，也就10的10次方。
如果你的参数取值是连续的，可以取小数那些的话，一般用遗传算法、粒子群优化算法这些单目标的启发式优化算法就OK了。有需要你可以再套个元启发式看看效果。
深度学习的话，我觉得你可以试下强化学习，我记得强化学习用来做参数优化的研究挺多的。或者简单点全连接套几层看看效果也行。

zifa2003293 发表于 2022-1-2 11:00

优化问题

1、遗传算法

遗传算法采用“优胜劣汰，适者生存”的生物进化原理，按照所选择的适应度函数并通过遗传中的复制、交叉、变异对个体进行筛选，适应度高的被留下来，组成新的群体。
它主要包括三个方面：（1）复制：从一个旧群体中选择适应度高的在下一代中更可能被保留下来。（2）交叉：通过两个个体的交换组合，产生新的优良品种。交叉又有单点交叉、两点交叉、一致交叉、顺序交叉和周期交叉，其中单点交叉运用最广。单点交叉：任意选择两个染色体，随机选择一个交换点位置，交换两个染色体右边的部分。（3）变异：变异运算用来模拟生物在自然的遗传环境中因为各种偶然因素引起的基因突变。算法中以很小的概率随机改变（染色体某一位置）的值，表现为随机将某一基因1变为0，0变为1。
算法流程为：初始化群体---->计算各个个体的适应度---->根据适应度选择个体（适应度高的留下，适应度低的淘汰）----->按照一定的概率进行交叉、变异来产生新的优良品种----->形成新的群体计算适应度（迭代）----->满足终止条件，输出结果
算法特点：（1）直接对结构对象进行操作（2）具有隐含并行性和更好的全局寻优能力（3）能自动获取和指导优化的搜索空间，自适应调整方向，不需要确定的规则
2、模拟退火算法
它采用类似于物理退火的过程，先在一个高温状态下，逐渐退火，在每个温度下进行状态转移，最终达到物理基态。
模拟退火算法从某一高温出发，以预设的领域函数，产生新的状态。比较新旧状态下的能量，如果新状态能量小于旧状态，则状态发生变化。否则，以Metropolis接受准则发生变化。当状态稳定后便可以开始降温，在下一温度继续迭代。
Metropolis准则：温度为T，当前状态i,新状态j,若Ei>Ej,则接受j为当前状态；否则，计算状态j与状态i的比值，若大于[0,1)产生的随机数，则接受j为当前状态。它以概率形式接受新状态，避免局部最优。
领域函数：通常在当前状态的领域结构以一定概率方式产生，概率分布可以是均匀分布、正态分布、指数分布等。
该算法的核心主要是内外两次循环，内循环模拟同一温度下多次的状态转移，外循环为进行的迭代次数。
该算法的初始温度和终止温度过低或过高都会延长搜索时间，而降温太快又容易漏掉全局最优，因此要选择合适的冷却进度表。

模拟退火算法它主要是在每一次的迭代下，寻找这次迭代的最优解（局部搜索，当前状态和下一状态进行比较），然后模拟降温过程进行迭代。若是降温的越慢，得到的最优解更精确，但搜索时间过长。由于计算速度和时间限制，在优化效果和计算时间上存在矛盾，优化效果不理想。
遗传算法它可以进行多个个体同时比较，有潜在的并行性。但是他得三个算子的实现有参数（如交叉和变异的概率），参数的选择大多依靠经验，它可能会影响效果。
3、粒子群算法
粒子群算法通过更新每次迭代的局部最优和全局最优来更新粒子的速度和位置，它保留了全局和局部，对于较快收敛和避免过早陷入局部最优都有较好的效果。

粒子群算法和遗传算法都可以同时比较多个个体寻找最优解，不同的是粒子群算法的每个个体还要和过去的个体进行比较，而遗传算法是把适应度大的较大概率的保留到下一代中，适应度小的淘汰。模拟退火算法它是对单个个体温度不变下，状态转移，求目标函数值更新最优解，随着温度不断降低，状态转移的范围也逐渐变小。
//遗传算法
import numpy as np
DNA_size=10
pops=60
jiaohuan=0.7
bianyi=0.003
gen=100
x_bound=[-3,3]
y_bound=[-3,3]
def fun(x,y):
return 100.0*(y-x**2.0)**2.0+(1-x)**2.0
def get_fitness(pop):
x,y=trans(pop)
pred=fun(x,y)
return pred
def trans(pop):
x_pop=pop[:,0:DNA_size]
y_pop=pop[:,0:DNA_size]
x=x_pop.dot(2**np.arange(DNA_size)[::-1])/float(2**DNA_size -1)*(x_bound-x_bound)+x_bound
y=y_pop.dot(2**np.arange(DNA_size)[::-1])/float(2**DNA_size-1)*(x_bound-x_bound)+x_bound
return x,y
def crossover(pop):
new_pop=[]
pred=get_fitness(pop)
index=np.argmax(pred)
index2=np.argmin(pred)
for father in pop:
   if (father == pop).all()==True:
         child=pop
   else:
         child=father
   if np.random.rand()<jiaohuan:
         mother=pop
         cross_point=np.random.randint(low=0,high=DNA_size*2)
         child=mother
   child=mutation(child)
   new_pop.append(child)
return new_pop
def mutation(child):
if np.random.rand()<bianyi :
   mutate_point=np.random.randint(0,DNA_size)
   child=child^1
return child
def select(pop,fitness):
idx=np.random.choice(np.arange(pops),size=pops,replace=True,p=(fitness)/(fitness.sum()))
return pop
def print_info(pop):
fitness=get_fitness(pop)
max_index=np.argmax(fitness)
print(&#34;最优解：&#34;,fitness)
x,y=trans(pop)
print(&#34;最优基因型：&#34;,pop)
print(&#34;最优解的x,y :&#34;,x,y)
if __name__==&#34;__main__&#34;:
pop=np.random.randint(2,size=(pops,DNA_size*2))
fitness=get_fitness(pop)
for i in range(gen):
   pop=np.array(crossover(pop))
   fitness=get_fitness(pop)
   pop=select(pop,fitness)
print_info(pop)<hr/>//模拟退火算法
import numpy as np
import matplotlib.pyplot as plt
import math
def fun(x):
y=x**3-60*x**2-4*x+6
return y
T=1000
Tmin=10
x=np.random.uniform(low=0,high=100)
k=50
t=0
y=0
while T>=Tmin:
for i in range(k):
   y=fun(x)
   xnew=x+np.random.uniform(low=-0.055,high=0.055)*T
   if (0<=xnew and xnew<=100):
         ynew=fun(xnew)
         if ynew-y<0:
            x=xnew
         else:
            p=math.exp(-(ynew-y)/T)
            r=np.random.uniform(low=0,high=1)
            if r<p:
               x=xnew
t +=1
print(t)
T=1000/(1+t)
print(x,fun(x))
<hr/>//粒子群算法
import numpy as np
import matplotlib.pyplot as plt

class PSO(object):
def __init__(self, population_size, max_steps):
   self.w = 0.6# 惯性权重
   self.c1 = self.c2 = 2
   self.population_size = population_size# 粒子群数量
   self.dim = 2# 搜索空间的维度
   self.max_steps = max_steps# 迭代次数
   self.x_bound = [-10, 10]# 解空间范围
   self.x = np.random.uniform(self.x_bound, self.x_bound,
                                 (self.population_size, self.dim))# 初始化粒子群位置
   self.v = np.random.rand(self.population_size, self.dim)# 初始化粒子群速度
   fitness = self.calculate_fitness(self.x)
   self.p = self.x# 个体的最佳位置
   self.pg = self.x# 全局最佳位置
   self.individual_best_fitness = fitness# 个体的最优适应度
   self.global_best_fitness = np.min(fitness)# 全局最佳适应度

def calculate_fitness(self, x):
   return np.sum(np.square(x), axis=1)

def evolve(self):
   fig = plt.figure()
   for step in range(self.max_steps):
         r1 = np.random.rand(self.population_size, self.dim)
         r2 = np.random.rand(self.population_size, self.dim)
         # 更新速度和权重
         self.v = self.w*self.v+self.c1*r1*(self.p-self.x)+self.c2*r2*(self.pg-self.x)
         self.x = self.v + self.x
         plt.clf()
         plt.scatter(self.x[:, 0], self.x[:, 1], s=30, color=&#39;k&#39;)
         plt.xlim(self.x_bound, self.x_bound)
         plt.ylim(self.x_bound, self.x_bound)
         plt.pause(0.1)
         fitness = self.calculate_fitness(self.x)
         # 需要更新的个体
         update_id = np.greater(self.individual_best_fitness, fitness)
         self.p = self.x
         self.individual_best_fitness = fitness
         # 新一代出现了更小的fitness，所以更新全局最优fitness和位置
         if np.min(fitness) < self.global_best_fitness:
            self.pg = self.x
            self.global_best_fitness = np.min(fitness)
         print(&#39;step: %.d, best fitness: %.5f, mean fitness: %.5f&#39; % (step+1, self.global_best_fitness, np.mean(fitness)))

pso = PSO(100, 100)
pso.evolve()
plt.title(&#34;minimum sum square&#34;)
plt.show()

页: [1]

Unity开发者联盟's Archiver

用什么优化算法(遗传算法, 神经网络等)解决多个参数的优化 ...