本文由四部分组成。第一部分主要介绍了四种随机优化算法(随机爬升、模拟退火、遗传算法和互信息最大化输入聚类)。第二部分采用三种随机优化算法(随机爬升、模拟退火和遗传算法)优化神经网络的权值。在第三部分中，我将三种算法和互信息最大化输入聚类(MIMIC)应用于三个经典优化问题。最后比较了各种算法的优缺点和效率。

1.介绍了四种随机优化算法。

1.1随机爬山(RHC)

爬山是一种数学优化技术，属于局部搜索的范畴。它从问题的随机解决方案开始，并通过增量更改不断寻找更好的解决方案，直到无法找到改进。RHC迭代爬山，每次从随机的初始猜测开始，并在每次迭代中向适应度增加的方向移动。这种算法占用内存很少，在凸问题中是最好的。

图1.爬山算法图一。爬山算法

1.2模拟退火(SA)

SA是一种非确定性的全局最优爬山算法。SA通过偶尔接受递减适应度的函数来模拟这个过程，所以它总是有机会逃离局部最优。它的一个参数“T”是温度。温度越高，接受差解的概率越大。通常，t随着算法的运行时间而减少。理论上，该算法总能找到全局最优解，但对于某些问题，其运行速度很慢。在实际应用中，如何确定降低T的速率将成为一个问题。

图2.模拟退火图二。模拟退火

1.3遗传算法

遗传算法是一种受自然选择过程启发的元启发式算法，属于进化算法的一般范畴。遗传算法允许在一个种群的两条父代染色体上进行变异和交叉，将新的后代放入新的种群，从而得到最优解。它不断迭代，直到找到给定函数的最优解。它可以随机搜索种群，在不知道适应度函数导数的情况下，找到局部搜索算法找不到的解。但是，对于复杂的问题，这种方法可能不太好。

图3.遗传算法图3。遗传算法

1.4互信息最大化输入聚类(MIMIC)

MIMIC是分布估计算法的一种，属于进化算法的大范畴。MIMIC首先从input 空空间中最有可能包含C()最优解的区域中随机选取样本，然后使用有效密度估计，该估计可用于捕捉input 空空间中的各种结构，并可通过数据的简单二阶统计计算。

图4.大多数优化算法的问题是，在搜索的前半部分所做的大部分工作并没有直接使搜索的后半部分受益

2.神经网络的权值优化。

2.1数据集选择和预处理

LendingClub(LC)在2005年和2006年成为一个P2P贷款的在线平台，连接借款人和投资者。对于一个公司来说，预测贷款是否会违约是非常重要的。

我选取的数据是2017Q4到2018Q3最近12个月的LC数据。原始数据包括485，484行和145列。在数据预处理过程之后，在机器学习数据集中使用了467，732行和17个特征。

通常情况下，违约不会频繁发生，因此数据集中只有2.2%的违约者。我做了抽样调查，删除了付款人组的随机记录。数据集中有9979个拖欠者和9979个缴纳者，即数据集有19958行和17个特征。

我将数据集分为80%的训练集和20%的测试集。在这一部分中，我将应用三种随机优化算法(随机爬升、模拟退火和遗传算法)来优化神经网络的权重，并将它们与通过反向传播得到的结果进行比较。

2.2随机优化算法的实现

根据我的分析，最佳反向传播设置为2个隐层，每层10个节点，初始学习率为0.064。这里，我使用相同的神经网络设置，但是使用上述三种随机优化算法而不是反向传播来优化权重。我用F1的分数来衡量这部分模型的表现。我使用各种算法的各种参数来测试这些算法，并将结果绘制在图5a中。然后，我根据图5b中每个算法的测试参数组合，画出了最佳模型。每个算法运行3000次迭代。

