基于混沌免疫进化算法的物流配送中心选址方案

来源:用户上传      作者: 李昌兵　杜茂康

　　[摘要] 电子商务环境下的物流配送中心选址问题是近年来物流研究中的热点。由于它是一个NP难题，较难得到最优解和满意解。本文将混沌免疫进化算法用于解决该问题。混沌免疫进化算法具有较好的全局搜索能力和收敛性，能够较好的解决该类复杂系统的优化问题。
　　[关键词] 物流 配送中心 选址 混沌免疫进化算法 多目标优化
　　
　　一、物流配送中心选址多目标优化模型
　　1.上层模型。上层规划为决策部门在允许的固定投资范围为，确定最佳的新选物流中心的地点以使总成本最小。具体模型如下：
　　令A=A1∪A2为所有物流中心地点的集合,A1为已有物流中心的集合，A2为新增物流中心的集合。
　　
　　式中:Cij(.)―第i个客户由j地点的物流中心提供服务的单位运量的广义费用；Xij―第i个客户在j地点的物流中心得到满足的需求量；fj―在j(j∈A2)地建物流中心的固定投资；B―修建物流中心的总投资预算；Yj―0-1变量，在j(j∈A2)地建物流中心时，此值为1，否则为零。
　　2.下层模型。下层规划(L)描述了在多个物流中心存在的条件下，客户需求量在不同物流中心之间的分配模式，它的目标是使每个客户的费用最低。下层规划为：
　　
　　M为充分大的正数,ε为充分小的正数,sj为j地的物流中心的供应能力，Wi为客户点i的总需求量。
　　一般来说，求解双层规划问题是非常困难的，原因之一就是由于双层规划问题是一个NP-hard问题，解答这类问题需要相当长的计算时间，这里采用混沌免疫算法来求解。
　　二、混沌免疫进化算法
　　本文在结合混沌优化算法和免疫进化算法各自特点的基础上，提出一种混沌免疫进化算法。该算法不仅能更好地保持种群的多样性，而且收敛速度快，搜索能力强。
　　1.混沌映射和混沌挠动方式的确定,本文采用常用的Logistic映射:
　　(3)
　　式中，0≤t(k)≤1，当取μ＝4时，系统完全处于混沌状态，其混沌空间为[0,1]。不动点为0．25，0．5，0．75。
　　对于随机扰动的确定，令 (4)
　　其中；β*为当前最优值映射到[0，1]区间后形成的向量，称为最优混沌向量；βk为迭代k次后的混沌向量；βk’为施加随机扰动后的混沌向量；0<α< l，α可以自适应变化。搜索初期希望变量变化较大，α值应较大；随着搜索的进行，变量逐渐接近最优值，α应逐渐减小。本文算法按下式确定：
　　
　　2.混沌免疫算法描述，采用混沌免疫算法求解约束优化问题的具体实现步骤如下：
　　(1)参数设置：设定种群进化代数为Ngen，种群规模为No，记忆细胞数量为NM，克隆选择数量为Ns，克隆倍数为Nη，免疫补充数量为NR，混沌变量序列长度为mc。
　　(2)初始化：初始种群X0随机生成，设个体x＝[x1,x2，…,xn]T，则生成N0个可行解个体的初始种群X0的步骤如下：
　　①令初始可行解集X0＝，满足约束条件的可行解个体计数j=0。②个体随机生成。 ③判断生成的候选解x是否为可行解，若是可行解，则x并入X0中，即X0←x，且计数器增加1，j←j＋1，转步骤(4);若不是可行解，则放弃生成的x，转步骤 。④判断计数器计数j是否达到N0，若达到，则结束种群初始化，转步骤③，否则转步骤(2)继续。
　　(3)进化开始：载入抗原，根据目标函数计算每个抗体的聚合适应度(聚合适应度的具体计算见公式，并按升序排列，令进化代数T=1。
　　(4)克隆选择：选取序列前N 个个体形成种群Xs，用于克隆。
　　(5)克隆扩增操作：对种群Xs中的每个个体，按照Nη倍进行克隆扩增，得到种群Xc。
　　(6)抗体突变操作：对种群Xc中的每个个体进行突变操作，得到种群Xm。
　　(7)对种群Xm中的个体进行可行解审查，合格的个体组成种群X，m，并计算其亲和度。
　　(8)父代样本X0和X，m组成新的种群X0←X，m，并按照亲和度重新排序。
　　(9)记忆细胞的形成：重新选择序列的前N0个个体作为子代种群X0，并把前NM个个体记为记忆细胞种群XM。
　　(10)混沌优化：对种群XM中的每个记忆细胞进行混沌优化操作。
　　终止条件判断：判断进化是否到达指定代数，若到达，输出记忆细胞种群中最小亲和度作为最优解，对应的个体为最优点，算法结束；否则T＝T+1，并执行步骤?
　　免疫补充：按式(3)随机生成NR个个体，代替种群X0中NR个亲和度最大的个体，种群按亲和度重新排列，并转步骤(4)。
　　在上述算法步骤中，除步骤(10)外，其余的步骤构成免疫算法，而步骤(10)为混沌优化方法。容易看出，在步骤(9)中的记忆细胞为免疫算法获得的全局近似最优解，而步骤(10)是在全局近似最优解的邻域内进行局部范围的混沌搜索，以获得全局精确最优解，这样免疫算法与混沌优化就有机地结合在一起。
　　三、混沌免疫算法的求解算法设计
　　算法的基本要素如下：
　　1.编码选择和生成初始种群,采用实数编码。
　　2.抗体聚合适应度的计算,抗体的聚合度的计算步骤如下：(1)分别计算抗体体的子目标函数值；(2)将抗体排序等级作为原始适应度；(3)根据如下公式计算抗体的浓度,Ci=与抗体i的相似度大于λ的抗体数/N;(4)根据如下公式计算抗体的聚合适应度;。
　　3.抗体扩增算子设计。模拟克隆扩增和超突变过程。群体B中任一个体的小邻域构造为：
　　扩展操作相当于在优秀个体的小邻域内搜索更优秀的个体。个体评价值越高，其邻域内存在优秀个体的概率越大。
　　4.抗体突变算子设计。在该算子操作中，构造一个较大邻域。其较大邻域构造为：
　　MN(vj)在解空间中是以vj为中心，以R为半径的球形区域，定义R为突变半径。突变半径应远大于扩展半径。
　　5.混沌优化算子设计。用混沌优化方法进行局部搜索，步骤如下：
　　(1)对记忆种群中的第k(k＝1，2，… ，NM)个记忆细胞，将其第i个基因变量xi映射到混沌空间[0，1.0]：
　　
　　把xi,0作为混沌迭代的初始值，按式3生成mc个不同轨迹的混沌变量序列{xi，j }( j＝1，2，…，mc)。
　　(2)利用选定的混沌变量xi，j分别对原变量进行载波：
　　
　　式中:△xi,j为xi的邻域；r为邻域半径;p为邻域半径系数，取p=0.05；函数randint(a，b)为区间 [a，b]内的随机整数。
　　(3)对混沌变量序列的个体进行可行解审查，设有m’c个个体满足约束条件。
　　(4)计算这m’c个可行解个体的亲和度Gj＝G(x’i,j)( i=1，2，…n,j=1，2，…，m’c)，并进行如下操作:设载波前k个记忆细胞和亲和度分别为x(k)、G(k)=G(x(k))，在载波后的可行解个体序列中最小亲和度与最优个体分别为G*=min(Gj)、x*，即G*=min(Gj)=G(x*)。进行下列判断:若G*

转载注明来源:https://www.xzbu.com/3/view-1493985.htm