1.3 智能优化方法概述

面对形形色色的优化问题，人们已经提出了大量的优化算法。优化算法可分为精确算法和近似算法。

· 精确算法：精确算法以找到问题最优解为目标。典型的精确算法包括动态规划、分支定界算法、割平面法等。

· 近似算法：近似算法不能保证得到最优解，通常以得到问题的满意解为目标。近似算法有逼近算法和启发式算法。逼近算法能够给出所得到的解质量估计以及运行时间的界。启发算法能找到大规模算例的好解，它能以可以接受的计算开销得到可以接受的解，但是不能得到解的质量估计。启发算法可分为专门的启发算法和智能计算方法。专门的启发算法是针对某一个问题设计的启发式算法；而智能计算方法能应用于几乎所有的优化问题。

在设计优化算法时，一种思路是针对问题的特殊结构，设计出专用型算法。例如单纯形算法是运筹学的经典之作，但是它只能用于线性规划问题。

经典数学规划中的算法基本是专用型算法。这类算法一般都有很好的理论支撑，强调对问题结构的数学化应用，往往能找到最优解。这当然限制了这类算法的应用范围，并且这类算法对于使用者的编程能力也提出了很高的要求。

随着人类社会的发展，新的复杂问题层出不穷，许多问题要求人们在较短的时间内得到一个满意的解，因此迫切需要通用性强且易于实现的算法。

这些困境促使人们探索新的优化方法。同时，随着科学技术的发展，人们将生物学、物理学、化学中的原理方法与优化相结合，提出了许多智能优化方法。

1.3.1 常用的智能优化方法

1．遗传算法

1）简介

遗传算法[41]是最早的智能计算方法。它模拟自然界进化现象，借鉴达尔文的进化论以及生物遗传学的基本思想求解优化问题。

1859年，达尔文在其经典巨著《物种起源》中提出了自然选择（天择）学说。其核心思想是“物竞天择、适者生存”。具体地说，生物间存在生存争斗，适应者存活下来，不适应者被淘汰。生物通过遗传、变异和自然选择，从低级到高级，从简单到复杂进化发展。现代生物学表明：遗传物质是基因，遗传性状由基因控制，物竞天择，竞的是基因。在生物进化过程中，遗传信息保存在基因中，而染色体是基因的载体，突变和基因重组可以得到新的基因，从而产生新的染色体。而具有优良染色体的个体能更好地适应环境。J.Holland正是借鉴这一思想提出了遗传算法。在1975年出版的著作《自然与人工系统的自适应》中，他系统提出了遗传算法，还建立了模式理论（Schema Theorem），以解释遗传算法的工作机理。模式理论是遗传算法的重要理论基石。

在遗传算法提出之初，它主要应用于自适应系统。凭借J.Holland的学生K.DeJong和D.Fogel等的大量研究，遗传算法才被用于求解优化问题。1985年，D.Goldberg在其博士论文中研究了面向天然气管道优化的遗传算法。1989年，D.Goldberg出版了《搜索、优化于机器学习中的遗传算法》，这是遗传算法发展过程中的又一里程碑式的著作。进入20世纪90年代以后，遗传算法得到了科学界和工业界的广泛重视，出现了大量的研究成果和成功的工程实践。

在数学规划中，首先用数学语言描述优化问题，建立数学模型，再利用数学中的运算求解问题。在用遗传算法求解优化问题时，首先用生物学语言描述优化问题，将解编码成一个染色体，利用目标函数和约束函数建立染色体适应度函数评价染色体的适应能力，再利用生物进化过程模拟算法求解过程。

2）基本框架

遗传算法模拟生物学的进化过程。它首先对优化问题的解进行编码，将其表达成染色体，并产生由一定数量染色体组成的初始种群。再利用遗传操作对种群中的染色体进行操作，产生出新的种群，优者繁殖，劣者淘汰，使新种群更适应于环境。末代种群中的最优个体经过解码，输出遗传算法得到的最优解。

遗传操作包括3个基本遗传算子（genetic operator）：选择（selection）、交叉（crossover）、变异（mutation）。它们都是以随机规则进行操作的，其效果与编码方法、适应度函数、参数设定等密切相关。

遗传算法的主要步骤如下：

（1）种群初始化：进化代数计数器t设为0，随机生成N个个体作为初始种群P（0），并计算种群P（t）中每个个体的适应度。

（2）选择运算：依据种群中个体的适应度，将选择算子作用于种群。选择的目的是把种群中适应度高的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。

