精华内容
下载资源
问答
  • 智能优化算法:麻雀搜索算法-附代码

    万次阅读 多人点赞 2020-09-27 16:34:00
    2020智能优化算法:麻雀搜索算法-附代码 文章目录2020智能优化算法:麻雀搜索算法-附代码1.算法原理2.算法结果3.参考文献4.Matlab代码 摘要:麻雀搜索算法(Sparrow Search Algorithm, SSA)是于2020年提出的。SSA ...

    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.

    算法相关应用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

    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.
    展开全文
  • 这些优化算法都是为针对一个目标值的最大或最小的寻找,前三种算法都属于概率性原理的算法(区别于工程优化里面的梯度下降,牛顿算法等连续直接的搜索算法,可以参考我这篇文章,求多元函数极值的情况分类与对应的...

    这些优化算法都是为针对一个目标值的最大或最小的寻找,前三种算法都属于概率性原理的算法(区别于工程优化里面的梯度下降,牛顿算法等连续直接的搜索算法,可以参考我这篇文章,求多元函数极值的情况分类与对应的算法),可以避免局部最优。 而禁忌搜索算法是靠禁忌表(里面存的是前面一些次数的搜索方向和搜索步伐,可能这些步伐有局部最优解了)来限制新的搜索方向和步伐跟禁忌表里不一样,这样可以跳出这个局部最优,去更广阔的的地方搜索(不是使用的随机方式)。

    群蚁算法

    蚂蚁寻找食物的过程:

    单只蚂蚁的行为及其简单,行为数量在10种以内,但成千上万只蚂蚁组成的蚁群却能拥有巨大的智慧,这离不开它们信息传递的方式——信息素。蚂蚁在行走过程中会释放一种称为“信息素”的物质,用来标识自己的行走路径。在寻找食物的过程中,根据信息素的浓度选择行走的方向,并最终到达食物所在的地方。信息素会随着时间的推移而逐渐挥发。在一开始的时候,由于地面上没有信息素,因此蚂蚁们的行走路径是随机的。蚂蚁们在行走的过程中会不断释放信息素,标识自己的行走路径。随着时间的推移,有若干只蚂蚁找到了食物,此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为轨迹是随机分布的,因此在单位时间内,短路径上的蚂蚁数量比长路径上的蚂蚁数量要多,从而蚂蚁留下的信息素浓度也就越高。这为后面的蚂蚁们提供了强有力的方向指引,越来越多的蚂蚁聚集到最短的路径上去。

    什么是蚁群算法?

    蚁群算法就是模拟蚂蚁寻找食物的过程,它能够求出从原点出发,经过若干个给定的需求点,最终返回原点的最短路径。这也就是著名的旅行商问题(Traveling Saleman Problem,TSP)。主要就是解决一个组合优化的问题,比如每个段都有长度,这些段怎么组合起来使得总距离最短,不就是高中学的排列组合嘛,目标函数就是总和最小,这里用的群蚁算法就是以一定的随机概率进行组合(如果是我们自己手动一一把所有的可能性都组合出来,算出各自的总和,这样是最原本理想的做法,但是因为段数太多了,比如30段,那么组合就是30的阶乘/2,计算机可能算到爆炸,所以就希望通过一种运算量小的近似的方式求出呢,确实是可以的,那么就是群蚁算法等,而为什么需要这种概率性的搜索算法呢,因为这样才能避免直接试探性组合产生的局部最优,即跳出局部最优。除了群蚁算法,其他算法可以不呢,但是根据其算法过程知道,群蚁算法适合解决这种离散组合最大值总和的的情况,比如像求一个函数最大值这种,就不需要组合的操作了,所以用遗传算法,模拟退火算法,爬山算法,梯度下降等搜索算法才合适。

    应用领域:

    可以使用蚁群算法来解决分布式环境下的负载均衡调度问题。

    大家感兴趣可以去具体看看参考链接给出的这篇文章的代码实现,还是挺通俗易懂的。
     

    遗传算法

     

    遗传算法(Genetic Algorithm, GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,不需要确定的规则就能自动获取和指导优化的搜索空间,自适应地调整搜索方向。

    初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。

     

     

    应用领域:

    一元函数最大值问题。

    其主要原因是遗传算法有个随机变异的方式,所以很有可能找到最高峰的那个坐标。而搜索算法(这是我以前写过的文章)只能一步一步向前搜索,这样很有可能遇到局部最优罢了。

     

    模拟退火算法

    继续考虑寻找f(x)最大值的问题,爬山算法搜索到A点时就会停止搜索,原因是A点左右的值均小于A点的值。模拟退火算法采用的解决办法是以一定的概率选择A两边的点,尽管A两边的点并不是局部最优解,这样就有一定的概率搜索到D点,从而搜索到B点,最终获得了全局最优解。上文中的一定概率来自于固体退火原理:当固体温度较高时,物质内能较大,固体内部分子运动剧烈;当温度逐渐降低时,物体内能也随之降低,分子运动趋于平稳;当固体温度降到常温时,固体内部分子运动最终平稳。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e^(-ΔE/(kT)),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。

    禁忌搜索算法 

    禁忌(Tabu Search)算法是一种亚启发式(meta-heuristic)随机搜索算法,它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解,TS搜索中采用了一种灵活的“记忆”技术,对已经进行的优化过程进行记录和选择,指导下一步的搜索方向,这就是Tabu表的建立。

    又名“tabu搜索算法”为了找到“全局最优解”,就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索,导致一叶障目,不见泰山。禁忌搜索散发就是对于找到的一部分局部最优解,有意识地避开它(但不是完全隔绝),从而获得更多的搜索区间。兔子们找到了泰山,它们之中的一只就会留守在这里,其他的再去别的地方寻找。就这样,一大圈后,把找到的几个山峰一比较,珠穆朗玛峰脱颖而出。

    当兔子们再寻找的时候,一般地会有意识地避开泰山,因为他们知道,这里已经找过,并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表(tabu list)”的含义。那只留在泰山的兔子一般不会就安家在那里了,它会在一定时间后重新回到找最高峰的大军,因为这个时候已经有了许多新的消息,泰山毕竟也有一个不错的高度,需要重新考虑,这个归队时间,在禁忌搜索里面叫做“禁忌长度(tabu length)”;如果在搜索的过程中,留守泰山的兔子还没有归队,但是找到的地方全是华北平原等比较低的地方,兔子们就不得不再次考虑选中泰山,也就是说,当一个有兔子留守的地方优越性太突出,超过了“best so far”的状态,就可以不顾及有没有兔子留守,都把这个地方考虑进来,这就叫“特赦准则(aspiration criterion)”。这三个概念是禁忌搜索和一般搜索准则最不同的地方,算法的优化也关键在这里。

    主要思路

    1、在搜索中,构造一个短期循环记忆表-禁忌表,禁忌表中存放刚刚进行过的 |T|(T称为禁忌表)个邻居的移动,这种移动即解的简单变化。

    2、禁忌表中的移动称为禁忌移动。对于进入禁忌表中的移动, 在以后的 |T| 次循环内是禁止的,以避免回到原来的解,从而避免陷入循环。|T| 次循环后禁忌解除。

    3、禁忌表是一个循环表,在搜索过程中被循环的修改,使禁忌表始终保持 |T| 个移动。

    4、即使引入了禁忌表,禁忌搜索仍可能出现循环。因此,必须给定停止准则以避免出现循环。当迭代内所发现的最好解无法改进或无法离开它时,算法停止。

    局部搜索算法

    局部搜索算法从一个初始解开始,通过邻域动作,产生其邻居解,判断邻居解的质量,根据某种策略,来选择邻居解,重复上述过程,至到达终止条件。

    针对局部邻域搜索,为了实现全局优化,可尝试的途径有:

    以可控性概率接受劣解来逃逸局部极小,如模拟退火算法;
    扩大邻域搜索结构,如TSP的2opt扩展到k-opt;
    多点并行搜索,如进化计算;
    采用TS的禁忌策略尽量避免迂回搜索,它是一种确定性的局部极小突跳策略。
    基本思想
    避免在搜索过程中的循环

    只进不退的原则,通过禁忌表实现

    不以局部最优作为停止准则

    标记已经解得的局部最优解或求解过程,并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于,太过于对某一局部区域以及其邻域的搜索,导致一叶障目。为了找到全局最优解,禁忌搜索就是对于找到的一部分局部最优解,有意识地避开它,从而或得更多的搜索区域。
     

    总结:遗传算法,模拟退火算法,禁忌搜索算法都是以概率选取新点或者避免重复搜索等的方式进行最优解的搜索(搜索目标函数的最值),蚁群算法主要是解决离组合优化等离散问题的最优值。


    参考文献

    * 10分钟搞懂蚁群算法

    【算法】超详细的遗传算法(Genetic Algorithm)解析

    模拟退火算法

    禁忌搜索算法

    禁忌搜索算法总结

    展开全文
  • 引力搜索算法

    千次阅读 2020-07-03 21:10:37
    最近在论文中看到有学者用改进的引力搜索算法解优化问题,有一个较好的效果,于是去了解了一下这个算法。 引力搜索算法(Gravitational Search Algorithm,GSA)是Esmat Rashedi等人在2009年提出的一种随机性启发式...

    最近在论文中看到有学者用改进的引力搜索算法解优化问题,有一个较好的效果,于是去了解了一下这个算法。

    引力搜索算法(Gravitational Search Algorithm,GSA)是Esmat Rashedi等人在2009年提出的一种随机性启发式搜索算法,这种算法的灵感来自于牛顿的万有引力定律与运动定律:1.任意两个质点有通过连心线方向上的力相互吸引,该引力大小与它们质量的乘积成正比与它们距离的平方成反比。2.力使物体获得加速度。

    在GSA中,质点被抽象成解空间的一个解,解之间存在一个相互吸引力,这个吸引力由解的质量与两个解之间的距离确定,质点的质量被抽象成解的评估函数值。在解空间中,每个解由其他解对其的吸引力获得加速度,质量更大(评估函数值更优)所提供的加速度更大,从而使解向更优解的方向移动。

    看到这里,有些小伙伴会以为GSA是个与PSO差不多的算法,是的,GSA与PSO的外层框架是一致的,但是,它们最关键的粒子移动策略却是不同的:

    1.在PSO中,粒子的移动只使用两个最佳位置pbest和gbest。但是在GSA中,智能体的方向是根据所有其他智能体或部分较优的智能体获得的总力来计算的。
    2.PSO使用一种内存来更新速度(由于pbest和gbest)。然而,GSA是无内存的,只有智能体的当前位置在更新过程中起作用。
    3.在PSO中,更新不考虑解之间的距离,而在GSA中,力与解之间的距离成反比。
    4.PSO模拟了鸟类的社会行为,而GSA的灵感来自于物理现象。

    GSA的主要过程如下:

    1. 确定搜索空间。
    2. 随机初始化个体种群。
    3. 对种群进行适应度评价。
    4. 更新引力常量G,更新种群中最好的个体 best与最差的个体worst,更新个体的质量。
    5. 计算每个个体在不同方向上的总引力。
    6. 计算个体的加速度,基于此更新个体的速度。
    7. 根据速度更新个体在解空间中的位置。
    8. 重复步骤3-7直到达到停止标准。

    算法流程:
    在这里插入图片描述

    具体的个体属性更新公式与引力计算公式建议参考 GSA: A Gravitational Search Algorithm这篇文章。

    例: min z = x1 ** 2 + x2 ** 2
    s.t. -10 <= x1 <= 10 , -10 <= x2 <= 10

    # Gravitational Search Algorithm
    import numpy as np
    import random as rd
    from math import exp, sqrt
    
    '''min z = X1 ** 2 + X2 ** 2
       s.t.   -10 <= x1 <= 10
              -10 <= X2 <= 10   '''
    
    def init(n):
        position, velocity = [], []
        for i in range(n):
            X1 = rd.uniform(-10, 10)
            X2 = rd.uniform(-10, 10)
            V1 = rd.uniform(-3, 3)
            V2 = rd.uniform(-3, 3)
            position.append([X1, X2])
            velocity.append([V1, V2])
        return position, velocity
    
    def objFuntion(x1, x2):
        return x1 ** 2 + x2 ** 2
    
    def fitnessEva(position):
        fitness = []
        for i in range(len(position)):
            fitness.append(objFuntion(position[i][0], position[i][1]))
        return fitness
    
    def findBestAndWorst(position):
        return min(fitnessEva(position)), max(fitnessEva(position))
    
    def calculateMass(fitness):
        mass = []
        Mass = []
        for i in range(len(fitness)):
            mass.append((fitness[i] - max(fitness)) / (min(fitness) - max(fitness)))
        for i in range(len(mass)):
            Mass.append(mass[i] / sum(mass))
        return Mass
    
    def calculateAcceleration(position, Mass, G, topK):
        acceleration = []
        Fi0, Fi1 = 0, 0
    
        for i in range(len(position)):
            for j in range(len(position)):
                if i != j and j in topK:
                    Fi0 += rd.random() * G * ((Mass[i] * Mass[j]) / (calculateDistance(position[i], position[j]) + r)) * (
                                position[j][0] - position[i][0])
                    Fi1 += rd.random() * G * ((Mass[i] * Mass[j]) / (calculateDistance(position[i], position[j]) + r)) * (
                                position[j][1] - position[i][1])
            if Mass[i] != 0:
                acceleration.append([Fi0 / Mass[i] / 10, Fi1 / Mass[i] / 10])   #这里除10是为了避免粒子的加速度过大
            else:
                acceleration.append([10, 10])
            Fi0 = 0
            Fi1 = 0
        return acceleration
    
    def findTopK(fitness, K):
        topK = []
        dic = {}
        for i in range(len(fitness)):
            dic[i] = fitness[i]
        fitness.sort()
        for i in range(K):
            topK.append(list(dic.keys())[list(dic.values()).index(fitness[i])])
        return topK
    
    
    def updateVelocityAndPosition(acceleration, position, velocity):
        for i in range(len(velocity)):
            velocity[i][0] = rd.random() * velocity[i][0] + acceleration[i][0]
            velocity[i][1] = rd.random() * velocity[i][1] + acceleration[i][1]
    
            position[i][0] = position[i][0] + velocity[i][0]
            position[i][1] = position[i][1] + velocity[i][1]
    
    def calculateDistance(p1,p2):
        return sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
    
    def checkPosition(position):
        for i in range(len(position)):
            if position[i][0] < -10:
                position[i][0] = -10
            elif position[i][0] > 10:
                position[i][0] = 10
            if position[i][1] < -10:
                position[i][1] = -10
            elif position[i][1] > 10:
                position[i][1] = 10
    
    if __name__ == '__main__':
        G = 100
        r = 1
        K = 50
    
        iterx, maxIterx = 0, 50
        position, velocity = init(50)
        while iterx < maxIterx:
            fitness = fitnessEva(position)               #适应性评估
            G = G * exp(-20 * iterx / maxIterx)          #更新引力常量
            Mass = calculateMass(fitness)                #更新粒子质量
            topK = findTopK(fitness, K)                  #找出适应度更优的前K个粒子
            acceleration = calculateAcceleration(position, Mass, G, topK)          #计算粒子加速度
            updateVelocityAndPosition(acceleration, position, velocity)            #根据加速度更新速度与位置
            checkPosition(position)                                                #检查粒子是否冲出了解空间
            iterx += 1
            K = K - iterx                                #更新K值
        print(min(fitnessEva(position)))
        print(position[fitnessEva(position).index(min(fitnessEva(position)))])
    

    参考文献:
    Rashedi E, Nezamabadi-pour H, Saryazdi S. GSA:a gravitational search algorithm[J].Information Science, 2009, 179 (13) :2232-2248.

    展开全文
  • 文章目录前言一、局部搜索算法(local search)二、 爬山法(HILL-CLIMBING)模拟退火(SIMULATED ANNEALING)集束搜索(Beam Search)遗传算法(Genetic algorithm)总结 前言 局部搜索算法简介 ​ 局部搜索算法是...


    前言

    局部搜索算法简介
    ​ 局部搜索算法是一类可以有效解决优化问题的通用算法。它的基本原理是在临近解中迭代,使目标函数逐步优化,直至不能再优化为止。

    ​ 局部搜索算法可以这样描述:假设问题的解空间表示为S, 局部搜索算法从一个初始解i∈S 开始,然后根据具体问题定义的具体邻域结构,在当前解 i 的邻域 Si 内按一定规则找到一个新解,再用这个新解取代 i 成为当前解,判断是否满足算法结束条件,如果不满足再对当前解继续使用算法,如果满足则算法结束,当前解就作为算法的最终解。

    局部搜索算法具有以下特点:

    算法结构通用易实现。只要定义好具体问题相关的邻域,就能有效的求解该问题。
    算法性能和邻域的定义以及初始状态有关。邻域定义的不同或初始状态选取的不同会对算法的性能产生决定性的影响。
    算法的局部优化特性。算法容易陷入局部最优解,达到全局最优比较困难。
    局部搜索算法主要包含五大要素:

    目标函数:用来判断解的优劣。
    邻域的定义:根据不同问题,有着不同的邻域定义。
    初始解的产生规则
    新解的产生和接受规则
    算法终止准则(常见的三个准则:求解时间;迭代次数;和解质量提高比例)


    以下为局部搜索的有关算法:

    一、局部搜索算法(local search)

    局部搜索是解决最优化问题的一种启发式算法。对于某些计算起来非常复杂的最优化问题,比如各种NP完全问题,要找到最优解需要的时间随问题规模呈指数增长,因此诞生了各种启发式算法来退而求其次寻找次优解,是一种近似算法(Approximate algorithms),以时间换精度的思想。局部搜索就是其中的一种方法。

    局部搜索算法是从爬山法改进而来的。
    简单来说,局部搜索算法是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。

    在计算机科学中,局部搜索是解决最优化问题的一种启发式算法。局部搜索从一个初始解出发,然后搜索解的邻域,如有更优的解则移动至该解并继续执行搜索,否则返回当前解。

    局部搜索算法的基本思想:在搜索过程中,始终选择当前点的邻居中与离目标最近者的方向搜索。 
     
    局部搜索的优点:简单、灵活及易于实现,缺点是容易陷入局部最优且解的质量与初始解和邻域的结构密切相关。

    二、 爬山法(HILL-CLIMBING)

    爬山算法:爬山算法是一种简单的贪心搜索算法,该算法每次从当前位置的临近空间中选择一个最优解作为当前解,直到达到一个局部最优解。

    爬山算法的输入是定义的两个局部变量,一个是当前状态(当前结点),还有一个就是用来存储邻居结点的neighbor。我们从初始结点(也就是我们的当前结点)出发,开始往前爬山(往前搜索)。首先根据当前结点能够产生多少个后续结点,然后在这些后续结点中选择一个最大值(这个值是用你所定义的评估函数评估出来的)的后续结点,并将它放进neighbor中,然后将后续结点的值与当前结点的值进行比较,如果发现当前结点的值比后续结点的值要大,那么就意味着当前结点就是一个局部最值点了,所以就不用动了,把当前结点对应的状态返回即可。但是如果当前结点的值比后续结点的值要小,那么就往前走。这样一步一步地进行迭代,直到走到一个局部最值点。

    我们可以类比成一个兔子爬山的例子,为了找出地球上最高的山,一群有志气的兔子们开始想办法。

    爬山算法可以类比成一个有失忆的兔子在浓雾中爬山。这里就揭示了爬山算法的两个问题:

    失忆:就是说这只兔子不记得他去过什么地方,它只记得他现在所处的位置,以及周边的情况(因为有浓雾,所以它只能看到最近的周边的情况)。

    所以说他在任何时候只存储一个当前的状态,之前的所有的状态全部不记得了。那么我们就可以看出爬山算法非常依赖于这个初始状态(如果初始状态距离全局最值点很近的话,是更容易搜索到全局最值点的)。

    浓雾:当他走到一个局部最值点时,因为他看见远处是否还有更大的最值点,所以就把当前这个局部最值点返回给你(爬山算法的返回是返回一个状态而不是一个路径,这个状态就是一个局部最值点)。

    所以说,爬山算法的主要缺点是可能会陷入局部最优解,而不一定能搜索到全局最优解。

    模拟退火(SIMULATED ANNEALING)

    为了防止陷入局部最优,模拟退火算法以一定概率接受比当前解差的解,接受差解的概率随着迭代次数的增加而下降,或者说是随着温度T的下降而下降。

    该算法从一个初始解开始,这个初始解可以是随机选择的,也可以是启发式方式得到的,并初始化一个温度。在每次迭代过程中,从当前解的邻居解中随机的选择一个解,若随机选择的一个邻居解比当前解的质量好,则替换当前解,若质量比当前解差,则以一定的概率接受这个差解,来替换当前解。最后更新温度T,进行下一次迭代。

    同样类比成兔子爬山,模拟退火方法是一群喝醉的兔子。
    兔子喝醉了。他随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,他渐渐清醒了并朝最高方向跳去。这就是模拟退火。

    集束搜索(Beam Search)

    1.简介

    Beam Search(集束搜索)是一种启发式图搜索算法,通常用在图的解空间比较大的情况下,为了减少搜索所占用的空间和时间,在每一步深度扩展的时候,剪掉一些质量比较差的结点,保留下一些质量较高的结点。这样减少了空间消耗,并提高了时间效率,但缺点就是有可能存在潜在的最佳方案被丢弃,因此Beam Search算法是不完全的,一般用于解空间较大的系统中。

    2.流程

    Beam Search(集束搜索)使用广度优先策略建立搜索树,在树的每一层,按照启发代价对节点进行排序,然后仅留下预先确定的个数(Beam Width-集束宽度)的节点,仅这些节点在下一层次继续扩展,其他节点就被剪掉了。如果集束宽度无穷大,那该搜索就是宽度优先搜索。

    集束宽度可以是预先定好的,也可以是变动的,可以先按照一个最小的集束宽度进行搜索,如果没有找到合适的解,再扩大集束宽度再找一遍。

    Ps. 个人认为集束搜索方法其实提供了一种找最优解的思路,就是说在适当的情况下,可以剪掉一些可信度低的路径,在实际使用中,可以每一层的集束宽度不一致,比如在初始的一些层次中多保留一些结果,在后边就可以放心大胆的进行剪枝。当然也可以活学活用,可以结合深度优先算法,通过回溯,可以找到最优解。

    3.应用

    Beam Search(集束搜索)多用在一些大型系统中,比如机器翻译系统,语音识别系统等,因为这些系统中的数据集可能非常大,而且结果也没有唯一正确的解,系统用最快的方式找到最接近正确的解才是系统的目标。

    遗传算法(Genetic algorithm)

    遗传算法实际上是随机束搜索的变形, 通过吧两个父状态结合生成后继。

    种群:种群中的每个个体都是潜在解
    个体表示: 染色体, 实际就是状态的表示
    适应度函数:表示解的好坏程度
    选择(利用):根据适应度选取比较好的解优先进行两两繁殖
    交叉(利用为主+探索): 选取一个杂交点, 两边染色体互相交换
    变异(探索):每个位置都会小概率发生变异

    类比成兔子,遗传算法是一群吃了失忆药片随机分布在地球上的某些地方的兔子们
    他们不知道自己的使命是什么。但是,如果你过几年就杀死一部分海拔低的兔子,多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。


    总结

    提示:这里对文章进行总结:
    方法还未介绍完全。暂无,待更新。

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

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

    千次阅读 多人点赞 2020-03-21 21:41:32
    通过搜索来解决问题 文章目录通过搜索来解决问题1. 什么是算法?2. 什么是搜索?3. 搜索算法3.1 如何做路径规划?3.2 搜索过...
  • 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.算法原理1.1 选择搜索空间1.2 搜索空间猎物 (探索)1.3 俯冲捕获猎物 (利用)2.实验结果3.参考文献4.Matlab代码 摘要:秃鹰搜索 (bald eagle search,...
  • 前言 魔兽世界、仙剑奇侠传这类 MMRPG(Multiplayer Online Role-PlayingGame) 游戏中,有一个非常重要的功能,那就是人物角色...实际上,这是一个非常典型的路径搜索问题。人物的起点就是他当下所在的位置,终点就...
  • 常用搜索算法—盲目搜索和启发式搜索

    万次阅读 多人点赞 2019-05-25 00:51:39
    搜索算法 本文主要以一些概念对较为常见的搜索作简单介绍: 一、盲目搜索 对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。在所有搜索方式中,广度优先算法和深度优先搜索算法都十分重要,因为它们提供了...
  • 智能优化算法:乌鸦搜索算法-附代码 文章目录智能优化算法:乌鸦搜索算法-附代码1.算法原理2.算法结果3.参考文献4.Matlab代码 摘要:乌鸦搜索算法(crow search algorithm, CSA)是2016 伊朗学者提出的,作为一种新的...
  • 智能优化算法:天牛须搜索算法

    千次阅读 多人点赞 2020-11-23 16:51:25
    智能优化算法:天牛须搜索算法一、前言二、算法简介三、算法原理3.1 算法模型3.2 算法流程总结 一、前言        天牛须算法 (Beetle Antennae search algorithm, BAS) 是由Jiang...
  • 自适应大邻域搜索算法

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

    千次阅读 多人点赞 2019-11-28 19:07:49
    作为程序员的我们可能经常会听到 A*搜索算法这个的词,听起来非常高大上,腻害,但是具体是什么呢? 引用 Wiki 上的说法就是: A* 搜索算法(A* search algorithm)是一种在图形平面上,有多个节点的路径,求出最低...
  • 禁忌搜索算法详解(含算法示例)

    千次阅读 多人点赞 2020-11-04 17:22:12
    禁忌搜索算法,含有算法示例,可以更好的理解该算法的过程
  • 禁忌搜索算法+蚁群算法,两种算法的融合解决矩形排样
  • a*启发式搜索算法的matlab仿真程序

    热门讨论 2014-05-19 11:32:09
    a*启发式搜索算法的matlab仿真程序
  • 禁忌搜索算法

    万次阅读 多人点赞 2019-04-29 11:39:57
    组合优化算法系列: ...现代优化算法(三):禁忌搜索算法 现代优化算法(四):改进的遗传算法 现代优化算法(五): 蚁群算法 目录 1 禁忌搜索算法的相关概念 (1)邻域 (2)侯选集合 (3)禁忌对象...
  • 1、禁忌搜索的基本原理 1、TS的要素构成 禁忌表(Tabu List) 渴望水平函数 移动准则——邻域选优 选优准则——保持历史上的最优解 停止准则——与GA类似 2、禁忌搜索的特点 禁忌搜索适用于离散优化,不适合实优化 ...
  • 禁忌搜索算法(TS)

    千次阅读 2020-06-29 22:58:35
    1 算法背景 禁忌搜索算法(Tabu Search或Taboo Search,简称TS)最早是由Glover等人在1986年提出。TS本质上是对局部领域搜索的一种扩展,是一种全局逐步寻优算法。TS算法通过模拟人类智能的记忆机制,引入一个灵活的...
  • 现代优化算法 之 禁忌搜索算法

    万次阅读 多人点赞 2015-12-22 12:45:02
    禁忌搜索算法简介禁忌搜索算法是组合优化算法的一种,是局部搜索算法的扩展。禁忌搜索算法是人工智能在组合优化算法中的一个成功应用。禁忌搜索算法的特点是采用了禁忌技术。所谓禁忌就是禁止重复前面的工作。禁忌...
  • 搜索算法 本文主要以一些概念对较为常见的搜索作简单介绍: 一、盲目搜索 对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。在所有搜索方式中,广度优先算法和深度优先搜索算法都十分重要,因为它们...
  • 禁忌搜索算法总结

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

    千次阅读 多人点赞 2020-02-22 17:02:06
    布谷鸟搜索算法(Cuckoo Search,缩写 CS)是由剑桥大学杨新社教授和S.戴布于2009年提出的一种新兴启发算法。根据昆虫学家的长期观察研究发现,一部分布谷鸟以寄生的方式养育幼鸟,它们不筑巢,而是将自己的卵产在...
  • 禁忌搜索算法详解

    万次阅读 多人点赞 2017-01-08 17:47:43
    禁忌搜索是由局部搜索算法发展而来,爬山法是从通用局部搜索算法改进而来。在介绍禁忌搜索之前先来熟悉下爬山法和局部搜索算法。 局部搜索算法 算法的基本思想 在搜索过程中,始终选择当前点的邻居中与离目标...
  • 局部搜索算法

    千次阅读 2019-03-24 09:10:22
    局部搜索算法是在一组可行解的基础上,在当前解的领域内进行局部搜索产生新的可行解的过程。 主要有路径内搜索和路径间搜索,以下都以VRP为例。 路径内搜索 2-opt 2-opt搜索算法由Lin S(1965)提的一种路径内改进...
  • 引力搜索算法[附python实现代码]

    千次阅读 2020-11-23 22:38:59
    在求解具有高维搜索空间的优化...到目前为止,研究者们已经采用了各种启发式方法来解决这些问题例如遗传算法、模拟退火算法、蚁群搜索算法、粒子群优化算法等。这些算法在许多不同领域被研究人员逐步分析或支持。 这..
  • 布谷鸟搜索算法学习

    千次阅读 2020-06-12 08:37:27
    布谷鸟搜索算法是一种结合了布谷鸟巢寄生性和莱维飞行模式的元启发式群体智能搜索技术,本文对布谷鸟搜索算法的原理和算法流程进行简单的论述,将布谷鸟搜索算法与遗传算法、蚁群算法、粒子群算法、蜂群算法做对比,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 661,164
精华内容 264,465
关键字:

搜索算法