随机搜索(Random Searching)算法概述

2023-11-05 02:32

本文主要是介绍随机搜索(Random Searching)算法概述,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

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

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

一、最基本的随机搜索

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

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

二、爬山搜索算法

爬山搜索算法是一种简单的贪心改进,通过基本的搜索算法我们发现,我们并没有利用到已经获得的最优解(假如十亿个数字按一定多项式分布),而是粗暴的进行了随机抽样求取最优解(简单粗暴有时候确实非常好)。贪心策略的假如,使随机搜索算法的效率和准确性有一个较好的提升。如下图所示:
爬山算法
图中有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个中心点的过程中,添加这一概率函数,使其有一定概率选取周围一些非局部最优点的话,就可以了,或者设计一个模型来选取新点。

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

四、遗传算法(Genetic Algorithm、GA)

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

算法步骤:

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

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

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

一般的终止条件有:

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

当然也可以组合使用。

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

最后,很难优化的一个问题:

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

这篇关于随机搜索(Random Searching)算法概述的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/346823

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

使用C#如何创建人名或其他物体随机分组

《使用C#如何创建人名或其他物体随机分组》文章描述了一个随机分配人员到多个团队的代码示例,包括将人员列表随机化并根据组数分配到不同组,最后按组号排序显示结果... 目录C#创建人名或其他物体随机分组此示例使用以下代码将人员分配到组代码首先将lstPeople ListBox总结C#创建人名或其他物体随机分组