【CVRP测评篇】 算法性能如何？来测！

我跨越了2100015秒的距离，为你送上更全面的算法性能评测。

目录

  • 往期优质资源
  • 1 CVRP数据集
  • 2 实验准备
    • 2.1 计算机配置
    • 2.2 调参方法
    • 2.3 参数设定
    • 2.4 实验方法
  • 3 实验结果
    • 3.1 最优解统计
      • 3.1.1各数据集上的算法性能对比
      • 3.1.2 求解结果汇总
      • 3.1.3小结一下
      • 3.1.4 还有话说
    • 3.2 调参时间统计
      • 3.2.1 各数据集上的运算时间对比
      • 3.2.2 运算时间汇总
      • 3.2.3 小结一下
    • 3.3 最优参数统计
    • 3.4 最优解路径
    • 3.5 调参过程
  • 4 结果分析

往期优质资源

CVRP系列
遗传算法
蚁群算法
禁忌搜索算法
模拟退火算法
自适应大邻域算法
粒子群算法
量子粒子群算法
差分进化算法
MDVRP系列
遗传算法
蚁群算法
禁忌搜索算法
模拟退火算法
自适应大邻域算法
粒子群算法
量子粒子群算法
差分进化算法
VRPTW系列
遗传算法
蚁群算法
禁忌搜索算法
模拟退火算法
自适应大邻域算法
粒子群算法
量子粒子群算法
差分进化算法
HVRP系列
遗传算法
蚁群算法
禁忌搜索算法
模拟退火算法
自适应大邻域算法
粒子群算法
量子粒子群算法
差分进化算法
MDHFVRPTW系列
遗传算法
蚁群算法
禁忌搜索算法
模拟退火算法
自适应大邻域算法
粒子群算法
量子粒子群算法
差分进化算法

     小编推出第一期、第二期《CVRP算法系列》（基础篇+改进篇）后，后台收到了很多粉丝的留言。大家最关心的问题可归结为以下两点：

  1. split算法的作用是什么？为什么要采用它？会降低解的质量吗？
  2. 哪个算法效果最好？有和标准数据集对比吗？结果如何？

     今天，小编将通过累计运行 【2100015秒≈35000分钟≈583小时≈24天】 的实验来回答以上问题。
2100015秒！
也许你只需要花费1分钟完成本文的阅读，但只要能帮助到大家就值得！

1 CVRP数据集

     网络上关于CVRP问题的标准数据集好像挺多的，但好像可用的又没那么多。小编今天采用的是下边这个网站数据
在这里插入图片描述
     小编下载了整个CVRP数据集，里面划分了A，B，E，F，G，M，P，V等8个类别（别担心，小编不会都测评）。考虑到时间成本，这里随机从中抽取了11个数据集。参与测评的11个数据集的最优解信息如下。
在这里插入图片描述
     以上各数据集的数据分布如下：

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2 实验准备

2.1 计算机配置

     本次采用Python3.8编程实现，电脑配置为 Intel® Core™ i7-9700F CPU @ 3.00GHz 3.00 GHz，24G内存。

2.2 调参方法

     元启发式算法的求解效果一方面取决于邻域规则，而另一方面则取决于参数设置。而且同一算法在不同数据集上的最优参数组合也可能是不一样的。
     为了尽可能的找到最优的“算法-参数-算例”组合，小编一开始采用的是网格化调参，虽然可以较为精确的找到最优的参数组合，但需要巧妙的设计搜索空间，否则既浪费了计算资源，又没有找到理想结果。尝试了几次后，发现这种方法太耗时耗力，果断放弃！
     随后想到了机器学习邻域常用的贝叶斯调参工具，简单来说，贝叶斯调参是建立在高斯过程基础之上的，根据历史搜索结果建立目标函数和参数之间的函数关系，然后预测最优的参数位置，再将预测的参数带入算法计算，重复这个过程，直至逼近最优的拟合关系。贝叶斯调参不仅效果好，而且省事！只需设定每个参数的搜索空间即可。于是经过一番探索，搞成了！以ACO调参为例，给出具体代码如下：

