1. matlab车间调度遗传算法中随机产生初始种群的问题，，求教
P应该是一个大小为n的数组，P(j)表示数组第j个元素；eps在matalab中叫做“浮点零”，也叫是matalab中的零值。用手厅特殊的MATLAB数eps来代替在一个数组中的零元素，eps近似为2.2e-16。不是最小的数，而是系统能准确表示的浮点轮薯禅数的精度；rand是matlab中的随机数，（0，1）间。
X(i,j)=1+(P(j)-eps)*rand;表示给矩阵X的第i行第j列的元素赋值，值为[1，P(j))范围内的随机数腊尘。
我解释的您还满意不？能在采纳时加点悬赏分吗？谢谢
2. 高分急求！ 关于 粒子群解决车间调度的英文文献 ！ ！先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）
3. 遗传算法-总结
最近在做遗传算法的项目，简单记录一下。
遗传算法是模拟自然界生物进化机制的一种算法，在寻优过程中有用的保留无用的去除。包括3个基本的遗传算子：选择（selection）、交叉（crossover）和变异（mutation）。遗传操作的效果与上述3个遗传算子所取的操作概率、编码方法、群体大小、初始群体，以及适应度函数的设定密切相关。
1、种群初始化
popsize 种群大小，一般为20-100，太小会降低群体的多样性，导致早熟；较大会影响运行效率；迭代次数一般100-500；交叉概率：0.4-0.99，太小会破坏群体的优良模式；变异概率：0.001-0.1，太大搜索趋于随机。编码包括实数编码和二进制编码，可以参考遗传算法的几个经典问题，TSP、背包问题、车间调度问题。
2、选择
目的是把优化个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代，我大部分采用了轮盘赌的方法。具体可参考 http://my.oschina.net/u/1412321/blog/192454 轮盘赌方法各个个体的选择概率和其适应值成比例，个体适应值越大，被选择的概率也越高，反之亦然。在实际问题中，经常需要最小值作为最优解，有以下几种方法进行转换
a、0-1之间的数据，可以用1-该数值，则最小值与最大值互换；
b、 求倒数；
c、求相反数；
以上几种方法均可以将最大值变为最小值，最小值变为最大值，便于利用轮盘赌选择最优个体，根据实际情况来确定。
3、交叉
交叉即将两个父代个体的部分结构加以替换重组而生成新个体的操作，通过交叉，遗传算法的搜索能力得以飞跃提高。根据编码方法的不同，可以有以下的算法：
a、实值重组
离散重组、中间重组、线性重组、扩展线性重组
b、二进制交叉
单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉
4、变异
基本步骤：对群中所有个体以事先设定的变异概率判断是否进行变异；对进行变异的个体随机选择变异位进行变异。根据编码表示方法的不同，有实值变异和二进制变异
变异的目的：
a、使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部搜索能力可以加速向最优解收敛。显然该情况下变异概率应取较小值，否则接近最优解的积木块会因为变异遭到破坏。
b、使遗传算法可维持多样性，以防止未成熟收敛现象。此时收敛概率应取较大值。
变异概率一般取0.001-0.1。
5、终止条件
当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设代数一般为100-500。
6、其它
多变量：将多个变量依次连接
多目标：一种方法是转化为单目标，例如按大小进行排序，根据排序和进行选择，可以参考 https://blog.csdn.net/paulfeng20171114/article/details/82454310