开源项目招募

在正文开始之前，先给Typography这个项目打个广告。Typography（中文名：泰否）的目标是开发成一个高性能的分布式随机采样器，通过采样器我们可以对一些组合优化问题进行求解，或者是解决一些机器学习的生成模型中有可能遇到的采样问题。项目主页链接为：typography: 一个基于Jax与Numpy的自适应高通量采样器，充分利用算力，自动分配采样资源与评分资源，有感兴趣参与到项目开发的童鞋，可以在Issue链接开源人手招募 · Issue #I4LTHQ · Typography/typography - Gitee.com下留下你的邮箱地址，我来邀请你加入项目的Slack群组，共同开发这个基于高性能采样的求解器框架。

了解背包问题

其实背包问题非常的好理解：有一个容量为c的背包，需要从j个物品中挑选若干个装进背包中，使得最终装在背包里的物品总价值最高。 如果用数学公式来表达就是：

其中ωj表示第j个物品的重量，vj表示第j个物品的价值，而θj∈0,1表示是否选取第j个物品装入背包。

背包问题的建模

参考的是 A Tutorial on Formulating and Using QUBO Models 这篇文章，作者也是当年禁忌搜索的创始人Fred Glover，以及Ising formulations of many NP problems这篇文章，QUBO模型和Ising模型之间本身存在着一个等价的转换关系。

虽然问题的最终解是一个硬性的约束条件，但是我们可以通过加惩罚值使其变为一个软约束：

这里加软约束的目的，是把背包容量这个硬性条件解释为：最终装进背包的物品的总重量越接近临界值越好，而不是越小越好。

目标函数的简化

因为常数项在最优化过程中是不影响计算结果的，因此最终保留下来的目标函数为：

相比于找f(θ)的最大值，我们一般更偏向于找最小值，因此一般都会加一个负号使得最大化问题变成一个最小化问题：

到这一步，我们就已经将一个背包问题的求解转换成了一个找目标函数g(θ)的最小值的问题。在通过优化算法寻找到minθg(θ)时，再对此时的onehot(θ)空间进行采样，并得到最终的最优解。这里因为使用的是θ的onehot空间，因此需要将g(θ)的形式再度改变：

背包问题示例

假设我们一共有6个物品，编号分别为[0,1,2,3,4,5]，重量分别为[1,3,5,7,9,11]，价值分别为[2,4,7,8,9,11]，背包总容量为20，最终的目标是找到在背包承重范围内收益最高的配置。有了这些参数之后，原本的硬性约束可以写成如下的形式：

代码实现

第一步我们首先定义好目标函数：

import numpy as np
from jax import numpy as jnp
from jax import vmap
from itertools import product

PENALTY = 20
nodes = 6
c = 20
theta = jnp.array(list(product([0,1],repeat=nodes)))
x = jnp.array(np.random.random((2**nodes,1)))
v = jnp.array([2,4,7,8,9,11])
w = jnp.array([1,3,5,7,9,11])

def single_term(theta, PENALTY, c, w, v):
    return -jnp.dot(v+PENALTY*c*w, theta)

def double_term(theta, PENALTY, w):
    return jnp.sum(PENALTY*jnp.outer(theta,theta)*jnp.outer(w,w))

def cost(theta, PENALTY, c, w, v):
    return single_term(theta, PENALTY, c, w, v)+double_term(theta, PENALTY, w)
vmap_cost = vmap(cost,(0,None,None,None,None))

def normalization(x):
    return x.reshape((2**nodes,1))/jnp.linalg.norm(x)

def objective_function(x, theta, PENALTY, c, w, v):
    x = normalization(x)
    return jnp.sum(vmap_cost(theta*x, PENALTY, c, w, v))

第二步优化采样的概率分布：

from scipy.optimize import minimize

res = minimize(objective_function, x, args=(theta, PENALTY, c, w, v,), method='COBYLA', options={'disp':True,'maxiter':10000})

最后一步使用Typography来对最终结果进行采样：

import typography as typy
from tabulate import tabulate

def get_res(samples, theta, w, v, c):
    return jnp.sum(theta[samples]*w,axis=1)<=c, jnp.sum(theta[samples]*v,axis=1)

opt_x = normalization(res.x)
nums = 10
samples = typy.sampleArray(opt_x, nums=nums)
satisfy, value = get_res(samples, theta, w, v, c)

header=['index']+list(range(nums))
sap = ('samples',)+tuple(samples)
sat = ('satisfy',)+tuple(satisfy)
val = ('value',)+tuple(value)
table=[sap,sat,val]

print(tabulate(table,headers=header))

得到的最终结果如下：

总结

我们这次采样的结果中，最理想的结果的总收益是20，采样得到的序号是3，也就是说，将重量分别为9和11的两个物品放到背包中。虽然我们知道这个解不是最优解，只是一个可行解，但是在10次的采样中就出现了3次，说明在这类的问题中有较大的概率获得到一个效果尚可的可行解。这个问题本身的最优解应该是将重量分别为：1,3,5,11的这四个物品放进背包中，最优总收益是24，那么我们所得到的解的优化率约为83%。单纯就这个案例来说，我们用31.25%的采样率就采到了优化率为83%的解，这就是基于采样的方法求解组合优化问题的框架。而在这个框架中还有众多的优化点，比如建模的优化，优化概率分布过程的算法设计，以及最终的采样方法，以及我们typography采样的性能，都有较大的优化空间。