import time
import xlsxwriter
from ACO_CVRP_Advance import run
from bayes_opt import BayesianOptimization
​
def F(Q,rho,alpha,beta):
    res = []
    file = f'./{filename}'
    for _ in [1,2]:
        _, obj = run(filepath=file, Q=Q, tau0=tau0, alpha=alpha, beta=beta, rho=rho,epochs=epochs,
                     v_cap=v_cap_dict[filename], popsize=popsize)
        res.append(obj)
    return -min(res)
v_cap_dict = {
    'A-n32-k5.csv':100,
    'A-n46-k7.csv':100,
    'A-n80-k10.csv':100,
    'B-n31-k5.csv':100,
    'B-n50-k7.csv':100,
    'B-n78-k10.csv':100,
    'E-n33-k4.csv':8000,
    'E-n51-k5.csv':160,
    'E-n101-k8.csv':200,
    'E-n101-k14.csv':112,
    'P-n40-k5.csv':140,
    'P-n101-k4.csv':400
}
filename = list(v_cap_dict.keys())[11]
tau0 = 2000
popsize = 100
epochs = 300
start_time = time.time()
rf_bo = BayesianOptimization(f=F,pbounds={'rho':(0.001,0.98),'alpha': (0.001, 5),'beta':(0.001,5),'Q':(1000,2000)})
rf_bo.maximize(n_iter=50, init_points=10)
run_time = time.time() - start_time
sp = rf_bo.space
history_obj = sp.target.tolist()
history_pararm = sp.params.tolist()

贝叶斯调参默认是求最大化，因此这里将目标函数取负数

2.3 参数设定

     不同算法在不同算例上的参数搜索空间基本一样，但由于ALNS算法在大规模算例上的求解较为耗时，因此部分算例上做了缩小，这里仅给出其一种搜索空间。
在这里插入图片描述
在这里插入图片描述

2.4 实验方法

     由于元启发式算法具有很大的随机性，相同的参数设置也可能跑出不同的结果，因此设定每组“算法-参数-算例”组合均运行2次，取最好的一组用于反馈贝叶斯。
     为了加快进度，早一点分享给大家，这里同时运行3组代码，因此可能会对解的质量及求解时间产生干扰。

3 实验结果

3.1 最优解统计

3.1.1各数据集上的算法性能对比

     首先来看看在同一算例上，不同算法的表现如何：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3.1.2 求解结果汇总

     以上结果汇总如下：
在这里插入图片描述
     求解误差如下：
在这里插入图片描述

3.1.3小结一下

  1. 整体来看，在实验范围内8个算法均无法找到已知最优解，最小的求解误差为0.39%（ALNS-A-n32-k5）。
  2. ALNS算法在各数据集上的表现大多位列第一（B-n31-k5稍逊于ACO）
  3. ACO算法在各数据集上的表现大多位列第二（在A-n32-k5，B-n31-k5，B-n50-k7三个数据集上稍逊于GA）；
  4. GA算法在各数据集上的表现大多位于第三；
  5. 其他算法的性能不再一一列举啦

3.1.4 还有话说

     虽然根据以上结果来看，基于split算法实现的8个算法并未找到已知最优解（虽然很接近啦），但并不代表就无法找到最优解，一方面小编实现的仅是基本的元启发式算法，还有众多改进版本来提升性能。且，加入启发式规则也是不错的想法。这里以文献[A simple and eBective evolutionary algorithm for the vehicle routing problem] 中的数据来佐证：

在这里插入图片描述
     以后再慢慢设计改进策略~

3.2 调参时间统计

3.2.1 各数据集上的运算时间对比

     除了目标函数外，大家肯定也很关注算法的求解时间如何。这里不再具体去分析某一参数组合下的算法运行时间，而是从整个调参过程的时间消耗来评判。这里根据算例的规模大小进行了排序，尝试去看随着问题规模的增大，算法求解时间的变化趋势，并大致做了数据拟合。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3.2.2 运算时间汇总

     各算法在不同数据集上的求解时间汇总如下：
在这里插入图片描述

