量子退火算法入门(3):整数分割问题的QUBO建模

这篇具有很好参考价值的文章主要介绍了量子退火算法入门(3):整数分割问题的QUBO建模。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

整数分割问题:

QUBO建模最重要的就是,把建模对象中的变量映射为binary(0/1 或者 -1/+1)的变量。我先从简单的问题开始说明,让大家有些直观感受。整数分割问题就是一个非常简单,并容易理解的例子。此文参考了日本NTT公司的量子计算指南文档[*1]。

  • 整数分割问题定义:

判断能否将一个N 个整数 a 1 , ・・・ a N a_1,・・・a_N a1,・・・aN 的整数集合分割成两个子集合,并且这两个子集合里的元素之和相等。

  • 例子:
    量子退火算法入门(3):整数分割问题的QUBO建模
    我们可以看到,上面👆的例子,分割后的两个子集合A和B的元素之和都等于6,所以该集合是可以满足整数分割的。

转化为组合优化问题:

之前讲的QUBO的例子里,用的变量都是0或1。其实,还可以是-1或+1,这时候也叫ising模型。求解变量什么时候用0/1,什么用-1/+1,这个之后用例子给大家解释。
这次的问题,是把求解的两个子集合的标签作为-1/+1的变量。如下图所示。
量子退火算法入门(3):整数分割问题的QUBO建模
我们的优化目标就成为了,最小化两个子集合的差值的平方和。大家可以思考一下,如果使用0/1作为子集合A和B的标签,我们要怎么定义最小化的目标函数。
量子退火算法入门(3):整数分割问题的QUBO建模

  • 目标集合为{ 1, 5, 6 }时的目标函数就是:
    量子退火算法入门(3):整数分割问题的QUBO建模
    我们来枚举一下,所有 x i x_i xi 从-1或+1取值的组合结果:
    量子退火算法入门(3):整数分割问题的QUBO建模
    我们可以看到,目标函数值为0时,我们得到了正确的整数分割结果。

目标函数转化为QUBO:

因为已经获得了目标函数,那我们先把多项式展开就好了。展开结果如下图所示:

量子退火算法入门(3):整数分割问题的QUBO建模

因为【 x i x_i xi 从-1或+1取值】这个设定,下面👇的式子是成立的:
・ x i 2 = 1 ・x_i^{2} = 1 xi2=1
所以我们可以得到下面的QUBO结果:
量子退火算法入门(3):整数分割问题的QUBO建模
最后献上Python代码。

PyQUBO实现Ising模型:

之前的目标函数都是展开后的二次多项式,大家可以直接计算出QUBO矩阵。这次使用PyQUBO直接定义目标函数,大家就不用手动求解QUBO矩阵了。

import pyqubo
import neal
x = pyqubo.Array.create('x', shape=(3), vartype='SPIN') # 'SPIN' 就表示目标变量是从{-1, 1}取值。目标变量需要从{0, 1}中取值时,就设定为 'BINARY' 

objective_function = (1 * x[0] + 5 * x[1] + 6 * x[2]) ** 2

model = objective_function.compile() 
bqm = model.to_bqm()

print("我们可以将bqm转为ising或qubo输出")
print(bqm.to_ising())

sa = neal.SimulatedAnnealingSampler()
sampleset = sa.sample(bqm, num_reads=10)
samples = model.decode_sampleset(sampleset)
best_sample = min(samples, key=lambda s: s.energy)

print("求解时,pyqubo内部已经将ising模型转换为qubo的0或1,所以输出结果为0或1")
print(best_sample.sample) 

运行结果如下:

我们可以将bqm转为ising或qubo输出
({'x[2]': 0.0, 'x[0]': 0.0, 'x[1]': 0.0}, {('x[0]', 'x[2]'): 12.0, ('x[1]', 'x[2]'): 60.0, ('x[1]', 'x[0]'): 10.0}, 62.0)
求解时,pyqubo内部已经将ising模型转换为qubo的01,所以输出结果为01
{'x[2]': 1, 'x[0]': 0, 'x[1]': 0}

以上就是一个简单建模的例子。下篇讲旅行商问题的建模。文章来源地址https://www.toymoban.com/news/detail-427392.html

  • 参考文献:[*1] : https://www.nttdata.com/jp/ja/-/media/nttdatajapan/files/news/services_info/2021/012800/012800-01.pdf

