粒子群算法英文文献

‘壹’ 什么是粒子群算法

粒子群算法介绍（摘自http://blog.sina.com.cn/newtech）
优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题. 为了解决各种各样的优化问题,人们提出了许多优化算法,比较着名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度. 爬山法精度较高,但是易于陷入局部极小. 遗传算法属于进化算法( Evolutionary Algorithms) 的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子:选择、交叉和变异. 但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.1995 年Eberhart 博士和kennedy 博士提出了一种新的算法;粒子群优化(Partical Swarm Optimization -PSO) 算法 . 这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性.

粒子群优化(Partical Swarm Optimization - PSO) 算法是近年来发展起来的一种新的进化算法( Evolu2tionary Algorithm - EA) .PSO 算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质. 但是它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作. 它通过追随当前搜索到的最优值来寻找全局最优 .

粒子群算法

1. 引言

粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，有Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究

PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。详细的步骤以后的章节介绍

同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域

2. 背景: 人工生命

"人工生命"是来研究具有某些生命基本特征的人工系统. 人工生命包括两方面的内容

1. 研究如何利用计算技术研究生物现象
2. 研究如何利用生物技术研究计算问题

我们现在关注的是第二部分的内容. 现在已经有很多源于生物现象的计算技巧. 例如, 人工神经网络是简化的大脑模型. 遗传算法是模拟基因进化过程的.

现在我们讨论另一种生物系统- 社会系统. 更确切的是, 在由简单个体组成的群落与环境以及个体之间的互动行为. 也可称做"群智能"(swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为

例如floys 和 boids, 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计.

在计算智能(computational intelligence)领域有两种基于群智能的算法. 蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟. 已经成功运用在很多离散优化问题上.

粒子群优化算法(PSO) 也是起源对简单社会系统的模拟. 最初设想是模拟鸟群觅食的过程. 但后来发现PSO是一种很好的优化工具.

3. 算法介绍

如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索

PSO 初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest. 另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。

在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置

v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = persent[] + v[] (b)

v[] 是粒子的速度, persent[] 是当前粒子的位置. pbest[] and gbest[] 如前定义 rand () 是介于（0， 1）之间的随机数. c1, c2 是学习因子. 通常 c1 = c2 = 2.

程序的伪代码如下

For each particle
____Initialize particle
END

Do
____For each particle
________Calculate fitness value
________If the fitness value is better than the best fitness value (pBest) in history
____________set current value as the new pBest
____End

____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained

在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax

4. 遗传算法和 PSO 的比较

大多数演化计算技术都是用同样的过程
1. 种群随机初始化
2. 对种群内的每一个个体计算适应值(fitness value).适应值与最优解的距离直接有关
3. 种群根据适应值进行复制
4. 如果终止条件满足的话，就停止，否则转步骤2

从以上步骤，我们可以看到PSO和GA有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解

但是，PSO 没有遗传操作如交叉(crossover)和变异(mutation). 而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。

与遗传算法比较, PSO 的信息共享机制是很不同的. 在遗传算法中，染色体(chromosomes) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动. 在PSO中, 只有gBest (or lBest) 给出信息给其他的粒子，这是单向的信息流动. 整个搜索更新过程是跟随当前最优解的过程. 与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解

5. 人工神经网络 和 PSO

人工神经网络(ANN)是模拟大脑分析过程的简单数学模型，反向转播算法是最流行的神经网络训练算法。进来也有很多研究开始利用演化计算(evolutionary computation)技术来研究人工神经网络的各个方面。

演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网络拓扑结构，传递函数)，网络学习算法。

不过大多数这方面的工作都集中在网络连接权重，和网络拓扑结构上。在GA中，网络权重和/或拓扑结构一般编码为染色体(Chromosome)，适应函数(fitness function)的选择一般根据研究目的确定。例如在分类问题中，错误分类的比率可以用来作为适应值

演化计算的优势在于可以处理一些传统方法不能处理的例子例如不可导的节点传递函数或者没有梯度信息存在。但是缺点在于：在某些问题上性能并不是特别好。2. 网络权重的编码而且遗传算子的选择有时比较麻烦

