一种适用于柔性作业车间动态调度的完全并行NSGA-II算法
摘要文本
本发明公开了一种适用于柔性作业车间动态调度的完全并行NSGA‑II算法，利用二级GPU指针，设计三层数据结构，使NSGA‑II的快速非支配排序和拥挤距离计算操作与GPU的网格式物理结构相兼容；构建融合非支配层级和拥挤距离的适应度函数，实现NSGA‑II中精英保留策略的并行处理。本发明提供的一种适用于柔性作业车间动态调度的完全并行NSGA‑II算法，通过在GPU上运行NSGA‑II的所有步骤，最小化CPU和GPU之间的传输成本，提高算法在求解复杂问题时的效率；保留NSGA‑II的核心结构，特别是快速非支配排序、拥挤距离计算和精英保留操作，不会牺牲算法的求解精度，确保帕累托最优解集的质量。
申请人信息
- 申请人:北京工业大学
- 申请人地址:100124 北京市朝阳区平乐园100号
- 发明人: 北京工业大学
专利详细信息
| 项目 | 内容 |
|---|---|
| 专利名称 | 一种适用于柔性作业车间动态调度的完全并行NSGA-II算法 |
| 专利类型 | 发明申请 |
| 申请号 | CN202311800963.5 |
| 申请日 | 2023/12/26 |
| 公告号 | CN117764150A |
| 公开日 | 2024/3/26 |
| IPC主分类号 | G06N3/126 |
| 权利人 | 北京工业大学 |
| 发明人 | 罗佳 |
| 地址 | 北京市朝阳区平乐园100号 |
专利主权项内容
1.一种适用于柔性作业车间动态调度的完全并行NSGA-II算法，其特征在于，在GPU上运行NSGA-II的所有步骤且不改变NSGA-II的核心结构；具体包括以下步骤：在CPU端为POP、RANK和CROWD分配内存，在GPU端为d_POP、d_RANK和d_CROWD分配内存；在CPU上随机初始化POP中所有个体的#chrom；将CPU端的POP、RANK和CROWD中的普通变量和指针变量按要求复制给GPU端的d_POP、d_RANK和d_CROWD；在GPU上启动内核函数初始化d_POP、d_RANK和d_CROWD；在GPU上启动内核函数fast_nondom_first_front<<<blocks, threads>>>(d_POP, d_RANK, ps)，设置第一层非支配层；利用for循环，在GPU上多次重复启动内核函数fast_nondom_other_front<<<blocks, threads>>>(d_POP, d_RANK, k)；第k次启动所述内核函数(k从0开始计数)时，以设定第k+1层非支配层，总计启动该内核函数ps-1次；利用for循环，计算个体关于第k个目标的拥挤距离，并进行累加；在GPU上启动内核函数，采用双调合并排序，逐行对d_CROWD的元素按#value以递减顺序排序；在GPU上启动内核函数dummy_fitness<<<blocks, threads>>>(d_RANK, d_CROWD, base, ps)；利用while循环，生成新一代d_POP；将GPU端的d_RANK中的普通变量按要求复制给CPU端的RANK；最后，释放CPU端和GPU端已分配的内存。