针对多目标柔性作业车间调度问题的含救济算子的混合遗传算法

摘要

一种针对多目标柔性作业车间调度问题的含救济算子的混合遗传算法。该算法第一阶段为准备阶段，产生N_pop个初始解，更新精英组，更新救济空间，通过相对重要性确定各目标函数加权值，计算适应度函数值；第二阶段，对种群中的解同时进行遗传搜索、局部搜索和信念算子（只对劣解执行信念算子），然后使用轮盘赌选择法从产生的解中选择N_pop个解；第三阶段为迭代，即重复上述过程（只有第一代需要产生初始解），直至迭代指定次数，最后更新精英组。本算法通过将遗传搜索、局部搜索和救济算子对每个解同时执行，大大提高了对每个解的利用程度，改进了传统的混合遗传算法。此外，新的编码方式简化了编码过程，根据相对重要性确定各目标函数权值的方法使权值的确定更加符合实际情况。

主权项

一种针对多目标柔性作业车间调度问题的含救济算子的混合遗传算法，该算法用于作业车间技术领域，该算法在具备全局搜索与局部搜索的同时，优化了各解的利用率，其特征是：该算法采用了一种通过各目标的相对重要性（各目标函数间的相对重要性通常由生产者根据实际情况得出）来为各目标函数赋加权值的方法；该算法对每个解同时进行遗传搜索和局部搜索；该算法在对每个解进行遗传搜索与局部搜索的同时，对劣解执行救济算子；该算法在局部搜索中，只随机选取每个当前解的部分邻域解进行检测；该算法设置精英组保存搜索过程中发现的非支配解该算法的流程如下：步骤一—初始化种群1）根据生产信息分别产生全部工件的工序集W（式（1））和全部工序的机器集M_ij（式（2））；2）按照工序集中工序的顺序，依次从相应工序的机器集中随机选择一台机器，以机器集中的编号组成机器选择部分的编码；3）根据每个工件的工序数产生相应个数的数值为工件编号的数，并将这些数随机排列组成工序序列部分的编码；4）机器选择部分的编码在前，工序序列部分的编码在后，将它们组合；5）返回本步骤2，直至已经产生N_pop个解；步骤二—更新精英组1）将当前种群中的非支配解复制入精英组；2）检测精英组中的解，将被其他解所支配的解从精英组中删除；步骤三——更新救济空间1）选择工件随机选择一个工件；2)确定救济空间对于机器选择部分，从最优解将被选择工件的工序所使用的加工机器编号提取；对于工序序列部分，从最优解中将被选择工件的工序的位置提取，将提取到的信息记入救济空间；步骤四—计算适应度函数值1)根据生产者给出的相对重要性关系，通过式（9）、式（10）、式（11）确定各目标函数的加权值；2)通过式（6）计算每个解的适应度函数值；步骤五——遗传搜索1）随机选择N_pop/2个个体；2）交叉随机将被选择的解两两一组作为一对父代解；对每个解的机器选择部分使用如图9所示的两点交叉算子进行交叉，对每个解的工序序列部分采用如图10所示的基于工序编码交叉算子进行交叉；3）根据突变概率P_m计算进行交叉的解的数目，并随机选出相应数目的解；对每个解的机器选择部分和工序序列部分分别采用如图11所示的突变算子和如图12所示的突变算子进行突变步骤六—局部搜索（与步骤五同时进行）步骤七——救济算子（与步骤五同时进行）步骤七—选择采用轮盘赌选择法选择：1）通过式（12）计算每个个体（x_i）被遗传到下一代的概率P（x_i）；2）通过式（13）计算每个个体（x_i）的积累概率q_i；3）在[0，1]之间产生一个随机数r；4）如果r< q₁，则个体x₁被选择；如果q_k‑1<r≤q_k，则选择个体x_k；5）对3、4重复N_pop次，以选择到N_pop个个体；步骤八—迭代如果算法已经迭代了指定次数，则执行下一步骤（更新精英组）；否则，返回步骤二；步骤九—更新精英组1）将当前种群中的非支配解复制入精英组；2）检测精英组中的解，将被其他解所支配的解从精英组中删除。