量子进化算法在拣选路径优化中的应用
来源:用户上传
作者:
【摘要】随着电子商务的迅速发展，商品流通速度加快，物流运作成本居高不下，怎样降低物流成本成为人们日益关注的焦点。本文以双区型仓库为研究对象，以拣选行走距离最短为目标建立数学模型，对量子进化算法改进，具有更好的种群多样性特征，与传统进化算法相比，量子进化算法具有种群规模小、全局寻优能力强、不易陷入局部最优解的特点。通过MATLAB编程实现对拣选路径问题的优化。
【关键词】量子进化算法 旋转门 量子位编码
一、引言
时代不断地改变，经济快速发展，我们的购物模式从原来的低频率、少品种向高频率、多品种的模式转变，从过去在实体店的购物模式向“线上购买”加上“线下体验”的方向改变，这种高频率、多品种的购物模式向电商企业提出了挑战，电商企业一定要适应这种消费模式，快速有效地面对挑战，加强对配送中心的重视力度，提供更快速的物流配送服务，更大程度上提高顾客的满意度，满足顾客的需求。
在配送中心的活动中，拣选作业的时间大约是配送中心工作时间的三分之一，占总成本的百分之九十。而拣选人员行走的时间又是拣选作业时间的比重较大的部分。对拣选路径进行优化可以大大地缩短行走距离，从而可以减少拣选作业所花费的时间。拣选路径的优化是提高工作效率、提高配送的速度、降低物流成本以及增加客户满意度的重要手段。
到目前为止，学者们已经研究出许许多多对路径优化的方法如禁忌搜索、模拟退火算法、进化算法等，这些优化方法都在拣选路径优化的问题中取得了很好的效果。但是在路径优化的具体应用过程中经常会陷入早熟收敛、易陷入局部等困境，很难得到最优解。本文基于Bloch球对量子进化算法改进，在旋转策略加入奖励函数，鼓励种群向他们有利的方向进化。这种方法克服了量子进化算法的收敛速度慢、受初始种群影响的缺点，能够更好地解决路径优化问题。通过MATLAB编程的方式来实现对拣选路径的优化，然后与其他智能算法优化结果作比较，验证改进量子进化算法的优越性。
二、量子进化算法的基本原理
（一）哈密顿图
哈密顿图（Hamiltonian path）是由天文学家哈密顿提出一个无向图。从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径。这与求解配送中心的拣选路径类似，唯一不同的是由于小车的总载重量的限制，当拣选人员拣选的货物超出拣选人员时，要回到出发点，然后再重现拣选。如待拣选货物顺序为1-2-3-4-5-6-7-8-9-10-1（1代表了出发点和结束点），这代表了一个完整的哈密顿图，其中在拣选到编号为5号的货物时，如果拣选5号货物，那么已经拣选的货物超出了小车的载重量，拣选人员需要回去把小车货物卸下，继续拣选，那么实际的哈密顿图有两个，分别为1-2-3-4-5-1，1-6-7-8-9-10-1，但是总的拣选路线还是1-2-3-4-5-6-7-8-9-10-1或者是1-6-7-8-9-10-2-3-4-5-1，总的拣选行走距离没有变化。生成多少个哈密顿图对拣选路径的优化没有影响。
（二）量子进化算法编码求解
在量子计算中，一个量子比特是一个可以在二维希尔伯特空间中描述的二阶量子系统，根据量子比特的特性，量子比特在二维希尔伯特空间中可以表示为：
借助哈密顿图对基于Bloch球的进化算法进行改进，对种群染色体初始化得到Q（to），其中种群染色体的量子比特编码都为，使得每个染色体所表达的全部状态是等概率的（配送中心的订单都是随机产生的），对量子染色体进行初始化种群进行特殊的二进制编码，然后生成哈密顿图即拣选路线，在量子进化算法中的哈密顿图通过编码可以如上6*6矩阵（式（2-6））所示。通过这种特殊的哈密顿图的形式，矩阵中的每一个1的变换都具有实际意义，有利于种群的多样性。其中矩阵的每一行的1所在行数表示拣选路径的顺序，每一列的1所在列数表示待拣选货物的位置，起始位置默认为1，因此上面的矩阵所代表的拣选路径为1-5-3-2-6-4-1，满足了哈密顿圈路途中经过图中每一个结点当且仅当一次，但是这种必须要保证矩阵的每行每列都为1，而且保证矩阵的最后一个1在第n（n表示种群规模）行第1列只有这样才能保证哈密顿图是一个完整的回路，如果不能保证，再生成拣选路线时，会导致生成的初始种群对最优结果产生不好的影响。因此在生成二进制矩阵的时候，确保每行每列只有一个1。
其中minx（1，1）x，maxx（1，2）x分别表示第一变量的最小值和最大值，miny（1，1）y，maxy（1，2）y分别表示第一变量的最小值和最大值，minz（1，1）z，maxz（1，2）z分别表示第一变量的最小值和最大值。经过转换之后就是所要求得的解。
在基于Bloch球改进的量子进化算法求解拣选路径优化问题中，求解出之后的是特殊的哈密顿圈（二进制编码），这种特殊的哈密顿圈只是为了我们更方便的求解，加快收敛速度、增加种群的多样性，并不是我们最终需要的拣选路径，需要通过对这种编码进行解码，最终转变为我们需要的拣选路径。
（四）量子染色体的更换
量子染色体的更新是经过量子旋转门更新量子位的相位来完成的。量子位相位旋转的作用在于使当前种群中每一个染色体逼近当代最优染色体，但在这种逼近过程中，也有可能產生出更好的当代最优染色体，从而使群体不断得到进化。因此量子旋转门，形式为：
但是在量子旋转门中旋转角是固定不变的，无论当前的适应度大于还是小于最优适应度，都是按着同样的速度进行染色体的更新，这种策略降低了算法的收敛速度。因此在此加入奖励函数，如下所示：
其中fitness（i）表示第次进化时的最小适应度，best.fitness当前种群的最小适应度，通过加入这种奖励函数，当第次进化时的最小适应度小于当前种群的最小适应度时，能够加快量子旋转门的更新速度，提高种群的收敛速度。旋转角策略如下表1所示：
（五）量子染色体的灾变
在拣选路径中，为了防止陷入最优解，需要在量子进化算法中加入种群灾变，当量子进化算法经过一定的迭代次数，最优的染色体就会保持不变，就很有可能陷入局部最优解，因此加入灾变操作，使其跳出局部最优，从种群的第100次进化代数实行变异，通过对初始生成的哈密顿图施加较大的扰动，重新生成哈密顿图，增加种群的多样性，使得算法不易陷入局部最优解。
三、仿真运行与结果分析
通过MATLAB编程对问题求解，验证算法的有效性，分别使用基于Bloch球的量子进化算法会与量子进化算法、蚁群算法以及禁忌搜索算法对拣选路径进行优化，结果如下表2、图2所示：
从以上图表可以看出模拟退火算法优化的拣选行走距离最大，它的曲线普遍在其它两个之上，它优化的平均距离和最短距离都是最大的，优化效果相对较差。基于Bloch改进的量子进化算法优化效果最好，不论是优化的平均距离还是优化的最短距离都是最小的，相比其他两个智能算法优化减少的距离程度较大，优化效果更好，收敛速度更快。因此基于Bloch球改进的量子进化算法在拣选路径优化问题中有着很好的适用性，能够较好的解决拣选路径优化问题。
四、结论
量子进化算法由于量子态的叠加性和相干性能够表达多个态的叠加，具有更好的多样性特征。与传统进化算法相比，量子进化算法具有种群规模小、全局寻优能力强、不易陷入局部最优解的特点，能够更好地解决路径优化问题。
转载注明来源:https://www.xzbu.com/2/view-14829081.htm
