多目标柔性调度问题的并行粒子群算法的分析与实现

多目标粒子群优化(Multi-objective Particle Swarm Optimization, MOPSO)算法是一种群体智能优化算法。根据外部档案的维护策略、全局最好位置的选取方法和自身最好位置更新方法等方面的不同,多目标粒子群优化算法形成了不同的分支。比较经典的多目标粒子群优化算法有CMOPSO算法、MOCLPSO算法、PAMOPSO算法等。本文通过分析粒子的运动速度和位置更新方式,编程实现了这三种经典的多目标粒子群优化算法,并以收敛性和多样性作为度量指标分析了这三种经典PSO算法在不同测试函数中的性能优劣。实验结果表明,MOCLPSO算法在多样性方面较好,而PAMOPSO算法在收敛性方面较好。 计算机图形处理器GPU和并行编程平台CUDA的出现进一步推动了并行粒子群算法的发展。本文编程实现了基于CUDA平台的基本PSO算法。在其它条件相同的情况下,基本PSO算法在GPU上运行比在CPU上运行速度更快而收敛性基本相同；在固定维数而改变粒子数目的情况下,基本PSO算法在GPU和CPU下运行时间均随种群的增加而增加,并且加速比也随之增加；在固定粒子数而改变维数的情况下,基本PSO算法在GPU和CPU下运行时间均随维数的增加而增加,但加速比几乎不变。在种群大小与维数均不变的情况下,基本PSO算法中测试函数越复杂,则加速比越高。 多目标柔性作业调度问题是指在并行机和多功能机并存的作业车间内将各工件的工序合理安排在机器上以确定各工序的开工时间,并优化给定的多个性能指标。本文在实现MOPSO算法和CUDA平台下的PSO算法基础上,以制造周期、机器总负荷和关键机器负荷最优为目标,采用GPU下并行多目标粒子群优化算法(MOPSO)与模拟退火算法(SA)相结合的混合算法求解多目标柔性作业调度问题。实现算法中,MOPSO算法主要用于为每个工序分配合适的机器,SA主要作为嵌套在PSO算法中的子程序进行粒子适应度评价和对各机器上的工序排序进行局部优化。首先进行编码设计、参数设置和适应度函数的选取,然后根据权值函数计算出外部档案中的最优解作为输出结果,并将运行结果与暂时分解法(TD)和经典遗传算法(GA)进行对比。实验结果表明,并行混合算法在调度优化结果和时间复杂性方面性能较好。