在Python中实现蒙特卡罗马尔可夫链时的错误

Question

我试图在Python 2.7中实现一个简单的马尔可夫链蒙特卡罗，使用numpy。目标是找到"背包问题"的解决方案，在这个问题中，给定m个价值为vi，重量为wi的物体，以及一个容量为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()