下载掌阅APP，畅读海量书库
立即打开
随着科技的快速发展，多学科的分布式合作在制造业中越来越流行。资源分配规模迅速增长，从设计、仿真到生产、运维的整个生产周期越来越复杂。为了进一步缩短工业周期，提高运作效率，改善资源和信息的利用率，很多宏观和微观过程中的复杂问题有待解决和优化。从数学的角度，这些问题均可以根据变量、特性等内容分解为连续的数值优化问题和离散的组合优化问题。例如，复变函数优化、控制和仿真领域的非线性方程、复杂非线性规划均可以划归为连续数值优化问题；生产过程和系统管理领域的车间/任务调度、服务组合最优选择、合作伙伴选择和资源分配问题均可以划归为离散组合优化问题。由于计算方法和决策方式直接决定了生产系统的效率，各领域的专家都致力于将约束条件下的复杂问题进行建模，然后设计确定性或近似算法来解决它们。对于解空间规模较小的问题，很多确定性算法就可以高效地给出最优解。然而，在实际情况中，大多数优化问题都是NP难题，随着问题规模的增大，传统确定性算法的搜索时间呈指数增长，这就意味着没有一个确定性算法能在多项式时间内找到最优解。在这种情况下，以遗传算法（GA）、模拟退火法（SAA）、蚁群算法（ACO）、粒子群算法（PSO）等为典型代表的智能优化算法，为大规模NP难题的解决带来了新的思路。
智能优化方法是由多个相对独立的技术领域融合发展而来，它已成为优化领域和人工智能领域的主要研究方向之一。当前的主流智能优化算法都是基于种群迭代模式，它们产生包含一组个体的初始种群，在每一代中保持解空间的优良信息，并通过迭代步步趋近较好位置。这一类算法独立于特定问题，可以广泛应用于传统优化算法难以解决的复杂优化问题，并具有一些共同特征：
1）所有操作作用于每一代中的当前个体；
2）搜索机制是基于迭代演进的；
3）可以通过多种群机制实现并行优化；
4）多数情况下可以给出较为满意的近优解，而不保证能得到全局最优解；
5）算法寻优具有一定的随机性，不能保证高效搜索到近优解。
智能优化方法的一般性过程如下：首先，根据问题描述、问题特性、约束条件等信息，设计编码方式。编码方式是问题变量的映射，它直接决定了算法的演进速度。当选择了合适的编码机制后，算法进行初始化，根据问题变量的定义生成包含一定数目个体的种群。每个个体是在定义范围内随机产生的，其适应度值根据问题的目标函数（适应度函数）计算。在迭代过程中，各个演进操作的组合起到了主要作用，比如遗传算法中的选择操作、交叉操作、变异操作，蚁群算法中的路径选择和信息素更新操作。不同的操作在算法中具有不同的影响，因此不同操作的组合在解决问题时往往具有不同的效果。经过几步操作后，种群中的一部分或全部个体发生了改变，通过新个体的解码即可产生一组新解，再由适应度函数评估出种群中的最优合体和最差个体。其次，采用随机迭代、精英代替、合并最优个体等策略更新整个种群，并引发新一轮迭代。当迭代次数达到最大值或找到令人满意的近优解或最优解时，算法跳出循环迭代并输出全局最优解。
在这种演进模式下，问题变量和目标值反映在编码方式和适应度函数上，而约束条件则往往以惩罚函数的形式体现在适应度函数上，或以定义取值边界的形式体现在编码过程中。算法中的操作独立于特定问题，并且易于实现。这种统一的迭代过程使得智能优化方法的设计、改进和混合研究变得更容易、更直观、更灵活，并且基于迭代的多点优化搜索机制，使得智能优化方法可以高效地解决NP难题，避免组合爆炸效应。当然，并不是所有的操作都可以任意组合成高效算法。由于演进过程具有随机性，各操作在探索和开发能力上具有不同的特点和缺陷，很多智能优化方法具有早熟收敛、易陷入局优解等缺点。因此，不同领域的研究者在编码方式、演进操作、算法融合等方面进行着不断探索，以期以较小的迭代次数和种群规模获得更好的解。
近年来，包含不同演进机制的多种智能优化方法得到空前发展，研究者针对特定问题的不同背景和目标，在算法设计方面做了大量工作，并涌现出很多研究成果。按照不同的标准，智能优化方法可以被分为多个类别。根据研究重点的不同，智能优化算法方面的主流工作大体可以分为四类：①算法革新；②算法改进；③算法融合；④算法应用。另外，根据不同算法的搜索机制，基本的智能优化方法又可以分为三类：①演进学习算法；②邻域搜索算法；③群智能算法。
1）演进学习算法包括遗传算法、演进规划、人工免疫算法、DNA计算等，它们来源于自然的学习演进机制。种群中的个体根据不同的启发式操作，通过每一代内个体间的相互学习进行更新。在这一类方法中，应用最广泛的代表是遗传算法和人工免疫算法。
2）邻域搜索算法包括模拟退火法、禁忌搜索和可变邻域搜索。这一类算法中的邻域搜索一般通过随机或规则的步进变化实现。在搜索过程中，附加的控制参数或个体接受规则逐渐变化以达到收敛。因此，这类算法的主要特征是个体的独立局域搜索，目前，它们主要作为其他算法的改进策略应用。
3）群智能算法包括蚁群算法、粒子群算法、人工鱼群算法等，它们通过模拟群居动物（如蚁群、蜜蜂、鸟群等）的自组织行为进行算法设计。通常它们通过传播从个体中获得的社会信息实现组织结构的优化，目前最流行的群智能算法是蚁群算法和粒子群算法。
另外，一些具有不同特征的算法改进策略相继提出。研究者在算法收敛性、探索和开发能力等方面做了相关工作，以期指导算法找到更好的近优解。根据策略的不同功效，也可以将策略分为三类：自适应改进、开发改进和探索改进。
自适应改进旨在平衡前期的搜索广度和后期的挖掘深度。参数自适应改进、模糊自适应改进和基于目标的自适应改进是这类策略的典型代表。开发改进主要提高算法的挖掘能力，主要表现为优化搜索方向和小范围遍历。探索改进又称为全局搜索改进，它主要用来增加算法搜索到的种群多样性，防止算法陷入局部最优解。混沌策略、多种变异策略是这一类改进的典型代表。
1.遗传算法
遗传算法（Genetic Algorithm，GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题潜在解集的一个种群开始的，一个种群是由经过编码的一定数目的个体（染色体）组成。一个个体实际上是一个可能解的编码映射。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体形状的外部表现，实际代表了问题变量的组合方式。因此，在一开始需要实现从表现型到基因型的映射，即编码工作。由于仿照基因编码工作很复杂，往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉（crossover）和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。
遗传算法的基本运算过程如下：
1）初始化：设进化代数计数器位 t ，初始时刻 t =0；设置最大进化代数 T ；设置种群规模为 M ，随机生成 M 个个体作为初始群体 P （0）。
2）个体评价：根据适应度函数（目标函数或其变体）计算种群 P （ t ）中每个个体的适应度值，用于衡量个体的优劣程度。
3）选择运算：采用合适的选择算子作用于种群。其目的是把优质的个体选择出来，使其有机会作为父体，把优良的全部或部分基因遗传到下一代。选择操作包括轮盘赌选择策略、精英选择策略等，它是建立在种群中个体的适应度评估基础上的。
4）交叉运算：设置交叉概率，产生随机数，当时以某种方式交换两个父体的部分基因，产生新个体进入下一代种群。交叉操作是算法迭代进化的关键步骤，包括单点交叉、多点交叉等多种方式，其作用是继承优良个体的部分基因，并产生新个体，增加种群的多样性。
5）变异运算：设置变异概率，产生随机数，以某种方式将当前个体的某一位基因变成其等位基因。变异操作旨在通过基因突变的方式发现更优解，增加了算法跳出局部最优解并向更优区域搜索的可能性。
群体 P （ t ）经过选择、交叉、变异运算之后得到下一代群体 P （ t +1）。
6）终止条件判断：若 t = T ，则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算，否则跳转步骤2），进行新一轮迭代。
2.模拟退火法
模拟退火法来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。
模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像为空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。
模拟退火的基本思想：
1）初始化：初始温度 T （充分大），初始解状态 S （是算法迭代的起点），每个 T 值的迭代次数 L 。
2）对 k =1，…， L ，做第3）至第6）步：
3）产生新解 S′ 。
4）计算增量Δ t′ = C （ S ）- C （ S′ ），其中 C （ S′ ）为评价函数。
5）若Δ t′ <0，则接受 S′ 作为新的当前解，否则以概率exp（-Δ t′/T ）接受 S′ 作为新的当前解。
6）如果满足终止条件，则输出当前解作为最优解，结束程序，当连续若干个新解都没有被接受时，终止算法。
7） T 逐渐减少，且 T →0，然后转第2）步。
模拟退火算法新解的产生和接受可分为如下四个步骤：
1）由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成当前解的全部或部分元素进行置换、互换等，产生新解的变换方法决定当前新解的邻域结构。
2）计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。对大多数应用而言，这是计算目标函数差的最快方法。
3）判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则：若Δ t′ <0，则接受 S′ 作为新的当前解 S ，否则以概率exp（-Δ t′/T ）接受 S′ 作为新的当前解 S 。
4）当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
模拟退火算法与初始值无关，算法求得的解与初始解状态 S （是算法迭代的起点）无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种依概率收敛于全局最优解的全局优化算法。另外，模拟退火算法具有并行性。
3.粒子群算法
粒子群（Particle Swarm Optimization，PSO）算法是基于种群的进化计算方法，它的灵感来自于鸟群和鱼群等生物体的行为。在PSO算法中，每个元素称作一个粒子，每个粒子根据个体经验和邻域经验或种群经验持续更新自己的速度向量，以此在多维搜索空间中移向有利位置。在搜索过程中，个体间共享社会信息，指导搜索方向朝最优解的位置趋近。总体来讲，PSO算法自适应考虑全局和局部探索能力，是具有较好的平衡机制的简单启发式算法。与遗传算法相比，可以更迅速地收敛到最优解。与梯度下降法、拟牛顿法等经典优化算法不同，PSO算法不需要优化问题是可微的，并且可应用于非正规的、含噪声的优化问题。由于思想简单、易于实现、收敛迅速，PSO算法被成功应用于各个领域，如神经网络训练、任务分配、排序问题等。
在PSO算法中，随机产生初始种群并初始化参数。在评价适应度值后，PSO算法按如下步骤迭代：
1）如果粒子发现了更好值，则更新个体最优值（每个个体到目前为止找到的最好值）；
2）按照下式，根据个体最优值和全局最优值更新所有粒子的速度，并据此更新每个粒子的位置；
式中，
代表了粒子
i
在第
t
轮迭代中第
j
维速度（
j
=1，…，
n
）。
代表了粒子
i
在第
t
轮迭代中第
j
维位置。
c
1
和
c
2
是正加速参数，分别称为认知参数和社会参数，
γ
1
和
γ
2
是（0，1）之间的随机数。
ω
是惯性权重，按照下式更新：
ω t = ω t -1 × α
式中， α 是一个缩减因数。 ω 的值越大，先前速度对于当前速度的影响越大。
3）计算每个解的适应度值，重复迭代过程，直到达到最大迭代次数。