传送门:IOA -「杂七杂八」

S.1 总览

1.1 进化类算法

遗传算法

遗传算法(Genetic Algorithm,GA)是模拟生物在自然界中的遗传和进化过程,从而形成的自适应全局优化算法。它起源于 20 世纪 60 年代人们对自然和人工自适应系统的研究,最早由美国 J.H.Holland 提出,并于 80 年代由 D.J.Goldberg 在一系列研究工作的基础上归纳总结而成。

遗传算法是通过模拟自然界生物进化机制而发展起来的随机全局搜索和优化方法。它借鉴了达尔文的进化论和孟德尔的遗传的遗传学说,使用 “适者生存” 的原则,本质上是一种并行、高效、全局搜索的方法;它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制过程以求得最优解。

差分进化算法

差分进化(Differential Evolution,DE)算法最初用于解决切比雪夫多项式问题,后来发现该算法也是解决复杂优化问题的有效技术。

差分进化算法是一种新兴的进化计算技术,它基于群体智能理论,是通过群体内个体间的合作与竞争产生的智能优化搜索算法。但相比于进化计算,差分进化算法保留了基于种群的全局搜索策略,采用实数编码、基于差分的简单变异操作和 “一对一” 的竞争生存策略,降低了进化计算的复杂性。同时,差分进化算法具有较强的全局收敛能力和鲁棒性,且不需要借助问题的特征信息适用于求解一些利用常规的数学规划方法很难求解甚至无法求解的复杂优化问题。

免疫算法

最早的免疫系统模型由 Jerne 于 1973 年提出,他基于 Burnet 的克隆选择学说,开创了独特型网络理论,给出了免疫系统的数学框架。Farmal 等人于 1986 年基于免疫网络学说理论构造出免疫系统的动态模型,展示了免疫系统与其他人工智能方法相结合的可能性,开创了免疫系统研究的先河。

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

1.2 群智能算法

群智能指的是 “无智能的主体通过合作表现出智能行为的特征”,是一种基于生物群体行为规律的计算技术。它受社会昆虫(如鸟群、鱼群和兽群)的启发,用来解决分布式问题。它在没有集中控制并且不提供全局模型的前提下,为寻找复杂的分布式问题的解决方案提供了一种新的思路。

群智能方法易于实现,其算法中仅涉及各种基本的数学操作,其数据处理过程对 CPU 和内存的要求也不高。而且,这种方法只需要目标函数的输入值,而不需要其梯度信息。

蚁群算法

蚂蚁在寻找食物时,能在其走过的路径上释放一种特殊的分泌物——信息素。随着时间的退役,该物质会逐渐挥发,后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时,其留下的信息素也越来越多,后来的蚂蚁选择该路径的概率也就越高,从而更增加了该路径上的信息素强度。二强度大的信息素会吸引更多的蚂蚁,从而形成一种正反馈机制。通过这种正反馈机制,蚂蚁最终可以发现最短路径。

蚁群算法(Ant Colony Optimization,ACO)就是通过模拟自然界中蚂蚁集团寻径行为而提出的一种基于种群的启发式随即搜索算法,是群智能理论研究领域的一种重要算法。

蚁群算法具有分布式计算、无中心控制和分布式个体之间间接通讯的等特征,易于与其他优化算法相结合,已经广泛用于优化问题的求解。

粒子群算法

粒子群算法(Particle Swarm Optimization,PSO)是 Kennedy 和 Eberhart 受人工生命研究成果的启发,通过模拟鸟群觅食过程中的前夕和群聚行为而提出的一种基于种群智能的全局随机搜索方法。

与其他进化方法一样,粒子群算法也是基于 “种群” 和 “进化” 的概念,通过个体间的协作与竞争,实现复杂空间最优解的搜索。但是,它对个体不进行交叉、变异、选择等进化算子的操作,而是将群体中的个体看成是在 D 维搜索空间中没有质量和体积的粒子,每个粒子以一定的速度在解空间运动,并向自身历史最佳位置 pbest 和群体历史最佳位置 gbest 聚集,实现对候选解的进化。

1.3 模拟退火算法

模拟退火(Suimulated Annealing,SA)算法是一种基于 Monte Carlo 迭代求解策略的三场寻优算法,它基于物理中固体物质的退火过程与一般组合优化问题之间的相似性,其目的在于为具有 NP(Non-deterministic Polynomial)复杂性的问题提供有效的近似求解算法;该算法克服了传统算法优化过程容易陷入局部最优极值的缺陷和对初值的依赖性。

