没有合适的资源?快使用搜索试试~ 我知道了~
核中心驱动混合蛙跳算法及其应用.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 126 浏览量
2022-11-28
20:30:36
上传
评论
收藏 1.61MB DOCX 举报
温馨提示
试读
37页
核中心驱动混合蛙跳算法及其应用.docx
资源推荐
资源详情
资源评论
容量限制车辆路径问题(capacity-limited vehicle routing problem,CVRP)
是车辆路径问题(vehicle routing problem,VRP)中最常用的一种
[1]
。CVRP 是
典型的非确定性多项式(non-deterministic polynomial,NP)难解问题
[2-3]
,现有
技术大多采用启发式算法求解,但均存在算法运行时间长、易于陷入早熟收敛
现象的缺陷
[4]
。在 CVRP 中,所有客户的服务类型相同,同为送货或同为收货,所
有车辆载重量一样,每个客户的需求量均不大于车辆载重量,车辆都从配送中心
出发最终也返回到配送中心
[1]
。
混合蛙跳算法(shuffled frog leaping algorithm, SFLA)是一种新的基于
全局搜索和局部更新的启发式合作搜索算法,它模仿了青蛙在受限环境中的觅
食机制
[5]
。该算法具有参数少,全局寻优能力强和较快的收敛性等优点
[6]
,在组合
优化问题等方面获得了较好的效果
[5]
。但是 SFLA 在寻优更新中,存在差异更新
随机性,导致 SFLA 在进化后期易出现收敛速度慢、精度低等问题
[7]
。目前,已有
诸多学者对 SFLA 的寻优策略进行改进,性能得到了较好的改善
[8]
。文献[9]把具
有极强局部搜索能力的幂律极值动力学优化结合如 SFLA,提出基于实数编码
模式的混合蛙跳算法求解容量约束车辆路径问题。文献[10]将改进后的 SFLA
采用实数编码方式,融入自适应差分扰动机制及混沌局部搜索策略到局部搜索
过程用于求解带有容量约束的车辆路径问题。文献[11]针对带容量约束的车辆
路径问题,提出了一种带分裂机制的帝国竞争算法进行求解。文献[12]提出了一
种量子行为粒子群优化算法和探索启发式局部搜索算法来求解容量约束的车
辆路径模型。文献[13]将容量约束的车辆路径问题扩展到更广泛的度量空间。
文献[14]定义了离散的蝙蝠位置、速度、频率以及更新规则,用于解决带容量约
束问题的车辆路径问题。文献[15]提出一种离散布谷鸟算法求解带容量约束的
车辆路径问题。文献[16]对粒子群与改进蚁群算法进行融合改进,并应用于三维
路径规划(autonomous underwater vehicle,AUV)问题中。文献[17]利用深度
学习的栈式自编码模型对高光谱影像进行光谱特征提取,通过混合蛙跳算法对
目标函数进行优化从而实现对最佳端元组合的搜索。文献[18]提出了一种混合
蛙 跳 算 法 和 禁 忌 搜 索 ( shuffled frog leaping algorithm along with the tabu
search,SFLA-TS)的算法。文献[19]引入变邻域搜索算法提升蛙跳算法的局部
搜索能力,引入针对关键工厂的全解空间禁忌搜索,扩大了算法解空间。文献[20]
设计求解多约束车辆路径模型的改进混合蛙跳算法,改进聚类算法并结合邻近
矩阵构造初始青蛙种群,设计自 内而外的交 流演化模式 ,定义远离矩阵,对青 蛙
进行引导性邻域搜索。文献[21]提出了采用单种群蛙跳优化的卷积神经网络算
法对眼底多种病变进行检测。
本文提出一种核中心驱动混合蛙跳算法(shuffled frog leaping algorithm
driven by nuclear center,NCSFLA),对容量限制车辆路径优化问题进行研究,
提出 一种 核 中心 驱动 混 合蛙 跳算 法 的容 量 限制 车辆 路 径优 化算 法 (shuffled
frog leaping algorithm driven by nu-clear center for capacity-limited vehicle
routing problem,NCSFLA-CVRP),以提高容量限制车辆路径的优化性能。
1 基础概 念
1.1 车 辆 路 径 问 题的 数 学 描 述
单目标最优化问题一般分为最大值优化问题和最小值优化问题。本文采用
容量限制车辆路径问题作为研究的对象,该问题属于单目标最小值优化问题,其
定义及描述如式(1)所示
[1]
。
minD(i,j)=∑i=0N∑j=0N∑s=1Kcijxijs
(1.1)
s.t.∑i=0Nxijs=yjs,j=1,2,⋯,N;s=1,2,⋯,K
(1.2)
∑j=0Nxijs=yis,i=1,2,⋯,N;s=1,2,⋯,K
(1.3)
∑i=0Nqiyis≤qs,s=1,2,⋯,K
(1.4)
∑s=1Kyis=1,i=1,2,⋯,NK,i=0
(1.5)
式中,D(i,j)代表所有车辆的总路径长度,cij 代表客户 i 和客户 j 之间的运输
距离,qi 代表客户 i 的运输需求,qs 代表车辆 s 的载荷容量,N 是客户的总数量,其
中 i,j=1,2,⋯,N 代表客户编号,i=0 和 j=0 代表配送中心的编号,K 是车辆的总数量,
其中 s=1,2,⋯,K 代表车辆编号,{xijs=1}代表车辆 s 从客户 i 到客户 j 之间的有直
接相连的路径,否则{xijs=0},yis 和 yjs 分别代表客户 i 和客户 j 的需求由车辆 s
满足。式(1.1)表示以配送中心 0 开始编号的所有车辆的最小总路径长度,是
待求解的目标函数。式(1.2)~(1.5)表示约束条件。式(1.2)~(1.3)表
示车辆到达客户 i 或客户 j 后,又从该客户出发。式(1.4)表示每条配送线路上
总客户需求量≤该配送线路上车辆的运载能力。式(1.5)表示每个客户仅和一
辆车相关联,配送中心 0 编号可以与 K 辆车关联
[1]
。
1.2 核 中 心 驱 动 混合 蛙 跳 算 法
本文引入量子力学理论
[22]
,以及玻尔原子模型理论
[22]
,将 SFLA 算法中的青
蛙个体跳跃进化行为定义为量子力学行为,对原始混合蛙跳算法进行改进,提出
一种核中心驱动混合蛙跳算法(NCSFLA)。
1.2.1 概念 提 出
定义 1(电子轨道) 将初始化的青蛙群体空间定义为量子空间,量子空间
中有一个原子模型,多个青蛙可以看作这个原子模型中的多个电子以及一个由
全局最优个体代表的原子核。青蛙的族群定义为多个电子轨道。则量子空间表
示为:
其中,量子空间中具有 P=n×m 个青蛙初始个体,m 为族群个数,n 为族群内
青蛙个 数 ,青 蛙 个体分 量 x(j)i 的维 数 记为 S。 设 各族 群迭代 局 部进 化次数 为
T1,全局进化次数为 T2。
定义 2(电子轨道中心) 族群 k 中局部最优个体定义为电子轨道中心,记
为 x(k)b=(x(k)b1,x(k)b2,⋯,x(k)bS)。
定义 3(原子核中心) 青蛙群体此次进化中的全局最优个体定义为原子
核中心,记为 x(g)b=(x(g)b1,x(g)b2,⋯,x(g)bS)。
定义 4(个体跃迁步长) 族群 k 中个体跃迁步长定义为电子轨道中心与
当前族群 k 中最差个体的差值,记为 D_tr=x(k)b-x(k)w,x(k)w 代表族群 k 中最差
个体。
定义 5(个体驱动步长) 族群 k 中个体驱动步长定义为原子核中心与当
前族群 k 中最差个体的差值,记为 D_dr=x(g)b-x(k)w,x(k)w 代表族群 k 中最差
个体。
1.2.2 电子 轨 道 中 心 驱 动 策 略
一次青蛙局部进化中,族群 k 中 最 差 个 体 x(k)w,k=1,2,⋯ ,n 中每一维分量
x(k)wi,i=1,2,⋯,S 将以电子轨道中心为圆心,以个体跃迁步长为半径进行进化,提
出电子轨道中心驱动策略,如式(2)所示:
x(k)winew=x(k)bi+rand(0,1)[x(k)bi-x(k)wiold]
(2)
1.2.3 原子 核 中 心 驱 动 策 略
一次青蛙局部进化中,如果通过电子轨道中心驱动策略进化得到的目标函
数值 f(x(k)winew)略于 f(x(k)wiold),即存在 f(x(k)winew)≥f(x(k)wiold)时,族群 k
中最差个体 x(k)w,k=1,2,⋯,n 中每一维分量 x(k)wi,i=1,2,⋯,S 将以原子核中心为
圆心,以个体驱动步长为半径进行进化,提出原子核中心驱动策略,如式(3)所
示。
x(k)winew=x(g)bi+rand(0,1)[x(g)bi-x(k)wiold]
(3)
1.2.4 核中 心 驱 动 混 合 蛙 跳 算法 原 理
本文 利用电子轨道中 心驱动策略和 原子核中心驱动 策略对混合蛙 跳算法
中的一次局部进化进行改进,提出一种核中心驱动混合蛙跳算法。算法进化原
理如图 1 所示。
图 1
图 1 核中心驱动混合蛙跳算法原理
Fig.1 Principle of shuffled frog leaping algorithm driven by nuclear center
原理 初始的青蛙个体分布在 m 个电子轨道上,电子轨道是以原子核为中
心的同心圆,每个轨道代表一个族群,每个族群中有 n 个青蛙个体。此时,青蛙个
体处于各自的电子轨道上的不同定态
[22]
。进化开始后,轨道 k(即族群 k)中的
一个青蛙个体以电子轨道中心驱动策略进行进化,使得轨道 k 中的青蛙个体统
一朝电子轨道中心趋近,形成不同定态之间跃迁
[22]
,跃迁步长是 D_tr。如果进化
后存在 f(x(k)wiold),则轨道 k(即族群 k)中的一个青蛙个体以原子核中心驱动
剩余36页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3681
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功