智能优化算法

• 差分进化算法

  • 概述

    • 差分进化算法（Differential Evolution，DE）是一种新兴的进化计算技术 。它是由 Storn 等人于1995年提出的，其最初的设想是用于解决切比雪夫多项式问题，后来发现它也是解决复杂优化问题的有效技术。
    • 差分进化算法是基于群体智能理论的优化算法，是通过群体内个体间的合作与竞争而产生的智能优化搜索算法。但相比于进化计算，它保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和“一对一”的竞争生存策略，降低了进化计算操作的复杂性。同时，差分进化算法特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，它具有较强的全局收敛能力和稳健性，且不需要借助问题的特征信息，适用于求解一些利用常规的数学规划方法很难求解甚至无法求解的复杂优化问题。因此，差分进化算法作为一种高效的并行搜索算法，对其进行理论和应用研究具有重要的学术意义和工程价值。
    • 目前，差分进化算法已经在许多领域得到了应用，如人工神经元网络、电力、机械设计、机器人、信号处理、生物信息、经济学、现代农业和运筹学等。然而，尽管差分进化算法获得了广泛研究，但相对于其他进化算法而言，其研究成果相当分散，缺乏系统性，尤其在理论方面还没有重大突破。

  • 原理

    • 差分进化算法是一种随机的启发式搜索算法，简单易用，有较强的鲁棒性和全局寻优能力。它从数学角度看是一种随机搜索算法，从工程角度看是一种自适应的迭代寻优过程。除了具有较好的收敛性外，差分进化算法非常易于理解与执行，它只包含不多的几个控制参数，并且在整个迭代过程中，这些参数的值可以保持不变。
    • 差分进化算法是一种自组织最小化方法，用户只需很少的输入。它的关键思想与传统进化方法不同：传统方法是用预先确定的概率分布函数决定向量扰动；而差分进化算法的自组织程序利用种群中两个随机选择的不同向量来干扰一个现有向量，种群中的每一个向量都要进行干扰。差分进化算法利用一个向量种群，其中种群向量的随机扰动可独立进行，因此是并行的。如果新向量对应函数值的代价比它们的前辈代价小，它们将取代前辈向量。
    • 同其他进化算法一样，差分进化算法也是对候选解的种群进行操作，但其种群繁殖方案与其他进化算法不同：它通过把种群中两个成员之间的加权差向量加到第三个成员上来产生新的参数向量，该操作称为“变异”；然后将变异向量的参数与另外预先确定的目标向量参数按一定规则混合来产生试验向量，该操作称为“交叉”；最后，若试验向量的代价函数比目标向量的代价函数低，试验向量就在下一代中代替目标向量，该操作称为“选择”。种群中所有成员必须当作目标向量进行一次这样的操作，以便在下一代中出现相同个数竞争者。在进化过程中对每一代都对最佳参数向量进行评价，以记录最小化过程。这样利用随机偏差扰动产生新个体的方式，可以获得一个收敛性非常好的结果，引导搜索过程向全局最优解逼近

  • 特点

    • （1）结构简单，容易使用。差分进化算法主要通过差分变异算子来进行遗传操作，由于该算子只涉及向量的加减运算，因此很容易实现；该算法采用概率转移规则，不需要确定性的规则。此外，差分进化算法的控制参数少，这些参数对算法性能的影响已经得到一定的研究，并得出了一些指导性的建议，因而可以方便使用人员根据问题选择较优的参数设置。
    • 2）性能优越。差分进化算法具有较好的可靠性、高效性和鲁棒性，对于大空间、非线性和不可求导的连续问题，其求解效率比其他进化方法好，而且很多学者还在对差分进化算法继续改良，以不断提高其性能。
    • （3）自适应性。差分进化算法的差分变异算子可以是固定常数，也可以具有变异步长和搜索方向自适应的能力，根据不同目标函数进行自动调整，从而提高搜索质量。
    • （4）差分进化算法具有内在的并行性，可协同搜索，具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力。在同样精度要求下，差分进化算法具有更快的收敛速度。
    • （5）算法通用，可直接对结构对象进行操作，不依赖于问题信息，不存在对目标函数的限定。差分进化算法操作十分简单，易于编程实现，尤其利于求解高维的函数优化问题。

  • 算法流程

    • 

