精华内容
下载资源
问答
  • 智能优化算法原子优化算法 文章目录智能优化算法原子优化算法1.原子优化算法原理2.实验结果3.参考文献4.Matlab代码 ...引力促使原子广泛地探索整个搜索空间,斥力使它们能够有效地开发潜在区域 。

    智能优化算法:原子搜索优化算法


    摘要:原子搜索优化算法(Atom Search Optimization)是于2019提出的一种基于分子动力学模型的新颖智能算法.模拟在原子构成的分子系统中,原子因相互间的作用力和系统约束力而产生位移的现象.在一个分子系统中,相邻的原子间存在相互作用力(吸引力和排斥力),且全局最优原子对其他原子存在几何约束作用 .引力促使原子广泛地探索整个搜索空间,斥力使它们能够有效地开发潜在区域 。具有寻优能力强,收敛快的特点。

    1.原子优化算法原理

    假设一个分子系统是由 s个原子构成的d维空间, Xid(t)X_i^d(t))为第ii 个原子在第tt次迭代时的位置,可以表示为:Xid(t)=(Xi,1,Xi,2,...,Xi,d),(i=1,2,...,s;,t=1,2,...,tmaxX_i^d(t) = (X_{i,1},X_{i,2},...,X_{i,d}),(i=1,2,...,s;,t=1,2,...,t_{max},tmaxt_{max}为最大迭代次数,Xbestd(t)X_{best}^d(t))为第t次迭代时全局最优解.

    在这里插入图片描述

    图1.n,F 和h关系图

    原子运动遵循经典力学根据牛顿第二定律,原子的加速度与其质量有关,且由原子间的相互作用力和最优原子对其的几何约束的共同作用产生,所以第i个原子在第t次迭代时加速度如下:
    aid(t)=Fid+Gid(t)mid(t)(1) a_i^d(t) = \frac{F_i^d + G_i^d(t)}{m_i^d(t)}\tag{1}
    式中,Fid(t)F_i^d(t)为第t次迭代时d维空间中作用于第 i个原子的总力,可以看作是适应度函数值较好的k个原子对第i个原子作用力的随机加权之和,表示如下:
    Fid(t)=jKbestrandjFijd(t)(2) F_i^d(t)=\sum_{j\in K_{best}}rand_jF^d_{ij}(t)\tag{2}
    式中,KbestK_{best}为适应度函数值较好的kk个原子的集合,FijdF_{ij}^d为两原子之间的作用势能,可以表示为:
    Fijd=n(t)[2(hij(t))3(hij(t))7](3) F_{ij}^d = -n(t)[2(h_{ij}(t))^3 - (h_{ij}(t))^7]\tag{3}
    式中,n(t)=α(1t1tmax)3e20t/tmaxn(t) = \alpha(1-\frac{t-1}{t_{max}})^3e^{-20t/t_{max}}可以调节引力区域和斥力区域的范围,nn随着迭代次数的增加, nn自适应递减,使得全局搜索和局部开发的范围都逐步缩小至最优值,保证了算法的收敛性;α\alpha为深度加权;hij(t)h_{ij}(t)为两个原子之间的距离,不同的hh值对应着不同的作用力性质 . 如图 1 所示,当h(0.9,1.1)h \in(0.9,1.1)时为斥力,且随着hh值得增大而增大;当h为1.12时,为平衡状态,作用力为0;当h(1.12,1.24)h \in(1.12,1.24)时,为吸引力且随着hh值得增大而增大,h(1.24,2)h \in(1.24,2)时,仍为吸引力但随着hh值得增大而减小至0 ,所以hh可以表示为:
    hij(t)={hmin,rij(t)/σ(t)<hminrij(t)/σ(t),hminrij(t)/σ(t)hmaxhmax,rij(t)/σ(t)>hmax(4) h_{ij}(t) = \begin{cases} h_{min}, r_{ij}(t)/\sigma(t)<h_{min}\\ r_{ij}(t)/\sigma(t),h_{min}\leq r_{ij}(t)/\sigma(t)\leq h_{max}\\ h_{max},r_{ij}(t)/\sigma(t)>h_{max} \end{cases}\tag{4}
    式中,hmin=ε0+ε(t)h_{min}=\varepsilon_0 + \varepsilon(t)hh的下界,ε(t)\varepsilon(t)为漂移因子随着迭代次数的变化而变化,使得算法在全局搜索和局部开发中转换;hmaxh_{max}hh上界;σ(t)=Xij(t),jKbestXij(t)/K(t)2\sigma(t)=||X_{ij}(t),\sum_{j\in K_{best}}X_{ij}(t)/K(t)||_2,是KbestK_{best}集合中的原子与第ii个原子的距离范围.

    在这里插入图片描述

    图2.原子群相互作用示意图(K=5)

    在ASO算法中,为了加强迭代初期的全局探索能力,每个原子需要与较多个适应度较好的邻近原子产生相互作用,而在迭代后期为了增强局部开发促进算法收敛,每个原子需要与较少的适应度较好的邻近原子产生相互作用 . 适应度较好的邻近原子的数量用KK表示,K=s(s2)t/tmaxK = s-(s-2)*\sqrt{t/t_{max}},随着迭代次数自适应减小,既保证了迭代前期算法跳出局部最优进行全局搜索的能力,又保证了算法后期局部开发能力并保证算法的收敛性 .KbestK_{best}为适应度函数值较好的 k 个原子的集合,原子群的作用力如图2所示.

    在分子动力学模型中,几何约束在原子运动中是十分重要的因素.在ASO中,为了简单起见,假设每个原子与最优原子具有共价键,因此每个原子受来自最佳原子的约束力的作用,所以(1)式中的Gid(t)G_i^d(t)为第tt次迭代时dd维空间中全局最优原子对第ii个原子的几何约束作用,表示为:
    Gid(t)=λ(t)(Xbestd(t)Xid(t))(5) G_i^d(t)=\lambda(t)(X_{best}^d(t) - X_i^d(t)) \tag{5}
    式中,λ(t)=βe20t/tmax\lambda(t) = \beta e^{-20t/t_{max}},随着迭代次数做自适应调整;β\beta为乘数权重 .

    (1) 式中mid(t)m_i^d(t)为原子的质量,可表示为:

    mid(t)=Mi(t)/j=1NMj(t)(6) m_i^d(t) = M_i(t)/\sum_{j=1}^NM_j(t) \tag{6}

    ait(t)=Fid(t)/mid(t)+Gid(t)/mid(t)=α(1t1tmax)3e20t/tmaxjKbestrandj[2(hij(t))13(hij(t))7]mi(t)(7) a_i^t(t)=F_i^d(t)/m_i^d(t) + G_i^d(t)/m_i^d(t)=-\alpha(1-\frac{t-1}{t_{max}})^3e^{-20t/t_{max}}\sum_{j\in K_{best}}\frac{randj[2(h_{ij}(t))^13 - (h_{ij}(t))^7]}{m_i(t)} \tag{7}

    加速度使得原子运动速度及位移发生变化,这便是ASO算法的位置更新的核心过程,表示为:
    vid(t+1)=randidvid(t)+aid(t)(8) v_i^d(t+1) = rand_i^dv_i^d(t) + a_i^d(t) \tag{8}

    Xid(t+1)=Xid(t)+vid(t+1)(9) X_i^d(t+1)=X_i^d(t) + v_i^d(t+1)\tag{9}

    算法流程:

    Step1:初始化ASO各参数如种群规模,最大迭代次数等

    Step2:对原子种群进行初始化

    Step3:根据目标函数计算每个个体的适应度函数值,并保留为当前的最优值及最优解;

    Step4:根据公式(7)更新原子运动加速度;

    Step5:根据公式(8)更新原子运动速度;

    Step6:根据公式(9)更新原子个体位置;

    Step7:再次计算种群个体的适应度函数值,根据适应度值的优劣来更新最优解和最优值;

    Step8: 重复步骤4-8 ,直到达到最大迭代次数时终止操作;

    Step9: 输出最优个体位置以及最优适应度值;

    2.实验结果

    在这里插入图片描述

    3.参考文献

    [1]Weiguo Zhao,Liying Wang,Zhenxing Zhang. A novel atom search optimization for dispersion coefficient estimation in groundwater[J]. Future Generation Computer Systems,2019,91.

    [1]肖子雅,刘升.黄金正弦混合原子优化算法[J].微电子学与计算机,2019,36(06):21-25+30.

    4.Matlab代码

    https://mianbaoduo.com/o/bread/YZaXlp9t

    展开全文
  • 基于原子搜索优化算法的结构参数识别 摘 要 土木工程结构在服役过程中遭受着环境侵蚀建筑材料老化荷载长期作用和各种 突发性外在因素的耦合作用导致结构抗力衰减和发生损伤累积这给结构的安全性和 耐久性带来巨大...
  • Atom Search Optimization(ASO)是一种用于...ASO在数学上模拟和模拟自然界中的原子运动模型,其中原子通过相互作用力相互作用,形成Lennard-Jones势能和由键长潜力产生的约束力。该算法简单易行。包含matlab源代码
  • 原子搜索优化(ASO)是解决优化问题的一种新的优化方法。ASO在数学上模拟并模拟了自然界中的原子运动模型,在原子运动模型中,原子通过Lennard-Jones势所产生的相互作用力和键长势所产生的约束力彼此相互作用。该...

    ASO是用于解决优化问题的新的优化算法。

    原子搜索优化(ASO)是解决优化问题的一种新的优化方法。ASO在数学上模拟并模拟了自然界中的原子运动模型,在原子运动模型中,原子通过Lennard-Jones势所产生的相互作用力和键长势所产生的约束力彼此相互作用。该算法简单易实现。

    展开全文
  • 该方法在过完备阻尼正弦原子库的基础上,通过将余弦迁移模型、改进迁移算子以及混沌变异策略引入到IBBO算法对传统的匹配追踪算法进行优化,降低其搜索的时间复杂度。依据优化后的匹配追踪算法对次同步振荡信号进行...
  • 量子启发式进化算法(QEA)是高效的优化方法,具有强大的搜索能力和快速收敛性。 本文提出了QEA的改进变体在TFAD问题中的应用。 提出了具有进化算法的TFAD问题。 通过使用格雷编码,精英组和适当的终止条件,开发了...
  • 为解决梯级水库联合优化调度求解时间较长的问题,提出一种改进的电子搜索算法(IESA).改进算法在原算法的基础上,首先采用新的参数自适应方法,同时保证运算前期向优秀个体的迁移速度以及运算后期较强的局部搜索能力;...
  • * 人工智能讲义 * Herbrand定理H域 几个基本概念 ft1, t2, tnf为子句集S中的所有函数变量t1, t2, tn为S的H域的元素通过它们来讨论永真性 原子集A谓词套上H域的元素组成的集合如 A = {所有形如 P(t1, t2, tn)的元素} ...
  • java——保证原子性操作的CAS算法

    千次阅读 2017-12-14 10:34:47
    看了一堆文章,终于把JAVA CAS的原理深入分析清楚了。...感谢GOOGLE强大的搜索,借此挖苦下百度,依靠百度什么都学习不到!   参考文档: http://www.blogjava.net/xylz/archive/2010/07/04/325206.html ...

    看了一堆文章,终于把JAVA CAS的原理深入分析清楚了。

    感谢GOOGLE强大的搜索,借此挖苦下百度,依靠百度什么都学习不到!

     

    参考文档:

    http://www.blogjava.net/xylz/archive/2010/07/04/325206.html

    http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html

    http://www.searchsoa.com.cn/showcontent_69238.htm

    http://ifeve.com/atomic-operation/

    http://www.infoq.com/cn/articles/java-memory-model-5

     

    java.util.concurrent包完全建立在CAS之上的,没有CAS就不会有此包。可见CAS的重要性。

     

    CAS

    CAS:Compare and Swap, 翻译成比较并交换。 

    java.util.concurrent包中借助CAS实现了区别于synchronouse同步锁的一种乐观锁。

     

    本文先从CAS的应用说起,再深入原理解析。

     

    CAS应用

    CAS有3个操作数,内存值V,旧的预期值A,要修改的新值B。当且仅当预期值A和内存值V相同时,将内存值V修改为B,否则什么都不做。

     

    非阻塞算法 (nonblocking algorithms)

    一个线程的失败或者挂起不应该影响其他线程的失败或挂起的算法。

    现代的CPU提供了特殊的指令,可以自动更新共享数据,而且能够检测到其他线程的干扰,而 compareAndSet() 就用这些代替了锁定。

    拿出AtomicInteger来研究在没有锁的情况下是如何做到数据正确性的。

    private volatile int value;

    首先毫无以为,在没有锁的机制下可能需要借助volatile原语,保证线程间的数据是可见的(共享的)。

    这样才获取变量的值的时候才能直接读取。

    public final int get() {
            return value;
        }

    然后来看看++i是怎么做到的。

    public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return next;
        }
    }

    在这里采用了CAS操作,每次从内存中读取数据然后将此数据和+1后的结果进行CAS操作,如果成功就返回结果,否则重试直到成功为止。

    而compareAndSet利用JNI来完成CPU指令的操作。

    public final boolean compareAndSet(int expect, int update) {   
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
        }

    整体的过程就是这样子的,利用CPU的CAS指令,同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。

     

    其中

    unsafe.compareAndSwapInt(this, valueOffset, expect, update);

    类似:

    if (this == expect) {

      this = update

     return true;

    } else {

    return false;

    }

     

    那么问题就来了,成功过程中需要2个步骤:比较this == expect,替换this = update,compareAndSwapInt如何这两个步骤的原子性呢? 参考CAS的原理。

     

    CAS原理

     CAS通过调用JNI的代码实现的。JNI:Java Native Interface为JAVA本地调用,允许java调用其他语言。

    而compareAndSwapInt就是借助C来调用CPU底层指令实现的。

    下面从分析比较常用的CPU(intel x86)来解释CAS的实现原理。

     下面是sun.misc.Unsafe类的compareAndSwapInt()方法的源代码:

    public final native boolean compareAndSwapInt(Object o, long offset,
                                                  int expected,
                                                  int x);

     

    可以看到这是个本地方法调用。这个本地方法在openjdk中依次调用的c++代码为:unsafe.cpp,atomic.cpp和atomicwindowsx86.inline.hpp。这个本地方法的最终实现在openjdk的如下位置:openjdk-7-fcs-src-b147-27jun2011\openjdk\hotspot\src\oscpu\windowsx86\vm\ atomicwindowsx86.inline.hpp(对应于windows操作系统,X86处理器)。下面是对应于intel x86处理器的源代码的片段:

     

    // Adding a lock prefix to an instruction on MP machine
    // VC++ doesn't like the lock prefix to be on a single line
    // so we can't insert a label after the lock prefix.
    // By emitting a lock prefix, we can define a label after it.
    #define LOCK_IF_MP(mp) __asm cmp mp, 0  \
                           __asm je L0      \
                           __asm _emit 0xF0 \
                           __asm L0:
    
    inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
      // alternative for InterlockedCompareExchange
      int mp = os::is_MP();
      __asm {
        mov edx, dest
        mov ecx, exchange_value
        mov eax, compare_value
        LOCK_IF_MP(mp)
        cmpxchg dword ptr [edx], ecx
      }
    }
    

    如上面源代码所示,程序会根据当前处理器的类型来决定是否为cmpxchg指令添加lock前缀。如果程序是在多处理器上运行,就为cmpxchg指令加上lock前缀(lock cmpxchg)。反之,如果程序是在单处理器上运行,就省略lock前缀(单处理器自身会维护单处理器内的顺序一致性,不需要lock前缀提供的内存屏障效果)。

     

     intel的手册对lock前缀的说明如下:

    1. 确保对内存的读-改-写操作原子执行。在Pentium及Pentium之前的处理器中,带有lock前缀的指令在执行期间会锁住总线,使得其他处理器暂时无法通过总线访问内存。很显然,这会带来昂贵的开销。从Pentium 4,Intel Xeon及P6处理器开始,intel在原有总线锁的基础上做了一个很有意义的优化:如果要访问的内存区域(area of memory)在lock前缀指令执行期间已经在处理器内部的缓存中被锁定(即包含该内存区域的缓存行当前处于独占或以修改状态),并且该内存区域被完全包含在单个缓存行(cache line)中,那么处理器将直接执行该指令。由于在指令执行期间该缓存行会一直被锁定,其它处理器无法读/写该指令要访问的内存区域,因此能保证指令执行的原子性。这个操作过程叫做缓存锁定(cache locking),缓存锁定将大大降低lock前缀指令的执行开销,但是当多处理器之间的竞争程度很高或者指令访问的内存地址未对齐时,仍然会锁住总线。
    2. 禁止该指令与之前和之后的读和写指令重排序。
    3. 把写缓冲区中的所有数据刷新到内存中。

    备注知识:

    关于CPU的锁有如下3种:

      3.1 处理器自动保证基本内存操作的原子性

      首先处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存当中读取或者写入一个字节是原子的,意思是当一个处理器读取一个字节时,其他处理器不能访问这个字节的内存地址。奔腾6和最新的处理器能自动保证单处理器对同一个缓存行里进行16/32/64位的操作是原子的,但是复杂的内存操作处理器不能自动保证其原子性,比如跨总线宽度,跨多个缓存行,跨页表的访问。但是处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性。 

      3.2 使用总线锁保证原子性

      第一个机制是通过总线锁保证原子性。如果多个处理器同时对共享变量进行读改写(i++就是经典的读改写操作)操作,那么共享变量就会被多个处理器同时进行操作,这样读改写操作就不是原子的,操作完之后共享变量的值会和期望的不一致,举个例子:如果i=1,我们进行两次i++操作,我们期望的结果是3,但是有可能结果是2。如下图

     

     

      原因是有可能多个处理器同时从各自的缓存中读取变量i,分别进行加一操作,然后分别写入系统内存当中。那么想要保证读改写共享变量的操作是原子的,就必须保证CPU1读改写共享变量的时候,CPU2不能操作缓存了该共享变量内存地址的缓存。

      处理器使用总线锁就是来解决这个问题的。所谓总线锁就是使用处理器提供的一个LOCK#信号,当一个处理器在总线上输出此信号时,其他处理器的请求将被阻塞住,那么该处理器可以独占使用共享内存。

      3.3 使用缓存锁保证原子性

      第二个机制是通过缓存锁定保证原子性。在同一时刻我们只需保证对某个内存地址的操作是原子性即可,但总线锁定把CPU和内存之间通信锁住了,这使得锁定期间,其他处理器不能操作其他内存地址的数据,所以总线锁定的开销比较大,最近的处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。

      频繁使用的内存会缓存在处理器的L1,L2和L3高速缓存里,那么原子操作就可以直接在处理器内部缓存中进行,并不需要声明总线锁,在奔腾6和最近的处理器中可以使用“缓存锁定”的方式来实现复杂的原子性。所谓“缓存锁定”就是如果缓存在处理器缓存行中内存区域在LOCK操作期间被锁定,当它执行锁操作回写内存时,处理器不在总线上声言LOCK#信号,而是修改内部的内存地址,并允许它的缓存一致性机制来保证操作的原子性,因为缓存一致性机制会阻止同时修改被两个以上处理器缓存的内存区域数据,当其他处理器回写已被锁定的缓存行的数据时会起缓存行无效,在例1中,当CPU1修改缓存行中的i时使用缓存锁定,那么CPU2就不能同时缓存了i的缓存行。

      但是有两种情况下处理器不会使用缓存锁定。第一种情况是:当操作的数据不能被缓存在处理器内部,或操作的数据跨多个缓存行(cache line),则处理器会调用总线锁定。第二种情况是:有些处理器不支持缓存锁定。对于Inter486和奔腾处理器,就算锁定的内存区域在处理器的缓存行中也会调用总线锁定。

      以上两个机制我们可以通过Inter处理器提供了很多LOCK前缀的指令来实现。比如位测试和修改指令BTS,BTR,BTC,交换指令XADD,CMPXCHG和其他一些操作数和逻辑指令,比如ADD(加),OR(或)等,被这些指令操作的内存区域就会加锁,导致其他处理器不能同时访问它。

     

    CAS缺点

     CAS虽然很高效的解决原子操作,但是CAS仍然存在三大问题。ABA问题,循环时间长开销大和只能保证一个共享变量的原子操作

    1.  ABA问题。因为CAS需要在操作值的时候检查下值有没有发生变化,如果没有发生变化则更新,但是如果一个值原来是A,变成了B,又变成了A,那么使用CAS进行检查时会发现它的值没有发生变化,但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号,每次变量更新的时候把版本号加一,那么A-B-A 就会变成1A-2B-3A。

    从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用,并且当前标志是否等于预期标志,如果全部相等,则以原子方式将该引用和该标志的值设置为给定的更新值。

    关于ABA问题参考文档: http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html

    2. 循环时间长开销大。自旋CAS如果长时间不成功,会给CPU带来非常大的执行开销。如果JVM能支持处理器提供的pause指令那么效率会有一定的提升,pause指令有两个作用,第一它可以延迟流水线执行指令(de-pipeline),使CPU不会消耗过多的执行资源,延迟的时间取决于具体实现的版本,在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突(memory order violation)而引起CPU流水线被清空(CPU pipeline flush),从而提高CPU的执行效率。

     

    3. 只能保证一个共享变量的原子操作。当对一个共享变量执行操作时,我们可以使用循环CAS的方式来保证原子操作,但是对多个共享变量操作时,循环CAS就无法保证操作的原子性,这个时候就可以用锁,或者有一个取巧的办法,就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i=2,j=a,合并一下ij=2a,然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性,你可以把多个变量放在一个对象里来进行CAS操作。

     

     

    concurrent包的实现

    由于java的CAS同时具有 volatile 读和volatile写的内存语义,因此Java线程之间的通信现在有了下面四种方式:

    1. A线程写volatile变量,随后B线程读这个volatile变量。
    2. A线程写volatile变量,随后B线程用CAS更新这个volatile变量。
    3. A线程用CAS更新一个volatile变量,随后B线程用CAS更新这个volatile变量。
    4. A线程用CAS更新一个volatile变量,随后B线程读这个volatile变量。

    Java的CAS会使用现代处理器上提供的高效机器级别原子指令,这些原子指令以原子方式对内存执行读-改-写操作,这是在多处理器中实现同步的关键(从本质上来说,能够支持原子性读-改-写指令的计算机器,是顺序计算图灵机的异步等价机器,因此任何现代的多处理器都会去支持某种能对内存执行原子性读-改-写操作的原子指令)。同时,volatile变量的读/写和CAS可以实现线程之间的通信。把这些特性整合在一起,就形成了整个concurrent包得以实现的基石。如果我们仔细分析concurrent包的源代码实现,会发现一个通用化的实现模式:

    1. 首先,声明共享变量为volatile;
    2. 然后,使用CAS的原子条件更新来实现线程之间的同步;
    3. 同时,配合以volatile的读/写和CAS所具有的volatile读和写的内存语义来实现线程之间的通信。

    AQS,非阻塞数据结构和原子变量类(java.util.concurrent.atomic包中的类),这些concurrent包中的基础类都是使用这种模式来实现的,而concurrent包中的高层类又是依赖于这些基础类来实现的。从整体来看,concurrent包的实现示意图如下:

    展开全文
  • 爬山算法是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。这种算法思想很单纯,但是也存在一个很大的缺陷。在搜索选择的过程中有可能会陷入局部最优...

    一 局部搜索算法

    对于复杂的问题,求解最优解比较麻烦,耗费大量时间,退而求其次,诞生了各种启发式算法来求解其次优解或近似最优解。局部搜索算法是一种解决优化问题的一种启发式算法,是一种简单的贪心搜索算法。

    算法思想:从一个邻居解开始,通过邻域动作产生邻居解,然后根据策略需求,对邻居解进行选择,一直重复上述操作,直到达到终止条件。

    不同的局部搜索算法之间的区别在于:领域动作的定义、对领域解进行选择时的策略。

    领域动作一般是一个函数,通过该函数可以根据当前的解产生所对应的邻居解的集合。

    二 简单局部搜索

    1:爬山法

    爬山算法是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。这种算法思想很单纯,但是也存在一个很大的缺陷。在搜索选择的过程中有可能会陷入局部最优解,而这个局部最优解不一定是全局最优解。

    爬山法是完完全全的贪心法。


    2:模拟退火

    2.1 背景

    物理退火( 材料中的原子原来会停留在使内能有局部最小值的位置,加热使能量变大,原子会离开原来位置,而随机在其他位置中移动。退火冷却时速度较慢,使得原子有较多可能可以找到内能比原先更低的位置。【简言之:加热的时候快速、随机分散到各处;退火的时候,降温(移动)】

    2.2 基本思想

     模拟退火算法原理也和物理上固体退火的原理近似,是一种全局优化的贪心算法,在贪心的时候一定概率接受一个更差的解(从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解),即在局部最优解时能概率性地跳出并最终趋于全局最优,具有很好的跳出局部最优的能力,在算法后期有良好的收敛性。

    简言之,模拟退火其实是一种贪心算法,只不过与爬山法不同的是,模拟退火算法在搜索过程引入了随机因素模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。

    2.3 算法流程

    上面提到该算法比较核心的部分是以一定的概率来接受一个比当前结果更差的一个解,对于“一定的概率”的定义,根据热力学的定义,在温度为T的时候,出现能量差为dE的降温概率为P(dE)=exp(dE/(kT))

    其中:dE表示能量差,dE<0(由于是降温,温度是变低的)

    exp代表自然常数

    k为一个常数

    结合指数函数的图像以及指数部分是负数的特性,可以知道P(dE)的取值范围为(0,1),如下图红色曲线所示:

    (图比较丑,用附件画图直接画的,请见谅【鬼脸】)

    随着温度的降低,p的值也逐渐降低,于是接受更差的解的概率也就越小,退火过程就趋于稳定。

    伪代码:

    while(T>T_min)

    {

    计算dE;

    如果变好,则接受,

    否则如果概率大于一个随机概率,则接受(以一定概率接受较差的结果)。

    降温

    }

    模拟退火的整体思想是:接纳一定的“不好”,可能最后得到的“更好”

    三 迭代局部搜索

    迭代局部搜索属于探索性局部搜索方法(EXPLORATIVE LOCAL SEARCH METHODS)的一种。它在局部搜索得到的局部最优解上,加入了扰动,然后再重新进行局部搜索。

    【ing,有机会会继续补充】

     

    展开全文
  • 量子计算带来超高速和超高效处理的可能性,搜索引擎巨头Google现在也出现在这个领域的风头浪尖上。New Scientist说Google在过去的三年中一直都在研究一种可以自动识别和分类图像或视频的量子算法。量子计算主要关注...
  • 原子引用AtomicReference

    2020-10-16 17:30:47
    作者简介:笔名seaboat,擅长工程算法、人工智能算法、自然语言处理、计算机视觉、架构、分布式、高并发、大数据和搜索引擎等方面的技术,大多数编程语言都会使用,但更擅长Java、Python和C++。平时喜欢看书写作、...
  • 因此,提出了一种基于用户、Mashup、服务、标签的服务社会化网络的搜索和推荐算法,此算法能同时推荐原子级服务和组合服务,并且既考虑了用户对服务的兴趣剖面,又考虑了服务对标签的满足度剖面。实验从准确率、召回...
  • 作者简介:笔名seaboat,擅长工程算法、人工智能算法、自然语言处理、计算机视觉、架构、分布式、高并发、大数据和搜索引擎等方面的技术,大多数编程语言都会使用,但更擅长Java、Python和C++。平时喜欢看书写作、...
  • 作者简介:笔名seaboat,擅长工程算法、人工智能算法、自然语言处理、计算机视觉、架构、分布式、高并发、大数据和搜索引擎等方面的技术,大多数编程语言都会使用,但更擅长Java、Python和C++。平时喜欢看书写作、...
  • MMP算法提出的文献: ...主要贡献:文章将传统贪婪算法原子选择问题建模为组合树的搜索问题,为原子选择提供了新的思路。 在传统贪婪算法的改进中,不外乎以下几个方面:调整原子选择策略,调整原子相似性的准则...
  • 作者简介:笔名seaboat,擅长工程算法、人工智能算法、自然语言处理、计算机视觉、架构、分布式、高并发、大数据和搜索引擎等方面的技术,大多数编程语言都会使用,但更擅长Java、Python和C++。平时喜欢看书写作、...
  • 首先,通过量子编码的叠加性构造抗体、免疫克隆操作实现种群扩张,以加速原子搜索进程,同时借助量子交叉操作避免算法陷入局部最优。然后,利用各次迭代选取的最佳匹配原子完成惯性传感器信号的重构,从而达到滤波的...
  • 针对电能质量中的复合扰动信号分析问题,提出一种粒子群优化(PSO)和匹配追踪(MP)算法相结合的分层搜索原子分解方法。首先应用MP算法提取基波分量,对于去除基波分量的残差信号,利用快速傅里叶变换找寻能量最大的...
  • 基于遗传算法的多道地震信号匹配追踪快速分解,王利君,王珺,以匹配追踪算法为基础,本文提出了基于遗传算法的多道地震信号匹配追踪快速分解算法。即通过改变搜索最佳匹配原子的准则函数,同
  • MQEPS是P系统方法,量子启发式进化算法和局部搜索的适当组合,它是通过使用类细胞P系统的分层框架进行设计的,该对象由量子启发性比特和经典比特组成,规则由系统中量子激发的门进化规则和进化规则的建立,以及在...
  • 仿真结果表明,基于改进的物种形成粒子群算法能够搜索到与跳频信号分量相匹配的原子,与平滑伪魏格纳分布相比,提出的参数估计算法在低信噪比下具有较小的估计方差,更加适宜于电子战的实际应用。
  • 研究基于Matching Pursuit(MP)方法...该算法针对语音信号的特点,以FFT算法实现的稀疏分解为基础缩小了原子搜索范围,从而不仅进一步提高分解速度,还能以更稀疏的形式表示语音信号。算法的有效性为实验结果所证实。
  • 传统声纳成像系统所要采集的...考虑到水下环境的复杂性,提出了A*OMP作为声纳成像算法,该算法使用A*搜索方法寻找最优原子,得到全局最优路径。实验结果表明,相比于传统OMP算法,所提算法有效地提高了声纳成像的质量。
  • 针对图论中的最短路径问题,提出了两种在GPU上改进的最短路径搜索算法,即针对单源最短路径问题的基于迭代方式且采用原子锁优化的Advanced_Atomics_SSSP算法以及针对所有顶点间最短路径问题的采用二叉堆优化的Heap_...
  • 量子算法与量子计算实验

    千次阅读 2009-12-22 10:25:00
    在对量子计算基本理论和量子算法有一定认识的基础上,进一步介绍了在量子计算实验方面起重要作用的二种体系:核磁共振、腔与原子体系。 [关键词]量子算法、量子计算、量子比特、纠缠Abstract:In th
  • 结合智能算法FOA及LM算法的优点,采用FOA算法求出Gabor原子参数初值,利用这些初值进行LM迭代搜索最优原子。仿真结果表明,基于FOA优化算法和LM算法相结合的方法,具有收敛速度快,精度高的特点,有较高的实用价值。
  • 首先利用遗传算法全局搜索能力强的特点优化初始权值,然后发挥BP算法局部搜索速度快的特点得到最佳权值。经计算机仿真表明,该算法与传统BP神经网络盲均衡算法相比,收敛速度加快,稳态剩余误差减小,误码率降低。
  • 在该算法中,引入变量对0和1(相对表示两个原子)以提高初始阶段的搜索优化速度,并添加了模拟退火算子以避免过早收敛并陷入局部最优解。 包含3285个原子的四面体(THH)Pt-Pd双金属NP用于测试该算法的有效性。 ...
  • 4.2.2 基本的广度优先搜索算法 33 4.2.3 应用 34 4.3 最短路径 35 4.4 最小生成树 36 4.4.1 问题 36 4.4.2 基本定理 36 4.4.3 算法 37 4.5 最大独立集 39 4.5.1 问题 40 4.5.2 随机化算法 40 4.5.3 分析* ...

空空如也

空空如也

1 2 3 4
收藏数 80
精华内容 32
关键字:

原子搜索算法