基于离散入侵杂草算法的作业车间调度方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN110458478A(43)申请公布日2019.11.15(21)申请号201910783042.X(22)申请日2019.08.23(71)申请人兰州理工大学地址730050甘肃省兰州市七里河区兰工坪路287号(72)发明人赵付青逯浩唐建新张建林(74)专利代理机构兰州振华专利代理有限责任公司62102代理人董斌(51)Int.Cl.G06Q10/06(2012.01)G06N3/00(2006.01)权利要求书2页说明书4页附图4页(54)发明名称基于离散入侵杂草算法的作业车间调度方法(57)摘要基于离散入侵杂草算法的调度方法，算法步骤包括：给所有的杂草给定一个随机数的初始解，并通过工序的编码方式对初始随机序列进行编解码；在每一次的迭代过程中，每个杂草计算其所要产生的种子个数；在算法的空间扩散操作中，种子根据父代植物的适应度值产生控制扩散距离的标准差值，种子根据这个标准差值在父代周围以正态分布的方式随机扩散；对于新生成的种子进行局部的寻优，使用VNS的思想改变工件的序列，提升算法的局部搜索能力；当杂草的总个数到达设定的最大值时，算法去除较差个体，只保留最大值个数的杂草。本发明提出了一种基于先进的新型进化算法的调度方法，并使其更加智能的解决制造业中的作业车间调度问题。CN110458478ACN110458478A权利要求书1/2页1.基于离散入侵杂草算法的作业车间调度方法，其特征在于，其步骤为：步骤1：初始化种群，种群大小为N；步骤2：初始化参数，包括种子和标准差值变化区间；步骤3：根据基于工序的编码方式生成包含n个解(杂草)的种群；步骤4：评价每个解的适应度值；当算法满足终止条件时，算法返回目前找到的当前解，算法结束；步骤5：计算种群的标准差值以及父代个体产生的种子数；步骤6：对杂草进行排序，找到最优和最差适应度值的杂草个体；步骤7：计算每个杂草产生的种子，并计算其适应度值；步骤8：对种群中的杂草个体执行局部搜索策略：步骤8.1：根据局部搜索策略，生成Wnew；步骤8.2：如果randi<PARg，则：步骤8.2.1：杂草个体从当前最好的杂草中选值；步骤8.2.2：否则：杂草个体从当代保留的所有杂草中选择值；步骤8.3：如果randi<HMCR，则：步骤8.3.1：杂草个体直接继承步骤10.2中得到的杂草个体；步骤8.3.2：否则：算法在解空间中产生新解；步骤9：对新产生杂草个体执行VNS操作：步骤9.1：对种群中的一杂草个体x执行插入操作，得到杂草个体x*；步骤9.2：对种群中的一杂草个体x*执行交叉操作，得到杂草个体x’；步骤9.3：如果f(x’)≤f(x)，则将x更新为x’；步骤10：将新产生的种子和杂草放在一起，按照适应度值排序；步骤11：消除适合度较低的杂草以达到群体中的最大允许群体；步骤12：更新整个种群的全局最优解，转步骤4。2.根据权利要求1所述的基于离散入侵杂草算法的作业车间调度方法，其特征在于，在初始化阶段，设置种群大小N；最大种子数Smax；最小种子数Smin；初始标准差值σinit，最终标准差值σfinal；最大种群数Pmax，扰动选择概率HMCR和PARg。3.根据权利要求1所述的基于离散入侵杂草算法的作业车间调度方法，其特征在于，在步骤1中，本发明通过使用一种基于工序的编码方式进行编码，将一个杂草表示为一组0到1之间的随机数，之后对其进行排序，并用工序编码的计算方式得到可以用于算法计算的工序，可以将应用于连续问题的算法，用于解决作业车间调度问题。4.根据权利要求1所述的基于离散入侵杂草算法的作业车间调度方法，其特征在于，在步骤8中，将局部搜索策略加入到算法的框架中，局部搜索策略会对所得到的解进行重新选择和组合，以求得不同于已得到解的新解，并计算所得到解的加工时间，以求得更优解；如果可以获得比当前最优解决方案更好的解决方案，则用得到的更好解决方案替换当前最优解决方案；同时算法还可以在算法陷入停滞时，产生完全不同于当前种群中解的新解，以此来增加种群的多样性；避免算法陷入局部最优，增强算法的局部搜索能力。5.根据权利要求1所述的基于离散入侵杂草算法的作业车间调度方法，其特征在于，在步骤8中，根据如下的公式进行算法的局部搜索：2CN110458478A权利要求书2/2页6.根据权利要求1所述的基于离散入侵杂草算法的作业车间调度方法，其特征在于，在步骤9中，将VNS的思想加入到算法框架中，算法对步骤9中生成的新杂草使用VNS中交叉和插入操作，对于经过两种操作后得到的新杂草，与步骤10中的杂草个体对比；保留两个杂草个体中更优的杂草个体，提升算法的局部搜索能力和深度搜索能力。7.根据权利要求1所述的基于离散入侵杂草算法的作业车间调