1.4 禁忌搜索方法

禁忌搜索(Tabu Search or Taboo Search,TS)算法以其灵活的存储结构和相应的禁忌准则来避免迂回搜索,在智能算法中独树一帜。TS 是对局部领域搜索的一种扩展,它在通过禁忌准则来避免重复搜索的同时,通过藐视准则来赦免一切被禁忌的优良状态,进而保证多样性的有效搜索,以最终实现全局优化。

1.5 神经网络算法

人工神经网络(Artificial Neural Network,ANN)简称为神经网络或称为连接模型。1943 年形成神经元的数据模型的提出,1982 年 J.J.Hopfield 提出了具有联想记忆的 Hopfield 神经网络,引入能量函数的原理,给出了网络的稳定性判据。

神经网络是一种模仿生物神经系统的新型信息处理模型,具有独特的结构,其显著的特点如下:具有非线性映射能力;不需要精确的数学模型;擅长从输入输出数据中学习有用的知识;容易实现并行计算;由大量的简单计算神经元组成,易于用软硬件实现;等等。

S.2 遗传算法

基本概念

遗传学术语 遗传算法术语
群体 可行解集
个体 可行解
染色体 可行解的编码
基因 可行解编码的分量
基因形式 遗传编码
适应度 函数评价值

遗传算法的特点

遗传算法是模拟生物在自然界中的遗传和进化的过程而形成的一种并行、高效、全局搜索的方法,它有以下特点:

  1. 遗传算法以决策变量的编码作为运算对象。使得在优化计算过程中可以借鉴生物学中的染色体和基因等概念,模拟自然界中生物的遗传和进化等的机理,方便地应用遗传操作算子。特别是对一些只有代码概念而无数值概念或很难有数值概念的优化问题,编码处理方式更显示出了其独特的优越性。

  2. 遗传算法直接以目标函数值作为搜索信息。它仅使用由目标函数值变换来的适应度函数值,就可确定进一步的搜索方向和搜索范围,而不需要目标函数的导数值等其他一些辅助信息。避开了函数求导这个障碍。

  3. 遗传算法同时使用多个搜索点的搜索信息。遗传算法对最优解的搜索过程,是从一个由很多个体所组成的初始种群开始的,而不是从单一的个体开始的。对这个种群所进行的选择、交叉、变异等运算,产生出新一代的群体,其中包括了很多群体信息。这些信息可以避免搜索出一些不必搜索的点,相当于搜索了更多的点,这是遗传算法所特有的一种隐含并行性。

  4. 遗传算法是一种基于概率的搜索技术。遗传算法属于自适应概率搜索技术,其选择、交叉、变异等运算都是以一种概率的方式来进行的,从而增加了其搜索过程的灵活性。虽然这种概率特性也会使群体中产生一些适应度不高的个体,但随着进化过程的进行,新的群体中总会更多地产生出优良的个体。与其他的一些算法相比,遗传算法的鲁棒性使得参数对其搜索效果的影响尽可能小。

  5. 遗传算法具有自组织、自适应和自学习等特性。当遗传算法利用进化过程获得信息自行组织搜索时,适应度大的个体具有较高的生存概率,并获得更适应环境的基因结构。同时遗传算法具有可扩展性,易于同别的算法相结合,生成综合双方优势的混合算法。

流程

  1. 初始化。设置进化代数计数器 $g=0$,设置最大进化代数 G,随机生成 $N_p$ 个个体作为初始种群 $P(0)$。

  2. 个体评价。计算种群 $P(t)$ 中各个个体的适应度。

  3. 选择运算。将选择算子作用于群体,根据个体的适应度,按照一定的规则或方法选择一些优良个体遗传到下一代群体。

  4. 交叉运算。将交叉算子作用于群体,对选中的成对个体,以某一概率交叉它们之间的部分染色体,产生新的个体。

  5. 变异运算。将变异算子作用于群体,对选中的个体,以某一概率改变某一个或某一些基因值为其他的等位基因。

  6. 循环操作。群体 $P(t)$ 经过选择、交叉和变异运算之后得到下一代群体 $P(t+1)$。计算其适应度值,并根据适应度进行排序,准备进行下一次遗传操作。

  7. 终止条件判断:若 $g \leq G$,则 $g = g+1$,转到从步骤(2);若 $g > G$,则此进化过程中所得到的具有最大适应度的个体作为最优解输出,终止计算。

