一种改进的粒子群算法求解作业车间调度问题

摘要

本发明提出了一种改进的粒子群算法求解作业车间调度问题，该算法涉及作业车间调度技术领域。本发明为了解决传统粒子群算法对离散的优化问题处理不佳，且容易陷入局部最优的问题。所以对此进行了改进，首先，在传统PSO随机产生初始解的方法上进行了改进：引进加权平均法设置粒子的初始解；其次，对均值偏移算法做改进：运用改进的均值偏移算法对初始解进行下一步状态的预测，将预测解与当前最优解做比较，将其中更好的解作为当前最优解，解决了粒子群算法中没有考虑到的粒子信息异常变动的情况；再次，引入禁忌搜索算法对粒子信息进行进一步更新，正好解决了粒子群算法容易陷入局部最优的问题。

主权项

一种改进的粒子群算法求解作业车间调度问题，本发明涉及作业车间调度领域，具体地涉及用算法求解作业车间调度问题，其特征在于：该算法的具体步骤如下：步骤1：初始化算法参数：包括PSO粒子的数目、位置和速度等信息；步骤2：获得初始最优解：采用加权法平均法设置初始粒子的优先级，得到初始最优解：步骤2.1：给每个粒子编号；步骤2.2：统计所有粒子的速度的和，用每个粒子的速度除速度和，得到每个粒子的优先权值；步骤2.3：按照优先权大小决定粒子的先后顺序，优先权值大的工件优先执行；步骤3：获得传统当前最优解：用粒子群算法更新粒子信息，得到当前传统粒子群算法当前最优解；步骤4：预测当前最优解：加入一种改进的均值偏移算法，用均值偏移算法在初始最优解的基础上对每个粒子的位置和整体位置进行预测：步骤4.1：初始化粒子位置信息；步骤4.2：确定当前粒子群中心；步骤4.3：计算粒子群权值矩阵；步骤4.4：计算粒子权值；步骤4.5：用高低点法预测下一步粒子的位置和速度；步骤4.6：计算相似函数；步骤4.7：计算均值偏移向量，由均值偏移向量确定粒子群最优预测位置和速度；步骤4.8：循环执行步骤4.2到步骤4.7，直到满足退出条件；步骤5：初选当前最优解：用粒子群算法的评判标准，将预测的最优位置和速度与群体以往最好位置和速度做比较，将更好的位置信息作为当前最好的位置信息；步骤6：确定当前最优解：执行禁忌搜索算法，找到当前最优解：步骤6.1：给定一个当前解和一种领域结构，然后在当前领域结构内确定若干候选解；步骤6.2：若其最佳候选解对应的目标函数优于已保留的最好解，则忽视其禁忌特性，用其代表当前解和最好解，并将相应的特性加入到禁忌表中，同时对禁忌表进行修改；步骤6.3：若不存在上述候选解，则在候选解中选择非禁忌的最好解作为新的当前解，而无视它与当前解的优劣，同时将解的响应特性加入禁忌表中，同时修改禁忌表；步骤6.4：循环步骤6.1到6.3，直到满足停止准则；步骤7：循环执行步骤2到步骤6，直到达到停止条件。