精华内容
下载资源
问答
  • 搜索算法
    万次阅读 多人点赞
    2020-09-27 16:34:00

    2020智能优化算法:麻雀搜索算法


    摘要:麻雀搜索算法(Sparrow Search Algorithm, SSA)是于2020年提出的。SSA 主要是受麻雀的觅食行为和反捕食行为的启发而提出的。该算法比较新颖,具有寻优能力强,收敛速度快的优点

    1.算法原理

    建立麻雀搜索算法的数学模型,主要规则如下所述:

    1. 发现者通常拥有较高的能源储备并且在整个种群中负责搜索到具有丰富食物的区域,为所有的加入者提供觅食的区域和方向。在模型建立中能量储备的高低取决于麻雀个体所对应的适应度值(Fitness Value)的好坏。
    2. 一旦麻雀发现了捕食者,个体开始发出鸣叫作为报警信号。当报警值大于安全值时,发现者会将加入者带到其它安全区域进行觅食。
    3. 发现者和加入者的身份是动态变化的。只要能够寻找到更好的食物来源,每只麻雀都可以成为发现者,但是发现者和加入者所占整个种群数量的比重是不变的。也就是说,有一只麻雀变成发现者必然有另一只麻雀变成加入者。
    4. 加入者的能量越低,它们在整个种群中所处的觅食位置就越差。一些饥肠辘辘的加入者更有可能飞往其它地方觅食,以获得更多的能量。
    5. 在觅食过程中,加入者总是能够搜索到提供最好食物的发现者,然后从最好的食物中获取食物或者在该发现者周围觅食。与此同时,一些加入者为了增加自己的捕食率可能会不断地监控发现者进而去争夺食物资源。
    6. 当意识到危险时,群体边缘的麻雀会迅速向安全区域移动,以获得更好的位置,位于种群中间的麻雀则会随机走动,以靠近其它麻雀。

    在模拟实验中,我们需要使用虚拟麻雀进行食物的寻找,由n只麻雀组成的种群可表示为如下形式:
    X = [ x 1 1 x 1 2 . . . x 1 d x 2 1 x 2 2 . . . x 2 d . . . . . . . . . . . . x n 1 x n 2 . . . x n d ] (1) X=\left[\begin{matrix} x_1^1&x_1^2&...&x_1^d\\ x_2^1&x_2^2&...&x_2^d\\ ...&...&...&... \\ x_n^1&x_n^2&...&x_n^d\\ \end{matrix}\right]\tag{1} X=x11x21...xn1x12x22...xn2............x1dx2d...xnd(1)
    其中, d d d 表示待优化问题变量的维数, n n n 则是麻雀的数量。那么,所有麻雀的适应度值可以表示为如下形式:
    F x = [ f ( [ x 1 1 x 1 2 . . . x 1 d ] ) f ( [ x 2 1 x 2 2 . . . x 2 d ] ) . . . f ( [ x n 1 x n 2 . . . x n d ] ) ] (2) F_x =\left[\begin{matrix} f([x_1^1&x_1^2&...&x_1^d])\\ f([x_2^1&x_2^2&...&x_2^d])\\ ... f([x_n^1&x_n^2&...&x_n^d]) \end{matrix}\right]\tag{2} Fx=f([x11f([x21...f([xn1x12x22xn2.........x1d])x2d])xnd])(2)
    其中,f 表示适应度值。

    在 SSA 中,具有较好适应度值的发现者在搜索过程中会优先获取食物。此外,因为发现者负责为整个麻雀种群寻找食物并为所有加入者提供觅食的方向。因此,发现者可以获得比加入者更大的觅食搜索范围。根据规则(1)和规则(2),在每次迭代的过程中,发现者的位置更新描述如下:
    X i , j t + 1 = { X i , j . e x p ( − i α . i t e r m a x ) , i f   R 2 < S T X i , j + Q . L , i f   R 2 ≥ S T (3) X_{i,j}^{t+1}=\begin{cases} X_{i,j}.exp(-\frac{i}{\alpha.iter_{max}}),if\, R_2<ST\\ X_{i,j} + Q.L,if\, R_2\geq ST \end{cases}\tag{3} Xi,jt+1={Xi,j.exp(α.itermaxi),ifR2<STXi,j+Q.L,ifR2ST(3)
    其中, t t t 代表当前迭代数, j = 1 , 2 , 3 , . . . , d j =1, 2, 3, . . . , d j=1,2,3,...,d i t e m m a x item_{max} itemmax
    是一个常数,表示最大的迭代次数。 X i j X_{ij} Xij表示第 i i i 个麻雀在第 j j j 维中的位置信息。 α ∈ ( 0 , 1 ] α∈(0, 1] α(0,1]是一个随机数。 R 2 ( R 2 ∈ [ 0 , 1 ] ) R_2(R_2∈[0,1]) R2(R2[0,1]) S T ( S T ∈ [ 0.5 , 1 ] ) ST(ST∈[0.5,1]) ST(ST[0.5,1])分别表示预警值和安全值。 Q Q Q 是服从正态分布的随机数。 L L L 表示一个 1 × d 1×d 1×d 的矩阵,其中该矩阵内每个元素全部为 1。

    R 2 < S T R2< ST R2<ST 时,这意味着此时的觅食环境周围没有捕食者,发现者可以执行广泛的搜索操作。如果 R 2 ≥ S T R2≥ ST R2ST,这表示种群中的一些麻雀已经发现了捕食者,并向种群中其它麻雀发出了警报,此时所有麻雀都需要迅速飞到其它安全的地方进行觅食。

    对于加入者,它们需要执行规则(3)和规则(4)。如前面所描述,在觅食过程中,一些加入者会时刻监视着发现者。一旦它们察觉到发现者已经找到了更好的食物,它们会立即离开现在的位置去争夺食物。如果它们赢了,它们可以立即获得该发现者的食物,否则需要继续执行规则(4)。加入者的位置更新描述如下:
    X i , j t + 1 = { Q . e x p ( X w o r s t − X i , j t i 2 ) , i f   i > n / 2 X P t + 1 + ∣ X i , j − X P t + 1 ∣ . A + . L , o t h e r w i s e (4) X_{i,j}^{t+1}=\begin{cases} Q.exp(\frac{X_{worst}-X_{i,j}^t}{i^2}),if\, i>n/2\\ X_P^{t+1}+ |X_{i,j} - X_P^{t+1}|.A^{+}.L,otherwise \end{cases}\tag{4} Xi,jt+1={Q.exp(i2XworstXi,jt),ifi>n/2XPt+1+Xi,jXPt+1.A+.L,otherwise(4)
    其中, X p X_p Xp是目前发现者所占据的最优位置, X w o r s t X_{worst} Xworst则表示当前全局最差的位置。 A A A表示一个 1 × d 1×d 1×d 的矩阵,其中每个元素随机赋值为 1 或-1,并且 A + = A T ( A A T ) − 1 A^+=A^T(AA^T)^{-1} A+=AT(AAT)1。当i >n/2 时,这表明,适应度值较低的第 i 个加入者没有获得食物,处于十分饥饿的状态,此时需要飞往其它地方觅食,以获得更多的能量。

    在模拟实验中,我们假设这些意识到危险的麻雀占总数量的 10% 到 20%。这些麻雀的初始位置是在种群中随机产生的。根据规则(5),其数学表达式可以表示为如下形式:
    X i , j t + 1 = { X b e s t t + β . ∣ X i , j t − X b e s t t ∣ , i f   f i > f g X i , j t + K . ( ∣ X i , j t − X w o r s t t ∣ ( f i − f w ) + ε ) , i f   f i = f g (5) X_{i,j}^{t+1}=\begin{cases} X_{best}^t + \beta.|X_{i,j}^t - X_{best}^t|,if\, f_i>f_g\\ X_{i,j}^t + K.(\frac{|X_{i,j}^t - X_{worst}^t|}{(f_i -f_w)+\varepsilon}), if\, f_i =f_g \end{cases}\tag{5} Xi,jt+1={Xbestt+β.Xi,jtXbestt,iffi>fgXi,jt+K.((fifw)+εXi,jtXworstt),iffi=fg(5)
    其中,其中 X b e s t X_{best} Xbest是当前的全局最优位置。 β β β 作为步长控制参数,是服从均值为 0,方差为 1 的正态分布的随机数。 K ∈ [ − 1 , 1 ] K∈[-1,1] K[1,1]是一个随机数,fi则是当前麻雀个体的适应度值。 f g f_g fg f w f_w fw分别是当前全局最佳和最差的适应度值。 ε \varepsilon ε 的常数,以避免分母出现零。

    为简单起见,当 f i > f g f_i >f_g fi>fg表示此时的麻雀正处于种群的边缘,极其容易受到捕食者的攻击。 X b e s t X_{best} Xbest表示这个位置的麻雀是种群中最好的位置也是十分安全的。 f i = f g f_i = f_g fi=fg时,这表明处于种群中间的麻雀意识到了危险,需要靠近其它的麻雀以此尽量减少它们被捕食的风险。 K K K 表示麻雀移动的方向同时也是步长控制参数。

    算法流程

    Step1: 初始化种群,迭代次数,初始化捕食者和加入者比列。

    Step2:计算适应度值,并排序。

    Step3:利用式(3)更新捕食者位置。

    Step4:利用式(4)更新加入者位置。

    Step5:利用式(5)更新警戒者位置。

    Step6:计算适应度值并更新麻雀位置。

    Step7:是否满足停止条件,满足则退出,输出结果,否则,重复执行Step2-6;

    2.算法结果

    在这里插入图片描述

    3.参考文献

    [1] Xue J , Shen B . A novel swarm intelligence optimization approach: sparrow search algorithm[J]. Systems ence & Control Engineering An Open Access Journal, 2020, 8(1):22-34.

    4.Matlab代码

    麻雀搜索算法
    改进算法:

    名称说明或者参考文献
    基于反向策略的麻雀搜索算法原创
    基于Tent混沌映射的麻雀搜索算法原创
    基于Logistic混沌映射的麻雀搜索算法原创
    基于Circle混沌映射的麻雀搜索算法原创
    基于Piecewise混沌映射的麻雀搜索算法原创
    基于Chebyshev混沌映射的麻雀搜索算法原创
    基于Sine混沌映射的麻雀搜索算法原创
    基于Singer混沌映射的麻雀搜索算法原创
    基于迭代混沌映射的麻雀搜索算法原创
    基于Sinusoidal混沌映射的麻雀搜索算法原创
    基于随机游走改进的麻雀搜索算法原创
    基于萤火虫改进的麻雀搜索算法原创
    基于精英反向策略的麻雀搜索算法1原创
    基于精英反向策略的麻雀搜索算法2原创
    基于levy飞行改进的麻雀搜索算法原创
    基于自适应t分布的麻雀算法原创
    混沌麻雀[1]吕鑫,慕晓冬,张钧,王震.混沌麻雀搜索优化算法[J/OL].北京航空航天大学学报:1-10[2020-11-16].https://doi.org/10.13700/j.bh.1001-5965.2020.0298.
    融合柯西变异和反向学习的改进麻雀算法[1]毛清华,张强.融合柯西变异和反向学习的改进麻雀算法[J/OL].计算机科学与探索:1-12[2020-12-16].http://kns.cnki.net/kcms/detail/11.5602.tp.20201203.1601.006.html.
    混合正弦余弦算法和Lévy飞行的麻雀算法(ISSA)[1]毛清华,张强,毛承成,柏嘉旋.混合正弦余弦算法和Lévy飞行的麻雀算法[J/OL].山西大学学报(自然科学版):1-6[2021-04-09].https://doi.org/10.13451/j.sxu.ns.2020135.
    基于 Sobol 序列和纵横交叉策略的麻雀搜索算法(SSASC)[1]段玉先,刘昌云.基于 Sobol 序列和纵横交叉策略的麻雀搜索算法[J/OL].计算机应用. https://kns.cnki.net/kcms/detail/51.1307.TP.20210525.1453.002.html
    融合正余弦和柯西变异的麻雀搜索算法(SCSSA)[1]李爱莲,全凌翔,崔桂梅,解韶峰.融合正余弦和柯西变异的麻雀搜索算法[J/OL].计算机工程与应用:1-11[2021-09-09].http://kns.cnki.net/kcms/detail/11.2127.TP.20210806.0937.008.html.
    多策略融合的改进麻雀搜索算法(ISSA)[1]付华,刘昊.多策略融合的改进麻雀搜索算法及其应用[J/OL].控制与决策:1-10[2021-09-09].https://doi.org/10.13195/j.kzyjc.2021.0582.
    基于Logistic回归麻雀算法(MSSA)[1]陈刚,林东,陈飞,陈祥宇.基于Logistic回归麻雀算法的图像分割[J/OL].北京航空航天大学学报:1-14[2021-09-26].https://doi.org/10.13700/j.bh.1001-5965.2021.0268.
    自适应变异麻雀搜索优化算法(AMSSA)[1]唐延强,李成海,宋亚飞,陈晨,曹波.自适应变异麻雀搜索优化算法[J/OL].北京航空航天大学学报:1-14[2021-09-27].https://doi.org/10.13700/j.bh.1001-5965.2021.0282.
    混合策略改进的麻雀搜索算法(MSSA)[1]张伟康,刘升,任春慧.混合策略改进的麻雀搜索算法[J/OL].计算机工程与应用:1-12[2021-08-05].http://kns.cnki.net/kcms/detail/11.2127.TP.20210721.0848.002.html.
    融合多策略的改进麻雀搜索算法(ISSA)[1]张晓萌,张艳珠,刘禄,张硕,熊夫睿.融合多策略的改进麻雀搜索算法[J/OL].计算机应用研究:1-8[2021-12-17].https://doi.org/10.19734/j.issn.1001-3695.2021.09.0412.
    自适应t分布与黄金正弦改进的麻雀搜索算法(tGSSA)[1]张伟康,刘升.自适应t分布与黄金正弦改进的麻雀搜索算法及其应用[J/OL].微电子学与计算机:1-8[2021-12-17].https://doi.org/10.19304/J.ISSN1000-7180.2020-0026.
    分数阶麻雀搜索算法(FDSSA)[1]江妍,马瑜,梁远哲,王原,李光昊,马鼎.基于分数阶麻雀搜索优化OTSU肺组织分割算法[J].计算机科学,2021,48(S1):28-32.
    螺旋探索与自适应混合变异的麻雀搜索(SHSSA)[1]陈功,曾国辉,黄勃,刘瑾.螺旋探索与自适应混合变异的麻雀搜索算法[J/OL].小型微型计算机系统:1-12[2021-12-24].http://kns.cnki.net/kcms/detail/21.1106.tp.20211214.1828.006.html.
    改进搜索机制的单纯形法引导麻雀搜索算法(SMSSA)[1]刘成汉,何庆.改进搜索机制的单纯形法引导麻雀搜索算法[J/OL].计算机工程与科学:1-9[2021-12-24].http://kns.cnki.net/kcms/detail/43.1258.TP.20211223.0930.002.html.
    基于逐维高斯变异的混沌麻雀优化算法(ISSA)[1]楚哲宇,唐秀英,谭庆,张清君.基于逐维高斯变异的混沌麻雀优化算法[J].自动化应用,2021(08):60-63.DOI:10.19769/j.zdhy.2021.08.019.
    基于莱维飞行扰动策略的麻雀搜索算法(ISSA)[1]马卫,朱娴.基于莱维飞行扰动策略的麻雀搜索算法[J].应用科学学报,2022,40(01):116-130.

    算法相关应用matlab代码:

    名称说明或者参考链接
    麻雀优化的BP神经网络(预测)https://blog.csdn.net/u011835903/article/details/112149776
    基于Tent混沌映射改进的麻雀搜索算法SSA优化BP神经网络(预测)-
    基于Sine混沌映射改进的麻雀搜索算法SSA优化BP神经网络(预测)-
    基于Logistic混沌映射改进的麻雀搜索算法SSA优化BP神经网络(预测)-
    麻雀优化的BP神经网络(分类)https://blog.csdn.net/u011835903/article/details/112149394
    基于麻雀搜索算法优化概率神经网络PNN的分类预测https://blog.csdn.net/u011835903/article/details/111496232
    基于麻雀搜索算法优化的Elman神经网络数据预测https://blog.csdn.net/u011835903/article/details/111411127
    基于麻雀搜索算法的极限学习机(ELM)分类算法https://blog.csdn.net/u011835903/article/details/111177850
    基于麻雀搜索算法的极限学习机(ELM)回归预测https://blog.csdn.net/u011835903/article/details/111073635
    基于麻雀算法优化的相关向量机RVM的分类算法https://blog.csdn.net/u011835903/article/details/119005293
    基于麻雀算法优化的相关向量机RVM回归预测算法https://blog.csdn.net/u011835903/article/details/118998966
    基于麻雀算法优化的核极限学习机(KELM)的分类算法https://blog.csdn.net/u011835903/article/details/116851164
    基于麻雀算法优化的核极限学习机(KELM)回归预测https://blog.csdn.net/u011835903/article/details/116849032
    基于麻雀搜索算法优化的广义回归神经网络(GRNN)预测https://blog.csdn.net/u011835903/article/details/110941139
    基于麻雀搜索算法优化的SVM数据分类预测https://blog.csdn.net/u011835903/article/details/110523352
    基于麻雀搜索的PID神经网络解耦控制算法https://blog.csdn.net/u011835903/article/details/110437852
    基于麻雀搜索优化K-means图像分割算法https://blog.csdn.net/u011835903/article/details/109404281
    基于麻雀算法优化的二维最大熵图像阈值分割https://blog.csdn.net/u011835903/article/details/108214713
    基于麻雀算法优化的最大熵多阈值分割https://blog.csdn.net/u011835903/article/details/108203775
    基于麻雀算法的二维Otsu图像阈值分割https://blog.csdn.net/u011835903/article/details/108023193
    麻雀算法优化的otsu多阈值分割https://blog.csdn.net/u011835903/article/details/108019744
    麻雀算法优化脉冲耦合神经网络的图像自动分割https://blog.csdn.net/u011835903/article/details/112909060
    基于麻雀算法优化的Tsallis相对熵图像多阈值分割https://blog.csdn.net/u011835903/article/details/113755585
    基于麻雀搜索算法与双伽马校正的图像自适应增强算法https://blog.csdn.net/u011835903/article/details/109330643
    基于麻雀搜索算法与非完全beta函数的自适应图像增强算法https://blog.csdn.net/u011835903/article/details/109313513
    基于麻雀搜索算法PID参数优化https://blog.csdn.net/u011835903/article/details/109306387
    基于麻雀搜索算法的TSP问题求解https://blog.csdn.net/u011835903/article/details/109587929
    基于麻雀搜索算法无线传感器网络(WSN)覆盖优化https://blog.csdn.net/u011835903/article/details/109262039
    基于麻雀搜索算法的3D无线传感器网络(WSN)覆盖优化https://blog.csdn.net/u011835903/article/details/113834323
    基于麻雀搜索的LMS自适应滤波算法https://blog.csdn.net/u011835903/article/details/110529694
    基于麻雀搜索的路径规划算法https://blog.csdn.net/u011835903/article/details/109100220
    基于麻雀搜搜算法的积分计算算法https://blog.csdn.net/u011835903/article/details/114330697
    基于麻雀搜索算法的工程优化案例(3种)https://blog.csdn.net/u011835903/article/details/114106139
    基于麻雀算法改进的随机森林回归预测算法(SSA-RF)https://blog.csdn.net/u011835903/article/details/121860633
    基于麻雀算法改进的随机森林分类算法(SSA-RF)https://blog.csdn.net/u011835903/article/details/121860734
    麻雀算法改进的深度极限学习机DELM的预测(SSA-DELM)https://blog.csdn.net/u011835903/article/details/123115147
    麻雀算法改进的深度极限学习机DELM的分类(SSA-DELM)https://blog.csdn.net/u011835903/article/details/123091238
    基于麻雀算法优化的Renyi熵图像多阈值分割https://blog.csdn.net/u011835903/article/details/108276355 原理一样只是优化算法部分原理为麻雀
    基于麻雀算法优化的指数熵图像多阈值分割https://blog.csdn.net/u011835903/article/details/108263933 原理一样只是优化算法部分原理为麻雀
    基于麻雀算法优化的灰度熵图像多阈值分割https://blog.csdn.net/u011835903/article/details/108243596 原理一样只是优化算法部分原理为麻雀
    基于麻雀算法优化的对称交叉熵图像多阈值分割https://blog.csdn.net/u011835903/article/details/108241032 原理一样只是优化算法部分原理为麻雀
    基于麻雀算法优化的最小交叉熵图像多阈值分割https://blog.csdn.net/u011835903/article/details/108240562 原理一样只是优化算法部分原理为麻雀
    基于麻雀算法优化的二维最大熵图像阈值分割https://blog.csdn.net/u011835903/article/details/108214713 原理一样只是优化算法部分原理为麻雀
    基于麻雀算法的二维Otsu图像阈值分割https://blog.csdn.net/u011835903/article/details/108023193 原理一样只是优化算法部分原理为麻雀
    基于麻雀搜索算法的同步优化特征选择https://blog.csdn.net/u011835903/article/details/121103001
    基于麻雀算法的投影寻踪模型(SSA-PP)https://blog.csdn.net/u011835903/article/details/121120392
    基于麻雀算法改进的无线传感器网络Dv-hop定位算法https://blog.csdn.net/u011835903/article/details/121334401
    基于麻雀算法的无人机航迹规划https://blog.csdn.net/u011835903/article/details/122926764

    5.Python代码

    麻雀搜索算法
    改进算法:

    名称说明或者参考文献
    基于反向策略的麻雀搜索算法原创
    基于Tent混沌映射的麻雀搜索算法原创
    基于Logistic混沌映射的麻雀搜索算法原创
    基于Circle混沌映射的麻雀搜索算法原创
    基于Piecewise混沌映射的麻雀搜索算法原创
    基于Chebyshev混沌映射的麻雀搜索算法原创
    基于Sine混沌映射的麻雀搜索算法原创
    基于Singer混沌映射的麻雀搜索算法原创
    基于迭代混沌映射的麻雀搜索算法原创
    基于Sinusoidal混沌映射的麻雀搜索算法原创
    基于随机游走改进的麻雀搜索算法原创
    基于萤火虫改进的麻雀搜索算法原创
    基于精英反向策略的麻雀搜索算法1原创
    基于精英反向策略的麻雀搜索算法2原创
    基于levy飞行改进的麻雀搜索算法原创
    基于自适应t分布的麻雀算法原创
    混沌麻雀[1]吕鑫,慕晓冬,张钧,王震.混沌麻雀搜索优化算法[J/OL].北京航空航天大学学报:1-10[2020-11-16].https://doi.org/10.13700/j.bh.1001-5965.2020.0298.
    混合正弦余弦算法和Lévy飞行的麻雀算法(ISSA)[1]毛清华,张强,毛承成,柏嘉旋.混合正弦余弦算法和Lévy飞行的麻雀算法[J/OL].山西大学学报(自然科学版):1-6[2021-04-09].https://doi.org/10.13451/j.sxu.ns.2020135.

    算法相关应用Python代码:

    名称说明或者参考文献
    基于麻雀算法的SVM分类(SSA-SVM)https://blog.csdn.net/u011835903/article/details/110523352
    基于麻雀算法的SVM回归预测(SSA-SVM)https://blog.csdn.net/u011835903/article/details/110630270
    基于麻雀搜索算法的极限学习机(ELM)分类算法(SSA-ELM)https://blog.csdn.net/u011835903/article/details/111177850
    基于麻雀搜索算法的极限学习机(ELM)回归预测算法(SSA-ELM)https://blog.csdn.net/u011835903/article/details/111073635
    基于麻雀算法的无线传感器网(WSN)覆盖优化(SSA-WSN)https://blog.csdn.net/u011835903/article/details/109262039
    基于麻雀算法改进的随机森林分类算法(SSA-RF)https://blog.csdn.net/u011835903/article/details/121860734
    基于麻雀算法改进的随机森林回归预测算法(SSA-RF)https://blog.csdn.net/u011835903/article/details/121860633
    更多相关内容
  • 麻雀搜索算法.rar

    2020-04-21 15:09:17
    麻雀搜索算法是最新的群智能优化算法,里面有相关文章和代码,可以结合自身课题进行研究,值得推荐,亲用优化效果非常的好
  • 基于麻雀搜索算法的函数寻优算法

    千次阅读 多人点赞 2021-05-28 10:54:38
    麻雀搜索算法(Sparrow Search Algorithm, SSA)是2020年提出的一种新兴的元启发式算法,它与粒子群算法、蜻蜓优化算法等同属于基于群体的社会化特征优化的群智能算法。该算法通过不断更新个体位置,模拟麻雀觅食和反...

    一、理论基础

    麻雀搜索算法(Sparrow Search Algorithm, SSA)是2020年提出的一种新兴的元启发式算法,它与粒子群算法、蜻蜓优化算法等同属于基于群体的社会化特征优化的群智能算法。该算法通过不断更新个体位置,模拟麻雀觅食和反捕食行为。相比传统算法,麻雀搜索算法的结构简单、易于实现,且控制参数较少,局部搜索能力较强。该算法在单峰、多峰等基准函数上的表现优于粒子群算法、蚁群算法等传统算法。
    在麻雀搜索算法中,将个体区分为发现者、跟随者和警戒者,每个个体位置对应一个解。根据算法设定,警戒者所占种群比例10%~20%,而发现者和跟随者是动态变化的, 即一只个体成为发现者必然意味着另一只个体将成为跟随者。按照分工划分,发现者主要为整个种群提供觅食方向和区域,跟随者则是跟随发现者进行觅食,警戒者负责对于觅食区域的监视。在觅食过程中,通过不断更新三者位置,完成资源的获取。
    设种群中有 n n n只麻雀,则由所有个体组成的种群可表示为 X = [ x 1 , x 2 , ⋯   , x n ] T X=[x_1,x_2,\cdots,x_n]^T X=[x1,x2,,xn]T,个体各自对应的适应度函数为 F = [ f ( x 1 ) , f ( x 2 ) , ⋯   , f ( x n ) ] T F=[f(x_1),f(x_2),\cdots,f(x_n)]^T F=[f(x1),f(x2),,f(xn)]T。具体表示为: X = [ x 1 , 1 x 1 , 2 ⋯ ⋯ x 1 , d x 2 , 1 x 2 , 2 ⋯ ⋯ x 2 , d ⋮ ⋮ ⋮ ⋮ ⋮ x n , 1 x n , 2 ⋯ ⋯ x n , d ] (1) X=\begin{bmatrix} x_{1,1} & x_{1,2} & \cdots & \cdots & x_{1,d} \\x_{2,1} & x_{2,2} & \cdots & \cdots & x_{2,d} \\\vdots & \vdots & \vdots & \vdots & \vdots\\ x_{n,1} & x_{n,2} & \cdots & \cdots & x_{n,d} \\ \end{bmatrix}\tag{1} X=x1,1x2,1xn,1x1,2x2,2xn,2x1,dx2,dxn,d(1) F = [ f ( [ x 1 , 1 x 1 , 2 ⋯ ⋯ x 1 , d ] ) f ( [ x 2 , 1 x 2 , 2 ⋯ ⋯ x 2 , d ] ) ⋮ f ( [ x n , 1 x n , 2 ⋯ ⋯ x n , d ] ) ] (2) F=\begin{bmatrix} f(\begin{bmatrix}x_{1,1} & x_{1,2} & \cdots & \cdots & x_{1,d}\end{bmatrix}) \\f(\begin{bmatrix}x_{2,1} & x_{2,2} & \cdots & \cdots & x_{2,d}\end{bmatrix})\\ \vdots\\ f(\begin{bmatrix}x_{n,1} & x_{n,2} & \cdots & \cdots & x_{n,d}\end{bmatrix}) \end{bmatrix}\tag{2} F=f([x1,1x1,2x1,d])f([x2,1x2,2x2,d])f([xn,1xn,2xn,d])(2)

    1、发现者位置更新

    发现者的位置更新方式如下: x i , j t + 1 = { x i , j t ⋅ exp ⁡ ( − i α × i t e r m a x ) , R 2 < S T x i , j t + Q ⋅ L ,      R 2 ≥ S T (3) x_{i,j}^{t+1}=\begin{dcases}x_{i,j}^t\cdot \exp(\frac{-i}{\alpha×iter_{max}}),R_2<ST\\[2ex]x_{i,j}^t+Q\cdot L,\quad\quad\quad\quad \,\,\,\,R_2≥ST\end{dcases}\tag{3} xi,jt+1=xi,jtexp(α×itermaxi),R2<STxi,jt+QL,R2ST(3)其中, t t t表示当前迭代次数, x i , j t x_{i,j}^t xi,jt表示在第 t t t代中第 i i i只麻雀在第 j j j维的位置, α ∈ ( 0 , 1 ) \alpha∈(0,1) α(0,1) i t e r m a x iter_{max} itermax是最大迭代次数, R 2 R_2 R2表示报警值, S T ST ST表示安全阈值, Q Q Q是服从正态分布的随机数, L L L 1 × dim ⁡ 1×\dim 1×dim的全1矩阵, dim ⁡ \dim dim表示维度。发现者位置更新方式可总结如下:当 R 2 < S T R_2<ST R2<ST时,意味着觅食区域周围没有捕食者,发现者可以广泛搜索食物;当 R 2 ≥ S T R_2≥ST R2ST时,意味着捕食者出现,所有发现者都需要飞往安全区域。

    2、跟随者位置更新

    跟随者的位置更新方式如下: x i , j t + 1 = { Q ⋅ exp ⁡ ( x w o r s t t − x i , j t i 2 ) ,    i > n 2 x P t + 1 + ∣ x i , j t − x P t + 1 ∣ ⋅ A + ⋅ L , i ≤ n 2 (4) x_{i,j}^{t+1}=\begin{dcases}Q\cdot\exp(\frac{x_{worst}^t-x_{i,j}^t}{i^2}),\quad\quad\quad\,\, i>\frac n2\\[2ex]x_P^{t+1}+|x_{i,j}^t-x_P^{t+1}|\cdot \boldsymbol A^+\cdot L,\quad i≤\frac n2\end{dcases}\tag{4} xi,jt+1=Qexp(i2xworsttxi,jt),i>2nxPt+1+xi,jtxPt+1A+L,i2n(4)其中, x w o r s t t x_{worst}^t xworstt表示第 t t t代适应度最差的个体位置, x P t + 1 x_P^{t+1} xPt+1表示第 t + 1 t+1 t+1代中适应度最佳的个体位置。 A \boldsymbol A A表示 1 × dim ⁡ 1×\dim 1×dim的矩阵,矩阵中每个元素随机预设为-1或1, A + = A T ( A A T ) − 1 \boldsymbol A^+=\boldsymbol{A^T}\boldsymbol{(AA^T)^{-1}} A+=AT(AAT)1。跟随者位置更新方式可总结为:当 i > n 2 i>\frac n2 i>2n时,表示第 i i i个加入者的适应度较低,没有同发现者竞争食物的资格,需要飞往其他区域觅食;当 i ≤ n 2 i≤\frac{n}2 i2n时,加入者将在最优个体 x P x_P xP近觅食。

    3、警戒者位置更新

    警戒者位置更新方式如下: x i , j t + 1 = { x b e s t t + β ⋅ ∣ x i , j t − x b e s t t ∣ ,    f i ≠ f g x b e s t t + k ⋅ ( x i , j t − x b e s t t ∣ f i − f w ∣ + ε ) , f i = f g (5) x_{i,j}^{t+1}=\begin{dcases}x_{best}^t+\beta\cdot|x_{i,j}^t-x_{best}^t|,\quad\quad\,\, f_i≠f_g\\[2ex]x_{best}^t+k\cdot(\frac{x_{i,j}^t-x_{best}^t}{|f_i-f_w|+\varepsilon}),\quad f_i=f_g\end{dcases}\tag{5} xi,jt+1=xbestt+βxi,jtxbestt,fi=fgxbestt+k(fifw+εxi,jtxbestt),fi=fg(5)其中, x b e s t t x_{best}^t xbestt表示第 t t t代中全局最优位置, β \beta β为控制步长,服从均值为0,方差为1的正态分布, k ∈ [ − 1 , 1 ] k∈[-1,1] k[1,1] ε \varepsilon ε设置为常数,用以避免分母为0。 f i f_i fi表示当前个体的适应度值, f g f_g fg f w f_w fw表示目前全局最优和最差个体的适应度值。警戒者位置更新方式可总结为:当 f i ≠ f g f_i≠f_g fi=fg时,意味着该个体处于种群外围,需要采取反捕食行为,不断变换位置获得更高 的适应度;当 f i = f g f_i=f_g fi=fg时,意味着该个体处于种群中心,它将不断接近附近的同伴,以此远离危险区域。

    4、SSA算法伪代码

    在这里插入图片描述

    图1 SSA算法的基本框架

    二、仿真实验与分析

    为了使算法更具说服力,在所有情况下,我们对每个测试函数进行30次独立试验。在每个实验中,迭代的最大次数为1000,种群大小设置为100( n = 100 n=100 n=100)。GWO的参数设置如下: a a a的值从2线性减少到0, r 1 , r 2 r_1,r_2 r1,r2 [ 0 , 1 ] [0,1] [0,1]中的随机向量;PSO的参数为 c 1 = c 2 = 1.49445 , w = 0.729 c_1=c_2=1.49445,w=0.729 c1=c2=1.49445,w=0.729;GSA的参数为 G 0 = 100 , α = 20 G_0=100,\alpha=20 G0=100,α=20。SSA的参数设置如下:发现者数量和 S D SD SD分别占20%和10%, S T = 0.8 ST=0.8 ST=0.8。以文献[1]的F1、F2、F3为例。
    下图为对比曲线。
    在这里插入图片描述在这里插入图片描述在这里插入图片描述最大值、最小值、平均值及标准差显示如下:

    函数:F1
    GWO:最大值: 1.9014e-90,最小值:1.1467e-93,平均值:2.6184e-91,标准差:5.3549e-91
    PSO:最大值: 25.6849,最小值:2.8582,平均值:9.0364,标准差:5.9129
    GSA:最大值: 6.5868e-18,最小值:2.3286e-18,平均值:4.0924e-18,标准差:1.0661e-18
    SSA:最大值: 0,最小值:0,平均值:0,标准差:0
    函数:F2
    GWO:最大值: 8.0552e-52,最小值:4.8965e-54,平均值:1.5053e-52,标准差:2.105e-52
    PSO:最大值: 14.9366,最小值:4.5229,平均值:8.2907,标准差:2.6433
    GSA:最大值: 1.2197e-08,最小值:8.179e-09,平均值:1.0214e-08,标准差:9.821e-10
    SSA:最大值: 9.1086e-306,最小值:0,平均值:3.0362e-307,标准差:0
    函数:F3
    GWO:最大值: 1.7551e-17,最小值:1.049e-25,平均值:7.2717e-19,标准差:3.1948e-18
    PSO:最大值: 255.9549,最小值:38.1862,平均值:112.098,标准差:53.1931
    GSA:最大值: 215.1596,最小值:44.459,平均值:106.1498,标准差:36.8177
    SSA:最大值: 0,最小值:0,平均值:0,标准差:0
    

    结果表明,该算法在搜索精度、收敛速度和稳定性等方面均优于现有算法。

    代码下载链接:https://download.csdn.net/download/weixin_43821559/85415931

    三、参考文献

    [1] Jiankai Xue, Bo Shen. A novel swarm intelligence optimization approach: sparrow search algorithm[J]. Systems Science & Control Engineering, 2020, 8(1): 22-34.
    [2] 段玉先, 刘昌云. 基于Sobol序列和纵横交叉策略的麻雀搜索算法[J]. 计算机应用, 2022, 42(1): 36-43.

    展开全文
  • 经典搜索算法总结

    千次阅读 2021-05-30 21:09:51
    前言0x01 搜索问题的形式化0x02 树搜索和图搜索0x03 搜索算法的评估0x04 盲目搜索算法0x04.01 宽度优先搜索算法BFS0x04.02 一致代价搜索算法UCS0x04.03 深度优先搜索算法DFS 前言 搜索问题是在解决各类问题时不可...

    前言

    搜索问题是在解决各类问题时不可避免的重点难点,很多问题的求解过程都可以转变为搜索问题。比如,对于以下罗马尼亚问题,希望找到一条路径使得从城市 Arad 到城市 Bucuresti 的路径最短,这就是一个经典的搜索问题,在数据结构课程中,我们都知道使用 Dijkstra 算法来求得最优解,受《人工智能 一种现代化的方法》这本书的影响,本博客则以此为基石通过更一般的方法来讨论通用的搜索问题的求解思路。
    在这里插入图片描述


    0x1 搜索问题的形式化

    一个搜索问题可以通过五个元素给出形式化的定义:

    • 初始状态。状态用 s 表述,初始状态也是状态的一种,上述罗马尼亚问题的初始状态可以描述为 In(Arad)
    • 可能的行动。行动用 a 表述,对于一个特殊状态 sACTIONS(s) 返回在状态 s 下可以执行的动作集合。例如,在状态 In(Arad) 下可能的行动为: {Go(Sibiu), Go(Timisoara), Go(Zerind)}
    • 转移模型。转移模型用 RESULT(s, a) 表述,表示在状态 s 下执行行动 a 后达到的状态。通常也用术语后继状态来表示从一给定状态出发通过单步行动可以到达的状态集合。例如:RESULT(In(Arad), Go(Zerind)) = In(Zerind)
    • 目标测试。确定给定的状态是不是目标状态。在罗马尼亚问题中,目标状态集是一个单元素集合 {In(Bucuresti)}
    • 路径代价。采用行动 a 从状态 s 走到状态 s’ 所需要的单步代价表述为 c(s,a,s'),路径代价就代表从初始状态到目标状态的单步代价总和。

    通过形式化的定义搜索问题,则搜索问题的解描述为一组让初始状态转变为目标状态的行动序列,而搜索问题的最优解描述为使得路径代价最小的一组让初始状态转变为目标状态的行动序列。


    0x2 树搜索和图搜索

    在对问题进行形式化后,需要对问题求解,而一个解就是一个行动序列,所以搜索算法的工作的就是考虑各种可能的行动序列。可能的行动序列从搜索树中根结点的初始状态出发,连线表示行动,结点对应问题的状态空间中的状态。

    树搜索算法
    例如在罗马尼亚问题中,从父结点 In(Arad) 出发得到三个子结点:In(Sibiu)In(Timisoara)In(Zerind),接下来需要继续从这三种子结点中选择其一继续考虑,假设我们选择 In(Sibiu) ,则检查它是否是目标状态,如果不是目标状态,则继续扩展它得到四个状态:In(Arad)In(Fagaras)In(Oradea)In(Rimnicu Vikea)。继续按此方式拓展 In(Timisoara)In(Zerind) 。如果未找到目标状态,则继续对叶子结点作同样的操作,如下图:
    在这里插入图片描述

    此时引入两个概念:
    frontier 结点:frontier 结点是指所有还没有扩展的搜索结点
    explored 结点:explored 结点是指所有已经扩展的搜索结点

    注意到在拓展 In(Sibiu) 的时候,将 In(Arad) 结点也加入了 frontier 集合,而此时 In(Arad) 结点已经是拓展过的结点,已经加入了 explored 集合。同时在扩展 In(Zerind) 结点的时候,将 In(Oradea) 结点也加入了 frontier 集合,而此时 In(Oradea) 结点本身已经在 frontier 集合中了,这个特别也是树搜索的精髓所在。树搜索的算法伪代码如下:
    在这里插入图片描述
    图搜索算法
    对于上述罗马尼亚问题,采用图搜索算法生成的树如下:
    在这里插入图片描述
    在图搜索算法中,在扩展的时候如果遇到已经在 explored 集合中的结点或已经在 frontier 集合中的结点,则不将该结点拓展进 frontier 集合,这也是其与树搜索算法的主要区别。图搜索的算法伪代码如下:
    在这里插入图片描述


    0x3 搜索算法的评估

    通常一个搜索算法用三个指标来进行评估:

    • 完备性:当问题有解时,这个算法是否可以保证找到解?
    • 最优性:当问题有解时,这个算法是否可以找到使得路径代价最小的解?
    • 复杂性:时空复杂度。

    在搜索算法中,是什么决定了搜索策略?
    由于搜索算法重复的从 frontier 集合中选择和移除一个结点,并且拓展该结点并且将拓展结点插入到 frontier 集合中。如果每次从 frontier 集合的固定位置选取结点,则搜索策略由结点在 frontier 中的顺序决定


    0x4 盲目搜索策略

    盲目搜索算法不会考虑结点离目标有多远,除了问题定义中提供的状态信息外没有任何其他附加信息!

    0x4.1 宽度优先搜索算法BFS

    宽度优先搜索算法(图搜索)的思路就和数据结构中的 BFS 是一个东西。其首先在 frontier 集合中找到最先进入该集合的结点,然后将该结点加入到 explored 集合,同时拓展该节点得到他的每个子结点,对于每个子结点,如果该子结点不在 frontier 集合和 explored 集合中且不是要找到目标结点,则将子结点加入到 frontier 集合中,如此循环直到 frontier 集合为空或者找到目标结点为止。BFS(图搜索)算法伪代码如下:
    在这里插入图片描述
    显然提前测试可以减少遍历的结点数,如果等到从 frontier 集合中弹出时再测试,那么需要拓展很多不必要的结点。通过将 frontier 集合设计成队列,采用先进先出的策略则可以实现 BFS。
    BFS 算法评估(设分支因子为 b,最浅的目标结点的深度为 d):

    • 完备性:当树的分支因子 b 是有限的,则算法是完备的。
    • 最优性:如果路径代价是基于结点深度的非递减函数,则算法是最优的,否则不具备最优性。
    • 复杂性:显然时空复杂度均为 O(bd)

    0x4.2 一致代价搜索算法UCS

    一致代价搜索算法(图搜索)的思想就类似于 Dijkstra 算法。其首先在 frontier 集合中找到当前代价最低的结点,判断该结点是否是目标结点,如果是,则返回解,否则将该结点加入到 explored 集合中,然后拓展该结点得到他的每个子结点。对于每个子结点,如果该子结点不在 frontier 集合和 explored 集合中,则将该子结点加入到 frontier 集合中;否则如果该子结点在 frontier 集合中,但是其代价比已经在 frontier 集合中的低,则用新生成的子结点代替原来 frontier 集合的子结点。UCS(图搜索)算法伪代码如下:
    在这里插入图片描述
    UCS 在结点被拓展时才进行目标检测,这是与 BFS 最大的区别,因为第一次生成的目标的结点可能在次优路径上。通过将 frontier 集合设计成优先级队列,则可以实现 UCS。
    UCS 算法评估(设分支因子为 b,某个小的正值 ξ,最优解的代价 C*):

    • 完备性:如果存在零代价的行动则可能陷入死循环,但如果每一步的代价都大于等于 ξ,则算法是完备的。
    • 最优性:显然具有最优性
    • 复杂性:时空复杂度均为 O(b^(1+ ⌊ C ∗ / ξ ⌋ \lfloor C^*/ξ \rfloor C/ξ))

    0x4.3 深度优先搜索算法DFS

    深度优先搜索算法(图搜索)的思路类似于数据结构中的DFS。其基本思想是首先在 frontier 集合中找到最后进入该集合的结点,然后将该结点加入到 explored 集合,同时拓展该节点得到他的每个子结点,对于每个子结点,如果该子结点不在 frontier 集合和 explored 集合中且不是要找到目标结点,则将子结点加入到 frontier 集合中,如此循环直到 frontier 集合为空或者找到目标结点为止。DFS 和 BFS 最大的区别在于对 frontier 集合中结点的选取,BFS 中对结点的选取符合先进先出的策略,而 DFS 中对结点的选取则符合先进后出的策略,所以 DFS 可以用栈来实现其 frontier 集合。DFS 算法有一个很重要的特别就是其及其依赖采取的是树搜索还是图搜索,因为树搜索每次都可能会加入重复的结点,这样就会导致在两个重复的结点之间无线循环。
    DFS 算法评估(设分支因子为 b,最浅的目标结点的深度为 d,最深的叶子结点为 m):

    • 完备性:对于树搜索,DFS 总是不完备的;而对于图搜索,DFS 在有限状态空间下是完备的,而在无限状态空间下是不完备的。
    • 最优性:显然不是最优的
    • 复杂性:时间复杂度为 O(bm),空间复杂度为 O(bm),可见其空间复杂度比上述两种搜索小很多,这也是深度优先搜索最大的优势。

    0x4.4 深度受限搜索DLS

    对于无限状态空间深度优先搜索算法总是会失败,而这个问题可以通过对深搜设定界限 l 来避免,也就是说在深搜的,当深度达到了 l ,则采取舍弃更深结点的策略。其算法可以采用基于递归的方式来实现,算法的伪代码如下:
    在这里插入图片描述
    DLS 算法评估(设分支因子为 b,限定的深度为 l,最浅的目标结点的深度为 d):

    • 完备性:显然当 l < d 的时候,DLS 则总是不完备的。
    • 最优性:即使当 l > d 的时候,根据 DFS 算法,DLS 也不是最优的。
    • 复杂性:时间复杂度为 O(bl),空间复杂度为 O(bl)

    0x4.5 迭代加深搜索IDS

    在 DLS 算法中,我们无法选取一个合适的深度 l 来求解,这就是 IDS 的动机,在未找到解之前不断的增加 l ,迭代的使用 DLS 算法,当 l 达到最浅的目标结点的深度 d 时,则可以求出解。其算法伪代码如下:
    在这里插入图片描述
    IDS 算法评估(设分支因子为 b,限定的深度为 l,最浅的目标结点的深度为 d):

    • 完备性:当分支因子是有限的的时候,IDS 是完备的
    • 最优性:类似于宽度优先搜索算法,如果路径代价是基于结点深度的非递减函数,则算法是最优的。
    • 复杂性:时间复杂度为 O(bd),空间复杂度为 O(bd)

    0x4.6 双向搜索算法

    双向搜索算法思想则是同时运行两个搜索——一个从初始状态向前搜索同时另外一个从目标状态向后搜索——希望他们在中间某个结点相遇,此时搜索停止。理由是,比如两边都采用宽度优先搜索,则显然 bd/2+bd/2 要远小于 bd

    0x4.7 六种搜索算法的对比

    在这里插入图片描述


    0x5 启发式搜索策略

    在盲目搜索策略中,往往不考虑结点离目标有多远,也就是说,在搜索的过程中,并不考虑目标的状态对当前搜索行为的影响,而仅仅依赖于当前的状态;比如在罗马尼亚问题中,从城市 Arad 到城市 Bucuresti 的搜索,仅仅只考虑在当前状态下可能导致的代价,该策略虽然能搜索到最优解,但是在搜索过程中可能会有很多不必要的操作,因为搜索的结果只关注那条最优的路径,但是实际在搜索的过程中可能会搜索到与最优路径无关的结点。而启发式搜索策略则不一样,他会考虑目标状态对当前状态的影响,这样做使得在搜索的过程中更大的可能搜索和最优路径相关的状态,减少不必要的搜索,增加搜索的效率,比如说在罗马尼亚问题中,可以在考虑代价的同时,还考虑当前结点离目标结点的直线距离来选取下一个要拓展的结点,而这个直线距离就作为启发式的信息来帮助搜索的决策,以此更快地搜索到最优路径。
    在启发式搜索中,通常用 g(n) 表示结点 n 当前的代价,用 h(n) 表示启发函数,一般来说 h(n) = 结点 n 到目标结点的最小代价路径的代价估计值(比如在罗马尼亚问题中可以用 AradBucuresti 的直线距离来作为从 AradBucuresti 的最小代价路径的代价估计值),用 f(n) 作为选择结点的代价评估值,f(n)=g(n)+h(n) ,当 f(n) 越小,则代表结点越优;启发式搜索对扩展结点的选择同时依赖于 g(n) 和 h(n),对于 h(n) 较小的结点,我们可以认为该结点会让我们离目标结点更近,所以 h(n) 作为启发式的信息能帮助我们在搜索的时候做出决策。

    0x5.1 贪婪最佳优先搜索GBFS

    贪婪最佳优先搜索算法试图扩展离目标最近的结点,理由是这样可能可以很快找到解,因此,它只用启发式信息,即 f(n)=h(n)。还是对于上述的罗马尼亚问题,通过 GBFS 算法求解的路径如下,可见该算法并不是最优的。
    在这里插入图片描述
    GBFS 算法评估(设分支因子为 b,最深的叶子结点为 m):

    • 完备性:当状态空间是无限的时候,GBFS 是不完备的;当状态空间是有限的,图搜索的 GBFS 算法是完备的,而树搜索的 GBFS 算法是不完备的。
    • 最优性:显然不是最优的。
    • 复杂性:时间复杂度为 O(bm),空间复杂度为 O(bm),因为要保存所有的结点在内存中。

    0x5.2 A*搜索

    在 GBFS 算法中,仅仅采用启发式作为评估值,导致不能求到最优解,A* 搜索算法同时考虑到代价,以期解决 GBFS 算法中的问题,因此 A* 搜索采用的代价评估值 f(n) 为 h(n) 与 g(n) 的和,其算法伪代码的实现如下:
    在这里插入图片描述
    A* 算法一定能找到最优的路径吗?考虑如下的例子:
    在这里插入图片描述
    假设从 S 走到 G ,那么在 S 结点扩展后,frontier 里面剩下 A(其代价估计 f(A) 为 7)和 G (其代价估计 f(G) 为 5),那么根据 A* 算法,会从 frontier 里面选取 G,此时得到解,但可以发现在这种情况下显然求到的不是最优解,这是因为在 A 结点出其启发式的值过于高,明显的大于其到 G 结点的真是代价,导致产生不准确的估计,所以我们的思路就是降低 A 结点的 h 到一个合适的值,在此处若 h(A) 比 4 小的话则可以根据 A* 算法求到最有解。此处引入一个新的概念——可采纳性

    • 可采纳性:假设 h*(N) 是从 N 结点到目标结点的最优路径的代价, 当启发式函数 h(N) 满足以下不等式的时候,我们称该 h(N) 是可采纳的 (admissible) ——0 ≤ \le h(N) ≤ \le h*(N)

    在引入可采纳性后,A* 算法在树搜索和图搜索下都具有最优性吗?同样考虑以下的例子:
    在这里插入图片描述
    该问题的启发式函数是可采纳的,假设从 A 走到 E,可以发现在树搜索的情况下找到最优解,而在图搜索的情况下却没有找到最优解。这是因为图搜索在遇到已经加入到 explored 集合的结点的时候,会直接不考虑该结点,导致可能不能修正之前扩展带来的错误,比如在上例中,树搜索在扩展右边的 D 结点后,在扩展 B 结点的时候将左边的 D 结点加入到了 frontier 里面,从而有机会修正一开始扩展的右边的 D 结点,使得算法找到最优解;而图搜索由于在第一次扩展 D 结点后,其加入到 explored 结点,导致第二次遇到估计代价更低的 D 结点时,直接将其抛弃而不加入到 frontier 结点,所以会找不到最优解。从这里可以看出,在图搜索算法中,如果结点被加入到了 explored 集合,则算法认为当前在 explored 集合中的路径一定会是最优路径的子路径(类似于 UCS 算法),其实并不是,这就导致无法像树搜索那行修正路径导致无法找到最优解。但是,如果给启发式函数加入比可采纳性更强的约束,会不会使得图搜索也是最优的呢?此处引入一个新的概念——一致性

    • 一致性:如果对于每个结点 N 和通过任一行动 a 生成的 N 的每个后继结点 N’,从结点 N 到达目标的估计代价不大于从 N 到 N’ 的单步代价与从 N’ 到达目标的估计代价之和,我们称启发式函数 h(N) 具有一致性 。即满足不等式 —— h(N) ≤ \le c(N, a, N’)+h(N’) 。显然一致性会使得启发式函数更小,也就说一致的启发式函数一定是可采纳的。

    当启发式函数满足一致性的时候,则 A* 图搜索算法是最优的。

    A* 算法评估(设 C* 是最优解路径的代价值,分支因子为 b,最浅的目标结点的深度为 d):

    • 完备性: A* 算法会扩展所有代价评估值 f(n) 小于 C* 的结点,但不会扩展代价评估值 f(n) 大于 C* 的结点,所以当代价小于等于 C* 的结点是有穷的,则 A* 算法是完备的。
    • 最优性:A* 算法的最优性依赖于其是树搜索还是图搜索,启发式函数是否是可采纳的,一致的。如下图:

    在这里插入图片描述

    • 复杂性:在所有的可以找到最优解的搜索算法里面,A* 搜索的效率是最高的,因为这些算法里面他们都会扩展所有代价评估值 f(n) 小于 C* 的结点,但是 A* 算法一定不会扩展代价评估值 f(n) 大于 C* 的结点,这样使得 A* 算法访问的结点更少,求解的速度更快。时间复杂度和空间复杂度为 O(bd)

    由以上讨论可知,A* 算法对于任何给定的一致的启发式函数都是效率最优的,所以设计 A* 算法,最关键的就是设计启发式函数 h(n) 。

    既然让启发式函数值更小,会让 A* 算法更可能达到一致性,那是不是启发式函数值越小越好呢?显然不是,对于两个一致的启发式函数 h1 和 h2 ,若 h1(N) > h2(N) ,我们则称 h1 更准确,采用 h1 会使得求解过程更快。也就是说我们期望的启发式函数,是在满足一致性的前提下,越大越好!!具体的设计启发式函数的时候可以从松弛问题出发,也可以从子问题出发,也可以从学习的角度出发,具体细节的在此处就不讨论了(逃),可以参考由我们任课老师翻译的 AI 原理神书 —— 《人工智能 一种现代的方法》!

    展开全文
  • 最优化算法 matlab 一维搜索 多维搜索
  • 广度优先搜索算法

    万次阅读 多人点赞 2019-04-25 13:26:58
    广度优先搜索算法(Breadth-First Search,BFS)是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验...

    一、简介

    广度优先搜索算法(Breadth-First Search,BFS)是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。

    广度优先搜索让你能够找出两样东西之间的最短距离,不过最短距离的含义有很多!使用广度优先搜索可以:

    1. 编写国际跳棋AI,计算最少走多少步就可获胜;
    2. 编写拼写检查器,计算最少编辑多少个地方就可将错拼的单词改成正确的单词,如将READED改为READER需要编辑一个地方;
    3. 根据你的人际关系网络找到关系最近的医生。

    二、例子

    假设你居住在旧金山,要从双子峰前往金门大桥。你想乘公交车前往,并希望换乘最少。可乘坐的公交车如下。

    为找出换乘最少的乘车路线,你将使用什么样的算法?
    一步就能到达金门大桥吗?下面突出了所有一步就能到达的地方。

    金门大桥未突出,因此一步无法到达那里。两步能吗?

    金门大桥也未突出,因此两步也到不了。三步呢?

    金门大桥突出了!因此从双子峰出发,可沿下面的路线三步到达金门大桥。

     还有其他前往金门大桥的路线,但它们更远(需要四步)。这个算法发现,前往金门大桥的最短路径需要三步。这种问题被称为最短路径问题(shorterst-path problem)。你经常要找出最短路径,这可能是前往朋友家的最短路径,也可能是国际象棋中把对方将死的最少步数。解决最短路径问题的算法被称为广度优先搜索。要确定如何从双子峰前往金门大桥,需要两个步骤。
    (1) 使用图来建立问题模型。
    (2) 使用广度优先搜索解决问题。
    下面介绍什么是图,然后再详细探讨广度优先搜索。

    三、图

    图是由顶点的有穷非空集合和顶点之间边的集合组成,通过表示为G(V,E),其中,G标示一个图,V是图G中顶点的集合,E是图G中边的集合。

    无边图:若顶点Vi到Vj之间的边没有方向,则称这条边为无项边(Edge),用序偶对(Vi,Vj)标示。

    对于下图无向图G1来说,G1=(V1, {E1}),其中顶点集合V1={A,B,C,D};边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}:

    有向图:若从顶点Vi到Vj的边是有方向的,则成这条边为有向边,也称为弧(Arc)。用有序对(Vi,Vj)标示,Vi称为弧尾,Vj称为弧头。如果任意两条边之间都是有向的,则称该图为有向图。

    有向图G2中,G2=(V2,{E2}),顶点集合(A,B,C,D),弧集合E2={<A,D>,{B,A},<C,A>,<B,C>}.

    权:有些图的边和弧有相关的数,这个数叫做权。这些带权的图通常称为网。

    四、广度优先搜索算法

    假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。

    这种查找很简单。首先,创建一个朋友名单。

     然后,依次检查名单中的每个人,看看他是否是芒果销售商。

     假设你没有朋友是芒果销售商,那么你就必须在朋友的朋友中查找。

     检查名单中的每个人时,你都将其朋友加入名单。

     这样一来,你不仅在朋友中查找,还在朋友的朋友中查找。别忘了,你的目标是在你的人际关系网中找到一位芒果销售商。因此,如果Alice不是芒果销售商,就将其朋友也加入到名单中。这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个人际关系网,直到找到芒果销售商。这就是广度优先搜索算法。

    五、查找最短路径

    再说一次,广度优先搜索可回答两类问题。
    第一类问题:从节点A出发,有前往节点B的路径吗?(在你的人际关系网中,有芒果销售商吗?)
    第二类问题:从节点A出发,前往节点B的哪条路径最短?(哪个芒果销售商与你的关系最近?)
    刚才你看到了如何回答第一类问题,下面来尝试回答第二类问题——谁是关系最近的芒果销售商。例如,朋友是一度关系,朋友的朋友是二度关系。

     在你看来,一度关系胜过二度关系,二度关系胜过三度关系,以此类推。因此,你应先在一度关系中搜索,确定其中没有芒果销售商后,才在二度关系中搜索。广度优先搜索就是这样做的!在广度优先搜索的执行过程中,搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系。顺便问一句:将先检查Claire还是Anuj呢?Claire是一度关系,而Anuj是二度关系,因
    此将先检查Claire,后检查Anuj。

    你也可以这样看,一度关系在二度关系之前加入查找名单。

    你按顺序依次检查名单中的每个人,看看他是否是芒果销售商。这将先在一度关系中查找,再在二度关系中查找,因此找到的是关系最近的芒果销售商。广度优先搜索不仅查找从A到B的路径,而且找到的是最短的路径。

     注意,只有按添加顺序查找时,才能实现这样的目的。换句话说,如果Claire先于Anuj加入名单,就需要先检查Claire,再检查Anuj。如果Claire和Anuj都是芒果销售商,而你先检查Anuj再检查Claire,结果将如何呢?找到的芒果销售商并非是与你关系最近的,因为Anuj是你朋友的朋友,而Claire是你的朋友。因此,你需要按添加顺序进行检查。有一个可实现这种目的的数据
    结构,那就是队列(queue)。

    六、队列

    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

    队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。

    顺序队列

    建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间,并设置两个指针进行管理。一个是队头指针front,它指向队头元素;另一个是队尾指针rear,它指向下一个入队元素的存储位置,如图所示

    每次在队尾插入一个元素是,rear增1;每次在队头删除一个元素时,front增1。随着插入和删除操作的进行,队列元素的个数不断变化,队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时,队列中没有任何元素,称为空队列。当rear增加到指向分配的连续空间之外时,队列无法再插入新元素,但这时往往还有大量可用空间未被占用,这些空间是已经出队的队列元素曾经占用过得存储单元。

    顺序队列中的溢出现象:

    (1) "下溢"现象:当队列为空时,做出队运算产生的溢出现象。“下溢”是正常现象,常用作程序控制转移的条件。

    (2)"真上溢"现象:当队列满时,做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态,应设法避免。

    (3)"假上溢"现象:由于入队和出队操作中,头尾指针只增加不减小,致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

    循环队列

    在实际使用队列时,为了使队列空间能重复使用,往往对队列的使用方法稍加改进:无论插入或删除,一旦rear指针增1或front指针增1 时超出了所分配的队列空间,就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0,可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间,环形空间中的存储单元循环使用,用这种方法管理的队列也就称为循环队列。除了一些简单应用之外,真正实用的队列是循环队列。 [2] 

    在循环队列中,当队列为空时,有front=rear,而当所有队列空间全占满时,也有front=rear。为了区别这两种情况,规定循环队列最多只能有MaxSize-1个队列元素,当循环队列中只剩下一个空存储单元时,队列就已经满了。因此,队列判空的条件时front=rear,而队列判满的条件时front=(rear+1)%MaxSize。队空和队满的情况如图:

    七、广度优先搜索算法实现

    我们要从“你”出发找到“ANUJ”,关系表示为下图,使用广度优先搜索算法

     先概述一下这种算法的工作原理。

    但这样可能会出现一些问题,Peggy既是Alice的朋友又是Bob的朋友,因此她将被加入队列两次:一次是在添加Alice的朋友时,另一次是在添加Bob的朋友时。因此,搜索队列将包含两个Peggy。

    但你只需检查Peggy一次,看她是不是芒果销售商。如果你检查两次,就做了无用功。因此,检查完一个人后,应将其标记为已检查,且不再检查他。
    如果不这样做,就可能会导致无限循环。假设你的人际关系网类似于下面这样。

    一开始,搜索队列包含你的所有邻居。

    现在你检查Peggy。她不是芒果销售商,因此你将其所有邻居都加入搜索队列。

    接下来,你检查自己。你不是芒果销售商,因此你将你的所有邻居都加入搜索队列。

    以此类推。这将形成无限循环,因为搜索队列将在包含你和包含Peggy之间反复切换。

    检查一个人之前,要确认之前没检查过他,这很重要。为此,你可使用一个列表来记录检查过的人。

    首先,需要使用代码来实现图。图由多个节点组成。
    每个节点都与邻近节点相连,如果表示类似于“你→Bob”这样的关系呢?好在你知道的一种结构让你能够表示这种关系,它就是散列表!
    记住,散列表让你能够将键映射到值。在这里,你要将节点映射到其所有邻居。

    图不过是一系列的节点和边,因此在JAVA中,你可以使用HashMap来表示一个图。

    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.concurrent.LinkedBlockingQueue;
    
    public class BFS {
    
    
        public static void main(String[] args) {
            HashMap<String,String[]> hashMap=new HashMap<>();
            hashMap.put("YOU",new String[]{"CLAIRE","ALICE","BOB"});
            hashMap.put("CLAIRE",new String[]{"YOU","JONNY","THON"});
            hashMap.put("JONNY",new String[]{"CLAIRE"});
            hashMap.put("THOH",new String[]{"CLAIRE"});
            hashMap.put("ALICE",new String[]{"YOU","PEGGY"});
            hashMap.put("BOB",new String[]{"YOU","PEGGY","ANUJ"});
            hashMap.put("PEGGY",new String[]{"BOB","ALICE"});
            hashMap.put("ANUJ",new String[]{"BOB"});
            Node target = findTarget("YOU","ANUJ",hashMap);
            //打印出最短路径的各个节点信息
            printSearPath(target);
        }
    
        /**
         * 打印出到达节点target所经过的各个节点信息
         * @param target
         */
        static void printSearPath(Node target) {
            if (target != null) {
                System.out.print("找到了目标节点:" + target.id + "\n");
    
                List<Node> searchPath = new ArrayList<Node>();
                searchPath.add(target);
                Node node = target.parent;
                while(node!=null) {
                    searchPath.add(node);
                    node = node.parent;
                }
                String path = "";
                for(int i=searchPath.size()-1;i>=0;i--) {
                    path += searchPath.get(i).id;
                    if(i!=0) {
                        path += "-->";
                    }
                }
                System.out.print("步数最短:"+path);
            } else {
                System.out.print("未找到了目标节点");
            }
        }
    
        static Node findTarget(String startId,String targetId,HashMap<String,String[]> map) {
            List<String> hasSearchList = new ArrayList<String>();
            LinkedBlockingQueue<Node> queue=new LinkedBlockingQueue<>();
            queue.offer(new Node(startId,null));
            while(!queue.isEmpty()) {
                Node node = queue.poll();
                if(hasSearchList.contains(node.id)) {
                    continue;
                }
                System.out.print("判断节点:" + node.id +"\n");
                if (targetId.equals(node.id)) {
                    return node;
                }
                hasSearchList.add(node.id);
                if (map.get(node.id) != null && map.get(node.id).length > 0) {
                    for (String childId : map.get(node.id)) {
                        queue.offer(new Node(childId,node));
                    }
                }
            }
            return null;
        }
    
        static class Node{
            public String id;
            public Node parent;
            public Node(String id,Node parent) {
                this.id = id;
                this.parent = parent;
            }
        }
    }

    运行时间

    如果你在你的整个人际关系网中搜索芒果销售商,就意味着你将沿每条边前行(记住,边是从一个人到另一个人的箭头或连接),因此运行时间至少为O(边数)。
    你还使用了一个队列,其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的,即为O(1),因此对每个人都这样做需要的总时间为O(人数)。所以,广度优先搜索的运行时间为O(人数 + 边数),这通常写作O(V + E),其中V为顶点(vertice)数,E为边数。

    展开全文
  • 文章目录前言一、局部搜索算法(local search)二、 爬山法(HILL-CLIMBING)模拟退火(SIMULATED ANNEALING)集束搜索(Beam Search)遗传算法(Genetic algorithm)总结 前言 局部搜索算法简介 ​ 局部搜索算法是...
  • 智能优化算法:秃鹰搜索算法 文章目录智能优化算法:秃鹰搜索算法1.算法原理1.1 选择搜索空间1.2 搜索空间猎物 (探索)1.3 俯冲捕获猎物 (利用)2.实验结果3.参考文献4.Matlab代码 摘要:秃鹰搜索 (bald eagle search,...
  • 这些优化算法都是为针对一个目标值的最大或最小的寻找,前三种算法都属于概率性原理的算法(区别于工程优化里面的梯度下降,牛顿算法等连续直接的搜索算法,可以参考我这篇文章,求多元函数极值的情况分类与对应的...
  • 人工智能之搜索算法

    千次阅读 多人点赞 2020-03-21 21:41:32
    通过搜索来解决问题 文章目录通过搜索来解决问题1. 什么是算法?2. 什么是搜索?3. 搜索算法3.1 如何做路径规划?3.2 搜索过...
  • 麻雀搜索算法——Matlab

    千次阅读 多人点赞 2021-10-11 20:53:24
    麻雀搜索算法是2020年提出的元启发式算法,算法的具体过程见下面链接 https://blog.csdn.net/weixin_43821559/article/details/117355563 https://blog.csdn.net/u011835903/article/details/108830958 个人写的...
  • 知识点二十五:启发式搜索算法——A*算法

    千次阅读 多人点赞 2020-02-03 18:05:09
    前言 魔兽世界、仙剑奇侠传这类 MMRPG(Multiplayer Online Role-PlayingGame) 游戏中,有一个非常重要的功能,那就是人物角色...实际上,这是一个非常典型的路径搜索问题。人物的起点就是他当下所在的位置,终点就...
  • 3 局部搜索算法(10-26)

    千次阅读 2020-12-15 15:40:44
    局部搜索算法考虑对一个或多个状态进行评价、改善、修改,而不是系统地探索从初始状态开始的路径。局部搜索算法对解决纯粹的最优化问题十分有用,算法的目标是根据估价函数或者目标函数找到最佳状态。
  • 麻雀搜索算法SSA优化BP神经网络回归预测以及MATLAB代码实现 文章目录麻雀搜索算法SSA优化BP神经网络回归预测以及MATLAB代码实现1. 麻雀搜索算法SSA原理1.1 算法灵感来源1.2 算法模型描述2. SSA优化BP神经网络预测...
  • 智能优化算法:乌鸦搜索算法-附代码 文章目录智能优化算法:乌鸦搜索算法-附代码1.算法原理2.算法结果3.参考文献4.Matlab代码 摘要:乌鸦搜索算法(crow search algorithm, CSA)是2016 伊朗学者提出的,作为一种新的...
  • 改进麻雀搜索算法

    千次阅读 2021-12-29 17:56:16
    改进的麻雀搜搜算法,物超所值,含有灰狼优化算法对比和粒子群优化算法对比
  • DFS(深度优先搜索算法)

    千次阅读 2022-01-27 19:14:49
    dfs:深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法.沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始...
  • 智能优化算法:引力搜索算法-附代码 文章目录智能优化算法:引力搜索算法-附代码1.算法原理2.算法结果3.参考文献4.Matlab代码 摘要:万 有 引 力 搜 索 算 法 (gravitational searchalgorithm,GSA) 由伊朗的 Esmat ...
  • 启发式搜索算法之贪婪最佳优先搜索算法和A*算法** 启发式搜索又称为有信息搜索,是相对于广度优先搜索和深度优先搜素这类无信息搜索的搜索算法。该类算法是基于能够获得辅助算法的额外信息进行运算,这些信息称为...
  • 智能优化算法:天牛须搜索算法

    万次阅读 多人点赞 2020-11-23 16:51:25
    智能优化算法:天牛须搜索算法一、前言二、算法简介三、算法原理3.1 算法模型3.2 算法流程总结 一、前言        天牛须算法 (Beetle Antennae search algorithm, BAS) 是由Jiang...
  • 文章目录1.A 算法1.1.全局择优算法1.1.1.求解八数码1.2.局部择优算法2.A*算法2.1 ...对启发式搜索算法,又可根据搜索过程中选择扩展节点的范围,将其分为全局择优搜索算法和局部择优搜索算法。 ` 1.1.全局择优算法 在全
  • 百度搜索于2017年7月4日发布飓风算法,严厉打击恶劣采集问题,并在2018年9月13日公布飓风算法升级为2.0版本。 飓风算法2.0主要打击以下四类恶劣采集行为: 1.存在大量从其他站点或公众号等内容生产方采集、搬运而...
  • 自适应大邻域搜索算法

    千次阅读 多人点赞 2020-06-16 20:50:10
    自适应大邻域搜索算法(Adaptive Large Neighborhood Search)是由Ropke与Pisinger在2006年提出的一种启发式方法,其在邻域搜索的基础上增加了的对算子的作用效果的衡量,使算法能够自动选择好的算子对解进行破坏与...
  • 禁忌搜索算法详解(含算法示例)

    万次阅读 多人点赞 2020-11-04 17:22:12
    禁忌搜索算法,含有算法示例,可以更好的理解该算法的过程
  • 变邻域搜索算法是对局部搜索算法的一种改进,是一种改进型的局部搜索算法。和自适应大邻域搜索属于不同的体系,但属于邻域的大家族。 1.局部搜索算法的共性 局部搜索算法的统一框架描述为: (1)算法从一个或...
  • Grover搜索算法

    千次阅读 2020-12-01 13:06:16
    目录一 简介二 问题描述三 算法描述3.1 量子门3.2 量子线路 一 简介 Grover算法和Shor算法是量子算法领域两个最重要的量子算法,而Grover算法相比于...注:经典随机算法需要Θ(n)\Theta(n)Θ(n)次查询才能解决该搜索
  • 搜索算法 本文主要以一些概念对较为常见的搜索作简单介绍: 一、盲目搜索 对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。在所有搜索方式中,广度优先算法和深度优先搜索算法都十分重要,因为它们...
  • 常用搜索算法—盲目搜索和启发式搜索

    万次阅读 多人点赞 2019-05-25 00:51:39
    搜索算法 本文主要以一些概念对较为常见的搜索作简单介绍: 一、盲目搜索 对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。在所有搜索方式中,广度优先算法和深度优先搜索算法都十分重要,因为它们提供了...
  • 禁忌搜索算法总结

    千次阅读 2019-02-04 12:21:53
    禁忌搜索算法简介 禁忌搜索(Tabu Search,TS)是一种现代启发式算法,由美国科罗拉多大学教授Fred Glover在1986年左右提出的,是一个用来跳脱局部最优解的搜索方法。 算法基于局部搜索算法改进而来,通过引入禁忌表...
  • 禁忌搜索算法

    万次阅读 多人点赞 2019-04-29 11:39:57
    组合优化算法系列: ...现代优化算法(三):禁忌搜索算法 现代优化算法(四):改进的遗传算法 现代优化算法(五): 蚁群算法 目录 1 禁忌搜索算法的相关概念 (1)邻域 (2)侯选集合 (3)禁忌对象...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 764,605
精华内容 305,842
关键字:

搜索算法