Your Solution object represents a solution to your problem. It is not necessarily a good solution - just a solution.
OpenTS imposes no restriction on how you define your solution or what data structures you use because OpenTS never manipulates your Solution objects directly. It relies on your Move object to modify the Solution, your ObjectiveFunction object to evaluate the Solution, and your Solution itself to clone it.
You may find it useful to subclass (extend) the SolutionAdapter class
since it automatically handles the three required methods
getObjectiveValue()
, setObjectiveValue(...)
,
and clone()
.
SolutionAdapter properly clones the objective value array, but it is essential that you properly clone your data structures as well. For an excellent discussion of cloning techniques, see this Java Developer Connection Tech Tip.
It is a common mistake to copy references to data instead of
copying the data itself. The easiest place to make this mistake
is with arrays. Suppose you have an int
array called sack
that maintains your solution state - perhaps it's an array of zero/one
variables in a knapsack problem. It would be tempting to implement
a clone()
method like this in your Solution object:
Wrong Way To Do It:
public Object clone() { TSPSolution copy = (TSPSolution)super.clone(); copy.sack = this.sack; return copy; } // end clone
All you've done is give your newly-cloned Solution a pointer to the original sack array. If you were to modify one Solution by manipulating the array, you would incorrectly be modifying the other Solution as well.
Instead, make sure you make a complete copy of your data structures.
In case where your data structures are representing by simple
arrays of primitives, you should have no problems using a
clone()
method like this:
Right Way To Do It:
public Object clone() { TSPSolution copy = (TSPSolution)super.clone(); copy.sack = (int[])this.sack.clone(); return copy; } // end clone
Another common way to represent your data is with a
java.util.ArrayList
or java.util.LinkedList
.
These are fairly efficient data structures depending on your problem type
and can be a real headache-saver for problems like the Traveling
Salesman Problem or Vehicle Routing Problem.
Suppose you create your own Vehicle.java and Customer.java classes each containing relevant information such as speed, endurance, location, capacity, demand, etc. An easy way to represent a tour would be to use Java's lists to store the customers you plan to visit in the order you plan to visit them.
In fact, you may end up with an ArrayList of ArrayLists
to account for multiple vehicles. Again, be sure that you think
through your clone()
method and make sure that you're cloning
deep enough to ensure independence in your solution objects.
In this case, it's probably okay if you don't clone the Vehicle and Customer objects since they don't change, but you will need to clone the ArrayLists.
OpenTS expects an objective/constraint penalties function to be able to evaluate a solution's worth. OpenTS will pass the ObjectiveFunction a Solution and optionally pass a proposed Move. If the passed move is not null, then the evaluation should consider the effect that executing this move on the solution would have before evaluating it.
If you can use some sort of incremental evaluation technique, this will save you time. If you must operate on the solution to actually calculate its value, you must return the solution to its original state before the method returns.
It may be helfpul to give yourself some helper methods in your
ObjectiveFunction to separate the incremental evaluation from the
absolute evaluation. You might setup your evaluate(...)
method like this:
It May Help to Separate Your Logic:
public double[] evaluate( Solution soln, Move proposedMove ) { if( proposedMove == null ) return evaluateAbsolutely( soln ); else return evaluateIncrementally( soln, proposedMove ); }
Then you can deal with the two pieces of logic separately. If you cannot incrementally evaluate your solution but are forced to modify the Solution object first, make sure your Move object has a way to undo its operation:
Always Return the Solution to its Original State:
private double[] evaluateIncrementally( Solution soln, Move proposedMove ) { proposedMove.operateOn( soln ); double[] val = evaluateAbsolutely( soln ); proposedMove.undoOperation( soln ); return val; }
It is a common mistake to try to reuse arrays of doubles and mess it up (it's possible, but you have to be careful). When you're first writing your code and aren't fine tuning it to this level, it's easiest to evaluate your objective function values with scalars and then return a fresh array:
Avoid Reusing Arrays:
public double[] evaluate( Solution soln, Move proposedMove ) { double val1 = ...; double val2 = ...; return new double[]{ val1, val2 }; }
The array of returned values will later be compared lexicographically in the classic "goal-programming" style. If instead you want some goals to overpower higher goals, use the style of weighting the levels with appropriate values.
In this trivial example, suppose your ObjectiveFunction returns an array of three doubles in an assignment problem where the first value in the array (Goal #1) is the number of customers in a day who wait longer than 10 minutes on hold waiting for one of the available Tech Support personnel (objective value #2: minimize hiring), and the third value is the total cost of the operation.
|
|
We see in the tables above that with the lexicographical comparison of ObjectiveFunction values, that Goal #1 is absolutely more important than the rest of the goals which is why, in Solution Pair A, Soln 2 beats Soln 1 despite Soln 1's lower cost and number of people hired.
In Solution Pair B we see that there's a tie on Goal #1, so OpenTS compares the next goal and declares Soln 1 the winner for hiring fewer people. If this goal had been a tie, OpenTS would have moved on to the next goal.
Although all numbers are stored and calculated as doubles, they are cast to floats before being compared. This helps avoid the problems where two "equal" values stored as doubles differ by 0.000000000001 or some ridiculously small value.
When OpenTS considers whether or not some solution X is better than some other solution Y, the answer is No if the two objective function values result in ties for all of the goals.
By implementing and registering as a TabuSearchListener
your objects can react dynamically to the search as it progresses.
This gives you an easy way to trigger techniques such as
Reactive/Adaptive Tabu Lists, Strategic Oscillation, Path Relinking,
and Restarts.
When registered, your object will receive the following events:
The first three events listed above will be fired in that order, should more than one need to be fired in a given iteration.
In OpenTS versions prior to v1.0-exp2,
if you changed the current or best solution using
the setCurrentSolution( ... )
or
setBestSolution( ... )
methods while responding to
these events, the appropriate event would be fired again, resulting
in an infinite loop. This "feature" has been removed since what
it offers in the rare case that it's useful can be accomplished
more safely in other ways.
You register as a TabuSearchListener by implementing the interface and registering with the TabuSearch object after you instantiate it:
Register As a TabuSearchListener
import org.coinor.opents.*; public class MySearchProgram implements TabuSearchListener { ... TabuSearch ts = new MultiThreadedTabuSearch( ... ); ts.addTabuSearchListener( this ); ... }
You may find it easier to use Java's anonymous inner classes along with the TabuSearchAdapter class. With this design pattern, you only have to implements methods for the events you're actually interested in:
Use TabuSearchAdapter with Anonymous Inner Classes
TabuSearch ts = new MultiThreadedTabuSearch( ... ); ts.addTabuSearchListener( new TabuSearchAdapter() { public void unimprovingMoveMade( TabuSearchEvent evt ) { ... } } );
You might find it particularly useful to have your tabu list or
objective function objects implement TabuSearchListener.
Here we extend the included SimpleTabuList
to make
it a reactive tabu list:
Reactive Tabu List
import org.coinor.opents.*; public class MyTabuList extends SimpleTabuList implements TabuSearchListener { public final static int MAX_TENURE = 30; public void newBestSolutionFound( TabuSearchEvent evt ) { // Decrease tenure setTenure( Math.max( 1, (int)( 0.75 * getTenure() ) ) ); } public void unimprovingMoveMade( TabuSearchEvent evt ) { // Increase tenure setTenure( Math.min( MAX_TENURE, getTenure() + 2 ); } // We're not using these events public void newCurrentSolutionFound( TabuSearchEvent evt ){} public void tabuSearchStarted( TabuSearchEvent evt ){} public void tabuSearchStopped( TabuSearchEvent evt ){} }
The tabuSearchStarted
and tabuSearchStopped
events are most important when using the MultiThreadedTabuSearch
implemenation of the TabuSearch
spec.
When startSolving()
is called on a MultiThreadedTabuSearch
object, control returns immediately to the calling thread, and the
tabu search runs on a newly-created thread.
If you have another part of your code, such as a progress bar or some other indicator, that needs to know when your tabu search has started - or more importantly, finished - register as a listener with the tabu search object and respond to the appropriate event.
In a well-designed GUI application, you should always offload long tasks such as a tabu search to another thread, and these two events will help you manage that task.
Here's a code fragment showing how we notify the user the tabu search has finished:
Notify When Done
TabuSearch ts = new MultiThreadedTabuSearch( ... ); final java.awt.Component parent = ...; // Your root window or similar ts.addTabuSearchListener( new TabuSearchAdapter() { public void tabuSearchStopped( TabuSearchEvent evt ) { TabuSearch theTS = (TabuSearch)evt.getSource(); Solution best = theTS.getBestSolution(); final String msg = "Done. Best solution: " + best; SwingUtilities.invokeLater( new Runnable() { public void run() { JOptionPane.showMessageDialog( parent, msg ); } }); } });