• 免疫算法

  • 概述

    • Immune（免疫）是从拉丁文衍生而来的。很早以前，人们就注意到传染病患者痊愈后，对该病会有不同程度的免疫力。在医学上，免疫是指机体接触抗原性异物的一种生理反应。1958年澳大利亚学者Burnet先提出了与免疫算法（Immune Algorithm，IA）相关的理论——率克隆选择原理 。1973年Jerne提出免疫系统的模型 ，他基于Burnet的克隆选择学说，开创了独特型网络理论，给出了免疫系统的数学框架，并采用微分方程建模来仿真淋巴细胞的动态变化。
    • 1986年Farmal等人基于免疫网络学说理论构造出的免疫系统的动态模型，展示了免疫系统与其他人工智能方法相结合的可能性，开创了免疫系统研究的先河。他们先利用一组随机产生的微分方程建立起人工免疫系统，再通过采用适应度阈值过滤的方法去掉方程组中那些不合适的微分方程，对保留下来的微分方程则采用交叉、变异、逆转等遗传操作产生新的微分方程，经过不断的迭代计算，直到找到最佳的一组微分方程为止。
    • 从此以后，对免疫算法的研究在国际上引起越来越多学者的兴趣。几十年来，与之相关的研究成果已经涉及非线性最优化、组合优化、控制工程、机器人、故障诊断、图像处理等诸多领域  。
    • 生物免疫系统是一个复杂的自适应系统。免疫系统能够识别出病原体，具有学习、记忆和模式识别能力，因此可以借鉴其信息处理机制来解决科学和工程问题。免疫算法正是基于生物免疫系统识别外部病原体并产生抗体对抗病原体的学习机制而提出的，由此诞生了基于免疫原理的智能优化方法研究这一新的研究方向。

  • 优点

    • 免疫算法是模仿生物免疫机制，结合基因的进化机理，人工构造出的一种新型智能优化算法。它具有一般免疫系统的特征，采用群体搜索策略，通过迭代计算，最终以较大的概率得到问题的最优解。相比较于其他算法，免疫算法利用自身产生多样性和维持机制的特点，保证了种群的多样性，克服了一般寻优过程（特别是多峰值的寻优过程）中不可避免的“早熟”问题，可以求得全局最优解。免疫算法具有自适应性、随机性、并行性、全局收敛性、种群多样性等优点。

  • 算法流程

    • 

群智能算法

• 蚁群算法(ACO)

  • 概述

    • 蚁群算法是一种源于大自然生物世界的新的仿生进化算法，由意大利学者M. Dorigo，V. Maniezzo和A. Colorni等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法 [1] 。蚂蚁有能力在没有任何提示的情形下找到从巢穴到食物源的最短路径，并且能随环境的变化，适应性地搜索新的路径，产生新的选择。其根本原因是蚂蚁在寻找食物时，能在其走过的路径上释放一种特殊的分泌物——信息素 [2] （也称外激素），随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，后来蚂蚁选择该路径的概率也就越高，从而更增加了该路径上的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径。
    • 蚁群算法具有分布式计算、无中心控制和分布式个体之间间接通信等特征，易于与其他优化算法相结合，它通过简单个体之间的协作表现出了求解复杂问题的能力，已被广泛应用于求解优化问题。蚁群算法相对而言易于实现，且算法中并不涉及复杂的数学操作，其处理过程对计算机的软硬件要求也不高，因此对它的研究在理论和实践中都具有重要的意义。
    • 目前，国内外的许多研究者和研究机构都开展了对蚁群算法理论和应用的研究，蚁群算法已成为国际计算智能领域关注的热点课题。虽然目前蚁群算法没有形成严格的理论基础，但其作为一种新兴的进化算法已在智能优化等领域表现出了强大的生命力。

  • 特点

    • （1）蚁群算法是一种本质上的并行算法。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法可以看作一个分布式的多智能体系统，它在问题空间的多点同时开始独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。
    • （2）蚁群算法是一种自组织的算法。所谓自组织，就是组织力或组织指令来自于系统的内部，以区别于其他组织。如果系统在获得空间、时间或者功能结构的过程中，没有外界的特定干预，就可以说系统是自组织的。简单地说，自组织就是系统从无序到有序的变化过程。
    • （3）蚁群算法具有较强的鲁棒性。相对于其他算法，蚁群算法对初始路线的要求不高，即蚁群算法的求解结果不依赖于初始路线的选择，而且在搜索过程中不需要进行人工的调整。此外，蚁群算法的参数较少，设置简单，因而该算法易于应用到组合优化问题的求解。
    • （4）蚁群算法是一种正反馈算法。从真实蚂蚁的觅食过程中不难看出，蚂蚁能够最终找到最优路径，直接依赖于其在路径上信息素的堆积，而信息素的堆积是一个正反馈的过程。正反馈是蚁群算法的重要特征，它使得算法进化过程得以进行。

  • 算法流程

    • 

    我创作的作品 (mbd.pub)

