Improvement MDP¶
Here we will build a improvement method for the MDP problem that we will be adding to the random constructive we have built. If you haven't done it yet, maybe you should start by reading this page "Random MDP". There you will find the problem's definition, how to how to build a random constructive and how to execute the experiment.
Our MDPLocalSearch class must extend the framework's AbstractImprovementMethod<MDPSolution, MDPInstance> generic class. We have implemented a local search based on the "best improvement" tactic. For a given solution we select the worst node and substitute it with the best node we can find. We repeat until the worst node can't be improved.
package es.optsicom.problem.mdp.constructives;
import es.optsicom.framework.approx.improvement.AbstractImprovementMethod;
import es.optsicom.problem.mdp.approx.MDPInstance;
import es.optsicom.problem.mdp.approx.MDPSolution;
public class MDPLocalSearch extends
AbstractImprovementMethod<MDPSolution, MDPInstance> {
@Override
public boolean internalImproveSolution(MDPSolution solution, long millis) {
int change;
double tempval;
boolean nodeChanged;
double initialWeight = solution.getWeight();
do {
nodeChanged = false;
change = solution.getWorst();
for (int i = 0; i < solution.getInstance().getN(); i++) {
if (!solution.belongs(i)) {
tempval = solution.nodeValue(change, i);
if (tempval > solution.getValue(change)) {
solution.nodeChange(change, i);
initialWeight = solution.getWeight();
nodeChanged = true;
}
}
}
} while (nodeChanged);
return solution.getWeight() > initialWeight;
}
@Override
public boolean isDeterminist() {
return false;
}
}
After building our improvement class we have to include it in the experiment if we want it to use it. For doing so, we should change the line:
ConstructiveMethod<MDPSolution, MDPInstance> constructive = new ConstructiveMethod<MDPSolution, MDPInstance>(new MDPRandomConstructive());
for this one:
MultiStart<MDPSolution, MDPInstance> constructive = new MultiStart(new MDPRandomConstructive(), new MDPLocalSearch());
As you can see, we are telling Multistart to create a MDPRandomConstructive and improve it with the MDPLocalSearch we just built.
Now you will see the importance of the local search with some results. For the default instance set I have executed the experiment with and without the local search and we obtain this results (higher is best):
WITHOUT LOCAL SEARCH default/type1/Type1.1.txt 262,8100 default/type1/Type1.2.txt 213,3200 default/type1/Type1.3.txt 531,4800 default/type1/Type1.4.txt 498,9100 default/type1/Type1.5.txt 959,0400 default/type1/Type1.6.txt 981,8400 default/type1/Type1.7.txt 1479,8700 default/type1/Type1.8.txt 1470,8500 default/type1/Type1.9.txt 2097,8500 default/type1/Type1.10.txt 2110,0700 WITH LOCAL SEARCH default/type1/Type1.1.txt 366,6000 default/type1/Type1.2.txt 355,0900 default/type1/Type1.3.txt 791,7600 default/type1/Type1.4.txt 779,2900 default/type1/Type1.5.txt 1310,7000 default/type1/Type1.6.txt 1399,0500 default/type1/Type1.7.txt 2055,4000 default/type1/Type1.8.txt 2017,7100 default/type1/Type1.9.txt 2939,2700 default/type1/Type1.10.txt 2928,9800