Opened 9 years ago

Closed 6 years ago

#1185 closed defect (done)

Moves are applied to different individuals than they were generated for

Reported by: svonolfe Owned by: abeham
Priority: low Milestone: HeuristicLab 3.3.4
Component: Algorithms.SimulatedAnnealing Version: 3.3.4
Keywords: Cc:

Description (last modified by svonolfe)

In the SimulatedAnnealingMainLoop there is an InnerIterations Parameter.

First of all, this number (InnerIterations) of moves are generated. Then, with a certain probability, these moves are applied.

Example scenario: InnerIterations = 5

  • Move 1 is not applied
  • Move 2 is applied (on the original individual)
  • Move 3 is not applied
  • Move 4 is not applied
  • Move 5 is applied (on the individual modified by move 2)

Move 5 was generated for the original individual, however it is applied to the modified one. This is a problem for instance for VRP moves where tours and cities are referenced. This means that the changed individual probably does not contain the tour anymore and thus the move is not valid.

The current solution is, that the VRP-moves contain a clone of the original individual and apply the move on it. However, in that case the usual semantic of the InnerIterations parameter is not followed.

Change History (9)

comment:1 Changed 9 years ago by svonolfe

  • Description modified (diff)
  • Summary changed from Moves werden auf einem anderen Individuum angewandt als das, für welches sie generiert wurden to Moves are applied to different individuals than they were generated for

comment:2 Changed 9 years ago by abeham

Thanks for reporting this issue. You raise a valid point.

It affects all moves that are specific to a certain solution. Moves that are not specific to the solution (like TSP Swap, Inversion, Test Functions additive move,...) are not affected.

The InnerIterations were added mainly to increase performance as SA performed quite slowly when in each iteration there was just one move considered (worse than a GA). But, you can set the parameter to 1 in which case the algorithm works according to your intentions. This is IMO better than to keep the original individual.

Options on how to completely resolve this issue for all moves:

  1. Change SA to remove the inner iterations and make only one move at a time (which slows performance in all cases).
  2. Change the move to be independent of the current solution (if possible) and document that moves would need to have the property to describe a general change.

Do we have more options?

comment:3 Changed 9 years ago by svonolfe

As a workaround the move quality could be set to NaN (not defined) if the move is not valid for the current individual anymore. That way invalid moves would be ignored.

The current solution is to store a clone of the original individual in the move, as stated in the ticket description.

Last edited 9 years ago by svonolfe (previous) (diff)

comment:4 Changed 9 years ago by abeham

  • Priority changed from minor to critical
  • Version changed from 3.3 to 3.3.1

comment:5 Changed 9 years ago by mkommend

  • Priority changed from high to low

comment:6 Changed 8 years ago by svonolfe

Fixed issue in VRP move evaluators in r5821

comment:7 Changed 6 years ago by abeham

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.4
  • Status changed from new to accepted
  • Version changed from 3.3.1 to 3.3.4

The issue of changing SA is treated in #1836 #1983. This will be fixed with SA-3.4. I'm closing this ticket on version 3.3.4, because that's where the only performed change was released with.

comment:8 Changed 6 years ago by abeham

  • Status changed from accepted to readytorelease

comment:9 Changed 6 years ago by abeham

  • Resolution set to done
  • Status changed from readytorelease to closed
Note: See TracTickets for help on using tickets.