（3）交叉运算：将交叉算子作用于种群。交叉的作用是将两个父代个体的部分基因加以交换重组而生成新个体。在遗传算法中，交叉算子发挥着重要的作用，它是产生新解的重要算子。

（4）变异运算：将变异算子作用于种群。该算子改变种群中个体的若干基因座上的基因值。

（5）种群更新：种群P（t）经过选择、交叉、变异运算之后得到下一代种群P（t+1）。

（6）停止条件判断：t=t+1。若进化次数t等于最大允许进化代数MaxT，则对进化过程中所得到的具有最大适应度个体进行解码，并将其作为最优解输出，算法停止。

在设计遗传算法时，需要重点考虑以下算法要素：

（1）解的编码：编码是一种映射，它将优化问题的解空间中的元素转换成遗传空间的由基因按一定结构组成的染色体或个体。因此，编码也可以称作问题的表示。

（2）适应度函数定义：进化论认为适者生存。这里的“适者”是指适应环境的个体。个体的适应环境能力用适应度衡量。与之相对应，遗传算法利用适应度函数评价种群中的个体的优劣程度，其定义依赖于待求解问题的目标函数。

（3）种群初始化：在遗传算法开始迭代时，需要初始化产生一个种群。在这一过程中，需要考虑种群多样性、种群中个体的可行性、初始化过程的计算效率。一般采用随机法初始化种群。

（4）选择算子：选择操作依据种群中个体的适应度，从种群中选择适应度高的个体，淘汰适应度低的个体进行交叉和变异。最常用的选择方法是轮盘赌选择法（roulette wheel selection）。

轮盘赌选择法来源于博彩游戏中的轮盘赌，轮盘由圆盘和指针组成。图1-2给出了一个6扇区的轮盘。每个扇区中的数字表示该扇区的面积占总轮盘的比例。

在轮盘赌选择法中，每个个体的选择概率是其适应度和种群中所有个体的适应度总和的比值。设种群规模为N，个体i的适应度为Fiti，则个体i被选择的概率为

由式（1-2）可见，个体适应度越高，其被选择的概率就越大。在计算出每个个体的选择概率后，采用轮盘赌法进行选择。将轮盘分成N个扇区，每个扇区对应一个个体，扇区中的数据即为个体的选择概率。每次选择，转动一次轮盘的指针，当轮盘停止转动时，指针指向的个体就被选择。这样进行N次后，得到规模为N的种群。

（5）交叉算子：依据交叉率将种群中的两个个体按照一定的随机规则交换某些基因，能够产生新的染色体。

（6）变异算子：一定的变异概率对种群中染色体的一个或多个基因座的基因值进行变动。

（7）算法结构：在设计遗传算法时，种群更新方式有代（generational）方式和稳态（steady-state）方式两类。前一种方式更新整个种群，而后一种方式仅替换一些适应度低的个体。稳态方式仅更新种群中的最劣个体，如果该个体比当前得到的新个体差，则用新个体替换最劣个体。

2．模拟退火算法

1983年，Kirkpatrick提出了模拟退火算法[42]。顾名思义，这一算法模拟热力学中的退火过程，采用Metropolis准则接受新的解或状态，避免陷于局部最优。作为一种全局优化算法，它已经用于求解连续问题、组合优化问题等不同类型的问题，在生产调度、控制工程、机器学习、神经网络、图像处理等领域得到了广泛的应用。

1）基本原理

退火过程是一个典型的物理过程。它包括加温过程、等温过程和冷却过程。金属物体在退火后会变得柔韧。图1-3给出了在每个过程中物体的宏观和微观变化特点。一般地，退火过程中的温度是逐渐下降的。如果高温金属物体的温度急剧下降，它没有达到平衡态，而是处于非均匀的亚稳态，这就是淬火过程。经过淬火过程，物体能量并没有达到最小值，它能提高金属的强度和硬度，但会减弱韧度。

工业上，为了使材料满足一定的硬度和塑性要求，去除残余应力，得到预期的物理性能，通常对材料进行退火处理。金属物体的退火过程实际上就是将固体加温至充分高，再让其徐徐冷却。在加热金属的过程中，金属原子的热运动不断增强，内能增大，原子的有序稳定的状态被破坏，呈随机无序的状态。而在冷却的过程中，随温度的缓慢降低，金属原子由高能无序的状态趋于低能有序。为了使金属原子在每一个恒定温度下都能处于一个较低能量的状态即达到充分的热平衡，冷却过程温度必须缓慢降低。这个过程可以用蒙特卡罗方法模拟，该方法虽然比较简单，但需要大量采样才能获得比较精确的结果，计算量较大。

