基于定向变异布谷鸟算法的配送路径问题
发布时间：2021-01-16 12:11
在货物配送路径规划问题中,为了保持基本布谷鸟算法中莱维飞行机制与偏好随机游动策略的特点,文中提出了基于定向变异的布谷鸟算法和求解配送路径问题的完整有效方法。首先采用快速排序法将实数编码个体的每一维元素映射成问题的城市编号,从而建立算法与问题模型之间的联系;然后运用邻域搜索法决定城市访问的次序,即通过各城市之间的距离寻找当前城市的邻近城市,以增强算法的收敛速度。同时,在算法局部搜索机制中,通过平均适应度函数将算法划分为双子群,然后针对不同的子群体采用相应的定向变异机制,从而使算法搜索具有目的性,以增强算法的局部搜索能力。对标准TSP数据库中测试算例的求解实验结果表明,所提算法在各个算例中的求解偏差率均有明显降低,无论在最优值还是平均值的偏差率上都小于其他几种对比算法,对于路径规划问题的求解效果较优。
【文章来源】：计算机科学. 2019,46(07)北大核心
【文章页数】：7 页
【部分图文】：
图５Ｃｈｉｎａ３１的适应度对比曲线Ｆｉｇ．５ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＣｈｉｎａ３１
，本文也通过图６－图１０对ＤＶＣＳ算法在５个算例上求解的最优路径进行了展示。图６Ｂｕｒｍａ１４上的最优路径Ｆｉｇ．６ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＢｕｒｍａ１４图７Ｕｌｙｓｓｅｓｓ１６上的最优路径Ｆｉｇ．７ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＵｌｙｓｓｅｓｓ１６图８Ｕｌｙｓｓｅｓｓ２２上的最优路径Ｆｉｇ．８ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＵｌｙｓｓｅｓｓ２２图９Ｅｉｌ５１上的最优路径Ｆｉｇ．９ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＥｉｌ５１图１０Ｃｈｉｎａ３１上的最优路径Ｆｉｇ．１０ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＣｈｉｎａ３１由图６－图１０可知，本文算法所求最优路径的走势清晰，并未出现任何路径交叉现象，这说明ＤＶＣＳ算法在求解货物配送路径规划问题时具有一定的优势，且此算法在实际问题的应用中也具有较好的适应性与可行性。结束语本文针对货物配送路径规划问题，设计了一种映射关系，从而将离散型的问题转化为连续型问题进行求解，并提出了一种ＤＶＣＳ求解算法。首先运用快速排序法将实数编码的种群个体映射成问题中车辆团队需要访问的城市编号，从而建立算法与实际问题模型之间的关系。然后运用各城市之间的距离进行邻域搜索，决定各城市的访问次序，此种方式通过对邻近城市的搜索可以加快算法的收敛速度，提高算法搜索的效率。同时，采用定向变异的方式优化布谷鸟算法的局部搜索机制，通过平均适应度函数将种群个体分为优质子群体与劣质子群体两类，针对不同子群体，采用不同的变异机制，从而保持算法种群的灵活性与多样性，增
图１Ｂｕｒｍａ１４的适应度对比曲线Ｆｉｇ．１ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＢｕｒｍａ１４图２Ｕｌｙｓｓｅｓｓ１６的适应度对比曲线Ｆｉｇ．２ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＵｌｙｓｓｅｓｓ１６图３Ｕｌｙｓｓｅｓｓ２２的适应度对比曲线Ｆｉｇ．３ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＵｌｙｓｓｅｓｓ２２图４Ｅｉｌ５１的适应度对比曲线Ｆｉｇ．４ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＥｉｌ５１图５Ｃｈｉｎａ３１的适应度对比曲线Ｆｉｇ．５ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＣｈｉｎａ３１上述实验结果显示：本文算法在５个算例上的收敛速度明显快于其他３种算法，且在寻优过程中出现拐点的次数较少，尤其是算例Ｕｌｙｓｓｅｓ１６上的收敛曲线在算法搜索前期收敛速度非常快，收敛曲线几乎垂直向下并且曲线较为光滑。对于算例Ｂｕｒｍａ１４，虽然ＤＶＣＳ算法前期的收敛速度与其他３种算法相差无几，但是该算法仍在进行深度挖掘。对于算例Ｕｌｙｓｓｅｓ２２，４种算法均出现了多处拐点，但是本文算法的收敛速度仍快于其他３种算法，且跳离局部极值的速度也较快。对于算例Ｅｉｌ５１、Ｃｈｉｎａ３１（中国３１个城市），本文算法呈弧状形态并不断进行深度搜索，而其他３种算法在搜索后期几乎呈水平直线状态，搜索能力减弱。基于上述分析，本文算法寻优曲线的下降速度均快于其他算法，收敛速度得到了提升。这是因为本文算法在映射过程中，通过邻域搜索方式中邻近表的决策使每次访问的城市都以自身最近城市为出发点进行访问，从而缩短了路径的距离，增强了算法的收敛速度。以
【参考文献】：
期刊论文
[1]基因-表现型的布谷鸟算法求解旅行商问题[J]. 林敏,钟一文,刘必雄,林晓宇. 计算机工程与应用. 2017(24)
[2]混合模拟退火的布谷鸟算法研究[J]. 马灿,刘坚,余方平. 小型微型计算机系统. 2016(09)
[3]求解TSP问题的离散狼群算法[J]. 吴虎胜,张凤鸣,李浩,梁晓龙. 控制与决策. 2015(10)
[4]新型元启发式布谷鸟搜索算法[J]. 李煜,马良. 系统工程. 2012(08)
硕士论文
[1]混合遗传算法和模拟退火算法在TSP中的应用研究[D]. 刘锦.华南理工大学 2014
本文编号：2980807
【文章来源】：计算机科学. 2019,46(07)北大核心
【文章页数】：7 页
【部分图文】：
图５Ｃｈｉｎａ３１的适应度对比曲线Ｆｉｇ．５ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＣｈｉｎａ３１
，本文也通过图６－图１０对ＤＶＣＳ算法在５个算例上求解的最优路径进行了展示。图６Ｂｕｒｍａ１４上的最优路径Ｆｉｇ．６ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＢｕｒｍａ１４图７Ｕｌｙｓｓｅｓｓ１６上的最优路径Ｆｉｇ．７ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＵｌｙｓｓｅｓｓ１６图８Ｕｌｙｓｓｅｓｓ２２上的最优路径Ｆｉｇ．８ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＵｌｙｓｓｅｓｓ２２图９Ｅｉｌ５１上的最优路径Ｆｉｇ．９ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＥｉｌ５１图１０Ｃｈｉｎａ３１上的最优路径Ｆｉｇ．１０ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＣｈｉｎａ３１由图６－图１０可知，本文算法所求最优路径的走势清晰，并未出现任何路径交叉现象，这说明ＤＶＣＳ算法在求解货物配送路径规划问题时具有一定的优势，且此算法在实际问题的应用中也具有较好的适应性与可行性。结束语本文针对货物配送路径规划问题，设计了一种映射关系，从而将离散型的问题转化为连续型问题进行求解，并提出了一种ＤＶＣＳ求解算法。首先运用快速排序法将实数编码的种群个体映射成问题中车辆团队需要访问的城市编号，从而建立算法与实际问题模型之间的关系。然后运用各城市之间的距离进行邻域搜索，决定各城市的访问次序，此种方式通过对邻近城市的搜索可以加快算法的收敛速度，提高算法搜索的效率。同时，采用定向变异的方式优化布谷鸟算法的局部搜索机制，通过平均适应度函数将种群个体分为优质子群体与劣质子群体两类，针对不同子群体，采用不同的变异机制，从而保持算法种群的灵活性与多样性，增
图１Ｂｕｒｍａ１４的适应度对比曲线Ｆｉｇ．１ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＢｕｒｍａ１４图２Ｕｌｙｓｓｅｓｓ１６的适应度对比曲线Ｆｉｇ．２ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＵｌｙｓｓｅｓｓ１６图３Ｕｌｙｓｓｅｓｓ２２的适应度对比曲线Ｆｉｇ．３ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＵｌｙｓｓｅｓｓ２２图４Ｅｉｌ５１的适应度对比曲线Ｆｉｇ．４ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＥｉｌ５１图５Ｃｈｉｎａ３１的适应度对比曲线Ｆｉｇ．５ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＣｈｉｎａ３１上述实验结果显示：本文算法在５个算例上的收敛速度明显快于其他３种算法，且在寻优过程中出现拐点的次数较少，尤其是算例Ｕｌｙｓｓｅｓ１６上的收敛曲线在算法搜索前期收敛速度非常快，收敛曲线几乎垂直向下并且曲线较为光滑。对于算例Ｂｕｒｍａ１４，虽然ＤＶＣＳ算法前期的收敛速度与其他３种算法相差无几，但是该算法仍在进行深度挖掘。对于算例Ｕｌｙｓｓｅｓ２２，４种算法均出现了多处拐点，但是本文算法的收敛速度仍快于其他３种算法，且跳离局部极值的速度也较快。对于算例Ｅｉｌ５１、Ｃｈｉｎａ３１（中国３１个城市），本文算法呈弧状形态并不断进行深度搜索，而其他３种算法在搜索后期几乎呈水平直线状态，搜索能力减弱。基于上述分析，本文算法寻优曲线的下降速度均快于其他算法，收敛速度得到了提升。这是因为本文算法在映射过程中，通过邻域搜索方式中邻近表的决策使每次访问的城市都以自身最近城市为出发点进行访问，从而缩短了路径的距离，增强了算法的收敛速度。以
【参考文献】：
期刊论文
[1]基因-表现型的布谷鸟算法求解旅行商问题[J]. 林敏,钟一文,刘必雄,林晓宇. 计算机工程与应用. 2017(24)
[2]混合模拟退火的布谷鸟算法研究[J]. 马灿,刘坚,余方平. 小型微型计算机系统. 2016(09)
[3]求解TSP问题的离散狼群算法[J]. 吴虎胜,张凤鸣,李浩,梁晓龙. 控制与决策. 2015(10)
[4]新型元启发式布谷鸟搜索算法[J]. 李煜,马良. 系统工程. 2012(08)
硕士论文
[1]混合遗传算法和模拟退火算法在TSP中的应用研究[D]. 刘锦.华南理工大学 2014
本文编号：2980807
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/2980807.html