我发现了三个非常有趣的事情:(1)从图5b来看，训练模型和交叉验证模型表现出相似的收敛路径；(2)从图5c可以看出，GA在F1分数中显示出很大的波动性；(3)反向传播。RHC和SA都在3000次迭代中收敛，但似乎GA需要更多的迭代才能收敛。反向传播收敛最快，而RHC是第二次。

图5a （a）反向传播，（b）RHC，（c）GA的各种变异参数，以及（d）SA的各种冷却指数参数的训练模型和交叉验证模型的F1得分。

图5b 图5a中用于（a）反向传播，（b）RHC，（c）GA和（d）SA的最佳交叉验证模型的F1得分。

为了更好地比较模型性能，我在下面的图5c中进一步比较了每个算法的最佳F1分数和运行时间。遗传算法、RHC算法和SA算法的F1得分都优于反向传播算法，其中遗传算法得分最高，SA算法得分略低但非常接近。至于运行时间，GA的运行时间比其他三种算法要长得多(327.8s)。从图5b可以看出，GA在3000次迭代后似乎没有收敛，所以如果运行更多次迭代，GA可能无法排除GA可能找到更好的解。在这次分析中，SA的得分为69.97%，GA的得分为69.99%，但用时要少得多(18.55秒vs . GA的327.8s)。

图5c 左图：（a）反向传播，（b）GA，（c）RHC和（d）SA的测试集的F1得分。右：经过3000次迭代后的运行时间（a）反向传播，（b）GA，（c）RHC和（d）SA。

简而言之，与反向传播测试相比，反向传播测试的所有三种算法都提高了F1分数。在所有测试算法中，反向传播运行和收敛最快。就F1评分而言，GA是这种神经网络权重优化的最佳算法。但是运行GA需要更长的时间，SA生成的结果和GA一样令人满意，而且在这个问题中运行时间要少很多。

3.在三个问题中实现四个算法。

3.1旅行商问题(TSP)

TSP是一个著名的NP-hard组合优化问题，在运筹学和理论计算机科学中具有重要意义。它提出了以下问题:“给定一个城市列表和每对城市之间的距离，访问每个城市并返回原城市的最短路径是什么？”TSP可以建模为一个图问题。城市是图的顶点，路径是图的边，路径的距离是边的权重。这是一个极小化问题，从一个指定的顶点开始，访问所有其他顶点一次后，在同一个顶点结束。TSP在规划、物流和DNA测序中有许多应用。

假设有100个城市(N = 100)，我用不同的参数测试了这四个算法，并把它们绘制在图6a中。每次运行3000次迭代。对于SA，最佳参数为Temp = 1E10，CE = 0.55。对于GA，最佳参数为Pop = 100，Mate = 50，Mutate = 10。对于MIMIC，最佳参数是Pop = 100，Keep = 50，m = 0.1。MIMIC的性能很大程度上取决于参数的选择。

图6a 通过（a）RHC，（b）SA算法的各种冷却指数参数，（c）GA算法的各种变异参数，（d）MIMIC算法的各种m参数，TSP的适应度得分。

为了更好地比较模型性能，我在下面的图6b中绘制了每个算法的最佳模型，该模型具有最高的适应度得分。结果表明，遗传算法的适应度最好，模仿算法的适应度最差。

图6b 基于测试参数的最佳模型的适应度分数。GA算法在TSP中获得了最佳的适应度分数。

为了比较模型的效率，我在下面的图6c中绘制了TSP的运行时间。从运行时间来看，MIMIC最差，SA最好。

图6c四种随机优化算法3000次迭代后的TSP运行时间。

总之，GA算法是TSP的最佳算法，其运行时间是令人满意的。模仿在适应性和效率上是最差的。在这个模仿的问题中，参数选择是一个非常重要的因素，所以完全不同的参数设置可能会产生不同的结果。

3.2触发器问题(FFP)

FFP是一个计算比特串中比特变换次数的问题。也就是说，从一个数字到下一个数字的任何数字都被记录为1。最大适应度位串应该是完全由交替数字组成的位串。

