第10期 王雷等：基于HTHS算法的多节点多加工路线订单接受问题研究 .1395· best()-(best()-Emew()×rand[0,1,以概率小于等于PAR=0.5 Enew(②)= best()+(wrost()-xmew()×rand0,1,以概率大于PAR=0.5; (15) znew(),以概率1一PAR Tbest()和Tworst()为最好和最差解向量的 声记忆库考虑概率、基音调整概率、基音调整步长 第个变量，变量以和声记忆库中之前迭代的历史 和最大迭代次数： 适应值为标准进行选取，因此基音调整基于搜索的 步骤2利用NEH_LOV启发式算法和随机搜 自我认知能力（和声搜索的记忆能力）.在算法的 索确定初始订单加工序列，并计算每个订单加工序 早期阶段，需要在深度搜索和广度搜索之间进行平 列的目标函数值： 衡，而在子库A中采取的基音调整策略能够实现这 步骤3即兴创作一个新订单加工序列： 种平衡.best(i)-(best()-xnew()×rand0,1允 步骤4针对新创作的订单加工序列进行局部 许被选择的变量xnew()在它本身和best()之间进 搜索，更新订单加工序列： 行搜索，所以这种基音调整策略主要体现在深度搜 索上.best(i)+(worst-xmew)×rand[0,主要调整 步骤5将新订单加工序列的目标函数值与和 声记忆库中最差目标函数值的订单加工序列进行比 算法的广度搜索能力，如果选择的变量xmew()接近 worst(i)则zbest(i)+(worst(i)-工new）×rand[0,1刂 较，如果大于最差目标函数值的订单加工序列则替 更接近于Zbest().如果选择的变量xnew(i)远离 换该订单加工序列，更新订单和声记忆库： worst(①)则值也远离zbest().子库A中这种基音 步骤6如果算法满足终止条件结束算法，否 调整策略可以加强算法的广度搜索能力 则跳转到步骤3重新计算， 子库A的搜索空间以cbest(d)和Tworst()为 混合和声搜索算法由智能调谐和声搜索和局 上下边界，如果解向量不在子库A的边界内，智 部搜索算法组成，混合算法可以利用各个算法自身 能调谐和声搜索的解有可能陷入局部最优解。为 的优势来计算出更好的解.和声搜索算法利用不 了克服搜索空间边界问题，提高智能调谐和声搜索 要求决策变量的初始值设置、应用概率随机搜索等 算法搜索的广度，构建子库B.如果被选择的变量 优势能够在深度搜索和广度搜索之间进行很好的平 工new()属于子库B,则子库B能够提高算法搜索 衡.局部搜索对新创作的和声进行进一步的更新， 的广度，变量best(d)从best中随机选择决策变量 增强了算法的局部搜索能力 并在它的邻域内开始搜索.子库B中变量xmew() 的基音调整策略按照以下方式进行：m=int(1+ 4数据实验 (N -1)x rand),zhew =Enew(i)+(xbest(m)- 4.1实验设计 xmew()×rand0,1.其中，m是根据初始规模随机 本文采用Microsoft Visual C++实现改进粒子 例，变量 生成的正整数，beat(m)=best(m×包 群算法，实验环境为Pentium4/2.80GHZ/2.24GB/ xnew()的边界为Lx(i),ux(,tbest(m)的范围是 Windows7.基本和声搜索算法参数设置为：初始 Lx(m),Uz(m)]. 和声记忆库规模大小为30、和声记忆库考虑概率为 3.3嵌入局部搜索的智能调谐和声搜索算法 0.9、基音调整概率为0.33、基音调整步长为0.01、 将局部优化算法嵌入到智能调谐和声搜索算法 最大迭代次数为100.混合智能调谐和声搜索算法 中能够提高算法的搜索能力，在即兴创作和声阶段 参数设置为：初始和声记忆库规模大小为30，和声 改进和声向量的质量.和声向量和订单加工顺序都 记忆库考虑概率为0.99，最大基音调整概率(PAR) 可以应用局部搜索进行改进，本文选取以订单加工 为1.0，最小基音调整概率(PAR)为0，初始和声记 顺序为基础的局部搜索.局部搜索可以使每个和 忆库中的基音的最大值为1.0，初始和声记忆库中 声在其邻域内进行局部最优值的搜索过程.在产生 的基音的最小值为-1.0，最大迭代次数为200. 新的和声时，对新的和声邻域展开搜索，如果某个 实验数据设置如下：订单数n=10,15,20:每 邻居的适应值优于这个和声，那么用这个邻居进行 个订单的合同金额在均匀分布区间「100,10001内随 替换.常用的局部搜索策略包括互换操作、交换操 机产生：订单在各个节点的加工时间在均匀分布区 作和逆序操作 间[1,10]内随机产生；订单的交货期在均匀分布区 3.4混合算法求解订单接受问题的计算步骤 间[4,40]内随机产生：订单提前完工单位惩罚系数 步骤1设置算法的参数订单和声记忆库、和 为1；订单延迟完工单位惩罚系数为3：假设加工节第 10 期 王 雷等：基于 HITHS 算法的多节点多加工路线订单接受问题研究 1395 ·· xnew(i) =    x best(i) − (x best(i) − xnew(i)) × rand[0, 1],以概率小于等于PAR = 0.5; x best(i) + (x wrost(i) − xnew(i)) × rand[0, 1],以概率大于PAR = 0.5; xnew(i),以概率 1 − PAR. (15) x best(i) 和 x worst(i) 为最好和最差解向量的 第i个变量，变量以和声记忆库中之前迭代的历史 适应值为标准进行选取，因此基音调整基于搜索的 自我认知能力 (和声搜索的记忆能力). 在算法的 早期阶段，需要在深度搜索和广度搜索之间进行平 衡，而在子库 A 中采取的基音调整策略能够实现这 种平衡. x best(i) − (x best(i) − xnew(i)) × rand[0, 1] 允 许被选择的变量 xnew(i) 在它本身和 x best(i) 之间进 行搜索，所以这种基音调整策略主要体现在深度搜 索上. x best(i) + (x worst −xnew)×rand[0, 1] 主要调整 算法的广度搜索能力，如果选择的变量 xnew(i) 接近 x worst(i) 则 x best(i) + (x worst(i) − xnew) × rand[0, 1] 更接近于 x best(i). 如果选择的变量 xnew(i) 远离 x worst(i) 则值也远离 x best(i). 子库 A 中这种基音 调整策略可以加强算法的广度搜索能力. 子库 A 的搜索空间以 x best(i) 和 x worst(i) 为 上下边界，如果解向量不在子库 A 的边界内，智 能调谐和声搜索的解有可能陷入局部最优解. 为 了克服搜索空间边界问题，提高智能调谐和声搜索 算法搜索的广度，构建子库 B. 如果被选择的变量 xnew(i) 属于子库 B，则子库 B 能够提高算法搜索 的广度，变量 x best(i) 从 −−→ x best 中随机选择决策变量 并在它的邻域内开始搜索. 子库 B 中变量 xnew(i) 的基音调整策略按照以下方式进行：m = int(1 + (N − 1) × rand)，则 x 0 new = xnew(i) + (x best(m) − xnew(i)) × rand[0, 1]. 其中，m 是根据初始规模随机 生成的正整数，x best(m) = x best(m) × Ux(i) Ux(m) ，变量 xnew(i) 的边界为 [Lx(i), Ux(i)]，x best(m) 的范围是 [Lx(m),U x(m)]. 3.3 嵌入局部搜索的智能调谐和声搜索算法 将局部优化算法嵌入到智能调谐和声搜索算法 中能够提高算法的搜索能力，在即兴创作和声阶段 改进和声向量的质量. 和声向量和订单加工顺序都 可以应用局部搜索进行改进，本文选取以订单加工 顺序为基础的局部搜索. 局部搜索可以使每个和 声在其邻域内进行局部最优值的搜索过程. 在产生 新的和声时，对新的和声邻域展开搜索，如果某个 邻居的适应值优于这个和声，那么用这个邻居进行 替换. 常用的局部搜索策略包括互换操作、交换操 作和逆序操作. 3.4 混合算法求解订单接受问题的计算步骤 步骤 1 设置算法的参数订单和声记忆库、和 声记忆库考虑概率、基音调整概率、基音调整步长 和最大迭代次数； 步骤 2 利用 NEH LOV 启发式算法和随机搜 索确定初始订单加工序列，并计算每个订单加工序 列的目标函数值； 步骤 3 即兴创作一个新订单加工序列； 步骤 4 针对新创作的订单加工序列进行局部 搜索，更新订单加工序列； 步骤 5 将新订单加工序列的目标函数值与和 声记忆库中最差目标函数值的订单加工序列进行比 较，如果大于最差目标函数值的订单加工序列则替 换该订单加工序列，更新订单和声记忆库； 步骤 6 如果算法满足终止条件结束算法，否 则跳转到步骤 3 重新计算. 混合和声搜索算法由智能调谐和声搜索和局 部搜索算法组成，混合算法可以利用各个算法自身 的优势来计算出更好的解. 和声搜索算法利用不 要求决策变量的初始值设置、应用概率随机搜索等 优势能够在深度搜索和广度搜索之间进行很好的平 衡. 局部搜索对新创作的和声进行进一步的更新， 增强了算法的局部搜索能力. 4 数据实验 4.1 实验设计 本文采用 Microsoft Visual C++ 实现改进粒子 群算法，实验环境为 Pentium4/2.80GHZ/2.24GB/ Windows 7. 基本和声搜索算法参数设置为：初始 和声记忆库规模大小为 30、和声记忆库考虑概率为 0.9、基音调整概率为 0.33、基音调整步长为 0.01、 最大迭代次数为 100. 混合智能调谐和声搜索算法 参数设置为：初始和声记忆库规模大小为 30，和声 记忆库考虑概率为 0.99，最大基音调整概率 (PAR) 为 1.0，最小基音调整概率 (PAR) 为 0，初始和声记 忆库中的基音的最大值为 1.0，初始和声记忆库中 的基音的最小值为 –1.0，最大迭代次数为 200. 实验数据设置如下：订单数 n=10，15，20；每 个订单的合同金额在均匀分布区间 [100,1000] 内随 机产生；订单在各个节点的加工时间在均匀分布区 间 [1,10] 内随机产生；订单的交货期在均匀分布区 间 [4,40] 内随机产生；订单提前完工单位惩罚系数 为 1；订单延迟完工单位惩罚系数为 3；假设加工节