遗传算法流程图

S.3 差分进化算法

算法特点

差分进化算法有以下特点:

  1. 结构简单,容易使用。差分进化算法主要通过差分变异算子来进行遗传操作,由于该算子只涉及向量的加减运算,因此很容易实现;该算法采用概率转换规则,不需要确定性的概率。

  2. 性能优越。差分进化算法具有较好的可靠性、高效性和鲁棒性,对于大空间、非线性和不可求导的连续问题,其求解效率比其他进化方法好。

  3. 自适应性。差分进化算法的差分变异算子可以是固定常数,也可以具有变异步长和搜索方向的自适应的能力,根据不同的目标函数进行自动调整,从而提高搜索质量。

  4. 并行性。差分进化算法具有内在的并行性,可协同搜索,具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力。在同样精度的要求下,差分进化算法具有更快的收敛速度。

  5. 通用性。差分进化算法可直接对结构对象进行操作,不依赖于问题信息,不存在对目标函数的限定。

算法流程

差分进化算法采用实数编码、基于差分的简单变异操作和 “一对一” 的竞争生存策略,具体步骤如下:

  1. 确定差分进化算法的控制参数和所要采用的具体策略。差分进化算法的控制参数包括:种群数量、变异算子、交叉算子、最大进化代数、终止条件等。

  2. 随机产生初始种群,进化代数 $k = 1$。

  3. 对初始种群进行评价,即计算初始种群中每个个体的目标函数值。

  4. 判断是否达到终止条件或达到最大进化代数:若是,则进化终止,将此时的最佳个体作为解输出;否则,继续下一步操作。

  5. 进行编译操作和交叉操作,对边界条件进行处理,得到临时种群。

  6. 对临时种群进行评价,计算临时种群中每个个体的目标函数值

  7. 对临时种群中的个体和原种群中对应的个体,进行 “一对一” 的选择操作,得到新种群。

  8. 进化代数 $k = k+1$,转步骤(4)。

差分进化算法

关键参数说明

S.4 免疫算法

基本概念

免疫算法与生物免疫系统概念的对应关系

生物免疫系统 免疫算法
抗原 优化问题
抗体(B细胞) 优化问题的可行解
亲和度 可行解的质量
细胞活化 免疫选择
细胞分化 个体克隆
亲和度成熟 变异
克隆抑制 克隆抑制
动态维持平衡 种群刷新

根据上述的对应关系,模拟生物免疫应答的过程形成了用于优化计算的免疫算法。算法主要包括以下几大模块:

算法特点

免疫算法是受免疫学启发,模拟生物免疫系统功能和原理来解决复杂问题的自适应智能系统它保留了生物免疫系统所具有的若干特点,包括:

  1. 全局搜索能力。模仿免疫应答过程所提出的免疫算法是一种具有全局搜索能力的优化算法,免疫算法在对优质抗体领域进行局部搜索的同时利用变异算子和刷群刷新算子不断产生新个体,探索可行解区间的多样性,保持算法在完整的可行解区间进行搜索,具有全局收敛性能。

  2. 多样性保持机制。免疫算法借鉴了生物免疫系统的多样性保持机制,对抗体进行浓度计算,并将浓度计算的结果作为评价抗体个体优劣的一个重要标准;它使浓度高的抗体被抑制,保证抗体种群具有很好的多样性,这也是爆保证算法全局收敛性能的一个重要方面。

  3. 鲁棒性强。基于生物免疫机理的免疫算法不针对特定问题,而且不强调算法参数设置和初始解的质量,利用其启发式的智能搜索机制,即使起步于劣势解种群,最终也可以搜索到问题的全局最优解,对问题和初始解的依赖性不强,具有很强的适应性和鲁棒性。

  4. 并行分布式搜索机制。免疫算法不需要集中控制,可以实现并行处理。而且,免疫算法的优化过程是一种多进程的并行优化,在探求问题最优解的同时可以得到问题的多个次优解,即除找到问题的最佳解决方案外,还会得到若干较好的备选方案,尤其适合于多模态的优化问题。

免疫算法算子

免疫算法的算子包括:亲和度评价算子、抗体浓度评价算子、激励度计算算子、免疫选择算子、克隆算子、变异算子、克隆抑制算子和种群刷新算子等。

