Implementing variants of tabu search

[huanfachen]

Hi all. I am using tabu search of JAMES ANALYSIS in my project. The current problem is that it is very time consuming to compute the whole neighbourhood and choose the best admissible solution. A possible improvement is to use other stategies of tabu search, for exmaple, first-best-admissible strategy. It selects the first admissible move that provides an improment in the objective value over the current solution. More details can be found on http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.361603. Is there any existing similar strategy in James-core? I am willing to implement it if necessary. Could you give some suggestion on it? It seems that the new feasibleBestAdmTabuSearch class should extend SingleNeighbourhoodSearch or TabuSearch, and implement the searchStep() function, in a simiar way with TabuSearch. Any help is appreciated, thanks!

[hdbeukel]

Hi,

Currently there are no such alternative implementations of tabu search in JAMES, but these could certainly be added. I don't seem to have access to the linked document though (I get the message "Full text unavailable from EThOS. Restricted access.").

Is it correct that the suggested tabu search implementation accepts the first admissible move that provides an improvement, if any, and else accepts the best admissible move as in the default tabu search? I.e. you gain time if an admissible improvement is found (and only then), because the remaining moves are not evaluated. Correct?

To implement this strategy in JAMES I suggest to extend TabuSearch (see TabuSearch.java) which already provides a lot of methods dealing with the tabu memory. You then only have to override the searchStep() method. The first part (lines 183-190) now selects the best admissible move, using the method getBestMove from the NeighbourhoodSearch class. Only moves that are not marked as tabu, or provide an improvement, are considered.

You could implement a similar method that accepts the first admissible improvement, if any. The implementation should be very similar to getBestMove, the only difference being that the loop iterating over all moves stops as soon as an admissible improvement is found. If none is found, all moves are still evaluated, and the best admissible one is selected.

There is one potential issue though. Currently, neighbourhoods generate either a random move, or a collection containing all moves. Tabu search uses the latter. This means that, even if you would accept the first admissible improvement, you would first still have generated all possible moves. Sure you would save (potentially a lot of) time by not evaluating all moves, but their generation might still be a bottleneck. In fact I have plans to refactor the neighbourhoods so that they instead return an iterator traversing all moves (which are lazily generated, i.e. only when actually retrieved/evaluated). See #21. This would be very useful to further optimize your tabu search implementation. I will let you know when/if this has been implemented.

If you have more questions, don't hesitate to post them here. Good luck!

[huanfachen]

Hi @hdbeukel ,

Thanks for your reply! I have found another paper by the same author. Please find attached the two papers.

The author describes some details of the FBA (first-best-admissible) move selection strategy. It selects the first admissible move that provides an improvement in the objective value. If all moves in the candidate list are tired without any improvement, then FBA selects the best recorded non-improveing move, which is the same as ordinary TS.

However, the author has not provide any codes or pseudocode on FBA. Therefore, I am going to implement it, which follows the following steps.

Generate all possible moves.
Shuffle the list of possible moves.
Iterate the list of possible moves. Record the best non-tabu move in the list. If any move provides improvement in the objective value over current solution, the move is selected.  If no such move is found in the list, select the best non-tabu move in the list.

I agree that the generation of all moves might still be a bottleneck. This will be tested in my code.

Another variant that I am interested in is the feature-based tabu search. Typically, the tabu list accepts the recently-visited solutions. However, if the search space is very large and of high dimensionality, it is easy to stay around in the same neighbourhood. An alternative approach is to create a tabu list of changes you have made recently to certain features, aka the recent moves. Do you have any experience with it, or any suggestion on its implementation?

Thanks very much for your help! Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem.pdf Ibrahim_Hassan_Osman-1991-PhD-Thesis.pdf

[huanfachen]

Hi @hdbeukel , I am trying to implement the FirstBestAdmissibleTabuSearch class under algo.tabu. I have several questions and would like to discuss with you.

1. The class FirstBestAdmissibleTabuSearch will extend the TabuSearch and override searchStep() function. To do so, it is needed to change TabuSearch::tabuMemory from private to protected. Is it okay?

2. The class FirstBestAdmissibleTabuSearch needs a new function called getFirstBestAdmissibleMove() which is similar to getBestMove(). To do so, I want to add getFirstBestAdmissibleMove() as a function of NeighbourhoodSearch class. Is it okay?

3. When I read the codes of NeighbourhoodSearch, I found a possible bug in getBestMove(), where bestMoveValidation is not updated if a new best solution is found. In fact, bestMoveValidation is never used in the getBestMove() function.

4. Is it okay if I submit a branch to the repo for your review?

Thanks.

[hdbeukel]

Hi, regarding your first question about feature-based tabu:

Another variant that I am interested in is the feature-based tabu search. Typically, the tabu list accepts the recently-visited solutions. However, if the search space is very large and of high dimensionality, it is easy to stay around in the same neighbourhood. An alternative approach is to create a tabu list of changes you have made recently to certain features, aka the recent moves. Do you have any experience with it, or any suggestion on its implementation?

Yes this is possible by implementing a custom tabu memory. For subset selection I have provided an ID-based memory that does not allow to add/remove items if they have recently been changed (see IDBasedSubsetTabuMemory.java).

[hdbeukel]

Regarding your alternative tabu search:

1. The class FirstBestAdmissibleTabuSearch will extend the TabuSearch and override searchStep() function. To do so, it is needed to change TabuSearch::tabuMemory from private to protected. Is it okay?

Not necessary, you can access the memory using getTabuMemory().

2. The class FirstBestAdmissibleTabuSearch needs a new function called getFirstBestAdmissibleMove() which is similar to getBestMove(). To do so, I want to add getFirstBestAdmissibleMove() as a function of NeighbourhoodSearch class. Is it okay?

Perhaps you need not even create a new method but can add a parameter like acceptFirstImprovement to getBestMove and update it's implementation accordingly?

3. When I read the codes of NeighbourhoodSearch, I found a possible bug in getBestMove(), where bestMoveValidation is not updated if a new best solution is found. In fact, bestMoveValidation is never used in the getBestMove() function.

You are right, this is most likely a bug! Thanks. I have created a separate issue for this bug (#38).

4. Is it okay if I submit a branch to the repo for your review?

Sure, go ahead. I will review your pull request.

[huanfachen]

Regarding the new function:

Perhaps you need not even create a new method but can add a parameter like acceptFirstImprovement to getBestMove and update it's implementation accordingly?

It makes sense. I will write a new getBestMove() function by adding the parameter boolean acceptFirstImprovement, while keeping the existing getBestMove() for compatibility.

Another problem is the shuffling of all moves. In the new getBestMove() function, it is necessary to shuffle the moves before searching the first improvement. However, I do not know any shuffle method on the Collection class. The Collection.shuffle() is used for List objects. Any suggestion on this issue?

[hdbeukel]

You can't shuffle an arbitrary Collection since this does not make sense for an unordered Collection like HashSet. That's why Collections.shuffle is defined for List only. I suggest you don't shuffle in getBestMove but in searchStep() of FirstBestAdmissibleTabuSearch. You can do it there since you get a list from the neighbourhood. I think it's also better to shuffle there specifically because shuffling might not be required/desired in other searches.

[huanfachen]

Agree. That is a good suggestion. Revised.