第1章群体智能算法概述

第1章 群体智能算法概述

1975年，美国Michigan大学的John Holland[1]教授发表了其开创性的著作《Adapatation in Natural and Artificail System》，在该著作中John Holland教授对智能系统及自然界中的自适应变化机制进行了详细阐述，并提出了计算机程序的自适应

[2]变化机制，该著作的发表被认为是群体智能（Swarm Intelligence）算法的开山之作。

随后，John Holland和他的学生对该算法机制进行了推广，并正式将该算法命名为遗传算法（Gentic Algorithm，GA）[3]~[5]。遗传算法的出现和成功，极大地鼓舞了广大研究工作者向大自然现象学习的热情。经过多年的发展，已经诞生了大量的群体智能算法，包括：遗传算法、蚁群优化（Ant Colony Optimization，ACO）[6]~[7]算法、差异演化（Differential Evolution，DE）[8]~[12]算法、粒子群优化（Particle Swarm Optimization，PSO）[13]~[16]算法等。

随着群体智能算法在诸如机器学习、过程控制、经济预测、工程预测等领域取得了前所未有的成功，它已经引起了包括数学、物理学、计算机科学、社会科学、经济学及工程应用等领域的科学家们的极大兴趣。目前关于群体智能计算的国际会议在全世界各地定期召开，各种关于信息技术或计算机技术的国际会议也都将智能进化技术作为主要研讨课题之一。甚至有专家指出，群体智能计算技术、混沌分析技术、分形几何、神经网络等将会成为研究非线性现象和复杂系统的主要工具，也将会成为人们研究认知过程的主要方法和工具。

1.1 群体智能算法的特点

1.1.1 智能性

群体智能算法通过向大自然界中的某些生命现象或自然现象学习，实现对于问题的求解，这一类算法中包含了自然界生命现象所具有的自组织、自学习和自适应性等特性。在运算过程中，通过获得的计算信息自行组织种群对解空间进行搜索。种群在搜索过程中依据事先设定的适应度函数值，采用适者生存、优胜劣汰的方式进化，所以算法具有一定的智能性。

由于群体智能算法具有的这种优点，应用群体智能算法求解问题时，不需要事

2

群体智能算法及其应用

先对待求解问题进行详细的求解思路描述。对于某些复杂性高的问题，高效求解成为可能。

1.1.2 隐含本质并行性

群体智能算法通过设定相应的种群进化机制完成计算，而种群内的个体则具有一定的性，个体之间或需要，或不需要进行信息交流，而个体的进化方式则完全取决于自身的状态。所以，对于群体智能算法而言，其个体之间完全是一种本质上的并行机制。如果使用分布式多处理机来完成群体智能算法，可以将算法设置为多个种群并分别放置于不同的处理机实现进化，迭代期间完成一定的信息交流即可（注：信息交流并不是必要的），迭代完成之后，根据适应度值进行优胜劣汰。所以，群体智能算法这种隐含的本质并行性，能够更充分利用多处理器机制，实现并行编程，提高算法的求解能力。更加适合目前云计算等分布式计算技术迅速发展的背景。

1.1.3 解的近似性

群体智能算法通常来自于对大自然中某种生命或其他事物的智能协作进化现象的模拟，利用某种进化机制指导种群对解空间进行搜索。由于该类算法缺乏严格的数学理论支持，对于问题的解空间采用反复迭代的概率性搜索，所以群体智能算法会存在早熟或解精度较低等问题，而这也是所有群体智能算法几乎都存在的弱点。所以，很多时候对求解的问题来说，群体智能算法仅仅得到的是一种最佳解的近似解。

1.2 群体智能算法的计算模式

不失一般性，考虑以最小化（min{f(x)|x∈X}）问题进行探讨（本书均以最小化问题考虑，下同）。式中，X称为问题的解空间，即问题的所有可能解。X既可以是连续域Rn的一个子集，也可以是离散域内一个有限集合。群体智能算法的优化求解就是从多个随机初始解开始，通过一定的规则不断迭代和进化产生新解的过程。

在群体智能算法中，将多个解的集合称为种群（Population），记为P(t)，t表示种群进化的代数，种群的大小称为种群规模，一般记为POP或N。以x1(t),x2(t),\",xn(t)表示种群中各个解，即种群的个体（Individual）或称染色体。种群中新个体（Offspring）通常由父个体（Parent）以某种交配组（Chromosome）

第1章 群体智能算法概述

3

合方式产生，这种交配方式称为进化模式（Evolutionary Model）。进化计算的迭代过程可以归纳为社会协作、自我适应和竞争进化等三个基本环节。