免疫算法流程

下面是一种免疫算法流程,分为以下步骤:

  1. 首先进行抗原识别,即理解待优化问题,对问题进行可行性分析,提取先验知识猛走此时合适的亲和度函数,并制定各种约束条件。

  2. 然后产生初始抗体群,通过编码把问题的可行解表示为解空间中的抗体,在接的空间内随机产生一个初始种群。

  3. 对比种群中的每一个可行解进行亲和度评价。

  4. 判断是否满足算法终止条件:如果满足条件,则终止算法寻优过程,输出计算结果;否则,继续寻优运算。

  5. 计算抗体浓度和激励度。

  6. 进行免疫操作,包括免疫选择、克隆、变异和克隆抑制。

  7. 种群刷新:以随机生成的新抗体替代种群中激励度较低的抗体,形成新一代抗体,转步骤(3)。

免疫算法中的进化操作是采用了基于免疫原理的进化算子实现的,如免疫选择、克隆、变异等。而且算法中增加了抗体浓度和激励度的计算,并将抗体浓度作为评价个体质量的一个标准,有利于保持个体多样性,实现全局最优。

免疫算法流程图

关键参数说明

S.5 蚁群算法

算法特点

蚁群算法是通过生物特征的模拟得到的一种优化算法,它本身具有很多优点:

  1. 蚁群算法是一种本质上的并行算法。每只蚂蚁搜索的过程彼此独立,仅通过信息激素进行通信。所以蚁群算法可以看作一个分布式的多智能体系统,它在问题空间的多点同时开始独立的解搜索,不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力。

  2. 蚁群算法是一种自组织的算法。所谓自组织,就是组织力或组织指令来自系统的内部,以区别于其他组织。如果系统搜到获得空间、时间或者功能结构的过程中,没有外界的特定干预,就可以说系统是自组织的。简单地说,自组织就是系统从无序到有序的变化过程。

  3. 蚁群算法具有较强的鲁棒性。相对于其他算法,蚁群算法对初始路线的要求不高,即蚁群算法的求解结果不依赖于初始路线的选择,而且在搜索过程中不需要人工的调整。此外,蚁群算法的参数较少,设置简单,因此该算法易于应用到组合优化问题的求解。

  4. 蚁群算法是一种正反馈算法。从真实蚂蚁觅食过程中不难看出,蚂蚁能够最终找到最优路径,直接依赖于其路径上的信息素的堆积,而信息素的堆积是一个正反馈的过程。正反馈是蚁群算法的重要特征,它使得算法进行过程得以进行。

算法流程以及步骤

  1. 参数初始化。令时间 $t = 0$和循环次数 $N_c = 0$,设置最大循环次数 $G$,将 $m$ 个蚂蚁置于 $n$ 个元素(城市)上,令有向图上每条边 $(i, j)$ 的初始化信息量 $\tau_{ij}(t) = c$,其中 $c$ 表示常数,且初始时刻 $\Delta\tau_{ij}(0) = 0$。

  2. 循环次数 $N_c = N_c+1$。

  3. 蚂蚁的禁忌表索引号 $k = 1$。

  4. 蚂蚁数目 $k = k+1$。

  5. 蚂蚁个体根据状态转移概率公式(P90-5.1)计算的概率选择元素 $j$ 并前进,$j \in J_k(i)$。

  6. 修改禁忌表指针,即选择好之后将蚂蚁移动到新的元素,并将该元素移动到该蚂蚁个体的禁忌表中。

  7. 若集合 $C$ 中元素未遍历完,即 $k < m$,则跳转到第(4)步;否则,执行第(8)步。

  8. 记录本次最佳路线。

  9. 根据公式(P90-5.2)和公式(P91-5.3)更新每条路径上的信息量。

  10. 若满足结束条件,即如果循环次数 $N_c \ge G$,则循环结束并输出程序优化结果;否则清空禁忌表并跳转到第(2)步。

蚁群算法流程

S.6 粒子群算法

算法特点

