版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
考虑学习效应的加工作业问题优化算法分析案例目录TOC\o"1-3"\h\u6079考虑学习效应的加工作业问题优化算法分析案例 1282761.1引言 1138541.2问题介绍 2225151.2.1问题描述 2131611.2.2学习效应函数 371311.2.3数学规划模型 4309661.3基于中小规模问题的改进粒子群算法 5188171.1.1编码方式 6242491.1.2惯性权重 738931.1.3初始化 9243901.1.4粒子更新 9298781.1.5算法框架 11258401.4基于大规模问题的SPT启发式算法 11323371.5数值仿真实验 13166271.5.1智能优化算法 1397121.5.2启发式算法 181.1引言本章研究了考虑学习效应的加工作业调度问题,目标函数为最大完工时间,即所有设备中最后一道工序的完工时间。在该问题中,每台设备都根据对应的作业位置具有不同的学习效应数值。例如,在航空发动机的生产过程中,需要生产涡轮扇,涡轮盘等不同种类的零件进行组装。同时,每个零件又需要车床,钻孔等一系列的不同步骤,且每个零件都拥有属于各自独立的作业顺序。假设一天的生产计划为n个零件,并且每个零件都需要经过车床、钻孔、磨床、镗床等多个工序。零件经过每种设备的顺序可以不必相同,但同类型零件的顺序一致。在实际的生产过程中,当某台设备正在进行操作时,处于等待阶段的零件不可抢占该设备,正在等待的零件必须在该设备完成当前作业后才可进行加工过程。在所有设备不断重复相同的作业过程中,操作设备的工作人员也会逐渐熟悉整个流程,提高工作效率,进而减少后续任务的实际作业时间。在上述的生产过程中,每个待加工零件在对应设备上的作业时间就可以视为加工作业问题中任务的处理时间,零件原料的准备时间就是加工作业问题中每个任务对应的释放时间。上述问题就可以被视为考虑学习效应的加工作业问题。针对考虑学习效应的调度问题,目前的研究方向主要集中于简单的单机或并行机问题。在前文的文献综述中已经提到,只有少数文献研究了多机流水作业问题等较为复杂的问题。而且这些文献都假设所有待处理任务同时达到,并没有考虑释放时间的约束。本章研究的加工作业问题,在基本问题之上引入学习效应及释放时间约束,目前仍是较为新颖的研究领域。本章将设计智能优化算法求解中小规模问题。该类算法通过模拟生物行为或使用某种规则在复杂的解空间内进行搜索,可以在很短的时间内获得一个较优解。但随着问题规模的不断扩大,问题解空间将越来越庞大,智能优化算法求解时间也会成指数型增加。尽管最终仍可获得问题的可行解,但求解时间以及最终解的质量已变得不可接受。因此,针对大规模问题,设计启发式算法来替代智能优化算法进行求解。启发式算法可以在大规模的情况下,在短时间内得到一个较为优秀的可行解。1.2问题介绍1.2.1问题描述考虑学习效应的加工作业调度问题同时兼顾了学习效应以及释放时间对最终调度序列的影响。该问题使用极小化最大完工时间作为优化目标。假设有n项待处理任务需要在m台设备上进行作业,且每个任务经过所有设备的顺序固定且不可改变。将任务i在设备j上作业的处理时间记为,每个任务的可开始作业时间记为。在整个调度序列中要求所有任务均按已给定的顺序进行作业,同时该调度序列需使得最大完工时间,即最小。该问题有如下几个基本假设。(1)所有待处理任务与设备独立,互相不受干扰。(2)所有待处理任务需在对应释放时间之后方可进行作业。(3)所有设备均在开始时刻可用。(4)每台设备基于相同作业位置的学习效应均相同。(5)每台设备作业过程中不可中断,开始作业之后直到该工序结束方可使用。(6)每个待处理任务在相同时间只能在一台设备上进行作业。(7)每台设备在相同时间只能处理一个任务。(8)各设备之间没有缓存限制,即允许多个待处理任务同时等待。根据调度问题经典三参数表示方法,该问题可以被记为。该表示方法中,Jm为包含m道工序的加工作业问题,与rj分别代表了学习效应与释放时间约束,Cmax为该问题的优化目标即最大完工时间。1.2.2学习效应函数在实际的生产过程中,工人在进行作业时,熟练度会随工作时间的增加而增强,对应的实际工作时间将会减少。学习效应问题意在模拟工人熟练度增加的过程。在调度序列中,每台设备越靠后位置任务的实际处理时间相对于原始所需的处理时间比例越小。在本章中,学习效应函数值将基于任务在不同设备上的处理位置决定,且每台设备的学习效应函数相互独立。在该问题中,学习效应函数呈单调递减趋势,并与任务的处理位置呈负增长关系。处理位置越靠后,对应的学习效应函数数值就越小,实际的处理时间也就越短。本章将分别设计线性函数、幂函数和指数函数来模拟学习过程。学习效应函数定义如下。(1)线性函数 (1.1)(2)幂函数 (1.2)(3)指数函数 (1.3)在学习效应函数的表达式中,t代表任务的处理位置。该变量需满足1≤t≤n不同种类的学习效应函数对应图像如图1.1所示。图1.1三类学习效应函数图像Fig.1.1Functionimagesofthreelearningeffectfunctions从图1.1中可以看出,线性函数的下降趋势自始至终稳定不变,幂函数和指数函数则呈非线性的下降趋势。幂函数的初始下降速率较大,进而很快的保持相对稳定状态,下降速率大幅减小。指数函数的下降速率初期大于线性函数,但随着自变量的不断加大,下降速率也将逐渐变慢。在三种学习效应函数中,线性函数下降速率不变的特点则过于理想化,幂函数和指数函数更符合实际的生产情况。1.2.3数学规划模型下面给出考虑学习效应的加工作业调度问题的变量定义,以及该问题的数学规划模型。问题变量定义如下所示。N任务集合,N={1,2,…,n};M设备集合,M={1,2,…,m};Let当前设备第t个处理位置的学习效应数值Pi,j任务在设备上的处理时间rj任务的释放时间Ci,j任务在设备上的完工时间Cj任务的最终完工时间Oi,j,kaj,i,lxi,j,kyi,jM一个很大的正数根据上述定义,该问题可以表述为如下的数学规划模型。MinimizeSubjectto(1.4)(1.5)(1.6)(1.7)(1.8)(1.9)(1.10)(1.11)(1.12)(1.13)在该问题的混合整数规划模型中,约束(1.4)保证了每项待处理任务必须在该任务的释放时间之后才可开始进行处理。约束(1.5)至约束(1.8)确保了变量xi,j,k的唯一性,即整个调度过程中处理任务的唯一性。约束(1.9)限制了同一任务相邻工序的先后关系。约束(1.10)限制了同一设备相邻任务的先后关系。约束(1.11)则确保该任务的最大完工时间需大于每道工序的完工时间。约束(1.12)和(1.13)指定了0、1限制和非负限制。1.3基于中小规模问题的改进粒子群算法本章将粒子群算法用以求解中小规模问题。问题的解空间是k(任务数设备数)维的。每个粒子拥有属于自身的位置和速度,则第i个粒子的位置和速度分别记为Xij=(xi1,xi2,xi3,...,xik)与Vij=(vi1,vi2,vi3,...,vik)。根据位置信息可得到出当前位置所对应的调度序列,并计算出该序列所对应的目标函数值。通过该目标函数值来确定是否更新当前粒子对应的最优个体=(xi1,xi2,xi3,...,xik)与当前种群发现过的最优个体=(xi1,xi2,xi3,...,xik)。粒子群算法通过不断改变速度与位置来对解空间进行搜索,直至输出最终的可行解。粒子群算法求解问题的效率受算法参数的影响较大。粒子群算法主要包括如下几个参数。惯性权重该参数将决定粒子在算法的运行过程中更偏向于全局搜索还是更侧重局部搜索。理想的惯性权重应该随着算法迭代次数的增大而不断减少。确保算法初期的全局搜索能力较强,在解空间内不断寻优。在算法运行后期,较小的惯性权重则可以增强局部搜索能力,提高收敛速度。一个良好的惯性权重不仅可以提高算法的运行效率,还可以极大的提高最终解的质量。学习因子学习因子可分为认知系数和社会系数。前者决定了粒子当前信息影响更新过程的重要性而后者决定了学习当前全局最优粒子的程度,通过二者间的相互影响最终决定粒子的搜索方向。当学习因子较小时,粒子只能在当前位置附近搜索。而学习因子过大时,粒子则会超出寻优范围,成为无效粒子。因此,选择合适的学习因子系数也是极为关键的。位置和速度范围在粒子群算法中,每个粒子可以搜寻的范围将由最大位置决定。同时,粒子飞行的最大速度也会有一定限制。粒子位置范围过大则会增大解空间,导致算法收敛速度变慢。位置范围过小则会人为降低解空间的范围,影响最终解质量。粒子的速度范围同样也影响算法的运行过程。速度范围过大则会越过最优解,过小则影响算法的迭代更新,快速处于局部最优状态,影响最终结果。基本的粒子群算法容易陷入局部最优影响最终得到的可行解结果,因此本章将设计一种全新的惯性权重更新方法优化基本的粒子群算法。1.1.1编码方式传统的粒子群算法用来解决连续优化问题,因此设计一种适用于本章离散问题的编码方式尤为重要。通过合适的编码方式将离散问题连续化,进行粒子速度和位置的更新,同时也需要将粒子位置还原成完整的调度序列,用来计算该粒子对应调度序列的目标函数。针对加工作业问题工序固定的特点,本文采用基于任务工序的编码方式,即每个染色体由维的向量组成。粒子位置向量对应的编码为待处理任务编号,编码出现的次数即为当前任务的工序。确定调度序列时,根据任务编号大小与出现次数来确定该任务对应工序在调度序列中的位置。考虑一个任务数为3,设备数为3的例子。为了更详细的了解编码方式,该例子暂时不考虑学习效应与释放时间。每个任务在设备上的处理时间由如下矩阵给出。每个任务的工序如下。则给定一个粒子的位置编码。131221323在该编码中,第1维向量数值为1,代表任务编号为1的第一道工序最先被处理。第8维向量的数值为2,该任务编号已在该编码中出现3次。该位置编码代表任务编号为2的第三道工序被处理,该粒子对应的目标函数值为14。由该编码解析出的完整调度序列甘特图如图1.2所示。图1.2编码甘特图Fig.1.2Ganttchartofcode1.1.2惯性权重在基本粒子群算法中,惯性权重一旦确定就不再更改,因此容易使整个粒子群体陷入局部最优而无法跳出。通过随算法运行不断更新惯性权重的方法可以良好的解决局部最优问题[55]。在算法运行的初始阶段,由于各粒子随机生成,因此希望在粒子更新速度时惯性权重较大,即粒子原速度对速度更新的影响较小,可以使粒子有更大可能在解空间中探索到更好解。而在接近最大迭代次数时,希望惯性权重较小,此时粒子种群已接近算法所能取得的最优值,因此通过使用较小的惯性权重增强局部搜索能力。针对惯性权重的更新方式,现在大多采用线性惯性权重的方式,惯性权重更新过程如下。(1.14)其中,为第D次迭代的惯性权重数值,和分别为惯性权重的最大值和最小值,为算法的最大迭代次数。在这种更新方式中,惯性权重随迭代次数的增加而减少。同时斜率恒定,惯性权重减少的速率保持不变。该方法尽管在恒定惯性权重的基础上做了改进,但由于变化速率不变,如果初始粒子的位置不理想,初期惯性权重的快速下降很可能导致该粒子陷入局部最优。线性惯性权重的方法过于依赖初始粒子位置。为了改进这一情况,设计一种线性微分的惯性权重更新方法来替代单一的线性更新方式。该方法的惯性权重更新过程如下。首先在式(1.14)中对迭代次数D微分。(1.15)在对等式两边进行积分。 (1.16)最终的惯性权重更新方法如下。 (1.17)根据图1.3所示,由线性微分的惯性权重更新方式与迭代次数呈二次负相关。在新的权重更新方式下,相对于简单的线性更新过程,算法运行初期权重ω的变化速率较慢,有利于在算法初始阶段在解空间内广泛搜索可行解。在接近最大迭代次数时,权重ω的变化速率将大幅提高,更有益于跳出局部最优状态。线性微分的权重更新方式相比于基本的线性过程可以更快逼近算法所能取得的全局最优值,极大的提高了算法的求解能力与运算效率。图1.3惯性权重更新过程示意图Fig.1.3Inertiaweightupdatingprocess1.1.3初始化在算法的初始阶段主要包括参数设置和初始粒子群体生成两个阶段。算法的主要参数包括粒子规模Λ,最大迭代次数Dmax,认知系数c1,社会系数c2,以及位置和速度范围Xmax与Vmax。同时也应设置权重范围[,]。这些参数均在数值仿真实验前由正交实验确定。在算法的初始化过程中,首先按任务编号依次在粒子位置与速度范围内生成对应工序的初始位置和初始速度。再根据工序对应的位置向量进行升序排列,确定该位置对应的编码,将连续的粒子位置映射成离散的调度序列。最终编码中任务出现次数为对应任务的工序次序,同时更新个体极值与全局极值。下面给出一个任务数为3,设备数为3的粒子初始化过程,该过程如表1.1所示。表1.1粒子初始化过程Table1.1Particleinitializationprocess维数123456789粒子位置1.42.0-1.0-2.6-2.42.6-1.81.2-1.6工序编码111222333位置排序-2.6-2.4-1.8-1.6-1.01.21.42.02.6最终编码223313112在粒子种群中,每个粒子对应的解向量均由上述初始化方法生成。最终将初始种群中目标函数最优粒子的对应位置赋值给全局极值点。1.1.4粒子更新在初始化粒子种群后,就需要对粒子进行更新搜索完成算法的运行过程。粒子的更新过程由速度更新和位置更新两部分构成。新的粒子速度将根据式(1.18)生成。(1.18)其中,表示新粒子第i维的速度,则表示当前第i维粒子的速度。为惯性权重,确定了在原始粒子速度对新粒子速度的影响。c1和c2分别为认知系数和社会系数,r1和r2则为[0,1]区间内的一个随机数。和则为当前粒子个体极值位置与全局极值的对应位置。在粒子位置的更新过程中,若粒子的新速度超出给定速度范围则采用“吸收”的方法,即新的粒子速度大于Vmax,则将置其为Vmax;若小于-Vmax则置为-Vmax。在确定粒子新的速度后,粒子位置根据式(1.19)进行更新。若新的位置超出位置范围,则同样采用上述“吸收”的方法,确保新的粒子位置在给定位置范围之内。(1.19)下面给出一个粒子更新的实例。粒子的当前位置、速度及对应编码由表1.2给出。当前粒子对应的个体极值及例子群体的全局极值由表1.3给出。表1.2粒子初始编码Table1.2EncodeofParticleinitialization维数123456789粒子位置-0.70.4-1.21-2.330.21.3-0.5粒子速度0.30.4-2.2-0.6-0.51.712.3-2粒子编码311123232表1.3粒子极值Table1.3Particleextremum维数123456789-1.20.21.22-2.42.3-33-10.72.2-1-1.2-0.80.61.42-1.8根据上述已知信息,结合式(1.18)就可以得到新的粒子速度。再根据式(1.19)进行粒子位置的更新,从而完成一次粒子的更新操作。粒子更新的具体过程在表1.4中。在该例中,惯性权重为0.6,认知系数c1和社会系数c2分别为0.5和1.5。表1.4粒子更新过程Table1.4Theprocessofparticleupdating维数123456789r10.40.90.20.20.60.40.40.60.3r20.80.20.70.40.90.40.20.20.9速度更新1.70.6-0.8-1.51.60.60.32.1-3位置更新11-2-0.5-0.71.60.51.4-1.5位置排序-3-2-0.7-0.50.51133新粒子212123133在上述例子中,初始粒子对应的调度序列为{3,1,1,1,2,3,2,3,2},经过粒子的速度和位置更新之后,新粒子对应的调度序列则为{2,1,2,1,2,3,1,3,3}。由此可见,在粒子经过一次更新后,该粒子对应的调度序列已经发生了很大变化,这说明粒子群算法在解空间的搜索能力是比较强的。1.1.5算法框架本节将通过伪代码来描述带有线性微分可变权重的粒子群算法过程。算法的完整过程如下。线性微分可变权重的粒子群算法伪代码1开始2初始化问题变量与算法参数3初始化粒子种群,并计算每个粒子对应的目标函数值4根据粒子种群赋值和;5D←6WhileD<Dmaxdo7Forj=1toΛ8根据式(1.18)生成粒子新速度;9根据式(1.19)与新速度生成粒子新位置;10计算该粒子对应的目标函数值;11If1213Endif14If1516Endif17Endfor18D=D+1;19Endwhile20返回21结束1.4基于大规模问题的SPT启发式算法(1)SPT启发式算法流程尽管智能优化算法可以在比较短的时间内获得一个较优可行解。但是随着任务数与设备数的不断增加,问题的解空间逐渐增大,智能优化算法的求解时间将会呈指数型上升。因此针对大规模问题,本节提出了一种SPT启发式算法。本节的启发式算法具体指在学习效应的影响下,优先选择当前设备处理时间小的任务进行排序。任务i在调度过程中的任意时间点到达,若其工序对应的设备可用则立即开始作业。若该设备被占用,该设备完成当前工序后,可处理任务数大于1时,则根据所有任务的处理时间来决定排序。选择当前处理时间最短的任务进行排序。在上述情况下,若仍存在多个处理时间相同的任务,则根据任务编号从小到大依次排序。SPT启发式算法可以缩短靠后位置处理任务的实际处理时间,因此可以有效的降低每台设备的完工时间从而进一步优化目标函数。下面给出一个设备数为3,任务数为4的启发式算法实例。在该例子中,学习效应函数选择线性函数,具体表达式为:,即每台设备第一个位置的学习效应系数为1,之后分别为0.8,0.6,最后一个位置的学习效应系数为0.4。该例子中任务的处理时间,释放时间由如下矩阵给出。每个任务的工序如下。则该例子对应的最终调度甘特图为图1.4,该调度序列的目标函数为21.4。图1.4SPT启发式算法甘特图Fig.1.4GanttchartofSPTheuristicalgorithm(2)SPT启发式算法框架本节所使用的目标函数为所有任务的最大完工时间Cmax。SPT启发式算法伪代码1开始2Forj=1todo3If当前只有一个任务j可被处理4将该任务j的当前工序安排到所对应的设备m上,根据该设备当前位置的学习效应更新任务j在设备m上的处理时间,更新任务j当前工序对应设备上的完工时间Cm,j,设备m处理过的任务数加15Endif6If当前设备m有多个任务可被处理7首先记录当前设备所有待作业的处理时间,并选择最短处理时间对应的任务j。若此时仍存在多个处理时间相同任务,则选择任务编码最小的任务j。根据该设备当前位置的学习效应更新任务j在设备m上的处理时间,更新任务j当前工序对应设备上的完工时间Cm,j,设备m处理过的任务数加18Endif9Endfor10返回11结束1.5数值仿真实验为了验证本章所提出算法的有效性,本节将会根据不同算法设计不同规模的数值仿真实验。实验所用学习效应函数为本章所提到的三种函数类型,即线性函数,幂函数和指数函数。所有数值实验所有代码均使用C++语言编写。实验所用电脑的硬件环境为Intel-i5-1.6GHz4核处理器及8GBRAM。1.5.1智能优化算法在本节的数值仿真实验中,设备数m={3,5,8},任务数n={30,50,80,100}。每个任务对应设备的处理时间根据离散均匀分布U(1,10)随机生成,每个任务的释放时间则由离散均匀分布U(0,3n)随机生成,每个任务的工序根据设备编号随机生成。针对每个不同的设备数与任务数组合,生成十组数据。每组数据将进行5次独立重复实验减少误差。实验所用学习效应函数分别为Le1(t)=1–t(0.5/n),Le2(t)=t−0.15,以及Le3(t)=0.993t−1。为了验证所提出算法的有效性,本节将与差分进化算法进行比较。本文所涉及的加工作业问题属于离散优化问题,与连续优化问题相比,使用智能优化算法求解的收敛趋势规律波动较大。因此为了体现算法性能,使用相对偏差百分比(Relativedifferencepercentage,RDP)进行算法评价,该指标的计算方法如下。(1.20)其中,表示每次算法运行得到的最终解,表示每组数据进行的5次独立重复实验中,两种算法得到该组数据对应问题的最优解。并根据RDP数值统计最大值、最小值、平均值以及标准差进一步分析算法性能。实验所用的算法参数全部由正交实验得出。通过正交实验表可以精简掉所有参数组合中的重复数据,高效快捷的得到实验结果[56]。为了提高实验效率,粒子群算法惯性权重的最小最大值分别为0.1和1.0。正交实验过程使用算法初始解与最终解的改进量为主效应值。根据正交实验获得粒子群算法的参数为:种群规模为200,最大迭代次数为300,认知系数和社会系数分别为2.5和2.0。表1.5至1.8给出了各学习效应函数对应的实验结果。其中表1.8为每种学习效应函数所有规模对应指标的平均值。为了更直观的展示实验结果,表中数据均省去了百分号。在数据表中,Max,Min,Ave,SD分别对应了RDP的最大值、最小值、平均值以及标准差。前三项可以反映出算法求解问题的能力,该数值越小说明算法求解问题的能力越强。标准差的大小则体现了算法求解问题的稳定性。首先从所有规模的平均值来看,粒子群算法对应三种学习效应函数的Ave值为1.898、4.269和4.234。而差分进化算法则为11.317、11.308和12.320,分别为粒子群算法的2.9倍,1.1倍以及2.9倍。这说明两种算法在求解本章问题的能力上存在着一定差距。表1.5线性函数实验结果Table1.5Experimentresultoflinearfunction粒子群算法RDP数值差分进化算法RDP数值MaxMinAveSDMaxMinAveSDm=3,n=3016.33801.5954.37826.8838.89317.9894.935m=3,n=5016.65501.7694.46822.6819.75615.9451.812m=3,n=8012.02801.7761.79218.4181.38511.4724.324m=3,n=10010.49501.3301.19317.5290.4909.8364.238m=5,n=3022.04706.0886.79225.19811.69518.5771.987m=5,n=5018.16904.2575.28821.0372.13111.6745.603m=5,n=8010.66701.5941.28615.86607.3331.985m=5,n=1009.68602.7502.9528.5000.8104.7182.195m=8,n=3020.13105.7556.32730.1771.30914.3527.645m=8,n=5017.34204.3525.14422.3791.42311.7945.766m=8,n=807.62102.3902.96014.6460.7306.7801.922m=8,n=10011.08801.1291.36412.1411.6685.3362.935表1.6幂函数实验结果Table1.6Experimentresultofpowerfunction粒子群算法RDP数值差分进化算法RDP数值MaxMinAveSDMaxMinAveSDm=3,n=3011.75801.0081.35028.9319.02116.4615.291m=3,n=5015.06901.5354.21827.5465.39415.9925.219m=3,n=8019.99904.2205.15821.8031.77811.1564.688m=3,n=10017.69601.9424.05718.5531.24410.0134.428m=5,n=3024.19706.3347.07129.2799.57721.5274.620m=5,n=5021.65306.3006.47721.6031.40714.9215.181m=5,n=8015.05004.0094.26416.1514.95210.8002.860m=5,n=1009.10502.9681.04011.49805.3221.406m=8,n=3017.61305.3285.30239.0218.09321.2247.071m=8,n=5025.25806.1786.84027.5438.56416.7004.766m=8,n=8012.29802.4611.31115.28907.0174.894m=8,n=1008.80702.9492.84811.1180.8646.5601.150表1.7指数函数实验结果Table1.7Experimentresultofexponentialfunction粒子群算法RDP数值差分进化算法RDP数值MaxMinAveSDMaxMinAveSDm=3,n=308.77402.0472.38421.132814.6571.677m=3,n=5015.04904.3244.77128.6586.39716.1295.383m=3,n=8011.45901.5601.59016.8261.56110.6801.371m=3,n=10014.35904.4204.20915.3522.8319.6672.773m=5,n=3022.43504.9195.80731.47111.49618.6854.294m=5,n=5018.27704.9046.01524.9138.02614.8384.754m=5,n=8010.79701.4561.36315.87808.5121.870m=5,n=10018.60604.7355.44917.3381.2868.2184.896m=8,n=3021.28105.7586.39724.3281.95215.2456.329m=8,n=5011.94304.2554.27022.4047.02915.1654.491m=8,n=8014.03701.8394.11317.4180.8788.7894.226m=8,n=10011.64804.5964.55711.77007.2591.993表1.8所有函数统计均值Table1.8Meanofallfunctionsresult粒子群算法RDP数值差分进化算法RDP数值MaxMinAveSDMaxMinAveSD线性函数14.52201.8984.32819.6211.35711.3174.445幂函数16.54204.2694.66122.6954.40811.3084.631指数函数15.38904.2344.57720.9574.28812.3204.338从Max以及SD指标上看,粒子群算法对应数值全部略小于差分进化算法,表明粒子群算法求解问题的稳定性也较优于差分进化算法。而在Min数值上,粒子群算法均为0。这表明在所有36个规模的实验中,粒子群算法均能取得最优值,而差分进化算法只在5个规模的某次实验中取得了最优值,所占比例仅为所有规模的11.9%。从图1.5所示三种学习效应函数对应差分进化算法的结果中可以看出,线性函数相对于另外两种函数指标数值较低。这是因为线性函数的变化规律相对稳定,因此也会有较好的鲁棒性。同时结合表中数据可知,在所有36个问题规模中,粒子群算法在其中21个规模的方差较小,算法运行较为稳定。从平均RDP来看,图1.5为差分进化算法线性学习效应函数下的所有规模结果。结合表1.8和图1.5来看,结果表明粒子群算法的平均求解能力要强于差分进化算法。而在线性函数对应的所有12个问题规模对应的SD指标中粒子群算法也在其中8个规模中占优,这说明粒子群算法在取得较优解的情况下,还能极大概率的保持稳定。随着任务数的增加,平均RDP数值逐渐减小。当设备数为5时,平均RDP值从18.557下降到了4.718。主要原因是随着任务数的增加,在学习效应的影响下,每个任务对应的处理时间将被极大的缩短,调度序列对最大完工时间的影响将被减小。而设备数与平均RDP之间并没有明显的关系。尽管设备数增加会增大解空间的范围,但是在工序及学习效应的影响下,最终结果会有一定随机性。从图1.6和1.7所呈现的结果来看,随着任务数的增加,指标数值也在不断下降。从上述两个指标来看,随着任务数的增大,学习效应使得目标函数差距变小,两个算法最终解的差值比例将被缩小。从实验数据可以看出,粒子群算法无论是求解问题的能力还是稳定性上均强于差分进化算法。这是由于惯性权重采用线性微分的二次函数更新方式,不断调整自身最优解和群体最优解对新搜索方向的影响比重,因此更符合算法的搜索规律。图1.5差分进化算法结果Fig.1.5DDEexperimentresultofallfunctions图1.6差分进化算法线性函数平均RDPFig.1.6DDEaverageRDPoflinearfunction图1.7差分进化算法幂函数最大RDPFig.1.7DDEmaxRDPofpowerfunction1.5.2启发式算法本节将设计一系列数值实验验证SPT算法求解大规模问题的能力。设备数、工序与释放时间生成方式与智能优化算法相同。实验任务数n={100,200,300,500,800,1000}。每道工序的处理时间则由均匀分布U(1,10)与正态分布N(5,2)分别生成,并确保处理时间大于零。针对每个实验规模将进行30次数值实验,用以测试大样本下启发式算法求解问题的能力,同时减小实验误差对最终结果的影响。实验所用学习效应函数分别为Le1(t)=1–t(0.5/n),Le2(t)=t−0.1,以及Le3(t)=0.9993t−1。图1.8学习效应问题下界甘特图Fig.1.8LowerboundGanttchartoflearningeffectproblem本节将启发式算法得到的结果与对应问题的下界进行对比。问题下界即为松弛掉某些约束获得的解。本章所用的下界将松弛掉工序约束,同时各任务对应学习效应数值则根据启发式算法确定。在下界中,每个任务的学习效应函数为对应任务在启发式算法中最后一道工序对应设备的学习效应函数值。同时在每台设备上使用LPT规则进一步缩小最大完工时间。所有设备中,最短的完工时间即为该问题对应的下界值。基于该思想,图1.8则为1.4节中对应例子的下界甘特图。该问题对应的下界值则为11.8。在实验中,使用GAP这一评价指标来衡量启发式算法性能。该指标的计算方法如下。(1.21)其中,SPT启发式算法得到的目标函数值记为Obj,下界值记为LB。根据GAP值的变化趋势可以很好的分析出启发式算法的收敛性。表1.9均匀分布线性函数实验结果Table1.9Experimentresultoflinearfunctioninuniformdistributionn=100n=200n=300n=500n=800n=1000m=328.57%25.44%24.79%21.38%21.67%22.87%m=541.63%34.12%30.86%27.94%26.27%25.42%m=861.77%45.45%39.67%31.25%30.42%29.73%表1.10均匀分布幂函数实验结果Table1.10Experimentresultofpowerfunctioninuniformdistributionn=100n=200n=300n=500n=800n=1000m=325.42%21.82%18.18%11.26%5.64%1.51%m=538.86%26.50%22.09%14.37%7.67%5.20%m=858.26%39.85%30.14%18.84%10.6%7.47%表1.11均匀分布指数函数实验结果Table1.11Experimentresultofexponentialfunctioninuniformdistributionn=100n=200n=300n=500n=800n=1000m=325.59%21.28%20.53%20.33%21.84%21.77%m=537.39%25.33%21.00%22.38%25.70%24.59%m=848.54%36.18%30.17%27.83%29.62%28.91%表1.12正态分布线性函数实验结果Table1.12Experimentresultoflinearfunctioninnorm
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 初中九年级心理健康教学设计《跨越代沟》单元整体教学设计与核心素养落实策略研究
- 高中信息技术必修3《信息的发布与交流》教学设计
- 高中三年级地理专题6高效复习与重难知识梳理教案
- 初中数学四边形一轮复习教学设计
- 2026事业单位工勤技能-新疆-新疆房管员五级(初级工)历年参考题库含答案详解
- CN119538165A 一种水套加热炉的温度监控系统及温度监控方法 (河北博勒皓拓节能科技有限公司)
- CN119538013A 基于多维度对比学习的以太坊钓鱼账户检测方法和系统 (泉城省实验室)
- CN119537632A 一种谱图数据的处理方法、装置、电子设备及存储介质 (中国石油天然气股份有限公司)
- 海南直辖县级行政单位万宁市2026-2027学年度第一学期期中考试七年级生物科试卷(文字版含答案)
- ICU循证护理课件
- 2026年中国电信广东公司应知应会练习题库【必考】附答案详解
- 2026年融资担保公司招聘题库及答案
- 2026年(高级)焦炉调温工职业技能考试题库(新版)
- 2025年长沙卫生职业学院单招职业技能测试测试卷附答案
- 胸痛诊疗规范课件
- 2026年及未来5年市场数据中国锂电池结构件行业发展运行现状及发展趋势预测报告
- 索尼摄像机HDR-CX670中文说明书
- 财会教师企业实践工作总结
- 商会采购管理办法
- 校友见面活动方案
- 外观检验基本知识培训课件
评论
0/150
提交评论