【NeurIPS 2020】基于蒙特卡罗树搜索的黑箱优化学习搜索空间划分
Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search
目标:从采样(Dt ∩ ΩA)中学习一个边界,从而最大化两方的差异
先使用Kmeans在特征向量上( [x, f(x)] )聚类,然后使用SVM划分出边界
通过learning+splitting构建一个树 --> 根据UCB选择一个区域 --> 在选择的区域上,进行采样
一、通过splitting进行动态树的构建
“Dynamic tree construction via splitting”这一段描述了一种动态树结构的构建方法,该方法通过分割操作来实现。具体来说,这个过程涉及以下几个步骤:
1、性能估计:通过计算在某个区域Ωi内所有样本xi的函数值f(xi)的平均值来估计该区域的性能,其中ni是该区域内样本的数量,xi ∈ Dt ∩ Ωi是在迭代t时收集的样本。
2、迭代收集新样本:在每次迭代中,收集新的样本xi,并且对于这些新样本,区域的性能估计误差|ˆv∗ni − v∗ni|会迅速减小。当这个误差达到一个平稳状态时,意味着不需要再收集新的样本。
3、使用潜在动作分割:一旦性能估计误差达到稳定,LA-MCTS会使用潜在动作来分割当前区域,从而继续精细化两个子区域的价值估计。潜在动作是指通过支持向量机(SVM)学习到的边界,它将节点代表的区域分割成高性能和低性能的两个区域。
4、树的深化:随着越来越多的样本从有希望的区域收集,树会向更好的区域深入,从而更好地引导搜索过程朝向最优解。
5、分割阈值θ:在实践中,使用一个阈值θ作为可调参数来控制分割。如果在任何叶子节点上,Dt ∩ Ωi的大小超过了阈值θ,就会对该叶子节点进行分割。
这个动态树构建过程的目的是为了更好地引导贝叶斯优化(BO)算法,特别是在高维问题中,通过直接在Ωleaves上优化来帮助BO算法避免过度探索,从而提高性能。
我们的搜索树的结构在迭代过程中动态变化,这与LaNAS中使用的预定义固定高度树不同。在迭代开始时,从包含所有样本的根开始,如果任何叶子的样本量超过分裂阈值θ,我们使用潜在动作递归地分裂叶子,例如在图2(a)中为节点B创建节点D和节点E。我们停止树的分裂,直到没有更多的叶子满足分裂标准。然后,树就可以在这个迭代中使用了。
二、通过UCB选择节点
本文使用UCB选择节点而不是贪心算法,因为UCB可以建立对整个搜索空间的全局视图。UCB的定义为每个节点的UCB如下,其中vj是节点j的平均值,nj是节点j的访问次数,np是节点j的父节点的访问次数,Cp是一个可调节的超参数,用于控制探索的程度。
通过从根节点到叶节点的路径选择一个分区进行采样,这个路径上的支持向量机(SVM)共同定义了一个用于采样的区域。例如,在图2(c)中,选择的区域为ΩE。在采样过程中,LA-MCTS在这个受限的搜索空间Ωselected上解决最小化目标函数f(x)的问题。
整个过程的目的是在保持对最有前途区域的关注的同时,确保算法不会过度探索或者忽视潜在的好区域。Cp参数的选择对算法的性能有显著影响,过小的Cp会导致性能下降,因为它可能忽略了探索;而过大的Cp则可能导致过度探索。文档建议将Cp设置为最大目标函数值的10%到1%。
三、通过贝叶斯优化BO进行采样
在文档中,“Sampling via Bayesian Optimizations”这一部分讲述了如何在贝叶斯优化(Bayesian Optimization, BO)框架内进行采样。它描述了在蒙特卡洛树搜索(LA-MCTS)中如何通过选择一条从根到叶的路径来确定一个采样区域。这个区域由路径上的支持向量机(SVM)共同定义,并且在这个区域内进行最小化目标函数f(x)的求解。
在与TuRBO(Truncated Robust Bayesian Optimization)集成的过程中,文档提到了几个关键的调整点:
-
在每次TuRBO重启时,只在选定的区域(Ωselected)内用随机样本进行初始化。由于选定区域的形状可能是任意的,因此使用拒绝采样(均匀采样并用SVM拒绝异常值)来获得Ωselected内的一些点。由于只需要少量样本进行初始化,所以拒绝采样就足够了。
-
TuRBO将一个边界框(bounding box)定位在到目前为止最好的解决方案上,而在LA-MCTS中,中心被限制在Ωselected中的最佳解决方案上。
-
TuRBO从边界框中均匀采样以选择下一个样本,而在LA-MCTS中,TuRBO被限制在边界框与Ωselected的交集中均匀采样。由于中心在Ωselected内,所以交集的存在是有保证的。
在每次迭代中,TuRBO会一直运行,直到信任区域(trust-region)的大小变为0,并且所有评估(例如xi和f(xi))都返回给LA-MCTS,以便在下一次迭代中细化学习到的边界。
这一部分的重点是在高维空间中,特别是在采样区域受限的情况下,如何有效地进行采样。文档提到了一些替代的采样方法,如hit-and-run或Gibbs采样,这些方法可能是拒绝采样的好替代品,因为在高维空间中,拒绝采样可能无法在Ωselected中获得足够的随机样本。文档还提出了一种新的启发式采样方法,即在Ωselected内的每个现有样本x处,绘制一个超立方体,并扩展这个立方体同时拒绝异常值。
Sampling with TuRBO:
here we illustrate the integration of SoTA BO method TuRBO [2] with LA-MCTS. We use TuRBO-1 (no bandit) for solving minf(x) within the selected region, and make the following changes inside TuRBO, which is summarized in Fig. 2(c).
a) At every re-starts, we initialize TuRBO with random samples only in Ωselected. The shape of Ωselected can be arbitrary,so we use the rejected sampling (uniformly samples and reject outliers with SVM) to get a few points inside Ωselected. Since we only need a few samples for the initialization, the reject sampling is sufficient.
b) TuRBO centers a bounding box at the best solution so far, while we restrict the center to be the best solution in Ωselected.
c) TuRBO uniformly samples from the bounding box to feed the acquisition to select the best as the next sample, and we restrict the TuRBO to uniformly sample from the intersection of the bounding box and Ωselected. The intersection is guaranteed to exist because the center is within Ωselected. At each iteration, we keep TuRBO running until the
size of trust-region goes 0, and all the evaluations, i.e. xi and f(xi), are returned to LA-MCTS to
refine learned boundaries in the next iteration. Noted our method is also extensible to other solvers
by following similar procedures.
相关文章:

【NeurIPS 2020】基于蒙特卡罗树搜索的黑箱优化学习搜索空间划分
Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search 目标:从采样(Dt ∩ ΩA)中学习一个边界,从而最大化两方的差异 先使用Kmeans在特征向量上( [x, f(x)] )聚类…...

面试题:线上MySQL的自增id用尽怎么办?
文章目录 前言表定义自增值idInnoDB系统自增row_idXidInnodb trx_id InnoDB数据可见性的核心思想为什么要加248?为何只读事务不分配trx_id?thread_id 总结 前言 MySQL的自增id都定义了初始值,然后不断加步长。虽然自然数没有上限,…...
Java集合框架:Collection 与 Map 接口深度解析
Java的集合框架提供了丰富的工具和数据结构,其中 Collection 和 Map 接口是这个框架的核心。这两个接口分别用于处理一组对象和键值对的映射关系,是Java编程中不可或缺的部分。让我们深入挖掘这两个接口的特性以及它们的实际应用场景。 1. Collection 接…...

qt多线程例子,不断输出数字
dialog.h #include "dialog.h" #include "ui_dialog.h"Dialog::Dialog(QWidget *parent) :QDialog(parent),ui(new Ui::Dialog) {ui->setupUi(this); }Dialog::~Dialog() {delete ui; }// 启动线程按钮 void Dialog::on_startButton_clicked() {//conn…...

基于厨师算法的无人机航迹规划-附代码
基于厨师算法的无人机航迹规划 文章目录 基于厨师算法的无人机航迹规划1.厨师搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要:本文主要介绍利用厨师算法来优化无人机航迹规划。 1.厨师搜索算法 …...
设计模式的六大原则
1、开闭原则(Open Close Principle) 开闭原则的意思是:对扩展开放,对修改关闭。在程序需要进行拓展的时候,不能去修改原有的代 码,实现一个热插拔的效果。简言之,是为了使程序的扩展性好&…...

原文远知行COO张力加盟逐际动力 自动驾驶进入视觉时代?
11月7日,通用足式机器人公司逐际动力LimX Dynamics官宣了两位核心成员的加入。原文远知行COO张力出任逐际动力联合创始人兼COO,香港大学长聘副教授潘佳博士为逐际动力首席科学家。 根据介绍,两位核心成员的加入,证明一家以技术驱…...

