VariableNeighborhoodSearch doesn't react to disabled analyzers

[abeham]

Analyzers in a VNS are executed even when all of them are unchecked.

I also got an exception when I created a new VNS, assigned a QAP (or a TSP) to it, and unchecked all analyzers. If you run this it should say:

OperatorExecutionException: An exception was thrown by the operator "BestQAPSolutionAnalyzer": An item with the same key has already been added.
   at HeuristicLab.SequentialEngine.SequentialEngine.Run(CancellationToken cancellationToken) in C:\Users\abeham\Work\HL3\trunk\sources\HeuristicLab.SequentialEngine\3.3\SequentialEngine.cs:line 75
   at HeuristicLab.Core.Engine.Run(Object state) in C:\Users\abeham\Work\HL3\trunk\sources\HeuristicLab.Core\3.3\Engine.cs:line 153
   at System.Threading.Tasks.Task.Execute()

If you check it, it works fine. I have no explanation for that behavior.

[svonolfe]

Did you also uncheck the analyzers in the local improvement operator?

Unfortunately I cannot reproduce the exception. I created a new VNS, added a new QAP, loaded the bur26a instance and unchecked all analyzers.

[svonolfe]

I think I located the cause of the exception... The analyzer in the local improvement is executed on a sub scope and the main loop analyzer on the global scope. This is a desired behavior, since in the local improvement we only want to analyze this part of the scope tree.

The QAP analyzer checks:

QAPAssignment assignment = BestSolutionParameter.ActualValue;
if (assignment == null) {
  results.Add(new Result("Best QAP Solution", assignment));
}

Now, if you enable the local analyzer and disable the one in the main loop, the value of the parameter (BestSolutionParameter) is written to the local scope and also the result is written.

If you then enable the global one, the global anaylzer does not find the value of the parameter and tries to add a new result. Then the exception occurs: "An item with the same key has already been added." This is because it already exists in the results.

Steps to reproduce:

1. Open the VNS sample with the TSP
2. Disable all analyzers in the main loop
3. Run the algorithm until the result "Best TSP Solution" appears
4. Pause the algorithm
5. Enable the BestTSPSolutionAnalyzer in the main loop
6. Start the algorithm
7. After the local iterations (150) have completed, the main loop analyzer is executed and the exception is thrown

To solve this problem, we would have to adapt the BestSolution analyzers in my point of view. The name of the result "Best QAP Solution" should not be hardcoded but added as a parameter. The we could change it in the local analyzer to "Best local QAP Solution".

Another solution would be to force all analyzers that are active in the local improvement to also be active in the main loop.

What do you think?

[abeham]

You're right that I did not uncheck the analyzers in the local improvement operator. But the problem is easier to reproduce in my eyes:

1. Create a new VNS and load a TSP
2. Disable all analyzers in the VNS's Analyzer parameter
3. Run the algorithm

Thanks for looking into this problem a bit deeper already. But, let's take a step back and look at this problem from a further point of view. Because, I think the actual issue is a bit more profound. What we want to do here is actually not supported as it wasn't intended to work. Certainly we see that it does work so there's some need for explanation.

Here are my thoughts on this:

What is the original problem? The assumption when coding analyzers was that there is only one analyzer which writes to its results. So the best solution analyzers assume that if its BestSolutionParameter returns null, the result also cannot exist. This assumption however breaks in this case as we have the same analyzer in multiple places, still writing to the same results.

We've got a similar situation in the IslandGeneticAlgorithm in which the solution was to collect the results of each island separately and have the analyzers write to their own results collection. These island results are then collected and inserted into the global results.

The other solution that you mention would be to allow parameterization of the result names of all analyzers. I agree that this would be nice, but currently that's a difficult thing as there doesn't quite exist a pattern on how to do it. There's the possibility of using a separate ValueParameter<StringValue> for every result, a LookupParameter<QAPAssignment> (but only ever use the TranslatedName of that parameter), or a new type of parameter ResultsParameter<QAPAssignment> that would be a parameter of a collection and return a variable in that collection. I think some discussion is necessary on how to proceed here in future versions.

We probably won't arrive at a very nice solution in the short time for the next release, so I suggest to patch the problem by disabling all analyzers in the LocalSearchImprovementOperator and SimulatedAnnealingImprovementOperator by default. We can live with the global analyzers and if any user requires advanced tracking of the local search phase she can enable them (and we can tell her that there's some caution to be taken). If you have more time you could consider collecting the results of the local search phase to a separate results collection similar to how this is done in the IslandGeneticAlgorithm. I don't particular like the idea of having results duplicated in the results view once with and without "Local..." prefix. In the end they're the same thing and the BestSolution of the VNS is also that of the LocalSearch, so I don't see a reason to have two results. The third solution if you will is to change the best solution analyzers to give up the assumption that the result does not exist when the assignment is null and check for these cases independently of each other.

Sorry for the rather lengthy explanation.

[svonolfe]

Thanks very much for the detailed analysis. I have disabled the local improvement operators by default in r8118 and updated the VNS sample in r8119.

I will leave the ticket open and for a future release we could collect the results in a separate collection as done in the island GA. This would be the best solution in my point of view.

[abeham]

This has already been released in 3.3.7. I'm closing this and opening follow-up ticket #2188.