3.2.3 小结一下

     整体来看，随着算例规模的增加，各算法的求解时间都呈现出指数增长趋势，ALNS算法和ACO算法的增长速度明显高于其他算法。

3.3 最优参数统计

     8个算法在不同数据集上的最优参数组合如下所示，未在调参范围的参数被设置为默认值。
（1）ACO
在这里插入图片描述
（2）ALNS
在这里插入图片描述
在这里插入图片描述
（3）DE
在这里插入图片描述
（4）DPSO
在这里插入图片描述
（5）GA
在这里插入图片描述
（6）QDPSO
在这里插入图片描述
（7）SA
在这里插入图片描述
（8）TS
在这里插入图片描述

可以看出同一算法在不同数据集上的最优参数组合还是有很大差异的。所以说：调参工作是很重要的！

3.4 最优解路径

     为了尽快地将优质内容分享给各位读者，这里悄悄偷个懒，仅呈现ACO算法在最优参数组合下的优化结果（ALNS算法实在太耗时啦）。此外，由于算法具有随机性，因此在最优参数组合下，不一定保障能得出上述调参时的结果，但差异不大~。
（1）A-n32-k5
在这里插入图片描述
（2）A-n46-k7
在这里插入图片描述
（3）A-n80-k10
在这里插入图片描述
（4）B-n31-k5
在这里插入图片描述
（5）B-n50-k7
在这里插入图片描述
（6）B-n78-k10
在这里插入图片描述
（7）E-n33-k4
在这里插入图片描述
（8）E-n51-k5
在这里插入图片描述
（9）E-n101-k8
在这里插入图片描述
（10）E-n101-k14
在这里插入图片描述
（11）P-n40-k5
在这里插入图片描述
（12）P-n101-k4
在这里插入图片描述

3.5 调参过程

     12套数据集×8套算法=96组结果，实在太多啦，根本分析不完。这里仅以【A-n32-k5】数据集为例，分析使用贝叶斯调参时个别算法的参数探索过程。
（1）ACO
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
（2）ALNS
在这里插入图片描述
在这里插入图片描述
（3）DE
在这里插入图片描述
在这里插入图片描述
（4）DPSO
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
（5）GA
在这里插入图片描述
在这里插入图片描述

从上图可以看出，贝叶斯工具会逐渐形成一个高密度采样区，这也是高斯过程的体现（一人之见）。

4 结果分析

     好了，估计各位读者也看累了。长话短说，这里对开头读者的问题做以下回答。

问题一：为什么使用split？会影响求解质量吗？

  1. split方法允许用户采用无车场信息的编码方式（文献中叫做 ‘TSP-like permutation chromosomes’），把容量、时间、里程等约束交给split处理，这样就无需在迭代中反复检查/修复不可行解，便于直接使用各算法的邻域搜索过程。
  2. 特定的split会建立TSP-like permutation chromosomes’ 与车辆路径集合的唯一映射。反过来思考的话，最优解也对应一个唯一的TSP-like permutation
    chromosomes’，因此找到最优的TSP-like permutation
    chromosomes’，就可以找到原问题的最优解。这里究竟影响多大，小编暂时无从考证。
  3. 学习过小编分享的算法的读者应该知道，小编推出的各系列VRP问题，都具有类似的代码架构，其最大的区别在于split机制不同，代码具有很强的迁移和扩展性，这也是小编推崇的原因。

问题二：与标准数据集对比如何？

  1. 上述实验结果大概率代表了目前的代码版本的求解效果：尚无法找到测试数据集的已知最优解，但很接近啦
  2. 从目标函数来看，ALNS，ACO，GA的效果都是很不错的。兼顾时间的话，ACO和GA可能更占优势。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/32952.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【软考网络管理员】2023年软考网管初级常见知识考点（10）- 网际协议IP及IPV6，IPV4详解

【软考网络管理员】2023年软考网管初级常见知识考点（10）- 网际协议IP及IPV6，IPV4详解

