法律状态公告日
法律状态信息
法律状态
2019-12-03
授权
授权
2017-01-11
实质审查的生效 IPC(主分类):G06Q10/04 申请日:20160718
实质审查的生效
2016-12-14
公开
公开
技术领域
本发明涉及一种基于改进粒子群优化的总拖期运输计划调度算法。
背景技术
总拖期运输计划调度问题(TTP)是调度问题中的经典难题，其包含了很多不同的子问题，总体上根据机器的配置分为单机(single machine)总拖期和多机(multimachines)总拖期运输计划调度问题。其中，单机总拖期运输计划调度问题的不同情况又分相同到达时间(equal release time)，不同到达时间(unequal release time)以及带权重的单机总拖期运输计划调度问题(the single machine total weighted tardinessproblem，SMTWTP)。多机总拖期运输计划调度问题包括并行多机(parallel machine)，流水车间(flow shop)和工作车间(job shop)总拖期。本文重点研究的是并行多机总拖期运输计划调度问题(P//T)，机器配置环境是m台功能无差别的等同机器，所有的机器在零时间就准备就绪，并且可连续的处理工作的加工，但是当机器正在加工一工作时，不允许打断以及被优先级高的工作中断处理。
目前在大型工厂中，需要实现设备工作时间最优配置才能满足目标函数，也就是总拖期值最小。但是现有的自动化工厂设计算法多种多样，无论在内部数据处理效率，还是应对多种变量情况下确定的解的优化度，都存在有待提高的地方。
发明内容
有鉴于此，本发明在蚁群算法的基础上，针对并行多机总拖期运输计划调度问题(P//T)的特性，提出了基于启发式规则的改进蚁群算法(Heuristic Ant ColonyOptimization，hACO)，并对算法进行了性能优化的研究，提供了一种基于改进粒子群优化的总拖期运输计划调度算法。
为了解决上述技术问题，本发明的技术方案是：一种基于改进粒子群优化的总拖期运输计划调度算法，步骤1，根据输入变量构建总拖期值数学模型，定义待加工工作数n和机器数m，以及每一待加工工作加工所需时间pj和交货期限dj,，则对于模型P＝(S,f,Ω)存在以下集合：工作集合J＝{J1,J2,…,Jn}，每一个Ji具有两个属性加工时间pi和交货期限di；机器集合M＝{M1,M2,…,Mm}，F(Ma)＝F(Mb)，(a≠b,0≤a,b≤m)；工况集合D＝{dij|i∈[1,n],j∈[1,m]}，dij表示将工作i调度置机器j上加工；有序集s＝{x12,xij,…}，其中xij∈D，且|s|＝n，所有s构成解空间S，
进一步地，步骤2中，在t＝0时刻，按照机器的序号以递增方式优先选择工作加工；当出现两台机器同时完成工作加工，则依然按照机器序号的递增顺序优先选择工作加工；当出现两台机器同时完成工作加工，则依然按照机器序号的递增顺序优先选择工作加工。在调度加工序列时，首先按照规定1在0时刻让每台机器选择第一个加工工作，每当完成一次加工，则将此工作的机器属性设为当前机器，然后重复规则2和规则3选择工作，直到所有工作均被加工完毕，即可得到无二义性的加工序列。下面具体比较两种构造方法的复杂度：假设P//T问题规模为n×m，复杂构造图方法所需要使用的构造节点数为n×m+2，而简单构造图方法只需要n+2个节点数。虽然简单构造图需要另外n个空间存放工作所被加工的机器，但是简单构造方法还是很大程度上降低了复杂性。进一步估算在复杂图和简单图下要最终求得一次解需要大概要进行的选择情况大小，分别为：
复杂构造图：
简单构造图：
由上两式可见，简单构造图在构造上要简单于复杂构造图，并且更加直观。除此之外，简单构造图方法在应用到蚁群算法(Ant Colony Optimization，ACO)中可以降低信息素的空间，提高随机概率选择的速度，以及更新信息素的开销。
进一步地，步骤3中，状态转移规则为：
>
式中，q0(0≤q0≤1)是一个调节参数，q是随机产生的介于[0,1]之间的均匀分布随机数，η为启发式信息，τ为信息素，当q≤q0时，选择当前最优节点，当q>q0选择随机方式探索。选择条件最好的节点，这也充分地利用(exploit)了蚁群目前所留下的信息。
进一步地，当q>q0时，采用如下公式进行随机探索。
>
进一步地，启发式信息确定方式为，sptj＝pj，将待加工工作按照短的加工时间非递减顺序排列，则ηij＝1/sptj。
进一步地，启发式信息确定方式如下，eddj＝dj，将待加工工作按照最早交货期限非递减顺序排列，则ηij＝1/eddj。
进一步地，启发式信息确定方式为：mddj＝max{C+pj,dj}，C表示为目前已加工的工作加工总时间，将工作以非递减顺序排列工作，则ηij＝1/mddj。启发式信息η是状态转移规则中的重要因素，它在一定程度上影响着蚂蚁选择节点时的倾向，对节点的好坏起着初步的判定作用。在求解单机总拖期运输计划调度问题时常被使用的是SPT规则，EDD规则，MDD规则。SPT意味着最短加工时间的工作被优先选择的概率大，而EDD则表示根据工作交货时间的紧急为判断依据。修改后的交货期限MDD其质上是按照工作能够实际加工完毕的最迟交货期限排列。虽然工作能够在交货期限前加工完毕，但是仍然等到交货期限到时再提交。在蚁群系统算法(Ant>
进一步地，步骤3中，信息素更新规则为：交替使用全局信息素更新和局部信息素更新；所述全局信息素更新规则为：τij(t+1)＝(1-ρ)·τij(t)+ρ·Δτij。
其中，
进一步地，步骤3中，当判断搜索处于停滞状态时，通过PTS策略重新部署信息素都恢复到τ0或τmax初始值。为了避免算法陷于搜索停滞，本文对两种算法皆使用了信息素重新初始化的策略。即在判断算法陷于停滞后，使用PTS策略重新部署信息素都恢复到0或max初始值。
进一步地，步骤3中，还包括局部搜索算法，步骤3-1，分别对每一台机器的加工序列使用单机局部搜索；步骤3-2，验证机器k是否满足公式
本发明技术效果主要体现在以下方面：本发明在蚁群算法的基础上，针对并行多机总拖期运输计划调度问题的特性，提出了基于启发式规则的改进蚁群算法，具体为：一、设计了将ACO用于求解P//T的复杂解构造模和简单解构造模型，其中，简单解构造模型在复杂解构造模型的基础上利用P//T的数学模型以及无差别机器的特性而提出；二、针对ACO求解P//T，提出了基于P//T分解原则的侯选列表构造方法，信息素更新策略以及改进局部搜索算法。三、本发明同时对算法进行了性能优化的研究，以提高事件最优解的确定精度，以及保证对内部数据的处理筛选效率。
附图说明
图1：真实世界中的蚂蚁觅食示意图；
图2：蚁群算法基本步骤图；
图3：二维矩阵的单机总拖期蚁群算法求解问题模型图；
图4：本发明4×3的P//T解的复杂构造图；
图5：本发明4×3的P//T实际生产中的调度顺序图；
图6：本发明4×3的P//T实际生产中的调度时间工作表；
图7：本发明4×3的P//T解的简单构造图；
图8：ACS算法对Ho与Chang问题求解的每代最优值图；
图9：ACS算法分别使用三种不同启发式信息运行100次的结果分布图；
图10：50×2规模问题的三种算法结果对比图；
图11：求解100×4规模的125个不同难易程度实例的平均值分布图；
图12：不同参数运行时的平均分支因子图。
具体实施方式
以下结合附图，对本发明的具体实施方式作进一步的详述，以使本发明技术方案更易于理解和掌握。
为了进一步理解本方案，首先对蚂蚁算法做个简单说明。
1.蚂蚁算法研究
图1中，假设A点是蚂蚁的洞穴，D点是食物源，EF是一个大障碍物。由于障碍物，蚂蚁具有两条连接洞穴和食物的路径ABECD和ABFCD。BE，EC的距离为1，而BF，FC的距离为0.5，可知路径ABFCD为最短路径。假设每个时间单位有30号蚂蚁由A点到达D点，有30号蚂蚁由D到达A点，蚂蚁过后留下的信息量为1。为了方简单，设信息素只在路径上停留1。在初始时间，所有路径上均无信息素，在两点的蚂蚁可以随机的选择路径，从统计学可以认为以相同的概率选择，如图1(b)。经过一个时间单位后，在路径BCD上的信息量是路径BEC上的信息量的2倍。又再经过一个时间，将有20只蚂蚁由BFC到达D点，如图1(c)所示。随着时间的推移，蚂蚁将会以越来越大的概率选择路径BFC，最终将会完全选择路径BFC，从而找到由洞穴到食物源的最短路径。在ACO中，人工蚂蚁除了自然具有的能力外，还被赋予了记忆功能和启发计算能力，记忆能力使得蚂蚁能够记载自己的行走路线，启发计算能力使得蚂蚁能够评估转移到的下一个节点对最终解带来的好处，除此之外，在有些算法中为了提高求解效果，还对人工蚂蚁赋予了局部搜索能力，即在构造一个完整解之后，再应用局部搜索算法对其构造的解进行改进。
1.1蚂蚁系统(Ant system，AS)在解决旅行商问题(Traveling SalesmanProblem，TSP)时，首先将m只蚂蚁随机的分布于n个城市。在构造路径时，蚂蚁k通过随机比例(random proportional)规则的概率行动选择规则，决定选择下一个城市。蚂蚁k从城市i选择城市j的概率计算公式为
>
其中，
t是表示第t次迭代；
α，β是两个重要的参数，决定信息素和启发式信息对选择概率的比重；
η是启发式信息。启发式信息根据不同的实际问题有不同的定义。在TSP中，启发式信息被定义为ηij＝1/dij，dij是城市i，j之间的距离；
τij是从城市i到城市j的路径上的信息素量。在对称TSP问题中τij＝τji，而非对称TSP问题则τij≠τji；
蚂蚁k根据公式(1-1)计算每个所能到达的城市选择的概率，一般使用赌注轮盘法选择城市。α，β是非常重要的两个参数，分别控制着信息素量和启发式信息在选择城市中所起的影响作用。当α＝0时，只有启发式信息作为计算概率的依据，依照TSP中启发式信息为路径信息，所以算法实质上退化为贪婪算法。当β＝0时，ACO变为随机的搜索算法。所以α，β参数的设置对算法的优化性能起到非常关键的作用。许多学者都投入到参数设置的研究中，希望赋予参数设置的理论支持和有效的规则。
信息素更新机制作为ACO另一个核心部份，常常也成为研究的重点，众多的改进算法也理所应当的将其放在了关键的位置。在最早提出的AS算法中共有三个不同的版本，蚂蚁密度(ant-density)，蚂蚁数量(ant-quantity)和蚂蚁周期(ant-cycle)。前两者都是每当蚂蚁经过一个城市即更新所经历过的路径上的信息素量。但经实验结果表明此种信息素更新性能低劣，远远不如后者。所以在其它的ACO中都采用蚂蚁周期的方式更新信息素，即在所有蚂蚁构造出所有路径后再更新信息素，并且根据各自求得解的好坏决定信息素量。更新信息素公式如下
>
其中，
ρ是残余因子，取值0≤ρ≤1。1-ρ就表示路径上信息素量的挥发数量。使用挥发机制可以避免信息素量的无限制增加，同时可以使从未选择过的路径渐渐地被“遗忘”；
>
公式中Lk(t)是由蚂蚁k所求解到的路径长度。由上式可得知，当蚂蚁寻找的路径越短，则遗留在该路径上的信息素量就越大，以至于下一次迭代中其它蚂蚁选择这条路径的概率就越大。信息素的这种更新机制所产生的正反馈效应正好体现了蚁群的学习能力，能不断地从历史中选择最优的路径。ACO基本步骤流程如图2所示。
最初的AS提出后虽然在小规模TSP问题求解上比其它一般启发式算法性能有所提高，也优于像模拟退火或遗传算法。但是当处理大规模TSP问题时，却劣势于其它算法。AS同时也存在不足，如信息素更新采用所有蚂蚁经过的路径全部更新策略，使得算法收敛性不好。这些劣势也成为了之后改进ACO的研究重点。
1.2蚁群系统(Ant Colony System，ACS)在ACS中，蚂蚁构造路径时，采用了新的状态转移规则选择下一个城市j。此规则与Ant-Q中的方法相似，利用了蚁群的学习能力。
>
其中，
q0(0≤ρ≤1)是一个参数，决定着探索和利用之间的平衡。q是随机产生的介于[0,1]之间的均匀分布随机数。当q≤q0时蚂蚁选择概率最大的城市。当q≥q0时，蚂蚁依旧按照公式1进行选择。为改进AS更新每一只蚂蚁路径上的信息素这点不足，ACS提出了两种更新信息素策略，全局信息素更新和局部信息素更新。在全局信息素更新中，只使用全局最优(目前最优或迭代最优)蚂蚁的解路径更新信息素，从而更多的在目前最优的解附近搜索以找到更优的解。ACS引入了新的局部信息素更新，在每只蚂蚁经过的一段路径上，会减少信息素量，从而使其它蚂蚁选择该路径的概率相对减少。局部信息素更新如下：
τij(t+1)＝(1-ξ).τij(t)+ξτ0(1-5)
其中，ξ(0<ξ<1)是信息素挥发因子，τ0是信息素量的初始值在TSP问题中τ0＝1/nCnn，Cnn是由最近相邻方法得到的路径长度。
除了上述改进以外，ACS还使用了候选列表(candidate list)限制构建路径时可能被选择城市的数目。通常，使用一些启发式算法对未选择的城市进行优先级的判定。如蚂蚁位于城市i时，选择下一个到达的城市j时不在从它所能到达的所有城市中选择，而是从侯选列表中去选择，只有当侯选列表中的所有城市被访问过后才从列表外的城市选择。在TSP问题中，经实验证明侯选列表在定程度上提高了解的质量，也加快了算法的速度。
1.3最大最小蚂蚁系统(Max-Min Ant System，MMAS)另一个成功改进的蚁群算法是Thomas Stützle等人提出的最大最小蚂蚁系统MMAS。MMAS采用了上下界以限制信息素量，使得蚂蚁可以更加广泛的搜索空间，避免陷入局部最优。
不同于AS和ACS算法，MMAS算法在蚂蚁构造路径期间并不对信息素产生任何影响，在每一次迭代之后，只选择最优蚂蚁用来更新信息素，所以给出新的更新公式：
>
其中，
只选择一只蚂蚁进行信息素的更新，有可能产生搜索的停滞现象。为避免此情况的发生，就特意的限制了信息素的区间，让某些从未被选择但隐含着最优解的路径不被永久地“遗忘”。
Stützle证明了每条路径上的信息素量符合以下定理：
>
根据上式定理，MMAS算法在运行前，根据以往存在的算法求出大概的最优值，并令f(sopt)为此最优值以设定算法运行初所使用的上下界限。只在出现比目前更优的最优值时才更新上下界限。
如果搜索已经停滞，可以使用PTS方法重新初始化全局的信息素分布，如下式：
>
当δ＝0时，全局信息素不变。当δ＝1时，全局信息素重新初始化为最初值。为了在使用PTS方法后，减少使用前的解对算法产生再次的相同停滞影响，在更新后常常使用重新开始寻找到的最优值(restart best)更新信息素。
1.4ACO求解SMWTP带权重单机总拖期运输计划调度问题(Single MachineWeighted Tardiness Problem，SMWTP)是总拖期运输计划调度问题中的经典问题，而非带权重单机总拖期运输计划调度问题SMTTP是属于带权重问题的特殊问题，即每一个工作的权重为1。并且带权重单机总拖期运输计划调度问题是强条件(strong sense)下的NP-Hard难题，而非带权重单机总拖期运输计划调度问题是弱条件(weak sense)下的NP-Hard难题。
1.4.1SMWTP问题定义 带权重单机总拖期运输计划调度问题可以定义为，存在n个待加工的工作，每个工作具有三个属性：加工所需要的时间(processing time)，交货期限(due date)和超期惩罚权重(weight)。只有一台机器用于加工，并且所有工作都没有优先级别，工作加工期间也不能中断，且仅需加工一次即可完成。无优先级别的在1台机器上独立加工，加工期间也不允许中断。带权重的总拖期值TW可以计算如下：
>
其中，Ci是工作i的实际完成时间，di交货期限，pi加工时间，wi工作i的惩罚权重。带权重单机总拖期运输计划调度问题的目标函数为min(TW)，即求解最优的加工序列使得总拖期值最小。
1.4.2整合ACO求解SMWTP 其简单构造图方法可简单描述为将工作i放置在加工序列的第j个位置，此时只需要一个二维的矩阵即可表达该问题空间，如图3所示，图中○表示未被选中的加工工作，●表示已选中的工作。该图的最终加工序列为2143。简单构造图不仅理解直观，而且可以对应信息素的设计，如(i,j)也可以表示为在整个信息素空间中第i个位置放置工作j的信息素量大小。
以上是对蚂蚁算法求解总拖期运输计划调度问题的研究，而本发明基于上述基础的改进如下文所示。
2.本发明的方案内容及原理
2.1P//T定义和数学模型 P//T可以定义为，n个待加工的工作和m台功能相同且独立的机器，每个工作具有两个属性：加工所需要的时间pj，交货期限dj。并且所有工作都没有优先级别，工作加工期间也不能中断，且仅需在任一台机器加工一次即可完成。另外所有工作均在零时刻全部准备好。每一个工作如果加工后的完成时间Cj超过了交货期限，则产生超期Ti。总拖期值T计算如下：
>
P//T的目标函数为min{T}，即求解最优的加工序列使得总拖期值最小。
P//T数学定义：假设存在一个n×m的P//T问题P＝(S,f,Ω)，则存在以下集合：
工作集合J＝{J1,J2,…,Jn}，每一个Ji具有两个属性加工时间pi和交货期限di。
机器集合M＝{M1,M2,…,Mm}，由于并行多机所以机器的功能无差别F(Ma)＝F(Mb)，(a≠b,0≤a,b≤m)。
集合D＝{dij|i∈[1,n],j∈[1,m]}，dij表示将工作i调度置机器j上加工，集合D包含了所有加工的空间集合|D|＝n×m。
存在一有序集s＝{x12,xij,…}，其中xij∈D，且|s|＝n，所有s构成解空间S。
Ω为约束条件，
其目标函数f(s)＝Σmax(Ci-di,0)。模型求解目标为寻找全局最优解s*，使得f(s*)≤f(s)，
2.2P//T解构造图模型根据并行多机总拖期的数学模型，参考Dorigo在解决JSP问题中所提出的解构造表示方法，本文提出了P//T的解构造方法，具体如下。
复杂构造图：解构造图G＝(V,E)，其中V是所有加工情况的集合
V＝D∪{d0}∪{dN+1}，其中{d0}，{dN+1}是图中有特殊意义的顶点，是加工开时前的开始顶点和结束顶点。N＝|D|，表示不同加工情况的总数。
图4给出了4×3规模的P//T构造前后的图表示，即4个工作在3台机器的环境中加工。图4(a)在构造前的情形，图中省略了可供选择的有向边，因为从0点开始可以选择除了结尾点以外所有点，边太多为了清楚就未画出。每个节点以序号index标注，节点上的数字(job，machine)processing time，due date分别表示工作，工作所在加工机器，加工时间和工作的对应交货期限。顶点按照4×3矩阵排列标注可以很容易计算出工作的序号(index-1)/m，以及所在加工机器的序号(index-1)％m+1。而所需要计算的每台机器的总加工时间和总拖期值，也可直接按有向边路径根据index序号分别统计。如图4(b)，所构造的解为{0,1,3,5,12,13}，即在机器1上所加工的工作为{1}，机器2上所加工的工作是{8}，机器3上的工作{6,12}，最后得出的各机器的拖期值是0，0，10，总拖期值是10。图(b)中画横线是因为当工作i经过一次加工时即完成，无须再进行加工，所以在选择下一个节点时，第i行的节点可以全部不用考虑。
简单构造图：然而，尽管复杂构造图可以直观并且涵盖整个解的空间，但是从图(b)中可以看出，当选择了一行中的节点之后，同行中的其它节点将会被删除，并且同一行工作的属性信息(processing time and due date)是相同的。这是因为复杂构造图是参考JSP问题而得来，JSP问题中的每个工作需要每一台机器上加工，并且每台机器上所开销的时间也不相同，而P//T问题只需在一台机器上加工即可完毕，所以复杂构造图有很多信息是重复了。
为了降低构造图复杂性，首先可以根据实际的生产调度，可以得到如下图5的各个机器的加工顺序。
图5中顶点的序号index直接表示工作的序号，而顶点上面的二元组(processingtime，due date)则表示工作的加工时间和交货期限。图5中分别以三种不同的线条表示了不同的机器同步选择的工作序列{0,2,4,5}，{0,1,5}和{0,3,5}，拖期值为10，0，0，总拖期值为10。按照上面所讲述的调度顺序，进一步可以得到各台机器的加工时间表，如图6所示。
横轴t表示时间进展，纵轴表示每台机器的调度情况，每个工作上方的元组(processing time，due date)machine的前两项仍然表示工作的加工时间和交货期限，后一项则是每个工作被调度的机器序号。为了将三台机器的各自加工序列组合成一个无二义性的序列，本文特意做了以下规则：规则1，在t＝0时刻，按照机器的序号以递增方式优先选择工作加工。规则2，按实际生产情况，当每台都在加工工作时，以最先完成工作加工的机器优先选择工作加工。规则3，当出现两台机器同时完成工作加工，则依然按照机器序号的递增顺序优先选择工作加工。
在调度加工序列时，首先按照规定1在0时刻让每台机器选择第一个加工工作，每当完成一次加工，则将此工作的机器属性设为当前机器，然后重复规则2和规则3选择工作，直到所有工作均被加工完毕，即可得到无二义性的加工序列。图7描绘了按以上规则产生的加工序列。
图7即是由规则得到的加工序列{0,2,1,3,4,5}，按照三元组的机器属性则可得每台机器的加工序列分别为{2,4}，{1}，{3}，总拖期值为10。
下面具体比较两种构造方法的复杂度：假设P//T问题规模为n×m，复杂构造图方法所需要使用的构造节点数为n×m+2，而简单构造图方法只需要n+2个节点数。虽然简单构造图需要另外n个空间存放工作所被加工的机器，但是简单构造方法还是很大程度上降低了复杂性。进一步估算在复杂图和简单图下要最终求得一次解需要大概要进行的选择情况大小，分别为：
复杂构造图：
简单构造图：
由上两式可见，简单构造图在构造上要简单于复杂构造图，并且更加直观。除此之外，简单构造图方法在应用到ACO中可以降低信息素的空间，提高随机概率选择的速度，以及更新信息素的开销。
综上所述，本节中提出了复杂与简单构造图模型用于ACO求解P//T，经比较，简单构造图更加适用于蚁群算法。
2.3整合ACO与P//T在这节中，本文将针对如何应用ACO求解P//T做详细的介绍。首先，此节中使用的是简单构造图方法建立ACO的求解模型，然后实现了前面章节所介绍的两种蚁群算法ACS和MMAS，并对其针对于总拖期运输计划调度问题进行了修改。
2.3.1初始化结构 无论是复杂构造图还是简单构造图都引入了两个虚拟的节点，起始节点d0和停止节点dn+1，由于本文在设计中都将每个节点都代表不同工作，具有三个属性加工时间processing>
在算法运行前，设定两个集合G＝{d0,d1,…,dn,dn+1}，M＝{m1,m2,m3}分别表示还未调度的工作节点和可使用的机器。在算法运行时首先选择d0，以后每当将一个工作节点i在机器j上加工调度后，则更新两个集合G*＝G-{di}，M*＝M-{mj}，并且设置节点i的属性di.machine＝mj。在加工过程中机器j都是不可中断，不可抢夺的，直到工作加工完毕才能释放机器更新集合M*＝M+{mj}。
如前面小节所述，简单构造图在信息素构造时也降低了其规模，现在只需要(n+2)×(n+2)的规模大小就可以表示全局的信息素，而复杂构造图则需要(n×m+2)×(n×m+2)的规模。二维矩阵τ[i][j]，0≤i，j≤n+1，直观的表示了从节点i选择节点j的信息素量大小。
2.3.2状态转移规则 在算法初始化时，每只蚂蚁被分配到虚拟节点d0，在选择下一个节点时，ACS蚁群算法使用了“伪随机”方式使用了Q-学习的方式按一定随机比例选择最符合条件的节点，而MMAS依然使用了基本蚁群算法AS的规则。不过MMAS在某些条件下也可以借助于“伪随机”方式转移，而获得更好的求解性能。本文实现的MMAS算法也采用了此方式。
>
当q≤q0时，选择条件最好的节点，这也充分地利用(exploit)了蚁群目前所留下的信息。当q>q0时，则采用下面的随机选择方式，将蚂蚁的探索(explore)能力得到体现。
>
启发式信息η是状态转移规则中的重要因素，它在一定程度上影响着蚂蚁选择节点时的倾向，对节点的好坏起着初步的判定作用。在求解单机总拖期运输计划调度问题时常被使用的是SPT规则，EDD规则，MDD规则。
1)最短加工时间SPT：sptj＝pj，将待加工工作按照短的加工时间非递减顺序排列，则ηij＝1/sptj。
2)最早交货期限EDD：eddj＝dj，将待加工工作按照最早交货期限非递减顺序排列，则ηij＝1/eddj。
3)修改的交货期限MDD：mddj＝max{C+pj,dj}，C表示为目前已加工的工作加工总时间。规则按照MDD将工作以非递减顺序排列工作，则ηij＝1/mddj。
SPT意味着最短加工时间的工作被优先选择的概率大，而EDD则表示根据工作交货时间的紧急为判断依据。修改后的交货期限MDD其质上是按照工作能够实际加工完毕的最迟交货期限排列。虽然工作能够在交货期限前加工完毕，但是仍然等到交货期限到时再提交。
在ACS算法中，候选列表(candidate list)被应用于转移规则中，优先选择候选列表中的节点，当列表中所有的节点都被选择之后，才选择之外的节点。引入候选列表加快了算法的速度，并提高了算法的效率。Besten在处理单机带权重总拖期运输计划调度问题时也应用了候选列表，并定义选择目前最优解中前cand(0≤cand≤n)个节点作为列表候选。
但是，上述方法的解容易陷入局部最优，因为每一次最优考虑的是目前最优解中的前段那些节点。为了让候选列表能更加建立的合理，避免解陷入局部最优，本发明利用总拖期分解原则，提出了新的侯选列表构造方法。
在以EDD排序的工作加工序列中，选择以最长加工时间的工作为一个分界点，之前的工作必定将会在分界点前，而之后的工作将会在之后加工。在算法运行前构造出列表为以后的每一只蚂蚁应用。此种方法生成候选列表比Besten所使用目前最好解生成方法更加具有性质支持，并且避免了解陷入局部最优，能正确的引导蚂蚁的搜索。
2.3.3信息素更新在信息素初始化和更新时，ACS算法和MMAS算法各有不同的机制，前面章节已做出详细的比较，在此只给出计算的方法。
ACS在信息素初始化时，每条路径的初始量τ0＝1/(n·tt)，其中tt是按启发式算法KPM计算所得的结果。而MMAS是以τmax初始化信息素量，τmax＝1/(ρ·tt)。
ACS和MMAS都在每一次迭代后选择单独的一只最优蚂蚁更新信息素，前者是每一次都使用目前最优蚂蚁(best so far)，而后者会根据算法运期的阶段按不同比例分别使用迭代最优(iteration best)和目前最优蚂蚁。ACS全局更新信息素公式如下
τij(t+1)＝(1-ρ)·τij(t)+ρ·Δτij(2-6)
其中，
>
ACS除了使用全局信息素更新外，还使用了局部信息素更新，在每只蚂蚁经过的一段路径上，会减少信息素量，从而使其它蚂蚁选择该路径的概率相对减少。局部信息素更新如下
τij(t+1)＝(1-ξ).τij(t)+ξτ0(2-8)
而MMAS在更新信息素时则单一的使用全局信息素更新，不同之处在于，MMAS交替的使用目前最优和迭代最优蚂蚁更新信息素。
为了避免算法陷于搜索停滞，本文对两种算法皆使用了信息素重新初始化的策略。即在判断算法陷于停滞后，使用PTS策略重新部署信息素都恢复到τ0或τmax初始值。
2.4局部搜索 利用局部搜索对启发式算法的解进行一系列小的更改，会很大程度上提高算法的性能。ACO也使用了局部搜索，将每一只蚂蚁的解或每一次迭代最优蚂蚁的解利用局部搜索调整解，从而得出更优的解。局部搜索能适用于总拖期运输计划调度问题是因为这和总拖期运输计划调度问题本身特性有关，总拖期是将工作加工顺序排列从而获得最小化的最优值，有规则的调整工作加工的先后次序则有可能达到最优解，所以局部搜索对总拖期运输计划调度问题的性能提高是显著的。
在前面章节已经简单介绍了适用于单机情况下的局部搜索，最常用也是最有效的方法是邻接调换法(neighborhood)，包括相邻调换，交换和插入。Besten详细的阐述了三种方法的实现，并且利用了加速方法(speed up)提高了三种局部搜索算法的运行时间。
本文在三种基本算法的基础上，结合多机的特有性质，提出了适用于并行多机的局部搜索算法。首先，每一台机器总共加工时间不能超过一定值。如果存在机器k超过该值，则将其后不满足该值的工作从机器k中移除，并将其加入到符合该条件的机器的最后加工，并验证添加后仍然满足该条件，否则选择其它机器。接着，每台机器最后一个工件加工的开工时间要小于其它机器的完工时间。按照简单构造图生成步骤，每一次工作的调度都是选取了目前总加工时间最小的机器。以上两步多机间的调换，应在每台机器单独进行了局部搜索后进行。局部搜索的步聚如下：Step 1，分别对每一台机器的加工序列使用单机局部搜索。Step 2，验证机器k是否满足公式(1-2)，如果成立，跳转Step 4。Step 3，将不满足条件的工作j从机器k的加工序列中移除，寻找其它满足条件的机器k*，将工作j添加至k*，并对机器k*的调度序列重新使用单机局部搜索。Step>
以上是对本发明方案设计进行总结，而本发明中的实施内容、实验理论以及结果如下。
3.本发明的实验与结果
3.1实验测试算例 本文首先以Ho和Chang基准问题，验证算法的正确性以及算法的稳定性。Ho和Chang问题是小规模测试问题，具有15个待加工的工作和两台无性能差别的机器。虽然Ho和Chang问题的规模偏小，但是在相同规模下的求解难度是最大的，即在一半工作不超期另一半工作超期的情况下。在实验部份本文将对实例的难度做具体分析。
Ho和Chang问题的最优解为159，加工序列分别为{7,15,3,10,13,1,9}和{14,5,8,6,4,2,12,11}。
表3-1Ho和Chang的基准问题
为了测试算法在其它规模问题中的性能，本文按照总拖期运输计划调度问题被得到公认的算例随机产生方法生成了不同的算列。生成方法具体如下：
对于n个工作，m台机器的问题规模，其中每一个工作Ji，Ji的加工时间pi是服从均匀分布(1,100)的整数，而Ji的交货期限di是服从如下的均匀分布：
[P*(1–TF-RDD/2),P*(1–TF+RDD/2)](3-1)
其中，
为了将每一种问题都考虑周全，不同的规模将TF，RDD的每一种组合方式皆生成不同的算例。TF，RDD一共有25种组合，每一种组合皆成为不同的5个随机算例，并按表3-2的顺序生成，一种问题规模一共是125个算例。
表3-2TF，RDD组合算例
本文针对规模的大小以及机器数量，主要测试了n＝50,100在m＝2,4,8台机器的加工情况下的求解。
3.2P//T实验结果与分析为了验证算法的正确性以及改进后的ACO性能是否提高，首先以Ho和Chang问题作为测试的基准问题。虽然Ho和Chang提出了此问题，但是他们所用的TPI算法却未能求解到最优值159。
3.2.1ACO启发式信息比较为了验证三种不同的启发式信息对ACO的性能提高最好，分别利用每一种启发式信息对Ho和Chang问题求解100次，比较总的达优率，平均百分比偏差(average percentage deviation)，以及最小时间ms，最大时间ms和平均时间ms。ACO参数设置为(＝1，(＝2，(＝0.1，(＝0.1，q0＝0.9蚂蚁数k＝10，最大迭代次数1000，算法停止的条件为得到最优值或是达到最大迭代数，并且算法未使用局部搜索，PTS策略如果没有特别说明，在实验部份都有使用。
表3-3不带LS的ACS对Ho和Chang问题的100次求解
从上表可以得出，SPT规则完全不能指引ACO找到最优解，而EDD的求解性能也不够理想只有45％的达优率，最好的启发式信息则是MDD规则可以达到85％的达优率，并且偏差是最小的。得到以上结果主要是因为SPT规则只考虑了加工时间的影响，而在总拖期中更重要的因素是交货期限，EDD规则也表明了这点，然而MDD考虑了两方面的影响，工作实际的完工时间和交货期限。虽然MDD可以得到更稳定的解，但是MDD是动态的规则，需要在每一次工作选择时重新计算转移概率，而EDD是静态的规则，所以MDD的计算需要更多的时间，表3-3中最大时间实质上是算法运行完1000次迭代所用的时间，相比较而且MDD的时间消耗要大得多，尤其在当问题规则增加时更加明显。图8是ACS算法运行一次的每代最优值，图9是ACS算法分别使用三种不同启发式信息运行100次的结果分布图。
表3-4是MMAS算法对问题的100次求解，其中参数设置为α＝1，β＝2，ρ＝0.1，ξ＝0.1，q0＝0.9蚂蚁数k＝10，最大迭代次数1000，其它条件与ACS算法皆相同。
表3-4不带LS的MMAS对Ho和Chang问题的100次求解
通过上表可以看出，MMAS算法在求解总拖期运输计划调度问题时的性能的确劣于ACS算法，这一点也与单机带权重总拖期得到的结论一致。同时也可以得出MDD规则是最适合的ACO启发式信息。
3.2.2P//T局部搜索验证为了验证局部搜索对算法性能的提高，表3-5分别对ACS和MMAS算法的结果使用了局部搜索，其参数设置与之前设置相同。实验结果表明，使用了局部搜索的两种算法在达优率上有明显的提高，并且平均偏差也得到提高。主要是因为总拖期运输计划调度问题的解的特性，交换邻近解的位置从而得到更好的解，虽然局部搜索本身会使解可能陷入局部最优，但是与ACO结合，只在每一次迭代的最优蚂蚁中的解采用局部搜索，减小了陷入局部最优的可能，充分利用了ACO的鲁棒性。
表3-5带LS的ACS和MMAS对Ho和Chang问题的100次求解
3.2.3P//T算法对比实验为了验证ACO的求解性能，本文将改进后的蚁群算法hACO与启发式KPM算法，以及遗传算法GA比较。测试的算例是根据前面小节随机生成的算例，包含了所有总拖期运输计划调度问题的难易组合。分别比较了在n＝50,100个工作，m＝2,4,8台机器不同情况的实验结果。
比较实验中，使用改进的ACS算法，启发式信息使用MDD规则，参数设置为α＝1，β＝2，ρ＝0.1，ξ＝0.1，q0＝0.9，对50个工作的问题蚂蚁数k＝10，而100个工作的蚂蚁数k＝20，局部搜索采用对每一代的最优值进行调度，并且当算法陷入搜索停滞时重新初始化信息素。算法终止的条件是达到最大迭代次数1000。
遗传算法使用了自然码编码以及块解码算法对编码解码，适应值函数使用目标函数，种群为50，运用轮盘赌注法选择遗传染色体，变异方式使用逆序变异，随机概率50％的选择染色体变异，每一代最优值无条件遗传。终止条件为迭代次数大于2000。
表3-6 50个工作的KPM，GA，hACO实验结果比较
表3-7 100个工作的KPM，GA，hACO实验结果比较
表3-6，表3-7分别比较了在50个和100个工作时的求解情况，hACO算法的性能明显优于其它的算法，可以达到85％的达优率，并且平均的偏差也是最小，即使未能求得与KPM和GA的最优值，最大偏差只有35.8％。而KPM算法是启发式算法中最优秀的算法，对不同的问题也可以保持在20％左右的达优率。GA算法未能达到理想的结果，经分析GA算法非常容易陷入搜索停止。ACO可以达到理想的求解质量，都依靠与ACO对求解组合优化问题上杰出的性能。不同于遗传算法，ACO通过更加直接的种群内的信息素交换信息与沟通，每只蚂蚁都利用(exploitation)以往蚁群所遗留的信息并且结合自身的探索能力(exploration)寻找更优秀的解。在智能群体中，虽然个体的能力不高，但是由个体组织而成的群体则表现了很强大的能力，这也就是ACO的基本思想。
由于总拖期运输计划调度问题的实验数据是由25种不同难易程度的125个随机实例产生，所以解的性能与实例的难易程度有很大的联系，表3-8是在100个工作4台机器的125个问题中的每种难易程度由不同算法所求得的平均值，并且以最小值作为最优值。
表3-8求解100×4规模的125个不同难易程度实例的平均值
在实验结果分析中，发现在求解TF＝0.2以及RDD∈{0.6,0.8,1.0}的问题时，总拖期最优值为0，KPM，GA，hACO算法都可以求解到0的最优值。在TF＝1.0时，绝大部分工作已经超过交货期限，此时按照SPT规则即可获得与最优值相近的解。而TF∈{0.6,0.8}以及RDD∈{0.2,0.4}时，问题的求解难度最大，而算法在求解此类问题时的偏差也是最大，最不稳定。
3.3P//T参数性能分析与优化从上节中的对比实验中可以看出，ACO的性能跟总拖期的实例难度有很大的联系。为了进一步优化ACO的性能，本文挑选了最难的实例作为实验测试算例，分别是TF＝0.6,0.8和RDD＝0.2时的100个工作4台机器的算例。
3.3.1蚂蚁数优化算法运行时的蚂蚁数目直接影响着算法求解的性能与效率，蚂蚁数目过少使得一次运行中蚂蚁无法随机的覆盖整个解的空间，从而减少寻找到最优解的概率。但是蚂蚁数目过多，虽然使得解的空间中可以分布更多的蚂蚁，提高解的质量，但是也使得算法运行的速度明显下降。表3-8所示的是求解100个工作4台机器中最难解的两个问题的实验结果，算法对每个问题运行10次，记录10次运行所产生的平均总拖期拖值以及平均的求解时间。参数设置为α＝1，β＝2，ρ＝0.1，ξ＝0.1，q0＝0.9，停止的条件是达到最大迭代数1000次。
表3-9不同蚂蚁数的hACO算法实验结果
从上表可以知道，增加蚂蚁数量的确可以在一定程度上提高算法求解的质量，两个算例的解都随着蚂蚁数的增加而提高，但是提高的幅度也是随之减小。当蚂蚁从10只提升到15，20只时，解的质量提升最大分别可以提升130和30。当达到30只数量的蚂蚁时，提升的幅度却只有10和10左右，但是时间却增加了三倍。
为了达到质量与时间的平衡，通过实验结果，一般选k＝20只蚂蚁往往可以得到性能上的平衡。而蚂蚁数的设定k＝n×20％，n为解空间中的节点数目。所以本文在求解50个工作的问题时就已经可以得到满意的解。但是在节点数目偏小时，蚂蚁的数目应有个下限，蚂蚁的数目过少信息素的间接信息交流得不到体现，将退化为随机搜索算法。所以针对Ho和Chang问题仍然使用了10只蚂蚁。
3.3.2ρ，ξ参数优化参数ρ，ξ是决定ACO中信息素更新的重要参数，ρ是全局信息素更新中决定路径信息素量的挥发与增加的参数，而ξ是局部信息素更新中减少蚂蚁走过的路径上的信息素量的参数。
ρ值过大，路径上的信息素量就会过快的挥发而最优蚂蚁的影响力会在单一的路径上增加，容易陷入搜索停滞，相反，ρ值过小最优的路径与一般的路径区分度不明显，使得算法收敛速度减慢。然而ξ的设置更加影响解的质量，因为局部信息素更新是针对每一只蚂蚁，而全局信息素更新只用于迄今最优值的路径。局部更新意在减弱蚂蚁路过路径上的信息素，以让其它蚂蚁可以选择不同的路径。
为了比较不同的ρ，ξ参数对算法运行过程的影响，本文使用λ平均分支因子判定算法是否陷入局部最优。在整个解空间中，最优解的边的信息素量往往会大于其它边，所以分析节点i相关边上的信息素量，可以判定算法是否陷入搜索停滞。统计与节点i相关边的数目bf根据下式
>
其中，τimin，τimax是与节点i相关的边的最大与最小信息素量，λ一般取0.05。平均λ分支因子即平均每一个节点可以供选择的结点总数。当算法陷入局部最优时往往平均每一个节点只有一条路径可供选择，即平均分支因子小于等于1时，算法陷入局部最优。
从图10中可以看出，ξ取值往往要取很小，如果ξ偏大，蚂蚁所经过的路径反而会更加过多减少信息素，当ξ＝0.2时，在算法初始就已经停滞。对较难的问题求解通常收敛会很慢会增加ρ，而要求解的质量高时会减小ρ。一般在求解时ρ，ξ＝0.1可以在收敛速度与陷入停滞中寻求一个平衡点。
当然，以上只是本发明的典型实例，除此之外，本发明还可以有其它多种具体的实施方式，凡采用等同替换或等效变换所形成的技术方案，均落在本发明要求保护的范围之内。
机译： 具有不同计划期和不同计划期的优先级计划者存储程序的方法，站和载体
机译： 基于改进粒子群优化算法的混合储能系统容量规划方法
机译： 用于通过机动车辆和拖车联接器来运输摩托车的拖头具有拖杆和球头，该拖杆和球头安装在拖头中，并且在拖头的颈部正下方，球头拖头刚性地连接到拖头。
