3

我正在实现一个模拟退火（SA）算法，我需要在其中复制状态（例如，记住迄今为止的最佳解决方案）。

我实现了一个复制方法，因为不鼓励使用 java 的clone().

SA 是一种启发式算法，因此下一步要采取的措施是随机确定的。这是通过使用Random我也想复制的对象来完成的。

虽然算法不需要它，但我希望副本具有完全相同的状态。但这只是这种情况，如果我在对象创建后直接进行“复制”并使用相同的种子对其进行初始化。

但是如果我在复制过程之前随机执行一些操作，对象的内在状态（即种子）会Random发生变化，并且复制的行为会有所不同。

那么我怎样才能得到一个实例的精确副本java.util.Random呢？

例子

public class State
{
  private final Random r;
  private final long seed;

  private Object currentOperand;

  public State()
  {
    this(System.nanoTime(), null);
  }

  private State(long seed, Object currentOperand)
  {
    this.seed = seed;
    this.r = new Random(seed);
    this.currentOperand = currentOperand;
  }

  public State copy()
  {
    return new State(seed, currentOperand);
  }

  public void doSth()
  {
    /* operation with random operand */
    currentOperand = r.nextInt(100);
  }

  public void redo()
  {
    // redo then set to null
    currentOperand = null;
  }

  /* for completeness' sake... since it's simulated annealing */
  public int computeEnergy() { return 0; }
}
4

3 回答 3

3

我想出了一个自己的解决方案。它主要覆盖next()in Random（因为所有其他方法都依赖于那个），以及其他一些保持一致性的东西。

它提供了调用此方法的实例的精确副本（制作随机实例的副本是否有意义是另一个话题......^^）。它的行为应该完全像它的超类，至少这是我的意图。

随意添加您的想法！

由于其他问题是关于获取种子的：人们可以轻松地getSeed()在我的解决方案中添加一种方法。或者getInitialSeed()，getCurrentSeed()。

/* Bounded parameter type since a class that implements this interface
 * should only be able to create copies of the same type (or a subtype).
 */
public interface Copyable<T extends Copyable<T>>
{
  public T copy();
}

public class CopyableRandom extends Random implements Copyable<CopyableRandom>
{
  private final AtomicLong seed = new AtomicLong(0L);

  private final static long multiplier = 0x5DEECE66DL;
  private final static long addend = 0xBL;
  private final static long mask = (1L << 48) - 1;

  public CopyableRandom() { this(++seedUniquifier + System.nanoTime()); }
  private static volatile long seedUniquifier = 8682522807148012L;

  public CopyableRandom(long seed) { this.seed.set((seed ^ multiplier) & mask); }

  /* copy of superclasses code, as you can seed the seed changes */
  @Override
  protected int next(int bits)
  {
    long oldseed, nextseed;
    AtomicLong seed_ = this.seed;
    do
    {
      oldseed = seed_.get();
      nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed_.compareAndSet(oldseed, nextseed));
    return (int) (nextseed >>> (48 - bits));
  }

  /* necessary to prevent changes to seed that are made in constructor */
  @Override
  public CopyableRandom copy() { return new CopyableRandom((seed.get() ^ multiplier) & mask); }

  public static void main(String[] args)
  {
    CopyableRandom cr = new CopyableRandom();

    /* changes intern state of cr */
    for (int i = 0; i < 10; i++)
      System.out.println(cr.nextInt(50));

    Random copy = cr.copy()

    System.out.println("\nTEST: INTEGER\n");
    for (int i = 0; i < 10; i++)
      System.out.println("CR\t= " + cr.nextInt(50) + "\nCOPY\t= " + copy.nextInt(50) + "\n");

    Random anotherCopy = (copy instanceof CopyableRandom) ? ((CopyableRandom) copy).copy() : new Random();
    System.out.println("\nTEST: DOUBLE\n");
    for (int i = 0; i < 10; i++)
      System.out.println("CR\t= " + cr.nextDouble() + "\nA_COPY\t= " + anotherCopy.nextDouble() + "\n");
  }
}

这里主要方法的输出：

19
23
26
37
41
34
17
28
29
6

TEST: INTEGER

CR      = 3
COPY    = 3

