在 Python 中实施 Monte Carlo 马尔可夫链时出现错误

Question

我正在尝试使用 numpy 在 Python 2.7 中实现一个简单的马尔可夫链 Monte Carlo。目标是找到 "Knapsack Problem," 的解决方案，其中给定一组价值为 vi 和重量为 wi 的 m 个对象，以及一个容量为 b 的袋子，你找到可以放入你的袋子中的最大价值的对象，以及这些对象是什么。我是夏天开始写代码的，我的知识非常不平衡，所以如果我遗漏了一些明显的东西，我深表歉意，我是自学的，一直在跳来跳去。

系统的代码如下（我把它分成几部分，试图找出问题所在）。

import numpy as np
import random


def flip_z(sackcontents): 
    ##This picks a random object, and changes whether it's been selected or not.
    pick=random.randint(0,len(sackcontents)-1)
    clone_z=sackcontents
    np.put(clone_z,pick,1-clone_z[pick])
    return clone_z

def checkcompliance(checkedz,checkedweights,checkedsack):
    ##This checks to see whether a given configuration is overweight
    weightVector=np.dot(checkedz,checkedweights)
    weightSum=np.sum(weightVector)
    if (weightSum > checkedsack):
        return False
    else:
        return True

def getrandomz(length):
    ##I use this to get a random starting configuration.
    ##It's not really important, but it does remove the burden of choice.       
    z=np.array([])
    for i in xrange(length):
        if random.random() > 0.5:
            z=np.append(z,1)
        else:
            z=np.append(z,0)
    return z

def checkvalue(checkedz,checkedvalue):
    ##This checks how valuable a given configuration is.
    wealthVector= np.dot(checkedz,checkedvalue)
    wealthsum= np.sum(wealthVector)
    return wealthsum

def McKnapsack(weights, values, iterations,sack): 
    z_start=getrandomz(len(weights))
    z=z_start
    moneyrecord=0.
    zrecord=np.array(["error if you see me"])
    failures=0.
    for x in xrange(iterations):
        current_z= np.array ([])
        current_z=flip_z(z)
        current_clone=current_z
        if (checkcompliance(current_clone,weights,sack))==True:
            z=current_clone
            if checkvalue(current_z,values)>moneyrecord:
                moneyrecord=checkvalue(current_clone,values)
                zrecord= current_clone
        else:failures+=1
    print "The winning knapsack configuration is %s" %(zrecord)
    print "The highest value of objects contained is %s" %(moneyrecord)

testvalues1=np.array([3,8,6])
testweights1= np.array([1,2,1])

McKnapsack(testweights1,testvalues1,60,2.)

应该发生以下情况：最大承载能力为 2，它应该在不同的潜在包携带配置之间随机切换，其中有 2^3=8 具有我的测试重量和值喂它，z 中的每个 1 或 0 代表有或没有给定的项目。它应该丢弃权重太大的选项，同时跟踪具有最高值和可接受权重的选项。正确答案是将 1,0,1 视为配置，将 9 视为最大值。每次我使用中等数量的迭代时，我每次都获得 9 个价值，但配置似乎完全随机，并且以某种方式打破了权重规则。我用很多测试数组仔细检查了我的 "checkcompliance" 函数，它似乎可以工作。这些错误的、超重的配置是如何通过我的 if 语句进入我的 zrecord 的？

Answer 1

诀窍在于 z（因此也是 current_z 和 zrecord）最终总是引用内存中完全相同的对象。 flip_z 通过 np.put.

就地修改此对象

一旦找到可以增加 moneyrecord 的新组合，您就可以设置对它的引用——但是在随后的迭代中，您可以继续更改同一引用的数据。

换句话说，像

这样的行

current_clone=current_z
zrecord= current_clone

不要复制，它们只会为内存中的相同数据创建另一个别名。

解决此问题的一种方法是在您发现它是赢家后明确复制该组合：

if checkvalue(current_z, values) > moneyrecord:
    moneyrecord = checkvalue(current_clone, values)
    zrecord = current_clone.copy()

在 Python 中实施 Monte Carlo 马尔可夫链时出现错误

Bug while implementing Monte Carlo Markov Chain in Python

python

numpy

probability

python-2.7