禁忌搜索算法公式

6.2基于均衡原理的LRP算法设计6.2.1基于均衡原理的LRP算法整体流程基于均衡原理的LRP算法整体流程如下：step1：初始化，设置整体收敛性判断参数；step2：随机生成一组LRP选址问题的解D，求出相应的目标值F；step3：根据上层解D，利用Frank-Wolfe算法（见6.2.3节）求出各客户的货物总量Qj及客户在各配送中心的货物均衡分配量xji,；step4：根据D及xji,运用禁忌算法求解VRP问题(见6.2.4节)，得出各配送中对各客户的单位货物配送费用Cji,；step5：根据xji,及公式（6-8）求出下层xji,与di的关系ydxjiijiW,,；step6：将LRP模型上层目标函数中用代替，并代入下层求得的Qj和Cji,，运用禁忌算法求得新的LRP选址规划的解'Z及目标函数'F（见6.2.2节）；step7：如果FF'，转step8，算法结束，D、F为LRP的最终解和解值；否则'':,:FFDD，转step3；step8：算法结束。6.2.2LRP选址规划的禁忌算法模型上层是基于0-1整数规划的选址问题。由于选址问题是NP-hard，如果用精确算法求解，对节点数目的限制将有严格的要求。本章根据模型的特点，采用禁忌算法优化产业选址问题。1．解的构造和初始解的生成采用二进制编码，编码长度为潜在的配送中心地点数量NT，对于编码中位置i，1表示选中i点作为厂址，0表示没有选中。对于解中任意点i，产生随机数，如果NTN/，则置i点为0，否则置1。重复以上步骤m次，得到初始解。2．邻域的搜索根据本章选址问题的特点，设计了三种邻域操作，分别为自身取反、2-swap交换和2-opt交换。1）．自身取反。为单点操作，即选择解中i点，对该点的值取反；2）．2-swap交换。为双点操作，选择解中两点进行交换，其它位置的值不变。例如解001101中的2、6点被选中，则2-swap交换后变为：011100；3）．2-opt交换。为多点操作，选择解中两点进行交换，同时两点之间的值逆序改变。例如解001101中的2、6点被选中，则2-swap交换后变为：010110；4）．自身取反、2-swap交换操作能较快的搜索到局部最优解，2-opt交换则能扩大搜索空间。自身取反、2-swap交换是每个循环都进行的操作，进行局部寻优。当代最优解没有变化时，进行一次2-opt交换操作，跳出局部最优点。将以上三种邻域结合，不仅保持了TS局部”爬山”能力强的优点，同时也让它的全局寻优能力大大加强。3．约束的处理本章LRP模型上层约束包括分厂数量约束和总投资额约束。对于分厂数量限制，本章在邻域操作中加以控制：如果当前解经过某邻域操作，违反分厂数量限制，则取消此邻域操作。对于总投资额约束，本章采用惩罚函数的方式进行处理，把超出约束的量乘以一个惩罚系数，作为一个惩罚项加入到解的适应度中。上层目标函数的适应度S可以表示为：),0max(*)(,,MpZQjSzBxCiIiiIiJjJjjiji式中p表示总投资额约束的惩罚系数。4．禁忌表和终止准则根据本禁忌算法邻域性质的不同，本章设计了两种禁忌表：局部禁忌表和全局禁忌表。局部禁忌表存储的是自身取反、2-swap交换邻域操作的对象，即如果当前解采用了某种邻域，那么在接下来的个循环内不允许进行该邻域的逆操作。全局禁忌表存储的是寻优过程中每个循环的解值，此禁忌表只在选用2-opt交换操作时采用，避免进行重复搜索，加快寻优速度。如果经过某邻域操作得到比当前最好解更好的解，那么不管该邻域是否被禁忌，都采用该邻域作为当前邻域。终止条件：如果连续代最优解没有改变，则终止循环，算法结束。5．关键步骤step1：初始化各参数，搜索循环次数0i；step2：形成初始解，令初始解为当前解，其解值为当前最优解值*f；step3：1:ii；step4：如果连续代最优值没有改变，转step12，否则继续；step5：如果进行2-opt邻域操作后，连续代最优值没有改变，继续，转step7；step6：搜索当前解的2-opt邻域，转step8；step7：搜索当前解的自身取反和2-swap两种邻域；step8：按邻域解值降序排列各邻域，令0j，第j个邻域解值为fj；step9：1:jj；step10：判断fj是否大于*f，是则令ffj:*，令第j个邻域解为当前解，转step3；否则继续；step11：判断第j个邻域解是否违反禁忌规则，是则转i；否则令其为当前解；转step3；step12：终止。6.2.3物流配送均衡模型的Frank-Wolfe算法设计在得到上层的解D后，本章采用Frank-Wolfe算法解下层物流配送均衡模型。该法是用线性规划逐步迭代逼近非线性规划的方法，在每步迭代中，先找到一个目标函数的最速下降方向，然后再找到一个最优步长，在最速方向上截取最优步长得到下一步迭代的起点，重复迭代直到找到最优解。Frank-Wolfe算法解物流配送均衡模型详细步骤如下：step1：初始化：按照jiccjiji,)0(,0,，实行一次全有全无分配，得到客户分配到各配送中心的货物量；令1n；step2：更新各配送中心的单位货物服务费用：jixccnjijinji,)(,,,；step3：寻找下一步的迭代方向：按照实行一次全有全无分配，得到一组各配送中心的附加的货物服务量；{:,},cnijij?{:,},dnijij?step4：确定迭代步长λ：4.1确定满足()0的λ合理取值范围[λbot,λtop]；,,,+?nijnijnijxλdx