鉴于物理系统倾向于能量较低的状态，而热运动又妨碍它准确落到最低态的物理形态，采样时只需着重取那些有贡献作用的状态就可较快达到较好的效果。1953年，Metropolis等受到蒙特卡罗模拟方法的启示，提出了一种重要性采样法，即以概率接受新状态。在温度t，从当前状态i的邻域随机产生新状态j，两者的能量分别为Ei和Ej，若Ei＞Ej，则接受新状态j为当前状态；否则，依据以下概率

接受状态j，其中K为玻耳兹曼（Boltzmann）常数，exp（x）为变量x的指数函数。当这个过程多次重复，即进入大量迁移后，系统将趋于能量较低的平衡态。各状态的概率分布将趋于一定的正则分布。这种接受新状态的方法被称为Metropolis准则，它能够大大减少采样的计算量。

从Metropolis准则中可以看出，高温下可接受与当前状态能量差较大的新状态，而在低温下只能接受比当前能量低的新状态或与当前能量差较小的新状态。这与不同温度下的热运动影响金属原子重新排列的过程一致。在温度趋于零时，就不能接收任一个Ej＞Ei的新状态j。

1983年，Kirkpatrick等根据金属物体的退火过程与组合优化问题之间存在的相似性和Metropolis等提出的原始模拟退火算法，提出了现代版本的模拟退火算法，并且成功利用它解决了许多组合优化问题。

在模拟退火算法中，组合优化问题的一个解相当于退火过程中物体的一个状态，该解对应的目标函数相当于该状态的能量函数，而最优解就对应于最低能量的状态。算法设定一个初始高温，按照Metropolis准则在当前最优解的领域中搜索有潜力的新解，通过控制温度参数t的下降模拟温度徐徐降低的冷却过程。模拟退火算法在每个温度下进行多次的搜索，趋于最优解模拟物体在每个温度下都充分地达到热平衡，而最终趋于能量最小的基态。

2）算法基本要素及过程

模拟退火算法的基本思想是：将待优化问题的可行解看作是物体的原子状态，将目标函数看作物体原子的能量函数，模拟物体退火过程中粒子的热运动。降温过程中，结合概率突跳特性的Metropolis抽样准则，在解空间中随机搜索全局最优解，在陷入局部最优时，能以一定概率跳出，最终趋于全局最优解。

在模拟退火算法执行过程中，算法的效果取决于一组控制参数的选择，关键技术的设计对算法性能影响较大。

本节从算法使用的角度讨论算法实现的一些要素，包括状态表示、邻域定义、热平衡达到和降温控制等的概念。

（1）状态表达，在模拟退火算法求解优化问题时，一个状态对应于一个解。为了有效求解优化问题，应采用合适的编码表示解或状态。例如，在求解背包问题时，可采用0-1编码；求解旅行商问题时，可采用顺序编码；对于连续函数优化，可以采用实数编码。

（2）邻域定义，模拟退火算法从一个解出发，探索其邻域，寻找改进解。邻域决定搜索范围。

模拟退火算法的邻域定义与局部搜索中的定义一样。

例如在车辆路径问题中，一种邻域定义是采用一系列k-边交换操作作为邻域，k表示交换边的个数，k越大，其邻域解与当前解差别越大。

模拟退火算法采用基于Metropolis准则的邻域移动方法。

如果一个新解优于当前解，当前解被新解替换，那么就称从当前解移动到这个新解，否则，依据一定的概率决定当前解是否移向新解。

Metropolis准则中状态转移概率p ij定义如下：移动；当新解劣于当前解时，以一定概率移动。

其中i为当前状态，j为其邻域中的一个状态，其目标函数值分别为f（i）和f（j），当前温度为T。可见，当抽样得到的邻域新解优于当前解时，无条件

从Metoropolis准则中可以看出，当T很大时，状态转移概率趋于1，当前邻域中的任一状态都可能被接受，此时算法正在进行全局搜索；而当T很小时，状态转移概率趋于0，它只会接受当前邻域中更好的状态，此时算法进行局部搜索。

因此，模拟退火算法既具备跳出局部优解的能力又具备探索全局最优的能力。

