History

Random MDP¶

Intro¶

This page is intended to show you how to start with the Optsicom Optimization Framework by showing an easy example solving the Maximum Diversity Problem (MDP) problem.

The minimum classes you will need in order to get some results are:

MDPProblem
MDPInstance
MDPSolution
MDPInstancesRepository
MDPRandomConstructive
RandomConstructiveExperiment

MDPProblem¶

This class must extend the class Problem from the framework. Here you will set the type of problem, by stating if it is a "max is best" problem or a "min is best" one.

As you can see on the code bellow, INSTANCE is a final static variable, which means it won't change and you will have one and one only instance at a time so we won't mess things up.

package es.optsicom.problem.mdp.approx;

import java.io.File;
import es.optsicom.framework.Problem;
import es.optsicom.framework.instancefile.InstancesRepository;
import es.optsicom.framework.util.BestMode;

public class MDPProblem extends Problem{

    private final static MDPProblem INSTANCE = new MDPProblem();

    public MDPProblem(){
        super("MDP", BestMode.MAX_IS_BEST);
    }

    @Override
    public InstancesRepository getInstancesRepository(File instanceFileDir,
            String useCase) {

        return new MDPInstancesRepository(useCase);
    }

    public static Problem getInstance() {
        return INSTANCE;
    }
}

MDPInstance¶

This class must inherit from AbstractInstance. Here we will store our instance of the problem along with other information about it which may be useful at some time. You will have to override the method getProblem that returns your instance, but you can use other methods like "getM" or "getN" to return the size of the solution and the size of the problem, respectively.

package es.optsicom.problem.mdp.approx;

import es.optsicom.framework.AbstractInstance;
import es.optsicom.framework.Problem;
import es.optsicom.framework.instancefile.InstanceFile;

import es.optsicom.problem.mdp.approx.MDPProblem;
import es.optsicom.problem.mdp.approx.util.Matrix;

public class MDPInstance extends AbstractInstance  {

    String filename;
    Matrix<Double> instance;
    int solutionsize;

    public MDPInstance(InstanceFile instanceFile, String name, Matrix<Double> m, int s) {
        super(instanceFile);
        filename = name;
        instance = m;
        solutionsize = s;

    }

    public int getM(){
        return solutionsize;
    }

    public int getN(){
        return instance.getRows();
    }

    public double getWeight(int node1, int node2){
        return instance.get(node1, node2);
    }

    @Override
    public Problem getProblem()
    {
        return MDPProblem.getInstance();
    }

}

MDPSolution¶

MDPSolution must extend the generic class Solution<MDPInstance>. In this class you will have to decide how to implement your solution. Here you will write for example, a method to calculate the weight of a solution, or create a copy, or compare it with other solutions.

In this example I choosed a double array approximation. In the first array i will store the number of the nodes that are part of my solution and in the second one I will store the values of the nodes compared with the other nodes of the solution. This means that if i add up all the values from the second array, i will have the weight of the solution multiplied by 2. Because if my first node is the node "A", my first value will be the comparation between "A" and all other nodes in solution, but all other nodes will be compared to the node "A" too! I used this implementation because this way i will be able to see which one is the worst node of the solution at a very low cost.

I also added nodes and values get and set methods to use the black box implementation in case i change my mind about the implementation.

package es.optsicom.problem.mdp.approx;
import es.optsicom.framework.*;
import java.util.ArrayList;

public class MDPSolution extends Solution<MDPInstance>{

    private ArrayList<Integer> solution;
    private ArrayList<Double> values; //value of every node so you can always see the worst of them
    private double weight=0;
    private boolean neverset=true;
    private MDPInstance instance;

    @SuppressWarnings("unchecked")
    public MDPSolution(ArrayList<Integer> nodes, MDPInstance instance){
        this.instance = instance;
        solution = (ArrayList<Integer>) nodes.clone();
        values = new ArrayList<Double>(instance.getM());
        for (int i=0; i<instance.getM(); i++){
            values.add((double) 0);
        }
    }

    @Override
    public double getWeight() {
        if (neverset){
            this.calculatePreciseWeight();
            neverset = false;
        }
        return weight;
    }

    public int length(){
        return this.instance.getM();
    }

    @Override
    public Solution<MDPInstance> createCopy() {
        MDPSolution sol = new MDPSolution(this.solution, this.instance);
        for (int i=0; i<this.instance.getM(); i++){
            sol.setValue(i,this.values.get(i));
        }
        sol.setWeight(this.weight);
        return sol;
    }

    @Override
    public MDPInstance getInstance() {
        return instance;
    }

    @Override
    public void calculatePreciseWeight() {
        double plus=0;
        double w=0;
        for (int i = 0; i<instance.getM(); i++){
            values.set(i, (double) 0);
        }
        for (int i = 0; i<instance.getM()-1; i++){
            for (int j=i+1; j<instance.getM(); j++){
                w=instance.getWeight(solution.get(i),solution.get(j));
                values.set(i, values.get(i)+w);
                values.set(j, values.get(j)+w);
            }
            plus += values.get(i);
        }
        //In the iteration the last node's value is not added to plus
        weight = plus + values.get(instance.getM()-1);

        //the node's weight is calculated with all partners so its doubled
        weight = weight/2;

    }

