传送门:IOA -「杂七杂八」
遗传算法(Genetic Algorithm,GA)是模拟生物在自然界中的遗传和进化过程,从而形成的自适应全局优化算法。它起源于 20 世纪 60 年代人们对自然和人工自适应系统的研究,最早由美国 J.H.Holland
提出,并于 80 年代由 D.J.Goldberg
在一系列研究工作的基础上归纳总结而成。
遗传算法是通过模拟自然界生物进化机制而发展起来的随机全局搜索和优化方法。它借鉴了达尔文的进化论和孟德尔的遗传的遗传学说,使用 “适者生存” 的原则,本质上是一种并行、高效、全局搜索的方法;它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制过程以求得最优解。
差分进化(Differential Evolution,DE)算法最初用于解决切比雪夫多项式问题,后来发现该算法也是解决复杂优化问题的有效技术。
差分进化算法是一种新兴的进化计算技术,它基于群体智能理论,是通过群体内个体间的合作与竞争产生的智能优化搜索算法。但相比于进化计算,差分进化算法保留了基于种群的全局搜索策略,采用实数编码、基于差分的简单变异操作和 “一对一” 的竞争生存策略,降低了进化计算的复杂性。同时,差分进化算法具有较强的全局收敛能力和鲁棒性,且不需要借助问题的特征信息适用于求解一些利用常规的数学规划方法很难求解甚至无法求解的复杂优化问题。
最早的免疫系统模型由 Jerne 于 1973 年提出,他基于 Burnet 的克隆选择学说,开创了独特型网络理论,给出了免疫系统的数学框架。Farmal 等人于 1986 年基于免疫网络学说理论构造出免疫系统的动态模型,展示了免疫系统与其他人工智能方法相结合的可能性,开创了免疫系统研究的先河。
免疫算法(Immune Algorithm,IA)是模仿生物免疫机制,结合基因的进化机理,人工构造出的一种新型智能优化算法,免疫算法具有一般免疫系统的特征,它采用群体搜索策略,通过迭代计算,最终以较大的概率得到问题的最优解。相比于其他算法,免疫算法克服了一般寻优过程中(特别是多峰值的寻优过程中)不可避免的 “早熟” 问题,可求得全局最优解,具有自适应性、随机性、并行性、全局收敛性、种群多样性等优点。
群智能指的是 “无智能的主体通过合作表现出智能行为的特征”,是一种基于生物群体行为规律的计算技术。它受社会昆虫(如鸟群、鱼群和兽群)的启发,用来解决分布式问题。它在没有集中控制并且不提供全局模型的前提下,为寻找复杂的分布式问题的解决方案提供了一种新的思路。
群智能方法易于实现,其算法中仅涉及各种基本的数学操作,其数据处理过程对 CPU 和内存的要求也不高。而且,这种方法只需要目标函数的输入值,而不需要其梯度信息。
蚂蚁在寻找食物时,能在其走过的路径上释放一种特殊的分泌物——信息素。随着时间的退役,该物质会逐渐挥发,后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时,其留下的信息素也越来越多,后来的蚂蚁选择该路径的概率也就越高,从而更增加了该路径上的信息素强度。二强度大的信息素会吸引更多的蚂蚁,从而形成一种正反馈机制。通过这种正反馈机制,蚂蚁最终可以发现最短路径。
蚁群算法(Ant Colony Optimization,ACO)就是通过模拟自然界中蚂蚁集团寻径行为而提出的一种基于种群的启发式随即搜索算法,是群智能理论研究领域的一种重要算法。
蚁群算法具有分布式计算、无中心控制和分布式个体之间间接通讯的等特征,易于与其他优化算法相结合,已经广泛用于优化问题的求解。
粒子群算法(Particle Swarm Optimization,PSO)是 Kennedy 和 Eberhart 受人工生命研究成果的启发,通过模拟鸟群觅食过程中的前夕和群聚行为而提出的一种基于种群智能的全局随机搜索方法。
与其他进化方法一样,粒子群算法也是基于 “种群” 和 “进化” 的概念,通过个体间的协作与竞争,实现复杂空间最优解的搜索。但是,它对个体不进行交叉、变异、选择等进化算子的操作,而是将群体中的个体看成是在 D 维搜索空间中没有质量和体积的粒子,每个粒子以一定的速度在解空间运动,并向自身历史最佳位置 pbest 和群体历史最佳位置 gbest 聚集,实现对候选解的进化。
模拟退火(Suimulated Annealing,SA)算法是一种基于 Monte Carlo 迭代求解策略的三场寻优算法,它基于物理中固体物质的退火过程与一般组合优化问题之间的相似性,其目的在于为具有 NP(Non-deterministic Polynomial)复杂性的问题提供有效的近似求解算法;该算法克服了传统算法优化过程容易陷入局部最优极值的缺陷和对初值的依赖性。
禁忌搜索(Tabu Search or Taboo Search,TS)算法以其灵活的存储结构和相应的禁忌准则来避免迂回搜索,在智能算法中独树一帜。TS 是对局部领域搜索的一种扩展,它在通过禁忌准则来避免重复搜索的同时,通过藐视准则来赦免一切被禁忌的优良状态,进而保证多样性的有效搜索,以最终实现全局优化。
人工神经网络(Artificial Neural Network,ANN)简称为神经网络或称为连接模型。1943 年形成神经元的数据模型的提出,1982 年 J.J.Hopfield 提出了具有联想记忆的 Hopfield 神经网络,引入能量函数的原理,给出了网络的稳定性判据。
神经网络是一种模仿生物神经系统的新型信息处理模型,具有独特的结构,其显著的特点如下:具有非线性映射能力;不需要精确的数学模型;擅长从输入输出数据中学习有用的知识;容易实现并行计算;由大量的简单计算神经元组成,易于用软硬件实现;等等。
遗传学术语 | 遗传算法术语 |
---|---|
群体 | 可行解集 |
个体 | 可行解 |
染色体 | 可行解的编码 |
基因 | 可行解编码的分量 |
基因形式 | 遗传编码 |
适应度 | 函数评价值 |
遗传算法是模拟生物在自然界中的遗传和进化的过程而形成的一种并行、高效、全局搜索的方法,它有以下特点:
遗传算法以决策变量的编码作为运算对象。使得在优化计算过程中可以借鉴生物学中的染色体和基因等概念,模拟自然界中生物的遗传和进化等的机理,方便地应用遗传操作算子。特别是对一些只有代码概念而无数值概念或很难有数值概念的优化问题,编码处理方式更显示出了其独特的优越性。
遗传算法直接以目标函数值作为搜索信息。它仅使用由目标函数值变换来的适应度函数值,就可确定进一步的搜索方向和搜索范围,而不需要目标函数的导数值等其他一些辅助信息。避开了函数求导这个障碍。
遗传算法同时使用多个搜索点的搜索信息。遗传算法对最优解的搜索过程,是从一个由很多个体所组成的初始种群开始的,而不是从单一的个体开始的。对这个种群所进行的选择、交叉、变异等运算,产生出新一代的群体,其中包括了很多群体信息。这些信息可以避免搜索出一些不必搜索的点,相当于搜索了更多的点,这是遗传算法所特有的一种隐含并行性。
遗传算法是一种基于概率的搜索技术。遗传算法属于自适应概率搜索技术,其选择、交叉、变异等运算都是以一种概率的方式来进行的,从而增加了其搜索过程的灵活性。虽然这种概率特性也会使群体中产生一些适应度不高的个体,但随着进化过程的进行,新的群体中总会更多地产生出优良的个体。与其他的一些算法相比,遗传算法的鲁棒性使得参数对其搜索效果的影响尽可能小。
遗传算法具有自组织、自适应和自学习等特性。当遗传算法利用进化过程获得信息自行组织搜索时,适应度大的个体具有较高的生存概率,并获得更适应环境的基因结构。同时遗传算法具有可扩展性,易于同别的算法相结合,生成综合双方优势的混合算法。
初始化。设置进化代数计数器 $g=0$,设置最大进化代数 G,随机生成 $N_p$ 个个体作为初始种群 $P(0)$。
个体评价。计算种群 $P(t)$ 中各个个体的适应度。
选择运算。将选择算子作用于群体,根据个体的适应度,按照一定的规则或方法选择一些优良个体遗传到下一代群体。
交叉运算。将交叉算子作用于群体,对选中的成对个体,以某一概率交叉它们之间的部分染色体,产生新的个体。
变异运算。将变异算子作用于群体,对选中的个体,以某一概率改变某一个或某一些基因值为其他的等位基因。
循环操作。群体 $P(t)$ 经过选择、交叉和变异运算之后得到下一代群体 $P(t+1)$。计算其适应度值,并根据适应度进行排序,准备进行下一次遗传操作。
终止条件判断:若 $g \leq G$,则 $g = g+1$,转到从步骤(2);若 $g > G$,则此进化过程中所得到的具有最大适应度的个体作为最优解输出,终止计算。
差分进化算法有以下特点:
结构简单,容易使用。差分进化算法主要通过差分变异算子来进行遗传操作,由于该算子只涉及向量的加减运算,因此很容易实现;该算法采用概率转换规则,不需要确定性的概率。
性能优越。差分进化算法具有较好的可靠性、高效性和鲁棒性,对于大空间、非线性和不可求导的连续问题,其求解效率比其他进化方法好。
自适应性。差分进化算法的差分变异算子可以是固定常数,也可以具有变异步长和搜索方向的自适应的能力,根据不同的目标函数进行自动调整,从而提高搜索质量。
并行性。差分进化算法具有内在的并行性,可协同搜索,具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力。在同样精度的要求下,差分进化算法具有更快的收敛速度。
通用性。差分进化算法可直接对结构对象进行操作,不依赖于问题信息,不存在对目标函数的限定。
差分进化算法采用实数编码、基于差分的简单变异操作和 “一对一” 的竞争生存策略,具体步骤如下:
确定差分进化算法的控制参数和所要采用的具体策略。差分进化算法的控制参数包括:种群数量、变异算子、交叉算子、最大进化代数、终止条件等。
随机产生初始种群,进化代数 $k = 1$。
对初始种群进行评价,即计算初始种群中每个个体的目标函数值。
判断是否达到终止条件或达到最大进化代数:若是,则进化终止,将此时的最佳个体作为解输出;否则,继续下一步操作。
进行编译操作和交叉操作,对边界条件进行处理,得到临时种群。
对临时种群进行评价,计算临时种群中每个个体的目标函数值
对临时种群中的个体和原种群中对应的个体,进行 “一对一” 的选择操作,得到新种群。
进化代数 $k = k+1$,转步骤(4)。
种群数量 $N_p$
一般情况下,种群的规模 %N_p% 越大,其中的个体就越多,种群的多样性也就越好,寻优的能力也就越强,但也因此增加了计算的难度
变异算子 $F$
变异算子 $F \in [0, 2]$ 是一个实常数因数,它决定偏差向量的缩放比例。变异算子 $F$ 过小,则可能造成算法 “早熟”。
交叉算子 $CR$
交叉算子 $CR \in [0, 1]$ 是一个常实数,它控制着一个试验向量参数来自随机选择的变异向量,而不是原来的向量的概率。交叉算子 $CR$ 越大,发生交叉的可能性就越大。
最大进化代数 $G$
最大进化代数 $G$ 是表示差分进化算法运行结束条件的一个参数,表示差分进化算法运行到指定的进化代数之后就停止运行,并将当前群体中的最佳个体作为所求问题的最优解输出。
终止条件
除了最大进化代数可作为差分进化算法的终止条件,还可以增加其他的判断准则。一般当目标函数小于阈值时程序终止,阈值常选 $10^{-6}$。
上述参数中,$F$、$CR$ 与 $N_p$ 一样,在搜索过程中时常数,一般 $F$ 和 $CR$ 影响搜索过程的收敛速度和鲁棒性,它们的优化值不仅依赖于目标函数的特性,还与 $N_p$ 有关。通常可通过对不同值做一些实验之后,利用实验和结果误差找到 $F$、$CR$ 与 $N_p$ 的合适值。
免疫算法与生物免疫系统概念的对应关系
生物免疫系统 | 免疫算法 |
---|---|
抗原 | 优化问题 |
抗体(B细胞) | 优化问题的可行解 |
亲和度 | 可行解的质量 |
细胞活化 | 免疫选择 |
细胞分化 | 个体克隆 |
亲和度成熟 | 变异 |
克隆抑制 | 克隆抑制 |
动态维持平衡 | 种群刷新 |
根据上述的对应关系,模拟生物免疫应答的过程形成了用于优化计算的免疫算法。算法主要包括以下几大模块:
抗体识别与初始抗体的产生。
根据待优化问题的特点涉及合适的抗体编码规则,并在此编码规则下利用问题的先验知识产生初始抗体种群。
抗体评价。
对抗体的质量进行评价,评价促销准则主要为抗体亲和度、个体浓度,评价得出的优质抗体将进行免疫操作,劣质抗体将会被更新。
免疫操作。
利用免疫选择、克隆、变异、克隆抑制、种群刷新等算子模拟生物免疫应答中的各种免疫操作,形成基于生物免疫系统克隆选择原理的进化规则和方法,实现对各种最优问题的寻优过程。
免疫算法是受免疫学启发,模拟生物免疫系统功能和原理来解决复杂问题的自适应智能系统它保留了生物免疫系统所具有的若干特点,包括:
全局搜索能力。模仿免疫应答过程所提出的免疫算法是一种具有全局搜索能力的优化算法,免疫算法在对优质抗体领域进行局部搜索的同时利用变异算子和刷群刷新算子不断产生新个体,探索可行解区间的多样性,保持算法在完整的可行解区间进行搜索,具有全局收敛性能。
多样性保持机制。免疫算法借鉴了生物免疫系统的多样性保持机制,对抗体进行浓度计算,并将浓度计算的结果作为评价抗体个体优劣的一个重要标准;它使浓度高的抗体被抑制,保证抗体种群具有很好的多样性,这也是爆保证算法全局收敛性能的一个重要方面。
鲁棒性强。基于生物免疫机理的免疫算法不针对特定问题,而且不强调算法参数设置和初始解的质量,利用其启发式的智能搜索机制,即使起步于劣势解种群,最终也可以搜索到问题的全局最优解,对问题和初始解的依赖性不强,具有很强的适应性和鲁棒性。
并行分布式搜索机制。免疫算法不需要集中控制,可以实现并行处理。而且,免疫算法的优化过程是一种多进程的并行优化,在探求问题最优解的同时可以得到问题的多个次优解,即除找到问题的最佳解决方案外,还会得到若干较好的备选方案,尤其适合于多模态的优化问题。
免疫算法的算子包括:亲和度评价算子、抗体浓度评价算子、激励度计算算子、免疫选择算子、克隆算子、变异算子、克隆抑制算子和种群刷新算子等。
下面是一种免疫算法流程,分为以下步骤:
首先进行抗原识别,即理解待优化问题,对问题进行可行性分析,提取先验知识猛走此时合适的亲和度函数,并制定各种约束条件。
然后产生初始抗体群,通过编码把问题的可行解表示为解空间中的抗体,在接的空间内随机产生一个初始种群。
对比种群中的每一个可行解进行亲和度评价。
判断是否满足算法终止条件:如果满足条件,则终止算法寻优过程,输出计算结果;否则,继续寻优运算。
计算抗体浓度和激励度。
进行免疫操作,包括免疫选择、克隆、变异和克隆抑制。
免疫选择:根据种群中抗体的亲和度和浓度计算结果选择优质抗体,使其活化;
克隆:对活化的抗体进行克隆复制,得到若干副本;
变异:对克隆得到的副本进行变异操作,使其发生亲和度突变;
克隆抑制:对变异结果进行再选择,抑制亲和度低的抗体,保留亲和度高的变异结果。
种群刷新:以随机生成的新抗体替代种群中激励度较低的抗体,形成新一代抗体,转步骤(3)。
免疫算法中的进化操作是采用了基于免疫原理的进化算子实现的,如免疫选择、克隆、变异等。而且算法中增加了抗体浓度和激励度的计算,并将抗体浓度作为评价个体质量的一个标准,有利于保持个体多样性,实现全局最优。
抗体种群大小 $N_p$
抗体种群保留了免疫细胞的多样性,从直观上看,种群越大,免疫算法的全局搜索能力越好,但是算法没带的计算量也相应增大。
免疫选择比例
免疫选择抗体的数量越多,将产生更多的克隆,其搜索能力越强,但是将增加每代的计算量。
抗体克隆扩增的倍数
克隆的背书决定了克隆扩增的细胞的数量,从而决定了算法的搜索能力,主要是局部搜索能力。克隆倍数数值越大,局部搜索能力越好,全局搜索能力也有一定提高,但是计算量也随之增大。
种群刷新比例
细胞的淘汰和更新是产生抗体多样性的重要准则,因而对免疫算法的全局搜索能力产生重要影响。
最大进化代数 $G$
最大进化代数 $G$ 是表示免疫算法运行结束条件的一个参数,表示免疫算法运行到指定的进化代数之后就停止运行,并将当前群体中的最佳个体作为所求问题的最优解输出。
蚁群算法是通过生物特征的模拟得到的一种优化算法,它本身具有很多优点:
蚁群算法是一种本质上的并行算法。每只蚂蚁搜索的过程彼此独立,仅通过信息激素进行通信。所以蚁群算法可以看作一个分布式的多智能体系统,它在问题空间的多点同时开始独立的解搜索,不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力。
蚁群算法是一种自组织的算法。所谓自组织,就是组织力或组织指令来自系统的内部,以区别于其他组织。如果系统搜到获得空间、时间或者功能结构的过程中,没有外界的特定干预,就可以说系统是自组织的。简单地说,自组织就是系统从无序到有序的变化过程。
蚁群算法具有较强的鲁棒性。相对于其他算法,蚁群算法对初始路线的要求不高,即蚁群算法的求解结果不依赖于初始路线的选择,而且在搜索过程中不需要人工的调整。此外,蚁群算法的参数较少,设置简单,因此该算法易于应用到组合优化问题的求解。
蚁群算法是一种正反馈算法。从真实蚂蚁觅食过程中不难看出,蚂蚁能够最终找到最优路径,直接依赖于其路径上的信息素的堆积,而信息素的堆积是一个正反馈的过程。正反馈是蚁群算法的重要特征,它使得算法进行过程得以进行。
参数初始化。令时间 $t = 0$和循环次数 $N_c = 0$,设置最大循环次数 $G$,将 $m$ 个蚂蚁置于 $n$ 个元素(城市)上,令有向图上每条边 $(i, j)$ 的初始化信息量 $\tau_{ij}(t) = c$,其中 $c$ 表示常数,且初始时刻 $\Delta\tau_{ij}(0) = 0$。
循环次数 $N_c = N_c+1$。
蚂蚁的禁忌表索引号 $k = 1$。
蚂蚁数目 $k = k+1$。
蚂蚁个体根据状态转移概率公式(P90-5.1)计算的概率选择元素 $j$ 并前进,$j \in J_k(i)$。
修改禁忌表指针,即选择好之后将蚂蚁移动到新的元素,并将该元素移动到该蚂蚁个体的禁忌表中。
若集合 $C$ 中元素未遍历完,即 $k < m$,则跳转到第(4)步;否则,执行第(8)步。
记录本次最佳路线。
根据公式(P90-5.2)和公式(P91-5.3)更新每条路径上的信息量。
若满足结束条件,即如果循环次数 $N_c \ge G$,则循环结束并输出程序优化结果;否则清空禁忌表并跳转到第(2)步。
粒子群算法本质是一种随机搜索算法,它是一种新兴的智能优化技术。该算法能以较大概率收敛于全局最优解。实践证明,它适合在动态、多目标优化环境中寻优,与传统优化算法相比,具有较快的计算速度和更好的全局搜索能力。
粒子群算法是基于群智能理论的优化算法,通过群体间粒子的合作与竞争产生的群体智能指导优化搜索。与其他算法相比,粒子群算法是一种高效的并行搜索算法,
粒子群算法与遗传算法都是随机初始化种群,使用适应度值来评价个体的优劣程度和进行一定的随机搜索。但粒子群算法根据自己的速度来决定搜索,没有遗传算法的交叉与变异。与进化算法相比,粒子群算法保留了基于种群的全局搜索策略,但是其采用的是速度-位移模型,操作简单,避免复杂的遗传操作。
由于每个粒子在算法结束时仍保持其个体极值,即粒子群算法除了可以找到问题的最优解外,还会得到若干较好的次优解,因此将粒子群算法用于调度和决策问题可以给出多种有意义的方案。
粒子群算法特有的记忆使其可以动态地跟踪当前搜索情况并调整其搜索策略。另外粒子群算法对种群的大小不敏感,即使种群数目下降时,性能下降也不是很大。
粒子群算法基于 “种群” 和 “进化” 的概念,通过个体间的协作与竞争,实现复杂空间最优解的搜索。
初始化粒子群,包括种群规模 $N$,每个粒子的位置 $x_i$ 和速度 $v_i$。
计算每个粒子的适应度值 $fit[i]$。
对每个粒子,用它的适应度值 $fit[i]$ 和个体极值 $p_{best}(i)$ 比较。如果 $fit[i] < p_{best}(i)$,则用 $fit[i]$ 替换掉 $p_{best}(i)$。
对每个粒子,用它的适应度值 $fit[i]$ 和全局极值 $g_{best}$ 比较。如果 $fit[i] < g_{best}$,则用 $fit[i]$ 替换掉 $g_{best}$。
迭代更新粒子的速度 $v_i$ 和速度 $x_i$。
进行边界条件处理。
判断算法终止条件是否满足:若是,则结束算法并输出优化结果;否则,返回步骤(2).
粒子群算法的控制参数主要包括:粒子种群规模 $N$,惯性权重 $w$,加速系数 $c_1$ 和 $c_2$,最大速度 $v_{max}$,停止准则,领域结构的设定,边界条件处理策略等。
粒子种群规模 $N$
粒子种群大小的选择视具体问题而定。粒子数目越大,算法搜索的空间范围越大,也就更容易发现全局最优解;当然,算法运行的时间也就越长。
加速常数 $c_1$ 和 $c_2$
加速常数 $c_1$ 和 $c_2$ 分别调节 $p_{best}$ 和 $g_{best}$ 方向飞行的最大步长,它们分别决定粒子个体经验和群体经验对粒子飞行轨迹的影响,反应粒子群之间的信息交流。如果 $c_1 = c_2 = 0$,则粒子将以当前的飞行速度飞到边界,此时粒子仅能搜索有限的区域,所以难以找到最优解。如果 $c_1 = 0$,则为 “社会模型”,例子缺乏认知能力,而只有群体经验,它的收敛速度较快,但容易陷入局部最优;如果 $c_2 = 0$,则为 “认知模型” 没有社会的共享信息,个体之间没有信息的交互,所以难以找到最优解的概率较小,一个规模为 $D$ 的群体等价于运行了 $N$ 个各行其是的粒子。因此一般设置 $c_1 = c_2$,通常可以取 $c_1 = c_2 = 1.5$。这样,个体经验和群体经验就有了同样重要的影响力,使得最后的最优解更精确。
粒子的最大速度 $v_{max}$
粒子的速度在空间中的每一维上都有一个最大速度限制值 $v_{dmax}$,用来对粒子的速度进行限制,使速度控制在 $[-v_{dmax}, +v_{dmax}]$ 内,这决定问题空间搜索的力度。如果 $v_{max}$ 设置太大,则粒子们也许会飞过优秀解区域;如果值太小,则粒子们可能无法对局部最优区域以外的区域进行充分的探测。它们可能陷入局部最优,而无法移动足够远的距离而跳出局部最优,达到空间中更佳的位置。
停止准则
最大迭代次数、计算精度或最优解的最大停滞步数 $\Delta t$(或可以接受的满意解)通常认为是停止准则,即算法的终止条件。根据具体的优化问题,停止准则的设定需同时兼顾算法的求解时间、优化质量和搜索效率等多方面的因素。
领域结构的设定
全局版本的粒子群算法将整个群体作为粒子的领域,具有收敛速度快的优点,但是有时算法会陷入局部最优。
局部版本的粒子群算法将位置相近的个体作为粒子的领域,收敛速度慢,不容易陷入局部最优值。
实际应用中,可先采用全局粒子群算法寻找最优解的方向,即得到大致的结果,然后采用局部粒子群算法在最优解点附近进行精细搜索。
边界条件处理
当某一维或若干维的位置或速度超过设定值时,采用边界条件处理策略可将粒子的位置限制在可行搜索空间内,这样能避免种群的膨胀和发散,也能避免粒子大范围地盲目搜索,从而提高搜索效率。
具体的方法有很多种,比如通过设置最大位置 $x_{max}$ 和最大速度限制 $v_{max}$,当超过最大位置或最大速度时,在取值范围内随机产生一个数值代替,或者将其设置为最大值,即边界吸收。
模拟退火算法是一种通用地优化算法,是局部搜索算法地扩展$^{(1)}$。它不同于局部搜四算法之处时以一定的概率选择邻域中目标值大地劣质解。从理论上说,它是一种全局最优算法。
局部搜索算法,有时候附近没有更好的个体并转移,因此只有局部搜索能力的话,很可能只出现局部最优。
模拟退火算法与金属退火过程地相似关系
物理退火 | 模拟退火 |
---|---|
粒子状态 | 解 |
能量最低态 | 最优解 |
溶解过程 | 设定初温 |
等温过程 | Metropolis 采样过程 |
冷却 | 控制参数地下降 |
能量 | 目标函数 |
在搜索区间随机游走(即随机选择点),再利用 Metropolis 抽样准则,使随机游走逐渐收敛于局部最优解。而温度是 Metropolis 算法中的一个重要控制参数,可以认为这个参数的大小控制了随机过程向局部或全局最优解移动地快慢。
模拟退火算法适用范围广,求得全局最优解的可靠性高,算法简单,便于实现;该算法的搜索策略有利于避免其搜索过程陷入局部最优解地缺陷,有利于提高求得全局最优解地可靠性。模拟退火算法具有十分强地鲁棒性,这是因为比起普通地优化搜索方法,它采用了许多独特的方法和技术。主要有以下方面:
以一定的概率接受恶化解。
模拟退火算法在搜索策略上不仅引入了适当的随机因素,而且还引入了物理系统退火过程地自然机理,使得模拟退火算法在迭代过程中不仅接受使目标函数变 “好” 的点,而且还能够以一定的概率接受使目标函数变 “差” 的点。
引入算法控制参数
引入类似于退货温度的算法控制参数,它将优化过程分为若干阶段,并决定各个阶段下随即状态的取舍标准,接收函数由 Metropolis 算法给出一个简单的数学模型。模拟退火算法有两个重要的步骤:一是在每个控制参数下,由前迭代点出发,产生邻近的随机状态,由控制参数确定的接受准则决定此新状态的取舍,并由此形成一定长度的随机 Markov 链;二是缓慢降低控制参数,提高接受准则,直至控制参数趋近于零,状态链稳定于优化问题的最优状态,从而提高模拟退火算法全局最优解的可靠性。
对目标函数要求少
传统搜索算法不仅需要利用目标函数值,而且往往还需要目标函数的导数值等其他一些辅助信息才能确定搜索方向,当这些信息不存在时,算法就失效了。而模拟退火算法不需要其他的辅助信息,而知识定义邻域结构,在其邻域结构内选取相邻解,再用目标函数进行评估。
模拟退火算法新解的产生和接受可分为如下三个步骤:
由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计划和接受,减少算法耗时,通常选择由当前解经过简单变换即可产生新解的方法。
注意:产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。
判断新解是否被接受,判断的依据时一个接受准则,最常用的接受准则时 Metropolis 准则;若 $\Delta E < 0$,则接受 $X’$ 作为新的当前解 $X$;否则,以概率 $exp(- \Delta E / T)$ 接受 $X’$ 作为新的当前解 $X$。
当新解被确定接受时,用新解代替当前解,这只需将当前解中对应产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代,可在此基础上开始下一轮试验。若当新解被判定为舍弃,则在原当前解的基础上继续下一轮试验。
模拟退火算法求得的解与初始解状态(算法迭代的起点)无关,具有渐近收敛性,已在理论上被证明是一种以概率 1 收敛于全局最优解的优化算法。模拟退火算法可以分解为解空间、目标函数和初始解三部分。算法流程如下:
初始化:设置初始温度 $T_0$(充分大)、初始解状态 $X_0$(是算法迭代的起点)、每个 $T$ 值的迭代次数 $L$;
对 $k = 1, …, L$ 进行第(3)至第(6)步操作;
产生新解 $X’$;
计算增量 $\Delta E = E(X’) - E(X)$,其中 $E(X)$ 为评价函数;
若 $\Delta E < 0$,则接受 $X’$ 作为新的当前解,否则以概率 $exp(- \Delta E / T)$接受 $X’$ 作为新的当前解;
如果满足终止条件,则输出当前解作为最优解,结束程序;
$T$ 逐渐缩小,且 $T \rightarrow 0$,然后转第(2)步。
模拟退火算法的性能质量高,它比较通用,而且容易实现。不过,为了得到最优解,该算法通常要求较高的初温以及足够多次的抽样,这使得算法的优化时间往往过长。从算法结构知,新的状态产生函数、初温、退温函数、Markov 链长度和算法停止准则,是直接影响算法优化结果的主要环节。
状态产生函数
设计状态产生函数应该考虑到尽可能地保证所产生的候选解遍布全部解空间。一般情况下状态产生函数由两部分组成,即产生首选姐的方式和产生候选解的概率分布。候选解的产生方式由问题的性质决定,通常在当前状态的邻域结构内以一定的概率产生。
初温
温度 $T$ 在算法中具有决定性的作用,它直接控制着退火的走向。由随即移动的接受准则可知:初温越大,获得高质量解的概率也越大,且 Metropolis 的接受率为 $1$。然而,初温过高会使计算时间增加。为此,可以均匀抽样一组状态,以各状态目标值的方差为初温。
退温函数
退温函数即温度更新函数,用于在外循环修改温度值。目前,最常用的温度更新函数为指数退温函数,即 $T(n+1) = K \times T(n)$,其中 $0 < K < 1$ 是一个非常接近于 $1$ 的常数。
Markov 链长度 $L$ 的选取
Markov 链长度是等温条件下进行迭代优化的次数。
算法停止准则
用于决定算法何时结束,可以简单设置温度终值 $T_f$,当 $T = T_f$ 时算法终止。模拟退火算法的收敛性理论要求 $T_f$ 趋向于零,这是不实际的。
常用的停止准则包括:设置终止温度的阈值、设置迭代次数阈值、或者当搜索到的最优值连续保持不变时停止搜索。
禁忌搜索算法是模拟人思维的一种智能搜索方法,即人们对已搜索的地方不会再立即去搜索,而失去对其它地方进行搜索;若没有找到,可再搜索已去过的地方,
禁忌搜索算法从一个初始可行解出发,选择一系列的特定搜索方向(或称为 “移动”)作为试探,选择使目标函数值减小最多的移动。为了避免陷入局部最优解,禁忌搜索算法采用了一种灵活的 “记忆” 技术,即对已经进行的优化过程进行记录,指导下一步的搜索方向,这就是禁忌表的建立。另外,为了尽可能不错过产生最优解的 “移动”,禁忌搜索算法还采用了 “特赦准则” 的策略。
禁忌搜索算法是在邻域搜索的基础上,通过设置禁忌表来禁忌一些已经进行过的操作,并利用藐视准则来奖励一些优良状态,其中邻域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。
与传统的优化算法相比,禁忌搜索算法的主要特点是:
禁忌搜索算法的新解不是在当前解的邻域中随机产生,它要么是优于 “best so far” 的解,要么是非禁忌的最优解,因此选取优良的概率远远大于其他劣质解的概率。
由于禁忌搜索算法具有灵活的记忆功能和藐视准则,并且在搜索过程中可以接受劣质解,所以具有较强的 “爬山” 能力,搜索时能够跳出局部最优解,转向解空间的其他区域,从而增大获得更好的全局最优解的概率。因此,禁忌搜索算法是一种局部搜索能力很强的全局迭代寻优算法。
禁忌搜索算法的基本思想是:给定一个当前解(初始解)和一种邻域,然后在当前解的邻域中确定若干候选解;若最佳候选解对应的目标优于 “best so far” 状态,则忽视其紧急特性,用它来替代当前解和 “best so far” 状态,并将相应的对象加入禁忌表,同时修改禁忌表中的各对象的任期;若不存在上述候选解,则在候选解中选择非禁忌的最佳状态为新的当前解,而无视它与当前解的优劣,同时将相应的对象加入禁忌表,并修改禁忌表中各对象的任期。如此重复上述迭代搜索过程,直至满足停止准则。算法步骤可描述如下:
给定禁忌搜索算法参数,随机产生初始解 $x$,置禁忌表为空。
判定算法终止条件是否满足:若满足,则结束算法并输出优化结果;否则,继续以下步骤。
利用当前解的邻域函数产生其所有(或若干)邻域解,并从中确定若干候选解。
对候选解判定藐视准则是否满足:若满足,则用藐视准则的最佳状态 $y$ 替代 $x$ 成为新的当前解,即 $x = y$,并用与 $y$ 对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用 $y$ 替换 “best so far” 状态,然后转步骤(6);否则,继续以下步骤。
判断候选解对应的各对象的禁忌属性,选择候选解集中非禁忌对象相对应的最佳状态为新的当前解,同时用与之对应的紧急对象替换最早进入禁忌表的禁忌对象。
判断算法终止条件是否满足:若满足,则结束算法并输出优化结果;否则,转步骤(3)。
一般设计一种禁忌搜索算法,需要确定以下环节:初始解、适配值函数、邻域结构、禁忌对象、候选解选择、禁忌表、禁忌长度、藐视准则、搜索策略、终止准则。
初始解
禁忌搜索算法可以随机给出初始解,也可以事先使用其他启发式算法等给出的一个较好的初始解。由于禁忌搜索算法主要是基于邻域的,初始解的好坏对搜索的性能影响很大。
适配值函数
禁忌搜索算法的适配值函数用于对搜索进行评价,进而结合禁忌准则和特赦准则来选取新的当前状态。
邻域结构
邻域结构,是指从一个解(当前解)通过 “移动” 产生另一个解(新解)的途径,它是保证搜索产生优良解和影响算法搜索速度的重要因素之一。领域结构的设计通常与问题有关。
禁忌对象
禁忌对象是被置入禁忌表中的那些变换的元素。禁忌的目的则是为了尽量避免迂回搜索而多搜索一些解空间中的其他地方。归纳而言,禁忌对象通常可选取状态本身或状态分量。
候选解选择
候选解变量通常在当前状态的邻域中择优选取,若选取过多将造成较大的计算量,而选取较少则会造成容易 “早熟” 收敛。
禁忌表
不允许恢复(即被禁止)的性质称作禁忌(Tabu)。禁忌表的主要目的是阻止搜索过程中出现循环和避免陷入局部最优,它通常记录前若干次的移动,禁止这些移动在近期内返回,在迭代固定次数后,禁忌表释放这些移动,重新参加运算,因此它是一个循环表,每迭代一次,就将最近一次移动放在禁忌表的末端,而它的最早的一个移动就从禁忌表中释放出来。
禁忌长度
所谓禁忌长度,就是指禁忌对象在不考虑特赦准则的情况下不允许被选取的最大次数。通俗的讲,禁忌长度可视为禁忌对象在禁忌表中的任期。
藐视准则
在禁忌搜索算法中,可能会出现候选解全部禁忌,或者存在一个优于 “best so far” 状态的禁忌候选解,此时特赦准则则将某些状态全部解禁,以实现更高效的优化性能。特赦准则的常用方式有:
基于适配值的原则:某个禁忌候选解的适配值优于 “best so far” 状态,则解禁次候选解为当前状态和新的 “best so far” 状态。
基于搜索方向的准则:若禁忌对象上次被禁忌时使得适配值有所改善,并且目前改禁忌对象对应的候选解的适配值优于当前解,则对该禁忌对象解禁。
搜索策略
搜索策略分为集中性搜索策略,以及多样性搜索策略。集中性搜索策略用于加强对优良解的邻域的进一步搜索。多样性搜索策略则用于拓宽搜索区域,尤其是未知区域。
终止准则
禁忌搜索算法需要一个终止准则来结束算法的搜索过程,而严格理论意义上的收敛条件,即在禁忌长度充分大的条件下实现状态空间的遍历,这显然是不可能实现的。因此,在实际设计算法时通常采用近似的收敛准则。
神经网络算法与传统的参数模型方法最大的不同,在于它是数据驱动的自适应技术,不需要对问题模型做任何先验假设,在解决问题的内部规律未知或难以描述的情况下,神经网络可以通过对样本数据的学习训练,获取数据之间隐藏的函数关系。因此,神经网络方法特别适用于解决一些利用假设和现存理论难以解释,但却具备足够多的数据和观察变量的问题。
神经网络技术具备泛化能力,泛化能力是指经过训练后学习模型对未来训练集出现的样本做出正确反应的能力。因此可以同通过样本内的历史数据来预测样本外的未来数据。神经网络可以通过对输入的数据样本的学习训练,获得隐藏在数据内部的规律,并利用学习到的规律来预测未来的数据。
神经网络是一个具有普遍适用性的函数逼近器。它可以以任何精度逼近任何的连续函数,神经网络的内部函数形式比传统的统计方式更加灵活和有效。
神经网络是非线性的方法。神经网络中的每个神经元都可以接受大量其他神经元的输入,而且每个神经元的输入和输出之间都是非线性的关系。神经元之间的这种互相制约和互相影响的关系,可以实现整个网络从输入状态到输出状态的非线性映射。因此,神经网络可以处理一些环境信息十分复杂、知识背景不清楚和推理规则不明确的问题。
BP 神经网络算法的主要思想是:
对于 $n$ 个输入学习样本 $“x^1, x^2, …, x^n”$,已知与其对应的 $m$ 个输出样本为 $(t^1, t^2, …, t^m)$ 之间的误差来修改其权值,使 $z^l$ $(l=1, 2, …, m)$ 与期望的 $t^l$ 尽可能接近,即:使网络输出层的误差平方和达到最小。
BP神经网络的学习过程主要由四部分组成:输入模式顺传播、输出误差逆传播、循环记忆训练、学习结果判别。这个算法的学习过程,由正向传播和反向传播组成,在正向传播过程中,输入信息从输入层经隐含层单元逐层处理,并传向输出层,每一层神经元的状态只影响下一层神经元的状态。如果在输出层不能得到所期望的输出,则转入反向传播,将误差信号沿原来的连接通路返回,通过修改各层的神经元的权值,使得误差信号减小,然后再转入正向传播过程。反复迭代,直到误差小于给定的值为止。