ExternalEval for Tabu Search and simulated annealing?

[Mati B.]

Hello,

I would like to perform an external evaluation for Tabu Search and Simulated Annealing.. (I would like to compare a GA to Tabu Search and Simulated Annealing).

What would be the easiest way to conduct this experiment?

Thanks in advance,

Mati

[Mati B.]

The External Evaluation for the GA works great BTW :)

[Andreas Beham]

Hi Mati,

Unfortunately, External Evaluation currently does not support moves. It's a bit tricky to realize this in a nice way. That's because for every move that exists we would need a corresponding external move evaluator. Something which I really want to avoid.

So maybe I can show you how you can implement such a move evaluator for yourself for the one neighborhood that you're using. Can you tell me what kind of MoveGenerator you would want to use?

As a general word of warning though: Moves rely on partial reevaluation to be fast, i.e. only the changed parts are evaluated in most moves. I doubt something like this can be realized for external evaluation problems easily. So each move needs to be evaluated like a full solution and this takes quite some time. I don't think that's a problem with simulated annealing, but more with tabu search.

Sincerely,
Andreas

[Mati B.]

Hi Andreas,

Thanks for your reply. I thought about it and this is what I would like to do.

The Nodes in my neighborhood are Partitions: http://en.wikipedia.org/wiki/Partition_(number_theory).

The neighbors for the partition a1,a2,a3,.ak,a(k+1).,an. (assume a1<=a2<=a3<=..<=an).

for each ak,a(k+1) (such that ak+2<=a(k+1)) there is a neighbor a1,a2,..ak+1,a(k+1)-1,a(k+2)...an (redistribute power)

for each  ak, there is a neighbor 1,a1,a2,..ak-1,..an. (adding an element to the partition)

Any tips on how to implement it in HeuristicLab?

Thanks again in advance,

Mati

[Andreas Beham]

Hi,

Assuming that you have got this running already it looks like you're using an IntegerVectorEncoding with a maximum length that is equal to the number that you're partitioning.

You'll have to create 3 operators if you want to run simulated annealing and 2 further operators if you want to use tabu search:
1. A move generator (this will create move objects and inject them into subscopes of the solution it is applied on)
2. A move evaluator (this will evaluate the quality of a move)
3. A move maker (this will apply the move to the current solution)
4. A tabu move evaluator (this will evaluate whether a move is tabu)
5. A tabu maker (this will declare the chosen move tabu)
You also need two objects:
1. A move object that stores the properties of the move
2. A tabu attribute object that stores attributes of the move that you want to set tabu

I would suggest that you take a look at the implementations in e.g. HeuristicLab.Encodings.RealVector. You certainly will need a different type of move, but it will tell you how the individual classes look like and what they do.

Sincerely,
Andreas