在社会协作过程中，个体之间进行彼此的信息交换和互相学习。种群内个体在自我适应过程中通过主动或被动的方式不断调节自身的状态以适应环境。相互竞争则是指种群内具有更优状态的个体将会获得较大的生存机会，进入子种群，即种群的更新策略。群体智能算法框架描述如下：

算法1.1 群体智能算法[13] 输入：解空间内的初始种群。

输出：最佳个体Xgbest(t)。

步骤1. 初始化种群规模、迭代次数等参数。

步骤2. 在解空间内随机初始化种群P(t)={X1(t),X2(t),\",Xn(t)},t=0。 步骤3. While（终止条件不满足）Do。 步骤4. 计算P(t)中个体的适应值。 步骤5. 挑选部分个体进行社会协作操作。 步骤6. 自我适应。

步骤7. 竞争操作，生成新一代种群。 步骤8. endwhile。 步骤9. 输出最终解。

通过以上计算框架可知，群体智能算法通过对附加于种群内个体的三种操作引导个体向最佳解靠近，从而达到寻优的目的，其形式化模型如公式（1.1）所示。

PIO={POP(u),S(α),A(β),C(γ);t} （1.1）

式中，POP(u)代表种群，u表示其规模；S、A、C分别代表社会协作、自我适应机制和竞争操作，括号内表示该操作所需的相应信息，t 表示算法迭代代数。

1.2.1 社会协作机制

在本过程中，将通过一定的选择机制挑选部分个体进行信息交换和相互学习。所涉及的信息包括：个体选择的方法（schoi）,个体规模（snum），新实验个体的产生机制（sway），种群历史信息的使用方式（shis）等，可以用公式（1.2）进行形式化描述。

S(POP(t),[schoi,snum,sway,shis]t)

（1.2）

1.2.2 自我适应机制

自我适应机制是指个体通过主动或被动机制不断调整自身的状态，以适应其所

4

群体智能算法及其应用

处的生存环境。个体通过两种搜索机制来调整自身的状态，全局搜索和局部搜索。全局搜索机制保证了个体在更加广泛的范围内探索新解的能力，能够更好地保证种群多样性，避免出现早熟收敛现象；局部搜索机制则与之相反，容易使算法提前收敛于局部最佳，但是能够较快地提高个体的质量，加快算法的收敛速度。种群中个体的自我适应通常就是处理好两种搜索机制之间的平衡。

通过上述两种过程，可以生成新的实验个体，新实验个体生成机制的形式化描述如公式（1.3）所示。

new(t)=A(S(POP(t),[schoi,snum,sway,shis]t,βt)

（1.3）

1.2.3 竞争机制

群体智能算法通过竞争机制从POP个父个体和m个临时子个体中挑选个体进入下一代种群中。在大部分群体智能算法中，种群的规模POP一般选择固定不变，个体替换策略分为整代替换策略r(POP,m)和部分替换策略r(POP+m)；前者指POP个父个体完全被m个子代个体所替换，后者指POP个父个体中只有部分个体被替换。当然，如果为了保存精英个体，可以选择精英保留策略，即父代个体中的优秀个体不被替换而进入下一代个体。

产生子种群的形式化描述如公式（1.4）所示。

POP(t+1)=C(POP(t),New(t),[p,r,elitist]t)

（1.4）

上述公式（1.4）中p代表种群个体，r代表替换模式，elitist代表精英个体。

1.3 遗 传 算 法

遗传算法采用随机机制对解空间进行搜索，并在搜索过程中不断迭代、进化。由于该算法采用了模拟生物界中的生物遗传原理进行随机解空间搜索，所以它具有一定的广泛性和适应性。

在实际的操作中，遗传算法利用自然界中的适者生存机制作为算法进化中的主要进化机制，同时将随机的信息交换机制吸收进来，较好地消除了迭代过程中出现的不适应因素，有力地提高了收敛速度。

自遗传算法被提出以来，已经被广泛应用于各种领域问题的求解，并表现出了非常好的求解效率。比如，求解组合优化问题（TSP问题、背包问题等）、神经网络的结构优化问题、灾害评价与预报、网络路由选择等。

遗传算法的操作对象是被称为种群的一组二进制串，而其中的单个个体称为染

第1章 群体智能算法概述

5

色体或者叫个体，每一个染色体对应于问题的一个解。遗传算法的操作流程是：从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异不断产生下一代群体。如此迭代，直至满足期望的终止条件。该算法的形式化描述如下：

GA=(P(0),N,l,s,g,p,f,t)

其中，P(0)=(X1(0),X2(0),\",Xn(0))表示初始种群；

N表示种群中含有个体的个数； l表示二进制串的长度； s表示选择策略； g表示遗传算子；

p表示遗传算子的操作概率；

f表示适应度函数（fitness function）； t表示终止准则。

1.3.1 标准遗传算法原理

应用遗传算法求解问题时，主要经过种群初始化、计算适应度函数值、父个体交叉、变异等操作，算法流程图如图1-1所示。

算法1.2 标准遗传算法（GA） 输入：种群P。

输出：最优个体Xgbest(t)。

步骤1. 初始化群体P(0),迭代次数t = 0。 步骤2. 计算P(t)中个体的适应度。

步骤3. 如果满足终止条件，则终止算法，输出最优个体；否则继续下一步。 步骤4. m= 0。

步骤5. 如果m≥N，即已经将全部的父个体处理完毕，则跳转到步骤2；否则，执行下一步。

步骤6. 根据个体的适应值比例选择两个父个体。

步骤7. 确定随机值β，如果该值随机大于1，则将两父个体进行杂交操作，然后将个体变异后插入到P(t + 1)中，并且跳转到步骤9。

步骤8. β如果在随机值0和1之间，则将两个父个体直接变异后，插入下一代个体P(t + 1)中。

步骤9. m = m + 2；并且跳转到步骤5。 设计一个求解实际问题的遗传算法的步骤如下。

6

群体智能算法及其应用

开始随机产生N个个体组成初始种群P(0)对当前种群中的个体进行评价Y终止吗？Nm=0随机选择两个个体结束输出结果满足PC？NY两个个体交叉生成临时子个体两个个体做临时子个体对若干临时子个体执行变异操作YM（1）确定编码方案

遗传算法求解问题不是直接作用在问题的解空间上，而是利用解的某种编码表示。选择何种编码表示对算法的质量和效率会产生较大的影响。遗传算法一般采用如下三种编码：二进制编码、十进制编码和格雷编码。 （2）确定适应函数

一般以目标函数或费用函数的形式表示。解的适应度值是进化过程中进行个体选择的唯一依据。应用适应度函数来评价解的质量，它通常依赖于解的行为和环境的关系。

第1章 群体智能算法概述

（3）设计遗传算子

包括繁殖操作、杂交操作、变异操作。 （4）设计终止条件

7

遗传算法没有利用目标函数的梯度信息，无法确定个体在解空间中的位置。从而无法用传统的方法判定算法是否收敛，并终止算法，所以一般都是预先设定一个最大的进化代数或检测种群的平均适应度连续几代的变化是否趋于平稳，以判断是否终止算法。

1.3.2 编码机制与主要算子

1．编码机制

遗传算法的求解主要是通过位串的操作实现对解空间的搜索，所以不同编码方式会影响算法的问题表达和解空间的搜索。

（1）二进制编码

将原问题的解映射为一个二进制串描述（0,1表示），然后，通过对位串的操作实现对问题的求解，最后将结果再还原为其解空间的解。

例如，染色体（0,1,0,1,1,1）表示为长度为6的串。 （2）十进制编码

将问题的解描述为一个0～9组成的十进制串。 （3）实数编码

实数编码将问题的解用实数来描述，实现了在解的表现型上直接进行遗传算法操作。即，问题的解空间实际就是遗传算法的运行空间。

（4）格雷编码

格雷编码其实质也是一种二进制的表示形式，与普通二进制不同的是，格雷编码是通过一个特定的格雷变换得到的二进制串。例如，假设存在一个二进制串a1, a2,

a3, …, an，格雷码串为c1, c2, c3, …, cn，则该二进制串与格雷编码存在的转换关系如公式（1.5）所示。

⎧a1(i=1) ci=⎨

⊕>(1)aaii⎩i−1

2．主要算子

遗传算法的算子主要包括选择算子、交叉算子、变异算子三种。 （1）选择算子

（1.5）

遗传算法中选择算子是需要方法最多的算子之一，该算子主要用于通过何种方式在父代多个个体中选择较为优良的个体遗传到下一代中。一般情况下会根据适应

8

群体智能算法及其应用

度值的优劣进行处理，选择的方法包括：比例选择方式、精英选择方法、排序选择、联赛选择、排挤机制选择等。

（2）交叉算子

主要用于实现父代染色体之间的信息交换，根据不同位交换方式，主要分为以下三种杂交操作方式。

① 点式杂交

分为单点式与多点式杂交。单点式杂交即随机的在两个父串上选择一个点，然后交换这两个串该杂交点后面对应的子串。

② 两点杂交

随机选取两个杂交点，然后将两个杂交点中间的部分数据进行交换。 ③ 均匀杂交

先随机生成一个与父个体长度一致的二进制串，然后依据该串的数据进行处理，

0则不交换两个父个体对象的串位，1则交换相应的位。

（3）变异算子

变异算子的操作是产生新个体的强有力的方法，它决定了遗传算法的全局搜索能

力。设置一定的概率pm，根据概率将所选个体的位取反，实现将该染色体的变异操作。

1.4 差异演化算法

借鉴遗传算法的思想，1995年美国的Rainer Storn和Kenneth Price提出了一种新颖群体智能算法——差异演化算法。该算法最主要的操作思想是基于种群内的个体差异度生成临时个体，采用一对一的贪婪选择竞争机制，通过随机重组实现种群进化。标准算法采用实数进行编码，避免了复杂的基因操作，所以具有较快的运算速度。由于采用实数编码，所以原始DE算法主要用于连续域的优化问题，如果要用于离散域的问题优化，则需要进行相应的转化或映射。

在DE中，首先利用父代个体与差异向量（Differential Vector）重组构成差异个体；接着，按照一定的概率由父代个体与差异个体交叉产生临时个体；最后，根据临时个体与父代个体的适应度大小，以“优胜劣汰”的贪婪方式产生子代个体。

差异演化算法具有三个基本操作，即变异操作算子、交叉操作算子和选择操作算子。它的协作策略数学模型可以用公式（1.6）描述。

α′=[(X1(t),X2(t),X3(t)),3,X1(t)+F*(X2(t)−X3(t)),Xgbest(t)]

（1.6）

差异演化算法的自我适应策略是利用交叉操作来提高种群的多样性，即公式（1.7）。 ⎧⎪dij(t+1)r1≤CR或r2=j β(t)=eij(t+1)=⎨

x(t)其他⎪⎩ij

（1.7）

第1章 群体智能算法概述

9

差异演化采用固定规模的种群，实施一对一的贪婪选择竞争机制；运算过程中，精英个体得以保留，因此算法的竞争策略描述为公式（1.8）。

Γt=[v=λ,(v+λ),Xgbest(t)]

（1.8）

设X1(t)、X2(t)是种群内两个互不相同的个体，则用D12=X1(t)−X2(t)表示它们构成的差异向量。在DE中，根据差异向量与父代个体重组方式的不同，可形成多种不同的进化模式，我们将其记为DE/X/Y/Z。其中X表示与差异向量进行重组的个体，它可以是任意父代个体，也可以是某个确定个体或当前最好个体；Y为重组时差异向量的个数；Z代表交叉所采用的模式。目前有超过10种的进化模式，常见的几种进化模式如公式（1.9）至公式（1.12）所示。

DE/rand1/1/bin模式：

Di=X1(t)+F*(X2(t)−X3(t))

DE/rand-to-best/1/bin模式：

Di=Xi(t)+F*(Xbest(t)−Xi(t))+F*(X1(t)−X2(t))

DE/best/1/bin模式：

Di=Xbest(t)+F*(X1(t)−X2(t))

（1.11） （1.12） （1.10） （1.9）

DE/rand2/1/bin模式：

Di=Xi(t)+F*(X1(t)−X2(t)) 差异向量的摄动幅度，一般取0.8。

不失一般性，假设待求解问题为最小化问题minf（x1, x2,…, xn），xj∈[Lj, Uj]，1≤j≤n。令Xi(t)=(xi1(t),xi2(t),\",xin(t))为第t代种群中第i个个体，种群规模为s，。 则差分进化算法的算法流程描述如下（DE/rand/1/bin模式）

算法1.3 标准DE算法

步骤1. 初始化参数，设定迭代次数t = 0。

步骤2. 在解空间内以公式（1.13）随机生成初始种群。 P(t)={Xi(t)|xij(t)=rand(0,1)*(Uj−Lj)+Lj∧1≤i≤s∧1≤j≤n}

（1.13）

说明：F∈（0, 1.2）称为摄动比例因子（Scale Factor of Perturbation），用于控制

其中rand(0,1)为（0,1）上的随机数，并置t=0；

步骤3. 执行变异操作。从当前种群P（t）中随机选择3个不同于Xi(t)的个体

Xa(t)、Xb(t)、Xc(t)，a≠b≠c。选择公式（1.9）至公式（1.12）中的某种模式生成差异个体，Di(t+1)=(di1(t+1),di2(t+2),\",din(t+1))。

步骤4. 执行交叉操作。随机生成随机小数r1∈(0,1)和随机整数r2∈[1,n]，按公式（1.14）生成临时个体。

10

群体智能算法及其应用

⎧⎪Dij(t+1)r1≤CR,or,r2=j

Eij(t+1)=⎨

其他X(t)⎪⎩ij

（1.14）

其中1≤i≤s且1≤j≤n；CR∈(0, 1)为交叉因子，用于控制种群个体之间的分散度。

步骤5. 执行选择操作。如果f(Ei(t+1))Xi(t+1)= Xi(t),1≤i≤s。

步骤6. 计算种群P(t+1)中适应度最佳的个体Xgbest(t)；

步骤7. 如果终止条件不满足，则t=t+1并跳转到步骤2；否则输出Xgbest(t)与

f(Xgbest(t))，结束算法。

差异演化算法原理简单，计算效率和解精度均较高，目前针对该算法的研究成果极为丰富，是一个应用较为广泛的群体智能算法。

1.5 粒子群算法

粒子群优化（Particle Swarm Optimization，PSO）[16]算法于1995年由Kennedy和Eberhart两位博士提出，该算法通过模拟自然界中鸟群的觅食运动来实现对于最终问题的求解。在PSO算法中，鸟群中个体所处的位置被看成是解空间中的一个栖息地，进化过程中通过个体之间不断的信息交流，引导种群逐步向可能的解位置靠近，并逐步提高在求解过程中所发现的栖息地质量，从而实现最终问题的求解。

PSO算法具有较好的全局收敛性和较佳的解精度，计算速度快，一经出现即引起了广大学者的研究兴趣，形成了一个研究热点。

1.5.1 粒子群算法的原理

PSO算法的优化过程体现了群体智能算法的一个重要的特征——群体之间的简单合作表现出较高的智能性。可以通过社会认知理论，将PSO算法概括为如下三个主要过程。

（1）模拟行为

粒子群中的个体通过利用某种机制模拟优于自身个体的行为，以达到向其学习的目的。这是社会中广泛存在的一种学习机制，人类、动物界均适用。

（2）优化行为

粒子群中的个体通过向其他个体学习，发现自身所存在的不足或缺陷，采用一定的机制修正、调整自身的状态。

（3）评价行为

粒子群算法较好地采用了社会学习中的激励机制。对于社会学习中所产生的正

第1章 群体智能算法概述

11

反馈、负反馈、个体吸引、排斥等进行优化、吸收。并通过所采用的激励措施等机制来完成对于所处环境的学习。

PSO算法将种群内的个体看做是一个没有质量、没有体积的粒子，这些粒子在其所处的解空间中进行搜索，粒子具有一定的速度，粒子根据自身的经验和群体的知识来综合调整各个粒子的飞行速度，逐渐向全局最优解的位置靠近。粒子群中的个体所处位置被视作问题的可能解，粒子的飞行速度、飞行方向、飞行距离通过一定的机制进行控制。进化过程中，设置相应的适应度函数（fitness function）来评价粒子所处位置的优劣，采用优胜劣汰的方式进化。

Angelie PJ在其文献中，对于PSO算法与GA算法的区别进行了分析。PSO算法通过维护粒子的速度矢量和位置矢量两个方面来保证算法对于解空间的搜索，并且PSO算法具有记忆能力，这是与GA算法不相同的特点。粒子在进化过程中保存其搜索到的历史最优位置，并保证搜索与记忆的分离。PSO算法在进化过程中还具有GA算法所没有的信息共享，通过gbest、pbest两个极值进行共享的信息传递，通过追随最优粒子的行为使种群向最优解方向收缩。

1.5.2 PSO算法的计算模型

标准PSO算法主要应用于连续解空间问题的优化，其数学描述如下： 设所求解问题的解空间为n维，粒子群规模设为M，则粒子i在第t次迭代过程中所达到的位置状态表示为Xi(t)={xi1(t),xi2(t),\",xin(t)},i=1,2,\",M，粒子的飞行速度定义为Vi(t)={vi1(t),vi2(t),\",vin(t)}，则粒子i在第t时刻的第j(j=1,2,\",n)维的飞行速度调整为下式（1.15）和公式（1.16）所示。

vij(t)=wvij(t−1)+c1r1(pij−xij(t−1))+c2r2(gj−xij(t−1))

（1.15）

⎧vmax vij(t)=⎨

⎩−vmax

vij(t)>vmax

vij(t)<−vmax

（1.16）

粒子i在t时刻的位置更新可由公式（1.17）计算所得。 xij(t)=xij(t−1)+vij(t)

（1.17）

公式（1.15）中w为惯性权值（Intertia Weight），c1和c2为加速因子（Acceleration

Constants）,r1,r2是[0,1]内的随机数，gj为第j维上的最优值。

算法1.4 标准PSO算法

输入：种群规模为POP的群体，最大迭代次数itermax。 输出：最佳个体Xgbest(t)。

12

群体智能算法及其应用

步骤1. 在解空间内随机初始化种群Pij(0)，设种群规模为POP，并初始化算法的相关参数。

步骤2. 根据所设定问题的适应度函数计算各个粒子的目标函数。 步骤3. 令全部粒子更新自己所经过的最佳位置pbest。

步骤4. 依据步骤3的结果更新整个群体所经历的最佳位置gbest。 步骤5. 根据公式（1.15）至公式（1.17）更新粒子i的速度和位置。

步骤6. 如果迭代次数满足终止条件或者所求解精度达到所设定的精度要求，则输出最终求解结果，终止算法，否则跳转到步骤2。

标准PSO算法的流程如图1-2所示。

开始种群初始化、参数初始化，迭代次数为t = 0评价粒子的适应度计算粒子的历史最优位置否计算群体历史最优位置粒子的速度和位置进行更新算法结束吗？是输出结果终止算法

图1-2 标准PSO算法的流程图

第1章 群体智能算法概述

13

1.6 教—学优化算法

教—学优化（Teaching Learning Based Optimization，TLBO）[17]算法是印度学者

RAO提出的一种新颖的群体智能算法。该算法模拟人类学习过程机制，分为两个阶段：教学阶段和学习阶段。

算法的种群被划分为“教师”和“学生”两个种群，“教师”即为种群内的最优个体，“学生”种群首先通过向教师学习来提高自身知识，实现向当前最优解逼近。其次，“学生”种群则通过内部之间的相互学习机制改变自身的状态，以保持种群多样性。RAO将其应用于机械设计优化等问题中，取得了良好的优化效果．TLBO具有结构简单、运算快、参数少等特点，在许多实际优化问题中得到了成功的应用[18]~[20]。

算法1.5 标准TLBO算法

输入：种群规模为POP的群体，最大迭代次数itermax。 输出：最佳个体Xgbest(t)。

步骤1. 设置算法的参数，种群规模POP、最大迭代次数itermax等。

步骤2. 设置迭代次数t = 0，并应用公式（1.10）在解空间内进行种群的初始化。 步骤3. 计算机种群中所有个体的适应度，并选择最优个体作为教师Xteach(t)。 步骤4. 教师教学阶段。计算出全部个体的平均值为Xmean(t)，设教学因子为

β=round(1+rand(0,1))（注：round()函数结果为四舍五入），则对种群中所有个体

执行公式（1.18）生成其子个体，以优胜劣汰的方式替换原个体Xi(t)。 Xi′(t)=Xi(t)+rand(0,1)*(Xteach(t)−β×Xmean(t))

（1.18）

步骤5. 学生学习阶段。从种群中随意选择两互不相同的个体Xr1(t)、Xr2(t)，令个体Xi(t)向其中优秀的个体学习，按公式（1.19）生成其子个体，同样以优胜劣汰的方式替换个体Xi(t)。

⎧Xi(t)+randi×(Xr1(t)−Xi(t)),f(Xr1)X(t)rand(X(t)X(t)),f(X)f(X)+×−>ir2ir1r2⎩i

（1.19）

步骤6. 若算法满足终止条件，输出最佳个体，终止算法；否则，跳转到步骤3。

1.7 顾问引导搜索算法

2010年，德国教授Serban Iordache提出了一种新颖的群体智能算法——顾问引导搜索（Consultant Guided Search，CGS）[21]~[24]算法。该算法产生的灵感来自于在群体内个体之间信息交流的直接性，以及在真实环境中，某人做出某种决定时，会

14

群体智能算法及其应用

向自己的顾问进行咨询，根据顾问的意见调整自己的决策。作为一种新颖的群体智能优化算法，CGS算法具有结构清晰、实现容易、参数设置简单等优点，为智能优化领域提供了新思想。在本章参考文献[21]中，作者对CGS算法的基本原理、参数设置、种群规模等问题进行了详细地论述，分析了该算法的优势和弱点，给出了应用该算法求解组合优化问题的模型，并与遗传算法等经典群体智能算法在求解精度、复杂度、运算时间等方面进行了对比。由于缺少严格的数学理论支持，该算法同样存在容易早熟，求解精度低等弱点。为了克服这些弱点，本章参考文献[22]中提出了一种引入局部搜索（Local Search）机制的改进CGS算法，新算法的局部搜索能力明显优于原始CGS，应用改进之后的CGS算法求解经典的TSP问题，取得了较好的求解效果。为了拓展CGS算法的应用领域，Serban Iordache教授在本章参考文献[23]中应用CGS算法求解了二次分配问题，对比其他相关算法，效果较好。在本章参考文献[24]中，作者应用CGS算法求解Job Shop Scheduling 问题，对比相关的算法，

CGS算法求解速度快，求解精度较高。

算法1.6 顾问引导算法（CGSA）

输入：种群规模为POP的群体，最大迭代次数itermax。 输出：最佳个体Xgbest(t)。

步骤1. 在解空间内随机产生n个虚拟人组成种群P。

步骤2. 参数初始化，迭代次数设为t，并设置所有个体p∈P的行为模式为“休假模式”。

步骤3. 遍历种群内的个体，执行如下子过程：

步骤3.1. 如果个体p∈P是休假模式，则创建策略，并更新当前最佳策略；

步骤3.2. 如果个体p∈P是普通模式，则选择种群内p'≠p作为自己的顾问，并根据当前最佳策略构建解决方案；如果构建的解决方案优于顾问的策略，则更新顾问的策略为当前解决方案，并且顾问的成功顾问次数加1。

步骤4. 更新个体的信誉值。 步骤5. 更新个体的行为模式。

步骤6. 不满足结束条件，则跳转到步骤3。 步骤7. 输出适应度最佳个体。

顾问引导搜索算法是以虚拟人群为基础的算法，在CGS中每个个体是一个虚拟人，可以同时作为客户和顾问。作为一名顾问，根据他的策略提供建议给客户。作为客户，通过顾问的策略来产生自己的解决方案。客户基于自己的个人偏好和顾问的信誉选择顾问，顾问k的信誉是通过公式（1.20）计算得到。 repuk=repuk(1−r)

（1.20）

第1章 群体智能算法概述

15

顾问个体每代的信誉都有一个衰减值，其中信誉衰减率r按照公式（1.21）计算。 sw⎛ r=r0⎜1+

2⎛sw⎞⎜

1+⎜⎟⎜⎝t⎠⎝

⎞⎟ ⎟⎟⎠（1.21）

公式（1.21）中，r0代表了客户在没有取得成功的情况下，最近w次迭代中排名靠前的顾问的信誉衰减率。参数sw影响着信誉衰减率，表示最近w次迭代排名靠具体计算如公式（1.22）前的顾问获得成功的次数。参数f的值通过参数kw计算获得，所示。

1⎞⎛1⎞⎛

f=⎜−1⎟⎜1−

wk⎟r⎝0⎠⎝w⎠（1.22）

顾问构建策略按照公式（1.23）计算得到。其中a是均匀分布在[0,1]的一个随机

变量,且a0∈[0,1],参数j是顾问下一步准备采取的方案。如果a≤a0，那么顾问选择所有方案di中最好的作为他的策略，否则可以采用轮盘赌方式选择方案，轮盘赌按照公式（1.24）来计算每个方案的概率，其中β是一个参数。

⎧argmin{di}if(a≤a0)

j=⎨

其他j⎩

(1/di)β pi=n

(1/di)β（1.23） （1.24）

∑

i=1

如果顾问被客户选中，即成为当前顾问，那么顾问会提供自己的策略给客户，客户获得顾问的策略后，紧接着构造自己的解决方案。选择方案如公式（1.25）所示。

if(v≠null)∧(q≤q0)⎧v

⎪

j=⎨argmin{di}if(v≠null)∧(q≤q0)∧(b≤b0)

⎪j其他⎩

（1.25）

其中v是顾问的建议，作为下一步采取的方案。q是均匀分布在[0,1]的一个随机变量,且q0(0≤q0≤1)，b是均匀分布在[0,1]的一个随机变量，且b0(0≤b0≤1)。否则，则采取公式（1.25）按轮盘赌方式来选择方案。

1.8 本 章 小 结

群体智能算法从诞生到现在经历了几十年的发展，产生了非常多的不同的算法，这些群体智能算法或模仿生命体的遗传行为、或模仿动物的觅食行为、或模仿动物的飞行行为等。每一个群体智能算法均具有自己的特色和独特的求解方

16

群体智能算法及其应用

式。基于协作、竞争机制，本章给出了群体智能算法的一般计算步骤和数学模型，并选择五个经典的群体智能算法：遗传算法、粒子群算法、差异演化算法、教—学优化算法和顾问引导搜索算法等进行了详细的介绍，讲解了它们的计算原理和求解步骤。

遗传算法开辟了群体智能的先河；粒子群算法是第一个通过模拟生物种群的协作、竞争行为实现目标求解的群体智能算法；建立在遗传算法基础之上，发展而来的差异演化算法，是目前求解连续函数优化问题效率最高的群体智能算法之一。最后所介绍的教—学优化算法和顾问引导搜索算法是近几年涌现出来的较优秀的群体智能算法。

参 考 文 献

[1] Holland J H. Outline for a logical theory of adaptive systems. Journal of Association for Computing

Machinery, 1962,9(3):297-314.

[2] Kennedy J, Eberhart R C,Shi Y. Swarm Intelligence. 2001.San Francisco:Morgan Kaufman

Publisher.

[3] Arabas J，Michalewicz Z,Mulawka J. A Genetic algorithm with varying population size.1994.Proc

of the 1st IEEE Int Conf on Evolutionary Copmputation.Orlando,Floria,USA：IEEE Press. [4] Hirotaka Itoh. The method of solving for travelling salesman problem using genetic algorithm with

immune adjustment mechanism [A].Traveling Salesman Problem, Theory and Applications[C]. Switzerland:Intech Press, 2010.97- 112.

[5] Abdelkader R F. An improved discrete PSO with GA operators for efficient QoS-multicast

routing[J]. International Journal of Hybrid Information Technology, 2011, 4(2): 23-38.

[6] Colorni A,Dorigo M,Maniezzo V,etal. Distributed optimization by ant colonies.1991,Proceedings

of the 1st European Conference on Artificial Life,134-142.

[7] Dorigo M,Maniezzo V,Colorni A. Ant system:optimization by a colony of cooperating agents. 1996,

IEEE Transaction on System,Man,and Cybernetics-Part B,26(1):29-41.

[8] Storn R and Price K. Differential evolution-a simple and efficient heuristic for global optimization

over continuous spaces[J]. Journal of Global Optimization,1997,11:341-359.

[9] Storn R and Price K. Differential evolution for multi-objective optimization[A]. Evolutionary

Computat ion[C], 2003, 4:8-12.

[10] J.Brest, S.Greiner, B.Boskovic, M.Mernik, V.Zumer. Self-Adapting Control Parameters in

Differential Evolution: A Comparative Study on Numerical Benchmark Problems. In:2006. Evolutionary Computation, IEEE Transactionson, Vol.10,no 6,pp.6-657,ISSN:10-778X.

第1章 群体智能算法概述

17

[11] Abbass H.. Self-adaptive pareto differetial evolution. In Proceedings of the IEEE 2002 Congress on

Evolutinary Computation,2002, 831-836.

[12] Mininno E，Neri F, Cupertino F，Naso D.Compact differential evolution. IEEE Transactions on

Evolutionary Computatio,2011,(151):32-54.

[13] 王凌, 刘波.微粒群优化与调度算法. 北京:清华大学出版社, 2008.

[14] 肖文显，刘震.一种融合反向学习和量子优化的粒子群算法. 微电子学与计算机,2013,30(6):

126-130.

[15] Kennedy J,Eberhart RC. A discrete binary version of the particle swarm algorithm. In:Proceedings

of the World Multiconference on Systemics,Cybernetics and Informatics 1997. Piscataway, NJ: IEEE Service Center, 1997. 4104-4109.

[16] 郭文忠，陈国龙.离散粒子群优化算法及其应用.北京：清华大学出版社,2012.

[17] Rao R V, Savsani V J, Vakharia D P. Teaching-learning-based optimization: a novel method for

constrained mechanical design optimization problems.Computer-Aided Design,2011, 43(3): 303-315．

[18] Rao R V, Savsani V J, Vakharia D P. Teaching-learning-based optimization: an optimization

method for continuous non- linear largescale problems. Information Sciences, 2012, 183(1): 1-15. [19] Rao R V, Savsani V J, Balic J. Teaching-learning-based optimization algorithm for unconstrained

and constrained real parameter optimization problems. Engineering Optimization, 2012,44 (2): 1447-1462．

[20] Rao R V, Savsani V J. Mechanical design optimization using advanced optimization techniques.

London: Springer-Verlag, 2012

[21] Serban Iordache . Consultant-Guided Search-A New Metaheuristic for Combinatorial Optimization

Problems. GECCO, 2010: 225-232.

[22] Serban Iordache.Consultant-Guided Search Algorithms with Local Search for the Traveling

Salesman Problem[C]. PPSN, 2010:81-90.

[23] Serban Iordache. Consultant-Guided Search Algorithms for the Quadratic Assignment Problem.

LNCS, 2010: 148-159.

[24] D.Deepanandhini,T.Amudha. Solving Job Shop Scheduling Problems With Consultant-Guided

Search Algorithms. India.University of Bahadier, 2013