一种求解车间作业调度问题的混合遗传模拟退火算法

摘要

本发明通过算法求解车间作业调度问题。针对遗传算法的局部搜索能力较差，但是把握搜索过程总体的能力较强，而模拟退火算法具有较强局部搜索能力，但模拟退火算法却对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域等问题，本发明将遗传算法与模拟退火算法相互结合，取长补短，提出了一种遗传模拟退火（GASA）混合算法，该算法先对种群执行选择、交叉、变异等遗传操作来产生新的种群，然后对新种群中各个体分别进行模拟退火过程，并以其结果作为下一步遗传操作的输入，这个运行过程经过反复迭代，直到满足某个终止条件为止。

说明书

技术领域

本发明涉及制造执行系统领域，具体来说就是通过算法求解车间作业调度问题（Job-Shop Scheduling Problem）。 

背景技术

车间作业调度问题（Job-Shop Scheduling Problem）是制造执行系统研究的核心和重点之一，它的研究不仅具有重大的现实意义，而且具有深远的理论意义。车间作业调度问题，简称JSP，就是根据产品制造需求合理分配产品制造资源，进而达到合理利用产品制造资源、提高企业经济效益的目的。JSP是产品制造行业中共存的问题，它与CIMS中的工厂管理、产品制造层次紧密相关，是CIMS领域中研究的重要课题。JSP是一个典型的NP-hard问题,它的研究必然会对NP问题的研究起到有意义的影响。 

JSP研究的难度较大，这不仅仅由于JSP本身是一个NP-hard问题，而且还由于JSP研究具有离散性、随机性、多目标性、多约束性和复杂性，所以有学者把JSP研究喻为“NP-hard之NP-hard”。目前精确算法主要有分支定界法、基于析取图模型的枚举方法、混合整数规划模型和拉格朗日松弛法等，这些算法虽然能保证得到全局最优解，但需花费较长的时间且只能解决小规模的车间调度问题，与车间实际调度应用还有较大的差距。 

遗传算法（Genetic Algorithm，GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的。其基本思想是力求模仿自然界寻优过程中的随机性、鲁棒性和全局性。将遗传算法应用于车间作业调度问题，可以利用其良好的全局搜索能力，快速地将解空间中的全体解搜索出，而不会陷入局部最优解的快速下降陷阱；并且利用它的内在并行性，可以方便地进行分布式计算，加快求解速度。但是遗传算法的局部搜索能力较差，导致单纯的遗传算法比较费时，在进化后期搜索效率 较低，容易产生早熟收敛的问题。 

模拟退火算法（Simulated Annealing，SA）是基于金属退火的机理而建立起来的一种全局最优化方法，它能够以随机搜索技术从概率意义上找出目标函数的全局最优点。该算法能有限度的接受“不好”的解，具有原理简单、使用灵活等优点，并且可以跳出局部最优解，能找到全局最优或者近似全局较优的解。但SA算法对退温历程依赖性很强，并且它的全局收敛性对退温条件的要求十分苛刻，因此SA算法的时间性能不好。 

发明内容

针对现有技术中存在的上述不足之处，本发明要解决的技术问题是提供一种将模拟退火算法和遗传算法结合起来的一种求解车间作业调度问题的混合遗传模拟退火算法。 

本发明为实现上述目的所采用的技术方案是：一种求解车间作业调度问题的混合遗传模拟退火算法，包括以下步骤： 

步骤1：将涉及车间作业调度问题的个体进行编码，并遗传算法与模拟退火算法所需要的参数； 

步骤2：随机产生初始种群； 

步骤3：以插入式贪婪解码算法计算个体适应度，评价个体适应度值； 

步骤4：选择下一代种群； 

步骤5：按交叉概率p_c进行POX交叉3次，从所有后代中选择最优两个染色体作为下一代； 

步骤6：按变异概率p_m进行反转变异，生成新子代个体； 

步骤7：保留上代最优个体； 