（3）热平衡达到，工业退火要求温度缓慢下降，以保证金属原子在每个温度下达到稳定的能量态。但是在实际应用中达到理论的平衡状态是不可能的。模拟退火算法采用在每一个温度，在邻域中寻找一定数量的解，这一循环称为算法的内循环。内循环次数应该尽可能大，以达到近似热平衡过程。内循环次数的选择与问题的解空间大小有关。当解空间较大时，可以将内循环次数设为较大的数。另外，也可以依据其他条件动态调节内循环次数。例如，高温时迭代次数减少，低温时迭代次数增加。

（4）降温函数。

模拟退火算法的搜索能力与退火速度（温度的降低速度）密切相关。

在高温状态下，当前邻域中几乎所有的解都会被接受，算法进行全局搜索；当温度变低时，当前邻域中越来越多的解将会被拒绝，算法进行局部搜索。

在同一温度下，需要对邻域进行充分的搜索以达到热平衡状态。如果温度下降速度太快，则可能错过最优解，过早地陷入局部最优；如果温度下降速度太慢，又可能会降低算法的收敛速度。因此，降温函数的选择对于模拟退火算法的性能有重要影响。

3．禁忌搜索

禁忌搜索[42]是Fred Glover提出的一类智能计算方法。禁忌是人类处理复杂难题时避免迂回犯错的重要策略之一。早在1977年，Fred Glover已经开始探索利用这一思想设计算法。直到1986年才正式提出禁忌搜索。

利用禁忌表避免迂回搜索，并利用藐视规则接受劣解实现全局优化。在禁忌搜索提出以前，人们一般利用局部搜索求解复杂的优化问题。但是局部搜索最终停止于一个局部最优点。禁忌搜索是对局部邻域搜索的扩展，它提供了一种逃离局部最优解的有效方法。

1）基本思想

禁忌搜索是局部搜索的一种改进。在局部搜索中，它首先构造一个可行解x作为当前解（incumbent solution），在一定的邻域N（x）内进行贪婪搜索，找到当前邻域内的最优解x＇（即局部最优解），再以此最优解为新的当前解进行邻域搜索，重复上述过程，直到找到满足条件的解。邻域搜索的优势在于算法结构简单、容易实现，但搜索结果依赖初始解，且只能搜索到邻域内的局部最优解。

为了在搜索过程中避免重复且能够跳出局部最优解，从而实现全局搜索，禁忌算法采用类似于人类短期记忆的禁忌表，将算法搜索过程中最近的若干次移动加入禁忌表中，禁止在之后的迭代中进行移动，避免重复搜索已经搜索过的邻域。同时，禁忌表使算法能够接受劣解，将算法带入新的区域进行搜索。

算法循环过程中会不断更新禁忌表，在一定次数的循环后，最早进入禁忌表的移动会从禁忌表中删除，这就是所谓的“解禁”。

在搜索过程中，某些处于禁忌表中的移动有可能会使邻域搜索得到优于当前最优解的解，因此禁忌搜索又提出了渴望水平概念，当移动达到渴望水平，不论它是否在禁忌表中，都会被接受，即“破禁”。

禁忌搜索中禁忌表和渴望水平是最重要的两部分，可以使算法跳出局部最优，在一定的迭代次数下得到一个相对较优的解。

2）算法要素

设计禁忌搜索算法时，需要考虑以下基本要素：初始解、搜索空间和邻域结构、适值函数、禁忌表、选择策略、渴望水平、停止准则、编码方法。

（1）初始解。禁忌搜索算法是单点法，其性能依赖于初始解质量。当初始解质量较好时，算法能够较快收敛，且结果质量较好；反之，初始解质量较差时，会降低禁忌搜索的收敛速度。在求解一些约束条件较复杂的组合优化问题时，如果采用随机法一般难以得到质量较好的解，甚至也难以得到一个可行解。一个解决方法是：先利用问题的结构信息，应用一些简单的算法得到一个较好的初始解，再用禁忌搜索求解，从而提高算法的求解质量和效率。

（2）搜索空间和邻域结构。搜索空间是由搜索过程中所有可能解组成的集合。例如，在车辆路径问题中，搜索空间指的是所有满足约束的解集。然而在一些问题中，定义搜索空间并不是一件简单的事，尤其是在有多种定义方式时，如何合理定义搜索空间将直接影响到算法效率。特别地，在一些问题中，搜索空间并不只包括可行解，而且允许访问不可行解有助于求解问题。邻域结构与搜索空间密切相关。在禁忌搜索中，当前解S的邻域结构N（S）由其所有局部修正组成。具体地，邻域结构N（S）针对特定的待求解问题，往往有许多邻域结构的定义方法。在应用禁忌搜索求解问题时，选择和定义搜索空间与邻域结构是其中的关键步骤，这要求设计算法时对问题要有充分的认识和了解。