粒子群算法本质是一种随机搜索算法,它是一种新兴的智能优化技术。该算法能以较大概率收敛于全局最优解。实践证明,它适合在动态、多目标优化环境中寻优,与传统优化算法相比,具有较快的计算速度和更好的全局搜索能力。

  1. 粒子群算法是基于群智能理论的优化算法,通过群体间粒子的合作与竞争产生的群体智能指导优化搜索。与其他算法相比,粒子群算法是一种高效的并行搜索算法,

  2. 粒子群算法与遗传算法都是随机初始化种群,使用适应度值来评价个体的优劣程度和进行一定的随机搜索。但粒子群算法根据自己的速度来决定搜索,没有遗传算法的交叉与变异。与进化算法相比,粒子群算法保留了基于种群的全局搜索策略,但是其采用的是速度-位移模型,操作简单,避免复杂的遗传操作。

  3. 由于每个粒子在算法结束时仍保持其个体极值,即粒子群算法除了可以找到问题的最优解外,还会得到若干较好的次优解,因此将粒子群算法用于调度和决策问题可以给出多种有意义的方案。

  4. 粒子群算法特有的记忆使其可以动态地跟踪当前搜索情况并调整其搜索策略。另外粒子群算法对种群的大小不敏感,即使种群数目下降时,性能下降也不是很大。

算法流程

粒子群算法基于 “种群” 和 “进化” 的概念,通过个体间的协作与竞争,实现复杂空间最优解的搜索。

  1. 初始化粒子群,包括种群规模 $N$,每个粒子的位置 $x_i$ 和速度 $v_i$。

  2. 计算每个粒子的适应度值 $fit[i]$。

  3. 对每个粒子,用它的适应度值 $fit[i]$ 和个体极值 $p_{best}(i)$ 比较。如果 $fit[i] < p_{best}(i)$,则用 $fit[i]$ 替换掉 $p_{best}(i)$。

  4. 对每个粒子,用它的适应度值 $fit[i]$ 和全局极值 $g_{best}$ 比较。如果 $fit[i] < g_{best}$,则用 $fit[i]$ 替换掉 $g_{best}$。

  5. 迭代更新粒子的速度 $v_i$ 和速度 $x_i$。

  6. 进行边界条件处理。

  7. 判断算法终止条件是否满足:若是,则结束算法并输出优化结果;否则,返回步骤(2).

粒子群算法流程图

关键参数说明

粒子群算法的控制参数主要包括:粒子种群规模 $N$,惯性权重 $w$,加速系数 $c_1$ 和 $c_2$,最大速度 $v_{max}$,停止准则,领域结构的设定,边界条件处理策略等。

S.7 模拟退火算法

模拟退火算法是一种通用地优化算法,是局部搜索算法地扩展$^{(1)}$。它不同于局部搜四算法之处时以一定的概率选择邻域中目标值大地劣质解。从理论上说,它是一种全局最优算法。

局部搜索算法,有时候附近没有更好的个体并转移,因此只有局部搜索能力的话,很可能只出现局部最优。

算法原理

模拟退火算法与金属退火过程地相似关系

物理退火 模拟退火
粒子状态
能量最低态 最优解
溶解过程 设定初温
等温过程 Metropolis 采样过程
冷却 控制参数地下降
能量 目标函数

算法思想

在搜索区间随机游走(即随机选择点),再利用 Metropolis 抽样准则,使随机游走逐渐收敛于局部最优解。而温度是 Metropolis 算法中的一个重要控制参数,可以认为这个参数的大小控制了随机过程向局部或全局最优解移动地快慢。

算法特点

模拟退火算法适用范围广,求得全局最优解的可靠性高,算法简单,便于实现;该算法的搜索策略有利于避免其搜索过程陷入局部最优解地缺陷,有利于提高求得全局最优解地可靠性。模拟退火算法具有十分强地鲁棒性,这是因为比起普通地优化搜索方法,它采用了许多独特的方法和技术。主要有以下方面:

  1. 以一定的概率接受恶化解。

    模拟退火算法在搜索策略上不仅引入了适当的随机因素,而且还引入了物理系统退火过程地自然机理,使得模拟退火算法在迭代过程中不仅接受使目标函数变 “好” 的点,而且还能够以一定的概率接受使目标函数变 “差” 的点。

  2. 引入算法控制参数

    引入类似于退货温度的算法控制参数,它将优化过程分为若干阶段,并决定各个阶段下随即状态的取舍标准,接收函数由 Metropolis 算法给出一个简单的数学模型。模拟退火算法有两个重要的步骤:一是在每个控制参数下,由前迭代点出发,产生邻近的随机状态,由控制参数确定的接受准则决定此新状态的取舍,并由此形成一定长度的随机 Markov 链;二是缓慢降低控制参数,提高接受准则,直至控制参数趋近于零,状态链稳定于优化问题的最优状态,从而提高模拟退火算法全局最优解的可靠性。

  3. 对目标函数要求少

    传统搜索算法不仅需要利用目标函数值,而且往往还需要目标函数的导数值等其他一些辅助信息才能确定搜索方向,当这些信息不存在时,算法就失效了。而模拟退火算法不需要其他的辅助信息,而知识定义邻域结构,在其邻域结构内选取相邻解,再用目标函数进行评估。