• • 改进的蚁群算法

  • 针对基本蚁群算法一般需要较长的搜索时间和容易出现停滞现象等不足，很多学者在此基础上提出改进算法，提高了算法的性能和效率。
    • 精英蚂蚁系统
    • 最大最小蚂蚁系统
    • 基于排序的蚁群算法
    • 自适应蚁群算法
  • 快速自适应动态蚁群算法(AFD-ACO)

• 粒子群算法(PSO)

  • 概述

    • 1995年，美国社会心理学家James Kennedy和电气工程师Russell Eberhart共同提出了粒子群算法（Particle Swarm Optimization，PSO），该算法的提出是受对鸟类群体行为进行建模与仿真的研究结果的启发。他们的模型和仿真算法主要对Frank Heppner的模型进行了修正，以使粒子飞向解空间并在最优解处降落。粒子群算法一经提出，由于其算法简单，容易实现，立刻引起了进化计算领域学者们的广泛关注，形成一个研究热点。2001年出版的J. Kennedy与R. Eberhart合著的《群体智能》将群体智能的影响进一步扩大 [1] ，随后关于粒子群优化算法的研究报告和研究成果大量涌现，继而掀起了国内外研究热潮。
    • 粒子群优化算法来源于鸟类群体活动的规律性，进而利用群体智能建立一个简化的模型。它模拟鸟类的觅食行为，将求解问题的搜索空间比作鸟类的飞行空间，将每只鸟抽象成一个没有质量和体积的粒子，用它来表征问题的一个可能解，将寻找问题最优解的过程看成鸟类寻找食物的过程，进而求解复杂的优化问题。粒子群优化算法与其他进化算法一样，也是基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索。同时，它又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是将群体中的个体看作在D维搜索空间中没有质量和体积的粒子，每个粒子以一定的速度在解空间运动，并向自身历史最佳位置p best 和邻域历史最佳位置g best 聚集，实现对候选解的进化。粒子群算法具有很好的生物社会背景而易于理解，由于参数少而容易实现，对非线性、多峰问题均具有较强的全局搜索能力，在科学研究与工程实践中得到了广泛关注。目前，该算法已广泛应用于函数优化、神经网络训练、模式分类、模糊控制等领域。
    • 粒子群算法本质是一种随机搜索算法，它是一种新兴的智能优化技术。该算法能以较大概率收敛于全局最优解。实践证明，它适合在动态、多目标优化环境中寻优，与传统优化算法相比，具有较快的计算速度和更好的全局搜索能力。

  • 特点

    • （1）粒子群算法是基于群智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索。与其他算法相比，粒子群算法是一种高效的并行搜索算法。
    • （2）粒子群算法与遗传算法都是随机初始化种群，使用适应值来评价个体的优劣程度和进行一定的随机搜索。但粒子群算法根据自己的速度来决定搜索，没有遗传算法的交叉与变异。与进化算法相比，粒子群算法保留了基于种群的全局搜索策略，但是其采用的速度-位移模型操作简单，避免了复杂的遗传操作。
    • （3）由于每个粒子在算法结束时仍保持其个体极值，即粒子群算法除了可以找到问题的最优解外，还会得到若干较好的次优解，因此将粒子群算法用于调度和决策问题可以给出多种有意义的方案。
    • （4）粒子群算法特有的记忆使其可以动态地跟踪当前搜索情况并调整其搜索策略。另外，粒子群算法对种群的大小不敏感，即使种群数目下降时，性能下降也不是很大。

  • 算法流程

    • 

    我创作的作品 (mbd.pub)