    @Override
    public Object getInfoToSave() {
        // [N1,N2,N3,...,Nn]=Weight
        String s="[";
        for (int i=0; i<instance.getM()-1;i++)
            s+=solution.get(i)+",";
        s+=solution.get(instance.getM()-1)+"]="+weight;

        return s;
    }

    @Override
    public boolean isBetterThan(Solution<MDPInstance> aSolution) {

        return instance.getProblem().getQualityComparator().compare(this, aSolution) > 0;
    }

    public void setWeight(double weight2){
        weight = weight2;
    }

    public void setValue(int i, Double w){
        values.set(i, w);
    }

    public boolean belongs (int obj){
        //True if obj belongs to the solution.
        return solution.contains(obj);
    }

    public double nodeValue (int position, int node){
        //Calculates the potential value of a node in the given position.
        double acum=0;
        for (int i=0; i<solution.size(); i++)
            if (i!=position){
                acum+=instance.getWeight(solution.get(i), node);
            }    
        return acum;
    }

    public void nodeChange(int position, int node){
        // Also updates the Weight
        double oldnodevalue=0;
        double newnodevalue=0;
        double nodefullvalue=0;
        for (int i=0; i<solution.size(); i++)
            if (i!=position){
                oldnodevalue=instance.getWeight(solution.get(i), solution.get(position));
                newnodevalue=instance.getWeight(solution.get(i), node);
                values.set(i, values.get(i)-oldnodevalue+newnodevalue);
                weight=weight-oldnodevalue+newnodevalue;
                nodefullvalue+=newnodevalue;
            }
        solution.set(position, node);
        values.set(position, nodefullvalue);
    }

    public void nodeInsert(int node, int pos){
        solution.set(pos, node);
    }

    public void ValueInsert(double value, int pos){
        values.set(pos, value);
    }

    public int getNode(int pos){
        return solution.get(pos);
    }

    public double getValue(int pos){
        return values.get(pos);
    }

    public int getWorst(){
        int worst=0;
        double worstvalue=99999;
        for(int i=0; i<solution.size();i++){
            if (worstvalue>values.get(i)){
                worst=i;
                worstvalue=this.getValue(i);
            }
        }
        return worst;
    }

}

MDPInstancesRepository¶

This class extends FileInstancesRepository from the framework. Here you will read set how to read a instance from a file and store it in a variable.

I decided to store the instance in a NxN symmetrical matrix so it won't matter when i consult a weight which node I put in first place since it will result in the same value.

package es.optsicom.problem.mdp.approx;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

import es.optsicom.framework.Instance;
import es.optsicom.framework.graph.matrix.FormatException;
import es.optsicom.framework.instancefile.*;
import es.optsicom.problem.mdp.approx.util.Matrix;

public class MDPInstancesRepository extends FileInstancesRepository{

    public MDPInstancesRepository(String useCase) {
        super(useCase);
    }

    @Override
    public Instance loadInstance(InstanceFile instanceFile) throws IOException {

        String name;
        int nodes, solutionsize;
        Matrix<Double> weights;

        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(instanceFile.getFile())));

        try{
            //First Line
            String line = br.readLine();

            if (line == null) {
                throw new FormatException("The file is empty");
            }

            String [] tokens = line.split(" ");
            name = tokens[0];
            nodes = Integer.parseInt(tokens[1]);
            solutionsize = Integer.parseInt(tokens[2]);
            weights = new Matrix<Double>(nodes,nodes);
            weights.init((Double) ((double) 0));

            //Rest of instance
            line = br.readLine();
            do{
                tokens = line.split(" ");
                weights.set(Integer.parseInt(tokens[0]),
                            Integer.parseInt(tokens[1]),
                            Double.parseDouble(tokens[2]));
                weights.set(Integer.parseInt(tokens[1]),
                            Integer.parseInt(tokens[0]),
                            Double.parseDouble(tokens[2]));
                line = br.readLine();
            }while(line != null);
            return new MDPInstance(instanceFile,name,weights,solutionsize);

        }catch (NumberFormatException e) {
            throw new FormatException("File format exception",e);
        }

    }

}

MDPRandomConstructive¶

The constructive class must extend from de generic class AbstractConstructive<MDPSolution, MDPInstance>. We need a constructive to build solutions which will be improved by our metaheuristics. In this case we are building random solutions.

package es.optsicom.problem.mdp.constructives;

import java.util.ArrayList;
import java.util.Random;

import es.optsicom.framework.approx.constructive.AbstractConstructive;
import es.optsicom.problem.mdp.approx.MDPInstance;
import es.optsicom.problem.mdp.approx.MDPSolution;