假设长度为1，000(N = 1，000)，我用不同的参数测试了四种算法，并将它们绘制在图7a中。每次运行1000次迭代。对于SA，最佳参数为Temp = 1E10，CE = 0.35。对于GA，最佳参数为Pop = 100，Mate = 30，Mutate = 50。对于MIMIC，最佳参数是Pop = 100，Keep = 50，m = 0.9。模拟退火算法和遗传算法的性能很大程度上取决于参数的选择。

图7a 通过（a）RHC，（b）SA算法的各种冷却指数参数，（c）GA算法的各种变异参数，以及（d）MIMIC算法的各种m参数，FFP的适应度得分。

为了更好地比较模型性能，我在下面的图7b中为每个算法绘制了具有最高适应度得分的最佳模型。结果表明，MIM的适应度最好，GA最差。RHC和南非在健康得分方面的表现几乎相同。

图7b 基于测试参数的最佳模型的适应度分数。MIMIC算法在FPP中获得了最佳的适应度分数。

为了比较模型的效率，我在下面的图7c中绘制了FFP的运行时间。从运行时间来看，MIMIC最差，SA最好。

图7c 四种随机优化算法在1000次迭代后的FFP运行时间图7c四种随机优化算法在1000次迭代后的FFP运行时间

总之，与TSP类似，MIMIC算法的迭代比其他三种算法慢很多，但与TSP不同，MIMIC算法产生的最佳适应度得分明显优于其他问题。在s a和GA的这个问题中，参数选择是一个非常重要的因素，因此完全不同的参数集可能会产生不同的结果。

3.3连续峰值问题(CPP)

CPP是许多局部最优的问题。在2D世界中，你可以通过在X轴上移动找到更好的解决方案。但是在高维世界里，每个维度的各个方向都能找到更好的解。因此，如果有许多局部最优，随机优化和非随机优化的区别会非常明显。

假设局部最优值是100(N = 100)，我用不同的参数测试了四个算法，并把它们绘制在图8a中。一次运行5000次迭代。对于SA，最佳参数为Temp = 1E10，CE = 0.55。对于GA，最佳参数为Pop = 100，Mate = 50，Mutate = 30。对于MIMIC，最佳参数是Pop = 100，Keep = 50，m = 0.7。MIMIC和GA的性能很大程度上取决于参数的选择。

图8a 通过（a）RHC，（b）SA算法的各种冷却指数参数，（c）GA算法的各种变异参数，以及（d）MIMIC算法的各种m参数，CPP的适应度得分。

为了更好地比较模型性能，我在下面的图8b中为每个算法绘制了具有最高适应度得分的最佳模型。结果表明，MIM的适应度最好，GA最差。RHC和SA在体能得分方面的表现几乎相同。

图8b 基于测试参数的最佳模型的适应度分数。SA算法在CPP中达到了最佳适应度分数。

为了比较模型的效率，我在下面的图8c中绘制了CPP的运行时间。从运行时间来看，MIMIC最差，SA最好。

图8c 四种随机优化算法在5000次迭代后的CPP运行时间图8c四种随机优化算法在5000次迭代后的CPP运行时间

简而言之，类似于TSP和FFP，MIMIC算法的迭代比其他三种算法慢得多。在这个问题中，SA算法产生的适应值最好，迭代速度最快。其适应度得分为99，最接近全局最优值(100)。从体能得分和跑步时间来看，MIMIC在这个问题上是最差的。在这个问题中，参数选择对于RHC和s a来说是一个非常重要的因素，因此完全不同的参数集可能会产生不同的结果。

4结论

在前面问题的基础上，总结了下面表1中每个算法的优缺点，以供比较。对于不同的问题，我们需要考虑它们的复杂性和特点来选择最佳的优化算法。

表1. RHC，SA，GA和MIMIC的比较1.rhc、SA、GA和MIMIC的比较