2.6 Algorithm

Now that we know how solvers and algorithms work, we will take a look on how to write an algorithm which will be able to solve these problems. We will not create a very effective algorithm here, just a simple one which works like steepest descend (takes the best improvement) and if there are no more improving steps it ends.

First thing to know is that we need not implement Algorithm from scratch. There is abstract class BaseAlgorithm which we could use to reduce the amount of repetitive work. If we do so, we need to implement only two methods, initialization and optimization step:

package basicusage.algorithm;

import cz.cvut.felk.cig.jcop.algorithm.BaseAlgorithm;
import cz.cvut.felk.cig.jcop.algorithm.CannotContinueException;
import cz.cvut.felk.cig.jcop.algorithm.InvalidProblemException;
import cz.cvut.felk.cig.jcop.problem.ObjectiveProblem;

public class PrimitiveAlgorithm extends BaseAlgorithm {

    public void init(ObjectiveProblem objectiveProblem) throws InvalidProblemException {

    }

    public void optimize() throws CannotContinueException {

    }
}

Note the exceptions those methods raises. InvalidProblemException is used to denote that algorithm required some interface which supplied problem (wrapped in ObjectiveProblem as shown in previous chapter) does not implement. In our example, we will require the problem to supply starting configuration by implementing StartingConfigurationProblem. Second method, Algorithm#optimize() throws a CannotContinueException. This exception is raised when algorithm has nothing more to do. In our example we will throw it when we cannot find a configuration with better fitness than current one. Whenever any exception is raised in Algorithm#init(ObjectiveProblem) or Algorithm#optimize(), solver should immediately stop current solver iteration as if any other condition was met.

Also, since we use BaseAlgorithm we are obliged to do certain steps in Algorithm#init(ObjectiveProblem). List of things required to do is as follows:

  1. Set BaseAlgorithm#fitness (usually to Problem#getDefaultFitness())
  2. Set BaseAlgorithm#bestConfiguration and BaseAlgorithm#bestFitness (if they are available before first optimize step)
  3. Set BaseAlgorithm#problem to problem being currently solved.
  4. Set BaseAlgorithm#label (optional)

Also keep in mind that Algorithm#init(ObjectiveProblem) is called whenever there is need to restart the algorithm, so it should reset all internal variables.

Now we can start. First we check if given ObjectiveProblem holds valid problem:

public void init(ObjectiveProblem objectiveProblem) throws InvalidProblemException {
    if (!objectiveProblem.hasStartingConfiguration()) throw new InvalidProblemException("Our algorithm requires StartingConfigurationProblem interface");
    
    this.problem = objectiveProblem;
}

Once we have our problem checked for type, we will take the fitness and starting configuration. Since it is only configuration we have visited, we will store it to BaseAlgorithm#bestConfiguration. In fact because of nature of our algorithm, we will use BaseAlgorithm#bestConfiguration to store our active configuration all the time. Note that most other algorithms would not take this approach since they usually allows expanding to worse configuration so they have to store active configuration in some other way.

public void init(ObjectiveProblem objectiveProblem) throws InvalidProblemException {
    if (!objectiveProblem.hasStartingConfiguration()) throw new InvalidProblemException("Our algorithm requires StartingConfigurationProblem interface");

    this.problem = objectiveProblem;

    this.fitness = objectiveProblem.getDefaultFitness();

    this.bestConfiguration = objectiveProblem.getStartingConfiguration();
    this.bestFitness = this.fitness.getValue(this.bestConfiguration);
}

Now we have our algorithm prepared, we will implement one optimization step. In each Algorithm#optimize() we expand current best configuration with all operations available for it. If any one is better, take the best one and assign it to BaseAlgorithm#bestConfiguration (along with BaseAlgorithm#bestFitness). If none is better than current best solution, end with CannotContinueException.

In code below, first we create nextBestConfiguration and nextBestFitness to store candidates for next best solution and an OperationIterator it to get operations. Next step is to expand with all operations we got, which is done by expanding as long as iterator provides operations (OperationIterator#hasNext()). Whenever we found a configuration with better fitness, we store it. At least if we did not find any one better, end raising an exception. Otherwise store best found configuration.

public void optimize() throws CannotContinueException {
    Configuration nextBestConfiguration = null;
    double nextBestFitness = 0.0;
    OperationIterator it = this.problem.getOperationIterator(this.bestConfiguration);

    // expand with every operation
    while (it.hasNext()) {
        // expand to next state, calculate fitness
        Configuration configuration = it.next().execute(this.bestConfiguration);
        double fitness = this.fitness.getValue(configuration);

        // found better configuration
        if (((nextBestConfiguration == null) && (fitness > this.bestFitness)) || ((nextBestConfiguration != null) && (fitness > nextBestFitness))) {
            nextBestConfiguration = configuration;
            nextBestFitness = fitness;
        }
    }

    if (nextBestConfiguration == null) {
        throw new CannotContinueException("Cannot continue, no better configuration");
    }

    this.bestConfiguration = nextBestConfiguration;
    this.bestFitness = nextBestFitness;
}

Now we have our algorithm, lets test it how it works. All we require has been shown in previous chapters. We will use Knapsack problem and SimpleSolver solver:

package basicusage.algorithm;

import cz.cvut.felk.cig.jcop.algorithm.Algorithm;
import cz.cvut.felk.cig.jcop.problem.Problem;
import cz.cvut.felk.cig.jcop.problem.knapsack.Knapsack;
import cz.cvut.felk.cig.jcop.result.render.SimpleRender;
import cz.cvut.felk.cig.jcop.solver.SimpleSolver;
import cz.cvut.felk.cig.jcop.solver.Solver;

public class DemoPrimitiveAlgorithm {
    public static void main(String[] args) {
        // create problem & algorithm
        Problem problem = new Knapsack("9000 4 100 18 114 42 136 88 192 3 223");
        Algorithm algorithm = new PrimitiveAlgorithm();

        // create solver
        Solver solver = new SimpleSolver(algorithm, problem);

        // run!
        solver.run();

        // render results
        solver.render();
    }
}

You should be familiar with above, if not, revert to chapters 2.2-2.4. Either way, after you run this piece of code, you should see this in console. If not, you have probably done something wrong in this tutorial.

=== Algorithm PrimitiveAlgorithm [] used on problem Knapsack [line=9000 4 100 18 114 42 136 88 192 3 223] ===
  CPU Time:                       1 [ms]
  System Time:                    1 [ms]
  User Time:                      1 [ms]
  Clock Time:                     1 [ms]
  Optimize counter:               2 [-]
  Optimize/sec (CPU):          2000 [1/s]
  Optimize/sec (Clock):        2000 [1/s]
  Best solution:         Configuration{attributes=[0, 0, 1, 1], operationHistory={0:Empty knapsack created, 1:AddOperation{knapsackItem=KnapsackItem{index=3, weight=3, price=223}}, 2:AddOperation{knapsackItem=KnapsackItem{index=2, weight=88, price=192}}}}
  Depth:                          2 [-]
  Fitness:                    415,0 [-]
  Ended with exception:  cz.cvut.felk.cig.jcop.algorithm.CannotContinueException: Cannot continue, no better configuration

We have found reasonably good solution (not the best one, which is [1, 1, 0, 1] with fitness 473,0) and algorithm ended with an exception that it cannot continue. Both results are as we expected. Source codes of this example could be downloaded here (zip, tgz, 7z).

Full list of bundled algorithms can be found in Appendix B.