随机搜索（Random Searching）算法概述

た入场券 2022-05-08 00:54 261阅读 0赞

个人理解，随机搜索是一种在巨大数据规模下执行一个耗时上无法接受的程序的优化方法。  
它可以用以对一个搜索算法施展优化的前提是：

> 1、数据规模大，精确的结果难以在一定时间计算出。  
> 2、结果的些许的不精确能够被接受。  
> 3、求取的结果是最优化（optimization）问题，有一个成本计算模型。

以上自己总结，欢迎补充。

下面还是一步步深入随机搜索算法叙述，也有人把有导向的随机搜索算法称为启发式搜索。

一、最基本的随机搜索

顾名思义，就是随机的搜索，没有特别的要说的，举个例子：有十亿个数字，我想搜索十万次就找出一个比较理想的最小（大）数。这就是一个简单的应用随机搜索的一个场景。这时候我们需要设计一个随机取样的函数，然后在十亿个数里取出十万个数进行比较获取最小（大）的数。虽然后最的结果不精确，但是如果并不需要知道确切的最优值的时候，这还是非常棒的提高程序效率的算法。

这只是一个简单的样例，当然还有许多其他场景会用到随机搜索。但是这种模型非常简单，有时候并不能给出令我们满意的结果，我们还需要对其一步步进行改进。但是核心的思想就是这样的，以后的都是围绕这一思想进行的，这先提前说一下。

二、爬山搜索算法

爬山搜索算法是一种简单的贪心改进，通过基本的搜索算法我们发现，我们并没有利用到已经获得的最优解（假如十亿个数字按一定多项式分布），而是粗暴的进行了随机抽样求取最优解（简单粗暴有时候确实非常好）。贪心策略的假如，使随机搜索算法的效率和准确性有一个较好的提升。如下图所示：  
![爬山算法][2010122016525713.png]  
图中有ABCDE五个点，我们想搜寻曲线中最高点，如果我们起始点随机选取到了C点，根据贪心策略，我们会向比C更高的点搜索过去，以此递归能够找到最高点A。同样的如果随机选取的E点同样的搜到最高点A。只有随机开始点在D的位置，我们才能够搜到真正的最高点B。由此我们可以发现爬山搜索算法的一个缺陷，就是比较容易陷入局部最优解中。

一个简单的消除（可能也消除不了）该缺陷的方法就是，我们多次执行该搜索算法，以期随机选取的开始点落在B点两侧的下降曲线上。最后再比较多次执行爬山搜索算法的结果获取更理想的解。有时候被称为“多重爬山算法”。

三、模拟退火算法(Simulated Annealing、SA)

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。  
模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。可以证明，模拟退火算法所得解依概率收敛到全局最优解。

以上模拟退火介绍引自wiki，简单的说就是在爬山搜索算法的基础上，添加一个概率函数，这个函数能给出一个概率值来决定是否选取该解当当前一步骤下的局部最优解，即有一定概率能够跳出局部最优解。

模拟退火算法新解的产生和接受可分为如下四个步骤：

> 1、由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。  
> 计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
> 
> 2、判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
> 
> 3、当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
> 
> 4、模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

算法步骤引自wiki，看wiki上说的已经很清晰了，所以就粘贴过来不再改了。说一下这个接受新解概率的问题，也是算法的关键部分。上述概率公式就是退火过程中原子选择新位置的概率的原理转换过来的，在退火的过程开始阶段，会有较大的概率接受较差的解。随着退火过程的不断进行，算法越来越不可能接受较差的解，直到最后只能接受最优解。比多重爬山算法更可靠，被证明以概率1收敛全局最优解，注意是收敛于全局最优解，而不是一定是全局最优解。（最后细说）

ps：额外说一下，这里模拟退火算法看起来有点[聚类算法中K-Means算法][K-Means]的味道，只是比前者多一个概率函数。而我们又知道K-Means算法是有一定概率陷入局部最优解的。那是不是能够在K-Means算法中添入概率函数来改进该算法呢？可以的，其实K-Means算法更类似爬山算法，每次只接受最优解，如果我们每次在选取K个中心点的过程中，添加这一概率函数，使其有一定概率选取周围一些非局部最优点的话，就可以了，或者设计一个模型来选取新点。

模拟退火算法，如果模型建的够好，都是能够改进其他穷举搜索算法的。当然别忘了随机搜索算法应用的前提。

四、遗传算法（Genetic Algorithm、GA）

这个算法也是受自然科学的启发，模拟生物种群的进化，实现的一种计算机模拟算法。算法中参考了种群（population）的形成、进化、物竞天择等概念，有颜色体串（基因串，即某一题解），发生交叉（crossover）、配对（breeding）、变异（mutation）等行为，繁殖产生新的一个更接近全局最优解的新种群，这样递归下去到某一步结束种群的发展。

算法步骤：

> 1、选取初始种群  
> 2、评价种群个体的适应度  
> 3、按比例选择产生下一个种群  
> 4、改变种群  
> 5、判断停止条件，不满足则返回第二步循环执行

初始种群的选取一般可以随机的选取一些题解。种群个体适应度就是根据成本函数计算出的花费。按比例选择下一代，一般会较高比例选取适应度高（花费低）的个体，也称之为精英选拔，按较低比例选取其他适应度低的个体。这样就产生了新的种群，新种群的组成还没完，还要包括第四步的改变种群，也就是交叉、配对、变异等操作，对已经加入新种群的个体进行修改产生新的个体。一般简单的操作就是进行一些题解的范围的、随机的修改、部分的值的互换、按规则合并等操作。这样一个全新的种群就产生了。然后就是继续评价种群适应度继续选拔。迭代到得到满意解或一定次数为止。

过程中比较关键的一些值还是需要经过多次计算来确定合适值的选取的，比如精英选拔比例，变异概率，成本函数，种群数量等，这些值如果选取还需根据自己需要进行实验而定。

一般的终止条件有：

> 1、进化次数限制  
> 2、计算耗费的资源限制  
> 3、得到一个满足的最优个体  
> 4、适应度不发生变化  
> 5、人为干预

当然也可以组合使用。

本篇先说这四个随机搜索的算法，还有其他的随机搜索算法，像：局部搜索、禁忌搜索、蚁群算法、人工免疫系统（AIS）算法、人工免疫系统（AIS）、粒子群优化（PSO ）、引力搜索算法（ GSA ）、蚁群聚类方法（ ACCM中） 、随机传播搜索（ SDS ）等等，非常多，自己也需要学习消化和实践，改篇再述。如有问题请留言指正，非常感谢。

最后，很难优化的一个问题：  
![7F20120918162128.png][]  
在上图的最右边，有一个狭长的成本最低区域，接近它的任何解都可能被排除在外，因为这些解的成本都很高，所以我们几乎没有概率得到这样一个全局最小值的途径。这是随机化算法的共同缺陷，没有很好的解决途径。

[2010122016525713.png]: http://blog.pureisle.net/wp-content/uploads/2012/09/2010122016525713.png
[K-Means]: http://blog.pureisle.net/?p=1982
[7F20120918162128.png]: http://blog.pureisle.net/wp-content/uploads/2012/09/%7F20120918162128.png