算法流程

模拟退火算法新解的产生和接受可分为如下三个步骤:

  1. 由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计划和接受,减少算法耗时,通常选择由当前解经过简单变换即可产生新解的方法。

    注意:产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。

  2. 判断新解是否被接受,判断的依据时一个接受准则,最常用的接受准则时 Metropolis 准则;若 $\Delta E < 0$,则接受 $X’$ 作为新的当前解 $X$;否则,以概率 $exp(- \Delta E / T)$ 接受 $X’$ 作为新的当前解 $X$。

  3. 当新解被确定接受时,用新解代替当前解,这只需将当前解中对应产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代,可在此基础上开始下一轮试验。若当新解被判定为舍弃,则在原当前解的基础上继续下一轮试验。

模拟退火算法求得的解与初始解状态(算法迭代的起点)无关,具有渐近收敛性,已在理论上被证明是一种以概率 1 收敛于全局最优解的优化算法。模拟退火算法可以分解为解空间、目标函数和初始解三部分。算法流程如下:

  1. 初始化:设置初始温度 $T_0$(充分大)、初始解状态 $X_0$(是算法迭代的起点)、每个 $T$ 值的迭代次数 $L$;

  2. 对 $k = 1, …, L$ 进行第(3)至第(6)步操作;

  3. 产生新解 $X’$;

  4. 计算增量 $\Delta E = E(X’) - E(X)$,其中 $E(X)$ 为评价函数;

  5. 若 $\Delta E < 0$,则接受 $X’$ 作为新的当前解,否则以概率 $exp(- \Delta E / T)$接受 $X’$ 作为新的当前解;

  6. 如果满足终止条件,则输出当前解作为最优解,结束程序;

  7. $T$ 逐渐缩小,且 $T \rightarrow 0$,然后转第(2)步。

模拟退火算法流程

关键参数说明

模拟退火算法的性能质量高,它比较通用,而且容易实现。不过,为了得到最优解,该算法通常要求较高的初温以及足够多次的抽样,这使得算法的优化时间往往过长。从算法结构知,新的状态产生函数、初温、退温函数、Markov 链长度和算法停止准则,是直接影响算法优化结果的主要环节。

S.8 禁忌搜索算法

禁忌搜索算法是模拟人思维的一种智能搜索方法,即人们对已搜索的地方不会再立即去搜索,而失去对其它地方进行搜索;若没有找到,可再搜索已去过的地方,

禁忌搜索算法从一个初始可行解出发,选择一系列的特定搜索方向(或称为 “移动”)作为试探,选择使目标函数值减小最多的移动。为了避免陷入局部最优解,禁忌搜索算法采用了一种灵活的 “记忆” 技术,即对已经进行的优化过程进行记录,指导下一步的搜索方向,这就是禁忌表的建立。另外,为了尽可能不错过产生最优解的 “移动”,禁忌搜索算法还采用了 “特赦准则” 的策略。

算法特点

禁忌搜索算法是在邻域搜索的基础上,通过设置禁忌表来禁忌一些已经进行过的操作,并利用藐视准则来奖励一些优良状态,其中邻域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。

与传统的优化算法相比,禁忌搜索算法的主要特点是:

  1. 禁忌搜索算法的新解不是在当前解的邻域中随机产生,它要么是优于 “best so far” 的解,要么是非禁忌的最优解,因此选取优良的概率远远大于其他劣质解的概率。

  2. 由于禁忌搜索算法具有灵活的记忆功能和藐视准则,并且在搜索过程中可以接受劣质解,所以具有较强的 “爬山” 能力,搜索时能够跳出局部最优解,转向解空间的其他区域,从而增大获得更好的全局最优解的概率。因此,禁忌搜索算法是一种局部搜索能力很强的全局迭代寻优算法。

