(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110586943.7 (22)申请日 2021.05.27 (65)同一申请的已公布的文献号 申请公布号 CN 113268928 A (43)申请公布日 2021.08.17 (73)专利权人 西南交通大 学 地址 610031 四川省成 都市金牛区二环路 北一段111号 (72)发明人 张剑　陈浩杰　丁国富　钱林茂　 孟祥印　 (74)专利代理 机构 北京盛询知识产权代理有限 公司 11901 专利代理师 张海青 (51)Int.Cl. G06F 30/27(2020.01)G06N 3/12(2006.01) G06Q 10/06(2012.01) G06F 111/06(2020.01) G06F 111/04(2020.01) (56)对比文件 CN 107992967 A,2018.0 5.04 CN 102004835 A,2011.04.06 CN 112039056 A,2020.12.04 审查员 刘娅 (54)发明名称 一种基于随机资源受限多项目调度的遗传 规划方法 (57)摘要 本发明公开了一种基于随机资源受限多项 目调度的遗传规划方法,包括初始化阶段： 采集 并初始化遗传规划参数， 获得优 先级规则表达集 合； 基于优 先级规则表达集合获得初始混合优先 级规则集合； 生成阶段： 通过NSGA ‑II算法对种群 优先级规则进行评估， 用于实现迭代优化和获得 非支配优先级规则集合； 选择阶段： 将传统优先 级规则集合和非支配优先级规则集合进行加权 归一， 获得目标优先级规则调度组合， 用于实现 工程项目在多状态下的优先级规则组合调度。 本 发明打破了传统遗传规划决策使用单一优先级 规则决策的缺陷， 实现了决策综合性能的进一步 提升。 对于随机资源受限多项目的调度具有重要 意义和工程应用价 值。 权利要求书2页 说明书10页 附图3页 CN 113268928 B 2022.07.19 CN 113268928 B 1.一种基于随机资源受限多项目调度的遗传规划方法,其特征在于， 所述遗传规划方 法包括初始化阶段、 生成阶段、 选择阶段， 其中， 所述初始化阶段包括以下步骤： 采集并初始化工程项目的遗传规划参数， 获得优先级 规则表达集合； 基于所述优先级规则表达集合获得初始混合优先级规则集合， 所述初始混 合优先级规则集 合包括属性 集、 功能集； 所述生成阶段包括以下步骤： 通过NS GA‑II算法对种群优先级规则进行评估， 用于实现 迭代优化和获得非支配优先级规则集 合； 所述选择阶段包括以下步骤： 将传统优先级规则集合和所述非支配优先级规则集合中 的优先级规则通过加权归一， 获得目标优先级规则调度 组合， 用于实现所述工程项目在多 状态下的优先级规则组合调度； 所述生成阶段还 包括以下步骤： 扩展和修 正所述属性 集和功能集， 用于适应随机环境下的项目调度优化； 构建遗传算子和 局部搜索算子， 进行种群进化， 用于提升 搜索能力； 所述选择阶段还 包括以下步骤： 通过项目执行进度百分比划分状态特征， 用于将所述工程项目的决策过程分为多个状 态； 根据多状态整数编码构建交叉算子、 变异算子和 局部邻域搜索， 用于提升 搜索能力。 2.根据权利要求1所述的一种基于随机资源受限多项目调度的遗传规划方法， 其特征 在于， 所述遗传算子包括交叉算子和变异操作； 所述局部 搜索算子包括节点取代局部 搜索、 子树取代局部 搜索、 子树删除局部 搜索； 所述节点取代局部 搜索为通过随机节点 替换树状编码结构被随机 选择的节点； 所述子树取代局部 搜索为通过随机生成的子树 替换原编码结构树被随机 选择的子树； 所述子树删除局部搜索为通过删除任意随机节点及其包括的子树而保留其父节点下 的另一个子树。 3.根据权利要求2所述的一种基于随机资源受限多项目调度的遗传规划方法， 其特征 在于， 所述节点取代局部 搜索的替换 条件包括： 被替换节点和随机节点具有相同的子节点数量； 被替换节点与随机节点 为不同元素； 被替换的节点 为“If”时， 变更判断子节点。 4.根据权利要求1所述的一种基于随机资源受限多项目调度的遗传规划方法， 其特征 在于， 所述状态特 征为和项目集的进度。 5.根据权利要求1所述的一种基于随机资源受限多项目调度的遗传规划方法， 其特征 在于， 所述交叉算子采用单点交叉， 当产生的随机数小于交叉率pc时， 执行交叉操作； 所产生 的另一个随机数小于0.5时， 交换父代优先级组合的前半部 分， 否则交换父代优 先级组合的 后半部分； 所述变异算子包括单点变异和双点交换变异， 第三随机数小于变异率pm时， 执行变异权　利　要　求　书 1/2 页 2 CN 113268928 B 2操作， 所产生的另一个随机数小于0.5时， 通过单点变异选择变异 点并用另一个随机生成的 不同于原基因的优先级规则编号替代， 否则通过双点交换变异随机选择两个变异点进 行基 因交换。 6.根据权利要求5所述的一种基于随机资源受限多项目调度的遗传规划方法， 其特征 在于， 所述局部邻域搜索包括双绑定交换局部搜索、 反转局部搜索、 向前/向后插入局部搜 索； 所述双绑定交换局部搜索为随机选择一个点b， 分别将b+3与b和b+2与b+1的基因进行 交换， 循环交换至基因的长度超过选择的位置导 致索引； 所述反转局部 搜索为随机 选择两个点的子基因序列进行反转； 所述向前/向后插 入局部搜索包括向前插 入局部搜索和向后插 入局部搜索； 所述向前插入局部搜索为选择第 一随机点和第 二随机点， 所述第 二随机点大于所述第 一随机点， 将所述第二随机点的基因插到所述第一随机点的后面； 所述向后插入局部搜索为选择第 一随机点和第 二随机点， 所述第 二随机点大于所述第 一随机点， 将所述第二随机点的基因插到所述第一随机点的前面。权　利　要　求　书 2/2 页 3 CN 113268928 B 3