【公益案例展】火山引擎公益电子票据服务——连接善意,共创美好
火山引擎公益案例 本项目案例由火山引擎投递并参与数据猿与上海大数据联盟联合推出的 #榜样的力量# 《2023中国数据智能产业最具社会责任感企业》榜单/奖项”评选。 大数据产业创新服务媒体 ——聚焦数据 改变商业 捐赠票据是慈善组织接受捐赠后给捐赠方开具的重要凭证&…...

postman中文乱码
在header中添加这两个: Content-Type application/json;charsetUTF-8 Accept application/json;charsetUTF-8...
设计模式简要介绍
设计模式有很多,较为重要的如下 静态和单例模式 单例模式的本质就是类成员中有一个对象实例 public class Animal{public static string Title "Animal" // 类成员public string Name; // 对象成员public const float Pi 3.14f; // 类成员public rea…...
LeetCode-232. 用栈实现队列(C++)
目录捏 一、题目描述二、示例与提示三、思路四、代码 一、题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的…...

无人机红外相机的畸变矫正
在项目开展过程中,发现大疆M30T的红外相机存在比较明显的畸变问题,因此需要对红外图像进行畸变矫正。在资料检索过程中,发现对红外无人机影像矫正的资料较少,对此,我从相机的成像原理角度出发,探索出一种效…...

C++编程案例讲解-基于结构体的控制台通讯录管理系统
基于结构体的控制台通讯录管理系统 通讯录是一个可以记录亲人、好友信息的工具,系统中需要实现的功能如下: 添加联系人:向通讯录中添加新人,信息包括(姓名、性别、年龄、联系电话、家庭住址)最多记录1000人…...

ASP.NETCore6开启文件服务允许通过url访问附件(图片)
需求背景 最近在做一个工作台的文件上传下载功能,主要想实现上传图片之后,可以通过url直接访问。由于url直接访问文件不安全,所以需要手动开启文件服务。 配置 文件路径如下,其中Files是存放文件的目录: 那么&…...

python爬取Web of science论文信息
一、python爬取WOS总体思路 (一)拟实现功能描述 wos里面,爬取论文的名称,作者名称,作者单位,引用数量 要求:英文论文、期刊无论好坏 检索关键词:zhejiang academy of agricultural sciences、 xianghu lab…...

本地域名 127.0.0.1 / localhost
所谓本地域名就是 只能在本机使用的域名 ,一般在开发阶段使用。 编辑文件 C:\Windows\System32\drivers\etc\hosts。 127.0.0.1 www.baidu.com如果修改失败,可以修改该文件的权限。 原理: 在地址栏输入 域名 之后,浏览器会先进行 DNS…...
Python —— 不同类型的数据长度计算方式
在Python 中,不同类型的数据长度计算方式,有何不同👇 字符串(String) my_string "Hello, World!" string_length len(my_string) print("字符串的长度是:", string_length) //输出…...

NowCoder | 环形链表的约瑟夫问题
NowCoder | 环形链表的约瑟夫问题 OJ链接 思路: 创建带环链表带环链表的删除节点 代码如下: #include<stdlib.h>typedef struct ListNode ListNode; ListNode* ListBuyNode(int x) {ListNode* node (ListNode*)malloc(sizeof(ListNode));node…...
华为政企数据中心网络交换机产品集
产品类型产品型号产品说明 核心/汇聚交换机CE8850-EI-B-B0BCloudEngine 8850-64CQ-EI 提供 64 x 100 GE QSFP28,CloudEngine 8800系列交换机是面向数据中心推出的新一代高性能、高密度、低时延灵活插卡以太网交换机,可以与华为CloudEngine系列数据中心…...

多门店自助点餐+外卖二合一小程序源码系统 带完整搭建教程
随着餐饮业的快速发展和互联网技术的不断进步,越来越多的餐厅开始采用自助点餐和外卖服务。市场上许多的外卖小程序APP应运而生。下面罗峰来给大家介绍一款多门店自助点餐外卖二合一小程序源码系统。该系统结合了自助点餐和外卖服务的优势,为餐厅提供了一…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...

力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
全面解析数据库:从基础概念到前沿应用
在数字化时代,数据已成为企业和社会发展的核心资产,而数据库作为存储、管理和处理数据的关键工具,在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理,到社交网络的用户数据存储,再到金融行业的交易记录处理&a…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”
案例: 某医药分销企业,主要经营各类药品的批发与零售。由于药品的特殊性,效期管理至关重要,但该企业一直面临效期问题的困扰。在未使用WMS系统之前,其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...