算法流程

禁忌搜索算法的基本思想是:给定一个当前解(初始解)和一种邻域,然后在当前解的邻域中确定若干候选解;若最佳候选解对应的目标优于 “best so far” 状态,则忽视其紧急特性,用它来替代当前解和 “best so far” 状态,并将相应的对象加入禁忌表,同时修改禁忌表中的各对象的任期;若不存在上述候选解,则在候选解中选择非禁忌的最佳状态为新的当前解,而无视它与当前解的优劣,同时将相应的对象加入禁忌表,并修改禁忌表中各对象的任期。如此重复上述迭代搜索过程,直至满足停止准则。算法步骤可描述如下:

  1. 给定禁忌搜索算法参数,随机产生初始解 $x$,置禁忌表为空。

  2. 判定算法终止条件是否满足:若满足,则结束算法并输出优化结果;否则,继续以下步骤。

  3. 利用当前解的邻域函数产生其所有(或若干)邻域解,并从中确定若干候选解。

  4. 对候选解判定藐视准则是否满足:若满足,则用藐视准则的最佳状态 $y$ 替代 $x$ 成为新的当前解,即 $x = y$,并用与 $y$ 对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用 $y$ 替换 “best so far” 状态,然后转步骤(6);否则,继续以下步骤。

  5. 判断候选解对应的各对象的禁忌属性,选择候选解集中非禁忌对象相对应的最佳状态为新的当前解,同时用与之对应的紧急对象替换最早进入禁忌表的禁忌对象。

  6. 判断算法终止条件是否满足:若满足,则结束算法并输出优化结果;否则,转步骤(3)。

禁忌搜索算法流程

关键参数说明

一般设计一种禁忌搜索算法,需要确定以下环节:初始解、适配值函数、邻域结构、禁忌对象、候选解选择、禁忌表、禁忌长度、藐视准则、搜索策略、终止准则。

S.9 神经网络算法

神经网络算法的特点

  1. 神经网络算法与传统的参数模型方法最大的不同,在于它是数据驱动的自适应技术,不需要对问题模型做任何先验假设,在解决问题的内部规律未知或难以描述的情况下,神经网络可以通过对样本数据的学习训练,获取数据之间隐藏的函数关系。因此,神经网络方法特别适用于解决一些利用假设和现存理论难以解释,但却具备足够多的数据和观察变量的问题。

  2. 神经网络技术具备泛化能力,泛化能力是指经过训练后学习模型对未来训练集出现的样本做出正确反应的能力。因此可以同通过样本内的历史数据来预测样本外的未来数据。神经网络可以通过对输入的数据样本的学习训练,获得隐藏在数据内部的规律,并利用学习到的规律来预测未来的数据。

  3. 神经网络是一个具有普遍适用性的函数逼近器。它可以以任何精度逼近任何的连续函数,神经网络的内部函数形式比传统的统计方式更加灵活和有效。

  4. 神经网络是非线性的方法。神经网络中的每个神经元都可以接受大量其他神经元的输入,而且每个神经元的输入和输出之间都是非线性的关系。神经元之间的这种互相制约和互相影响的关系,可以实现整个网络从输入状态到输出状态的非线性映射。因此,神经网络可以处理一些环境信息十分复杂、知识背景不清楚和推理规则不明确的问题。

BP 神经网络算法

BP 神经网络算法的主要思想是:

对于 $n$ 个输入学习样本 $“x^1, x^2, …, x^n”$,已知与其对应的 $m$ 个输出样本为 $(t^1, t^2, …, t^m)$ 之间的误差来修改其权值,使 $z^l$ $(l=1, 2, …, m)$ 与期望的 $t^l$ 尽可能接近,即:使网络输出层的误差平方和达到最小。

BP神经网络的学习过程主要由四部分组成:输入模式顺传播、输出误差逆传播、循环记忆训练、学习结果判别。这个算法的学习过程,由正向传播和反向传播组成,在正向传播过程中,输入信息从输入层经隐含层单元逐层处理,并传向输出层,每一层神经元的状态只影响下一层神经元的状态。如果在输出层不能得到所期望的输出,则转入反向传播,将误差信号沿原来的连接通路返回,通过修改各层的神经元的权值,使得误差信号减小,然后再转入正向传播过程。反复迭代,直到误差小于给定的值为止。

算法流程

神经网络算法流程