Opened 3 years ago

Closed 3 years ago

#2251 closed defect (done)

TSPImprover should use InversionManipulator's Apply method

Reported by: abeham Owned by: jkarder
Priority: medium Milestone: HeuristicLab 3.3.11
Component: Problems.TravelingSalesman Version: 3.3.10
Keywords: Cc:

Description

The TSPImprover reimplements an invert functionality (with a rather obscure if condition and some xor trickery) which can be replaced with a simple call to InversionManipulator.Apply(..).

Also it can happen that both breakpoints are the same which wouldn't have any effect on the fitness function. There are more cases of inversion moves that you don't want to sample such as inverting the whole permutation or inverting all but one element in the permutation. Neither of these moves changes the fitness value for the symmetric tsp. I think these are even calculated wrongly. You can see that the improvement is very ineffective if you compare a LocalSearch applying 10000 improvement steps to the ch130 vs 10000 improvement attempts of the TSPImprover. The first can achieve a quality as low as in the 8000s, while the latter hardly goes beyond 30000. I don't think that operator is working as expected.

Change History (9)

comment:1 Changed 3 years ago by jkarder

  • Status changed from new to accepted

comment:2 Changed 3 years ago by jkarder

r11840: used existing classes to reproduce (valid) improvement logic

comment:3 Changed 3 years ago by jkarder

  • Owner changed from jkarder to abeham
  • Status changed from accepted to reviewing

comment:4 follow-up: Changed 3 years ago by abeham

  • Owner changed from abeham to jkarder
  • Status changed from reviewing to assigned

Thanks for fixing this. It looks cleaner, and shorter now (plus, you can now blame it on me if this operator doesn't work).

There are a couple more things that I noted. You write

var solution = CurrentScope.Variables[SolutionParameter.ActualName].Value as Permutation;

Again here:

CurrentScope.Variables.Add(new Variable("LocalEvaluatedSolutions", ImprovementAttempts));

You could just assign this to a corresponding lookup parameter. Also the question is how much sense it makes to just take one variable and write it to the scope. Where is that variable used? You're not counting here. And nobody that is using your operator is knowing that it will output LocalEvaluatedSolutions as there is no parameter for that.

I saw this behavior in all ISingleObjectiveImprovementOperators. This is a rather non-standard way to read and write variables. Is there a specific reason? You would be doing that through a call to ActualValue of a corresponding parameter.

I also found a few inconsistencies in how parameter types are being used in this operator:

  • The ImprovementAttemptsParameter should be a ValueLookupParameter<T>, you may want to specify that parameter in an algorithm
  • The SolutionParameter sould be a LookupParameter<T>, you will not want to set a permutation as a value to this operator (nobody else could access it when it's not in the scope). This parameter is also in the interface as an IValueLookupParameter<T>. Also the name SolutionParameter doesn't really seem appropriate since a "Solution" refers to the object that contains the representation as well as the problem data.
  • The DistanceMatrixParameter is a corner-case. I am fine with LookupParameter, but in a way ValueLookup would also make sense.
  • The CurrentScopeParameter should be removed. The original purpose of this parameter was to indicate a change to the scope structure which is not the case here.

Typcially in an operator, you would be using following types:

  • An ILookupParameter<T> if the variable is always coming from/going to the scope or context.
  • An IValueParameter<T> if the variable is never coming from/going to the scope or context.
  • An IValueLookupParameter<T> if the variable can be coming from/going to the scope or context, but can be overwritten (mostly used for parameters that are only read).

In my opinion we would only need one type of local search operators in HeuristicLab. Currently we have:

  • ISingleObjectiveImprovmentOperator
  • ILocalImprovementOperator

If we make a major increment we should unify these.

comment:5 Changed 3 years ago by ascheibe

I put your last point on the next-gen HL agenda.

comment:6 in reply to: ↑ 4 Changed 3 years ago by jkarder

I will address this in #2304.

Replying to abeham:

Thanks for fixing this. It looks cleaner, and shorter now (plus, you can now blame it on me if this operator doesn't work).

There are a couple more things that I noted. You write

var solution = CurrentScope.Variables[SolutionParameter.ActualName].Value as Permutation;

Again here:

CurrentScope.Variables.Add(new Variable("LocalEvaluatedSolutions", ImprovementAttempts));

You could just assign this to a corresponding lookup parameter. Also the question is how much sense it makes to just take one variable and write it to the scope. Where is that variable used? You're not counting here. And nobody that is using your operator is knowing that it will output LocalEvaluatedSolutions as there is no parameter for that.

I saw this behavior in all ISingleObjectiveImprovementOperators. This is a rather non-standard way to read and write variables. Is there a specific reason? You would be doing that through a call to ActualValue of a corresponding parameter.

I also found a few inconsistencies in how parameter types are being used in this operator:

  • The ImprovementAttemptsParameter should be a ValueLookupParameter<T>, you may want to specify that parameter in an algorithm
  • The SolutionParameter sould be a LookupParameter<T>, you will not want to set a permutation as a value to this operator (nobody else could access it when it's not in the scope). This parameter is also in the interface as an IValueLookupParameter<T>. Also the name SolutionParameter doesn't really seem appropriate since a "Solution" refers to the object that contains the representation as well as the problem data.
  • The DistanceMatrixParameter is a corner-case. I am fine with LookupParameter, but in a way ValueLookup would also make sense.
  • The CurrentScopeParameter should be removed. The original purpose of this parameter was to indicate a change to the scope structure which is not the case here.

Typcially in an operator, you would be using following types:

  • An ILookupParameter<T> if the variable is always coming from/going to the scope or context.
  • An IValueParameter<T> if the variable is never coming from/going to the scope or context.
  • An IValueLookupParameter<T> if the variable can be coming from/going to the scope or context, but can be overwritten (mostly used for parameters that are only read).

In my opinion we would only need one type of local search operators in HeuristicLab. Currently we have:

  • ISingleObjectiveImprovmentOperator
  • ILocalImprovementOperator

If we make a major increment we should unify these.

comment:7 Changed 3 years ago by jkarder

  • Status changed from assigned to reviewing

comment:8 Changed 3 years ago by jkarder

  • Status changed from reviewing to readytorelease

comment:9 Changed 3 years ago by jkarder

  • Resolution set to done
  • Status changed from readytorelease to closed

r11897: merged r11840 into stable

Note: See TracTickets for help on using tickets.