CR      = 18
COPY    = 18

CR      = 25
COPY    = 25

CR      = 9
COPY    = 9

CR      = 24
COPY    = 24

CR      = 5
COPY    = 5

CR      = 15
COPY    = 15

CR      = 5
COPY    = 5

CR      = 30
COPY    = 30

CR      = 26
COPY    = 26


TEST: DOUBLE

CR      = 0.7161924830704971
A_COPY  = 0.7161924830704971

CR      = 0.06333509362539957
A_COPY  = 0.06333509362539957

CR      = 0.6340753697524675
A_COPY  = 0.6340753697524675

CR      = 0.13546677259518425
A_COPY  = 0.13546677259518425

CR      = 0.37133033932410586
A_COPY  = 0.37133033932410586

CR      = 0.796277965335522
A_COPY  = 0.796277965335522

CR      = 0.8610310118615391
A_COPY  = 0.8610310118615391

CR      = 0.793617231340077
A_COPY  = 0.793617231340077

CR      = 0.3454111197621874
A_COPY  = 0.3454111197621874

CR      = 0.25314618087856255
A_COPY  = 0.25314618087856255

我还进行了一项测试，将 CopyableRandom 与 Random 进行了比较。它产生了相同的结果。

long seed = System.nanoTime();

Random cr  = new CopyableRandom(seed);
Random cmp = new Random(seed);
于 2013-08-30T11:00:06.753 回答
3

我知道这是一个可以接受答案的老问题，但我在自己寻找答案时遇到了这个问题，我最终采取了不同的方法。

看到上面的 Mike's note that Randomimplements Serializable，我只是用它来制作副本：

/**
 * Uses serialization to create a copy of the given Random, needed for
 * repeatability in some tests.
 */
public static Random cloneRandom(Random src) throws Exception {
    ByteArrayOutputStream bo = new ByteArrayOutputStream();
    ObjectOutputStream oos = new ObjectOutputStream(bo);
    oos.writeObject(src);
    oos.close();
    ObjectInputStream ois = new ObjectInputStream(
            new ByteArrayInputStream(bo.toByteArray()));
    return (Random)(ois.readObject());
}

它的性能可能不如 mike 的好CopyableRandom，但它更简单，并且足以满足我的小单元测试。

（我有一个现有的单元测试，它从Random一个已知种子开始，然后执行了一系列操作；我试图在测试中间Random添加一点，并且想要一个; 调用或类似的副本nextLong()在中间获得/a种子的测试将改变种子，炸毁测试的其余部分。真的我只是想要类似的东西Random.getSeed()。）

于 2019-01-12T03:32:58.783 回答
1

我认为你应该在你的State班级中存储，不仅是开始种子，而且还包括nextInt()你已经完成的呼叫次数。Random 这是由于生成伪随机数字序列的内在事实。那是：

伪随机数生成器可以使用种子状态从任意起始状态开始。此后，当使用该状态初始化时，它将始终产生相同的序列

让我先用一个示例来解释一下：

public static void main(String[] args){

     Random r = new Random(42);      
     Random s = new Random(42);

     for(int i = 0; i < 5; i++){
       System.out.println("First random " +r.nextInt());
     }

     for(int i = 0; i < 5; i++){
       System.out.println("Second random " +s.nextInt());
     }

  }

结果是：

First random -1170105035
First random 234785527
First random -1360544799
First random 205897768
First random 1325939940
Second random -1170105035
Second random 234785527
Second random -1360544799
Second random 205897768
Second random 1325939940

由于两个 Random 实例都以相同的种子开始，我总是得到相同的数字序列。

因此，在复制对象时，您应该将新对象初始化Random到相同的源种子（您已经这样做了）并“消耗”您已经在源对象中使用的尽可能多的调用nextInt()（这就是您必须保留该数字的原因）。

完成此操作后，nextInt()在副本上调用 将为您提供与源对象相同的结果。我希望我的代码足以重构你的代码，让你理解我的解决方案。

要了解更好的伪随机数生成器 (PRNG)，也称为确定性随机位生成器 (DRBG)，您可以查看此Wikipedia 文章

于 2013-08-29T20:54:08.183 回答