public class MDPRandomConstructive extends
        AbstractConstructive<MDPSolution, MDPInstance> {

    @Override
    public MDPSolution createSolution() {
        int n;
        // List of selected nodes
        ArrayList<Integer> nodes = new ArrayList<Integer>();

        Random aleatorio = new Random();
        for (;;) {
            do {
                n = aleatorio.nextInt(getInstance().getN());
            } while (nodes.contains(n));

            // Add to the list the selected node
            nodes.add(n);

            // Stops when the number of nodes is the desired number
            if (nodes.size() == getInstance().getM()) {
                break;
            }
        }

        // Returns the solution
        return new MDPSolution(nodes, getInstance());

    }

    @Override
    public void initSolutionCreation() {

    }

    @Override
    public void initSolutionCreationByNum(int numSolutions) {

    }

    @Override
    public void initSolutionCreationByTime(long millis) {

    }

    @Override
    public boolean isDeterminist() {
        return false;
    }

}

RandomConstructiveExperiment¶

package es.optsicom.problem.mdp.constructives;

import java.util.ArrayList;
import java.util.Random;

import es.optsicom.framework.approx.constructive.AbstractConstructive;
import es.optsicom.problem.mdp.approx.MDPInstance;
import es.optsicom.problem.mdp.approx.MDPSolution;

public class MDPRandomConstructive extends
        AbstractConstructive<MDPSolution, MDPInstance> {

    @Override
    public MDPSolution createSolution() {
        int n;
        // List of selected nodes
        ArrayList<Integer> nodes = new ArrayList<Integer>();

        Random aleatorio = new Random();
        for (;;) {
            do {
                n = aleatorio.nextInt(getInstance().getN());
            } while (nodes.contains(n));

            // Add to the list the selected node
            nodes.add(n);

            // Stops when the number of nodes is the desired number
            if (nodes.size() == getInstance().getM()) {
                break;
            }
        }

        // Returns the solution
        return new MDPSolution(nodes, getInstance());

    }

    @Override
    public void initSolutionCreation() {

    }

    @Override
    public void initSolutionCreationByNum(int numSolutions) {

    }

    @Override
    public void initSolutionCreationByTime(long millis) {

    }

    @Override
    public boolean isDeterminist() {
        return false;
    }

}

RandomConstructiveExperiment¶

Finally we get to the main class. Here we will set the specific class we are using on this execution. In case we have more than one constructive, or more than one improvement here we will choose which ones we are using. Here we will also select the set of instances we are using for the execution.

package es.optsicom.problem.mdp.experiment;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

import es.optsicom.framework.analysis.CommonExpAnalysis;
import es.optsicom.framework.approx.ApproxMethod;
import es.optsicom.framework.approx.algorithm.ConstructiveMethod;
import es.optsicom.framework.approx.experiment.ApproxMethodExperiment;
import es.optsicom.framework.instancefile.InstanceFile;
import es.optsicom.framework.instancefile.InstanceFileSet;
import es.optsicom.framework.instancefile.InstancesRepository;
import es.optsicom.problem.mdp.approx.MDPProblem;
import es.optsicom.problem.mdp.approx.MDPInstance;
import es.optsicom.problem.mdp.approx.MDPSolution;
import es.optsicom.problem.mdp.constructives.MDPRandomConstructive;

public class RandomConstructiveExperiment {

static int NUM_EXECUTIONS = 1;
static int MAX_TIME = 2000;

    public static void main(String[] args) {

        // 1. Methods
        List<ApproxMethod<MDPSolution, MDPInstance>> scMethods = new ArrayList<ApproxMethod<MDPSolution, MDPInstance>>();
        ConstructiveMethod<MDPSolution, MDPInstance> constructive = new ConstructiveMethod<MDPSolution, MDPInstance>(new MDPRandomConstructive());
        scMethods.add(constructive);

        // 2. Instances
        InstancesRepository repository = MDPProblem.getInstance().getInstancesRepository();
        InstanceFileSet set = repository.getInstanceFileSet("type1");    
        List<InstanceFile> instanceFiles = set.getInstanceFiles();    

        // 3. Experiment
        ApproxMethodExperiment<MDPSolution, MDPInstance> experiment = new ApproxMethodExperiment<MDPSolution, MDPInstance>(scMethods,NUM_EXECUTIONS);        
        experiment.setInstanceFiles(instanceFiles);        
        experiment.setRecordEvolution(true);

        // 4. execution
        try {
            experiment.executeExperiment();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }        

        // 5. Analysis

        // Getting the directory with the results
        File resultsDir = experiment.getResultsDir();

        // Performing an analysis over the data
        CommonExpAnalysis.showBestValueByMethodAndInstance(resultsDir, MAX_TIME);        

    }    
}

Research » Optsicom » Optsicom Optimization Suite

Wiki

Random MDP¶

Intro¶

MDPProblem¶

MDPInstance¶

MDPSolution¶

MDPInstancesRepository¶

MDPRandomConstructive¶

RandomConstructiveExperiment¶

RandomConstructiveExperiment¶