到了这里,关于量子退火算法入门(3):整数分割问题的QUBO建模的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 量子退火算法入门(7):如何QUBO中的三次多项式怎么转换?

    本文还是大部分截图来自于:《最適化問題とWildqatを用いた量子アニーリング計算入門》 https://booth.pm/ja/items/1415833 终于有人问到怎么将QUBO中的三次多项式转换为二次多项式了。直接以一个例题开始讲解。中间会用到之前文章里的知识,大家最好读了该系列前两篇之后,再阅

    2023年04月14日
    浏览(37)
  • 模拟退火算法与遗传算法求解多目标优化问题的算法实现(数学建模)

    模拟退火算法是一种全局优化算法,解决的问题通常是找到一个最小化(或最大化)某个函数的全局最优解。它通过模拟物理退火的过程来搜索解空间,在开始时以一定的温度随机生成初始解,然后一步步降低温度,同时在当前解的周围随机搜索新的解,并根据一定概率接受

    2024年02月02日
    浏览(52)
  • 数学建模|通过模拟退火算法求解供货与选址问题:问题二(python代码实现)

    今天继续用模拟退火算法供货与选址问题的问题二,如果还没看过问题一的可以看我之前的博客 数学建模|通过模拟退火算法求解供应与选址问题:问题一(python代码实现)-CSDN博客 这里还是把题目放上来(题目来自数学建模老哥的视频): 那么我们可以分析一下,第一问和

    2024年01月16日
    浏览(55)
  • 数学建模笔记——整数规划类问题之我见(匈牙利算法)

    目录 浅浅叙述匈牙利算法 基本思路 计算步骤 来一道简单例题 1.1 符号规定 1.2目标函数​编辑       1.3约束条件 ​编辑 1.4代码 题目复述 基本假设 问题分析 符号说明  模型的建立与求解 模型建立思路 模型建立的过程 建立0-1整数规划模型  运用匈牙利方法: 代码实现  

    2023年04月11日
    浏览(48)
  • 数学建模-退火算法和遗传算法

    退火算法和遗传算法 一.退火算法 退火算法Matlab程序如下: [W]=load(\\\'D:100个目标经度纬度.txt\\\'); 二、遗传算法 [E]=xlsread(\\\'D:100个目标经度纬度\\\');  % 加载敌方 100 个目标的数据, 数据按照表格中的位置保存在纯文本文件 sj.txt 中 x=[E(:,1)]; y=[E(:,2)]; e =[x y]; d1=[70,40]; e =[d1;  e ;d1];

    2024年02月20日
    浏览(55)
  • 数学建模学习(9):模拟退火算法

    模拟退火算法(Simulated Annealing, SA)的思想借 鉴于固体的退火原理,当固体的温度很高的时候,内能比 较大,固体的内部粒子处于快速无序运动,当温度慢慢降 低的过程中,固体的内能减小,粒子的慢慢趋于有序,最 终,当固体处于常温时,内能达到最小,此时,粒子最为 稳

    2024年02月14日
    浏览(36)
  • 【数学建模学习(9):模拟退火算法】

    模拟退火算法(Simulated Annealing, SA)的思想借 鉴于固体的退火原理,当固体的温度很高的时候,内能比 较大,固体的内部粒子处于快速无序运动,当温度慢慢降 低的过程中,固体的内能减小,粒子的慢慢趋于有序,最 终,当固体处于常温时,内能达到最小,此时,粒子最为 稳

    2024年02月14日
    浏览(40)
  • 数学建模(三):模拟退火算法(SA)

    1、 算法简介 模拟退火算法(simulated annealing,SA)来源于固体退火原理,是一种基于概率的算法。 模拟退火算法(SA)来源于固体退火原理,是一种基于概率的算法。将固体加温至充分高的温度,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,分子和原

    2023年04月17日
    浏览(62)
  • Matlab数学建模算法之模拟退火算法(SA)详解

    🔗 运行环境:Matlab 🚩 撰写作者:左手の明天 🥇 精选专栏:《python》 🔥  推荐专栏:《算法研究》 🔐####  防伪水印——左手の明天 #### 🔐 💗 大家好🤗🤗🤗,我是 左手の明天 !好久不见💗 💗今天分享 matlab数学建模算法 —— 模拟退火算法 💗

    2024年01月16日
    浏览(43)
  • 数学建模--退火算法求解最值的Python实现

    目录 1.算法流程简介 2.算法核心代码 3.算法效果展示

    2024年02月09日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包