• 蝙蝠算法(Bat Algorithm,BA)

  • 优点：BA在保持简易结构的同时还拥有较好的搜索能力。
  • 缺点：迭代搜索时仍存在一定缺陷,如结果精度偏低、在得到局部较优解后搜索易陷入停滞、无法保持稳定的寻优结果等。
  • 改进算法：
    • 混合蝙蝠算法(Golden Sine Bat Algorithm,GSBA),该算法主要引入黄金正弦算子并结合种群平均位置对个体位置进行更新。
    • 三维空间中无人机路径规划的改进型蝙蝠算法(IBA)：根据标准BA和人工蜂群算法(ABC)的特点，使用ABC对BA进行修改，解决了BA局部搜索能力差的问题。解决静态环境下无人机的飞行路径规划问题。主要目的是使无人机在复杂的三维战场环境中，在起点和终点之间获得无事故、更短、更安全的飞行路径。

模拟退火算法

• 概述

  • 模拟退火算法（Simulated Annealing，SA）的思想最早由Metropolis等人于1953年提出；Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题 [1] 。模拟退火算法是一种基于Monte Carlo迭代求解策略的随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。其目的在于为具有NP（Non-deterministic Polynomial）复杂性的问题提供有效的近似求解算法，它克服了其他优化过程容易陷入局部极小的缺陷和对初值的依赖性。
  • 模拟退火算法是一种通用的优化算法，是局部搜索算法的扩展。它不同于局部搜索算法之处是以一定的概率选择邻域中目标值大的劣质解。从理论上说，它是一种全局最优算法。模拟退火算法以优化问题的求解与物理系统退火过程的相似性为基础，它利用Metropolis算法并适当地控制温度的下降过程来实现模拟退火，从而达到求解全局优化问题的目的 [2]。
  • 模拟退火算法是一种能应用到求最小值问题的优化过程。在此过程中，每一步更新过程的长度都与相应的参数成正比，这些参数扮演着温度的角色。与金属退火原理相类似，在开始阶段为了更快地最小化，温度被升得很高，然后才慢慢降温以求稳定。
  • 目前，模拟退火算法迎来了兴盛时期，无论是理论研究还是应用研究都成了十分热门的课题 [3] - [7] 。尤其是它的应用研究显得格外活跃，已在工程中得到了广泛应用，诸如生产调度、控制工程、机器学习、神经网络、模式识别、图像处理、离散/连续变量的结构优化问题等领域。它能有效地求解常规优化方法难以解决的组合优化问题和复杂函数优化问题，适用范围极广。
  • 模拟退火算法具有十分强大的全局搜索性能，这是因为比起普通的优化搜方法，它采用了许多独特的方法和技术：在模拟退火算法中，基本不用搜索空间的知识或者其他的辅助信息，而只是定义邻域结构，在其邻域结构内选取相邻解，再利用目标函数进行评估；模拟退火算法不是采用确定性规则，而是采用概率的变迁来指导它的搜索方向，它所采用的概率仅仅是作为一种工具来引导其搜索过程朝着更优化解的区域移动。因此，虽然看起来它是一种盲目的搜索方法，但实际上有着明确的搜索方向。

• 优点

  • 模拟退火算法适用范围广，求得全局最优解的可靠性高，算法简单，便于实现；该算法的搜索策略有利于避免搜索过程因陷入局部最优解的缺陷，有利于提高求得全局最优解的可靠性。模拟退火算法具有十分强的鲁棒性，这是因为比起普通的优化搜索方法，它采用许多独特的方法和技术。
  • （1）以一定的概率接受恶化解；
  • （2）引进算法控制参数；
  • （3）对目标函数要求少。

• 改进方向

  • 在确保一定要求的优化质量基础上，提高模拟退火算法的搜索效率，是对模拟退火算法改进的主要内容 [9] - [10] 。有如下可行的方案：选择合适的初始状态；设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性；设计高效的退火过程；改进对温度的控制方式；采用并行搜索结构；设计合适的算法终止准则；等等。
  • （1）增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将到目前为止的最好状态存储下来。
  • （2）增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避兔算法在局部极小解处停滞不前。
  • （3）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而不是标准模拟退火算法的单次比较方式。
  • （4）与其他搜索机制的算法（如遗传算法、免疫算法等）相结合。可以综合其他算法的优点，提高运行效率和求解质量。

• 算法流程

  • 

   参考书籍：《智能优化算法及其MATLAB实例》包子阳、余继周编著