（3）适值函数。适值函数是对搜索结果的评价。一般而言，以目标函数直接作为适值函数是比较常用的方法。当目标函数的计算比较困难时，可以对目标函数进行适当的变形，作为适值函数以便于计算，从而节省计算时间，但变形后的适值函数必须是严格单调的，且适值函数的最优性与目标函数的最优性必须一致。

（4）禁忌表。禁忌表是禁忌搜索算法区别于局部搜索的关键，是禁忌搜索算法的核心。为能使算法跳出局部极小点，需要接受非改进移动。

禁忌表的作用在于避免循环，换言之，避免接受一个已经经历过的解。从数据结构上讲，禁忌表是具有一定长度的先进先出的队列。

通过避免访问以前搜索的区域，禁忌能使算法探索新的区域。在搜索过程中，禁忌对象保存在禁忌表中，而且通常只需要保存有限的信息。在设计禁忌表时，要考虑对什么禁忌以及禁忌多久。

（5）渴望水平。

禁忌搜索中，某些情况下，仅仅采用禁忌表会禁止一些可能得到高质量解的操作，甚至会导致算法停滞（即陷入局部最优）。因此，有必要采取措施以取消禁忌。即当某个移动满足某个条件时，不论该移动是否在禁忌表中，都接受这个移动，并更新当前解和当前最优解。这种使移动不受禁忌表禁忌的条件称为渴望水平，或称为特赦准则、藐视准则。

4．粒子群算法

粒子群优化算法[43]是一种基于种群的全局搜索算法和随机搜索算法。该算法以简单、易于实现、无须梯度信息、参数少、精度高和收敛速度快等优点受到学术界和工业界的重视，成功地解决了一系列连续和离散的优化问题，成为进化计算领域的研究热点。

粒子群优化算法是由心理学研究者James Kennedy和计算智能研究者Russell Eberhart在受到人工生命研究结果的启发后于1995年提出的，它是模拟动物群体的智能行为和使用计算机对这些认知行为进行仿真后的产物。

自然界中的许多生物都具有一定的群体行为，揭示自然界生物的群体智能行为并通过计算机建模是人工生命研究的主要内容之一。如图1-4所示，科学家们通过对鸟群、鱼群等群体性行为的研究发现：单个个体的行为很简单，一般不具有规律性，但是许多个体组成的群体通常表现出某种智能行为，表现出高度的组织性和纪律性。这一发现引起了科学家们的高度关注，吸引了包括生物科学家、计算机科学家和社会心理学家等研究的兴趣，促使他们展开广泛而深入的研究。例如，1987年Reynolds使用粒子系统模拟鸟群的集体行为。1990年，Heppner和Grenander发现鸟巢能吸引鸟群。他们发现，鸟群在飞行中可以改变方向，也可以朝着某一特定方向飞行，还可以重组队形，这其中一定具有某种潜在的规律。后来，这两个发现被用于标准的粒子群算法。

社会心理学研究，特别是动态社会影响理论的发展，是粒子群算法发展的又一重要来源。粒子在一个问题的搜索空间中可以看作一种人类的社会行为，个体可以根据环境的变化及时地调整他们的信念和态度，从而和群体的行为保持一致。这些研究为粒子群算法的提出奠定了思想来源和理论基础。

1）基本原理

粒子群优化算法源于对鸟类觅食行为的研究。鸟类觅食时，寻找食物最简单有效的方法是搜寻目前距离食物最近的周围区域。生物群体中个体与个体之间、个体与群体之间相互影响、相互作用，体现在群体中的信息共享，促进群体的进化发展。粒子群算法是根据生物种群的智能行为得到的启发求解优化问题，每个粒子都代表优化问题在搜索空间中的一个潜在解和对应一个由适应度函数决定的适应度值，每个粒子的速度决定飞行的方向和距离，速度根据粒子自身和其他粒子的移动经验进行动态的调整，以此实现个体在可行解空间中的寻优。粒子群算法首先对可行解空间中的一群粒子初始化，每个粒子都代表极值优化问题的一个潜在可行解，该粒子的特征用位置（position）、速度（velocity）和适应度3个指标表示。其中，适应度值通过适应度函数计算，其大小反映了粒子的优劣程度。粒子在解空间中运动时，其位置更新是通过跟踪个体极值Pbest和群体极值Gbest完成的。其中，个体极值Pbest是指在个体所经过的位置中通过计算其适应度值得到的最优位置，群体极值Gbest是指种群中所有粒子搜索到适应度最优的位置。粒子每更新一次位置，就计算一次适应度值，通过比较新粒子的适应度值与个体极值、群体极值的适应度值来更新个体极值Pbest和群体极值Gbest。

