chocoteam / chocoteam/choco-solver
[BUG] Search.randomStrategy uses the same seed for VariableSelector and ValueSelector
- Dominant language
- Java
- Stars
- 779
- Forks
- 159
- Avg merge
- 6d 9h
- Merged PRs (30d)
- 10
Description
Hello,
## The issue
I found a bug in the way the random seed is used when creating a Search.randomStrategy. The same seed is used for the VariableSelector and the ValueSelector. This makes the two selectors not independent, and is an issue, for example in the next model:
```java
long seed = XXX;
Model model = new Model("RandomIssue");
IntVar x = model.intVar("x", 0, 2, false);
IntVar y = model.intVar("y", 0, 2, false);
IntVar z = model.intVar("z", 0, 2, false);
model.allDifferent(new IntVar[]{x,y,z}).post();
Solver solver = model.getSolver();
solver.setSearch(Search.randomSearch(new IntVar[]{x,y,z}, seed));
```
**Whatever the value of the seed,** the first solution returned by the solving process will be [0,1,2]. This happens because on this particular example, the calls to the random will always be done on the same values on the ValueSelector and on the VariableSelector.
## Some possible fixes
### Modifying the body of Search.randomSearch(...)
Replace the body of the function by
```java
public static IntStrategy randomSearch(IntVar[] vars, long seed) {
java.util.Random random = new java.util.Random(seed);
long valueSelectorSeed = random.nextLong();
IntValueSelector value = new IntDomainRandom(valueSelectorSeed);
IntValueSelector bound = new IntDomainRandomBound(valueSelectorSeed);
IntValueSelector selector = var -> {
if (var.hasEnumeratedDomain()) {
return value.selectValue(var);
} else {
return bound.selectValue(var);
}
};
return intVarSearch(new Random<>(random.nextLong()), selector, vars);
}
```
By generating seeds with the random generator, the seeds will be independent.
### Modifying the type of Search.randomSearch(...)
An other solution is to give an instance of java.util.Random to Search.randomSearch(...), and proceed as the previous . That way, the user would input the random generator.
### Having a global random generator
Maybe the best but most expensive way to do is to have a random generator initialized at the beginning of the program (either by a seed given by the user, or another random generator given by the user), and pass this random generator to all the classes that need to generate random numbers. The same random generator will be used by every class, ensuring that each call to generate a new number is independent from the previous ones.
This fix raises a big problem on how to deal with parallelism.
##
I hope you will be able to find a solution. I don't know if there is a canonical way to deal with randomness in software, my solutions may not be the best ones.
Have a great day.
Contributor guide
Assessment
This issue has not been assessed yet.