涉及知识点 分类的IP地址，子网划分，CIDR和路由汇聚，IPV4数据报格式，IPV6协议，软考网络管理员常考知识点，软考网络管理员网络安全，网络管理员考点汇总。 原创于：CSDN博主-《拄杖盲学…
阅读更多...
剑指 Offer 68 - II. 二叉树的最近公共祖先 / LeetCode 236. 二叉树的最近公共祖先（搜索与回溯）

剑指 Offer 68 - II. 二叉树的最近公共祖先 / LeetCode 236. 二叉树的最近公共祖先（搜索与回溯）

题目： 链接：剑指 Offer 68 - II. 二叉树的最近公共祖先；LeetCode 236. 二叉树的最近公共祖先 难度：中等 上一题博客：剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 / LeetCode 235. 二叉搜索树的最近公共祖先&#xf…
阅读更多...
SSH远程直连Docker容器

SSH远程直连Docker容器

文章目录 1. 下载docker镜像2. 安装ssh服务3. 本地局域网测试4. 安装cpolar5. 配置公网访问地址6. SSH公网远程连接测试7.固定连接公网地址8. SSH固定地址连接测试8. SSH固定地址连接测试 转载自cpolar极点云文章：SSH远程直连Docker容器 在某些特殊需求下,我们想ssh…
阅读更多...
机器学习李宏毅学习笔记34

机器学习李宏毅学习笔记34

文章目录 前言一、Knowledge distillation二、Parameter quantization三、Architecture design四、Dynamic computation总结 前言 神经网络压缩（二）其他方法 一、Knowledge distillation 先train一个大的network叫做teacher network，小的ne…
阅读更多...
Vue3：计算属性、监听器

Vue3：计算属性、监听器

computed 计算属性 计算属性是指 基于现有状态派生 (演变) 出新的状态，现有状态发生变化，派生状态重新计算。 computed 接收回调函数作为参数，基于回调函数中使用的响应式数据进行计算属性的创建，回调函数的返回值就是基于现有状态…
阅读更多...
壳牌小程序笔记

壳牌小程序笔记

壳牌加油站 uni-app-基础-day01 概览 为什么要学uni-app？ 现在很多中小型公司，都有自己的小程序项目，然后开发小程序就会用到uni-app。 uni-app没有诞生之前，怎么写小程序 使用原生微信小程序这个框架去开发？ 只…
阅读更多...
解析vcruntime140.dll文件，缺失了要怎么去修复？

解析vcruntime140.dll文件，缺失了要怎么去修复？

在计算机的世界中，vcruntime140.dll是一个重要的动态链接库文件。然而，有时候这个文件可能会引发一系列问题，影响应用程序的正常运行。如果你缺少了vcruntime140.dll，那么你的程序就会打不开，今天我们一起来聊聊vcrunt…
阅读更多...
鸟类识别Python，基于TensorFlow卷积神经网络【实战项目】

鸟类识别Python，基于TensorFlow卷积神经网络【实战项目】

一、介绍 鸟类识别系统，使用Python作为主要开发语言，基于深度学习TensorFlow框架，搭建卷积神经网络算法。并通过对数据集进行训练，最后得到一个识别精度较高的模型。并基于Django框架，开发网页端操作平台，…
阅读更多...
Linux Ubuntu man文档的图文安装教程

Linux Ubuntu man文档的图文安装教程

文章目录 前言man文档的起源man文档的安装man文档的使用总结 前言 当提及"man文档"时，通常是指Unix和类Unix系统中的手册页（man page），因为Linux是在Unix的基础上发展而来的操作系统，所以我们的Linux也有ma…
阅读更多...
IIS安装localhost显示下载，urlrewrite设置

IIS安装localhost显示下载，urlrewrite设置

1.取消ftp服务勾选 2. ping localhost ping 127.0.0.1 如果显示 ：：1 则需要禁用ipv6 在注册表 找到并单击下面的注册表子项： HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Tcpip6\Parameters\ 双击“DisabledComponents”以修…
阅读更多...
【机器学习】sklearn数据集的使用，数据集的获取和划分

【机器学习】sklearn数据集的使用，数据集的获取和划分