一个由n个粒子组成的种群X=（x1, x2, …, xn），在D维搜索空间中以一定的速度飞行，每个粒子在搜索时，充分考虑搜索到的历史最好位置和种群内其他粒子的历史最优点，在此基础上进行位置（或状态、解）的变化。

相关变量定义如下：

第i个粒子的位置表示为xi=（xi1, xi2, …, xiD）；

第i个粒子的速度表示为υi=（vi1, vi2, …, viD）；

第i个粒子的个体极值表示为pi=（pi1, pi2, …, piD）；

种群内所有粒子的群体极值表示为pg=（pg1, pg2, …, pgD）。

一般来说，粒子的位置和速度都是在连续的实数空间内取值。

在每次迭代过程中，粒子通过个体极值和群体极值更新自身的速度和位置信息，其数学表达式如下：

其中，d∈{1,2, …, D}; i∈{1,2, …, n}; k为当前的迭代次数；c1和c2称为学习因子（也称加速系数，学习因子使粒子具有自我总结和向种群中优秀个体学习的能力，并能向着自己的历史最优位置以及种群内或邻域内的历史最优位置靠近）。通常情况下，c1和c2取为2; r1和r2是[0,1]均匀分布的伪随机数。粒子速度和位置的关系如图1-5所示。

在粒子群算法中，粒子的速度主要由3部分构成。

（1）粒子当前的速度，是粒子飞行中的惯性作用和其能够飞行的基本保证，表明粒子当前的状态，防止粒子大幅度改变方向，平衡粒子的全局和局部搜索能力。

（2）认知部分，表示粒子在飞行中凭借自身的经验，向自己曾经找到过的最优位置靠近，使粒子有足够强的全局搜索能力，避免局部最优。

（3）社会经验部分，表示粒子在飞行中考虑到社会经验，向邻域中其他粒子学习，通过借鉴和信息共享，使粒子在飞行时向邻域内所有粒子曾经找到过的最好点靠近。

2）粒子群算法的要素

迄今为止，对于粒子群算法的研究大多以带有惯性权重的粒子群算法为基础进行分析、扩展和修正。因此，大多数文献中将带有惯性权重的粒子群算法称为标准版粒子群算法，而将前面的粒子群算法称为基本粒子群算法（或原始的粒子群算法）。

粒子群算法的要素包括算法的相关参数和算法设计中的相关问题两部分。其中相关参数包括种群大小、学习因子、最大速度、惯性权重；算法设计中的相关问题有邻域拓扑结构、粒子空间的初始化和停止条件。

在粒子群算法中，由n个粒子组成的集合X=（x1, x2, …, xn），每个粒子对应可行解空间中的一个潜在解，一个粒子从它的邻域ni接收信息，其中ni∈X。标准的粒子群算法中，粒子与粒子之间的关系可以用一个无向图G=（V, E）表示，其中V是粒子的集合；E是边的集合，表示粒子与邻域粒子之间的配对关系。这个无向图通常被称为粒子群的拓扑结构。粒子群算法中常见的拓扑结构有星型结构、环型结构、冯·诺依曼结构和齿型结构等，如图1-6所示。

粒子群算法的主要流程如下：

第1步：初始化粒子群，随机设定位置xi和速度υi；

第2步：在每一次进化（迭代）中计算每个粒子的适应度值；

第3步：对于每个粒子xi，如果其适应度值比所经历过的历史最好位置P best的适应度值好，则用当前位置pi更新个体历史最优位置P best；

第4步：对于每个粒子xi，如果其历史最优适应度值比群体内或邻域内所经历的最好位置Gbest的适应度值好，则用当前的全局最优位置pg 更新种群的历史最优的位置Gbest；

第5步：根据更新公式对粒子的位置xi和速度υi进行修正；

第6步：若未达到停止条件，则转到第2步。

5．人工蜂群算法[44]