步骤8：把交叉和变异子代个体进行模拟退火操作，产生新一代种群； 

步骤9：判断是否满足终止条件：如不满足，利用t_k=α*t_k-1进行降温操作， 并把遗传代数加1，返回步骤3；如满足终止条件，则输出当前最优个体。 

所述将涉及车间作业调度问题的个体进行编码的方法为：染色体由所有工件的一个排列构成，给同一工件的所有工序指定相同的符号，然后根据它们在给定染色体中出现的顺序进行解码。 

所述插入式贪婪解码算法包括以下步骤： 

步骤3.1：初始化工件i当前允许操作的工序号数组k[i]=1,(i=1,2,...,n)；工件i目前的最早允许加工时间t[i]=0,(i=1,2,...,n)； 

步骤3.2：i从1到                                                  对每个i做步骤3.3到步骤3.5； 

步骤3.3：得到加工工件s[i]的机器号p； 

步骤3.4：从工件s[i]的前一工序k[s[i]]-1的完成时间t[s[i]]开始，在机器p上从前向后依次判断各加工空闲时间能否将此工序插入；若能，则在空闲中插入加工，并修改该机器上的加工队列；否则，以当前时刻加工该工序，将此工序排在该机器当前队列的末尾； 

步骤3.5：修改记录工件s[i]的目前最早允许加工时间t[s[i]]；令k[s[i]]=k[s[i]]+1；修改机器p的工件工序分配链表ML[p]； 

其中，s为染色体，s[i]为基因，ML[i]是机器i的工件工序分配链表工件，s[i]能在机器p上空闲时间段[a，b]插入加工的条件为： 

max{t[s[i]],a}+T[s[i],k[s[i]]]≤b 

