基于混合启发式算法的三维装箱研究
发布时间：2021-01-24 03:34
装箱问题的求解与应用可以为物流和仓储等行业提供高效便利的服务,然而由于装箱问题的复杂性以及装箱算法的非普适性,使得装箱问题和装箱算法的研究成为需要解决的实际问题。概念简单、容易实现且具有能背景的粒子群算法在求解装箱问题中受到了广泛的关注。作为组合优化问题中的典型问题,装箱问题的研究在实际应用和理论研究方面具有重要意义,具有广阔的研究前景。本文主要对粒子群算法的外部参数和内部拓扑结构进行改进,然后与启发式算法相结合,得到混合启发式算法用以求解装箱问题。本文的主要工作及结论概括如下:1、基于离散问题对粒子群算法外部参数进行调整,采用惯性权重随机递减,学习因子c1线性递增,c2线性递减的方式改进算法性能,能到求解装箱问题最优的参数设置,比传统粒子群算法的收敛速度提高了86%,与WPSO算法相比收敛速度提高了36%。2、对粒子群算法内部拓扑结构进行改进,采用双判断的方式,在粒子调整前与粒子调整后均进行适应度判断的方式构造动态拓扑结构,实现动态粒子群算法改进。改进粒子群算法迭代500次的实验中,平均30次可以求得最优解,而其它算法分别在90,1 20,150才能得到最优解,提高了算法的收敛速度。...
【文章来源】：西安理工大学陕西省
【文章页数】：44 页
【学位级别】：硕士
【部分图文】：
改进粒子群算法流程图
西安理工大学工程硕士专业学位论文10图2-2三种算法求解0-1背包问题的迭代过程Fig.2-2Iterativeprocessofthreealgorithmsforsolving0-1knapsackproblem分析表2-1和图2-2可知，三种算法在最大迭代次数内都可找到0-1背包问题的最优解，但改进粒子群算法相比其它两种算法可以更快的求得最优解，收敛性较好，改进粒子群算法与传统粒子群算法比较收敛速度提高了86%，与WPSO算法相比收敛速度提高了36%。通过比较最优迭代次数和最差迭代次数可知，本文改进的算法稳定性优于其它两种算法，更适合求解背包问题。2.4本章小结本章主要对标准PSO算法进行参数改进，将PSO算法中惯性权重随机递减的变化方式与学习因子c1线性递减、c2线性递增相结合，用于求解离散问题并取得不错的效果。实验采用背包问题作为测试函数，与标准PSO算法，WPSO算法完成参数对比。结果显示，作者改进的PSO算法具有非常快的收敛速度效果。
西安理工大学工程硕士专业学位论文12在连接网图中，节点i和j之间的最短路径的边数叫做节点i到j的距离。平均路径长度是所有结点之间距离的平均值，它用于测量粒子间的信息交换速率，具体的计算如式所示：jiijsNN)1(2L（3-2）式中：sij——节点i和j的距离；L——平均路径长度。(3)平均聚类系数聚类系数为个别部分的以节点为主要面向对象的，就节点i而言，将其相邻的节点集合ki找出，对其网络结构里面的边数Ei进行求取，再除以集合ki可能具有的边的数量，即2/)1(iikk。见下图3-1：一节点相邻的节点）（2,3，二者构成边的数量为1，会形成1条边，所以1=1/1，两节点相邻的节点为）（1,3，二者构成边的数量为1，会形成1条边，所以1=1/1是，三节点相邻的节点为）（1,2,4,5，其构成边的数量为1，会形成）（/234条边，所以1/6=1/6，四节点相邻的节点为）（3，其无法构成边，会构成0条边，所以0，五节点相邻的节点为）（3，其无法构成边，会构成0条边，所以0。因此，节点为五时对应的聚类系数为(1+1+1/6)/5=13/30。图3-1节点连接图Fig.3-1Nodeconnectiondiagram)1i(i2kkEiCi（3-3）式中：Ci——聚类系数；ki——粒子i邻居粒子个数；Ei——ki个邻居粒子在搜索空间中实际存在的边数。NiiCNC11（3-4）式中：C——平均聚类系数；
【参考文献】：
期刊论文
[1]高效求解三维装箱问题的剩余空间最优化算法[J]. 尚正阳,顾寄南,唐仕喜,孙晓红. 计算机工程与应用. 2019(05)
[2]一种自适应权重的并行PSO快速装箱算法[J]. 廖星,袁景凌,陈旻骋. 计算机科学. 2018(03)
[3]基于动态加速因子的粒子群优化算法研究[J]. 滕志军,吕金玲,郭力文,王志新,许恒,袁丽红. 微电子学与计算机. 2017(12)
[4]有向动态拓扑混合作用力微粒群优化算法及可靠性应用[J]. 姚成玉,赵哲谕,陈东宁,檀雪云,吕世君. 机械工程学报. 2017(10)
[5]基于分类学习粒子群优化算法的液压矫直机控制[J]. 张凯,宋锦春,李松,时佳. 机械工程学报. 2017(18)
[6]Dynamic Topology Multi Force Particle Swarm Optimization Algorithm and Its Application[J]. CHEN Dongning,ZHANG Ruixing,YAO Chengyu,ZHAO Zheyu. Chinese Journal of Mechanical Engineering. 2016(01)
[7]基于自适应搜索中心的骨干粒子群算法[J]. 王东风,孟丽,赵文杰. 计算机学报. 2016(12)
[8]自适应小世界粒子群优化算法[J]. 龚月姣,嵇智源. 计算机工程与设计. 2015(06)
[9]单一尺寸长方体三维装箱问题的一种求解算法[J]. 王岩,潘卫平,陈秋莲,崔耀东. 包装工程. 2015(11)
[10]求解三维装箱问题的启发式正交二叉树搜索算法[J]. 刘胜,朱凤华,吕宜生,李元涛. 计算机学报. 2015(08)
硕士论文
[1]价值可变的0-1多背包问题模型及其优化算法研究[D]. 张悦.北京交通大学 2017
[2]基于混合遗传算法的集装箱船三维装箱问题研究[D]. 朱莹.华中科技大学 2016
[3]基于文化算法的三维装箱问题研究[D]. 章翼.太原理工大学 2014
[4]滚装船舶配载优化问题的研究[D]. 金燕燕.大连海事大学 2011
[5]混合遗传算法在集装箱船舶配载中的应用[D]. 史宗耀.长春理工大学 2010
本文编号：2996488
【文章来源】：西安理工大学陕西省
【文章页数】：44 页
【学位级别】：硕士
【部分图文】：
改进粒子群算法流程图
西安理工大学工程硕士专业学位论文10图2-2三种算法求解0-1背包问题的迭代过程Fig.2-2Iterativeprocessofthreealgorithmsforsolving0-1knapsackproblem分析表2-1和图2-2可知，三种算法在最大迭代次数内都可找到0-1背包问题的最优解，但改进粒子群算法相比其它两种算法可以更快的求得最优解，收敛性较好，改进粒子群算法与传统粒子群算法比较收敛速度提高了86%，与WPSO算法相比收敛速度提高了36%。通过比较最优迭代次数和最差迭代次数可知，本文改进的算法稳定性优于其它两种算法，更适合求解背包问题。2.4本章小结本章主要对标准PSO算法进行参数改进，将PSO算法中惯性权重随机递减的变化方式与学习因子c1线性递减、c2线性递增相结合，用于求解离散问题并取得不错的效果。实验采用背包问题作为测试函数，与标准PSO算法，WPSO算法完成参数对比。结果显示，作者改进的PSO算法具有非常快的收敛速度效果。
西安理工大学工程硕士专业学位论文12在连接网图中，节点i和j之间的最短路径的边数叫做节点i到j的距离。平均路径长度是所有结点之间距离的平均值，它用于测量粒子间的信息交换速率，具体的计算如式所示：jiijsNN)1(2L（3-2）式中：sij——节点i和j的距离；L——平均路径长度。(3)平均聚类系数聚类系数为个别部分的以节点为主要面向对象的，就节点i而言，将其相邻的节点集合ki找出，对其网络结构里面的边数Ei进行求取，再除以集合ki可能具有的边的数量，即2/)1(iikk。见下图3-1：一节点相邻的节点）（2,3，二者构成边的数量为1，会形成1条边，所以1=1/1，两节点相邻的节点为）（1,3，二者构成边的数量为1，会形成1条边，所以1=1/1是，三节点相邻的节点为）（1,2,4,5，其构成边的数量为1，会形成）（/234条边，所以1/6=1/6，四节点相邻的节点为）（3，其无法构成边，会构成0条边，所以0，五节点相邻的节点为）（3，其无法构成边，会构成0条边，所以0。因此，节点为五时对应的聚类系数为(1+1+1/6)/5=13/30。图3-1节点连接图Fig.3-1Nodeconnectiondiagram)1i(i2kkEiCi（3-3）式中：Ci——聚类系数；ki——粒子i邻居粒子个数；Ei——ki个邻居粒子在搜索空间中实际存在的边数。NiiCNC11（3-4）式中：C——平均聚类系数；
【参考文献】：
期刊论文
[1]高效求解三维装箱问题的剩余空间最优化算法[J]. 尚正阳,顾寄南,唐仕喜,孙晓红. 计算机工程与应用. 2019(05)
[2]一种自适应权重的并行PSO快速装箱算法[J]. 廖星,袁景凌,陈旻骋. 计算机科学. 2018(03)
[3]基于动态加速因子的粒子群优化算法研究[J]. 滕志军,吕金玲,郭力文,王志新,许恒,袁丽红. 微电子学与计算机. 2017(12)
[4]有向动态拓扑混合作用力微粒群优化算法及可靠性应用[J]. 姚成玉,赵哲谕,陈东宁,檀雪云,吕世君. 机械工程学报. 2017(10)
[5]基于分类学习粒子群优化算法的液压矫直机控制[J]. 张凯,宋锦春,李松,时佳. 机械工程学报. 2017(18)
[6]Dynamic Topology Multi Force Particle Swarm Optimization Algorithm and Its Application[J]. CHEN Dongning,ZHANG Ruixing,YAO Chengyu,ZHAO Zheyu. Chinese Journal of Mechanical Engineering. 2016(01)
[7]基于自适应搜索中心的骨干粒子群算法[J]. 王东风,孟丽,赵文杰. 计算机学报. 2016(12)
[8]自适应小世界粒子群优化算法[J]. 龚月姣,嵇智源. 计算机工程与设计. 2015(06)
[9]单一尺寸长方体三维装箱问题的一种求解算法[J]. 王岩,潘卫平,陈秋莲,崔耀东. 包装工程. 2015(11)
[10]求解三维装箱问题的启发式正交二叉树搜索算法[J]. 刘胜,朱凤华,吕宜生,李元涛. 计算机学报. 2015(08)
硕士论文
[1]价值可变的0-1多背包问题模型及其优化算法研究[D]. 张悦.北京交通大学 2017
[2]基于混合遗传算法的集装箱船三维装箱问题研究[D]. 朱莹.华中科技大学 2016
[3]基于文化算法的三维装箱问题研究[D]. 章翼.太原理工大学 2014
[4]滚装船舶配载优化问题的研究[D]. 金燕燕.大连海事大学 2011
[5]混合遗传算法在集装箱船舶配载中的应用[D]. 史宗耀.长春理工大学 2010
本文编号：2996488
本文链接：https://www.wllwen.com/shoufeilunwen/boshibiyelunwen/2996488.html
