一种基于有向图适应度评估的混合差分进化算法

摘要

本发明提供了一种基于有向图适应度评估的混合差分进化算法来解决一个同时结合了时间依赖转换时间、选择与调度结合和时间依赖收益特点的调度问题，包括编码及种群初始化、变异操作、交叉操作、选择操作，本发明所述的算法在能够在不同阶段循序渐进不断调整自身的值，具有优化性能；本发明在算例上取得的收益明显优于其他算法；本发明能够处理任何形式的转换时间表现形式，具有很强的灵活性。

主权项

一种用于解决时间依赖转换时间调度问题的基于有向图适应度评估的混合差分进化算法，所述算法包括以下步骤：步骤1).编码及种群初始化：采用位于0和1之间的实数作为编码方式，生成一组实值向量，其中：g表示第代种群，i表示第i个个体，每个向量构成一个染色体，每个实数表示工件的实际完工时间占整个时间窗口长度的比率，根据向量中的各实数预先确定对应工件的开工时间和完工时间，并且根据工件的开工和完工时间计算不同工件之间需要的转换时间；种群初始化时使实值向量对应的工件完工时间初始化时在其交货期附近随机采样；步骤2). 变异操作：从当前种群中随机选择三个个体，利用其中两个生成一个差分向量，再将差分向量乘以缩放因子之后加到第三个向量上，即得到一个向量，按如下操作：其中，的初始值设为0.5，在每次迭代过程中，记录采用第一种和第二种变异操作生成成功进入下一代的个体个数分别为和，而不能进入下一代的个体个数记为和，当这两组数字积累50代之后，采用如下方式更新：每次更新之后，将，，和置为0进入下一次统计过程。步骤3).交叉操作：对当前种群中的目标向量和经变异操作生成的向量进行重组生成新的向量，按如下操作：其中是0到1之间满足均匀分布的随机数，在每次调用时重新生成；是一个随机选择的索引以确保至少从经变异操作生成的向量中获得一位基因而不会与完全重复，对每个向量生成一次；是交叉概率。步骤4).选择操作：若交叉操作后生成的向量小于或等于变异操作前向量，则在下一代中用交叉操作后生成的向量替换掉变异操作前向量；所述算法其特征在于：采用有向图进行适应度评估，根据给定的实值向量，计算各工件的完工时间、开工时间和收益，将各工件按照开工时间升序排列，构建一个有向无环图，图中最长路径上的节点即为被安排加工的工件，路径的长度即为该实值向量对应的目标函数。