最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。研究表明PSO 是一种很有潜力的神经网络算法。PSO速度比较快而且可以得到比较好的结果。而且还没有遗传算法碰到的问题

这里用一个简单的例子说明PSO训练神经网络的过程。这个例子使用分类问题的基准函数(Benchmark function)IRIS数据集。(Iris 是一种鸢尾属植物) 在数据记录中，每组数据包含Iris花的四种属性：萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有50组数据. 这样总共有150组数据或模式。

我们用3层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层有4个节点，输出层有3个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定隐含层有6个节点。我们也可以训练神经网络中其他的参数。不过这里我们只是来确定网络权重。粒子就表示神经网络的一组权重，应该是4*6+6*3=42个参数。权重的范围设定为[-100，100] (这只是一个例子，在实际情况中可能需要试验调整).在完成编码以后，我们需要确定适应函数。对于分类问题，我们把所有的数据送入神经网络，网络的权重有粒子的参数决定。然后记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利用PSO来训练神经网络来获得尽可能低的错误分类数目。PSO本身并没有很多的参数需要调整。所以在实验中只需要调整隐含层的节点数目和权重的范围以取得较好的分类效果。

6. PSO的参数设置

从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤: 问题解的编码和适应度函数
PSO的一个优势就是采用实数编码, 不需要像遗传算法一样是二进制编码(或者采用针对实数的遗传操作.例如对于问题 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接编码为 (x1, x2, x3), 而适应度函数就是f(x). 接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程, 中止条件一般为设置为达到最大循环数或者最小错误

PSO中并没有许多需要调节的参数,下面列出了这些参数以及经验设置

粒子数: 一般取 20 – 40. 其实对于大部分的问题10个粒子已经足够可以取得好的结果, 不过对于比较难的问题或者特定类别的问题, 粒子数可以取到100 或 200

粒子的长度: 这是由优化问题决定, 就是问题解的长度

粒子的范围: 由优化问题决定,每一维可是设定不同的范围

Vmax: 最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如上面的例子里,粒子 (x1, x2, x3) x1 属于 [-10, 10], 那么 Vmax 的大小就是 20

学习因子: c1 和 c2 通常等于 2. 不过在文献中也有其他的取值. 但是一般 c1 等于 c2 并且范围在0和4之间

中止条件: 最大循环数以及最小错误要求. 例如, 在上面的神经网络训练例子中, 最小错误可以设定为1个错误分类, 最大循环设定为2000, 这个中止条件由具体的问题确定.

全局PSO和局部PSO: 我们介绍了两种版本的粒子群优化算法: 全局版和局部版. 前者速度快不过有时会陷入局部最优. 后者收敛速度慢一点不过很难陷入局部最优. 在实际应用中, 可以先用全局PSO找到大致的结果,再有局部PSO进行搜索.

另外的一个参数是惯性权重, 由Shi 和Eberhart提出, 有兴趣的可以参考他们1998年的论文(题目: A modified particle swarm optimizer)

‘贰’ 高分急求！ 关于 粒子群解决车间调度的英文文献 ！ ！先50 满意再加50

基于动态双种群粒子群
算法的柔性工作车间调度
摘 要: 针对标准粒子群优化算法存在易陷入局部最优点的缺点,提出了一种基于动态双种群的粒子群
优化算法(DPSO) ·DPSO 算法将种群划分成两个种群规模随进化过程不断变化的子种群,两个子种群分别采
用不同的学习策略进行进化,并在进化过程中相互交换信息·该算法提高了全局寻优能力,有效地避免了早熟
收敛的发生·将以DPSO 算法为基础的排序算法和启发式分配算法(HA) 相结合形成了解决柔性工作车间调
度问题的新方法(DPSO2HA) ·通过对算例的研究和与其他方法的比较表明,该方法是有效可行的·
A Dynamic Double2Population Particle Swarm Optimization
Algorithm for Flexible Job2Shop Scheling
L I Dan , GA O L i2qun , MA Jia , L I Yang
( School of Information Science & Engineering , Northeastern University , Shenyang 110004 , China.
Correspondent : L I Dan , E2mail : lidanneu @163. com)
Abstract : A dynamic double2population particle swarm optimization ( DPSO) algorithm is
presented to solve the problem that the standard PSO algorithm is easy to fall into a locally
optimized point , where the population is divided into two sub2populations varying with their own
evolutionary learning st rategies and the information exchange between them. The algorithm thus
improves it s solvability for global optimization to avoid effectively the precocious convergence.
Then , an ordering algorithm based on DPSO is integrated with the heuristic assignation ( HA)
algorithm to form a new algorithm DPSO2HA so as to solve the flexible job2shop scheling
problem (FJ SP) . The new algorithm is applied to a set of benchmark problems as instances , and
the simulation result s show the effectiveness and feasibility of DPSO2HA algorithm for the flexible
job2shop scheling.
Key words : double population ; PSO(particle swarm optimization) ; learning st rategy ; DPSO2HA
algorithm; flexible job2shop scheling
柔性工作车间调度问题( flexible job2shop
scheling problem , FJ SP) 是经典工作车间调度
问题的一个延伸,它允许工件被给定的有处理能
力的任何机器处理·柔性工作车间调度问题由于
减少了机器约束,扩大了可行解的搜索范围,提高
了问题的复杂性,所以与传统工作车间调度问题
相比更加接近实际生产环境的模拟·
相对于传统工作车间调度,关于柔性工作车
间调度问题的文献还比较少·目前所采用的方法
主要有分枝定界法[1 ] 、多项式算法、分等级法和
传统进化算法( EA) [2 ]等,在近几年中,很多研究
者使用禁忌搜索和遗传算法对FJ SP 进行求
解[3 - 4 ]
·
本文提出一个新的求解柔性工作车间调度问
题的方法———基于动态双种群粒子群优化的分阶
段方法·本方法的主要思想是:将柔性工作车间调
度问题分解成两个有时间顺序的子问题来考虑,
首先考虑工序排序子问题,在获得可行的排序后
再考虑机器分配子问题·本文首先利用动态双种
群粒子群优化算法为工序进行排序,使其满足约
束条件从而获得一个可行解,然后利用文中所提
出的分配算法为每道工序分配合适的机器,形成
可行的调度方案·本文所考虑的优化目标是最小
化最大完工时间(makespan) ·
1 柔性工作车间调度问题描述
柔性工作车间调度问题可描述为将n 个加工
顺序不同的工件在m 台机器上加工完成·每个工
件使用同一台机器可以多于一次,每道工序的加工
过程不允许中断·机器的集合用U 来表示,每个工
件J 包含nj 道工序,各工序之间的顺序不允许改
变·Oij表示工件J 的第i 道工序,它可以在有处理
能力的任何一台机器上被加工·Ti , j , k表示工序Oij
用机器Mk 来加工所需要的时间, 可用集合T =
{ Ti , j , k| 1 ≤j ≤N ;1 ≤i ≤nj ;1 ≤k ≤M}表示, N 为
工件的数量, M 为机器的数量·例如表1 即是一个
实际的柔性工作车间调度加工时间表·
表1 柔性工作车间调度加工时间表
Table 1 Proce ssing schele for FJ SP
工件工序M1 M2 M3 M4
J1
O1 ,1 1 3 4 1
O2 ,1 3 8 2 1
O3 ,1 3 5 4 7
J2
O1 ,2 4 1 1 4
O2 ,2 2 3 9 3
O3 ,2 9 1 2 2
J3
O1 ,3 8 6 3 5
O2 ,3 4 5 8 1
在柔性工作车间调度问题中, 应满足以下假
设:
(1) 所有的机器在时间t = 0 时都是可以使
用的,每个工件都可以在t = 0 时开始加工;
(2) 在给定的时间内, 一台机器只能加工一
道工序,直到加工完此工序后方可加工其他工序,
这就是所谓的资源约束;
(3) 对于每个工件的各道工序只能按照事先
给定的顺序加工,这就是所谓的优先约束·
对于每一道工序Oi , j , 本文用ri , j来表示其
最早开始加工时间, 对不同的工序分别用下式进
行计算:
ri , j =
0 , 1 ≤ j ≤ N ;
ri - 1 , j +γi , j , 2 ≤ i ≤ nj ,1 ≤ j ≤ N ·
式中,γi , j = mink ( Ti , j , k) ,1 ≤i ≤nj ;1 ≤j ≤N·
对于FJ SP 来说一般存在两个难题:第一个
是如何为每道工序选择合适的机器;第二个是如
何计算每道工序的开始加工时间t i , j和结束加工
时间tf i , j·
本文所要研究的FJ SP 的优化目标是,在满
足上述优先约束和资源约束的条件下寻找最优调
度方案,使全部工件的最大完工时间(Makespan)
最短·
2 排序算法———动态双种群粒子群
优化算法
2. 1 标准粒子群优化算法
粒子群优化(particle swarm optimization ,简
称PSO) 算法是由Kennedy 和Eberhart 在1995
年提出·在PSO 系统中,每个潜在解被称为一个
粒子,多个粒子共存、合作寻优,每个粒子根据它
自身的经验在目标搜索空间中向更好的位置飞
行,搜索最优解·由文献[ 5 ]可知,每个粒子根据如
下的公式来更新自己的速度和在解空间的位置·
v ( t +1)
id = w v ( t)
id + c1 r1 p ( t)
id - x ( t)
id +
c2 r2 p ( t)
gd - x ( t)
id , (1)
x ( t +1)
id = x ( t)
id + v ( t +1)
id · (2)
其中, d = 1 ,2 , ⋯, n , i = 1 ,2 , ⋯, m , m 为种群规
模; t 为当前进化代数; r1 和r2 为均匀分布于[0 ,
1]的随机数; w 为惯性权重, 其值由下式来确
定[6 ] :
w = w max -
w max - w min
itermax
×iter · (3)
式中, w max , w min分别是w 的最大值和最小值;
iter ,itermax分别是当前迭代次数和最大迭代次数·
2. 2 粒子群优化算法的学习策略
由标准粒子群优化算法可知,粒子通过跟踪
自己迄今为止所找到的最优解和种群迄今为止所
找到最优解这两个极值来更新自己的速度,从而
更新自己的位置·这种行为也可以理解为,粒子在
借鉴自身和整个群体所取得的成功经验,通过对
以往的成功经验的学习获得有用的信息,指导自
己下一步的行动策略·但人们也常说“失败乃成功
之母”“, 吃一堑,长一智”,可见从一些失败的尝试
中也可以获得有用的信息,基于这一点,提出了新
的粒子群优化算法学习策略,这就是从以往的失
败中获得有价值的信息,使粒子远离粒子本身和
整个群体所找到的最差的位置,从而更新粒子的
速度和位置·粒子在搜索过程中的失败可以表现
为搜索到的具有较差适应值的位置,记第i 个粒
子迄今为止搜索到的最差位置为si = ( si1 , si2 ,
⋯, sin) ,整个粒子群迄今为止搜索到的最差位置
为sg = ( sg1 , sg2 , ⋯, sg n) ,则第i 个粒子的速度和
位置更新公式如下:
v ( t +1)
id = w v ( t)
id + c1 r1 x ( t)
id - s ( t)
id +
c2 r2 x ( t)
id - s ( t)
gd , (4)
x ( t +1)
id = x ( t)
id + v ( t +1)
id · (5)
如果只是利用上述的位置和速度更新公式更
新粒子,也就是说只是从失败中获取经验,这与实
际经验不符·一般来说,还是更多地从成功的经历
中获取信息,而从失败的经历中获得相对少的信
息,基于这一点本文的算法同时从成功和失败的
经历中获取信息来更新粒子·
2. 3 动态双种群粒子群优化算法
由上面的叙述可以知道粒子群中的粒子可以
按照不同的学习策略进行学习,对速度和位置作
出更新·所以本文将一个种群分成两个子种群,每
个子种群选用不同的学习策略,即第一个子种群
中的粒子选用从成功经历中获得学习信息的策
略,更新自己;第二个子种群中的粒子选用从失败
的经历中获得学习信息的策略进行进化·本文可
以设置一个比例系数ρ来控制两个子种群中粒
子的个数·
ρ =
m1
m2
, m1 + m2 = m · (6)
式中, m 为粒子群中的粒子总数; m1 为第一个子
种群中的粒子个数; m2 为第二个子种群中的粒
子个数·
为了使每个粒子都能从自身和群体的经历中
获得充分的学习, 本文规定两个子种群中的粒子
是不断变化的, 即每隔一定的代数后将整个种群
按照比例系数ρ重新随机划分成两个子种群·从
粒子群优化算法的进化过程中知道在优化的初期
粒子的位置比较分散, 得到较优值和较差值的机
会相差不多,所以此时采用上述两种不同学习策
略的粒子的个数应大致相等·在优化搜索的后期
粒子将聚集在最优值的附近,这时将很难出现比
历史最差值更差的值了,第二个子种群将从失败
经历中得不到太多的有价值的信息·此时第二个
子种群中的粒子数应该远远小于第一个子种群中
的粒子个数,直至完全采用跟踪最优值来更新粒
子,即第二个子种群消亡·基于上述原因将ρ设
为一个线性变化的量,其值由下式确定:
ρ = ρmax -
ρmax - ρmin
018 ×itermax
×iterc · (7)
式中,ρmax和ρmin分别是ρ的最大值和最小值;
iterc 和itermax分别是种群重新划分时的进化代数
和最大进化代数·
动态双种群粒子群优化算法的实现步骤如
下:
(1) 设PSO 种群规模为m , 加速常数为c1
和c2 ,惯性权重的最大值和最小值为w max , w min ,
比例系数ρ的最大值和最小值为ρmax ,ρmin ,种群
重新划分代数iterc ,最大进化代数为Tmax·将当前
进化代数置为t = 1 ;
(2) 在解空间中初始化粒子的速度和位置;
(3) 将种群按照比例系数ρ划分为两个子种
群;
(4) 按式(3) 更新惯性权重w , 按式(7) 更新
比例系数ρ, 第一个子种群按式(1) 和(2) 更新粒
子速度和位置,第二个子种群按式(4) 和(5) 更新
子种群中的粒子,从而产生新种群Xt ;
(5) 评价种群Xt·将第i 个粒子当前点适应
值与该粒子迄今找到的最优位置pi (最差位置
si) 的适应值进行比较, 若更优(差) , 则更新pi
( si) ,否则保持pi ( si) 不变,再与种群迄今找到的
最优位置pg (最差位置sg) 的适应值进行比较,若
更优(差) ,则更新pg ( sg) ;否则保持pg ( sg) 不变;
(6) 检查是否满足寻优结束条件, 若满足则
结束寻优, 求出最优解; 否则, 置t = t + 1 , 转至
(3) ;结束条件为寻优达到最大进化代数Tmax·
2. 4 基于动态双种群粒子群优化算法的工序排序
2. 4. 1 粒子的编码和解码
根据第1 节对柔性工作车间调度问题的描
述,本文定义所有工件的总工序数L = 6n
j =1
nj ,把
一个粒子表示为一个L 维的向量·对所有工序进
行连续编号,即为每道工序指定一个固定的编号·
例如可以对表1 所给出的例子中的工序进行编
号,如表2 所示,则粒子的位置向量x [ L ]就是由
一组连续的自然数组成的L 维的向量,自然数的
顺序决定了工序调度的顺序·xi = [1 ,7 ,2 ,4 ,8 ,3 ,
5 ,6 ]就表示了一个满足优先约束的可行的工序排
序·
表2 工序编号
Table 2 Serial numbers of operations
工序O1 ,1 O2 ,1 O3 ,1 O1 ,2 O2 ,2 O3 ,2 O1 ,3 O2 ,3
编号1 2 3 4 5 6 7 8
2. 4. 2 位置向量和速度向量的更新
对每个粒子, 粒子的速度向量可以用v [ L ]
表示·按照上面所述的更新公式对x [ L ] , v [ L ]
进行更新·由于粒子群优化算法经常用在连续空
间上,而柔性工作车间调度问题为整数规划问题
而且有工序先后顺序约束,所以将粒子群算法用
于柔性工作车间调度问题时,在速度和位置更新
方式上要做如下的修改:令粒子i 的当前的位置
为xi = [1 , 7 , 2 , 4 , 8 , 3 , 5 , 6 ] , 在经过一次迭代以
后位置向量变为xi = [ 2. 5 , 6. 7 , 3. 6 , 5. 9 , 8. 5 ,
112 ,4. 1 ,7. 6 ]·位置向量里存放的是工序的编号,
很明显不能为小数, 本文对迭代后的位置向量进
行如下的处理:将更新后的位置向量中各分量的
值按照由小到大的顺序进行排列, 并为其进行重
新编号:1. 2 (1) < 2. 5 (2) < 3. 6 (3) < 4. 1 (4) < 5. 9
(5) < 6. 7 (6) < 7. 6 (7) < 8. 5 (8) ,式中括号内的数
字为该分量的编号, 然后位置向量中各分量用其
获得的相应的编号代替·例如,第一个分量2. 5 用
编号2 代替,第二个分量6. 7 用编号6 代替等等,
此时位置向量变为xi = [2 , 6 , 3 , 5 , 8 , 1 , 4 , 7 ]·但
是这个工序排序不满足优先约束,还要对其进行
调整,使其满足约束条件·例如第一个分量2 代表
的是工序O21 ,第6 个分量1 代表的是工序O11 ,
工序O21应在工序O11之后进行加工, 所以要对
其进行调整·调整的方法为:对属于同一个工件的
工序调换其相应先后位置使其满足约束, 对每个
工件都做相似的处理, 则可以得到满足优先级约
束的位置向量: xi = [1 ,4 ,2 ,5 ,7 ,3 ,6 ,8 ]·
3 启发式分配算法
通过上一节介绍的排序算法本文可以获得一
个满足工序优先约束的可行的工序序列·这一节
通过一个启发式算法为这一工序序列中的每一工
序分配一台合适的机器对其进行加工·
本文所采用的分配算法的主要思想是:选择
一台能使本道工序获得最小完工时间的机器分配
给待加工的工序·可以用如下公式表示选择机器
Mk 分配给待加工的工序以使本道工序的完工时
间最短:
tf i , j = min k ( ri , j + Ti , j , k) ,
ri , j = max ( rpfk , ropf) ·
式中, tf i , j 为工序Oi , j 的完工时间; ri , j 为工序的
开始加工时间; Ti , j , k为工序用机器k 加工消耗的
时间; rpfk为机器Mk 当前状态下所加工的最后一
个工件的完工时间; ropf为待加工工序紧前工序的
完工时间·
利用排序算法和分配算法就可以获得一个满
足优先约束和资源约束的可行的调度方案, 并且
利用分配算法还可以得到目标函数———全部工件
的最大完工时间的值·
将前面介绍的排序算法和分配算法综合起来
便形成本文所采用的处理柔性工作车间调度优化
问题的方法,记为DPSO2HA·该方法将柔性工作
车间调度问题分解为两个子问题———排序问题和
分配问题,在每一次迭代中首先通过动态双种群
粒子群算法获得一个可行的工序序列, 然后利用
分配算法给该序列分配合适的机器并计算目标函
数值,直至达到最大进化代数·
4 算例仿真
4. 1 仿真研究1
本文选用文献[ 7 ]中的一个10 ×10 (10 个工
件,10 台机器) ,30 道工序的柔性工作车间调度问
题来计算最大完工时间·实验参数如下:粒子群的
种群规模为m = 30 , c1 = c2 = 2 ,ρmax = 015 ,ρmin =
0 ,每隔5 代重新划分种群,最大迭代次数Tmax =
150·
实验中采用本文所提出的算法运行10 次,和
传统的GA 方法、文献[8 ]中采用的MSA 算法相
比较,比较结果如表3 所示·
表3 实验结果比较
Table 3 Comparison of te sting re sults
方 法最优值平均值标准偏差
GA 8 11. 5 2. 67
MSA 7 7. 9 0. 97
DPSO2HA 7 7. 1 0. 32
从表3 中可以看出DPSO2HA 求得的平均值
和标准偏差都明显优于GA 和VEGA , 这说明
DPSO2HA 的精度与稳定性明显优于GA 和
VEGA 算法·实验中所获得的一个较优的调度方
案的甘特图如图1 所示·图中方框内的数字“i . j”
表示第j 个工件的第i 道工序·,
（不好意思，图粘贴不下来，要不你告我邮箱）
图1 柔性工作车间调度优化结果
Fig. 1 Optimization solution to the problem
10 ×10 with 30 operations
4. 2 仿真研究2
为了进一步对本文提出的算法的性能加以验
证,选用文献[ 9 ]中所给出的实验数据,利用本文
提出的算法进行求解,并将调度结果与文献[ 9 ]及
文献[ 10 ]中所提算法的调度结果加以比较·比较
结果如表4 所示·
表4 不同方法的调度结果比较
Table 4 Comparison of different scheling re sults
算例描述Brandimarte GENACE DPSO2HA
MK1 10 ×6 42 41 40
MK2 10 ×6 32 29 28
MK4 15 ×8 81 67 61
MK5 15 ×4 186 176 173
MK6 10 ×15 86 68 62
MK7 20 ×5 157 148 141
MK8 20 ×10 523 523 523
MK9 20 ×10 369 328 307
MK10 20 ×15 296 231 207
由上述的比较结果可以看出,本文所提出的
DPSO2HA 方法对上述算例的求解结果较另外两
种方法有了较大的提高·
5 结 论
本文提出了一种动态双种群粒子群优化算法
(DPSO) ·DPSO 将种群划分成两个种群规模随进
化过程不断变化的子种群,两个子种群分别采用
不同的学习策略进行进化,并在进化过程中相互
交换信息·该算法在保持PSO 算法高效简单的基
础上提高了全局寻优能力·将以DPSO 算法为基
础的排序算法和启发式分配算法相结合形成了解
决柔性工作车间调度问题的新方法·通过对算例
的研究和与其他方法的比较表明,该方法是有效
可行的·
参考文献:
[ 1 ] Carlier J , Pinson E. An algorithm for solving the job2shop
problem[J ] . Management Science , 1989 ,35 (2) :164 - 176.
[ 2 ] Reynolds R G. An introction to cultural algorithms[ C] ‖
Proceedings of the Third Annual Conference on Evolutionary
Programming. River Edge : World Scientific , 1994 : 131 -
139.
[ 3 ] Mastrolilli M , Gambardella L M. Effective neighborhood
functions for the flexible job shop problem[ J ] . Journal of
Scheling , 2002 ,3 (1) :3 - 20.
[ 4 ] Kacem I , Hammadi S , Borne P. Pareto2optimality approach
for flexible job2shop scheling problems : hybridization of
evolutionary algorithms and fuzzy logic[J ] . Mathematics and
Computers in Simulation , 2002 ,60 (3) :245 - 276.
[ 5 ] Kennedy J , Eberhart R. Particle swarm optimization [ C] ‖
Proceedings of IEEE International Conference on Neural
Networks. Perth : IEEE Press , 1995 :1942 - 1948.
[ 6 ] Shi Y, Eberhart R C. Empirical study of particle swarm
optimization [ C ] ‖Proceedings of the 1999 Congress on
Evolutionary Computation. Washington , 1999 : 1945 -
1950.
[ 7 ] Xia WJ , Wu Z M. An effective hybrid optimization approach
for multi2objective flexible job2shop scheling problems[J ] .
Computers & Inst rial Engineering , 2005 ,48 (2) :409 -
425.
[ 8 ] Najid N M , Stephane D P , Zaidat A. A modified simulated
annealing method for flexible job shop scheling problem[C]
‖Proceedings of the IEEE International Conference on
Systems , Man and Cybernetics. Hammamet : IEEE Press ,
2002 :89 - 94.
[ 9 ] Brandimarte P. Routing and scheling in a flexible job shop
by tabu search[J ] . A nnals of Operations Research , 1993 ,41
(3) :158 - 183.
[ 10 ] Ho N B , Tay J C. GENACE: an efficient cultural algorithm
for solving the flexible job2shop problem[C] ‖Proceedings of
the IEEE Congress on Evolutionary Computation. Portland :
IEEE Press , 2004 :1759 - 1766.

（do you know）

‘叁’ 粒子群算法的引言

优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题. 为了解决各种各样的优化问题,人们提出了许多优化算法,比较着名的有爬山法、遗传算法、神经网络算法等. 一是要求寻找全局最优点,
二是要求有较高的收敛速度. 近年来，一些学者将PSO算法推广到约束优化问题，其关键在于如何处理好约束，即解的可行性。如果约束处理的不好，其优化的结果往往会出现不能够收敛和结果是空集的状况。基于PSO算法的约束优化工作主要分为两类：
（1）罚函数法。罚函数的目的是将约束优化问题转化成无约束优化问题。
（2）将粒子群的搜索范围都限制在条件约束簇内，即在可行解范围内寻优。
根据文献介绍，Parsopoulos等采用罚函数法，利用非固定多段映射函数对约束优化问题进行转化，再利用PSO算法求解转化后问题，仿真结果显示PSO算法相对遗传算法更具有优越性，但其罚函数的设计过于复杂，不利于求解；Hu等采用可行解保留政策处理约束，即一方面更新存储中所有粒子时仅保留可行解，另一方面在初始化阶段所有粒子均从可行解空间取值，然而初始可行解空间对于许多问题是很难确定的；Ray等提出了具有多层信息共享策略的粒子群原理来处理约束，根据约束矩阵采用多层Pareto排序机制来产生优良粒子，进而用一些优良的粒子来决定其余个体的搜索方向。
但是，目前有关运用PSO算法方便实用地处理多约束目标优化问题的理论成果还不多。处理多约束优化问题的方法有很多，但用PSO算法处理此类问题目前技术并不成熟，这里就不介绍了。 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，1995 年由Eberhart 博士和kennedy 博士提出，源于对鸟群捕食的行为研究 。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。粒子群算法在对动物集群活动行为观察基础上，利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得最优解。
PSO同遗传算法类似，是一种基于迭代的优化算法。系统初始化为一组随机解，通过迭代搜寻最优值。但是它没有遗传算法用的交叉(crossover)以及变异(mutation)，而是粒子在解空间追随最优的粒子进行搜索。同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。

‘肆’ 【PSO-LSTM】基于PSO优化LSTM网络的电力负荷预测（Python代码实现）

PSOLSTM模型是基于粒子群优化算法优化长短期记忆网络参数，用于电力负荷预测的一种有效方法。以下是其Python代码实现的核心要点：

1. 导入必要的库：

   • 需要导入如numpy、pandas用于数据处理，tensorflow或keras用于构建LSTM网络，以及sklearn中的评估函数等。

2. 数据预处理：

   • 加载电力负荷数据，并进行归一化、划分训练集和测试集等操作。

3. 构建LSTM网络：

   • 使用keras.Sequential构建LSTM模型，设置输入层、LSTM层、全连接层和输出层。
   • LSTM层的神经元数量、学习率等作为待优化的参数。

4. 定义PSO算法：

   • 实现粒子群优化算法，包括初始化粒子位置、速度，以及适应度函数。
   • 通过迭代更新粒子的位置和速度，寻找最优的LSTM超参数。

5. 训练LSTM网络：

   • 使用PSO找到的最优超参数训练LSTM网络。
   • 记录训练过程中的损失值和准确率等指标。

6. 预测与评估：

   • 使用训练好的LSTM网络对测试集进行预测。
   • 计算并输出预测结果的误差指标。

7. 可视化结果：

   • 可视化实际负荷与预测负荷的对比图，以及PSO优化过程中的适应度值变化图等。

由于具体的Python代码实现涉及较多细节和库函数调用，这里不给出完整的代码示例。但可以根据上述步骤，结合tensorflow、keras和sklearn等库的文档，逐步编写代码实现PSOLSTM模型。同时，可以参考相关文献和开源项目中的代码，以获取更具体的实现细节和技巧。