粒子群优化算法研究

粒子群优化算法研究

0组合优化问题的提出及求解颗粒优化算法（pso）是基于集体智能理论的优化算法。这一算法由金融家和艾尔霍尔于1995年提出，并已由许多科学家进行了广泛的研究。现在，它已成功应用于优化领域，如函数优化、神经网络训练、多目标优化和模糊控制。传统的PSO适合于处理连续优化问题,在复杂的组合优化问题上的应用相当有限。目前已有学者利用PSO来解决旅行商问题和单机调度问题,但所采用的方法都是先通过映射技术把离散问题转化为连续问题,然后再利用PSO对连续问题进行优化。这种优化从本质上讲还是在处理连续问题,并没有实质性的突破。作业车间调度问题(Job-shopSchedulingProblem,JSP)是一类典型的组合优化问题,它可以简单描述为:n个工件在m台机器上加工,已知各操作的加工时间和各工件在每台机器上的加工次序约束,要求确定与工艺约束条件相容的各机器上所有工件的加工开始时间,使加工性能指标达到最优。本文中加工性能指标取为完成全部操作所需的时间(Makespan)。JSP属于一类NP-hard问题,当前比较有效的求解方法主要有遗传算法(GeneticAlgorithm,GA)、模拟退火(SimulatedAnnealing,SA)、禁忌搜索(TabuSearch,TS)和蚁群算法(AntColonyOptimization,ACO)等近似求解方法以及这些方法的混合算法。本文分析了传统PSO的优化机理,提出了广义粒子群优化模型,并以此模型为基础构建了适合JSP求解的广义粒子群优化算法(GeneralParticleSwarmOptimization,GPSO)。与已有的其他JSP求解方法相比,本算法在收敛速度和精度上都有了较大的提高。实验结果亦显示了GPSO的有效性。1广义粒子组优化模型1.1最优解的迭代PSO随机初始化为问题的一组解,称为一群粒子。第i个粒子在d维解空间的位置表示为Xi=(xi1,xi2,xi3,…,xid),此外还有一个速度Vi=(vi1,vi2,vi3,…,vid)来决定其单次迭代的位移。在整个搜索过程中,粒子通过种群和个体经验来动态调整自己的位置。在基本的粒子群优化算法中,粒子通过跟踪两个极值来更新自己,第1个是粒子自身所找到的最优解Pi=(pi1,pi2,pi3,…,pid),另一个就是整个种群目前找到的最优解Pg=(pg1,pg2,pg3,…,pgd)。迭代公式如下:其中,w为惯性权重;c1和c2为加速因子,一般取常数;rand()和Rand()为两个独立的均匀分布在区间的随机数。式(1)分为3部分,第1部分代表前一次速度值对当前速度的影响,称为突进部分;第2部分称为认知部分,粒子根据自身的经验来学习;第3部分称为社会部分,粒子向整个种群中的最优粒子学习。为了提高传统PSO的搜索效率,众多学者对基本算法进行了扩展,当前PSO的研究主要集中于算法的改进、邻域拓扑结构设计、参数的选择、与其他进化算法的混合以及算法的应用。笔者注意到,目前对PSO的研究都是以上面提到的速度-位移迭代公式为基础,尽管改进后的算法在各自的问题上取得了不同程度的进展,但到目前为止,PSO在解决复杂的组合优化问题上仍然没有取得突破。1.2pso优化机理传统的PSO局限于速度-位移更新模型,不能有效地拓展到离散及组合优化领域。速度-位移模型中粒子采用实数编码,其位置和速度的每一维都代表独立的变量,迭代过程中并不能反映出这些变量之间的顺序或者其他约束关系。该模型的本质为粒子所代表的解在连续空间内,跟随个体以及邻域极值以矢量运算的形式进行更新,因此并不适合处理作业车间调度之类的复杂组合优化问题。算法应用于整数规划问题时仅通过简单的截断法将连续解映射到离散空间,处理单机调度问题时则是通过一种启发式规则将连续解转换为工序的排列。本文以速度-位移更新模型为基础,分析传统PSO的优化机理,并在此基础上提出了GPSO模型。根据速度-位移迭代公式,粒子的更新按照以下步骤进行:步骤1粒子从其个体极值获取部分信息。式(1)的c1×rand()×(pid-xid)代表粒子从个体极值获得更新信息,其中c1×rand()表示粒子从个体极值pi的信息继承度。步骤2粒子从种群中获取部分信息。式(1)中c2×Rand()×(pgd-xid)代表粒子从全局极值中获得更新信息,其中c2×Rand()代表粒子从全局极值pg的信息继承度。需要指出的是,粒子根据全局极值来更新只是其从种群中获取信息的一种具体形式。步骤3粒子进行局部或随机搜索。粒子从个体与全局极值获得更新信息之后,进行自身的更新操作w×vid,其中vi在初始化阶段的随机性使得粒子具有在解空间的全局搜索能力,惯性权重w具有平衡算法全局搜索和局部搜索的能力,较大的w可以加强PSO的全局搜索能力,而较小的w则能加强其局部搜索。由以上分析可知,粒子群优化的本质为粒子从其个体极值以及种群中获得更新信息,并在此基础上进行自身的局部或随机搜索。速度-位移更新模型仅为符合此优化机理的具体实现之一,而这种更新方法本质上更适合于连续优化问题的求解。传统PSO采用速度-位移更新模型,该模型本身的局限性限制了PSO在离散以及组合优化问题上的应用。1.3基于局部搜索的优化模型基于以上对传统PSO核心优化机理的分析,忽略粒子的具体更新策略,可以总结出GPSO模型,其基本流程如图1所示。按照此模型,粒子可以多种形式从其个体极值以及种群中获取更新信息。以遗传操作为例,粒子可通过与个体极值及全局极值的交叉来获取更新信息,而变异操作则可以作为粒子的随机搜索策略。粒子的局部搜索也可以采用TS,SA等多种形式来实现。这样,对于离散以及组合优化问题,可以选择更加适合问题本身的方式来实现粒子群优化。2选择适合ga、ts的gpso方法从图1可以看出,GPSO的关键在于确定粒子的更新方式,以及粒子的局部搜索和随机搜索方法。GA和TS作为JSP求解方法,可以运用到GPSO中来。GA中解的编码设计、基因的交叉和变异操作都可以被GPSO借鉴。例如,GA的染色体可以看作是GPSO中的粒子,交叉操作则可以当作是一种粒子间的信息交换策略,而变异操作也可以看作是粒子的随机搜索。本文借鉴GA和TS在解决JSP上取得的成果,按照GPSO模型构建出适合JSP求解的GPSO方法。现分别介绍GPSO的各组成部分及其算法流程。2.1标准质量及snp的缺失本文GPSO中的粒子对应GA中的染色体,采用基于操作的编码方式。对于一个n×m的JSP问题,每个粒子由n×m个代表操作的基因组成,对应于所有操作的一个排列,其中各工件号均出现m次。解码时先将基因串转化为一个有序的操作表,然后基于此操作表以及工艺约束条件对各操作以最早允许的加工时间逐一进行加工,从而产生调度方案。2.2gpso初始种初始种群应该具有一定的分布性,能够以较大的概率覆盖整个解空间。此外,为了提高种群的搜索效率,避免盲目搜索,初始种群中也应该包括部分质量较高的解。本文GPSO采用随机初始化和启发式方法相结合的初始化策略。种群中比例为α的粒子采用随机方法生成,其余的粒子使用启发式规则生成。这样,既保证了初始种群的分布性,也提高了质量。2.3基于工件的交叉生成GPSO中粒子的更新采用GA中的交叉操作来实现。传统PSO中粒子向全局极值学习,这只是粒子从种群中获取更新信息的一种具体方式。在这种信息交换机制中,粒子过于贪婪地获取更新信息,算法容易早熟。针对这种信息共享机制的局限性,本文引入记忆库(memorypopulation)的概念,利用记忆库来保留搜索过程中比较好的解。粒子通过与个体极值以及记忆库中的粒子进行交叉,从个体极值以及种群中获取更新信息。GPSO使用一种基于工件的交叉,该交叉操作的过程为:所有的工件随机分成两个集合J1和J2,子代染色体c1/c2继承父代p1/p2中集合J1/J2内的工件所对应的基因,c1/c2其余的基因位则分别由p2/p1删除了c1/c2中已经确定的基因后所剩的基因按顺序填充。交叉操作如图2所示。2.4禁忌搜索的生成本文GPSO采用TS作为粒子的局部搜索策略。TS算法中的邻域定义、禁忌表设置和邻域搜索策略均与文献相同。用s表示JSP的一个可行解,V(s)表示解s对应的移动集合,Cmax(s)表示解s对应的完工时间,C*表示当前最小的完工时间,T表示禁忌表,IterNum表示当前迭代次数,NSP表示邻域搜索程序,maxIterNum表示禁忌搜索的最大步长。设s*为禁忌搜索的初始解,则GPSO中禁忌搜索的步骤为:步骤1设置最大步长maxIterNum,令IterNum=0,T=,C*=Cmax(s*),s=s*。步骤2IterNum=IterNum+1,找出移动集合V(s),如果V(s)=,迭代停止,返回新的解s*。步骤3应用NSP,找到移动v′∈V(s),求出新解s′和新的禁忌表T′,令s=s′,T=T′。步骤4如果Cmax(s)<C*,则设置C*=Cmax(s),s*=s。步骤5如果IterNum<maxIterNum,转步骤2;否则停止迭代,得到新的解为s*。需要说明的是,本文中粒子采用的是基于操作的编码,因此,在进行禁忌搜索时需要先将粒子对应的编码转换为一个JSP解。而禁忌搜索的输出解也需要进行编码,从而得到一个新的粒子。2.5随机搜索中的粒子GPSO中粒子的随机搜索可以采用GA中的变异操作来实现。这里采用逆序变异,即将粒子中两个不同随机位置间的基因串逆序。2.6gpso的重复停止基准如果已达到最大迭代次数maxIterStep,或者迭代过程中最优值连续不提高的次数达到maxStagnantStep,迭代停止。2.7迭代算法及过程下面给出适合JSP求解的GPSO步骤:步骤1确定种群规模n1以及记忆库规模n2,种群初始化。步骤2评价种群中粒子的适应值,取初始种群中比例为β的较优粒子进入记忆库,其中β=n2/n1;记录每个粒子的个体极值。步骤3对于当前种群中的每一个粒子,按照概率γ选择下面两种方式之一进行操作:(1)从记忆库中随机选取一个粒子,当前粒子分别与该粒子以及个体极值进行交叉,当前粒子被其较优的子代取代;(2)以当前粒子对应的JSP解作为初始解进行禁忌搜索;对禁忌搜索得到的输出解进行编码,得到新的粒子,当前粒子被新的粒子取代。其中按(1)操作的概率为γ,按(2)操作的概率为1-γ。步骤4重新评价种群中的每一个粒子,求出当前最优解;判断是否满足迭代停止准则,如果满足,停止迭代,返回最优解。步骤5更新种群中每个粒子的个体极值。步骤6根据以下原则用当前种群中的粒子更新记忆库粒子:对于当前考虑的粒子,如果其Makespan小于记忆库中最差粒子的Makespan,并且记忆库中不存在此粒子,则用当前粒子替换记忆库中最差的粒子,按照此原则考察当前种群中的每一个粒子,即可完成记忆库的更新。步骤7对当前种群中的每一个粒子,按照一定概率λ进行变异操作,用变异后得到的粒子取代当前粒子,转步骤3。迭代过程步骤3中,(1)操作代表粒子从个体极值以及种群中获取更新信息,而(2)操作则为粒子的局部搜索。在搜索的早期,粒子以较大的概率向个体极值以及种群中较优的粒子学习,整个种群迅速向较优的区域集中,此时γ较大,禁忌搜索的最大步长较小。而在搜索的后期,粒子主要集中于较好的区域进行搜索,此时局部搜索的概率变大,γ值变小,禁忌搜索的步长加大。在GPSO中,γ值随迭代次数线性递减,而禁忌搜索的最大步长则随迭代次数线性递增。迭代过程的步骤7代表粒子的随机搜索,整个迭代过程中粒子按照一定的概率λ随机搜索。从上面的流程可以看出,相对于GA中染色体互相共享信息,整个种群比较均匀地向最优区域移动比较,GPSO中粒子直接从记忆库及其个体极值中获取更新信息,这种单向信息流动的目的性更强,效率更高,即单次信息流动对解的改进影响较大,避免了大量冗余的更新操作,提高了收敛效率。3ts的运行效果很快,与gasa和gpso算法比较取种群规模n1=150,β=10%,则记忆库规模n2=15;随机初始化粒子的比例α=70%;GPSO最大迭代次数maxIterStep=40;最优值无改进的最大允许步数maxStagnantStep=10;当迭代进行到第CurIterStep时,粒子按照交叉方式更新的概率,粒子禁忌搜索的最大步长为。整个迭代过程中,粒子随机搜索的概率λ=0.1。上述GPSO算法用C++语言编程实现,采用标准的JSP测试问题FT类(FT6,FT10,FT20)和LA类(LA1～LA40)共43个问题对其进行测试。程序运行环境为:P4CPU,主频1.8G,内存为512MB。对于每个测试问题,程序连续运行20次。表1给出了GPSO以及文献中一些其他算法的计算结果。从表1可以看出,对于比较简单的FT06,LA01～LA15,LA17,LA23,LA26,LA30～LA35问题,GPSO基本上每次都能求得最优解,而且求解速度非常快。对于较困难的FT10和FT20问题,GPSO在平均不到10s的时间内也取得了较好的结果,其中FT10问题在20次连续运行中有7次取得了930的最优值。GPSO在求解难度较大的LA36～LA40时都没有找到最优值,这与本文中采用的迭代停止准则有关。可以看到,在有限的时间内,GPSO已经得到了比较理想的结果,如果增加迭代次数,解的质量将会得到更大提高。表1中TS可以求得大部分问题的最优解,但这是以运行时间为代价的,而且TS的运行效果与初始解的选取有很大的关系,如果初始解选择不当,效果可能会差很远。与混合遗传算法(HybridGeneticAlgorithm,HGA)相比,GPSO表现出了更优的性能,43个测试问题中仅LA21,LA27,LA36,LA37这4个问题上得到的最优值差一些,而对于所有问题,GPSO的计算时间大大缩短。表2给出了GPSO与GASA和GATS的比较结果。从平均值来看,GPSO比GASA效果更好,而GATS也仅在FT10问题上优于GPSO。从取得的最优值来看,尽管在LA21问题上,GPSO不如其他两种算法,在LA36问题上GPSO也不如GASA,但这与GPSO的迭代步数较小有关,而在其他问题上,GPSO均取得了最优值。尽管这3种算法运行机器的配置不同,但是可以明显看出,GPSO运行速度更快,搜索效率更高。从实验结果可以看出,按照GPSO模型提出的GPSO算法,已经对文献提出的GATS混合算法进行了改进。在GASA和GATS中,分别利用SA和TS来替代遗传算法中的变异操作,在每次迭代中,种群中的染色体首先进行交叉操作,然后进行一定步数的SA或者TS操作。整个搜索过程中交叉操作与局部搜索串行进行,而且局部搜索步长一致,导致了大量的重复搜索。而在GPSO中,粒子按照一定的概率