自然界的蜜蜂是一种社会性群居生物，在群体中，单个蜜蜂的智能与能力是有限的。然而，由一群具有简单智能的个体组成的群体却表现出令人惊讶的智能。无论所处的环境多么复杂，它们总能找到蜂巢周围、距离适中且食物最丰富的食物源。蜂群表现出的智能行为引起了科学家的极大兴趣。

2005年，Karaboga系统地提出了人工蜂群算法（Artificial Bee Colony Algorithm）算法，并将人工蜂群算法应用于求解函数值优化问题，取得很好的效果。

1）基本原理

Seeley最早提出了一种蜂群的群居行为模型：自组织模拟模型。该模型中，群体由各种角色的蜜蜂组成，虽然每个角色的蜜蜂只能完成单一的任务，但蜂群中的蜜蜂通过舞蹈、气味等信息交互方式使整个蜂群能够协同完成诸如蜂巢构建、觅食等多种较为复杂的任务。

在模型中，蜂群包括3种基本要素：食物源、雇佣蜂和非雇佣蜂，其中非雇佣蜂包括侦察蜂和跟随蜂。具体地，这些要素描述如下：

（1）食物源，食物源的优劣程度主要依赖以下因素：食物源到蜂巢的距离；食物源的丰富程度；食物获取的困难程度等。一般地，用食物源的收益表征这些因素。

（2）雇佣蜂，也称为引领蜂。模型中雇佣蜂指正在某个食物源觅食或已经被这个食物源雇佣的蜜蜂。其数量一般与食物源有关。它们会把这个食物源的信息，例如离蜂巢的距离和方位、食物源的收益等信息通过舞蹈的方式告知其他蜜蜂。

（3）侦察蜂，侦察蜂通常在蜂巢周围搜索附近的食物源。一般地，蜂群中的侦察蜂数量约占整个蜂群总数的5%～10%。

（4）跟随蜂，跟随蜂在舞蹈区等待由雇佣蜂带回的食物源信息，它们观察雇佣蜂的舞蹈，选择自己认为满意的食物源进行跟随。

模型中，蜂群有两种基本行为模式：①引领模式，即当一只蜜蜂找到自己认为丰富的食物源时，引领其他蜜蜂到食物源处；②放弃模式，即放弃一处食物源，寻找新的食物源。

蜂巢附近的舞蹈区是蜂群中的个体进行信息交换的主要场所，也是角色转换的地方。在舞蹈区，蜜蜂通过摇摆舞的形式与其他蜜蜂交流食物源信息。在蜂群智能行为中，信息交换的过程如下：侦查蜂飞回蜂巢，并在舞蹈区进行舞蹈，舞蹈区周围的蜜蜂通过观察进行选择，一旦选定自己的食物源，蜜蜂角色转换随之发生。食物源被选择的可能性依赖于其收益率。食物源的收益率越大，其被选择的可能性也大。

在觅食行为之初，一部分蜜蜂从蜂巢出发，它们的角色是侦察蜂，在蜂巢周围进行随机搜索。当蜜蜂搜索到食物源后便进行采蜜，并记录食物源的相关信息，此时蜜蜂的角色就转变为“被雇佣者”，其余没有进行采蜜的蜜蜂，就成为“非雇佣蜂”。其中，被雇佣的蜜蜂在觅食完成后，回巢并做如下选择：

（1）放弃已经搜索到的食物源，角色由雇佣蜂变成侦察蜂。

（2）在舞蹈区与其他蜜蜂进行信息共享，招募更多的蜜蜂。

（3）继续返回采蜜，而不招募其他蜜蜂。

非雇佣的蜜蜂会做出如下选择：

（1）以侦察蜂的身份对蜂巢附近的食物源展开搜索。其搜索可以是完全随机的，也可依赖于先验知识。

（2）选择一个雇佣蜂进行跟随，其角色转变为跟随蜂，并在食物源的邻域进行搜索。

2）人工蜂群算法的基本过程

在用人工蜂群算法求解优化问题时，食物源对应于待优化问题的一个可行解，食物源的丰富程度（即适应度）代表解的质量。引领蜂和跟随蜂各占蜂群数量的一半，每个食物源只有一个引领蜂，即引领蜂数量等于蜜源数量。当一个食物源被放弃时，它所对应的引领蜂就变成了侦查蜂。在算法初始化后，蜜蜂开始对全部的食物源进行搜索。