「作者主页」：士别三日wyx 「作者简介」：CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」：对网络安全感兴趣的小伙伴可以关注专栏《网络安全入门到精通》 sklearn数据集 二、安装sklearn二、获取数据集三、…
阅读更多...
从电源 LED 读取智能手机的秘密？

从电源 LED 读取智能手机的秘密？

研究人员设计了一种新的攻击方法，通过记录读卡器或智能手机打开时的电源 LED，使用 iPhone 摄像头或商业监控系统恢复存储在智能卡和智能手机中的加密密钥。 众所周知，这是一种侧信道攻击。 通过密切监视功耗、声音、电磁辐射或执行操作所需…
阅读更多...
STC单片机存储器介绍和使用

STC单片机存储器介绍和使用

STC单片机存储器介绍和使用 🌿STC15F2K60S2系列内部结构框图 🌿STC12C5A60S2系列内部结构框图 📑程序存储器(ROM/Flash) 🔖STC单片机ROM容量大小可以根据其型号和命名规则了解到。 🌿STC15
阅读更多...
WiSA Technologies开始接受WiSA E多声道音频开发套件的预订

WiSA Technologies开始接受WiSA E多声道音频开发套件的预订

美国俄勒冈州比弗顿市 — 2023年6月13日 — 为智能设备和下一代家庭娱乐系统提供沉浸式无线声效技术的领先供应商WiSA Technologies股份有限公司（NASDAQ股票代码：WISA）宣布：该公司现在正在接受其WiSA E开发套件的预订。WiSA E使用…
阅读更多...
【深度学习】6-1 卷积神经网络 - 卷积层

【深度学习】6-1 卷积神经网络 - 卷积层

卷积神经网络(Convolutional Neural Network，CNN)。 CNN 被用于图像识别、语音识别等各种场合，在图像识别的比赛中，基于深度学习的方法几乎都以 CNN 为基础。 首先，来看一下 CNN 的网络结构，了解 CNN 的大致框架。CNN…
阅读更多...
macOS编译开源全景拼接库OpenPano

macOS编译开源全景拼接库OpenPano

1. 准备工具 clang与cmake 如果要处理png文件要下载安装libjpeg 安装相当依赖: brew install gnu-sed brew install libjpeg brew install eigen brew install libomp2.克隆源码 git clone --recursive https://github.com/ppwwyyxx/OpenPano.git 3.编译 mkdir build cd …
阅读更多...
力扣 404. 左叶子之和

力扣 404. 左叶子之和

题目来源：https://leetcode.cn/problems/sum-of-left-leaves/description/ C题解1：递归法，前序遍历。 1. 确定输入参数：当前节点，左叶子的和； 2. 确定终止条件：空节点时返回； 3. …
阅读更多...
Java的Stream流详细讲解

Java的Stream流详细讲解

一.Stream 是什么 Stream是Java 8新增的重要特性, 它提供函数式编程支持并允许以管道方式操作集合. 流操作会遍历数据源, 使用管道式操作处理数据后生成结果集合, 这个过程通常不会对数据源造成影响。 ​ 同时stream不是一种数据结构，它只是某种数据源的一个视图&…
阅读更多...
用Python写了一个下载网站所有内容的软件，可见即可下

用Python写了一个下载网站所有内容的软件，可见即可下

目录标题 前言效果展示环境介绍:代码实战获取数据获取视频采集弹幕采集评论 GUI部分尾语 前言 嗨喽~大家好呀，这里是魔王呐 ❤ ~! 今天我们分享一个用Python写下载视频弹幕评论的代码。 顺便把这些写成GUI，把这些功能放到一起让朋友用起来更方便~ 效果…
阅读更多...
Debezium系列之：深入理解tinyint(n)

Debezium系列之：深入理解tinyint(n)

Debezium系列之：深入理解tinyint 一、背景二、相关技术博客三、查看表的ddl四、深入理解tinyint(n)五、创建表六、插入数据七、查看topic数据八、总结一、背景 数据库修改了字段类型为tinyint，希望采集的时候能够转化为boolean类型，数据库字段类型如下图所示： 在设置了conv…
阅读更多...
最新文章

Copyright @ 2022~2023