- JavaEightQueensProblem.
Main class which employs random walk algorithm for solving eight queens problem.
- RandomWalkerParameter.
Class which holds random value to shift in each algorithm iteration. Besides it holds two ranges - random value range, which defines number limits for random value and shift step range, which defines number limits for shift step. In each iteration random shift step is added to current random value.
- RandomWalkerUnit.
Class holding list of random walk parameters and state which defines unit has reached terminating value or not. If unit has reached terminating value - subsequent random shifts are not applied to unit parameters. Basically this class is just needed for grouping parameters. For example queen random unit will have two parameters - X,Y. So in queen case both values X,Y will be randomly mutated until queen will reach good position on board. So calculation terminating condition is meaningful only for X,Y pair - i.e. random unit will have two X,Y parameters in list for queen problem case.
- RandomWalker.
Class which executes random walk algorithm. Most important things which should be passed into RandomWalker constructor is: list of random walker units and object which will have method for checking if random walk unit has reached terminal state or not. This method will be then executed dynamically by using java reflection in each subsequent random walk iteration. By the way, you can pass class instance OR class itself into this calculator object parameter. Passing class itself is good if your terminal condition calculation method is static - so in this case you don't have to create class instance for calling method and thus it is reasonable for random walk constructor to accept class object itself. Next when random walker object is constructed one just needs to execute one method named "startRandomWalkSearch()" to begin looking for solution to some problem. This random search algorithm has no special magic in it :-), basic code is simple like this:
public void startRandomWalkSearch() {
Random rnd = new Random();
int iterationsUntilRestart = 0;
initializeRandomWalkUnits();
for (int i = 0; i < iterationsToTry; i++) {
iterationsUntilRestart++;
if (unitsNotInTerminalState == 0) {
iterationsUntilSolution = i + 1;
return;
}
if (iterationsUntilRestart > restartRandomWalkAfterIterations) {
iterationsUntilRestart = 0;
initializeRandomWalkUnits();
continue;
}
for (int iUnit = 0; iUnit < randomWalkUnits.size(); iUnit++) {
if (!randomWalkUnits.get(iUnit).terminalConditionReached) {
for (RandomWalkerParameter randomWalkParameter : randomWalkUnits.get(iUnit).randomWalkerParameters) {
double stepValue;
double stepValueDiff = randomWalkParameter.stepRange[1] - randomWalkParameter.stepRange[0];
// calculate step value
if (randomWalkParameter.onlyIntegralValuesInStep)
stepValue = randomWalkParameter.stepRange[0] + (double)rnd.nextInt((int)(stepValueDiff + 1.0));
else
stepValue = randomWalkParameter.stepRange[0] + stepValueDiff * rnd.nextDouble();
// apply step
randomWalkParameter.value += stepValue;
randomWalkParameter.value = Math.min(randomWalkParameter.value, randomWalkParameter.valueRange[1]);
randomWalkParameter.value = Math.max(randomWalkParameter.value, randomWalkParameter.valueRange[0]);
}
// check terminal condition
Class[] types = new Class[2];
types[0] = List.class;
types[1] = int.class;
try {
boolean isJavaClass = terminalConditionCalculatorObject.getClass().toString().contains("java.lang.Class");
Method method;
if (isJavaClass)
method = ((Class)terminalConditionCalculatorObject).getMethod(terminalConditionCalculatorMethod, types);
else
method = terminalConditionCalculatorObject.getClass().getMethod(terminalConditionCalculatorMethod, types);
randomWalkUnits.get(iUnit).terminalConditionReached =
(boolean)method.invoke(terminalConditionCalculatorObject, randomWalkUnits, iUnit);
if (randomWalkUnits.get(iUnit).terminalConditionReached)
unitsNotInTerminalState--;
}
catch ( NoSuchMethodException |
NullPointerException |
SecurityException |
IllegalAccessException |
InvocationTargetException e) {
throw new RuntimeException(e.toString());
}
}
}
}
}
Algorithm idea is to initialize each unit's parameters to some random value. Then there is for loop which applies small random step to parameter value and then checks if this unit has reached terminal(solution) state or not, by calling terminal condition calculation method using reflection.And there is some unit test package which checks if random walk algorithm works - if you will want to modify algorithm. So you will need to see if random walk has good integrity after that or not :-) There is just one test package:
- RandomWalkerTest.
. What it does is - creates random walk object for performing random search if some number X can be factorized into A * B. This test package has two tests inside - testRandomWalkSearchNumberWasFactorized which tests if number was factorized correctly and test named testRandomWalkSearchNumberWasNotFactorized which expects that factorization must fail, because we pass prime number for factorization, which of course can't be factorized into smaller parts.
Have fun in using random walk search algorithm !!