其中：t[s[i]]为工件s[i]目前的最早允许加工时间，即前一工序的完成时间；T[s[i],k[s[i]]为工件s[i]的当前工序k[s[i]]在机器p上的加工时间。 

所述选择下一代种群包括以下步骤： 

计算群体中每个个体在下一代群体中的生存期望数目： 

$N_i=M*F_i/{\Sigma }_{i=1}^M{F}_i(i=\mathrm{1,2},...,M)$

其中，M表示群体的个数，即随机生成的染色体个数；F_i表示第i个个体的染色体适应度值； 

取N_i的整数部分[N_i]为对应个体在下一代群体中的生存数目，确定出下一代M个群体中的   个个体； 

以   为各个个体的新的适应度，使用比例选择方法来随机确定下一代群体中还未确定的   个个体。 

所述POX交叉包括以下步骤： 

首先随机划分工件集{1,2,…,n}为两个非空子集J₁和J₂； 

复制父染色体V₁包含在J₁的工件到子染色体V₁′，父染色体V₂包含在J₁的工件到子染色体V₂′，保留这些工件的位置； 

复制V₂包含J₂的工件到V₁′，V₁包含J₂的工件到V₂′，保留这些工件的顺序。 

所述反转变异包括以下步骤： 

在父染色体中，随机选择两个位置作为变异位置进行变异操作； 

将所选取的两个位置之间的子基因串反转，形成新的染色体。 

所述保留上代最优个体采用精英保留策略，其实施方法是：如果当代种群中的最优个体比之前的最优个体还要好，则用前者替换后者，更新最优个体；否则，最优个体保持不变，并用其替换当代种群中的最差个体。 

所述模拟退火操作包括以下步骤： 

令初始当前状态S=V_i，初始最优解S^*=V_i，p_t=0； 

设置循环计算器，为其赋值为0； 

由状态S产生新状态S′，计算增量Δc′=c(V_i′)-c(V_i)； 

若Δc′＜0，则接受S′为当前状态并判断c(S′)是否小于c(S^*)；若是，则令S^*=S′,p_t=0；否则，无操作； 

若Δc′＞0，以概率exp(-Δc′/t_k)接受S′为当前状态，若S′被接受，则令S′=S,p_t=0；否则p_t=p_t+1； 

判断p_t≥L₁是否为真，即当前状态连续L₁步是否保持不变；若是，则终止循环计数器； 

若循环计算器小于终止步数，则对其进行加1操作，转至“由状态S产生新状态S′”步骤；所述终止步数为马尔科夫链长； 

将当前最优解S^*赋值给V_i； 

重复上述过程直到对种群中各个个体都分别进行了SA抽样搜索。 

本发明具有以下优点及有益效果： 

1.本无人机地面控制箱将无人机所需要的多个功能相结合，组成一站式无人机操控系统，方便了用户的使用。 

2．操作简单，使无人机的操作更加方便。 

3.采用改进的抽样过程，在算法搜索过程保留中间最优解，并即时更新，设置阈值使得在尽量保持最优性的前提下减少计算量，提高搜索效率。 

附图说明

图1为本发明的算法流程图； 

图2为POX交叉的一个实例； 

图3为交叉概率自适应变化曲线； 

图4为反转变异法（INV）的一个实例； 

图5为变异概率自适应变化曲线。 

具体实施方式

下面结合附图及实施例对本发明做进一步的详细说明。 

为了克服传统遗传算法解决车间作业调度问题的局限性，本发明将模拟退火算法和遗传算法结合起来，提出了一种新型遗传模拟退火（GASA）混合算法。遗传算法的局部搜索能力较差，但是把握搜索过程总体的能力较强；而模拟退火算法具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解，但模拟退火算法却对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域，从而使得模拟退火算法的运行效率不高。但如果能将遗传算法与模拟退火算法相互结合，相互取长补短，则可开发出性能优良的全局搜索算法，该算法先对种群执行选择、交叉、变异等遗传操作来产生新的种群，然后对新种群中各个体分别进行模拟退火过程，并以其结果作为下一步遗传操作的输入，这个运行过程经过反复迭代，直到满足某个终止条件为止。 

编码与解码，编码就是设计一种码制将问题的状态空间与可行解空间联系起来，解码是将染色体编码还原为决策变量实际值的过程。编码方式采用的是一种基于工序的直接编码方式，该编码优点是编码、解码简单，解码和置换染色体后总能得到可行的调度方案，不存在编码非法性问题；且柔性高，结合适当的解码器，就能满足调度规模变化、工件工序数不定和加工路线可变等各种复杂情况，同时可避免由于前述双重约束带来的死锁问题。解码算法采用一种插入式贪婪解码算法，能确保染色体经过解码后产生主动调度。插入式贪婪解码方法的描述如下：首先将染色体看作工序的有序序列，根据工序在该序列上的顺序进行解码，序列上第1道工序首先安排加工，然后取序列上第2道工序，将其插入到对应机器上最佳可行的加工时刻安排加工，以此方式直到序列上所有工序都安排在其最佳可行的地方。 

适应度函数设计，对于Job-Shop调度问题，通过求解最大的或较大的适应度函数值来得到一种最优的或较优的调度方案。本发明采用如下的适应度变换方法： 

f_n=k/(p_n-b) 

式中p_n为目标函数（目标值为最大的完工时间）；k和b为常数，用来控制适应度值的大小和比例；f_n为个体适应度。从式中可以看出，当b取值较小时，即使差的个体也存在生存机会，这样就能保证种群的多样性。 

选择操作，为了提高算法的收敛性和效率的一种方式，该操作通过让适应度值较大的个体保留生存和让适应度值小的值淘汰的方式来避免优良的基因丢失。采用无回放随机余数选择，该方法结合了确定性采样法和基于轮盘赌的比例选择法的优点。这种选择方法的选择误差比较小，可以保证适应度比平均适应度大的一些个体一定能够被遗传到下一代群体中，保证了群体较高的适应度值。 

交叉操作，能够对有效模式的破坏概率降低，从而保证算法在问题解空间内向最优解方向进行有效地搜索。本发明采用基于工序编码POX交叉法，且交叉概率采用自适应调整，自适应交叉概率是随着进化过程的进行自适应调整的，其变化曲线如图3所示，其定义如下： 

$p_c=\left(\begin{array}{c}{p}_{c1}-\frac{(p_{c1}-p_{c2})(f^{\prime }-f_{\mathrm{avg}})}{f_{\max }-f_{\mathrm{avg}}},f^{\prime }\ge f_{\mathrm{avg}}\\ p_{c1},f^{\prime }<f_{\mathrm{avg}}\end{array}\right)$

式中：p_c1=0.9,p_c2=0.6;f_max为群体的最大适应度；f_avg为每代群体中的平均适应度值；f′为要交叉的两个个体中较大的适应度值；p_c为求得的交叉概率。每一组交叉操都会进行3次，然后从所有后代中选择最优两个染色体作为下一代。 

变异操作，目的是为了保持种群的多样性，避免出现由于种群单一而使得最终得不到全局的最优解的现象。采用反转变异法，且变异概率采用自适应调整，自适应变异概率是随着进化过程的进行自适应调整的，其变化曲线如图5所示，其定义如下： 

$p_m=\left(\begin{array}{c}{p}_{m1}-\frac{(p_{m1}-p_{m2})(f_{\max }-f)}{f_{\max }-f_{\mathrm{avg}}},f\ge f_{\mathrm{avg}}\\ p_{m1},f<f_{\mathrm{avg}}\end{array}\right)$

式中：p_m1=0.1,p_m2=0.001；f_max为群体的最大适应度；f_avg为每代群体中的平均适应度值；f为要变异的个体适应度值；p_m为求得的变异概率。 

精英保留操作，目的是使已获得的进化成果不丧失。 

模拟退火操作，对交叉和变异后的染色体进行改进，以改善解的质量，并将改善的特性传递到下一代中，加快遗传算法的收敛速度。 

在本发明插入该操作，能保证经过交叉和变异后得到的进化成果不丧失。 

本发明采用改进的抽样过程，在算法搜索过程保留中间最优解，并即时更新，设置阈值使得在尽量保持最优性的前提下减少计算量，提高搜索效率。 

求解Job-Shop调度问题的GASA混合算法，其具体执行步骤如图1所示，执行步骤如下： 

步骤1：设计GASA混合算法的编码方式以及对应的遗传算子，并设置相应的种群大小、交叉概率、变异概率、初始温度、衰减系数等遗传算法与模拟退火算法所需要的各种参数。 

步骤2：随机产生初始种群。 

步骤3：解码计算个体适应度，评价个体适应度值。 

步骤4：按无回放随机余数选择策略选择下一代种群。 

步骤5：按交叉概率p_c和POX交叉3次，从所有后代中选择最优两个染色体作为下一代。 

步骤6：按变异概率p_m和INV，生成新子代个体。 

步骤7：采用精英保留策略保留上代最优个体。 

步骤8：把交叉和变异子代个体进行模拟退火操作，产生新一代种群。 

步骤9：判断是否满足终止条件。如不满足，利用t_k=α*t_k-1进行降温操作，并把遗传代数加1，返回步骤3；满足终止条件，则输出当前最优个体，算法结束。 

所述的编码方法，其具体实施方案如下：染色体由所有工件的一个排列构成，操作时给同一工件的所有工序指定相同的符号，然后根据它们在给定染色体中出现的顺序进行解码；对于一个共有n个工件在m台机器加工的调度问题，其染色体由n*m个基因组成，每个基因不表明一个工件的具体工序，而是指有上下依赖关系的工序。每个工件序号只能在染色体中出现m次，从左到右扫描染色体，对于第k次出现的工件序号，表示该工件的第k道工序。 

所述的插入式贪婪解码算法，其具体过程如下： 

步骤1：初始化工件i当前允许操作的工序号数组k[i]=1,(i=1,2,...,n)；工件i目前的最早允许加工时间t[i]=0,(i=1,2,...,n)。 

步骤2：i从1到   对每个i做步骤3到步骤5。 

步骤3：得到加工工件s[i]的机器号p。 

步骤4：从工件s[i]的前一工序k[s[i]]-1的完成时间t[s[i]]开始，在机器p上从前向后依次判断各加工空闲时间能否将此工序插入。若能，则在空闲中插入加工，并修改该机器上的加工队列；否则，以当前时刻加工该工序，将此工序排在该机器当前队列的末尾。 

步骤5：修改记录工件s[i]的目前最早允许加工时间t[s[i]]；令k[s[i]]=k[s[i]]+1；修改机器p的工件工序分配链表ML[p]。 

步骤6：结束。 

算法中s为染色体，s[i]为基因，ML[i]是机器i的工件工序分配链表工件，s[i]能在机器p上空闲时间段[a，b]插入加工的条件为： 

max{t[s[i]],a}+T[s[i],k[s[i]]]≤b 

其中：t[s[i]]为工件s[i]目前的最早允许加工时间(即前一工序的完成时间)，T[s[i],k[s[i]]为工件s[i]的当前工序k[s[i]]在机器p上的加工时间。 

所述的无回放随机余数选择，其具体过程如下： 

步骤1：计算群体中每个个体在下一代群体中的生存期望数目：    其中M表示群体的个数，即随机生成的染色体个数；F_i表示第i个个体的染色体适应度值。 

步骤2：取N_i的整数部分   为对应个体在下一代群体中的生存数目。这样共可确定出下一代M个群体中的   个个体。 

步骤3：以   为各个个体的新的适应度，使用比例选择方法来随机确定下一代群体中还未确定的   个个体。 

所述的基于工序编码POX交叉法(Precedence Operation Crossover，POX)，其具体过程如下，图2为其的一个实例： 

步骤1：首先随机划分工件集{1,2,…,n}为两个非空子集J₁和J₂。 

步骤2：复制父染色体V₁包含在J₁的工件到子染色体V₁′,父染色体V₂包含在J₁的工件到子染色体V₂′，保留它们的位置。 

步骤3：复制V₂包含J₂的工件到V₁′,V₁包含J₂的工件到V₂′，保留它们的顺序。 

所述的反转变异法（INV），其具体过程如下，图4为其的一个实例： 

步骤1：在父染色体中，随机选择两个位置作为变异位置进行变异操作。 

步骤2：将步骤1中所选取的两个位置之间的子基因串反转，形成新的染色体。 

所述的精英保留策略，其实施方法是：如果当代种群中的最优个体比之前的最优个体还要好，则用前者替换后者，更新最优个体；否则，最优个体保持不变，并用其替换当代种群中的最差个体。 

所述的模拟退火操作的抽样过程，其具体过程如下： 

步骤1：令初始当前状态S=V_i，初始最优解S^*=V_i,p_t=0。 

步骤2：设置循环计算器，为其赋值为0； 

步骤3：由状态S产生新状态S′，计算增量Δc′=c(V_i′)-c(V_i)。 

步骤4：若Δc′＜0，则接受S′为当前状态并判断c(S′)＜c(S^*)，若是，则令S^*=S′,p_t=0。若Δc′＞0，以概率exp(-Δc′/t_k)接受S′为当前状态，若S′被接受，则令S′=S,p_t=0；否则p_t=p_t+1。 

步骤5：判断p_t≥L₁是否为真，即当前状态连续L₁步保持不变，若是，则终止循环。 

步骤6：若循环计算器小于终止步数（马尔科夫链长），则对其进行加1操作，转步骤3。 

步骤7：将当前最优解S^*赋值给V_i。 

步骤8：重复上面1-7过程直到对种群中各个个体都分别进行了SA抽样搜索。