引领蜂会先对全局进行搜索，并比较搜索前后食物源的丰富程度，蜜蜂会选择食物源较为丰富的目标。当所有的引领蜂完成搜索后，它们会回到信息交流区（即舞蹈区）将其了解的食物源相关信息与其他蜜蜂进行信息共享。跟随蜂则会根据引领蜂提供的信息按照一定的概率选择引领蜂进行跟随。适应度越高的食物源被选择的概率越大。然后，跟随蜂会和引领蜂一样进行邻域搜索，并选择较好的解。

1.3.2 智能优化方法的一般框架

智能优化方法是人工智能的一个重要分支。笔者将从人工智能视角，提出智能优化方法的一般框架。

人工智能的工程目标是设计制造出智能产品[45]，替代人解决问题或完成任务。在解决问题时，需要用到知识。所谓知识，是可用于解决该问题的领域信息。为了有效解决问题，需要解决以下问题：

（1）知识表示：将知识表示成能用计算机处理的符号；

（2）知识发现与学习：从经验中不断地自动获取知识；

（3）知识推理与应用：利用知识产生行为。

一般而言，智能优化方法是一种基于采样的迭代过程。在求解问题时，智能优化方法将该问题进行编码。在每一代，它主要包括产生解和信息加工两个过程。产生解过程对应于知识推理与应用过程，而信息加工过程对应于知识发现与学习过程。例如经典遗传算法选择两个个体的染色体进行重组得到解，其信息加工机制是种群更新机制。在遗传算法中，知识利用染色体进行编码表示。因此，智能优化方法是符合人工智能解决问题的一般范式的。

本书将讨论的蚁群算法在知识表示、知识发现与学习及知识推理与应用方面具有显著特色。在蚁群算法中，信息素具有重要的作用，它是知识的载体。在蚁群算法演化过程中，蚁群通过信息素进行信息交互，并用以指导解的构造。

1.3.3 智能优化方法分类

目前，已有数十种智能计算方法。常见的分类准则有以下几种。

· 种群vs单点：单点法在搜索过程中仅对一个解进行操作和变换；而基于种群的算法对一个种群进行演化。

· 记忆的作用：有些智能计算方法是无记忆的，即在搜索过程中，没有利用到动态提取的信息，例如模拟退火算法。而有些智能计算方法是有记忆的，它们利用到在线学习的信息，如禁忌搜索的长期和短期记忆。

· 构造型vs非构造型算法：通过构造过程得到解。

· 确定型vs随机型：在求解问题过程中，确定性的智能计算采用确定型决策。而在随机智能计算方法中，采用了许多随机规则。在确定型算法中，如果初始解给定，则输出解是确定的。而在随机型算法中，即使给定初始解，最终得到的解也可能是不同的。

本书研究的蚁群智能优化算法与粒子群算法和蜜蜂算法均属于群体智能（Swarm Intelligence）范畴[44]。群体智能是受蚁群、鸟群、蜂群等群居生物体行为启发，通过模拟这些群居生物行为产生的计算方法。在自然界中，单个蚂蚁（或鸟或蜜蜂）的能力非常有限，难以独立生存，但是一群蚂蚁却能通过相互协作很好地适应环境，表现出智能行为。

在群体智能中，一群相互之间直接或间接通信的个体组成群体，这些个体通过相互协作求解问题。

1994年，Mark Millonas提出了群体智能应该遵循的5条基本原则。

（1）接近原则（Proximity Principle）：群体中的个体具有对空间和时间进行简单计算的能力。

（2）质量响应原则（Quality Principle）：群体能够对环境中的质量因子作出响应。

（3）多样性响应原则（Principle of Diverse Response）：群体的行动和响应范围不能太窄，应具有多样性。

（4）稳定性原则（Stability Principle）：每次环境变化时，群体不应该随之改变其行为模式。

（5）适应性原则（Adaptability Principle）：在保证计算代价的条件下，群体能够改变其行为模式。

1.3.4 智能优化方法的特点

与传统优化方法相比，智能计算方法一般具有以下特点：

（1）自适应性强。对待求解的优化问题没有过多的要求，一般不要求满足可微性、凸性等条件，在迭代过程中，一般只用到目标函数值等信息，不必用到目标函数的导数等问题信息。这使得智能计算方法具有很强通用性。

（2）优良的全局寻优能力。它们在解空间进行全局搜索，按照一定的机制指导搜索，算法具有很好的鲁棒性，对初始条件不敏感，具有很强的容差能力。

（3）易于实现。智能计算方法原理简单，一般不需要数学推导。